Bounded-Load Consistent Hashing

The ring balances load in expectation, but traffic is not an expectation. One viral key, one heavy tenant or one unlucky arc, and a single node runs at three times the average while the rest of the fleet idles. Tail latency is set by the slowest shard, so everyone's requests feel it. Virtual nodes smooth the keyspace; they do nothing about hot keys. Your ring will learn to say "this node is full, try the next one".

One rule added to the ring

Mirrokni, Thorup and Zadimoghaddam ("Consistent Hashing with Bounded Loads", 2016) added a single rule and got a hard guarantee:

Walk clockwise as usual. If the node you reach is already at its cap, skip it and keep walking.

The cap is ceil((1 + epsilon) * average load), where the average includes the request being placed. That is 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. A small epsilon means tight balance but more keys displaced from their natural owner (less cache locality); a large one behaves almost like a plain ring with a loose safety net. Production uses 0.1 to 0.5.

HAProxy expresses it as hash-balance-factor in percent (Vimeo's implementation): hash-balance-factor 125 means a cap at 125% of the average, epsilon 0.25. Envoy exposes the same knob as hash_balance_factor for its ring-hash and Maglev balancers. This course uses the percent form, so the cap is integer arithmetic:

cap = ceil( balance * (total + 1) / (100 * n) )

total is the sum of all current loads, n the number of nodes, and balance defaults to 125. The + 1 counts the request being placed, and the cap is recomputed for every assignment, because the average moves.

A walk-through

Three nodes web1, web2, web3, balance 125, and one hot key viral whose natural owner is web1. Each row is one ASSIGN viral:

#   cap   what the walk finds                       chosen   loads web1/web2/web3
1   1     web1 has 0, below 1                       web1     1/0/0
2   1     web1 is full, web2 has 0                  web2     1/1/0
3   2     web1 has 1, below 2                       web1     2/1/0
4   2     web1 is full, web2 has 1                  web2     2/2/0
5   3     web1 has 2, below 3                       web1     3/2/0
6   3     web1 is full, web2 has 2                  web2     3/3/0
7   3     web1 and web2 are full, web3 has 0        web3     3/3/1

Without the cap, all seven would land on web1. Note that skipping happens per ring entry: a node with many points can be met several times in the walk, and each time it is full it is skipped again.

In a real service a node's load is its in-flight requests, so finishing a request lowers it. That is RELEASE, and it lowers total and therefore the cap.

Common mistakes

• Dropping the + 1. With total instead of total + 1 the very first CAP prints 0 and the first ASSIGN finds every node "full".
• Computing the cap once. The cap grows as the total grows. A cap stuck at 1 sends the third key past web1 even though web1 has room.
• Floor instead of ceiling. Integer division rounds down; the cap must round up, otherwise the nodes cannot hold the load.
• Omitting zero loads. LOADS lists every node, including the ones that hold nothing yet.
• Going around twice. The walk visits each ring entry at most once; when nothing has room (which the cap prevents) the answer is NONE.

Your exercise

The ring and LOOKUP are in the starter. You write the cap, the capped walk and the release.