zheguang opened a new pull request, #20911: URL: https://github.com/apache/kafka/pull/20911
This PR address KAFKA-19782 by replacing hashset with trie for prefix search. Previously the Authorizer uses character-by-character comparisons to search for prefix patterns to deny within a set of allowed literals. This prefix search is suboptimal when the set contains many strings that share the same prefix -- the complexity is linear in number of strings sharing a prefix. By constrast, a trie will reduce the complexity to constant. In particular, this PR uses Apache Commons Collection's PATRICIA Trie, which is an efficient algorithm that offers worst-case `O(k)` operations, where `k` is the largest key bit-length. The resulting code appears also clearer in logic. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
