Bounded-Load Consistent Hashing

The ring balances load in expectation. Actual traffic is not an expectation: one viral key, one heavy tenant, one unlucky arc, and a single node runs at 3x the average while the fleet idles — and because tail latency is set by the slowest shard, everyone's requests feel it. Vnodes smooth the keyspace; they do nothing about hot keys.

Mirrokni, Thorup, and Zadimoghaddam ("Consistent Hashing with Bounded Loads", 2016 — Google Research plus the University of Copenhagen) added one rule to the ring and got a hard guarantee:

Walk clockwise as usual — but if the next node is already at its cap, skip it and keep walking.

The cap is ceil((1 + epsilon) * average_load). That's the whole algorithm, and it buys a theorem: no node ever holds more than (1+epsilon) times the average — not usually, ever. Epsilon is the dial. Small epsilon (0.1) means tight balance but more keys displaced from their natural owner (worse cache locality); large epsilon (1.0) means almost pure consistent hashing with a loose safety net. Production favors 0.1-0.5.

This escaped the paper unusually fast. Vimeo's Andrew Rodland implemented it in HAProxy, where it ships as hash-balance-factor — the setting hash-balance-factor 125 means "cap = 125% of average", i.e. epsilon = 0.25, exactly this exercise's EPSILON. Google reported using it for Cloud Pub/Sub, and Envoy exposes the same knob (hash_balance_factor) for its ring-hash and Maglev balancers. The appeal: you keep consistent hashing's stickiness (same key, same backend, warm cache) 99% of the time, and under a hot-key storm the overflow spills to the next nodes instead of melting one machine.

In this exercise the cap is recomputed at every assignment over the count including the incoming key:

Trace the visible test — nodes A, B, C (the usual clustered vnodes; every key wraps to (148, A) first):

CAP        -> ceil(1.25 * 1/3) = 1
ASSIGN k1  -> cap 1: A has 0 < 1        -> A   (loads A=1)
ASSIGN k2  -> cap 1: skip (148,A),(149,A); B has 0 < 1 -> B
ASSIGN k3  -> cap ceil(1.25 * 3/3) = 2: A has 1 < 2    -> A
STATS      -> A: 2 / B: 1 / C: 0

Note k2: the walk skips every vnode entry whose real node is full — both of A's leading tuples — before reaching B's.

Your exercise

ADD_NODE, ASSIGN <key> (print the chosen node, or NONE if the ring is empty or everyone is capped), STATS (<name>: <load> for every node, sorted, zero-loads included), CAP. The grader-caught mistakes: dropping the + 1 — with total instead of total + 1, the very first CAP prints 0 instead of 1 and the first ASSIGN finds all nodes "full" and prints NONE where the grader expects A. Computing the cap once instead of per-assignment — with the cap stuck at 1, ASSIGN k3 walks past A and B to print C, but the expected output is A (the cap has grown to 2 by then). And the STATS contract flip: unlike the weighted lesson's STATS, this one includes C: 0 — omitting zero-load nodes fails the visible test on its last line.