[v92-audit] hotkeys: per-slot hotkeysPurgeSlot rehashes every tracked key, CLUSTER DELSLOTSRANGE blocks 24s

[madolson]

With hot key detection enabled, removing one cluster slot calls hotkeysPurgeSlot(), which walks every tracked entry in both Space-Saving windows and recomputes keyHashSlot() over the full key name to decide whether the entry belongs to that slot. Slot removal happens inside loops over all 16384 slots, so the work is O(slots x 2 x hotkeys-top-k x key-name-length) of crc16 on the main thread: on a single cluster-enabled node with hotkeys-top-k 1000 and tracked names of 1 KiB, CLUSTER DELSLOTSRANGE 0 16383 blocks for 24.033 seconds against 0.000s with detection off. That is longer than the default 15s cluster-node-timeout, so the rest of the cluster marks the node failed while it sits in the purge. clusterReset() already dodges this with a bulk hotkeysPurgeAll() before its per-slot loop, but the other clusterDelSlot() loops did not get the same treatment, including clusterUpdateSlotsConfigWith(), which runs off the cluster bus and so needs no local command at all.

Details

Problem

hotkeysPurgeSlot() is per-slot and its cost is proportional to the whole tracked set:

• src/hotkeys.c:66-68 — hotkeysPurgeSlot(slot) calls spaceSavingManagerRemoveIf(m, hotkeysItemInSlot, &slot).
• src/space_saving.c:296-300 — spaceSavingManagerRemoveIf scans both the live and the frozen window.
• src/hotkeys.c:54-57 — the predicate is keyHashSlot(key, sdslen(key)) == slot. The slot is not cached per entry, by design ("The cluster hash slot is not stored per entry — it is derived from the key name on demand", src/hotkeys.c:52-53), so every call crc16s every tracked key name in full.

clusterDelSlot() calls it unconditionally (src/cluster_legacy.c:7139), and six callers invoke clusterDelSlot() in a loop over up to 16384 slots:

src/cluster_legacy.c:1773   clusterReset            for (j = 0; j < CLUSTER_SLOTS; j++) clusterDelSlot(j);
src/cluster_legacy.c:2432   clusterDelNode          if (server.cluster->slots[j] == delnode) clusterDelSlot(j);
src/cluster_legacy.c:3376   clusterUpdateSlotsConfigWith
src/cluster_legacy.c:3446   clusterUpdateSlotsConfigWith
src/cluster_legacy.c:7155   clusterDelNodeSlots
src/cluster_legacy.c:7836   clusterUpdateSlots      (CLUSTER DELSLOTS / DELSLOTSRANGE)
src/cluster_migrateslots.c:900

Only clusterReset is protected, and the comment there names the exact problem:

    /* Unassign all the slots. */
    hotkeysPurgeAll(); /* Bulk purge before individual clusterDelSlot calls */
    for (j = 0; j < CLUSTER_SLOTS; j++) clusterDelSlot(j);

(src/cluster_legacy.c:1771-1773)

clusterUpdateSlotsConfigWith at src/cluster_legacy.c:3376 is the one that matters most. Both of its callers are inside clusterProcessPacket (src/cluster_legacy.c:4665 and :4822, function starts at :4113), so it runs off the cluster bus when another node's gossip or UPDATE message claims slots this node owns. A slot handoff or a failover elsewhere imposes the stall on a node that issued no command at all.

Repro

Single cluster-enabled node at 3f9062e, plain build, empty keyspace. The tracked names do not even have to exist as keys, because a miss is sampled like a hit (src/db.c:133 is after the miss branch of lookupKeyWithFlags).

valkey-server --port 7444 --cluster-enabled yes --save '' \
  --hotkeys-top-k 1000 --hotkeys-sampling-percentage 100 --hotkeys-window-seconds 300
valkey-cli -p 7444 cluster addslotsrange 0 16383

then

c.pipe([("GET", ("k%05d" % i).encode() + b"x" * 1024) for i in range(1000)])
t = time.time(); c.cmd("CLUSTER", "DELSLOTSRANGE", "0", "16383"); print(time.time() - t)

Verbatim, on the identical tracked state, contrasting the protected caller against an unprotected one:

dbsize 0
CLUSTER RESET SOFT b'OK'  0.009s  (bulk hotkeysPurgeAll first)
CLUSTER DELSLOTSRANGE 0 16383 b'OK'  24.033s  (per-slot hotkeysPurgeSlot)
PING b'PONG' dbsize 0

Scaling is exactly linear in hotkeys-top-k and in key-name length, which confirms the attribution:

top-k=0     keylen=64      DELSLOTSRANGE b'OK'  0.000s
top-k=1000  keylen=16      DELSLOTSRANGE b'OK'  0.370s
top-k=1000  keylen=64      DELSLOTSRANGE b'OK'  1.563s
top-k=1000  keylen=256     DELSLOTSRANGE b'OK'  6.058s
top-k=1000  keylen=1024    DELSLOTSRANGE b'OK'  24.022s
top-k=100   keylen=1024    DELSLOTSRANGE b'OK'  2.581s

Key names of 4 KiB pushed a single CLUSTER DELSLOTSRANGE 0 16383 past a 60 second client timeout. Names with a hash tag are cheap (keyHashSlot only hashes the tag), so the cost is driven by untagged names, which is the common case outside multi-key workloads.

Fix

Cache the slot on the entry at insert time. spaceSavingSlot already carries a uint32_t hash (src/space_saving.c:26-32); a uint16_t slot beside it makes the predicate a compare instead of a crc16 over the whole name, which removes the keylen factor entirely and leaves only 16384 x 2K cheap integer compares (the top-k=1000 keylen=16 row above, 0.370s). The design note at src/hotkeys.c:52-53 chose against storing it to keep the entry small; the trade is 2 bytes per entry against O(slots x K x len) crc16. Removing the remaining slots x K factor needs a range-aware purge (one pass with a slot bitmap) for CLUSTER DELSLOTSRANGE and clusterUpdateSlotsConfigWith.

Two tempting alternatives lose. Calling hotkeysPurgeAll() in the other loops the way clusterReset does is wrong for clusterUpdateSlotsConfigWith, which only reassigns the slots the sender claims, so it would throw away hot key data for slots this node still owns. An early return in hotkeysPurgeSlot() when the tracked set is empty does not help either: after the first slot is purged the set still holds every entry belonging to the other 16383 slots. That guard is only what makes clusterReset's explicit hotkeysPurgeAll() cheap, not a fix on its own.

Note

Not memory unsafety and not divergence. It is a main-thread stall long enough to cause failure detection and a spurious failover, reachable via CLUSTER DELSLOTS/DELSLOTSRANGE and via the cluster bus. hotkeys-top-k defaults to 0, so the feature is off unless an operator enables it.

Introduced by #3708 (Add server-side hot key detection).

This was generated by AI but verified, with love, by a human.