Throw error on conflicting BCAST tracking prefixes.#8176
Conversation
oranagra
left a comment
There was a problem hiding this comment.
you're missing a couple of call to raxStop.
i'm a bit concerned about all the loops, maybe a good exercise would be if we can (at least hypothetically) describe the O complexity for this in https://redis.io/commands/client-tracking ?
|
TIL about raxStop. The complexity is alright, its O(Log(K)*K + Pn*P*Log(P)) where K is the number of keys that are current tracked, P is the number of prefixes currently being tracked, and Pn is the new number of new prefixes. The first component is the one that can be large if there are lots of keys. The second component can't really ever grow that large unless you are tracking a lot of prefixes. |
|
This complexity formula looks scary (long) 8-) (wouldn't want to put it in the docs) maybe the middle ground is to refuse the command (error), but unlike the code in #8135, do that only when there's a conflict. |
|
@hwware @oranagra I'm not really convinced this is strictly much better than Wen's original PR. I don't like that this is an API that allows you incrementally add on more prefixes, without it being clear that it is that type of API. If you guys are happy though, it's not something I feel that strongly about since we can't un-release this API. |
oranagra
left a comment
There was a problem hiding this comment.
sorry for the delay (somehow missed the fact you changed the code).
This looks good to me, unlike the other PR, this one doesn't require changing an old test and breaking an intended feature (intended by the comment in the test), and instead it just prevents the user from doing an invalid configuration.
The performance cost is a shame, but it's simpler that the previous version of this PR.
and also worth to note that the complexity is high only if that specific client tracks a lot of prefixes.
Also, this version doesn't prevent us from adding any tracking introspection commands in the future.
|
@hwware does this look good to you? |
|
Hi @oranagra @madolson , sorry for the delay, to summarize the potential ways to solve this problem, we have the following ways:
from these four points i felt like the third way(this current pr) is the best choice. Also regarding the complexity, we cannot do much for now to improve, since some of the radix tree APIs are not ready. but maybe this can be done sometime in the future. |
|
@madolson @itamarhaber do you think we should update the complexity formula in redis-doc? |
|
I can update the complexity, since I want to update the docs anyways to document this behavior. |
|
@redis/core-team please approve. this still allows incrementally registering prefixes (as long as they don't overlap), and still allows adding prefix introspection in the future. so the only breaking change here is that it'll error only in the cases where in the past could have cause duplicate messages. |
|
@madolson looks like you can (squash) merge this. |
|
@oranagra I did open a doc PR: redis/redis-doc#1486 |
Throw an error if there are conflicting bcast tracking prefixes.
|
a sporadic failure in this test on freebsd: https://github.com/redis/redis/runs/6516880161?check_suite_focus=true |
…-overlap
checkPrefixCollisionsOrReply documents a boolean contract: 1 on no
collision, 0 on collision (with the error reply already sent). The
sole caller in networking.c relies on this:
if (!checkPrefixCollisionsOrReply(c, prefix, numprefix)) {
zfree(prefix);
return;
}
When a collision between two user-provided prefixes is detected in
the inner j-loop, the function returns the outer loop index i instead
of 0. At i=0 this happens to be falsy and the caller behaves correctly,
which hid the bug from casual testing. For any i>=1 the non-zero value
is truthy, the caller falls through to enableTracking(), and the
client receives both the error reply and +OK while the overlapping
prefixes get registered:
> CLIENT TRACKING ON BCAST PREFIX BAZ PREFIX FOOBAR PREFIX FOO
-ERR Prefix 'FOOBAR' overlaps with another provided prefix 'FOO'...
+OK
History
-------
The bug has been present since the function was introduced in redis#8176,
which added both the function and the boolean-style caller in the
same commit. The original contract was three-valued (-1 success,
0 existing-collision, i self-collision) but the caller used !retval,
so at i>=1 the self-collision path was silently a pass.
redis#8456 later changed the success return from -1 to 1 and tightened the
docstring to a boolean contract, but did not touch the `return i`
path below. That cleanup codified the boolean contract while leaving
the non-boolean exit alive, making the inherited bug easier to spot
by reading the function but no easier to catch at runtime.
Nothing in the tree consumes the returned index value -- it has
always been dead information. This change returns 0 in that path so
both error exits match the documented contract.
Test
----
Adds tests/unit/tracking.tcl case that triggers a self-collision at
i>=1 (BAZ FOOBAR FOO), asserts the error reply, and asserts
CLIENT TRACKINGINFO reports `flags off` -- i.e. tracking was not
wrongly enabled. Verified the test fails on master without the fix
and passes with it. Full unit/tracking suite green.
Signed-off-by: Raj Danday <rajkripal.danday@gmail.com>
…-overlap Caller is `if (!checkPrefixCollisionsOrReply(...))` — expects 0 on collision, non-zero on success. The self-collision branch returns the outer loop index `i` instead of 0. At i=0 it's falsy so the caller bails correctly. At i>=1 it's truthy, caller proceeds to enableTracking(), client gets both the error reply AND +OK, overlapping prefixes get registered. Repro: CLIENT TRACKING ON BCAST PREFIX BAZ PREFIX FOOBAR PREFIX FOO -ERR Prefix 'FOOBAR' overlaps with 'FOO' +OK Been there since redis#8176. redis#8456 flipped the success return to match a boolean docstring but left `return i` alone. The index value isn't read anywhere — always dead info. Return 0 and add a regression test. Signed-off-by: Raj Danday <rajkripal.danday@gmail.com>
Caller is `if (!checkPrefixCollisionsOrReply(...))` — expects 0 on collision, non-zero on success. The self-collision branch returns the outer loop index `i` instead of 0. At i=0 it's falsy so the caller bails correctly. At i>=1 it's truthy, caller proceeds to enableTracking(), client gets both the error reply AND +OK, overlapping prefixes get registered. Repro: CLIENT TRACKING ON BCAST PREFIX BAZ PREFIX FOOBAR PREFIX FOO -ERR Prefix 'FOOBAR' overlaps with 'FOO' +OK Been there since redis#8176. redis#8456 flipped the success return to match a boolean docstring but left `return i` alone. The index value isn't read anywhere — always dead info. Return 0 and add a regression test. Signed-off-by: Raj Danday <rajkripal.danday@gmail.com>
Caller is `if (!checkPrefixCollisionsOrReply(...))` — expects 0 on collision, non-zero on success. The self-collision branch returns the outer loop index `i` instead of 0. At i=0 it's falsy so the caller bails correctly. At i>=1 it's truthy, caller proceeds to enableTracking(), client gets both the error reply AND +OK, overlapping prefixes get registered. Repro: CLIENT TRACKING ON BCAST PREFIX BAZ PREFIX FOOBAR PREFIX FOO -ERR Prefix 'FOOBAR' overlaps with 'FOO' +OK Been there since redis#8176. redis#8456 flipped the success return to match a boolean docstring but left `return i` alone. The index value isn't read anywhere — always dead info. Return 0 and add a regression test. Signed-off-by: Raj Danday <rajkripal.danday@gmail.com>
Caller is `if (!checkPrefixCollisionsOrReply(...))` — expects 0 on collision, non-zero on success. The self-collision branch returns the outer loop index `i` instead of 0. At i=0 it's falsy so the caller bails correctly. At i>=1 it's truthy, caller proceeds to enableTracking(), client gets both the error reply AND +OK, overlapping prefixes get registered. Repro: CLIENT TRACKING ON BCAST PREFIX BAZ PREFIX FOOBAR PREFIX FOO -ERR Prefix 'FOOBAR' overlaps with 'FOO' +OK Been there since redis#8176. redis#8456 flipped the success return to match a boolean docstring but left `return i` alone. The index value isn't read anywhere — always dead info. Return 0 and add a regression test. Signed-off-by: Raj Danday <rajkripal.danday@gmail.com>
Handle BCAST deduplications. This is mostly a POC to evaluate whether or not we should do this or throw an error: #8135
I'm not sure if we need to do all the work to copy all the keys into the BCAST state, but it handles some edge cases where a new client had created the new bcast state.