[GitHub] [kafka] d8tltanc edited a comment on pull request #9485: KAKFA-10619: Idempotent producer will get authorized once it has a WRITE access to at least one topic

[GitBox]

d8tltanc edited a comment on pull request #9485:
URL: https://github.com/apache/kafka/pull/9485#issuecomment-740501882


   
![image](https://user-images.githubusercontent.com/31675100/101454358-b62cfd00-38e5-11eb-9eee-200604895b16.png)
   Chart description (from left to right)
   1. The performance comparison btw the trunk's and my branch's of 
`aclAuthorizer#updateCache`.
   2. The performance comparison btw the trunk's and my branch's of 
`aclAuthorizer#authorize`.
   3. The performance comparison btw my branch's `aclAuthorizer#authorize` and 
`aclAuthorizer#authorizeByResourceType`
   
   1 and 2 indicate that the newly added `resourceCache` doesn't add too much 
overhead to the time complexity. The time complexity increasing is constant (my 
branch doubled the hashmap add/remove operation).
   
   In chart 3, the horizontal axis "Percentage of dominant deny" means the 
percentage of "allow resource" which has a "deny resource" added to the 
authorizer.
   
   The benchmark used in chart 3 has the "dominant deny" distributed evenly.
   
   Define the average of resource name length is L, the expected "allow 
resource" in the "allow resource set" to iterate is E_A, the time complexity of 
my implementation of `authorizeByResourceType` is L * E_A. How to compute E_A?
   
   Define the "percentage of dominant deny" as P. Every resource in the "allow 
resource" set has the probability (100-P)/100 to be allowed by the authorizer. 
So 
   
   expected_elements_iterated_in_the_allow_resource_set.
   
   1. The time complexity of `AclAuthorizer#authorize` is irrelevant to the 
"percentage of dominant deny"
   2. If we treat L as a constant, the time complexity of 
`AclAuthorizer#authorizeByResourceType` is only relevant to E_A, where E_A = 
1/[(100-P)/100] = 100/(100-p), which is a hyperbola. Chart 3 can confirm this.
   
   
![image](https://user-images.githubusercontent.com/31675100/101465299-9f41d700-38f4-11eb-9415-5eb9a6a0b5f3.png)
   
   From the benchmark, when P = 99.99, if "dominant deny" distributed evenly, 
authorizeByResourceType only took 2.5ms. In the worst case, if "dominant deny" 
distributed unevenly or P = 100, the API will take ~40ms, but this is very 
unlikely.


----------------------------------------------------------------
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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org