[
https://issues.apache.org/jira/browse/KAFKA-17423?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Claude Warren updated KAFKA-17423:
----------------------------------
Description:
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!
was:
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 2 orders 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||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!
> 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)
