8000 0817 improve topic-index search by zmstone · Pull Request #11495 · emqx/emqx · GitHub
[go: up one dir, main page]
Skip to content

0817 improve topic-index search #11495

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 10 commits into from
Closed

0817 improve topic-index search #11495

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
ae094e3
chore: fix a typo in log message
zmstone Aug 15, 2023
6b152b3
test: add more debug output
zmstone Aug 20, 2023
f4c8c6b
refactor(topic_index): optimize trie-search performance
zmstone Aug 17, 2023
a1e6635
refactor(topic_index): no forced ceiling entry in index table
zmstone Aug 23, 2023
a30d87e
refactor(topic_index): remove more unnecessary next calls
zmstone Aug 24, 2023
62423b0
refactor(topic_index): less special handling for leading $ words
zmstone Aug 24, 2023
cf45e80
feat(topicidx): iterate on trie search implementation
keynslug Aug 24, 2023
ecac673
refactor(topic_index): simplify compare function
zmstone Aug 25, 2023
2332eb2
docs: refine code comments
zmstone Aug 25, 2023
8089639
chore(topic_index): add topic validation
zmstone Aug 25, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
chore(topic_index): add topic validation
  • Loading branch information
@zmstone
zmstone committed Aug 25, 2023
commit 808963900a8cc9235e81da270af5c6a7fb486818
24 changes: 14 additions & 10 deletions apps/emqx/src/emqx_trie_search.erl
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -113,7 +113,7 @@
%% @doc Make a search-key for the given topic.
-spec make_key(emqx_types:topic(), ID) -> key(ID).
make_ke 8000 y(Topic, ID) when is_binary(Topic) ->
Words = words(Topic),
Words = filter_words(Topic),
case emqx_topic:wildcard(Words) of
true ->
%% it's a wildcard
Expand Down Expand Up @@ -171,7 +171,7 @@ matches(Topic, NextF, Opts) ->

%% @doc Entrypoint of the search for a given topic.
search(Topic, NextF, Opts) ->
Words = words(Topic),
Words = topic_words(Topic),
Base = base_init(Words),
ORetFirst = proplists:get_bool(return_first, Opts),
OUnique = proplists:get_bool(unique, Opts),
Expand Down Expand Up @@ -309,7 +309,7 @@ compare([W | Filter], [W | Words], RPrefix) ->
compare(Filter, Words, [W | RPrefix]);
compare([F | _Filter], [W | _Words], _RPrefix) when W < F ->
lower;
compare([F | _Filter], [W | _Words], RPrefix) ->
compare([_F | _Filter], [W | _Words], RPrefix) ->
% NOTE
% Topic: a/b/z
% Filter: +/+/x
Expand All @@ -324,18 +324,22 @@ match_add(K, Acc) when is_list(Acc) ->
match_add(K, first) ->
throw({first, K}).

-spec words(emqx_types:topic()) -> [word()].
words(Topic) when is_binary(Topic) ->
-spec filter_words(emqx_types:topic()) -> [word()].
filter_words(Topic) when is_binary(Topic) ->
% NOTE
% This is almost identical to `emqx_topic:words/1`, but it doesn't convert empty
% tokens to ''. This is needed to keep ordering of words consistent with what
% `match_filter/3` expects.
[word(W) || W <- emqx_topic:tokens(Topic)].
[word(W, filter) || W <- emqx_topic:tokens(Topic)].

-spec word(binary()) -> word().
word(<<"+">>) -> '+';
word(<<"#">>) -> '#';
word(Bin) -> Bin.
topic_words(Topic) when is_binary(Topic) ->
[word(W, topic) || W <- emqx_topic:tokens(Topic)].

word(<<"+">>, topic) -> error(badarg);
word(<<"#">>, topic) -> error(badarg);
word(<<"+">>, filter) -> '+';
word(<<"#">>, filter) -> '#';
word(Bin, _) -> Bin.

%% match non-wildcard topics
match_topics(Topic, {Topic, _} = Key, NextF, Acc) ->
Expand Down
32 changes: 32 additions & 0 deletions apps/emqx/test/emqx_trie_search_tests.erl
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,32 @@
%%--------------------------------------------------------------------
%% Copyright (c) 2023 EMQ Technologies Co., Ltd. All Rights Reserved.
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%% http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%--------------------------------------------------------------------

-module(emqx_trie_search_tests).

-include_lib("eunit/include/eunit.hrl").

topic_validation_test() ->
NextF = fun(_) -> '$end_of_table' end,
Call = fun(Topic) ->
emqx_trie_search:match(Topic, NextF)
end,
?assertError(badarg, Call(<<"+">>)),
?assertError(badarg, Call(<<"#">>)),
?assertError(badarg, Call(<<"a/+/b">>)),
?assertError(badarg, Call(<<"a/b/#">>)),
?assertEqual(false, Call(<<"a/b/b+">>)),
?assertEqual(false, Call(<<"a/b/c#">>)),
ok.
0