In the previous article, you learned about rate limiting algorithms. Now let us solve a fundamental problem in distributed systems: how to distribute data across multiple servers.
Consistent hashing is the answer. It is used by Amazon DynamoDB, Apache Cassandra, Akamai CDN, and Discord. Once you understand it, you will see it everywhere.
The Problem: Distributing Data Across Servers
Imagine you have a cache with 4 servers. You need to decide which server stores which data. The simplest approach is modular hashing.
Simple Hash Approach:
server = hash(key) % number_of_servers
Example with 4 servers:
hash("user:1001") = 7823 --> 7823 % 4 = 3 --> Server 3
hash("user:1002") = 4512 --> 4512 % 4 = 0 --> Server 0
hash("user:1003") = 9341 --> 9341 % 4 = 1 --> Server 1
hash("user:1004") = 6128 --> 6128 % 4 = 0 --> Server 0
This works! Data is evenly distributed.
Why Simple Hashing Breaks
The problem happens when you add or remove a server.
Before: 4 servers
hash("user:1001") % 4 = 3 --> Server 3
hash("user:1002") % 4 = 0 --> Server 0
hash("user:1003") % 4 = 1 --> Server 1
After: 5 servers (added one)
hash("user:1001") % 5 = 3 --> Server 3 (same)
hash("user:1002") % 5 = 2 --> Server 2 (MOVED from Server 0!)
hash("user:1003") % 5 = 1 --> Server 1 (same)
After: 3 servers (one crashed)
hash("user:1001") % 3 = 1 --> Server 1 (MOVED from Server 3!)
hash("user:1002") % 3 = 0 --> Server 0 (same)
hash("user:1003") % 3 = 2 --> Server 2 (MOVED from Server 1!)
When the number of servers changes, almost every key maps to a different server. For a cache with millions of keys, this means almost all cached data becomes invalid. This is called a cache stampede — all requests hit the database at once because the cache is effectively empty.
Impact of Adding 1 Server:
4 servers -> 5 servers
Keys that move: ~80% (4 out of 5 keys on average)
4 servers -> 3 servers (one crashes)
Keys that move: ~75% (3 out of 4 keys on average)
With 100 million cached keys:
~75-80 million keys suddenly point to the wrong server.
--> Cache miss for all of them
--> Database overwhelmed
--> System goes down
We need a solution where adding or removing a server only moves a small fraction of the keys. That solution is consistent hashing.
How Consistent Hashing Works
The Hash Ring
Instead of using modular arithmetic, consistent hashing places both servers and keys on a circular ring (also called a hash ring).
Step 1: Create a hash ring (0 to 2^32 - 1)
Think of it as a clock with 4 billion positions.
0
|
270 -+- 90
|
180
Step 2: Place servers on the ring
Hash each server's identifier (like its IP address) to get a position on the ring.
hash("Server A") = 50
hash("Server B") = 130
hash("Server C") = 210
hash("Server D") = 310
0
| Server A (50)
|/
310 -+- 130
D | B
210
C
Step 3: Place keys on the ring
Hash each key to get its position on the ring.
hash("user:1001") = 75
hash("user:1002") = 160
hash("user:1003") = 240
Step 4: Assign keys to servers
Each key is assigned to the FIRST server found by going
CLOCKWISE from the key's position.
"user:1001" at 75 --> clockwise --> Server B at 130
"user:1002" at 160 --> clockwise --> Server C at 210
"user:1003" at 240 --> clockwise --> Server D at 310
What Happens When a Server Is Added
Add Server E at position 170:
Before:
"user:1002" at 160 --> Server C at 210
After:
"user:1002" at 160 --> Server E at 170 (closer clockwise)
Only keys between Server B (130) and Server E (170) move.
All other keys stay on their current servers.
Keys moved: only those in the small arc from 130 to 170.
That is roughly 1/N of all keys (where N is the number of servers).
What Happens When a Server Is Removed
Remove Server B at position 130:
Before:
"user:1001" at 75 --> Server B at 130
After:
"user:1001" at 75 --> Server C at 210 (next clockwise)
Only keys that were on Server B move to the next server.
All other keys stay where they are.
Keys moved: only Server B's keys (~1/N of all keys).
This is the key advantage. With simple hashing, adding a server moves about 80% of keys. With consistent hashing, adding a server moves only about 1/N of keys (where N is the number of servers). With 100 servers, only about 1% of keys move.
Comparison: Adding 1 Server
Simple hashing (4 -> 5 servers):
Keys moved: ~80%
With 100M keys: ~80M keys move
Consistent hashing (4 -> 5 servers):
Keys moved: ~20% (1/5)
With 100M keys: ~20M keys move
Consistent hashing (100 -> 101 servers):
Keys moved: ~1% (1/101)
With 100M keys: ~1M keys move
The Problem with Basic Consistent Hashing
Basic consistent hashing has one big issue: uneven distribution.
Uneven Distribution Problem:
With 3 servers placed randomly on the ring:
Server A at 10
Server B at 20
Server C at 350
Server A handles keys from 351 to 10 (arc: 20 degrees)
Server B handles keys from 11 to 20 (arc: 10 degrees)
Server C handles keys from 21 to 350 (arc: 330 degrees!)
Server C handles 92% of all keys!
Server A handles 5.5%
Server B handles 2.5%
This is terrible. One server is overloaded while others are idle.
When a server goes down, the next server clockwise inherits all of its keys. This can double the load on that server while others stay the same.
Virtual Nodes: The Solution
Virtual nodes (also called vnodes) solve the uneven distribution problem. Instead of placing each physical server at one position on the ring, you place it at many positions.
Without Virtual Nodes:
Server A: 1 position on the ring
Server B: 1 position on the ring
Server C: 1 position on the ring
With Virtual Nodes (150 per server):
Server A: positions A-0, A-1, A-2, ... A-149
Server B: positions B-0, B-1, B-2, ... B-149
Server C: positions C-0, C-1, C-2, ... C-149
Total: 450 positions on the ring (150 * 3 servers)
Each virtual node is placed on the ring by hashing the server name combined with a number:
Virtual Node Placement:
hash("Server-A-0") = 42
hash("Server-A-1") = 1823
hash("Server-A-2") = 3502
...
hash("Server-A-149") = 4012
hash("Server-B-0") = 512
hash("Server-B-1") = 2105
...
All virtual nodes for Server A map to the same physical server.
A key that lands on any of Server A's virtual nodes is stored on Server A.
With 150 virtual nodes per server, the data distribution becomes much more even. The standard deviation drops from over 50% to under 5%.
Distribution with Virtual Nodes:
3 servers, 150 virtual nodes each:
Server A: ~33.2% of keys
Server B: ~33.5% of keys
Server C: ~33.3% of keys
Much better than without virtual nodes!
When Server C goes down:
Server C's keys are distributed across Server A and Server B
based on which virtual node is next clockwise.
Load is shared evenly, not dumped on one server.
Choosing the Number of Virtual Nodes
More virtual nodes means better distribution but more memory to store the ring.
Virtual Nodes vs Distribution:
Nodes per server Standard deviation
10 ~25%
50 ~10%
100 ~7%
150 ~5%
200 ~3%
500 ~1.5%
Recommended: 100-200 virtual nodes per server.
This gives good balance between distribution and memory usage.
Consistent Hashing Implementation
Here is a simple consistent hashing implementation in Go:
package main
import (
"fmt"
"hash/crc32"
"sort"
"strconv"
"sync"
)
type ConsistentHash struct {
ring map[uint32]string // hash -> server name
sortedKeys []uint32 // sorted hash values
replicas int // virtual nodes per server
mu sync.RWMutex
}
func NewConsistentHash(replicas int) *ConsistentHash {
return &ConsistentHash{
ring: make(map[uint32]string),
replicas: replicas,
}
}
func (ch *ConsistentHash) hashKey(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
// AddServer adds a server with virtual nodes to the ring.
func (ch *ConsistentHash) AddServer(server string) {
ch.mu.Lock()
defer ch.mu.Unlock()
for i := 0; i < ch.replicas; i++ {
virtualKey := server + "-" + strconv.Itoa(i)
hash := ch.hashKey(virtualKey)
ch.ring[hash] = server
ch.sortedKeys = append(ch.sortedKeys, hash)
}
sort.Slice(ch.sortedKeys, func(i, j int) bool {
return ch.sortedKeys[i] < ch.sortedKeys[j]
})
}
// RemoveServer removes a server and all its virtual nodes.
func (ch *ConsistentHash) RemoveServer(server string) {
ch.mu.Lock()
defer ch.mu.Unlock()
for i := 0; i < ch.replicas; i++ {
virtualKey := server + "-" + strconv.Itoa(i)
hash := ch.hashKey(virtualKey)
delete(ch.ring, hash)
}
// Rebuild sorted keys
ch.sortedKeys = ch.sortedKeys[:0]
for hash := range ch.ring {
ch.sortedKeys = append(ch.sortedKeys, hash)
}
sort.Slice(ch.sortedKeys, func(i, j int) bool {
return ch.sortedKeys[i] < ch.sortedKeys[j]
})
}
// GetServer returns the server responsible for a given key.
func (ch *ConsistentHash) GetServer(key string) string {
ch.mu.RLock()
defer ch.mu.RUnlock()
if len(ch.sortedKeys) == 0 {
return ""
}
hash := ch.hashKey(key)
// Find the first server with a hash >= the key's hash
idx := sort.Search(len(ch.sortedKeys), func(i int) bool {
return ch.sortedKeys[i] >= hash
})
// Wrap around to the first server if we passed the end
if idx == len(ch.sortedKeys) {
idx = 0
}
return ch.ring[ch.sortedKeys[idx]]
}
func main() {
ch := NewConsistentHash(150)
ch.AddServer("cache-server-1")
ch.AddServer("cache-server-2")
ch.AddServer("cache-server-3")
// Check where some keys land
keys := []string{"user:1001", "user:1002", "user:1003", "order:5001"}
for _, key := range keys {
server := ch.GetServer(key)
fmt.Printf("Key: %-15s --> Server: %s\n", key, server)
}
// Add a new server -- only some keys will move
fmt.Println("\n--- Adding cache-server-4 ---")
ch.AddServer("cache-server-4")
for _, key := range keys {
server := ch.GetServer(key)
fmt.Printf("Key: %-15s --> Server: %s\n", key, server)
}
}
When you run this, you will see that adding a fourth server only moves a fraction of the keys. Most keys stay on the same server.
Real-World Usage
Amazon DynamoDB
DynamoDB uses consistent hashing to partition data across storage nodes. Each table’s partition key is hashed to determine which node stores the data. When the system detects a hot partition, it can split it and redistribute data with minimal disruption.
Apache Cassandra
Cassandra places each node on a hash ring. The partition key of each row is hashed to determine which node owns it. Cassandra uses virtual nodes (128-256 per node by default) to ensure even distribution. When you add a new node, it takes over a portion of the ring from existing nodes.
Akamai CDN
Akamai pioneered consistent hashing in production. They use it to determine which edge server caches which content. When an edge server goes down, its content is distributed across the remaining servers instead of all going to one server.
Discord
Discord uses consistent hashing to route users to the correct server for their guild (chat server). When they add new servers to handle growth, only a fraction of guilds need to be migrated.
Consistent Hashing vs Rendezvous Hashing
Rendezvous hashing (also called highest random weight hashing) is an alternative to consistent hashing. Instead of a ring, each key computes a weight for every server and picks the server with the highest weight.
Rendezvous Hashing:
Key: "user:1001"
Servers: A, B, C
weight(key, A) = hash("user:1001" + "A") = 8234
weight(key, B) = hash("user:1001" + "B") = 3412
weight(key, C) = hash("user:1001" + "C") = 9102
Highest weight: C --> "user:1001" goes to Server C
When Server C is removed:
Highest weight among A, B: A --> "user:1001" goes to Server A
Only keys that were on Server C move. Same benefit as consistent hashing.
When to use which:
| Feature | Consistent Hashing | Rendezvous Hashing |
|---|---|---|
| Lookup speed | O(log N) with sorted ring | O(N) — must check all servers |
| Memory | Higher (virtual nodes) | Lower (no ring needed) |
| Implementation | More complex | Simpler |
| Best for | Large clusters (100+ nodes) | Small clusters (< 20 nodes) |
For most production systems with many servers, consistent hashing with virtual nodes is the standard choice.
When to Use Consistent Hashing
Good use cases:
- Distributed caches (Redis cluster, Memcached) — route keys to the right cache server
- Database sharding — determine which shard stores a row
- Load balancing — route requests to servers with session affinity
- CDN routing — determine which edge server caches which content
- Distributed storage — decide which node stores a file chunk
When you do NOT need it:
- Single server setups — no distribution needed
- Small, fixed clusters — simple modular hashing works if servers never change
- Systems with a central coordinator — the coordinator can track assignments directly
Common Mistakes
Too few virtual nodes. Using 1-5 virtual nodes per server leads to very uneven distribution. Use at least 100-200.
Poor hash function. The hash function must distribute values uniformly across the ring. CRC32 or MD5 work well. Do not use a simple hash like
key.length().Forgetting about replication. Consistent hashing determines which server is the primary for a key. For fault tolerance, you also need to replicate data to the next N servers on the ring (where N is your replication factor).
Interview Tips
When discussing consistent hashing in interviews:
- Start with the problem. Explain why simple modular hashing breaks when servers change.
- Draw the ring. Sketch a circle with servers and keys placed on it. Show how keys find their server by going clockwise.
- Mention virtual nodes. This shows you understand the uneven distribution problem and its solution.
- Give real examples. “DynamoDB and Cassandra both use consistent hashing with virtual nodes.”
- Know the numbers. Adding a server moves about 1/N of the keys, compared to (N-1)/N with simple hashing.
Related Articles
- System Design #10: Rate Limiting — Protecting APIs from abuse
- System Design #5: Databases — SQL vs NoSQL, sharding, replication
- System Design #4: Caching — Redis, Memcached, CDN
What’s Next?
In the next article, System Design #12: Data Partitioning and Sharding, you will learn:
- Horizontal vs vertical partitioning
- Sharding strategies: range-based, hash-based, directory-based, geography-based
- How to choose a shard key
- How Instagram and Discord shard their databases
This is part 11 of the System Design Tutorial series. Follow along to learn system design from scratch.