Skip to content

Throw error on conflicting BCAST tracking prefixes.#8176

Merged
madolson merged 10 commits into
redis:unstablefrom
madolson:csc-dedupe
Jan 8, 2021
Merged

Throw error on conflicting BCAST tracking prefixes.#8176
madolson merged 10 commits into
redis:unstablefrom
madolson:csc-dedupe

Conversation

@madolson

Copy link
Copy Markdown
Contributor

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.

@oranagra oranagra left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 ?

@madolson

madolson commented Dec 13, 2020

Copy link
Copy Markdown
Contributor Author

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.

@madolson madolson marked this pull request as ready for review December 13, 2020 19:54
Comment thread src/tracking.c Outdated
@oranagra

Copy link
Copy Markdown
Member

This complexity formula looks scary (long) 8-) (wouldn't want to put it in the docs)
And i think i Agree with Wen's comment about the fact that merging prefixes would be blocking any future introspection effort.

maybe the middle ground is to refuse the command (error), but unlike the code in #8135, do that only when there's a conflict.
this would not block the user from incremental prefix registration, and will only error in these cases where he's later subject to duplicate invalidation messages.
and this will also slightly reduce and simplify the complexity of that command.

@madolson madolson changed the title Deduplicate bcast tracking clients Deduplicate bcast tracking clients (Or throw an error on conflict?) Dec 16, 2020
@madolson

Copy link
Copy Markdown
Contributor Author

@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
oranagra previously approved these changes Dec 21, 2020

@oranagra oranagra left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

@oranagra oranagra added release-notes indication that this issue needs to be mentioned in the release notes state:to-be-merged The PR should be merged soon, even if not yet ready, this is used so that it won't be forgotten labels Dec 21, 2020
@oranagra

Copy link
Copy Markdown
Member

@hwware does this look good to you?

@hwware

hwware commented Dec 21, 2020

Copy link
Copy Markdown
Contributor

Hi @oranagra @madolson , sorry for the delay, to summarize the potential ways to solve this problem, we have the following ways:

  1. return error directly when calling tracking with bcast again, and an extra duplication check for the prefixes that user provided.
    pros: easy to implement and straightforward.
    cons: break the backward compatability.

  2. doing extra deduplication of prefixes work, like previousy this PR do.
    pros: not break backward compatability.
    cons: need some extra logic and may potentically affect how we implement some future extentions of tracking prefix related API.

  3. return error only when it collision with previous registered prefix.
    pros: easy and less affect user compared to method 1.
    cons: complexity is big, may break backward compatability, but we may need to do this to avoid issue.

  4. instead we doing anythings on prefixes, we track duplication when redis sending messages, which says we use an extra key-client mapping for bcast mode, for checking the duplication.
    pros: this looks like a more elegant way(we allow user register more prefixes and we check the dupications when send the msg). not affect future work for extentions of tracking prefix related API.
    cons: need to define new data structure to save the key-client mapping, lots of code need to refactored for bcast mode, and may cause redis spend extra memory which we may need to avoid.

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.
please let me know if i missed something but I agree this pr looks like what we should do now.

Comment thread src/networking.c Outdated
Comment thread src/tracking.c
@oranagra

Copy link
Copy Markdown
Member

@madolson @itamarhaber do you think we should update the complexity formula in redis-doc?

@madolson

Copy link
Copy Markdown
Contributor Author

I can update the complexity, since I want to update the docs anyways to document this behavior.

@madolson madolson added the state:needs-doc-pr requires a PR to redis-doc repository label Dec 23, 2020
@oranagra oranagra added the approval-needed Waiting for core team approval to be merged label Jan 1, 2021
@oranagra

oranagra commented Jan 3, 2021

Copy link
Copy Markdown
Member

@redis/core-team please approve.
previous behavior is that when a client subscribes to overlapping prefixes, he's getting duplicate invalidation messages.
new behavior is to reject the command that adds an overlapping prefix.

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.
one note that if the user ignores errors, assuming the later registration is the shorter prefix, after the fix the user might be missing some messages too.

@oranagra

oranagra commented Jan 7, 2021

Copy link
Copy Markdown
Member

@madolson looks like you can (squash) merge this.
make sure the commit comment is up to date, and consider a redis-doc PR.

@madolson

madolson commented Jan 8, 2021

Copy link
Copy Markdown
Contributor Author

@oranagra I did open a doc PR: redis/redis-doc#1486

@madolson madolson merged commit 999494c into redis:unstable Jan 8, 2021
@madolson madolson changed the title Deduplicate bcast tracking clients (Or throw an error on conflict?) Throw error on conflicting BCAST tracking prefixes. Jan 8, 2021
JackieXie168 pushed a commit to JackieXie168/redis that referenced this pull request Mar 2, 2021
Throw an error if there are conflicting bcast tracking prefixes.
@oranagra

Copy link
Copy Markdown
Member

a sporadic failure in this test on freebsd:

*** [err]: BCAST with prefix collisions throw errors in tests/unit/tracking.tcl
Expected 'CLIENT TRACKING ON BCAST PREFIX FOOBAR PREFIX FOO' to match 'ERR Prefix 'FOOBAR'*'FOO'*' (context: type eval line 4 cmd {assert_match {ERR Prefix 'FOOBAR'*'FOO'*} $output} proc ::test) 

https://github.com/redis/redis/runs/6516880161?check_suite_focus=true

rajkripal added a commit to rajkripal/redis that referenced this pull request Apr 19, 2026
…-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>
rajkripal added a commit to rajkripal/redis that referenced this pull request Apr 19, 2026
…-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>
rajkripal added a commit to rajkripal/redis that referenced this pull request Apr 19, 2026
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>
rajkripal added a commit to rajkripal/redis that referenced this pull request Apr 25, 2026
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>
rajkripal added a commit to rajkripal/redis that referenced this pull request Apr 27, 2026
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

approval-needed Waiting for core team approval to be merged release-notes indication that this issue needs to be mentioned in the release notes state:needs-doc-pr requires a PR to redis-doc repository state:to-be-merged The PR should be merged soon, even if not yet ready, this is used so that it won't be forgotten

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants