Consistent Hashing Explained for System Design Interviews

Consistent hashing comes up whenever data is spread across machines: distributed caches, key-value stores, sharded databases, load balancers with sticky routing. Interviewers want to know that you understand the problem it solves, not just the ring diagram.

The problem with hash(key) mod N

The obvious way to pick a server for a key is hash(key) mod N, where N is the number of servers. It spreads keys evenly, and it breaks the moment N changes.

Go from 4 servers to 5: a key stays put only if hash mod 4 equals hash mod 5. That's true for about 1 in 5 keys, so roughly 80% of keys move.

For a cache, that means most keys miss at once and the database takes the full load. For a database, it means moving most of your data to add one machine.

The ring

Consistent hashing maps both servers and keys onto the same circular hash space (picture 0 to 2³² − 1 bent into a circle):

  1. Hash each server's ID to a position on the ring.
  2. Hash each key to a position on the ring.
  3. A key belongs to the first server clockwise from its position.

Now add a fifth server: it takes over only the keys between itself and the previous server on the ring. Roughly 1/5 of keys move, the minimum possible. Removing a server moves only the keys it owned, to its clockwise neighbour.

Virtual nodes

With only a few servers, their positions on the ring are uneven, so some servers own much bigger arcs than others. Also, when a server fails, all its keys land on one neighbour.

The fix is virtual nodes: each physical server appears at many points on the ring (for example 100–200), by hashing serverId#0, serverId#1, and so on.

  • Load evens out, because each server owns many small arcs.
  • When a server fails, its keys spread across many servers instead of one.
  • Heterogeneous hardware: give a bigger machine more virtual nodes so it takes a bigger share.

Replication on the ring

To store each key on R servers, walk clockwise from the key and take the next R distinct physical servers (skipping extra virtual nodes of a server you already picked). This is the scheme popularised by Amazon's Dynamo paper and used, with variations, in systems like Cassandra.

Pair it with a consistency choice: with R replicas, writes acknowledged by W of them and reads querying Rq of them, W + Rq > R means every read overlaps at least one replica that has the latest acknowledged write.

Implementing the lookup

Keep the ring as a sorted list of (position, server). To find a key's server, hash the key and binary search for the first position greater than or equal to it, wrapping around to the start if you run off the end. Lookups are O(log V) for V virtual nodes.

ring = sorted([(hash(f"{server}#{i}"), server) for server in servers for i in range(VNODES)])

def owner(key):
    h = hash(key)
    i = bisect_left(ring, (h,))
    return ring[i % len(ring)][1]

Forgetting the wrap-around (% len(ring)) is the classic bug: keys that hash past the last position must go to the first server.

Alternatives worth naming

  • Rendezvous (highest random weight) hashing: for each key, score every server and pick the highest. Simple, with minimal movement, but O(N) per lookup.
  • Jump consistent hash: very fast and needs no ring, but servers must be numbered sequentially, so removing one from the middle is awkward.

Naming one alternative and its trade-off is a strong signal; you rarely need to go deeper.

What interviewers push on

  1. "How many keys move when a server is added?" (About 1/N of them.)
  2. "Why virtual nodes?" (Even load, failure spread, weighted capacity.)
  3. "A single key is extremely hot. Does consistent hashing help?" (No. It balances many keys, not one; replicate or cache the hot key.)
  4. "How do clients know the ring?" (A config service or gossip protocol distributes membership; clients cache it.)
  5. "What happens to data during the move?" (Stream the affected ranges to the new owner before switching reads.)

Practise it in context. Prepd's key-value store and distributed cache questions are where data placement comes up naturally, and the AI-assisted coding track has a consistent hash ring problem where you fix, review and extend a real implementation.

Practise it