Consistent Hashing
A way of distributing data so that when servers are added or removed only a little data moves, not all of it.
14.1 Why is it used?
- With simple hash(key) % N, adding or removing one server changes the server of almost every key: the cache goes empty and the DB is flooded.
- With consistent hashing and N servers only about 1/N of the keys move.
- In auto-scaling clusters (cache, DB, CDN) nodes come and go often; this stays smooth.
- It helps spread the load evenly across nodes (with virtual nodes).
14.2 How it works
- Hash ring: treat the hash space (for example 0 to 2^32-1) as a circular ring.
- Hash each server and place it at a position on the ring.
- Hash each key and walk clockwise on the ring; the first server you meet owns the key.
- Adding a server: only the keys between it and the previous server move to the new server.
- Removing a server: its keys simply go to the next server, everything else stays the same.
- Virtual nodes (vnodes): place each physical server at 100-256 spots on the ring; the load is even, and a bigger server can be given more vnodes.
- Replication: also copy the key to the next 2-3 distinct servers (the preference list in Dynamo/Cassandra).
- Alternatives: Rendezvous (HRW) hashing, Jump consistent hash, Maglev hashing (Google load balancer).
- 1.4 cache servers, a key's server = hash % 4
- 2.A 5th server is added before the sale: now hash % 5
- 3.8 out of 10 keys change servers (~80%)
- 4.The cache is effectively empty -> all requests hit the DB -> site down
| Key hash | % 4 | % 5 | Moves? |
|---|---|---|---|
| 17 | S1 | S2 | Yes |
| 22 | S2 | S2 | No |
| 35 | S3 | S0 | Yes |
| 41 | S1 | S1 | No |
| 58 | S2 | S3 | Yes |
| 64 | S0 | S4 | Yes |
| 76 | S0 | S1 | Yes |
| 90 | S2 | S0 | Yes |
| 104 | S0 | S4 | Yes |
| 119 | S3 | S4 | Yes |
- 1.Ring 0 ... 2^32-1; servers A, B, C, D sit at different spots
- 2.Hash the key and walk clockwise: the first server found is the owner
- 3.New server E is added between A and B
- 4.Only the keys of the A-E arc moved from B to E, ~20% = 1/5
- 5.The remaining ~80% of keys stay safe in the cache
- 1.Without vnodes: 1 spot on the ring, some server owns a big arc -> uneven load
- 2.150 vnodes / server: each server is scattered at 150 spots on the ring
- 3.A new server takes a little load from every old server
- 4.A bigger server can be given more vnodes
Keys moved on adding a server: hash % N ~80%, consistent hashing ~20% (1/N). Used in: Cassandra Murmur3 token ring, DynamoDB, Redis/Memcached clients, Maglev LB
14.3 Tools
| Tool | Type | How it is used |
|---|---|---|
| Apache Cassandra | Wide-column DB | Murmur3 token ring, vnodes on every node (num_tokens), replication factor. |
| Amazon DynamoDB | Managed NoSQL | The original Dynamo paper (2007) popularised consistent hashing + vnodes; partitions are mapped by hash. |
| Memcached clients (ketama) | Client-side sharding | The client uses ketama consistent hashing to decide which cache server a key goes to. |
| Nginx / HAProxy | Load balancer | Sticky and cache-friendly routing with Nginx "hash $key consistent" and HAProxy "hash-type consistent". |
| Envoy (ring_hash, Maglev) | Proxy / service mesh | Ring hash and Maglev load balancing policies. |
| Akamai / CDNs | CDN | Consistent hashing originates in the 1997 paper by Akamai's founders: mapping content onto edge servers. |
14.4 Comparison: Modulo Hashing vs Consistent Hashing vs Rendezvous Hashing
| Point | hash % N | Consistent Hashing (ring + vnodes) | Rendezvous (HRW) |
|---|---|---|---|
| Keys moved on node add/remove | Almost all | Only ~1/N | Only ~1/N |
| Load balance | Good (for a fixed N) | Good with vnodes | Good |
| Lookup cost | O(1) | O(log N) binary search on the ring | O(N): a score for every node |
| Complexity | Very simple | Medium | Simple |
| Weighted nodes | Hard | Give more vnodes | Score with a weight |
| Used in | Simple fixed clusters | Cassandra, Dynamo, Memcached ketama, Nginx | Some CDNs, distributed caches, Kafka-like systems |
14.5 When to choose which
- hash % N: when the server count never changes and you want simplicity.
- Consistent hashing + vnodes: cache clusters, distributed DBs, auto-scaling; the default choice.
- Rendezvous hashing: when there are few nodes (10-50) and you want simple code.
- Maglev / Jump hash: for very high-throughput load balancers or when node IDs are sequential.
14.6 Real-world example
Scaling a cache cluster before a sale (an illustrative scenario)
- 4 Memcached/Redis servers, 10 crore keys, distributed with hash % 4.
- A 5th server was added before the sale: with hash % 5 about 80% of keys changed servers.
- Suddenly 80% cache misses, all requests on the DB: DB slow, site down. This is the problem.
- Switched to a consistent hashing ring, with 150 virtual nodes per server.
- Now when adding the 5th server only ~20% of keys move (1/5), the other 80% stay safe in the cache.
- Thanks to vnodes the new server took a little load from every old server: no single one is overloaded.
14.7 Interview tips
- A ring without virtual nodes is a mistake: some servers get far too many keys (uneven load).
- Thinking that consistent hashing solves the hot key problem is wrong: a single hot key still lands on one node.
- Interview tip: draw the ring diagram and explain the effect of add/remove and the 1/N movement.
- For replication, do not make two vnodes of the same physical server the replicas: pick distinct physical nodes.