I would vote for option 1. Yes it's O(N^2), but how many prefixes are people really using? This is really an enabling configuration.

Also technically backwards breaking, so @redis/core-team

Hi @madolson , thank you for your optionion, actually I also think application or user shouldn't have many prefixes for the BCAST tracking call , so option 1 should be good to handle... But just not sure if it is ok for us to assume something in the application even though we did not see that. Maybe we can wait for some other comments?

@hwware @madolson on my way to merge it and edit the commit message i have doubts.
better late then sorry... right?

i don't recall our previous discussions about the matter and what state i had in my brain at the time (volatile memory).

this change actually prevents users that wants to enable two different BCAST prefixes using two consecutive calls from achieving their purpose, and is of course a braking change (evident by the test that had to be modified).

i'm afraid that when we roll this out we'll break some applications.
so thinking of it again, i think i prefer users that enabled two similar prefixes to receive duplicate invalidation messages, rather than disallowing two different prefixes to be added in consecutive calls to the TRACKING command.
it may have been an acceptable limitation (require a single TRACKING command) if it had existed since the get go, but i don't think wanna do this now.

looking again at the discussion, maybe at the time i belied that this is a partial (non hermetic) solution to the problem, which we can later improve to be more hermetic. but now i realize (correct me if i'm wrong) that if we implement the O(N^2) search later on, this limitation will be lifted.
considering that, i think i rather keep the duplicate invalidation messages for now.

[i'll downvote this till we finish the discussion, so that we don't risk accidentally merging it before then]

thanks @oranagra for the concern, it is better we clearify everything before we merge it.

We discussed this issue in #8003 and our chat. I was actually had same concern before if we disabled te second BCAST call, which will disable the ability to register new prefixes. Since currently there is no APIs for managing BCAST prefixes separatelly, this is the way how we can register prefix in a accumulating way. but as @madolson mentioned, clients can still do a disable/enable approach for registering the new prefixes(but not a accumulating way) and this might be the most common way client manage this. In some stateless application I am not sure if the incremental way might be the case client side choosed, but we maybe can leave the discussion and implementsion for prefix add/delete functionality after client opened this request? but for now I think fixing this bug is necessary. How do you think on this? thanks

I guess that's fair, I was in the mindset that most of the client tracking APIs are setting the state, not adding to the state. So in this case, calling this function twice was basically a bug. But, if instead we think of this as an add prefix API, like you are suggesting, then this use case is perfectly valid.

We can just solve the deduplication bug, it shouldn't be that hard to to loop over all the already registered prefixes and see if either are a substring of another one.

CLIENT TRACKING BCAST ON PREFIX foo PREFIX bar
CLIENT TRACKING BCAST ON PREFIX f

Would deduplicate to having two prefixes, 'bar' and 'f'. @hwware We should be able to do that easily right?

@madolson i felt this might introduce some level of complexity, if we doing deduplicate. since the prefixes will be saved in two places: the global PrefixTable for all clients prefixes and for each client itself which is in client_tracking_prefixes .. If we do deduplicates we need to search and delete in these two rax trees, for client rax itself i would't consider much, but for the global Prefix, since it contains all the client registered prefix, it maybe inefficient for searching and operating in some scenario. Therefore i would vote for fail early before actually insert the prefix... Please let me know if i miss anything. thanks

@hwware @oranagra I posted an implementation for deduplication: #8176

I don't think it's that complex, and it's more backwards compatible.

Hi @madolson @oranagra , i am thinking this dupicate invalidation message issue could have another way to solve. I think we put too much complexity in managing the prefixes but maybe when we doing the invalidate we can do something.
how about we do this?

1. the idea is we can setup a nested rax tree for tracking whether a key has been invalidated already for a client in every round . this is like a lookup table from key to clients..
2. when we do the invalidation in https://github.com/redis/redis/blob/unstable/src/tracking.c#L494, we additionally check whether the key has been set in the rax tree for this client. If so we skip and if not we set it.

I think this way we can also avoid the duplicate invalidation message issue, also since the invalidation happens in beforeSleep call, this rax tree shouldn't grow big. not sure if that make sense to your guys or is there anything that I was missing? thanks!

Sorry about the previous notification, i made a mistake :(

@hwware I don't like the idea of adding complexity on the hot path. The deduplication work is harder, but we don't expect people to be updating them very often.

Hi @madolson , for the deduplication work, I have one concern regarding this: it may potentically close the door for us to implement some other prefix APIs, if user request and we need to extend in the future: such as show registered prefixes, or delete prefixes.. Not sure for now we have a valid use case or not, but just want to leave a note here. otherwise this idea seems ok to me..

closing this PR since we agree to use #8176 for this fix.