Consistent Hashing
Consistent hashing explained with diagrams: the hash ring, virtual nodes, minimal data movement, and its use in caches and databases.
Consistent hashing is a way to spread keys across a changing set of servers so that adding or removing a server moves only a small fraction of the keys. It is the reason a distributed cache or database can grow from 10 to 11 nodes without reshuffling almost all of its data.
The idea comes from David Karger and colleagues' 1997 paper on distributed caching ("Consistent Hashing and Random Trees"), written to relieve hot spots on the web. Note that "consistent" here has nothing to do with replica consistency or the C in ACID: it means the key-to-server mapping stays mostly the same when servers change. That property makes it a staple of caches and distributed databases.
The problem with hash mod N
The obvious way to pick a server for a key is server = hash(key) % N. It spreads keys evenly, but it breaks badly when N changes. Go from 4 servers to 5 and a key stays on the same server only if hash % 4 == hash % 5, which is true for about 1 key in 5. Roughly 80% of keys move.
For a cache that means most lookups suddenly miss and fall through to the database at the worst possible moment, when you were adding capacity. For a database it means copying most of the data across the network.
| Change | Keys that move with hash mod N | Keys that move with consistent hashing |
|---|---|---|
| 4 → 5 servers | ~80% | ~20% (only those the new server takes over) |
| 10 → 11 servers | ~91% | ~9% |
| 100 → 99 servers (one fails) | ~99% | ~1% (only the failed server's keys) |
How the hash ring works
Imagine the output range of a hash function (say 0 to 2^32 − 1) bent into a circle. Both servers and keys are hashed onto this same ring. Each key belongs to the first server clockwise from its position.
Now watch what happens when the membership changes:
- Adding server E between C and D: E takes over only the keys between C and E that used to belong to D. Every other key stays exactly where it was.
- Removing server B: only B's keys (k1 and k2) move, to the next server clockwise, C. Nothing else moves.
On average, adding or removing one of N servers moves about 1/N of the keys, the minimum possible, since the new server has to get its share from somewhere.
Two equivalent ways to picture the ring (positions 0 to 2^32 − 1 with a 32-bit hash): split the ring into arcs, one per server, and a key belongs to whichever arc its hash falls in; or, closer to real implementations, place servers as points on the ring and give each key to the first server clockwise from it. With servers A, B and C, item id:12345 might hash to a point whose next server clockwise is B, and id:67890 to one whose next server is C, so id:12345 → B and id:67890 → C. Server positions come from hashing their ID or IP address, or are set by hand when there are few servers, taking capacity into account.
Virtual nodes fix uneven load
With one point per server, failure is lopsided: if C goes down, all of C's keys move to the next server clockwise (A), which suddenly carries double load. Mapping each physical server to several points on the ring (A-B-C-A-B-C, two points each) means a failed server's keys split between the other two. Food for thought: does the order A-B-C-A-B-C behave differently from A-B-A-C-B-C? Both split C's load over A and B only if C's points are followed by different servers; random vnode placement with many points per server makes that true on average.
With only a few points on the ring, the gaps between servers are random, so one server can easily own twice another's share. And when a server fails, its whole range lands on one neighbour, doubling that neighbour's load.
The fix is virtual nodes (vnodes): hash each physical server onto the ring many times, for example hash("A#1"), hash("A#2") … hash("A#200"). Each server now owns many small arcs spread around the ring:
- Load evens out, because many small random arcs average out. With 100–200 vnodes per server the spread is typically within a few percent.
- When a server fails, its arcs are scattered, so its load spreads across all remaining servers instead of one unlucky neighbour.
- Heterogeneous hardware is easy: give a server with twice the capacity twice as many vnodes.
Looking up a key
In code, the ring is just a sorted array of vnode positions. Finding a key's server is a binary search for the first position greater than or equal to the key's hash, wrapping to the start if you run off the end: O(log V) for V virtual nodes.
positions = sorted(hash(f"{server}#{i}") for server in servers for i in range(200))
owner = {hash(f"{server}#{i}"): server for server in servers for i in range(200)}
def server_for(key):
h = hash(key)
i = bisect_left(positions, h)
return owner[positions[i % len(positions)]] # wrap around the ringReplication on the ring
Databases like Cassandra and DynamoDB also use the ring to place replicas: a key is stored on its owner and the next N − 1 distinct physical servers clockwise (skipping further vnodes of a server already chosen). Combined with read and write quorums, this gives a simple, decentralised answer to "which three machines hold this key?" See replication.
Alternatives
| Approach | How it works | Trade-off |
|---|---|---|
| Rendezvous (HRW) hashing | Score every server with hash(key, server), pick the highest | Same minimal movement, no ring or vnodes, but O(N) per lookup |
| Jump consistent hash | A tiny arithmetic function maps a key to a bucket number | Very fast and even, but servers must be numbered and only the last one can be removed |
| Range partitioning with a directory | A lookup table maps key ranges to servers | Flexible splits and moves, but needs a metadata service. See sharding |
| Fixed partitions | Hash into, say, 4,096 slots and assign slots to servers | Redis Cluster's 16,384 hash slots: simple rebalancing by moving whole slots |
Where it’s used
Partition data across nodes on a token ring with virtual nodes, and place replicas on the next distinct nodes clockwise.
Client libraries hash keys onto a ring of cache servers so adding a cache node invalidates only a small slice of the cache.
Envoy's ring-hash and Maglev policies send all requests for a key (a user, a session, a shard) to the same backend, keeping its local cache warm.
Route a user, a guild or a URL to a consistent set of servers so in-memory state and caches are reused.
In an interview
- Reach for consistent hashing whenever servers in a cache or partitioned store are added or removed often, and quantify the win: about 1/N of keys move instead of nearly all.
- Always mention virtual nodes; a ring without them is the most common follow-up gap.
- Explain how replicas are placed on the next distinct nodes, then connect it to quorum reads and writes.
- Know that it balances keys, not load: a single hot key still lands on one server, so you still need caching or key splitting for celebrities and viral items.
Further reading
- Consistent Hashing and Random Trees (Karger et al., 1997)ACM Digital Library