HLD · Distribution

Consistent Hashing

Distribute keys across nodes with minimal remapping when nodes join or leave.

1. The problem with simple hash mod

server = hash(key) % N — when N changes from 10 to 11, almost every key maps to a different server → cache stampede, mass data movement.

Example: Memcached cluster adds a node; mod-N reshuffles 90% of keys → DB overload on misses.

2. Consistent hashing idea

Hash servers and keys onto a ring (0 to 2³²-1). Key belongs to first server clockwise on the ring.

When a server is added/removed, only keys between that server and its predecessor move — not all keys.

3. Virtual nodes (vnodes)

Each physical server gets many points on the ring (e.g., 150 virtual nodes) for even distribution.

Without vnodes, uneven arc lengths cause hot spots.

Example: 3 servers with 100 vnodes each → smooth load even with skewed keys.

4. Where it's used

• Distributed caches (Memcached, Redis Cluster)
• CDNs routing requests to edge groups
• Databases: Cassandra, DynamoDB partition placement
• Load balancers (consistent hash on user_id for sticky routing)

5. Walkthrough example

Ring with servers A, B, C. Key "user:42" hashes to position 75 → clockwise first server is B.

Server D joins at position 70. Only keys between 70–75 (previously on B) move to D. Keys on A and C unchanged.

6. Replication on the ring

Store each key on server + next K clockwise servers for fault tolerance.

Server B dies → keys replicated to C and D still available.

7. Hot spots still possible

Viral key "celebrity:1" hashes to one vnode. Fix: Application-level sharding of hot keys, random suffix celebrity:1:0..7 spread across nodes.

8. Interview comparison