[BUG] Tracking table items not cleaned after client disconnect

[JimB123]

Describe the bug

TrackingTable in tracking.c is a RAX of key->RAX. The inner RAX is a set of client IDs. When a client is deleted, it isn't removed from this table (intentionally) to avoid an O(N) operation.

The tracking table gets cleaned when the key is modified/deleted.

A problem occurs when clients access a number of keys, and then disconnect. If the keys are rarely modified, the inner RAX grows with invalid clients and is never cleaned up. This can result in unbounded growth on the inner table.

NOTE: The outer table has a maximum size and will discard keys once that size is hit. But there is no limit on the inner table.

ALSO - it appears that there is no defragmentation applied to the TrackingTable. This makes it likely that small buckets 8/16 bytes will be unable to defragment if TrackingTable entries are present.

To reproduce

Create many clients with tracking enabled to connect, read a large set of keys, then disconnect — and those keys are rarely/never modified afterward. This leaves the inner rax entries permanently occupied with dead client IDs.

Expected behavior

• There should be a limitation on the inner rax size (in aggregate)
• A mechanism must exist to clean up dead entries (sweeper?)
• Defragmentation should be applied to the TrackingTable.

[quanyeyang]

I would like to help work on this! ´ ▽ ` )ﾉ

[rayjinghaolei]

I would also like to help out since I worked with Jim to raise this issue.

[quanyeyang]

Hi @rayjinghaolei @JimB123 — following up on helping with this.

I'd like to sync on design before coding. Happy to take a first cut at
the implementation + Tcl tests once we agree on the approach.

Proposed direction

1. Dead-ID sweeper (progressive, not on disconnect)

• Keep lazy cleanup in disableTracking() so disconnect stays O(1).
• From server cron / beforeSleep, walk TrackingTable with a bounded
  effort budget (same spirit as trackingLimitUsedSlots).
• For each inner-rax entry: if lookupClientByID(id) == NULL (or the
  client no longer has tracking), remove that ID and decrement
  TrackingTableTotalItems; free the inner rax when empty.
• Optionally, when trackingInvalidateKey skips a dead ID, remove it
  instead of only continue.

2. Aggregate / inner limit

• Cap TrackingTableTotalItems (and/or per-key inner size), not only
  outer tracking-table-max-keys.
• When over limit: sweep dead IDs first; if still over, fall back to
  invalidating random keys via the existing path.

@JimB123 — for the aggregate cap, do you have a preferred default /
knob shape from experience? For example:

• reuse / scale off tracking-table-max-keys (e.g. items ≤ N × max_keys),
• a separate tracking-table-max-items config, or
• a hard per-key inner-rax limit plus a global items cap?

3. Active defrag for TrackingTable

• Reuse defragRadixTree() from defrag.c for the outer table and each
  inner client-ID rax (Stream paths look like a good template).

I'm leaning toward landing (1)+(2) first, with (3) as a follow-up if that
keeps the PR smaller — but happy to follow your preferred split.

Note on #4163

The current diff adds an unused root-level file and does not modify
TrackingTable in src/tracking.c, so it doesn't address the lazy-cleanup
/ unbounded inner-rax growth described here. A real fix needs to land in
the tracking + cron/defrag paths, with tests under tests/. I think we
can disregard that PR for this work.

@rayjinghaolei — do you already have a preferred split (design vs code vs
tests) or an approach you want to stick to? I can hold off on opening a
PR until we've agreed.

[rayjinghaolei]

Hi @quanyeyang Thanks for the discussion. Regarding your proposed direction, on high level I am aligned with your ideas. I was looking into this myself and my implementation is very similar to what you are proposing yet there are minor differences open for discussion. Listing them below

Implementation discussion points

• Sweep rate — the sweeper visits TRACKING_SWEEP_KEYS_PER_CALL (100) keys per second,
  so a full pass over a table at the tracking-table-max-keys default (1,000,000) takes
  hours. This is intentional background reclamation (the alternative is the memory never
  being freed), and tracking-table-max-items covers acute pressure. Open to making the
  rate adaptive or configurable if there's a preference — kept it a documented constant to
  minimize new surface area.

• Liveness strictness — the sweeper only removes an ID when the client is fully gone
  (lookupClientByID(id) == NULL). IDs of clients that are still connected but have since
  disabled tracking (or switched to BCAST) are left for the existing lazy path. Removing
  those too would be safe (a client re-enabling tracking re-registers on its next read)
  and would reclaim more; happy to add the flag.tracking check if preferred.

• Bound enforcement order — when over tracking-table-max-items, enforcement evicts
  random keys directly (mirroring trackingLimitUsedSlots) rather than sweeping dead IDs
  first. The sweeper runs continuously anyway, so in steady state dead IDs are already
  being reclaimed; a sweep-first step under pressure would only help probabilistically
  since it must stay bounded-effort. Can add a bounded sweep chunk at the top of
  enforcement if reviewers prefer fewer spurious invalidations to live clients.

• Default-off bound — tracking-table-max-items defaults to 0 (unlimited) so there
  is zero behavior change without opt-in; the sweeper alone fixes the leak by default.
  An alternative is a non-zero default (or scaling off tracking-table-max-keys), which
  would protect unconfigured deployments at the cost of a behavior change on upgrade.

• Per-key inner limit — a hard cap on a single key's inner rax size was considered but
  not implemented: it penalizes legitimately hot keys (many live tracking clients) and the
  aggregate cap plus sweeper already bound the failure mode. Can revisit if there's a use
  case.

• PR split — all three pieces (sweeper, bound, defrag stage) are in this PR since they
  share tests and context, but they layer cleanly: sweeper + defrag are independent, and
  the bound only adds a config plus one function. Happy to split (e.g. sweeper+bound first,
  defrag follow-up per the suggestion in [BUG] Tracking table items not cleaned after client disconnect #4143) if that eases review.