Consistent Hashing

IPL Night. You Just Added 3 Cache Servers. 75% of Your Cache Just Vanished.

It's an IPL final night. Swiggy is seeing 5x normal order volume. Your team spins up 3 additional Redis cache servers to handle the load. Within seconds, your cache hit rate drops from 92% to 23%. The database is suddenly handling 4x more direct queries. Response times spike from 50ms to 1.2 seconds. Orders start timing out.

What happened? You were using hash(key) % num_servers to decide which cache server holds which data. When num_servers changed from 4 to 7, almost every key now maps to a different server. Your perfectly warm cache? Ice cold.

You just learned, the hard way, why consistent hashing exists.

Why Should You Care?

1. Every distributed cache, CDN, and database uses it. Redis Cluster, Memcached, Cassandra, DynamoDB, Akamai: all of them use consistent hashing or a close variant.
2. It solves the rehashing catastrophe. When you add or remove servers, consistent hashing moves only K/N keys (where K is total keys and N is total servers), not nearly all of them.
3. It's a top interview question. "How does your cache cluster handle adding/removing nodes?" If you don't say consistent hashing, the interviewer knows you've never operated a distributed cache.

🟢 The Simple Version

The Problem with Naive Hashing

Suppose you have 4 cache servers. The simplest approach:

server_index = hash(key) % 4

Key "user:42" hashes to 2,394,751. 2394751 % 4 = 3 → goes to Server 3. Key "order:99" hashes to 1,087,202. 1087202 % 4 = 2 → goes to Server 2.

Works beautifully. Until you add a 5th server.

Now 2394751 % 5 = 1 → "user:42" should be on Server 1, but the data is on Server 3. Cache miss. Same story for most other keys. With modular hashing, changing the number of servers remaps approximately (N-1)/N of all keys, roughly 75% when going from 4 to 5 servers.

For a cache with 10 million keys, that means 7.5 million sudden cache misses. All those requests slam the database simultaneously. This is called a cache stampede, and it can take down your entire system.

Watch the disaster play out. Adding ONE server remaps 6 of 8 keys (the red ones):

The Ring Idea

Consistent hashing uses a different mental model. Instead of a numbered array of slots, imagine a circular ring, like a clock face, but with positions from 0 to 2^32.

1. Hash each server onto the ring. Server A might land at position 10,000, Server B at 750,000, Server C at 2,100,000.
2. Hash each key onto the same ring. Key "user:42" might land at position 800,000.
3. Walk clockwise from the key's position until you hit a server. The first server you reach owns that key.

So "user:42" at position 800,000 walks clockwise and hits Server C at position 2,100,000.

What Happens When You Add a Server?

Here's the magic. You add Server D to the ring, and it lands between Server A and Server B. Only the keys in that arc (between A and D) need to move. They used to walk clockwise to B; now they walk clockwise to D instead.

Every other key stays exactly where it is. Instead of remapping 75% of keys, you remap roughly 1/N of them (where N is the number of servers). With 4 servers, that's ~25%. With 100 servers, it's ~1%.

Similarly, if Server C dies, only its keys need to move. They just walk clockwise to the next server on the ring.

