Consistent Hashing: Beyond the Basics for Distributed Systems

The Challenge of Naive Hashing in Distributed Systems

Distributing keys across a cluster using simple `hash(key) % N` is straightforward initially. However, this approach becomes problematic in dynamic environments where servers are frequently added or removed. When `N` (the number of servers) changes, almost all keys remap to new servers. This can lead to a massive cache stampede, where a significant portion of cached data becomes invalid, overwhelming the underlying database with requests that the cache was intended to absorb.

Consistent Hashing with a Hash Ring

Consistent hashing addresses the remapping problem by mapping both servers and keys onto a conceptual "hash ring" (a circular hash space, typically 0 to 2 ³²−1). Each key is assigned to the first server encountered by walking clockwise from the key's position on the ring. This design significantly reduces key remapping:

• Adding a server: Only keys between the new server and its clockwise predecessor are remapped.
• Removing a server: Only keys owned by the removed server are shifted to the next server clockwise.

Roughly `K/N` keys (where K is total keys, N is total servers) move per server change, a substantial improvement over the entire dataset remapping.

Mitigating Uneven Load with Virtual Nodes

While a hash ring reduces remapping, a small number of physical servers can still result in uneven distribution of keys (data imbalance) due to random placement on the ring. Virtual nodes solve this by mapping each physical server to multiple (e.g., 100-200) distinct points on the hash ring. This increases the number of server positions, allowing the law of large numbers to distribute keys more evenly, typically resulting in less than 5% load variance between machines.

Addressing Hot Keys and Traffic Imbalance

Even with perfect data balance from virtual nodes, a single "hot key" (e.g., a viral celebrity profile) can direct all its traffic to one server, creating a traffic imbalance. This server becomes a bottleneck despite holding an average number of keys. Common mitigations include:

• Read Replicas: Replicate the hot key's data across multiple servers and use a load balancer to distribute read requests among these copies.
• Key Salting: Append a random suffix (e.g., `key-0`, `key-1`...`key-9`) to the hot key. This spreads its reads across multiple positions on the hash ring, effectively sharding the hot key's traffic. Reads would then require aggregating results from these salted keys.