← All concepts
Scale & distribution
Consistent hashing
Map keys to servers on a hash ring so adding or removing a server moves only a small share of keys.
With plain hash mod N, changing N remaps almost every key — a disaster for caches and connection routing. Consistent hashing places servers and keys on the same ring; each key belongs to the next server clockwise, so a change only affects neighbours.
See it in action
Play with the idea, then follow it through a real architecture.
Try it: change the cluster
Keys (small dots) belong to the next server clockwise. Add or remove a server and see how few keys move.
0 of 16 keys moved (outlined dots).
Change the cluster to compare with plain hash mod N.
Laying out diagram…
1/2hash('user:42') lands just before node B on the ring, so B owns it.
- Client library
- — Hashes each key onto the ring
- Node A
- — Owns the arc before it
- Node B
- — Owns the arc before it
- Node C
- — Owns the arc before it
How it works
- Each server gets many virtual nodes on the ring to even out load.
- Used for cache clusters, wide-column databases, WebSocket session routing and rate-limit counters.
Trade-offs
- Still needs replication for availability; a lost node's keys must be rebuilt or read from replicas.
Seen in
- Twitter / XShort posts, follow graph and real-time home timelines
- WhatsApp / MessengerBillions of real-time messages per day
- API rate limiterFair-use limits checked on every request in under a millisecond
- Web crawlerFetch billions of pages politely and without repeats
- WebSockets at scaleMillions of live connections with Go on Kubernetes
- Redis ClusterDistributed in-memory data store