Consistent Hashing and Sharding

TL;DR: Modulo sharding is correct and unusable at scale, because changing the server count remaps almost every key. Consistent hashing puts both servers and keys on a ring and assigns each key to the next server clockwise, so adding one server takes over only the arc between it and its predecessor: roughly one over N of the keys move rather than nearly all of them. A plain ring distributes badly with few servers, because arc lengths are random, so each server is placed at many points on the ring as virtual nodes, which pulls the spread toward even. Rendezvous hashing is a simpler alternative with the same movement property and no ring to maintain. The reason this matters for LLM serving is cache affinity: routing a request by a hash of its prompt prefix sends it to the replica that already holds the corresponding KV blocks, turning a full prefill into a cache hit.

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

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: the spread is a few percent
  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
  so turn 2 of a conversation hashes to the same point as turn 1 and lands on the same replica

what it buys
  with a 2,000-token shared head on a 2,200-token prompt, a hit removes about 91 percent of
    prefill work
  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

The movement arithmetic, said as a fraction. A candidate who says consistent hashing moves fewer keys is repeating a definition; one who says a change moves about one over N of them against nearly all for modulo has the property that matters. Virtual nodes are the second signal, because a ring without them distributes badly and mentioning them shows the candidate has implemented one rather than read about it. In a serving context, the third signal is choosing the prefix rather than the request as the key.

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.