[
https://issues.apache.org/jira/browse/KAFKA-17423?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Viktor Somogyi-Vass updated KAFKA-17423:
----------------------------------------
Labels: (was: kip)
> 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: 0.9.0.2, 3.8.0
> Reporter: Claude Warren
> Priority: Major
>
> KAFKA-17316 introduces extensible StandardAuthorizer. This change is to
> provide a Trie based authorizer that extends the StandardAuthorizer.
> Tests indicate that such an authorizer is at least an order of magnitude
> faster than the current authorizer.
>
> This change is dependent upon KAFKA-17316
>
> 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||
> |1000|0.0057 ± 0.0011|0.0032 ± 0.0006|0.0052 ± 0.001|0.0044 ± 0.0016|
> |8000|0.0178 ± 0.0011|0.0085 ± 0.0006|0.012 ± 0.0009|0.0076 ± 0.0009|
> |27000|0.0614 ± 0.0009|0.0299 ± 0.0005|0.0402 ± 0.0006|0.0254 ± 0.0004|
> |64000|0.1625 ± 0.0021|0.0771 ± 0.0022|0.098 ± 0.0026|0.0645 ± 0.0013|
> |125000|0.3591 ± 0.0032|0.1632 ± 0.0019|0.1942 ± 0.0037|0.1304 ± 0.0068|
> !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)
