What is consistent hashing and why does it matter for distributed systems?
Take a moment.
Say your answer out loud or write it down first — retrieval is what makes it stick. Reveal when you're ready.
Short answer
Consistent hashing maps both data keys and server nodes onto the same hash ring. A key is stored on the first node encountered clockwise from its hash. When a node is added or removed, only the keys adjacent to it remap — the rest stay put. This minimizes data movement during scaling, which is why distributed caches and databases use it.
Detailed explanation
Naive hashing (hash(key) mod N) breaks when N changes: adding or removing a server remaps nearly every key, forcing a massive data migration and cache stampede. Consistent hashing (Karger et al., 1997) solves this. Build a hash ring covering the hash space. Place each node at one or more positions on the ring (via hashing the node ID, often with virtual nodes for even spread). Hash each key; walk clockwise to the first node — that node owns the key. When a node joins, it takes ownership of keys between its position and the next node clockwise; only those keys move. When a node leaves, its keys shift to the next clockwise node; again, only a fraction moves. Virtual nodes (vnodes) — each physical node gets many positions on the ring — smooth out uneven distributions and ensure balanced load. The technique underpins Dynamo, Cassandra, Riak, and distributed caches like Memcached. Related idea: rendezvous hashing (highest random weight) picks the node with the highest hash(key + node) and has similar minimal-remapping properties with simpler implementation. The practical benefit: you can add capacity without rehashing the entire dataset, and failures cause graceful degradation rather than global reshuffling.
Example
Ring with nodes A, B, C at positions 100, 200, 300:
- Key hash 150 → walks clockwise to B (owns it)
- Key hash 350 → wraps to A
Add node D at position 250:
- Only keys between 200–250 move from B to D. Everything else stays.
Remove node B:
- Keys B owned move to C. A and D unaffected.Interview tip
Explain the clockwise-walk rule and state the payoff: only K/N keys move when a node changes. Naming one real system (Cassandra or DynamoDB) that uses it grounds the answer.
Common mistakes
- Confusing consistent hashing with simple modulo hashing.
- Not mentioning virtual nodes, which balance load.
- Forgetting the actual benefit: minimal key remapping on resize.