Claude Warren created KAFKA-17423:
-------------------------------------
Summary: Replace StandardAuthorizer with Trie implementation
Key: KAFKA-17423
URL: https://issues.apache.org/jira/browse/KAFKA-17423
Project: Kafka
Issue Type: Improvement
Components: core
Affects Versions: 3.8.0, 0.9.0.2
Reporter: Claude Warren
KAFKA-17316 introduces extensible StandardAuthorizer. This change is to
provide a Trie based authorizer that extends the StandardAuthorizer.
Tests indicate that such an authroizer is 2 orders of magnitude faster than the
current authorizer.
h2. Trie vs KRAFT Standard Search times
h3. Evaluation of Head wildcard
I developed some quick tests using random words and creating literal ACLs by
combining three words with hyphens. Prefixed ACLs were created by removing the
last word from the literal acl. Head wildcard ACLs were created by removing
the first word from the literal ACLs and replacing it with an asterisk "*".
All literal ACLs were searched for in each test. Timing was recorded in nano
seconds and converted to seconds for this table. The results here show that
the Trie search beats the Standard search for both literal and prefix searches.
In addition the new head wildcard search is approximately as fast as the
current literal search.
||Number of Acls||Standard
literal||Standard
prefix||Trie
literal||Trie
prefix||Trie
head wildcard||
|1000|0.0057 ± 0.0011|0.0032 ± 0.0006|0.0052 ± 0.001|0.0044 ± 0.0016|0.0117 ±
0.0029|
|8000|0.0178 ± 0.0011|0.0085 ± 0.0006|0.012 ± 0.0009|0.0076 ± 0.0009|0.0213 ±
0.0023|
|27000|0.0614 ± 0.0009|0.0299 ± 0.0005|0.0402 ± 0.0006|0.0254 ± 0.0004|0.0793 ±
0.0053|
|64000|0.1625 ± 0.0021|0.0771 ± 0.0022|0.098 ± 0.0026|0.0645 ± 0.0013|0.1794 ±
0.0091|
|125000|0.3591 ± 0.0032|0.1632 ± 0.0019|0.1942 ± 0.0037|0.1304 ± 0.0068|0.3484
± 0.0022|
!https://cwiki.apache.org/confluence/download/attachments/303794855/head-tail.png?version=1&modificationDate=1722351326000&api=v2|height=250!
h3. JMS Test Suite
All tests were run using the standard JMS test suite from the Kafka test
library. All values are for runs comprising 50 ACLs with 100K Resources. Each
test was executed 15 times and the median score and error calculated. The
maximum memory consumption for each test is also presented.
Both implementations pass all the Authorizer, and AuthorizerProperty tests.
Test were executed on a Thinkpad with Ryzen pro 7 running Ubuntu 22.04.4 LTS
with a total of 28544904 Kb memory. The test system was unable to run the
Standard tests for 200K resoources as it ran out of memory, though it was able
to do so for the Trie tests.
Tests do not include any head wildcard tests as they are not supported by
Standard implementation.
h4. Acls Iterator
This test retrieves an iterator over the collection of ACLs that is filtered by
an AclBindingFilter. This is a measure of how fast the system can scan all the
ACLs looking for specific data. ACLs are not searched for by resource name.
|Deny % | |0|20|50|90|99|99.9|99.99|100|
|Standard|ms/op|636.370 ± 8.419|744.872 ± 10.324|1168.908 ± 221.970|1790.758
± 312.487|2039.684 ± 371.359|1915.952 ± 248.867|2094.022 ± 346.507|2154.379 ±
245.848|
|total
KiB|6,993,926.242|7,315,873.742|9,935,234.141|9,884,250.906|9,867,064.727|9,837,963.148|9,901,205.375|9,863,042.500|
|Trie |ms/op|779.097 ± 16.420|931.984 ± 22.113|1218.173 ± 18.023|1571.095 ±
40.815|1603.855 ± 16.527|1659.850 ± 17.646|1688.720 ± 53.368|1720.753 ±
38.237|
|total KiB|5,756,430.383|7,048,136.438|7,136,180.156
|8,626,626.211|9,839,865.086|8,495,973.211|9,954,063.266|8,602,073.469|
!https://cwiki.apache.org/confluence/download/attachments/303794855/ITER_Ex.png?version=1&modificationDate=1722333121000&api=v2|height=250!!https://cwiki.apache.org/confluence/download/attachments/303794855/ITER_Mem.png?version=1&modificationDate=1722333131000&api=v2|height=250!
h4. Authorize by Resource Type
This tests a case where we check if the caller is authorized to perform a given
operation on at least one resource of the given type. This is a case of
looking for resources of a specific type that the principal can access. It is
similar to the ACL iterator test but stops on the first approval.
|Deny % | |0|20|50|90|99|99.9|99.99|100|
|Standard|ms/op| 1186.324 ± 42.475|1360.158 ± 81.720|2004.596 ±
51.584|2411.931 ± 104.194|2718.558 ± 77.745|2627.366 ± 91.740 |2466.940 ±
160.395|2420.297 ± 75.351|
|total
KiB|6,331,528.313|6,971,241.883|7,622,133.336|9,905,097.813|10,048,529.578|10,122,265.617|9,679,931.570|10,532,133.234|
|Trie|ms/op|1.090 ± 0.014 |1.319 ± 0.009|1.787 ± 0.026|2.296 ±
0.049|2.167 ± 0.082|2.340 ± 0.065|2.373 ± 0.072|2.004 ± 0.049|
|total
KiB|5,862,343.477|7,046,550.586|5,869,397.102|5,872,297.258|7,487,485.984|3,550,240.320|3,23,9351.586|5,416,103.469|
!https://cwiki.apache.org/confluence/download/attachments/303794855/ART_Ex.png?version=1&modificationDate=1722332811000&api=v2|height=250!!https://cwiki.apache.org/confluence/download/attachments/303794855/ART_Mem.png?version=1&modificationDate=1722332820000&api=v2|height=250!
h4. Authorizer
This is the standard authorization request. It attempts to discover if the
principal has the requested action granted on a specific ACL.
|Deny % | |0|20|50|90|99|99.9|99.99|100|
|Standard|ms/op|1.785 ± 0.052|2.592 ± 0.215|2.800 ± 0.194|3.180 ±
0.225|3.183 ± 0.183|3.837 ± 0.386|4.283 ± 0.422| 4.765 ± 0.690|
|total
KiB|6,673,559.914|7,587,627.867|8,150,199.570|8,301,222.914|8,330,982.719|8,320,206.023|8,326,969.375|8,318,412.859|
|Trie|ms/op|0.036 ± 0.001 |0.041 ± 0.002|0.049 ± 0.001|0.068 ±
0.003|0.062 ± 0.003|0.061 ± 0.003|0.063 ± 0.004|0.069 ± 0.002|
|total
KiB|6,969,258.734|7,092,858.141|7,696,657.625|7,815,699.461|7,871,944.383|7,875,301.055|7,917,752.148|7,874,817.164|
h1.
!https://cwiki.apache.org/confluence/download/attachments/303794855/Auth_Ex.png?version=1&modificationDate=1722332958000&api=v2|height=250!!https://cwiki.apache.org/confluence/download/attachments/303794855/Auth_Mem.png?version=1&modificationDate=1722332967000&api=v2|height=250!
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
