Re: Contribution to RAT

[Claude Warren, Jr]

The development of RAT is moving along and the format of the XML has
changed.  We now detect multiple licenses within a single file, so this
report will need to change too.  I have put it on the list of things to
change.  It might make it into 0.17 which has massive changes already,
mostly around including and excluding files for processing.

Claude

On Sat, Sep 14, 2024 at 9:48 PM Colin McCabe  wrote:

> Hi Claude,
>
> Well, as you said, there is no licensing issue, since they're both Apache
> :)
>
> I don't see why anyone in Apache Kafka would object to moving or
> duplicating this file to be within the RAT project. The place to ask is
> probably in the RAT project itself -- I don't know if this is something
> they'd like to include or not (hopefully yes.)
>
> cheers,
> Colin
>
>
> On Thu, Aug 15, 2024, at 04:54, Claude Warren, Jr wrote:
> > Greetings,
> >
> > I have been working on Apache RAT recently and I noticed that Kafka has a
> > very nice XSLT to convert the Rat output to an HTML document.
> >
> > I know there is not a legal or licensing issue but I am asking if there
> are
> > any objections to my taking the .gradle/resources/rat-output-to-html.xsl
> > file into the Apache RAT project so that we can have a nice HTML output
> > available to all users?
> >
> > Thanks,
> > Claude
>

Re: Possible bug in Authorize by ResourceTypeQue

[Claude Warren, Jr]

Followup2: your answer speaks directly to "WRITE" access.  My example was
READ access.  So the question method is answering then is: Does the user
have access to READ any TOPIC?  And that is further restricted by the
requestContext host is it not?


On Tue, Sep 3, 2024 at 2:10 PM Claude Warren, Jr 
wrote:

> Followup:  If ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true" then
> authorizeByResourceType should return true in all cases since the user
> would have access for any operation on any undefined topic?
>
>
> On Tue, Sep 3, 2024 at 2:08 PM Claude Warren, Jr 
> wrote:
>
>> I am working on a replacement for the StandardAuthorizer and my
>> implementation DENIED while the standard implementation ALLOWED.  In
>> reading the specs I thought it should be DENIED.  But your statement makes
>> it clear that I misread.
>>
>> Thank you,
>> Claude
>>
>> On Tue, Sep 3, 2024 at 1:14 PM Rajini Sivaram 
>> wrote:
>>
>>> Hi Claude,
>>>
>>> `authorizeByResourceType` doesn't grant access to any specific topic, it
>>> grants access to idempotent write if the user has access to write to any
>>> topic (which may or may not exist). In this case,
>>> ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true", so `User:alice` can
>>> write to a topic that doesn't start with `foo` and hence
>>> `authorizeByResourceType` should be ALLOWED. What was the behaviour you
>>> observed?
>>>
>>> Regards,
>>>
>>> Rajini
>>>
>>>
>>> On Tue, Sep 3, 2024 at 12:22 PM Claude Warren  wrote:
>>>
>>> > *Setup:*
>>> > Superuser = "User:superman"
>>> >
>>> > ACLs added to system
>>> > new StandardAcl(TOPIC, "foo", PREFIXED, "User:alice", WILDCARD, READ,
>>> DENY)
>>> > new StandardAcl(TOPIC, "foobar", LITERAL, "User:alice", WILDCARD, READ,
>>> > ALLOW)
>>> > new StandardAcl(TOPIC, "foo", PREFIXED, "User:bob", WILDCARD, READ,
>>> ALLOW)
>>> >
>>> > ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true"
>>> >
>>> > AuthorizerContext requestContext = MockAuthorizableRequestContext with
>>> > principal = User:alice
>>> > host = InetAddress.getLocalHost()
>>> >
>>> >
>>> > *Method Call:*
>>> >
>>> > authorizer.authorizeByResourceType(requestContext, READ, TOPIC)
>>> >
>>> > *Question:*
>>> >
>>> > Should the result be true because there is a LITERAL READ ALLOW on
>>> "foobar"
>>> > or should the result be false because there is an overriding PREFIXED
>>> READ
>>> > DENY on "foo" ?
>>> >
>>> >
>>> >
>>> > --
>>> > LinkedIn: http://www.linkedin.com/in/claudewarren
>>> >
>>>
>>

Re: Possible bug in Authorize by ResourceTypeQue

[Claude Warren, Jr]

Followup:  If ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true" then
authorizeByResourceType should return true in all cases since the user
would have access for any operation on any undefined topic?


On Tue, Sep 3, 2024 at 2:08 PM Claude Warren, Jr 
wrote:

> I am working on a replacement for the StandardAuthorizer and my
> implementation DENIED while the standard implementation ALLOWED.  In
> reading the specs I thought it should be DENIED.  But your statement makes
> it clear that I misread.
>
> Thank you,
> Claude
>
> On Tue, Sep 3, 2024 at 1:14 PM Rajini Sivaram 
> wrote:
>
>> Hi Claude,
>>
>> `authorizeByResourceType` doesn't grant access to any specific topic, it
>> grants access to idempotent write if the user has access to write to any
>> topic (which may or may not exist). In this case,
>> ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true", so `User:alice` can
>> write to a topic that doesn't start with `foo` and hence
>> `authorizeByResourceType` should be ALLOWED. What was the behaviour you
>> observed?
>>
>> Regards,
>>
>> Rajini
>>
>>
>> On Tue, Sep 3, 2024 at 12:22 PM Claude Warren  wrote:
>>
>> > *Setup:*
>> > Superuser = "User:superman"
>> >
>> > ACLs added to system
>> > new StandardAcl(TOPIC, "foo", PREFIXED, "User:alice", WILDCARD, READ,
>> DENY)
>> > new StandardAcl(TOPIC, "foobar", LITERAL, "User:alice", WILDCARD, READ,
>> > ALLOW)
>> > new StandardAcl(TOPIC, "foo", PREFIXED, "User:bob", WILDCARD, READ,
>> ALLOW)
>> >
>> > ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true"
>> >
>> > AuthorizerContext requestContext = MockAuthorizableRequestContext with
>> > principal = User:alice
>> > host = InetAddress.getLocalHost()
>> >
>> >
>> > *Method Call:*
>> >
>> > authorizer.authorizeByResourceType(requestContext, READ, TOPIC)
>> >
>> > *Question:*
>> >
>> > Should the result be true because there is a LITERAL READ ALLOW on
>> "foobar"
>> > or should the result be false because there is an overriding PREFIXED
>> READ
>> > DENY on "foo" ?
>> >
>> >
>> >
>> > --
>> > LinkedIn: http://www.linkedin.com/in/claudewarren
>> >
>>
>

Re: Possible bug in Authorize by ResourceTypeQue

[Claude Warren, Jr]

I am working on a replacement for the StandardAuthorizer and my
implementation DENIED while the standard implementation ALLOWED.  In
reading the specs I thought it should be DENIED.  But your statement makes
it clear that I misread.

Thank you,
Claude

On Tue, Sep 3, 2024 at 1:14 PM Rajini Sivaram 
wrote:

> Hi Claude,
>
> `authorizeByResourceType` doesn't grant access to any specific topic, it
> grants access to idempotent write if the user has access to write to any
> topic (which may or may not exist). In this case,
> ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true", so `User:alice` can
> write to a topic that doesn't start with `foo` and hence
> `authorizeByResourceType` should be ALLOWED. What was the behaviour you
> observed?
>
> Regards,
>
> Rajini
>
>
> On Tue, Sep 3, 2024 at 12:22 PM Claude Warren  wrote:
>
> > *Setup:*
> > Superuser = "User:superman"
> >
> > ACLs added to system
> > new StandardAcl(TOPIC, "foo", PREFIXED, "User:alice", WILDCARD, READ,
> DENY)
> > new StandardAcl(TOPIC, "foobar", LITERAL, "User:alice", WILDCARD, READ,
> > ALLOW)
> > new StandardAcl(TOPIC, "foo", PREFIXED, "User:bob", WILDCARD, READ,
> ALLOW)
> >
> > ALLOW_EVERYONE_IF_NO_ACL_IS_FOUND_CONFIG = "true"
> >
> > AuthorizerContext requestContext = MockAuthorizableRequestContext with
> > principal = User:alice
> > host = InetAddress.getLocalHost()
> >
> >
> > *Method Call:*
> >
> > authorizer.authorizeByResourceType(requestContext, READ, TOPIC)
> >
> > *Question:*
> >
> > Should the result be true because there is a LITERAL READ ALLOW on
> "foobar"
> > or should the result be false because there is an overriding PREFIXED
> READ
> > DENY on "foo" ?
> >
> >
> >
> > --
> > LinkedIn: http://www.linkedin.com/in/claudewarren
> >
>

Re: [DISCUSS] KAFKA-17316 and KAFKA-17423

[Claude Warren, Jr]

Colin,

I can see that it makes sense to replace the StandardAuthorizer so that
there are not 2 implementations.  However, I think the testing framework
should remain so that in future new improved implementations of
StandardAuthorizerData can be easily implemented and tested.

I will put forward a pull request to satisfy KAFKA-17423 that contains only
the new implementation.

Claude

On Mon, Sep 2, 2024 at 9:09 AM Claude Warren, Jr 
wrote:

> I have been working on implementing a Trie structure to store ACLs and
> improve the performance in the metadata/authorization code.  The upshot of
> this was that I found it very difficult to determine if the implementation
> was correctly reimplementing the current implementation.
>
> My goal was to simply change the StandardAuthorizerData implementation and
> leave the rest of the code as is.  However, there were no abstracted tests
> that would allow me to test this.
>
> KAFKA-17316 addresses this issue by creating some internal interfaces for
> the "metadata/authorizer" package.  The one change to the
> StandardAuthorizer was to implement the"authorizeByResourceType" defined in
> the "org.apache.kafka.server.authorizer.Authorizer" interface by passing
> the request down to the AuthorizerData implementation.
>
> This change allowed me to create three test implementations.  One that
> implemented "authorizeByResourceType" as it is in the released code base,
> one that verified that the StandardAuthorizerData implementation did not
> change the expected results, and one that showed the Trie implementation in
> KAFKA-17423 was also correct.
>
> I think that retaining the work in KAFKA-17316 makes sense as when the
> next faster implementation comes along we can drop in the replacement and
> verify that it works correctly.
>
> KAFKA-17423 builds on KAFKA-17316 by implementing a Trie based
> AuthorizerData implementation.  By splitting the data into a Trie format
> the search for matching ACLs is improved by an order of magnitude.  The
> trie implementation allows us to quickly locate the candidate ACLs by
> splitting them into groups based upon the similarity of the resource name.
> In addition since we are moving through the trie based on resource name we
> have several advantages:
>
>1. If we encounter a matching DENY while descending the Trie we can
>stop as it overrides anything that may be found at lower levels.
>2. We only look for LITERAL matches on the descent.  If we reach a
>matching resource name or a leaf node we know there are no LITERAL matches.
>3. If we don't have a DENY or a LITERAL match we walk back up the path
>checking the nodes from the descent looking for a PREFIX match.  The
>advantage here is that we don't have to search again but can simply retrace
>the path using the Trie structure.
>
> I believe that #1 and #2 above account for a significant portion of the
> speed increase as we do not have to reposition within a sorted list of all
> ACLs using a binary search.
>
> Finally, I think that we should prohibit the use of the java.util.stream
> classes within the authorizer due to hot path speed considerations.  The
> only existing code that uses streams within that package were test cases.
> We can prohibit the use by a simple checkstyle prohibition.  Doing so will
> short circuit any misguided potential changes.
>
> Thoughs?
> Claude
>
>

