Consistent Hashing

Intermediate · 13 min read · High-Level Design, Storing Data

The hash ring, virtual nodes, and why adding a server should not reshuffle everything.

Whenever you distribute keys across a changing set of servers — cache nodes, database shards, WebSocket servers — you need a mapping from key to server. Consistent hashing is a mapping that stays mostly stable when servers are added or removed.

The problem with modulo hashing

The obvious approach is:

The hash ring

Consistent hashing maps both servers and keys onto the same circular hash space — for example, 0 to 2^32 − 1, wrapped into a ring.

The problem: uneven distribution

With only a few servers placed at random positions, the arcs between them are uneven. One server might own 50% of the ring and another 10%. And when a server leaves, its entire load lands on a single neighbour, which may then overload and fail too — a cascading failure.

Virtual nodes

The fix is to place each physical server on the ring many times, at different positions, as virtual nodes (vnodes).

Implementation sketch

Lookup is O(log V) where V is the total number of virtual nodes. Use a fast, well-distributed non-cryptographic hash (MurmurHash3, xxHash).

Replication on the ring

Consistent hashing extends naturally to replication: store each key on the first N distinct physical servers clockwise from its position. Skip virtual nodes belonging to a server already chosen, and in multi-datacenter setups, prefer servers in different racks or zones.

Where it's used

Alternatives worth knowing

Interview questions

  • Why can't we just use hash(key) mod N for a distributed cache?
  • What problems do virtual nodes solve?
  • Consistent hashing gives even key distribution. Does it guarantee even load?
  • How does a client know the current state of the ring?

Practice

Write your answer before opening the suggested one. Anything you mark "Partly" or "Missed it" comes back in your review deck.

Further reading

Key takeaways

  • hash mod N remaps almost every key when N changes; consistent hashing remaps only ~1/N.
  • Servers and keys share one hash ring; each key belongs to the next server clockwise.
  • Virtual nodes give even distribution, spread out failover load, and support weighted capacity.
  • Replication extends naturally: store a key on the next N distinct servers clockwise.
  • Consistent hashing balances keys, not traffic — hot keys still need separate handling.

Previous: Partitioning & Sharding · Next: Object Storage & File Uploads