System design deep dive
Consistent Hashing: deep dive
Consistent hashing assigns keys to servers so that adding or removing a server moves only about 1/N of the keys instead of nearly all of them. It is the quiet workhorse behind distributed caches and databases like Cassandra and DynamoDB, and a favourite interview follow-up to sharding.
Why plain modulo hashing breaks
With server = hash(key) % N, going from 4 to 5 servers changes the result for roughly 80% of keys, because a key only stays put if hash % 4 equals hash % 5. For a cache, that means an instant drop to a near-zero hit rate and a flood of database traffic. For a database, it means migrating most of your data. Consistent hashing exists to make membership changes cheap.
How consistent hashing works, step by step
- Pick a hash function with a large output space, such as the first 64 bits of MD5 or MurmurHash, and treat the output range as a circle.
- Place each server on the circle many times by hashing labels like
cache-A#0,cache-A#1, up tocache-A#149. These positions are virtual nodes. - Store all positions in a sorted structure, such as a
TreeMapfrom position to server. - To locate a key, hash it and find the first position at or after that hash, wrapping to the start of the circle if needed. That position's server owns the key.
- When a server is added, its virtual nodes land in many places on the ring, and each one takes over only the keys between it and its predecessor. On average 1/(N+1) of keys move, all to the new server.
- When a server is removed, its keys go to the next positions clockwise, which, thanks to virtual nodes, are spread across many different servers rather than one unlucky neighbour.
class HashRing {
private final TreeMap<Long, String> ring = new TreeMap<>();
private final int vnodes;
HashRing(int vnodes) { this.vnodes = vnodes; }
void addServer(String server) {
for (int i = 0; i < vnodes; i++) ring.put(hash(server + "#" + i), server);
}
void removeServer(String server) {
for (int i = 0; i < vnodes; i++) ring.remove(hash(server + "#" + i));
}
String serverFor(String key) {
if (ring.isEmpty()) throw new IllegalStateException("no servers");
Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
return (e != null ? e : ring.firstEntry()).getValue(); // wrap around
}
// hash(): first 8 bytes of MD5 or Murmur3, as a long
}Replication on the ring
Distributed databases extend the lookup: instead of stopping at the first owner, they keep walking clockwise and collect the next R distinct physical servers (skipping additional vnodes of servers already chosen). With R = 3, those three servers form the key's preference list. Placing replicas in different racks or availability zones is done by also skipping servers in a zone that is already represented. This is the foundation that makes replication and quorum reads work in Dynamo-style systems.
Consistent hashing vs alternatives
| Scheme | Keys moved on resize | Lookup cost | Notes |
|---|---|---|---|
| Modulo hash | About (N-1)/N | O(1) | Fine only if N never changes |
| Ring with vnodes | About 1/N | O(log V) for V vnodes | Most common; Cassandra, DynamoDB |
| Rendezvous (HRW) hashing | About 1/N | O(N) per lookup | No ring state; great for small N |
| Jump consistent hash | About 1/N | O(log N), no memory | Servers must be numbered 0..N-1; cannot remove arbitrary ones |
| Fixed slots + map | Only reassigned slots | O(1) | Redis Cluster uses 16,384 slots |
When to use it (and when not to)
Use consistent hashing whenever servers in a key-partitioned tier come and go: client-side sharding across Memcached nodes, partitioning in a sharded database, sticky routing of WebSocket users to chat servers, or spreading work across stateless workers that keep local caches. It is unnecessary when the number of partitions is fixed forever, and it is the wrong tool when you need range scans over ordered keys, because hashing scatters neighbouring keys across the ring.
Common mistakes in interviews
- Describing the ring without virtual nodes. With one position per server, arc sizes vary wildly, so some servers own several times more keys than others.
- Claiming consistent hashing fixes hot keys. It balances the number of keys, not the traffic per key; one viral key still lands on one server.
- Forgetting heterogeneous hardware: give bigger servers proportionally more vnodes.
- Not explaining how clients learn about ring membership changes (gossip, a coordination service like ZooKeeper, or a config push).
Interview questions
›How many virtual nodes should each server have?
Typically 100 to 256. More vnodes make load more even (the standard deviation of load shrinks roughly with the square root of the vnode count), but increase ring metadata and the number of small ranges to stream during rebalancing. Cassandra historically defaulted to 256 and newer versions use fewer, combined with smarter token allocation.
›What happens to the cache hit rate when you add a node to a 10-node cache cluster?
Roughly 1/11 of keys, about 9%, now map to the new node and miss once until it is warm. The other 91% keep hitting. With modulo hashing, about 91% would miss instead.
›How does Redis Cluster differ from a hash ring?
Redis Cluster hashes each key with CRC16 into one of 16,384 fixed slots, and each master owns a set of slots. Rebalancing moves whole slots between nodes. It achieves the same goal of minimal movement with simpler, explicit bookkeeping.
›What is rendezvous hashing?
For each key, compute a score hash(key, server) for every server and pick the highest. Removing a server only moves the keys it owned, and no ring needs to be stored. The lookup is O(N), which is fine for tens of servers.
›How would you handle a hot key on a consistent hash ring?
Detect it through per-key metrics, then replicate it to several nodes and spread reads across them, for example by appending a random suffix from 0 to 9 to the key on reads. A small local cache in front of the distributed tier also absorbs most of the traffic for a handful of super-hot keys.