[DISCUSS] KIP-1042: Support for GLOBs when creating new acls

[Claude Warren, Jr]

After some discussion about the earlier KIP-1042 we have rewritten it to
focus on the implementation of a GLOB pattern type.  Please review and
comment.

We have removed all discussion of the Trie implementation and focus on what
is required for the GLOB implementation.  The KIP does assume that the Trie
implementation will be available.

Thank you,
Claude

[DISCUSS] KAFKA-17316 and KAFKA-17423

[Claude Warren, Jr]

I have been working on implementing a Trie structure to store ACLs and
improve the performance in the metadata/authorization code.  The upshot of
this was that I found it very difficult to determine if the implementation
was correctly reimplementing the current implementation.

My goal was to simply change the StandardAuthorizerData implementation and
leave the rest of the code as is.  However, there were no abstracted tests
that would allow me to test this.

KAFKA-17316 addresses this issue by creating some internal interfaces for
the "metadata/authorizer" package.  The one change to the
StandardAuthorizer was to implement the"authorizeByResourceType" defined in
the "org.apache.kafka.server.authorizer.Authorizer" interface by passing
the request down to the AuthorizerData implementation.

This change allowed me to create three test implementations.  One that
implemented "authorizeByResourceType" as it is in the released code base,
one that verified that the StandardAuthorizerData implementation did not
change the expected results, and one that showed the Trie implementation in
KAFKA-17423 was also correct.

I think that retaining the work in KAFKA-17316 makes sense as when the next
faster implementation comes along we can drop in the replacement and verify
that it works correctly.

KAFKA-17423 builds on KAFKA-17316 by implementing a Trie based
AuthorizerData implementation.  By splitting the data into a Trie format
the search for matching ACLs is improved by an order of magnitude.  The
trie implementation allows us to quickly locate the candidate ACLs by
splitting them into groups based upon the similarity of the resource name.
In addition since we are moving through the trie based on resource name we
have several advantages:

   1. If we encounter a matching DENY while descending the Trie we can stop
   as it overrides anything that may be found at lower levels.
   2. We only look for LITERAL matches on the descent.  If we reach a
   matching resource name or a leaf node we know there are no LITERAL matches.
   3. If we don't have a DENY or a LITERAL match we walk back up the path
   checking the nodes from the descent looking for a PREFIX match.  The
   advantage here is that we don't have to search again but can simply retrace
   the path using the Trie structure.

I believe that #1 and #2 above account for a significant portion of the
speed increase as we do not have to reposition within a sorted list of all
ACLs using a binary search.

Finally, I think that we should prohibit the use of the java.util.stream
classes within the authorizer due to hot path speed considerations.  The
only existing code that uses streams within that package were test cases.
We can prohibit the use by a simple checkstyle prohibition.  Doing so will
short circuit any misguided potential changes.

Thoughs?
Claude

Re: [VOTE] KIP-1042: Support for wildcard when creating new acls

[Claude Warren, Jr]

Colin,

I would like to leave the framework that is in KAFKA-17316 as it makes
testing the new implementations easier.  But let's discuss that elsewhere
(I will start another discussion for 17316 and 17423 together).

PatternType.GLOB makes sense, I will adjust the KIP to use that
terminology.  I understand from some of my compatriots that there is a
desire to allow GLOBs in resource names, Kafka Principals and Host names.
(Basically all the non-enum based ACL data).

With the Trie implementation for the resource names we can force the trie
to put the '*' and '?' on individual nodes when it encounters them.  This
makes them a natural pivot point when traversing the trie, It is how I
implemented it initially.  The idea is that the more "specific" an ACL is
the better a match it is assumed to be.  So the searching algorithm is
start descending the trie until a matching DENY ACL, a matching LITERAL
ACL, or leaf node is found.  A DENY ACL yields a DENY, a matching LITERAL
ACL yields its specified result.  A non matching leaf node requires further
searching.  We start back up the path starting with the leaf node, looking
for matching PREFIXED nodes.  If a GLOB symbol ('*' or '?') is located as
the child of the current node check for a GLOB match.  Continue until a
PREFIXED ACL match, GLOB ACL Match or the root node is encountered.
PEFIXED and GLOB return their specified value, root return a NOT FOUND
state.

With respect to the Principal and Host names,  I have been recently working
on Apache Rat moving maven based file exclusion to the core and have found
that the Plexus pattern match and selector code is very fast and would
probably not be a significant change in performance from straight check to
GLOB checking.  In these cases we would create what the plexus code calls a
"MatchPattern" and for collections of patterns "MatchPatterns".  We can
then simply check if the requested ACL matches the pattern.  The
MatchPattern will return the original text so we can perform the standard
string match we do today if desired.

I think that the KIP will need updating and that this will require changes
in the Client, Server and Metadata components.  I also believe that we
should prohibit the use of "java.util.stream" classes in the
metadata/authorizer package.  Currently it is only used in a couple of test
cases, but the overhead of streams would kill the authorizer performance so
best to restrict it before someone brings code.

Thoughts?

Claude



On Fri, Aug 30, 2024 at 4:38 PM Colin McCabe  wrote:

> Hi Claude,
>
> I think this is great work. Speeding up the Authorizer will be a big win
> for us.
>
> I don't think we need to add additional interfaces for this, though. Just
> get rid of the old slower implementation that I wrote, and replace it with
> your newer, faster one.
>
> Also, I think we should continue the discussion about globs... after all,
> it is the topic of this KIP! (You are calling it "wildcards" but I don't
> think that is good terminiology since it will cause confusion with the
> existing "*" wildcard). Anyway, earlier I requested that you add
> PatternType.GLOB and use it for these things. Does that make sense? I don't
> see another path to doing it compatibly. I certainly wouldn't want to
> create a "Python 2 vs. Python 3" type situation where people get stuck on
> an older authorizer fork because the new one requires globs and they can't
> handle that. No authorizer forks (or at least, not for things like this.)
>
> best,
> Colin
>
>
> On Fri, Aug 30, 2024, at 01:32, Claude Warren, Jr wrote:
> > I made it easier to replace the existing StandardAuthorizerData with a
> > different implementation in order show the Trie implementation met all
> the
> > requirements of the StandardAuthorizerData and could be replaced without
> > changing the StandardAuthorizer implementation.
> >
> > Replacing the current StandardAuthorizerData with a Trie
> > implementation makes sense because it is an order of magnitude faster.
> > This means that when we go to implement the Wildcard types we can perform
> > the search in times that are equivalent to the literal search times in
> the
> > current StandardAuthorizerData implementation.
> >
> > The changes for the first pull request is to create an interface for
> > AuthorizerData and create an "authorizeByResourceType" method within that
> > interface.  This adds an initial implementation in StandardAuthorizerData
> > that mirrors the default implementation found in the Authorizer
> interface.
> >
> > The Trie implementation is not dependent upon other classes local to
> > StandardAuthorizerData other than the MatchingRule and 

Re: [VOTE] KIP-1042: Support for wildcard when creating new acls

[Claude Warren, Jr]

I made it easier to replace the existing StandardAuthorizerData with a
different implementation in order show the Trie implementation met all the
requirements of the StandardAuthorizerData and could be replaced without
changing the StandardAuthorizer implementation.

Replacing the current StandardAuthorizerData with a Trie
implementation makes sense because it is an order of magnitude faster.
This means that when we go to implement the Wildcard types we can perform
the search in times that are equivalent to the literal search times in the
current StandardAuthorizerData implementation.

The changes for the first pull request is to create an interface for
AuthorizerData and create an "authorizeByResourceType" method within that
interface.  This adds an initial implementation in StandardAuthorizerData
that mirrors the default implementation found in the Authorizer interface.

The Trie implementation is not dependent upon other classes local to
StandardAuthorizerData other than the MatchingRule and some of its
implementations which are now found in the AuthorizerData interface instead
of the StandardAuthorizerData implementation.  Obviously it is dependent
upon AuthorizationResult, AclBinding, KafkaPrincipal and other classes that
are defined elsewhere.

In addition, abstract test cases are implemented to validate that any
replacement implementations yield the same results as the original
StandardAuthorizerData.

I hope that this aswages any concerns that you may have had,
Claude

On Thu, Aug 29, 2024 at 6:51 PM Colin McCabe  wrote:

> On Thu, Aug 29, 2024, at 01:34, Claude Warren, Jr wrote:
>
> Colin,
>
> Thanks for your insightful comments.  I came to the same conclusion.
>
> I do have 2 Jira tickets to simplify some of this.
>
> 1)  KAFKA-17316 <https://issues.apache.org/jira/browse/KAFKA-17316> -
> Makes developing a new Authorizer by creating a new implementation of the
> StandardAuthorizerData easier.  Basically adds interfaces, abstract classes
> and lots of tests.
>
> 2) KAFKA-17423 <https://issues.apache.org/jira/browse/KAFKA-17423> -
> Builds on KAFKA-17316 by creating a Trie implementation (without the new
> wildcards from KIP-1042).  This provides an order of magnitude faster
> processing of ACL requests.
>
> My plan is to get these through the process, so I have a better
> understanding of the Kafka development process, and then rework KIP-1042 to
> create a new PatternType with wildcard processing.
>
> I would appreciate your feedback on the above tickets if you have the time.
>
>
> Hi Claude,
>
> Thanks for the response. However, I don't want to fork the
> StandardAuthorizer. I would be -1 on that since it would greatly enlarge
> our maintenance burden, for no good reason. And if we did fork it, I
> wouldn't want the forked version to depend on the internal classes of the
> original one, since that would make evolving either one much more difficult.
>
> We should be able to add wildcards to the existing authorizer without too
> much trouble, just by adding a new type alongside LITERAL, PREFIXED.
> Perhaps GLOB ? We always planned on adding more types, to cover exactly
> this scenario.
>
> best,
> Colin
>
> Claude
>
> On Fri, Aug 23, 2024 at 9:43 PM Colin McCabe  wrote:
>
> On Sat, Jul 27, 2024, at 04:20, Claude Warren, Jr wrote:
> > I have updated the KIP with results from the Trie implementation and they
> > are dramatic to say the least.  For most searches they are at least an
> > order of magnitude faster and use less memory.  The wildcard search is
> not
> > a regular expression but rather a file type wild card (*=1 or more
> > character, ?=1 character).
> >
>
> Hi Claude,
>
> One issue here is that your change is incompatible. For example, if I have
> a consumer group named '?', and an ALLOW ACL  for '?', this change alters
> the meaning of that ACL. Previously it just ALLOWed '?' Now it allows any
> single-character group. This obviously could be a major security issue for
> people doing upgrades.
>
> (This wouldn't be an issue if we restricted consumer group names to a
> sensible set of characters, like we did with topics. But that ship has
> sailed...)
>
> If you want to add new behavior in a backwards-compatible fashion, your
> best bet probably is to create a new PatternType. Unfortunately this makes
> the complexity issue worse, but I don't see a way around it. Perhaps we can
> deprecate LITERAL and PREFIXED at some future date, if this wildcard thing
> makes them unecessary.
>
> Another issue I see, somewhat related, is that Authorizers are pluggable,
> and probably won't be updated all at once to support this new type. That
> should be fine, but we should document the

