Consistent Hashing Algorithms

In distributed caching (Memcached, Redis Cluster) and distributed storage engines (Amazon DynamoDB, Apache Cassandra, Discord Guild Router), nodes are continuously added or removed due to auto-scaling, hardware failures, and routine rolling deployments.

If keys are mapped using naive modulo arithmetic ($hash(key)(\mathrm{mod}N)$), adding or removing a single server invalidates almost every key in the entire cluster, triggering catastrophic database overload.

Consistent Hashing (Karger et al., MIT 1997) solves this fundamental scaling problem.

1. The Naive Modulo Disaster

Suppose you have $N=4$ cache servers, and route keys using:

$\text{Server}=\text{hash}(\text{key})(\mathrm{mod}N)$

If Server 4 crashes, $N$ changes from 4 to 3:

The Math of Modulo Invalidation:

When $N$ changes to $N+1$ or $N-1$:

$\text{Fraction of Invalidated Keys}=\frac{N-1}{N}$

In a 100-node cluster, adding 1 node invalidates 99% of all cached keys simultaneously, causing a massive Cache Stampede that immediately melts downstream databases!

2. The Consistent Hash Ring Concept

Consistent Hashing treats the 32-bit hash output space ($[0\dots 2^{32}-1]$) as a continuous circular ring (a Hash Ring):

1. Map Nodes to the Ring: Hash each server's identifier (IP or hostname) to place it at a specific coordinate on the ring: $\text{Pos}(\text{Node A})=\text{hash}("192.168.1.10")$
2. Map Keys to the Ring: Hash each data key to place it on the ring: $\text{Pos}(\text{Key})=\text{hash}("user:42")$
3. Clockwise Lookup Rule: To find which node stores a key, find the key's position on the ring and walk clockwise until you encounter the first server node.

3. Minimal Key Redistribution ($K/N$ Invariant)

What happens when a node is added or removed in Consistent Hashing?

Suppose Node D is added between Node A and Node B:

• Only the keys that fall between Node A and Node D are reassigned to Node D.
• All other keys on the ring remain completely undisturbed on their existing servers!

$\text{Keys Rebalanced}=\frac{K}{N}$

Where $K$ is the total number of keys and $N$ is the number of nodes.

4. Virtual Nodes (VNodes): Eliminating Non-Uniform Hotspots

A basic consistent hash ring has two critical real-world flaws:

1. Non-Uniform Key Distribution: With only 3 or 4 physical nodes, the distances between nodes on the ring are uneven, resulting in one node handling 60% of traffic while another handles 10%.
2. Cascading Failure: If Node B dies, 100% of Node B's load instantly dumps onto its immediate clockwise neighbor (Node C), causing Node C to crash from overload and triggering a cascading failure across the entire cluster.

The Solution: Virtual Nodes (VNodes)

Instead of placing each physical server on the ring once, assign each physical server $V$ Virtual Nodes (e.g. $V=100-250$):

Benefits of VNodes:

• Statistically Perfect Load Balancing: Standard deviation of key distribution drops below $2\%$.
• Even Failure Distribution: If physical Node 1 fails, its 150 vnodes are distributed all around the ring, spreading the orphaned load equally across all surviving nodes.
• Hardware Heterogeneity: Powerful servers can be assigned 300 vnodes while smaller servers receive 75 vnodes.

5. Code Deep-Dive: Complete Consistent Hash Ring Implementation

6. Production Failure Postmortem: The Un-Ringed Cache Resizing Meltdown

Incident Overview:

In 2020, a major streaming video platform added 4 new nodes to an overloaded 16-node Memcached cluster to alleviate peak traffic pressure. Instead of reducing load, the database tier crashed within 30 seconds.

What Happened:

1. The caching client library was configured with naive modulo routing: shard = hash(video_id) % num_nodes.
2. When the node count changed from 16 to 20, $80\%$ of all cache keys re-mapped to different servers.
3. Over 400,000 requests/sec missed the cache simultaneously and hit the primary Aurora PostgreSQL database cluster.
4. The database CPU spiked to 100%, query latency exceeded connection timeouts, and the entire video streaming API crashed globally.

Remediation:

• Migrated all client drivers to Ketama Consistent Hashing with 160 VNodes per server.
• Added dynamic warm-up backfills to pre-populate newly joined nodes before routing production traffic.

7. Landmark Capstone #6: Build a Consistent Hash Ring with Virtual Nodes ⚔️

Put your distributed hashing skills to the test by implementing a complete Consistent Hash Ring with Virtual Nodes:

👉 Launch Capstone: Build a Consistent Hash Ring Engine

• Supported Languages: TypeScript & Python 3
• Challenge Focus:
  • Implement 32-bit integer hash mapping.
  • Distribute physical nodes across configurable virtual node counts.
  • Implement logarithmic binary search lookups with circular ring wraparound.
  • Dynamically add/remove nodes and verify minimal key rebalancing ($K/N$).

8. Chapter Summary & Consistent Hashing Rules