Consistent Hashing
On this page
You run four cache servers and pick one for each key with hash(key) % 4. Traffic grows, so you add a fifth server and change the formula to % 5. Instantly, about 80% of keys map to a different server than before. The cache is effectively empty, the database takes the full read load at once, and the site slows to a crawl, all because you added capacity.
The problem is the formula, not the servers. You need a way to assign keys so that adding or removing a server moves only a small, fair share of keys. Consistent hashing does exactly that.
How it works
The ring

- Take a hash function with a large output range, say 0 to 2³²−1, and bend that range into a circle.
- Hash each server name (
cache-a,cache-b, …) to a point on the ring. - Hash each key to a point on the ring.
- A key belongs to the first server you meet going clockwise from it.
To find a server quickly, keep the server positions in a sorted array and binary-search for the first position ≥ hash(key), wrapping to the start if needed. That is O(log S) for S ring positions, microseconds.
Adding and removing servers
- Add server D: it lands between two existing servers. Only the keys in the arc just before D (which used to go to the next server) now go to D. Everything else stays.
- Remove server C: its keys move to the next server clockwise. Everything else stays.

With N servers, adding one moves about 1/(N+1) of the keys, the minimum possible if the new server is to take its fair share.
Virtual nodes
With only a few points on the ring, the arcs are uneven: one server might own 40% of the ring and another 10%. And when a server dies, all of its keys land on one neighbour, which may then overload too.
The fix is virtual nodes: place each physical server at many points (cache-a#1, cache-a#2, … up to, say, 150). Now:
- Each server owns many small arcs, so load is close to even.
- When a server dies, its many small arcs are picked up by many different servers.
- Bigger machines can get more virtual nodes, so capacity can be weighted.
Replication on the ring
Stores like Dynamo-style key-value databases replicate each key to the next R distinct physical servers clockwise. The first is the owner; the others hold copies. Walking the ring for replicas is natural and keeps placement deterministic: any node can compute where a key lives.
Trade-offs and costs
- Still some movement: 1/N of keys still move on every change, so a cache still loses that share of hits for a while, and a database still copies data.
- Need virtual nodes for balance; without them, load can be badly skewed.
- Hot keys are not solved: one very popular key still lives on one server (and its replicas). Handle it separately: replicate hot keys, add a local cache, or split the key.
- Membership must be agreed: every client or router needs the same view of the ring. A config service, a gossip protocol, or a central router keeps it consistent.
- Alternatives exist: rendezvous (highest random weight) hashing gives the same "minimal movement" property without a ring; jump consistent hash is compact for numbered buckets. Many systems use fixed virtual partitions instead (hash into 1,024 slots, move slots), which is simpler to reason about.
When to reach for it
- A cluster of cache servers where clients choose the server (memcached-style).
- Partitioning a distributed key-value store or database across nodes that come and go.
- Load balancing where the same key should keep hitting the same backend (session affinity, per-user state, sharded websockets).
- Any interview answer where you say "shard by hash" and the interviewer asks "what happens when you add a node?"
Example
A cache tier for product pages. Assumptions: 400 GB of hot data, 8 cache servers of 64 GB each, 200,000 reads per second, database can take 20,000 reads per second.
- Ring: each server gets 150 virtual nodes, 1,200 points in total. Clients hold the sorted ring and route each
product:{id}key locally. - Load: with 150 virtual nodes, each server's share stays within a few percent of 1/8, so about 25,000 reads per second each.
- Adding a ninth server: it takes about 1/9 of keys, about 11%. Those keys miss once, roughly 22,000 extra reads per second hitting the database briefly, which is at its limit. So the new server's virtual nodes are added in steps (50 at a time, a few minutes apart) to spread the misses.
- A server dies: its keys spread over the other seven, each taking about 1/7 more. Misses again hit the database briefly. With
% 8hashing, a failure would have remapped almost everything. - Hot product during a sale: consistent hashing alone puts it on one server, so the service also keeps a 5-second in-process cache for the top 100 products.
Common mistakes
- Using
hash % Nand not mentioning what happens when N changes. - Forgetting virtual nodes, then claiming the load is even.
- Thinking it fixes hot keys. It balances many keys, not one very hot key.
- Not saying how clients learn the ring (config service, gossip, or a router).
- Moving all the data at once when a node is added, instead of gradually.
Say this in the interview
"Keys are assigned with consistent hashing: servers and keys hash onto a ring and each key goes to the next server clockwise. Each server has about 150 virtual nodes so load is even and a failure spreads across everyone. Adding a node moves only about 1/N of keys, instead of nearly all of them with mod N. Clients get the ring from a config service. For the few very hot keys, I'll add a small local cache on top."
Used in
- Partitioning / Sharding Basics, Cache, Database.
- Design a Distributed Cache like Redis, Design a Distributed Key-Value Store, Design a Web Crawler.