Re: [VOTE] KIP-1042: Support for wildcard when creating new acls

[Claude Warren, Jr]

Colin,

Thanks for your insightful comments.  I came to the same conclusion.

I do have 2 Jira tickets to simplify some of this.

1)  KAFKA-17316 <https://issues.apache.org/jira/browse/KAFKA-17316> - Makes
developing a new Authorizer by creating a new implementation of the
StandardAuthorizerData easier.  Basically adds interfaces, abstract classes
and lots of tests.

2) KAFKA-17423 <https://issues.apache.org/jira/browse/KAFKA-17423> - Builds
on KAFKA-17316 by creating a Trie implementation (without the new wildcards
from KIP-1042).  This provides an order of magnitude faster processing of
ACL requests.

My plan is to get these through the process, so I have a better
understanding of the Kafka development process, and then rework KIP-1042 to
create a new PatternType with wildcard processing.

I would appreciate your feedback on the above tickets if you have the time.

Claude

On Fri, Aug 23, 2024 at 9:43 PM Colin McCabe  wrote:

> On Sat, Jul 27, 2024, at 04:20, Claude Warren, Jr wrote:
> > I have updated the KIP with results from the Trie implementation and they
> > are dramatic to say the least.  For most searches they are at least an
> > order of magnitude faster and use less memory.  The wildcard search is
> not
> > a regular expression but rather a file type wild card (*=1 or more
> > character, ?=1 character).
> >
>
> Hi Claude,
>
> One issue here is that your change is incompatible. For example, if I have
> a consumer group named '?', and an ALLOW ACL  for '?', this change alters
> the meaning of that ACL. Previously it just ALLOWed '?' Now it allows any
> single-character group. This obviously could be a major security issue for
> people doing upgrades.
>
> (This wouldn't be an issue if we restricted consumer group names to a
> sensible set of characters, like we did with topics. But that ship has
> sailed...)
>
> If you want to add new behavior in a backwards-compatible fashion, your
> best bet probably is to create a new PatternType. Unfortunately this makes
> the complexity issue worse, but I don't see a way around it. Perhaps we can
> deprecate LITERAL and PREFIXED at some future date, if this wildcard thing
> makes them unecessary.
>
> Another issue I see, somewhat related, is that Authorizers are pluggable,
> and probably won't be updated all at once to support this new type. That
> should be fine, but we should document the error that is returned when
> someone tries to create your new-style ACLs with an authorizer that does
> not support them.
>
> > Code is available on my personal branch [1].  It is not fully documented
> > and does not meet the checkstyle requirements yet.  I also modified the
> jmh
> > tests to run the Trie tests and limit the test to the single case
> mentioned
> > in the KIP documentation.
> >
> > If there are no issues with this code, I will complete the documentation
> > and fix the checkstyle and then open a pull request.
>
> It's fine to open a pull request. You can link it on the KIP page. As
> always, we don't want to commit it until the KIP is accepted.
>
> best,
> Colin
>
> >
> > Claude
> >
> > [1]
> https://github.com/Claudenw/kafka/pull/new/KIP-1042_Trie_Implementation
> >
> >
> > On Wed, Jul 3, 2024 at 2:21 PM Claude Warren, Jr  >
> > wrote:
> >
> >> I think that if we put in a trie based system we should be able to halve
> >> the normal searhc times and still be able to locate wild card matches
> very
> >> quickly.  Users should be warned that "head wildcard" matches are slow
> and
> >> to use them sparingly.  I am going to see if I can work out how to do
> >> wildcard matches within the trie.
> >>
> >> But in all cases can show that the trie is faster than the current
> >> implementation.
> >>
> >> Claude
> >>
> >>
> >>
> >> On Wed, Jun 19, 2024 at 7:53 PM Muralidhar Basani
> >>  wrote:
> >>
> >>> There are some test results mentioned in the Test Plan section of the
> Kip,
> >>> but we need to do more testing with various patterns and permission
> types.
> >>> As mentioned in the discuss thread, the trie implementation could
> >>> potentially surpass the current speed of ACL match.
> >>>
> >>> However, we can only accurately assess the results after updating the
> >>> actual classes and analysing them with AuthorizerBenchmark.
> >>>
> >>> Thanks,
> >>>
> >>> Murali
> >>>
> >>> On Mon, 17 Jun 2024 at 20:39, Colin McCabe  

[DISCUSS] KAFKA-17423 Replace StandardAuthorizer with Trie implementation

[Claude Warren, Jr]

URL: https://issues.apache.org/jira/browse/KAFKA-17423

