Consistent hashing: the algorithm behind distributed databases

When distributing millions of cache keys across N backend servers, the simplest approach is modulo hashing:

server_index = hash(key) % N

While simple, modulo hashing fails catastrophically when your cluster scales.

The Failure of Naive Modulo Hashing

Suppose you have 4 cache servers (N = 4) holding 1,000,000 keys.

During peak traffic, you add a 5th server (N = 5) to relieve memory pressure.

Because the modulo denominator changes from 4 to 5, nearly 80% of all keys compute to a completely different server index:

Key        hash(key)    hash % 4 (Old)    hash % 5 (New)    Status
-------------------------------------------------------------------
"user:101" 1482931238   Server 2          Server 3          ❌ Cache Miss
"user:102" 8492019482   Server 2          Server 2          ✅ Cache Hit
"user:103" 3920184719   Server 3          Server 4          ❌ Cache Miss
"user:104" 9182371920   Server 0          Server 0          ✅ Cache Hit
"user:105" 5819203817   Server 1          Server 2          ❌ Cache Miss

This creates an immediate cluster-wide cache stampede: millions of concurrent queries miss cache and strike your primary database simultaneously, knocking it offline.

The Solution: The Consistent Hash Ring

Consistent Hashing bounds key relocation so that adding or removing a node only moves a tiny fraction (K / N) of keys.

                         [Node 1] (pos: 0)
                            ▲
                          /   \
           Key "user:9"  /     \  Key "user:1"
                        │   ⭕  │
           [Node 3] ────┤       ├──── [Node 2] (pos: 120°)
          (pos: 240°)   │       │
                         \     /  Key "user:4"
                          \   /
                            ▼

1. The Circular Identifier Space

Both servers and keys are mapped to the exact same continuous circular range (typically [0, 2^32 - 1] using MD5 or MurmurHash).

2. Clockwise Routing

To find which server owns key K:

Compute hash(K) to find its position on the ring.
Travel clockwise along the ring until you encounter the first server node. That node owns the key.

3. Scaling Without Stampedes

When a new node (Node 4) joins the ring between Node 1 and Node 2:

Only keys located between Node 1 and Node 4 are remapped to Node 4.
Keys mapped to Node 2 and Node 3 remain 100% untouched and valid in cache.
On average, only K / N keys move (e.g. 20% instead of 80% when going from 4 to 5 servers).

Hotspots & Virtual Nodes (vnodes)

In a basic hash ring with a small number of physical nodes (e.g. 3 servers), hash distribution can be statistically uneven, leading to hot spots where one server receives 60% of total traffic.

To ensure uniform load distribution, systems assign each physical server hundreds of Virtual Nodes (vnodes) across the ring:

Physical Server A  ───>  vnodes: A-1 (pos 12°), A-2 (pos 145°), A-3 (pos 290°)
Physical Server B  ───>  vnodes: B-1 (pos 48°), B-2 (pos 190°), B-3 (pos 330°)

Uniform Distribution: Standard deviation drops significantly, balancing memory and bandwidth across the cluster.
Weighted Capacity: A server with 64GB RAM can be assigned 200 vnodes, while a 16GB server gets 50 vnodes.

Real-World Production Usage

Consistent Hashing is the foundational data routing algorithm behind:

Amazon DynamoDB & Apache Cassandra: Distributing partition keys and replica sets across cluster rings.
Discord: Routing voice channel connections across distributed media servers.
Akamai & Cloudflare CDNs: Maximizing edge cache hit rates during origin server scaling.
Memcached / Twemproxy: Client-side sharding of distributed memory caches.