Here is that exact failure, animated. Node B dies, and only K1 (the key in B's arc) slides clockwise to Node C. K2, K3 and K4 don't move. That is the whole trick:

This is the fundamental property: when the number of servers changes, only a minimal fraction of keys are remapped.

🟡 Going Deeper: Virtual Nodes

The basic ring has a problem. With only 3-4 servers, they're unlikely to be evenly spaced on the ring. One server might own 60% of the key space while another owns 10%. This means uneven load distribution.

The fix: virtual nodes (vnodes). Instead of placing each server once on the ring, you place it at many positions, say 100 or 200 per server. Each position is a "virtual node" that maps back to the same physical server.

Why Virtual Nodes Work

With 150 virtual nodes per server and 5 physical servers, you have 750 points on the ring. By the law of large numbers, each server ends up owning very close to 1/5 (20%) of the ring, within a few percentage points.

More benefits:

• Heterogeneous hardware. Give a beefy 64GB server 200 vnodes, and a smaller 16GB server 50 vnodes. Proportional load distribution without complex routing rules.
• Smoother rebalancing. When a server is added, its 150 vnodes are scattered across the ring, so data is pulled from many existing servers, not just one.

Cassandra uses 256 virtual nodes per server by default. Redis Cluster uses a fixed 16,384 hash slots (similar concept, slightly different implementation).

🟡 Consistent Hashing vs Naive Hashing: Side by Side

Let's quantify the difference with real numbers.

The lookup for consistent hashing is a binary search on a sorted array of ring positions to find the next server clockwise. With 1000 vnodes, that's about 10 comparisons. Negligible.

🟡 Real-World Implementations

How Memcached Clients Use Consistent Hashing

Memcached itself doesn't know about consistent hashing. It's just a key-value server. The client library (like libmemcached or pylibmc) implements consistent hashing to decide which Memcached server to talk to.

# Conceptual flow (not actual code)
ring = build_ring(["mc1:11211", "mc2:11211", "mc3:11211"])

def get(key):
   server = ring.find_server(hash(key))  # clockwise lookup
   return server.get(key)

def set(key, value):
   server = ring.find_server(hash(key))
   server.set(key, value)

This means the client needs to know the full server list. When you add a server, you update the client configuration, and the ring is rebuilt.

How Redis Cluster Uses Hash Slots

Redis Cluster takes a different approach. Instead of a continuous ring, it divides the key space into 16,384 hash slots. Each key maps to a slot via CRC16(key) % 16384. Each Redis node owns a subset of slots.

When you add a node, you manually (or automatically) migrate some slots from existing nodes to the new one. This is conceptually similar to consistent hashing, but with a fixed, discrete number of positions instead of a continuous ring.

How Cassandra Uses Consistent Hashing

Cassandra uses a consistent hash ring as its core data distribution mechanism. Each node has a token (its position on the ring). The partition key of every row is hashed, and the row lives on the node that owns that token range.

By default, Cassandra assigns 256 virtual nodes per server using num_tokens: 256 in cassandra.yaml. When a node joins or leaves, Cassandra automatically streams data to rebalance the ring.

🔴 Architect's Corner

Jump Consistent Hashing

Google published Jump Consistent Hash (2014), a simpler algorithm that achieves perfect distribution with zero memory overhead. It uses a clever pseudorandom number generator to map keys to buckets:

int JumpConsistentHash(uint64 key, int num_buckets) {
   int64 b = -1, j = 0;
   while (j < num_buckets) {
       b = j;
       key = key * 2862933555777941757ULL + 1;
       j = (int64)((b + 1) * (double(1LL << 31) / double((key >> 33) + 1)));
   }
   return b;
}

It's brilliant for stateless lookups (no ring to maintain), but it only works when servers are numbered 0 to N-1 and you only add/remove from the end. Not suitable for arbitrary node failures, which limits its use to controlled environments.

Rendezvous Hashing (Highest Random Weight)

An alternative to ring-based consistent hashing. For each key, compute hash(key, server) for every server. The server with the highest hash value wins.

• Pros: No ring. No vnodes. Perfect distribution. Simple to implement.
• Cons: O(N) per lookup (must compute hash for every server). Fine for small N, impractical for thousands of servers.

Used by some CDNs and content routing systems where the number of servers is manageable.

Bounded Load Consistent Hashing (Google, 2017)

Standard consistent hashing can still create hot spots. If a key is extremely popular (a viral video, a trending hashtag), the server that owns it gets hammered regardless of ring distribution.

Google's bounded load variant adds a constraint: no server can hold more than (1 + ε) × average_load. When a server is "full," the key walks further clockwise to the next server with capacity. This provides a worst-case load guarantee while maintaining minimal remapping.

Vimeo's HAProxy implementation uses this for video CDN routing.

Indian Tech Context

Hotstar During IPL

Hotstar (now JioCinema) serves 50+ million concurrent viewers during IPL matches. Their CDN and caching layer must handle:

• Millions of requests per second for the same video segments
• Adding/removing edge cache servers without disrupting streams
• Uneven popularity (final match > league match)

Consistent hashing ensures that when they add edge servers during peak load, only ~1/N of the cached segments need to be re-fetched from origin, keeping the CDN warm.

Flipkart's Search Index

Flipkart's product search likely distributes its search index across multiple servers using consistent hashing (or hash slots). Each server holds a portion of the product catalog. When a new server is added during a Big Billion Days sale, only a fraction of the index needs to be rebalanced.

Common Mistakes

1. Using modular hashing in production. hash(key) % N works in development with a fixed number of servers. In production, where servers are added, removed, and fail, it creates cache stampedes.

2. Forgetting virtual nodes. Basic consistent hashing with 3-5 servers leads to highly uneven load. Always use virtual nodes (100-200 per server) in production.

3. Using MD5 or SHA for the hash function. Cryptographic hashes are slow. Use a fast non-cryptographic hash like MurmurHash3 or xxHash. You need distribution quality, not collision resistance.

4. Not handling server failure gracefully. When a server on the ring dies, its keys automatically map to the next server clockwise. But that server now handles its own load PLUS the dead server's load, potentially 2x its normal capacity. Monitor for this and have capacity margins.

5. Ignoring hot keys. Consistent hashing distributes keys evenly, but if one key receives 50% of all traffic, no hash ring saves you. You need application-level caching or key replication for hot keys.

🧠 Key Takeaways

• Naive modular hashing remaps almost all keys when the number of servers changes. Catastrophic for caches.
• Consistent hashing uses a ring: add/remove a server, and only ~1/N keys need to move.
• Virtual nodes solve uneven distribution by placing each server at many positions on the ring.
• Every major distributed system uses some variant: Redis Cluster (hash slots), Cassandra (token ring), Memcached clients (ring-based), CDNs (for content routing).
• Alternatives exist: jump consistent hash (stateless, Google), rendezvous hashing (O(N) lookup), bounded load (caps hot spots).
• Always use a fast hash function (MurmurHash3, xxHash), not a cryptographic one.

Think About It

1. You're building a distributed cache for a food delivery app. During Diwali sales, you need to scale from 10 to 15 cache servers. With consistent hashing, roughly what percentage of keys need to be remapped? What happens to cache hit rate during the transition?

2. Your consistent hash ring has 3 servers with 100 virtual nodes each. One server dies. What happens to the remaining two servers' load? How would you prepare for this scenario?

3. A single product page on your e-commerce site is going viral, getting 100,000 requests per second for the same cache key. How does consistent hashing help (or not) with this? What additional strategies would you use?

Further Reading

• Consistent Hashing and Random Trees (Karger et al., 1997): The original paper that introduced consistent hashing
• Jump Consistent Hash (Lamping & Veach, 2014): Google's simpler, zero-memory consistent hash
• Consistent Hashing with Bounded Loads (Mirrokni et al., 2017): Google's improvement for handling hot spots
• Redis Cluster Specification: How Redis implements hash-slot-based distribution