The above is an improvement to Kafka to replace the sorted list ACL
implementation with a Trie based implementation.  I have an implementation
that passes all the tests, including the new ones in
KAFKA-17316 (pull request https://github.com/apache/kafka/pull/16779).

Data from the JMS test suite indicates that the Trie implementation is at
least an order of magnitude faster than the existing implementation.

The change does not modify any API, it simply replaces the
StandardAuthorizerData class with a Trie structure based class.

Is there any reason not to implement this change?

Claude

Question about ResourcePatternFilter

[Claude Warren, Jr]

Should a ResourcePatternFilter that has a PatternType of ANY and a name of
WILDCARD_RESOURCE  not match any Acls?  I think this is a bug.I am writing
a series of tests to ensure that I have implemented everything correctly in
the Trie implementation and this has come up.

public boolean matches(ResourcePattern pattern) {
if (!resourceType.equals(ResourceType.ANY) &&
!resourceType.equals(pattern.resourceType())) {
return false;
}

if (!patternType.equals(PatternType.ANY) &&
!patternType.equals(PatternType.MATCH) &&
!patternType.equals(pattern.patternType())) {
return false;
}

if (name == null) {
return true;
}

if (patternType.equals(PatternType.ANY) ||
patternType.equals(pattern.patternType())) {
return name.equals(pattern.name());
}

switch (pattern.patternType()) {
case LITERAL:
return name.equals(pattern.name()) ||
pattern.name().equals(WILDCARD_RESOURCE);

case PREFIXED:
return name.startsWith(pattern.name());

default:
throw new IllegalArgumentException("Unsupported
PatternType: " + pattern.patternType());
}
}

The above code is from the ResourcePatternFilter.
The first if checks for resource type not matching.
the second if checks for pattern type not matching.
the third if will return true if the name is null.
the fourth if will return true if the name matches in the case where
pattern type is ANY or has equality.  The only possible conditions here are
ANY, MATCH or equality.
the switch handles the case where the pattern type does not match.I think
this can be simplified as:

public boolean matches(ResourcePattern pattern) {
if (!resourceType.equals(ResourceType.ANY) &&
!resourceType.equals(pattern.resourceType())) {
return false;
}

switch (pattern.patternType()) {
case UNKNOWN:
return patternType.equals(pattern.patternType());

case ANY:
case MATCH:
return name == null || name.equals(pattern.name()) ||
pattern.name().equals(WILDCARD_RESOURCE) ||
name.equals(WILDCARD_RESOURCE);

case LITERAL:
return patternType.equals(pattern.patternType()) ||
name == null || name.equals(pattern.name()) ||
pattern.name().equals(WILDCARD_RESOURCE);

case PREFIXED:
return patternType.equals(pattern.patternType()) ||
name == null || name.startsWith(pattern.name()) ||
pattern.name().equals(WILDCARD_RESOURCE);

default:
throw new IllegalArgumentException("Unsupported
PatternType: " + pattern.patternType());
}
}


The above case still handles the null name and handles the
WILDCARD_RESOURCE as a valid pattern name.  I also think it is simpler to
read.

Am I missing something?

Contribution to RAT

[Claude Warren, Jr]

Greetings,

I have been working on Apache RAT recently and I noticed that Kafka has a
very nice XSLT to convert the Rat output to an HTML document.

I know there is not a legal or licensing issue but I am asking if there are
any objections to my taking the .gradle/resources/rat-output-to-html.xsl
file into the Apache RAT project so that we can have a nice HTML output
available to all users?

Thanks,
Claude

Re: ACL authorization question

[Claude Warren, Jr]

:DOH: Nevermind.   Problem between keyboard and seat.

On Thu, Aug 15, 2024 at 8:36 AM Claude Warren, Jr 
wrote:

> If there is an authorizer with no ACLs and 
> authorizeByResourceType(AuthorizableRequestContext
> requestContext, AclOperation op, ResourceType resourceType) is called
> with op = UNKNOWN or ANY, or resourceType = UKNOWN or ANY should an
> IllegalArgumentException be thrown as it is when there are ACLs?
>
> I think it should, and I think this is a bug in the default implementation
> in the Authorizer interface.
>
> Thoughts?
>

ACL authorization question

[Claude Warren, Jr]

If there is an authorizer with no ACLs and
authorizeByResourceType(AuthorizableRequestContext
requestContext, AclOperation op, ResourceType resourceType) is called with
op = UNKNOWN or ANY, or resourceType = UKNOWN or ANY should an
IllegalArgumentException be thrown as it is when there are ACLs?

I think it should, and I think this is a bug in the default implementation
in the Authorizer interface.

Thoughts?

Re: [DISCUSS] KIP-1042 support for wildcard when creating new acls

[Claude Warren, Jr]

I have created 2 branches in my repository to implement the Trie changes.


   -
   https://github.com/Claudenw/kafka/compare/trunk...StandardAuthorizer_refactor
refactors the authorizer code to make it easy to implement a different
   Authorizor data block that plugs into the StandardAuthorizor.
   -
   
https://github.com/Claudenw/kafka/compare/StandardAuthorizer_refactor...KIP-1042_trie_simplification
applies
   the Trie changes to the authorizer refactor.





On Fri, Aug 2, 2024 at 10:07 AM Claude Warren, Jr 
wrote:

> Proposed Changes
>> This KIP suggests to support *MATCH* resource pattern type when creating
>> a new kafka acl.
>>
>
> I do not think we need the MATCH support within the Authorizer as noted in
> my earlier message.
>
> *Main changes include :*
>>
>>- Adding support for MATCH when creating new acl in above and below
>>classes
>>
>>
> Strike this ^.
>
>>
>>- Updating Authorizer
>>
>>
>>- AdminClient changes
>>
>>
>>- Updating cli
>>
>> *Detailed changes also include *
>>
>>- Modification of the org.apache.kafka.server.authorizer.Authorizer
>>class to update authorizeByResourceType method
>>
>>
> Authorizer is an interface, while we can update the default
> implementation the Trie changes have moved the StandardAuthorizer
> implementation down into the StandardAuthorizerData class.  I do not think
> that there are any changes to this functionality required.  What do you
> think needs to be done?
>
>
>>- Modification of the kafka.security.authorizer.AclAuthorizer class to
>>
>>
>>- update authorizeByResourceType method and other methods
>>
>>
>>- update matchingAcls (this is performance sensitive, as it impacts
>>latency of every producer and consumer client to get authorization. Verify
>>AuthorizerBenchmark)
>>
>>
>>- Modification of the kafka.admin.AclCommand class to update multiple
>>methods like getResourceFilter and objects for parsing arguments
>>AclCommandOptions
>>
>>
>>- Modification of the kafka.zk.ZkData class to update multiple
>>objects like ZkAclStore
>>
>>
> Let's not support ZK with this change.
>
>>
>>- Modification of kafka.server.AuthHelper class to update authorize
>>method
>>
>>
>>- Modification of the org.apache.kafka.jmh.acl.AuthorizerBenchmark
>>class to update multiple methods like setup and prepareAclCache
>>
>>
>>- Modification of
>>org.apache.kafka.jmh.acl.StandardAuthorizerUpdateBenchmark class to update
>>prepareAcls method
>>
>>
>>- Modification of
>>org.apache.kafka.metadata.authorizer.StandardAuthorizerData class to 
>> update
>>authorize method
>>
>>
>>- Modification of org.apache.kafka.controller.AclControlManager class
>>to update validateNewAcl method
>>
>>
>>- Updating tests
>>
>>
>>- Similar to prefixed, match ACLs will be stored under the ZK path:
>>'/kafka-acl-extended/' and change events to such ACLs will 
>> be
>>stored under: '/kafka-acl-extended-changes'. where pattern type will be
>>prefixed or match
>>
>>
>> *Optimization* for existing LITERAL/PREFIX
>>
>>- Currently LITERAL lookups still go through the tree lookup, while
>>they can be moved to *hash-lookup*
>>
>>
>>    - For PREFIX : with a Trie-based solution. Refactor matchingAcls
>>method in AclAuthorizer.scala, to match LITERAL and PREFIXED acls.
>>
>>
>>- Define the Trie structure
>>
>>
>>- Populate the Trie with ACLs
>>
>>
>>- Retrieve ACLs using the Trie
>>
>> With this optimization, we hope to have a drastic reduced latency in the
>> matchingAcls method, and it's much more efficient.
>
> The entire Optimization section can be removed as the Trie based solution
> solves the LITERLAL, PREFIX and wildcard lookup problems.
>
>
> On Fri, Aug 2, 2024 at 9:55 AM Claude Warren, Jr 
> wrote:
>
>> I do not think we need to add the additional MATCH and ALL into the
>> Authorizer.  Currently we have
>>
>>- Literal - matches exactly
>>- Prefix - Will match patterns that are longer as long as the part
>>specified matches exactly.
>>
>> The Trie proposal works well with just these two.  The wildcard is
>> introduced as a pivot point in the trie, so any wildcard is on a node in
>> the t

Re: [DISCUSS] KIP-1042 support for wildcard when creating new acls

[Claude Warren, Jr]

>
> Proposed Changes
> This KIP suggests to support *MATCH* resource pattern type when creating
> a new kafka acl.
>

I do not think we need the MATCH support within the Authorizer as noted in
my earlier message.

*Main changes include :*
>
>- Adding support for MATCH when creating new acl in above and below
>classes
>
>
Strike this ^.

>
>- Updating Authorizer
>
>
>- AdminClient changes
>
>
>- Updating cli
>
> *Detailed changes also include *
>
>- Modification of the org.apache.kafka.server.authorizer.Authorizer
>class to update authorizeByResourceType method
>
>
Authorizer is an interface, while we can update the default
implementation the Trie changes have moved the StandardAuthorizer
implementation down into the StandardAuthorizerData class.  I do not think
that there are any changes to this functionality required.  What do you
think needs to be done?


>- Modification of the kafka.security.authorizer.AclAuthorizer class to
>
>
>- update authorizeByResourceType method and other methods
>
>
>- update matchingAcls (this is performance sensitive, as it impacts
>latency of every producer and consumer client to get authorization. Verify
>AuthorizerBenchmark)
>
>
>- Modification of the kafka.admin.AclCommand class to update multiple
>methods like getResourceFilter and objects for parsing arguments
>AclCommandOptions
>
>
>- Modification of the kafka.zk.ZkData class to update multiple objects
>like ZkAclStore
>
>
Let's not support ZK with this change.

>
>- Modification of kafka.server.AuthHelper class to update authorize
>method
>
>
>- Modification of the org.apache.kafka.jmh.acl.AuthorizerBenchmark
>class to update multiple methods like setup and prepareAclCache
>
>
>- Modification of
>org.apache.kafka.jmh.acl.StandardAuthorizerUpdateBenchmark class to update
>prepareAcls method
>
>
>- Modification of
>org.apache.kafka.metadata.authorizer.StandardAuthorizerData class to update
>authorize method
>
>
>- Modification of org.apache.kafka.controller.AclControlManager class
>to update validateNewAcl method
>
>
>- Updating tests
>
>
>- Similar to prefixed, match ACLs will be stored under the ZK path:
>'/kafka-acl-extended/' and change events to such ACLs will be
>stored under: '/kafka-acl-extended-changes'. where pattern type will be
>prefixed or match
>
>
> *Optimization* for existing LITERAL/PREFIX
>
>- Currently LITERAL lookups still go through the tree lookup, while
>they can be moved to *hash-lookup*
>
>
>- For PREFIX : with a Trie-based solution. Refactor matchingAcls
>method in AclAuthorizer.scala, to match LITERAL and PREFIXED acls.
>
>
>- Define the Trie structure
>
>
>- Populate the Trie with ACLs
>
>
>- Retrieve ACLs using the Trie
>
> With this optimization, we hope to have a drastic reduced latency in the
> matchingAcls method, and it's much more efficient.

The entire Optimization section can be removed as the Trie based solution
solves the LITERLAL, PREFIX and wildcard lookup problems.


On Fri, Aug 2, 2024 at 9:55 AM Claude Warren, Jr 
wrote:

> I do not think we need to add the additional MATCH and ALL into the
> Authorizer.  Currently we have
>
>- Literal - matches exactly
>- Prefix - Will match patterns that are longer as long as the part
>specified matches exactly.
>
> The Trie proposal works well with just these two.  The wildcard is
> introduced as a pivot point in the trie, so any wildcard is on a node in
> the trie by itself.  Ignoring the DENY and wildcard processing for a
> moment, when searching we descend the trie looking for the best matching
> node (LITERAL or PREFIX) and then check if there are ACLs on that node that
> match the request.  If not we move to the parent node and check there.  We
> continue up the tree until we find a match or reach the root (NO MATCH).
>
> For wildcard processing we insert an extra step before each move up to the
> parent we check for a wildcard match.  For the wildcard to match at this
> point it must be a PREFIX type.  By requiring a PREFIX type we can allow
> "*" and "?" as valid characters in a LITERAL match.
>
> DENY processing is performed during descent of the and matches PREFIX when
> or LITERAL depending on whether or not there is an exact match.
>
> Claude
>
> On Mon, Jul 29, 2024 at 8:36 AM Claude Warren, Jr 
> wrote:
>
>> I have updated the KIP with results from the Trie implementation and
>> they are dramatic to say the least.  For mo

Re: [DISCUSS] KIP-1042 support for wildcard when creating new acls

[Claude Warren, Jr]

I do not think we need to add the additional MATCH and ALL into the
Authorizer.  Currently we have

   - Literal - matches exactly
   - Prefix - Will match patterns that are longer as long as the part
   specified matches exactly.

The Trie proposal works well with just these two.  The wildcard is
introduced as a pivot point in the trie, so any wildcard is on a node in
the trie by itself.  Ignoring the DENY and wildcard processing for a
moment, when searching we descend the trie looking for the best matching
node (LITERAL or PREFIX) and then check if there are ACLs on that node that
match the request.  If not we move to the parent node and check there.  We
continue up the tree until we find a match or reach the root (NO MATCH).

For wildcard processing we insert an extra step before each move up to the
parent we check for a wildcard match.  For the wildcard to match at this
point it must be a PREFIX type.  By requiring a PREFIX type we can allow
"*" and "?" as valid characters in a LITERAL match.

DENY processing is performed during descent of the and matches PREFIX when
or LITERAL depending on whether or not there is an exact match.

Claude

On Mon, Jul 29, 2024 at 8:36 AM Claude Warren, Jr 
wrote:

> I have updated the KIP with results from the Trie implementation and they
> are dramatic to say the least.  For most searches they are at least an
> order of magnitude faster and use less memory.  The wildcard search is not
> a regular expression but rather a file type wild card (*=1 or more
> character, ?=1 character).
>
> Code is available on my personal branch [1].  It is not fully documented
> and does not meet the checkstyle requirements yet.  I also modified the jmh
> tests to run the Trie tests and limit the test to the single case mentioned
> in the KIP documentation.
>
> If there are no issues with this code, I will complete the documentation
> and fix the checkstyle and then open a pull request.
>
> Claude
>
> [1] https://github.com/Claudenw/kafka/pull/new/KIP
> -1042_Trie_Implementation
>
> On Mon, Jun 3, 2024 at 9:31 PM Muralidhar Basani
>  wrote:
>
>> Hi,
>>
>> Just bumping this thread again. It seems no concerns have been raised so
>> far.
>>
>> I'll request votes in 2 weeks.
>>
>> Thanks,
>> Murali
>>
>> On Tue, May 28, 2024 at 1:24 PM Muralidhar Basani <
>> muralidhar.bas...@aiven.io> wrote:
>>
>> > Hi all,
>> >
>> > Any other suggestions or objections to the proposal?
>> >
>> > Thanks,
>> > Murali
>> >
>> > On Thu, May 23, 2024 at 10:18 AM Muralidhar Basani <
>> > muralidhar.bas...@aiven.io> wrote:
>> >
>> >> Thanks Greg.
>> >> I have updated KIP with details on optimisation of LITERAL too.
>> >>
>> >> Regarding limitations in performance by introducing MATCH is
>> definitely a
>> >> question.
>> >> - By optimizing LITERAL and PREFIX we are gaining a few nano secs I
>> >> think. (described in kip)
>> >> - MATCH can be introduced only with a configuration. So by default, we
>> >> can disable the MATCH check (ex : acls.pattern.match.enable=false),
>> and if
>> >> customer enables the config, only then add the lookup in the
>> matchingAcls()
>> >> - With the proposal already described in KIP for MATCH, we may not have
>> >> any limitations., rather will be efficient.
>> >>
>> >> Maybe we are in good shape with these propositions
>> >>
>> >> Thanks,
>> >> Murali
>> >>
>> >>
>> >>
>> >> On Tue, May 21, 2024 at 6:15 PM Greg Harris
>> 
>> >> wrote:
>> >>
>> >>> Hi Murali,
>> >>>
>> >>> I don't have a trie library in mind. I looked at the current
>> >>> implementation of the StandardAuthorizer and found that we are already
>> >>> benefiting from the prefix structure in the implementation [1]. The
>> >>> current implementation appears to be a TreePSet [2].
>> >>>
>> >>> Now, we've already made this tradeoff once with PREFIX: Prefixes are
>> >>> less structured than literals, because with literals you can use a
>> >>> hashing algorithm to jump directly to your relevant ACLs in O(1), but
>> >>> with a prefix you either need to do multiple lookups, or some sort of
>> >>> O(log(n)) lookup. And we determined that the ultimate limitation in
>> >>> performance was worth it for the expressiveness.
>> >>> We're making this t

Re: [DISCUSS] KIP-1042 support for wildcard when creating new acls

[Claude Warren, Jr]

 >>> > > > to the contents "localtopic", it's true for any MATCH which
> >>> includes a
> >>> > > > wildcard at the beginning.
> >>> > > >
> >>> > > > This has implications for execution complexity: If we can't
> compute
> >>> > > > whether two patterns overlap, then we need to run both of them on
> >>> each
> >>> > > > piece of input to test if they both match. Under the current
> >>> > > > LITERAL/PREFIX system, we can optimize execution with a trie, but
> >>> that
> >>> > > > option wouldn't be available to us with MATCH.
> >>> > > >
> >>> > > > The current system makes users evaluate a trade-off:
> >>> > > > 1. Optimize the number of ACLs by organizing topics according to
> >>> > > > prefixes (for example, "accounts-localtopic-nl" and PREFIX
> >>> "accounts",
> >>> > > > PREFIX "accounts-localtopic")
> >>> > > > 2. Use less-structured topic names, with a corresponding ACL
> scheme
> >>> > > > that has more individual rules.
> >>> > > > The system currently informs users of this tradeoff by making
> them
> >>> > > > write multiple ACLs, and making them think "there has got to be a
> >>> > > > better way!". Perhaps we can find a better way to surface this
> best
> >>> > > > practice, or better inform users about it.
> >>> > > >
> >>> > > > I understand that there are going to be situations more complex
> >>> than
> >>> > > > your example, where multiple individual rules will always be
> >>> necessary
> >>> > > > with only PREFIX evaluation. I think even in those situations, a
> >>> > > > number of efficient-to-evaluate rules is preferable to just one
> >>> > > > expensive-to-evaluate rule.
> >>> > > >
> >>> > > > One alternative that I thought of could be "PARAMETERIZED" ACLs
> >>> which
> >>> > > > are like PREFIXED, but allow some parameter substitution. For
> >>> example
> >>> > > > PARAMETERIZED "(nl|de|cz)-accounts-". I'm lifting regex syntax
> >>> here,
> >>> > > > but this isn't actually a regex, and wouldn't allow arbitrary
> >>> numbers
> >>> > > > of characters, or the * or + operators.
> >>> > > > In the background it could evaluate exactly like the 3 individual
> >>> > > > PREFIX rules, but be easier to evaluate on the backend, and
> support
> >>> > > > the intersection query I mentioned earlier. It could also support
> >>> > > > [a-zA-Z] notation in case the parameter values aren't known ahead
> >>> of
> >>> > > > time, but have a fixed length.
> >>> > > >
> >>> > > > Thanks,
> >>> > > > Greg
> >>> > > >
> >>> > > > On Mon, May 6, 2024 at 11:17 AM Claude Warren 
> >>> wrote:
> >>> > > > >
> >>> > > > > I have an idea for how to reduce the time for ACL lookups in
> >>> general
> >>> > > and
> >>> > > > > particularly where wildcards are involved using sequence
> >>> > > > > characterization techniques from bioinformatics.  But I need a
> >>> set of
> >>> > > ACL
> >>> > > > > patterns and associated topics to test with.
> >>> > > > >
> >>> > > > > On Fri, May 3, 2024 at 2:45 PM Haruki Okada <
> ocadar...@gmail.com
> >>> >
> >>> > > wrote:
> >>> > > > >
> >>> > > > > > Hi, Murali.
> >>> > > > > >
> >>> > > > > > First, could you add the KIP-1042 to the index (
> >>> > > > > >
> >>> > > > > >
> >>> > > >
> >>> > >
> >>>
> https://cwiki.apache.org/confluence/display/KAFKA/Kafka+Improvement+Proposals
> >>> > > > > > )
> >>> > > > > > as well so that everyone can find it eas

Re: [VOTE] KIP-1042: Support for wildcard when creating new acls

[Claude Warren, Jr]

I have updated the KIP with results from the Trie implementation and they
are dramatic to say the least.  For most searches they are at least an
order of magnitude faster and use less memory.  The wildcard search is not
a regular expression but rather a file type wild card (*=1 or more
character, ?=1 character).

Code is available on my personal branch [1].  It is not fully documented
and does not meet the checkstyle requirements yet.  I also modified the jmh
tests to run the Trie tests and limit the test to the single case mentioned
in the KIP documentation.

If there are no issues with this code, I will complete the documentation
and fix the checkstyle and then open a pull request.

Claude

[1] https://github.com/Claudenw/kafka/pull/new/KIP-1042_Trie_Implementation


On Wed, Jul 3, 2024 at 2:21 PM Claude Warren, Jr 
wrote:

> I think that if we put in a trie based system we should be able to halve
> the normal searhc times and still be able to locate wild card matches very
> quickly.  Users should be warned that "head wildcard" matches are slow and
> to use them sparingly.  I am going to see if I can work out how to do
> wildcard matches within the trie.
>
> But in all cases can show that the trie is faster than the current
> implementation.
>
> Claude
>
>
>
> On Wed, Jun 19, 2024 at 7:53 PM Muralidhar Basani
>  wrote:
>
>> There are some test results mentioned in the Test Plan section of the Kip,
>> but we need to do more testing with various patterns and permission types.
>> As mentioned in the discuss thread, the trie implementation could
>> potentially surpass the current speed of ACL match.
>>
>> However, we can only accurately assess the results after updating the
>> actual classes and analysing them with AuthorizerBenchmark.
>>
>> Thanks,
>>
>> Murali
>>
>> On Mon, 17 Jun 2024 at 20:39, Colin McCabe  wrote:
>>
>> > My concern is that the extra complexity may actually slow us down. In
>> > general people already complain about the speed of ACL matches, and
>> adding
>> > another "degree of freedom" seems likely to make things worse.
>> >
>> > It would be useful to understand how much faster or slower the code is
>> > with the propsed changes, versus without them.
>> >
>> > best,
>> > Colin
>> >
>> >
>> > On Mon, Jun 17, 2024, at 01:26, Muralidhar Basani wrote:
>> > > Hi all,
>> > >
>> > > I would like to call a vote on KIP-1042 which extends creation of acls
>> > with
>> > > MATCH pattern type.
>> > >
>> > > KIP -
>> > >
>> >
>> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls
>> > >
>> > > Discussion thread -
>> > > https://lists.apache.org/thread/xx3lcg60kp4v34x0j9p6xobby8l4cfq2
>> > >
>> > > Thanks,
>> > > Murali
>> >
>>
>

Re: [VOTE] KIP-1042: Support for wildcard when creating new acls

[Claude Warren, Jr]

I think that if we put in a trie based system we should be able to halve
the normal searhc times and still be able to locate wild card matches very
quickly.  Users should be warned that "head wildcard" matches are slow and
to use them sparingly.  I am going to see if I can work out how to do
wildcard matches within the trie.

But in all cases can show that the trie is faster than the current
implementation.

Claude



On Wed, Jun 19, 2024 at 7:53 PM Muralidhar Basani
 wrote:

> There are some test results mentioned in the Test Plan section of the Kip,
> but we need to do more testing with various patterns and permission types.
> As mentioned in the discuss thread, the trie implementation could
> potentially surpass the current speed of ACL match.
>
> However, we can only accurately assess the results after updating the
> actual classes and analysing them with AuthorizerBenchmark.
>
> Thanks,
>
> Murali
>
> On Mon, 17 Jun 2024 at 20:39, Colin McCabe  wrote:
>
> > My concern is that the extra complexity may actually slow us down. In
> > general people already complain about the speed of ACL matches, and
> adding
> > another "degree of freedom" seems likely to make things worse.
> >
> > It would be useful to understand how much faster or slower the code is
> > with the propsed changes, versus without them.
> >
> > best,
> > Colin
> >
> >
> > On Mon, Jun 17, 2024, at 01:26, Muralidhar Basani wrote:
> > > Hi all,
> > >
> > > I would like to call a vote on KIP-1042 which extends creation of acls
> > with
> > > MATCH pattern type.
> > >
> > > KIP -
> > >
> >
> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls
> > >
> > > Discussion thread -
> > > https://lists.apache.org/thread/xx3lcg60kp4v34x0j9p6xobby8l4cfq2
> > >
> > > Thanks,
> > > Murali
> >
>

Re: [VOTE] KIP-1042: Support for wildcard when creating new acls

[Claude Warren, Jr]

I give this a cautious +1 (non binding) as development may yield better
head wildcard results.

I think the adoption criteria for the ACL search needs to be specified in
the KIP.  We do not have a good handle on how long the current searches
take.  If the wildcard tests can be merged into a trie search (see KIP
testing section) then the overall speed may be increased.


On Mon, Jun 17, 2024 at 10:27 AM Muralidhar Basani
 wrote:

> Hi all,
>
> I would like to call a vote on KIP-1042 which extends creation of acls with
> MATCH pattern type.
>
> KIP -
>
> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls
>
> Discussion thread -
> https://lists.apache.org/thread/xx3lcg60kp4v34x0j9p6xobby8l4cfq2
>
> Thanks,
> Murali
>

Re: [DISCUSS] KIP-1044: A proposal to change idempotent producer -- server implementation

[Claude Warren, Jr]

Igor,

Thanks for the well thought out comment.  Do you have a suggestion for a
fast way to write to disk?  Since the design requires random access perhaps
just a random access file?

Claude

On Thu, May 23, 2024 at 1:17 PM Igor Soarez  wrote:

> Hi Claude,
>
> Thanks for writing this KIP. This issue seems particularly
> thorny, and I appreciate everyone's effort to address this.
>
> I want to share my concern with the KIP's proposal of the
> use of memory mapped files – mmap is Java's achilles heel,
> Kafka should make less use of it, not more.
>
> The JVM often needs to stop all application threads (aka
> mutator threads) before some operations, such as GC,
> optimizations, redefinitions, internal cleanups and various
> other internal reasons. This is known as Safepointing.
>
> Because the JVM cannot forcefully stop threads, it must instead
> wait for each thread to observe the Safepointing request,
> mark themselves as safe and stop.
> A single delayed thread can leave the whole JVM hanging, waiting.
>
> Reads and writes to memory mapped files can trigger system interrupts,
> which can block on IO for prolonged amounts of time.
> One particualrly bad example is hitting the page cage dirty ratio,
> and having to flush all of the page cage, in a potentially large
> (high RAM) system into a potentially slow filesystem.
> I have seen pauses as extreme as 1 minute, and others have reported
> There are other public reports on this. [1][2]
>
> Safepointing in the JVM is designed with mechanisms to prevent having
> to wait for a single busy thread: Threads mark themselves as safe before
> waiting on locks, before system calls, before doing JNI, etc, and upon
> returning they check if a Safepoint is ongoing.
> So if a read or write syscall takes a bit longer that's fine, the JVM
> won't halt for Safepointing, it will proceed knowing that any thread stuck
> on a syscall will stop if necessary when it returns.
> But there's no protection against long system interrups.
> From the JVM's perspective the use of mmap is just a simple memory access,
> so there's no Safepointing protection around that.
> The kernel does know nor care for Java's Safepointing, and does not treat
> halting a single unsuspecting thread for a longer period of time with
> the severity that it may imply during a JVM Safepoint.
>
> So for this reason, I urge you to consider alternatives to the use
> of memory mapped files.
>
> Best,
>
> --
> Igor
>
> https://groups.google.com/g/mechanical-sympathy/c/LFrJPhyVOJ4
>
> https://groups.google.com/g/mechanical-sympathy/c/tepoA7PRFRU/m/7HbSINaFBgAJ
>
>

Re: [DISCUSS] KIP-1044: A proposal to change idempotent producer -- server implementation

[Claude Warren, Jr]

First, a "mea culpa".   In the KIP I state that several other KIPs are
rejected alternatives.  That is not the case, they are addressing different
issues and would still work with KIP-1044.  I will address this with an
update to the KIP.

Addressing the case where PID has not been seen before:

The KIP adds Bloom filter on disk for each Snapshot file.  This is simply
to quickly load the Bloom filter at startup and is not read again in the
operation once the system is running.

The Snapshot file names and Bloom filters are paired  and placed in a sorted in memory list with the most recent snapshot
listed first: [, ,...]

When a PID that has not been seen is presented the following would occur:


   1. The cache is searched and fails.
   2. The cache tries to find the PID in the snapshot files and fails.
   3. the PID is added to the cache.

So in step 2 the actions taken are effectively (some hand waving here to
gloss over some optimizations)

   1. a Bloom filter for the PID is created.
   2. Each of the Bloom filters in the list is checked to see if it
   contains the PID Bloom filter.  This operation is extremely fast (on the
   order of 4 machine instructions per 64 bits).  if we have properly
   configured the Bloom filters there should be a false positive 1 in 1K or 1
   in 10K times (This is adjustable).
   3. If there is a match on a Bloom filter the Snapshot file is scanned
   looking for the PID.  If found PID is returned.
   4. If we get here, none of the filters match, or none of the snapshots
   associated with matching filters contains the PID, so "no match" is
   reported.


Some thoughts:
Using the Commons-Collection bloom filter implementation and a sample of
snapshots I should be able to give you some idea of how fast the solution
is.  However, I have a couple of engagements (Community over Code, EU for
one) in the next few weeks that may delay that a bit.

I do recognize your point that the scanning of the snapshots may be too
slow for the new PID case, but I think with tuning we can adjust that.

Claude


On Tue, May 21, 2024 at 5:50 PM Justine Olshan 
wrote:

> Can you clarify the intended behavior? If we encounter a producer ID we've
> not seen before, we are supposed to read from disk and try to find it? I
> see the proposal mentions bloom filters, but it seems like it would not be
> cheap to search for the producer ID. I would expect the typical case to be
> that there is a new producer and we don't need to search state.
>
> And we intend to keep all producers we've ever seen on the cluster? I
> didn't see a mechanism to delete any of the information in the snapshots.
> Currently the snapshot logic is decoupled from the log retention as of
> KIP-360.
>
> Justine
>
> On Mon, May 20, 2024 at 11:20 PM Claude Warren  wrote:
>
> > The LRU cache is just that: a cache, so yes things expire from the cache
> > but they are not gone.  As long as a snapshot containing the PID is
> > available the PID can be found and reloaded into the cache (which is
> > exactly what I would expect it to do).
> >
> > The question of how long a PID is resolvable then becomes a question of
> how
> > long are snapshots retained.
> >
> > There are, in my mind, several advantages:
> >
> >1. The in-memory cache can be smaller, reducing the memory footprint.
> >This is not required but is possible.
> >2. PIDs are never discarded because they are produced by slow
> >producers.  They are discarded when the snapshots containing them
> > expire.
> >3. The length of time between when a PID is received by the server and
> >when it is recorded to a snapshot is significantly reduced.
> > Significantly
> >reducing the window where PIDs can be lost.
> >4. Throttling and other changes you wish to make to the cache are
> still
> >possible.
> >
> >
> > On Mon, May 20, 2024 at 7:32 PM Justine Olshan
> > 
> > wrote:
> >
> > > My team has looked at it from a high level, but we haven't had the time
> > to
> > > come up with a full proposal.
> > >
> > > I'm not aware if others have worked on it.
> > >
> > > Justine
> > >
> > > On Mon, May 20, 2024 at 10:21 AM Omnia Ibrahim <
> o.g.h.ibra...@gmail.com>
> > > wrote:
> > >
> > > > Hi Justine are you aware of anyone looking into such new protocol at
> > the
> > > > moment?
> > > >
> > > > > On 20 May 2024, at 18:00, Justine Olshan
> >  > > >
> > > > wrote:
> > > > >
> > > > > I would say I have first hand knowledge of this issue as someone
> who
> > > > > responds to such incidents as part of my work at Confluent over the
> > > past
> > > > > couple years. :)
> > > > >
> > > > >> We only persist the information for the length of time we retain
> > > > > snapshots.
> > > > > This seems a bit contradictory to me. We are going to persist
> > > > (potentially)
> > > > > useless information if we have no signal if the producer is still
> > > active.
> > > > > This is the problem we have with old clients. We are always going
> to
> > > have
> > > > > to draw t

Re: [DISCUSS] KIP-1042 support for wildcard when creating new acls

[Claude Warren, Jr]

sociated topics to test with.
> >
> > On Fri, May 3, 2024 at 2:45 PM Haruki Okada  wrote:
> >
> > > Hi, Murali.
> > >
> > > First, could you add the KIP-1042 to the index (
> > >
> > >
> https://cwiki.apache.org/confluence/display/KAFKA/Kafka+Improvement+Proposals
> > > )
> > > as well so that everyone can find it easily?
> > >
> > > I took a look at the KIP, then I have 2 questions:
> > >
> > > 1. Though the new MATCH resource pattern type may reduce the effort of
> > > adding ACLs in some cases, do you have any concrete use case you are in
> > > mind? (When prefixed ACL was introduced in KIP-290, there was a
> use-case
> > > that using it for implementing multi-tenancy)
> > >
> > > 2. As you may know, ACL lookup is in the hot-path which the
> performance is
> > > very important. (
> > >
> > >
> https://github.com/apache/kafka/blob/240243b91d69c2b65b5e456065fdcce90c121b04/core/src/main/scala/kafka/security/authorizer/AclAuthorizer.scala#L539
> > > ).
> > > Do you have ideas how do we update `matchingAcls` to support
> MATCH-type ACL
> > > without introducing performance issue?
> > >
> > >
> > > Thanks,
> > >
> > > 2024年5月3日(金) 19:51 Claude Warren, Jr :
> > >
> > > > As I wrote in [1], the ACL evaluation algorithm needs to be specified
> > > with
> > > > respect to the specificity of the pattern so that we know exactly
> which
> > > if
> > > > *-accounts-* takes precedence over nl-accounts-* or visa versa.
> > > >
> > > > I think that we should spell out that precedence is evaluated as
> follows:
> > > >
> > > > 1. Remove patterns that do not match
> > > > 2. More specific patterns take precedence over less specific patterns
> > > > 3. for patterns of the same precedence DENY overrides ALLOW
> > > >
> > > > Determining specificity:
> > > >
> > > > Specificity is based on the Levenshtein distance between the pattern
> and
> > > > the text being evaluated. The lower the distance the more specific
> the
> > > > rule.
> > > > Using the topic name: nl-accounts-localtopic we can evaluate the
> > > > Levenshtein distance for various patterns.
> > > > nl-accounts-localtopic = 0
> > > > *-accounts-localtopic = 2
> > > > nl-accounts-local* = 5
> > > > *-accounts-local* = 7
> > > > nl-accounts-* = 10
> > > > *-accounts-* = 12
> > > >
> > > > In the special case of matching principles User matches are more
> specific
> > > > than Group matches.
> > > >
> > > > I don't know if this should be added to KIP-1042 or presented as a
> new
> > > KIP.
> > > >
> > > > Claude
> > > >
> > > > [1] https://lists.apache.org/thread/0l88tkbxq3ol9rnx0ljnmswj5y6pho1f
> > > > <
> > > >
> > >
> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls
> > > > >
> > > >
> > > > On Fri, May 3, 2024 at 12:18 PM Claude Warren 
> wrote:
> > > >
> > > > > Took me awhile to find it but the link to the KIP is
> > > > >
> > > > >
> > > >
> > >
> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls
> > > > >
> > > > > On Fri, May 3, 2024 at 10:13 AM Murali Basani <
> murali.bas...@gmail.com
> > > >
> > > > > wrote:
> > > > >
> > > > > > Hello,
> > > > > >
> > > > > > I'd like to propose a suggestion to our resource patterns in
> Kafka
> > > > ACLs.
> > > > > >
> > > > > > Currently, when adding new ACLs in Kafka, we have two types of
> > > resource
> > > > > > patterns for topics:
> > > > > >
> > > > > >- LITERAL
> > > > > >- PREFIXED
> > > > > >
> > > > > > However, when it comes to listing or removing ACLs, we have a
> couple
> > > > more
> > > > > > options:
> > > > > >
> > > > > >- MATCH
> > > > > >- ANY (will match any pattern type)
> > > > > >
> > > 

Re: [DISCUSS] KIP-1042 support for wildcard when creating new acls

[Claude Warren, Jr]

As I wrote in [1], the ACL evaluation algorithm needs to be specified with
respect to the specificity of the pattern so that we know exactly which if
*-accounts-* takes precedence over nl-accounts-* or visa versa.

I think that we should spell out that precedence is evaluated as follows:

1. Remove patterns that do not match
2. More specific patterns take precedence over less specific patterns
3. for patterns of the same precedence DENY overrides ALLOW

Determining specificity:

Specificity is based on the Levenshtein distance between the pattern and
the text being evaluated. The lower the distance the more specific the
rule.
Using the topic name: nl-accounts-localtopic we can evaluate the
Levenshtein distance for various patterns.
nl-accounts-localtopic = 0
*-accounts-localtopic = 2
nl-accounts-local* = 5
*-accounts-local* = 7
nl-accounts-* = 10
*-accounts-* = 12

In the special case of matching principles User matches are more specific
than Group matches.

I don't know if this should be added to KIP-1042 or presented as a new KIP.

Claude

[1] https://lists.apache.org/thread/0l88tkbxq3ol9rnx0ljnmswj5y6pho1f


On Fri, May 3, 2024 at 12:18 PM Claude Warren  wrote:

> Took me awhile to find it but the link to the KIP is
>
> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1042%3A+Support+for+wildcard+when+creating+new+acls
>
> On Fri, May 3, 2024 at 10:13 AM Murali Basani 
> wrote:
>
> > Hello,
> >
> > I'd like to propose a suggestion to our resource patterns in Kafka ACLs.
> >
> > Currently, when adding new ACLs in Kafka, we have two types of resource
> > patterns for topics:
> >
> >- LITERAL
> >- PREFIXED
> >
> > However, when it comes to listing or removing ACLs, we have a couple more
> > options:
> >
> >- MATCH
> >- ANY (will match any pattern type)
> >
> >
> > If we can extend creating acls as well with 'MATCH' pattern type, it
> would
> > be very beneficial. Even though this kind of acl should be created with
> > utmost care, it will help organizations streamline their ACL management
> > processes.
> >
> > Example scenarios :
> >
> > Let's say we need to create ACLs for the following six topics:
> > nl-accounts-localtopic, nl-accounts-remotetopic, de-accounts-localtopic,
> > de-accounts-remotetopic, cz-accounts-localtopic, cz-accounts-remotetopic
> >
> > Currently, we achieve this using existing functionality by creating three
> > prefixed ACLs as shown below:
> >
> > kafka-acls --bootstrap-server localhost:9092 \
> > > --add \
> > > --allow-principal
> > >
> >
> User:CN=serviceuser,OU=ServiceUsers,O=Unknown,L=Unknown,ST=Unknown,C=Unknown
> > > \
> > > --producer \
> > > --topic nl-accounts- \
> > > --resource-pattern-type prefixed
> >
> >
> > kafka-acls --bootstrap-server localhost:9092 \
> > > --add \
> > > --allow-principal
> > >
> >
> User:CN=serviceuser,OU=ServiceUsers,O=Unknown,L=Unknown,ST=Unknown,C=Unknown
> > > \
> > > --producer \
> > > --topic de-accounts- \
> > > --resource-pattern-type prefixed
> >
> >
> > kafka-acls --bootstrap-server localhost:9092 \
> > > --add \
> > > --allow-principal
> > >
> >
> User:CN=serviceuser,OU=ServiceUsers,O=Unknown,L=Unknown,ST=Unknown,C=Unknown
> > > \
> > > --producer \
> > > --topic cz-accounts- \
> > > --resource-pattern-type prefixed
> >
> >
> > However, if we had the 'MATCH' pattern type available, we could
> accomplish
> > this with a single ACL, as illustrated here:
> >
> > kafka-acls --bootstrap-server localhost:9092 \
> > > --add \
> > > --allow-principal
> > >
> >
> User:CN=serviceuser,OU=ServiceUsers,O=Unknown,L=Unknown,ST=Unknown,C=Unknown
> > > \
> > > --producer \
> > > --topic *-accounts-* \
> > > --resource-pattern-type match
> >
> >
> >
> > This pattern closely resembles PREFIXED but offers broader allow/deny
> > rules.
> >
> > Implementing this change could significantly reduce the effort in several
> > acl management processes.
> >
> > I welcome your thoughts and any concerns you may have regarding this
> > proposal.
> >
> > Thanks,
> > Murali
> >
>
>
> --
> LinkedIn: http://www.linkedin.com/in/claudewarren
>

Re: Suggestion about support for wildcard when creating new acls

[Claude Warren, Jr]

I think that if this is introduced (and perhaps even if it is not) we need
a clear ACL evaluation process.

I know we have both allow and deny, and that deny takes precedence over
allow.

But let's consider two scenarios

1. Unintended access.

Let's assume we start with the 6 topics Murali used in his
example: nl-accounts-localtopic, nl-accounts-remotetopic,
de-accounts-localtopic, de-accounts-remotetopic, cz-accounts-localtopic,
and cz-accounts-remotetopic
Assume that *-accounts-* pattern granted read access to anyone.
I create an account us-accounts-privatetopic and grant explicit access some
individuals.
Because of the *-accounts-* everyone has access to my privatetopic, and I
may not know that there is a leak until it is far too late.
I don't have a good way to determine which ACLs will impact my topic.
I cannot add a general us-accounts-privatetopic DENY and hope my explicit
access works because DENY takes precedence over ALLOW.

2. Unintended/Hostile denial
Let's assume we start with the 6 topics Murali used in his
example: nl-accounts-localtopic, nl-accounts-remotetopic,
de-accounts-localtopic, de-accounts-remotetopic, cz-accounts-localtopic,
and cz-accounts-remotetopic
Assume that *-accounts-* pattern grants read access to anyone.
A bad or carless actor could create *-* DENY which would cause the system
to cease functioning as expected.
There is not a good way to determine which ACLs impacted the topic.


*Note* that both of these issues can occur with the PREFIXED pattern as
well, so this is not an argument against the MATCH pattern.  There is a
fundamental issue with the current ACL implementation as relates to
wildcards.

I think that the evaluation process should be:

   1. Remove patterns that do not match
   2. More specific patterns take precedence over less specific patterns
   3. for patterns of the same precedence DENY overrides ALLOW

*Determining specificity*:

Specificity is generally based on the Levenshtein distance between the
pattern and the text being evaluated.  The lower the distance the more
specific the rule.
Using the topic name: nl-accounts-localtopic we can evaluate the
Levenshtein distance for various patterns.

nl-accounts-localtopic = 0
*-accounts-localtopic = 2
nl-accounts-local* = 5
*-accounts-local* = 7
nl-accounts-* = 10
*-accounts-* = 12

In the special case of matching principles User matches are more specific
than Group matches.

*Usability*

With the ACL system becoming a complex web of patterns, it is
incumbent upon the development team to provide tools to assist in
permissions problem determination.

1.  There should be a tool that will provide a list of all ACLs that impact
the decision to allow or deny access for a principal to a topic based on
principal ID, host, and operation.  This will assist operators in rapidly
determining the reason for access denied errors.
2. There should be a tool to show the effects of adding an ACL.  Using the
example from above adding *-accounts-*", should list that
nl-accounts-localtopic, nl-accounts-remotetopic,
de-accounts-localtopic, de-accounts-remotetopic, cz-accounts-localtopic,
and cz-accounts-remotetopic are affected.
3. There should be a tool to show the effects of adding a topic.  Using the
example from above adding *us-accounts-privatetopic", should list that
"*-accounts-*" will influence the permissions calculations for the new
topic.

*Summary*

I leave determining whether or not adding MATCH as a pattern type is a good
idea to others with more experience in Kafka.  But in either case, I
believe that we need to look at how we evaluate ACLs given that we already
have a wild card ACL pattern.

Claude

On Thu, May 2, 2024 at 3:56 PM Murali Basani 
wrote:

> Hello,
>
> I'd like to propose a suggestion to our resource patterns in Kafka ACLs.
>
> Currently, when adding new ACLs in Kafka, we have two types of resource
> patterns for topics:
>
>- LITERAL
>- PREFIXED
>
> However, when it comes to listing or removing ACLs, we have a couple more
> options:
>
>- MATCH
>- ANY (will match any pattern type)
>
>
> If we can extend creating acls as well with 'MATCH' pattern type, it would
> be very beneficial. Even though this kind of acl should be created with
> utmost care, it will help organizations streamline their ACL management
> processes.
>
> Example scenarios :
>
> Let's say we need to create ACLs for the following six topics:
> nl-accounts-localtopic, nl-accounts-remotetopic, de-accounts-localtopic,
> de-accounts-remotetopic, cz-accounts-localtopic, cz-accounts-remotetopic
>
> Currently, we achieve this using existing functionality by creating three
> prefixed ACLs as shown below:
>
> kafka-acls --bootstrap-server localhost:9092 \
> > --add \
> > --allow-principal
> >
> User:CN=serviceuser,OU=ServiceUsers,O=Unknown,L=Unknown,ST=Unknown,C=Unknown
> > \
> > --producer \
> > --topic nl-accounts- \
> > --resource-pattern-type prefixed
>
>
> kafka-acls --bootstrap-server localhost:9092 \
> > --add \
> > --allow

Re: [DISCUSS] KIP-936 Throttle number of active PIDs

[Claude Warren, Jr]

There is some question about whether or not we need the configuration
options.  My take on them is as follows:

producer.id.quota.window.num  No opinion.  I don't know what this is used
for, but I suspect that there is a good reason to have it.  It is not used
within the Bloom filter caching mechanism
producer.id.quota.window.size.seconds Leave it as it is one of the most
effective ways to tune the filter and determines how long a PID is
recognized.
producer.id.quota.cache.cleanup.scheduler.interval.ms  Remove it unless
there is another use for it.   We can get a better calculation for
internals.
producer.id.quota.cache.layer.count Leave it as it is one of the most
effective ways to tune the filter.
producer.id.quota.cache.false.positive.rate Replace it with a constant,  I
don't think any other Bloom filter solution provides access to this knob
for end users.
producer_ids_rate Leave this one, it is critical for reasonable operation.

Re: [DISCUSS] KIP-936 Throttle number of active PIDs

[Claude Warren, Jr]

Quick note:  I renamed the example code.  It is now at
https://github.com/Claudenw/kafka/blob/KIP-936/storage/src/main/java/org/apache/kafka/storage/internals/log/ProducerIDQuotaManagerCache.java

On Thu, May 2, 2024 at 10:47 AM Claude Warren, Jr 
wrote:

> Igor,  thanks for taking the time to look and to review the code.  I
> regret that I have not pushed the latest code, but I will do so and will
> see what I can do about answering your Bloom filter related questions here.
>
>  How would an operator know or decide to change the configuration
>> for the number layers – producer.id.quota.cache.layer.count –
>> e.g. increasing from 4 to 5; and why?
>> Do we need a new metric to indicate that change could be useful?
>
>
> In our usage the layered Bloom filter [6] retains the record of a PID for
> producer.id.quota.window.size.seconds.  It breaks that window down into
> multiple fragments, so 4 layers = 15 minute fragments.  It "forgets" a
> fragment worth of data when the fragment has been around for
> window.size.seconds.  The layers will determine how big a chunk of time is
> deleted at once.  Changing the layers to 10 will yield 6 minute fragments,
> 60 will yield 1 minute fragments and so on.  There are other idiosyncrasies
> that I will get into later.  I would not set the value lower than 3.  If
> you find that there are multiple reports of new PIDs because on average
> they only ping every 50 minutes it might make sense to use more layers.  If
> you use too many layers then there will only be one PID in each layer, and
> at that point a simple list of Filters would be faster to search, but in
> reality does not make sense.  If you have two layers then recurring PIDs
> will be recorded in both layers.
>
>  Is producer.id.quota.cache.cleanup.scheduler.interval.ms a
>> guaranteed interval, or rather simply a delay between cleanups?
>> How did you decide on the default value of 10ms?
>
>
> In the code this is not used.  Cleanups are amortized across inserts to
> keep the layers balanced.  There is a thread that does a cleanup every
>  producer.id.quota.window.size.seconds /
> producer.id.quota.cache.layer.count seconds to detect principals that are
> no longer sending data.  This is a reasonable frequency as it will align
> well with when the layers actually expire.
>
>  Under "New ProducerIdQuotaManagerCache", the documentation for
>> the constructor params for ProducerIDQuotaManagerCache does not
>> match the constructor signature.
>
>
> Sorry, this is because I did not push the changes.  The constructor is
> ProducerIDQuotaManagerCache(Double falsePositiveRate, long ttl, int
> layerCount).  Where falsePositiveRate is the Bloom filter false positive
> rate, ttl is producer.id.quota.window.size.seconds in milliseconds, and the
> layerCount is the desired number of layers.
>
> Under "New ProducerIdQuotaManagerCache":
>>   public boolean track(KafkaPrincipal principal, int producerIdRate, long
>> pid)
>> How is producerIdRate used? The reference implementation Claude shared
>> does not use it.
>>
>> https://github.com/Claudenw/kafka/blob/49b6eb0fb5cfaf19b072fd87986072a683ab976c/storage/src/main/java/org/apache/kafka/storage/internals/log/ProducerIDQuotaManager.java
>
>
> Again, sorry for not updating the code.  The producer rate is used to
> build a Bloom filter of the proper size.  The producer rate is the number
> of PIDs per hour expected to be created by the principal.  The Bloom filter
> shape [1] is determined by the expected number of PIDs per layer
> (producerRate * seconds_per_hour / producer.id.quota.window.size.seconds /
> producer.id.quota.cache.layer.count) and the falsePositiveRate from the
> constructor.  These values are used to call the Shape.fromNP() method.
> This is the Shape of the Bloom filters in the layer.  It is only used when
> the principal is not found in the cache.  Thomas Hurst has provided a web
> page [5] where you can explore the interaction between number of items and
> false positive rate.
>
> I could not find a description or definition for
>> TimestampedBloomFilter, could we add that to the KIP?
>
>
> I will add it.  It is simply an implementation of WrappedBloomFilter [2]
> that adds the timestamp for when the filter was created.
>
> LayeredBloomFilter will have a fixed size (right?), but some
>> users (KafkaPrincipal) might only use a small number of PIDs.
>> It it worth having a dual strategy, where we simply keep a Set of
>> PIDs until we reach certain size where it pays off to use
>> the LayeredBloomFilter?
>
>
> Each principal has its own Layered Bloom filter.
>
> Here come the idiosyncrasies and benefits of the layered Bloom f

Re: [DISCUSS] KIP-936 Throttle number of active PIDs

[Claude Warren, Jr]

Igor,  thanks for taking the time to look and to review the code.  I regret
that I have not pushed the latest code, but I will do so and will see what
I can do about answering your Bloom filter related questions here.

 How would an operator know or decide to change the configuration
> for the number layers – producer.id.quota.cache.layer.count –
> e.g. increasing from 4 to 5; and why?
> Do we need a new metric to indicate that change could be useful?


In our usage the layered Bloom filter [6] retains the record of a PID for
producer.id.quota.window.size.seconds.  It breaks that window down into
multiple fragments, so 4 layers = 15 minute fragments.  It "forgets" a
fragment worth of data when the fragment has been around for
window.size.seconds.  The layers will determine how big a chunk of time is
deleted at once.  Changing the layers to 10 will yield 6 minute fragments,
60 will yield 1 minute fragments and so on.  There are other idiosyncrasies
that I will get into later.  I would not set the value lower than 3.  If
you find that there are multiple reports of new PIDs because on average
they only ping every 50 minutes it might make sense to use more layers.  If
you use too many layers then there will only be one PID in each layer, and
at that point a simple list of Filters would be faster to search, but in
reality does not make sense.  If you have two layers then recurring PIDs
will be recorded in both layers.

 Is producer.id.quota.cache.cleanup.scheduler.interval.ms a
> guaranteed interval, or rather simply a delay between cleanups?
> How did you decide on the default value of 10ms?


In the code this is not used.  Cleanups are amortized across inserts to
keep the layers balanced.  There is a thread that does a cleanup every
 producer.id.quota.window.size.seconds /
producer.id.quota.cache.layer.count seconds to detect principals that are
no longer sending data.  This is a reasonable frequency as it will align
well with when the layers actually expire.

 Under "New ProducerIdQuotaManagerCache", the documentation for
> the constructor params for ProducerIDQuotaManagerCache does not
> match the constructor signature.


Sorry, this is because I did not push the changes.  The constructor is
ProducerIDQuotaManagerCache(Double falsePositiveRate, long ttl, int
layerCount).  Where falsePositiveRate is the Bloom filter false positive
rate, ttl is producer.id.quota.window.size.seconds in milliseconds, and the
layerCount is the desired number of layers.

Under "New ProducerIdQuotaManagerCache":
>   public boolean track(KafkaPrincipal principal, int producerIdRate, long
> pid)
> How is producerIdRate used? The reference implementation Claude shared
> does not use it.
>
> https://github.com/Claudenw/kafka/blob/49b6eb0fb5cfaf19b072fd87986072a683ab976c/storage/src/main/java/org/apache/kafka/storage/internals/log/ProducerIDQuotaManager.java


Again, sorry for not updating the code.  The producer rate is used to build
a Bloom filter of the proper size.  The producer rate is the number of PIDs
per hour expected to be created by the principal.  The Bloom filter shape
[1] is determined by the expected number of PIDs per layer (producerRate *
seconds_per_hour / producer.id.quota.window.size.seconds /
producer.id.quota.cache.layer.count) and the falsePositiveRate from the
constructor.  These values are used to call the Shape.fromNP() method.
This is the Shape of the Bloom filters in the layer.  It is only used when
the principal is not found in the cache.  Thomas Hurst has provided a web
page [5] where you can explore the interaction between number of items and
false positive rate.

I could not find a description or definition for
> TimestampedBloomFilter, could we add that to the KIP?


I will add it.  It is simply an implementation of WrappedBloomFilter [2]
that adds the timestamp for when the filter was created.

LayeredBloomFilter will have a fixed size (right?), but some
> users (KafkaPrincipal) might only use a small number of PIDs.
> It it worth having a dual strategy, where we simply keep a Set of
> PIDs until we reach certain size where it pays off to use
> the LayeredBloomFilter?


Each principal has its own Layered Bloom filter.

Here come the idiosyncrasies and benefits of the layered Bloom filter.  The
layered Bloom filter can be thought of as a collection of bloom filters
that are queried to see if the item being searched for (target) has been
seen.  There are a bunch of ways that the layered filter could be used.
You could have a layer for each storage location in a multiple location
storage engine for example.  But in our case the layer signifies a starting
time fragment.  That fragment will be at most
producer.id.quota.window.size.seconds / producer.id.quota.cache.layer.count
seconds long.  The earliest layers are at the lower indices, the latest one
at the highest.

In general, when an item is added to the Layered Bloom filter the following
processes take place:

   - old layers filters are removed using t

Re: [DISCUSS] KIP-1034: Dead letter queue in Kafka Streams

[Claude Warren, Jr]

I am new to the Kafka codebase so please excuse any ignorance on my part.

When a dead letter queue is established is there a process to ensure that
it at least is defined with the same ACL as the original queue?  Without
such a guarantee at the start it seems that managing dead letter queues
will be fraught with security issues.


On Wed, Apr 10, 2024 at 10:34 AM Damien Gasparina 
wrote:

> Hi everyone,
>
> To continue on our effort to improve Kafka Streams error handling, we
> propose a new KIP to add out of the box support for Dead Letter Queue.
> The goal of this KIP is to provide a default implementation that
> should be suitable for most applications and allow users to override
> it if they have specific requirements.
>
> In order to build a suitable payload, some additional changes are
> included in this KIP:
>   1. extend the ProcessingContext to hold, when available, the source
> node raw key/value byte[]
>   2. expose the ProcessingContext to the ProductionExceptionHandler,
> it is currently not available in the handle parameters.
>
> Regarding point 2.,  to expose the ProcessingContext to the
> ProductionExceptionHandler, we considered two choices:
>   1. exposing the ProcessingContext as a parameter in the handle()
> method. That's the cleanest way IMHO, but we would need to deprecate
> the old method.
>   2. exposing the ProcessingContext as an attribute in the interface.
> This way, no method is deprecated, but we would not be consistent with
> the other ExceptionHandler.
>
> In the KIP, we chose the 1. solution (new handle signature with old
> one deprecated), but we could use other opinions on this part.
> More information is available directly on the KIP.
>
> KIP link:
> https://cwiki.apache.org/confluence/display/KAFKA/KIP-1034%3A+Dead+letter+queue+in+Kafka+Streams
>
> Feedbacks and suggestions are welcome,
>
> Cheers,
> Damien, Sebastien and Loic
>