System Design Consistent Hashing
Consistent hashing is a technique that spreads data across many servers and keeps data movement small when servers join or leave. Distributed caches, databases, and content networks rely on it every day.
The Problem with Simple Hashing
A basic method picks a server with a formula: server number = hash(key) mod number of servers. The formula works well while the server count stays fixed.
Trouble starts when the count changes. Take the key with hash value 10.
3 servers : 10 mod 3 = 1 -> Server 1 4 servers : 10 mod 4 = 2 -> Server 2 (key moved!)
Adding a single server changes the answer for almost every key. A cache loses most of its stored data at once. Every request hits the database, and the database may collapse under the sudden load.
The Ring Idea
Consistent hashing replaces the formula with a circle. The circle holds hash values from 0 up to a very large number, and the end connects back to the start.
- Place each server on the ring at the position of its hash value.
- Place each key on the ring at the position of its hash value.
- Walk clockwise from the key. The first server met owns that key.
0
Server A
/ \
key K1 key K2
| |
Server D Server B
\ /
Server C
K1 walks clockwise -> reaches Server A
K2 walks clockwise -> reaches Server C
Layman example
Picture a round dinner table with four hosts seated around it. Each guest walks clockwise and joins the first host they reach. Guests always know whom to join without a master list.
Adding a Server
A new server lands on the ring between two existing servers. Only the keys between the new server and its counterclockwise neighbor move to the new server. Every other key stays put. With 4 servers growing to 5, only about one fifth of the keys move. Simple hashing would move nearly all of them.
Removing a Server
A server fails or leaves the ring. Its keys flow clockwise to the next server. All other keys remain untouched. Users barely notice the change.
The Uneven Load Problem
Servers placed by chance may cluster in one part of the ring. One server owns a huge arc and handles far more keys than others. A cluster of keys on one server creates a hot spot.
Virtual Nodes
Virtual nodes solve this problem. Each physical server appears at many ring positions under names such as A1, A2, A3, and A4. The many small arcs even out the load.
Ring order: A1 B1 C1 A2 B2 C2 A3 B3 C3 Each server owns several small arcs instead of one big arc.
Virtual nodes bring another gain. A powerful server can hold more virtual nodes than a weak server, so it carries a larger share of the work.
Where Systems Use It
- Distributed caches: cache clusters pick the server that stores each key.
- NoSQL databases: systems such as Cassandra and DynamoDB place data on ring positions.
- Content delivery networks: requests for one file reach the same edge server.
- Load balancers: sticky routing sends a user to the same backend.
Simple Hashing vs Consistent Hashing
| Feature | Mod Hashing | Consistent Hashing |
|---|---|---|
| Keys moved when a server joins | Almost all | About 1 divided by N |
| Handles server failure | Poorly | Smoothly |
| Setup effort | Very low | Moderate |
| Best for | Fixed small clusters | Growing distributed systems |
Key Takeaways
The ring limits damage when the cluster changes. Virtual nodes keep the load fair. Learners who master this idea understand how large systems scale without constant reshuffling.