I have updated the KIP with results from the Trie implementation and they are dramatic to say the least. For most searches they are at least an order of magnitude faster and use less memory. The wildcard search is not a regular expression but rather a file type wild card (*=1 or more character, ?=1 character).
Code is available on my personal branch [1]. It is not fully documented and does not meet the checkstyle requirements yet. I also modified the jmh tests to run the Trie tests and limit the test to the single case mentioned in the KIP documentation. If there are no issues with this code, I will complete the documentation and fix the checkstyle and then open a pull request. Claude [1] https://github.com/Claudenw/kafka/pull/new/KIP-1042_Trie_Implementation On Wed, Jul 3, 2024 at 2:21 PM Claude Warren, Jr <claude.war...@aiven.io> wrote: > I think that if we put in a trie based system we should be able to halve > the normal searhc times and still be able to locate wild card matches very > quickly. Users should be warned that "head wildcard" matches are slow and > to use them sparingly. I am going to see if I can work out how to do > wildcard matches within the trie. > > But in all cases can show that the trie is faster than the current > implementation. > > Claude > > > > On Wed, Jun 19, 2024 at 7:53 PM Muralidhar Basani > <muralidhar.bas...@aiven.io.invalid> wrote: > >> There are some test results mentioned in the Test Plan section of the Kip, >> but we need to do more testing with various patterns and permission types. >> As mentioned in the discuss thread, the trie implementation could >> potentially surpass the current speed of ACL match. >> >> However, we can only accurately assess the results after updating the >> actual classes and analysing them with AuthorizerBenchmark. >> >> Thanks, >> >> Murali >> >> On Mon, 17 Jun 2024 at 20:39, Colin McCabe <cmcc...@apache.org> wrote: >> >> > My concern is that the extra complexity may actually slow us down. In >> > general people already complain about the speed of ACL matches, and >> adding >> > another "degree of freedom" seems likely to make things worse. >> > >> > It would be useful to understand how much faster or slower the code is >> > with the propsed changes, versus without them. >> > >> > best, >> > Colin >> > >> > >> > On Mon, Jun 17, 2024, at 01:26, Muralidhar Basani wrote: >> > > Hi all, >> > > >> > > I would like to call a vote on KIP-1042 which extends creation of acls >> > with >> > > MATCH pattern type. >> > > >> > > KIP - >> > > >> > >> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls >> > > >> > > Discussion thread - >> > > https://lists.apache.org/thread/xx3lcg60kp4v34x0j9p6xobby8l4cfq2 >> > > >> > > Thanks, >> > > Murali >> > >> >
