LESSON 15.2
Consistent hashing
Hash rings, virtual nodes, and a worked example of how adding capacity changes ownership without remapping almost every key.
6 min read
Hashing distributes keys, but the placement rule matters when machines change. With hash(key) % server_count, adding one server changes the divisor and remaps many keys. A cache suddenly misses for moved keys; a durable store must physically transfer them. Consistent hashing limits changes to the ranges whose ownership actually changes.
Walk clockwise around the ring
Treat the hash space as a circle. Hash each server token to a point and hash each key into the same space. A key belongs to the first token encountered clockwise, wrapping around at the end. Each token therefore owns the interval after the preceding token through itself.
For a tiny ring numbered 0–99, place A at 24, B at 49, C at 74 and D at 99. A owns 0–24, B owns 25–49, C owns 50–74 and D owns 75–99. Key hash 32 goes to B; hash 80 goes to D.
Add E at 39. It takes hashes 25–39 from B; hashes 40–49 stay on B, and every other interval stays where it was. That moves 15% in this deliberately small example. A random single token can own a much larger or smaller interval, so this isn't a guarantee of balance.
How much data moves?
For equal-capacity servers with well-balanced ownership and roughly uniform data, adding one node to N existing nodes transfers approximately 1 / (N + 1) of primary data to the newcomer. It doesn't move that fraction from every node independently; that's the total share the new node needs.
- Before adding a node
- 250 GB per node
- After adding a fifth
- 200 GB per node
- New node's share
- 200 GB = 20% of the total
- Existing nodes give upWith many well-distributed tokens
- About 50 GB each
- Ideal copy time at 100 MB / sBefore live writes, replication and throttling
- About 2,000 s, or 33 minutes
This estimates primary ownership changes, not all network traffic. Replica placement, retries and maintaining live writes add work. Removing a node redistributes its old ranges, about 1/N of the primary data if ownership was balanced.
Virtual nodes
Instead of giving each physical server one token, give it many, perhaps 128 as an example. Each virtual node is an ownership position, not another process. A physical machine owns the union of its small intervals.
One token per machine
- Small placement map
- Easy to draw
- Randomly uneven ownership
- Large transfers between a few neighbors
Pick it when: Explaining the basic ring, or deliberately managed small layouts.
Many virtual nodes
- Smoother ownership
- Transfers spread across peers
- Can weight larger machines with more tokens
- More routing metadata
- More ranges to manage
Pick it when: A ring serving machines with changing capacity.
For replicas, walk to distinct physical machines and failure domains, not just the next few tokens. Several neighboring tokens may belong to the same machine; counting those as separate replicas provides no protection from its failure.
What the ring doesn't solve
Consistent hashing is a placement rule. It doesn't copy data, agree on membership or prevent two routers using different ring versions. A membership service publishes versioned maps; a migration protocol transfers ranges and handles requests using stale maps.
It also doesn't divide one hot key. Virtual nodes balance many keys statistically; a viral object's requests still converge on its owner unless replication or another application-level strategy spreads them.
Try it
Distributed Cache HLD
Place cache keys so adding a node moves a bounded share rather than flushing most of the cache.