Consistent Hashing

Consistent Hashing distributes keys (cache entries, data records, requests) across a set of nodes in a way that stays stable as the node set changes. Naive hashing with hash(key) % N remaps almost every key when N changes, causing massive cache misses or data movement. Consistent hashing limits the disruption: adding or removing one node remaps only about 1/N of keys.

How It Works

Nodes and keys are both hashed onto the same circular space, a hash ring. A key is assigned to the first node found by moving clockwise from the key's position. When a node is removed, only the keys it owned move, to the next node on the ring; when a node is added, it takes over only the keys between it and its predecessor. Other keys stay put.

To balance load, each physical node is placed at many positions using virtual nodes, smoothing out uneven distribution. This technique underlies systems such as memcached client sharding, Cassandra, DynamoDB, and many distributed caches and load balancers.

The number of virtual nodes per physical node trades memory for balance: more virtual nodes smooth the distribution but enlarge the ring. Some systems extend the basic ring with bounded loads, capping how much any node may hold and spilling overflow to the next node, which prevents a single node from being overwhelmed by a skewed key distribution.

When to Use It

Use consistent hashing when you partition data or load across nodes that scale up and down, especially distributed caches and key-value stores, and when minimizing remapping during scaling or failure is important. It gives each key a deterministic owner without a central coordinator.

For a fixed, rarely changing node set, simple modulo hashing may be adequate.

It is also a natural fit for sticky routing, sending requests for the same session or entity consistently to the same instance to maximize local cache hits.

Trade-offs

Consistent hashing greatly reduces remapping but is more complex than modulo hashing and can distribute load unevenly unless virtual nodes are used. It assigns keys by hash, so range queries are not supported directly. Hotspots can still occur for popular keys. The major benefit is graceful scaling with minimal data movement. When a few keys are extremely popular, consistent hashing alone will not save a hotspot, so it is often combined with replication of hot keys or request coalescing to spread that concentrated load.

Related Patterns

Consistent Hashing is a strategy for Sharding that minimizes resharding cost. It provides single-owner key assignment without a Distributed Lock or Leader Election. Scatter-Gather often queries across the resulting partitions. Rendezvous hashing is a related alternative that achieves similar minimal remapping with a different selection rule.

Example

A distributed cache runs on five nodes. Using consistent hashing with 150 virtual nodes each, keys spread evenly across the ring. When a sixth node is added for capacity, only roughly one-sixth of keys move to it; the rest keep hitting their existing nodes, so the cache hit rate stays high during scaling instead of collapsing as it would with modulo hashing.