Consistent Hashing and Sharding
Consistent hashing limits key movement when a shard set changes. It can preserve cache affinity, but it does not guarantee that cached data is present or that load is balanced.
TL;DR: Assign keys to stable positions or scores so membership changes move only an affected share. Virtual nodes can improve distribution, while hot keys still need separate handling. In serving, use the assignment as a preferred location and check compatibility, residency and queue load before expecting reuse.
Why modulo fails
keys assigned as hash(key) mod N
N = 4 -> 5, how many keys keep their server?
a key stays only if hash mod 4 == hash mod 5, which holds for about 1 in 5 of them
so roughly 80 percent of keys move
the general case
moving from N to N+1 remaps approximately N/(N+1) of the keys, which tends to 100 percent
as N grows
what that costs
for a cache: nearly every entry is now on the wrong node, so the hit rate collapses to
almost zero and every request becomes a miss at once
for a stateful shard: nearly all data must be moved
sanity: the failure is not that modulo is wrong, it is that it is maximally disruptive at
exactly the moment you are adding capacity because you are already under load
The ring, and what it moves instead
Hash each server to a point on a ring of size 2 to the 32 or 2 to the 64. Hash each key the same way. A key belongs to the first server clockwise from it.
adding a server
the new server takes over only the arc between itself and its predecessor
expected fraction of keys moved = 1 / (N + 1)
N = 4 -> 5: 1/5 = 20 percent, against roughly 80 percent for modulo
N = 20 -> 21: 1/21 = 4.8 percent
and no other server's assignment changes
removing a server
its arc passes to the next server clockwise
expected fraction moved = 1 / N, and again nothing else moves
sanity: the property is that a change touches only the changed server's share, which is what
makes scaling a cache survivable rather than an outage
Use a small section of the ring to see exactly which keys change owner.
Before D joins
- A at 12
- Key hashes to 20
The next point clockwise is C at 28.
- C at 28 owns key 20
After D joins at 24
- A at 12
- Key hashes to 20
The next point is now D at 24.
- D takes keys in (12, 24]
Keys in (24, 28] still belong to C.
With virtual nodes
- Each server has many ring points.
- D takes the preceding interval at each new point; other assignments remain unchanged.
Virtual nodes, and why a plain ring is uneven
With few servers the arcs between random points vary a lot, so one server can own several times another's share. Placing each server at many points averages the arcs.
imbalance against virtual nodes per server
the spread of load narrows roughly as one over the square root of the number of points
1 point per server: load can differ by a large factor between servers
100 points per server: roughly 10% relative spread under a simplified independent-point model
200 to 500 points: common in production, at the cost of a larger ring to search
the cost
the lookup is a binary search over the sorted points, so it is logarithmic in
servers x points per server, which stays cheap even at 500 points each
sanity: virtual nodes are not an optimization, they are what makes the ring usable below a
few hundred servers, and omitting them is the most common way a first implementation
distributes badly
Rendezvous hashing reaches the same movement property differently: for each key, compute a score from the key and each server, and pick the highest. It needs no ring, distributes evenly without virtual nodes, and costs a pass over the servers per lookup, which is fine for tens of servers and not for thousands.
The serving application: routing by prefix
An LLM replica holds KV blocks for prefixes it has already processed, so sending a request to a replica that holds its prefix turns prefill into a cache hit. Hashing the prompt's prefix rather than the whole request makes that affinity stable across turns of a conversation.
what the routing key should be
not the whole prompt, since every turn differs and every turn would route somewhere new
a prefix: the system prompt plus tool definitions plus the conversation so far, truncated
to a fixed length or a fixed token count
choose a stable portion or explicit affinity key; a short first prompt that later grows
beyond the truncation length can otherwise change the key
what it buys
with a 2,000-token shared head on a 2,200-token prompt, a compatible resident hit can reuse 91 percent of the prompt tokens;
the saved execution time also depends on attention and engine behavior
and the affinity survives adding a replica, because only one over N of the prefixes move
sanity: this is the reason consistent hashing appears in an inference stack at all, and it is
why the routing key is a prefix rather than the request
Request Routing and Load Balancing for LLMs covers the serving side, including what to do when affinity and load balance disagree, which they will: a replica holding a popular prefix attracts traffic, and the router needs a cap on how far affinity may skew the load.
What interviewers are listening for
Explain which keys move when a server joins or leaves and what assumptions make the expected fraction meaningful. Then consider unequal server capacity and one unusually hot key. For prefix routing, distinguish a stable assignment from proof of a cache hit and state when load should override affinity.
Key takeaways
- Modulo sharding remaps roughly N over N+1 of keys when the server count changes, which collapses a cache at the worst moment.
- A hash ring moves about one over N+1 of keys when adding a server, and nothing else changes.
- Virtual nodes narrow the load spread roughly as one over the square root of the point count; 100 to 500 per server is typical.
- Rendezvous hashing gives the same movement property with no ring, at a cost linear in servers per lookup.
- For LLM serving, hash a prompt prefix rather than the request, so a conversation returns to the replica holding its KV blocks.