You are viewing a plain text version of this content. The canonical link for it is here.
Posted to jira@kafka.apache.org by "zheguang (via GitHub)" <gi...@apache.org> on 2025/11/18 09:49:59 UTC
[PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
zheguang opened a new pull request, #20911:
URL: https://github.com/apache/kafka/pull/20911
This PR address KAFKA-19782 by replacing hashset with trie for prefix search.
Previously the Authorizer uses character-by-character comparisons to search for prefix patterns to deny within a set of allowed literals. This prefix search is suboptimal when the set contains many strings that share the same prefix -- the complexity is linear in number of strings sharing a prefix. By constrast, a trie will reduce the complexity to constant.
In particular, this PR uses Apache Commons Collection's PATRICIA Trie, which is an efficient algorithm that offers worst-case `O(k)` operations, where `k` is the largest key bit-length.
The resulting code appears also clearer in logic.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-5612409959
This PR is being marked as stale since it has not had any activity in 90 days. If you
would like to keep this PR alive, please leave a comment asking for a review. If the PR has
merge conflicts, update it with the latest from the base branch.
<p>
If you are having difficulty finding a reviewer, please reach out on the
[mailing list](https://kafka.apache.org/contact).
<p>
If this PR is no longer valid or desired, please feel free to close it. If no activity
occurs in the next 30 days, it will be automatically closed.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3630086677
A label of 'needs-attention' was automatically added to this PR in order to raise the
attention of the committers. Once this issue has been triaged, the `triage` label
should be removed to prevent this automation from happening again.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "ekuvardin (via GitHub)" <gi...@apache.org>.
ekuvardin commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3546784388
Hi seems we make parallel changes :)
https://github.com/apache/kafka/pull/20912
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "ekuvardin (via GitHub)" <gi...@apache.org>.
ekuvardin commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3547010418
Also take a look that this PR connected with big problem with benchmarks
1. They are unstable and should be run and fixed also
2. Error should be(oh.. it's the most dangerous zone) no more than 10 % percent in jmh.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-4677220693
A label of 'needs-attention' was automatically added to this PR in order to raise the
attention of the committers. Once this issue has been triaged, the `triage` label
should be removed to prevent this automation from happening again.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3590948759
A label of 'needs-attention' was automatically added to this PR in order to raise the
attention of the committers. Once this issue has been triaged, the `triage` label
should be removed to prevent this automation from happening again.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-4036059156
A label of 'needs-attention' was automatically added to this PR in order to raise the
attention of the committers. Once this issue has been triaged, the `triage` label
should be removed to prevent this automation from happening again.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-4656258368
This PR is being marked as stale since it has not had any activity in 90 days. If you
would like to keep this PR alive, please leave a comment asking for a review. If the PR has
merge conflicts, update it with the latest from the base branch.
<p>
If you are having difficulty finding a reviewer, please reach out on the
[mailing list](https://kafka.apache.org/contact).
<p>
If this PR is no longer valid or desired, please feel free to close it. If no activity
occurs in the next 30 days, it will be automatically closed.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-4020990443
This PR is being marked as stale since it has not had any activity in 90 days. If you
would like to keep this PR alive, please leave a comment asking for a review. If the PR has
merge conflicts, update it with the latest from the base branch.
<p>
If you are having difficulty finding a reviewer, please reach out on the
[mailing list](https://kafka.apache.org/contact).
<p>
If this PR is no longer valid or desired, please feel free to close it. If no activity
occurs in the next 30 days, it will be automatically closed.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3578838925
A label of 'needs-attention' was automatically added to this PR in order to raise the
attention of the committers. Once this issue has been triaged, the `triage` label
should be removed to prevent this automation from happening again.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "zheguang (via GitHub)" <gi...@apache.org>.
zheguang commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3549423052
> Hi seems we make parallel changes :) on the same day #20912
>
> Maybe we should keep just one branch, and I'll merge the benchmarks into it and fix the bug with them?
Small world :) Sure, happy to collaborate. I'll take a look at your benchmark changes. Once ready, are you able to push those benchmark changes to this branch? Otherwise I am also happy to merge your benchmark changes. Let me know!
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "ekuvardin (via GitHub)" <gi...@apache.org>.
ekuvardin commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-3552045164
@lucasbru
Hi Lucas, could you help us out?
We accidentally created two PRs for the same task, and we’ll actually be working together on it going forward.
Right now we have a question about which approach is better.
Could you coordinate us a bit and take a look at both PRs?
One PR introduces a PatriciaTrie-based Set on top of PatriciaTrie, - https://github.com/apache/kafka/pull/20911 (this pr)
and the other one uses a PatriciaTrie Map. - https://github.com/apache/kafka/pull/20912
In your opinion, which option is better to use? Both approaches work.
By the way, I’ve already written to a colleague from the library Apache common collections and suggested adding a PatriciaTrie Set, but he’s very busy and hasn’t responded yet - https://github.com/apache/commons-collections/pull/589
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] KAFKA-19782: improve Authorizer by using (Patricia) trie [kafka]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #20911:
URL: https://github.com/apache/kafka/pull/20911#issuecomment-5643114323
A label of 'needs-attention' was automatically added to this PR in order to raise the
attention of the committers. Once this issue has been triaged, the `triage` label
should be removed to prevent this automation from happening again.
--
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.
To unsubscribe, e-mail: jira-unsubscribe@kafka.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org