Design Consistent Hashing

To spread keys over N cache or storage servers, the obvious approach is server = hash(key) % N. It distributes evenly as long as N never changes. But clusters change constantly: servers fail, and capacity is added. When N changes, the modulo result changes for most keys, so almost every key is looked up on the wrong server. For a cache this means a flood of misses that falls straight onto the database, exactly when the cluster is already stressed.

Consider a concrete check: going from 4 to 5 servers, a key stays put only if k % 4 == k % 5. Over keys 0 to 19, that holds for just 0, 1, 2 and 3, so only 20% stay and 80% move. In general, about N/(N+1) of keys relocate. The requirement is a scheme where a membership change moves only about 1/N of keys.

Take a cache tier with 1 billion keys spread across 100 servers, 10 million keys each. With modulo hashing, adding one server remaps roughly 100/101 of keys, about 990 million cache misses hitting the database almost at once. With consistent hashing, the new server takes about 1/101 of the keyspace, roughly 10 million keys, a 99x reduction in disruption.

Virtual nodes cost a little memory. With 100 servers and 200 virtual nodes each, the ring has 20,000 entries; at about 30 bytes per entry (a 20-byte hash plus a server reference) that is roughly 600 KB, trivially small to keep in every client. A lookup is a binary search over 20,000 sorted positions, about 15 comparisons.

Pick a hash function with a large output space. SHA-1 produces values from 0 to 2^160 - 1; join the two ends and the space becomes a ring. Hash each server (by IP or name) onto the ring, and hash each key onto the same ring. To find a key's server, start at the key's position and walk clockwise until you hit a server. In code, this is a sorted array of server positions and a binary search for the first position greater than or equal to the key's hash, wrapping to the start if none is found.

Because ownership depends only on the neighboring server, membership changes are local. When a server is added, it takes over only the keys between its predecessor and itself; everything else stays put. When a server is removed, only its keys move, to the next server clockwise.

With one point per server, partitions are uneven. Random placement can leave one server owning a huge arc and another a sliver, and the imbalance gets worse whenever a server leaves, because its neighbor inherits its entire arc and now owns double. Fair partition sizes cannot be guaranteed with so few points.

Second, even with equal arcs, key distribution can be skewed if keys cluster in one region of the ring, and heterogeneous hardware is not accounted for at all. A powerful new machine and an old one each get one arc. Both problems point to the same fix: give each server many points.

Each physical server is represented by many virtual nodes (also called replicas or tokens) scattered around the ring, for example by hashing server-A#0, server-A#1 and so on. A key maps to the first virtual node clockwise, and thus to that node's physical server. Each server now owns many small arcs, so by the law of large numbers its share of the ring converges on the average.

More virtual nodes mean a smaller standard deviation in load. Reported figures are roughly 10% of the mean with 100 virtual nodes per server and about 5% with 200. The trade-off is memory for the ring metadata and slightly slower rebalancing bookkeeping, which is usually negligible. Virtual nodes also handle heterogeneity: give a server twice the capacity twice as many virtual nodes. When a server leaves, its many small arcs are spread across many successors instead of dumping everything on one neighbor.

When membership changes, you must know which keys to move. If server S is added at some position, the affected keys lie on the arc from S counterclockwise back to the previous server; they used to belong to S's clockwise successor and now belong to S. If S is removed, the affected range is the same arc, and those keys must move to S's clockwise successor.

With virtual nodes this is done per virtual node, so a join triggers many small transfers from many peers, which also spreads the rebalancing load. In storage systems with replication, the replicas of those ranges must also be updated, which is why systems like Cassandra stream ranges in the background before the new node starts serving.

Consistent hashing minimizes movement and naturally removes the hotspot of one server suddenly owning twice its share. It does not solve hot keys: a single celebrity key still lands on one server, so caching or splitting such keys is a separate concern. Alternatives include rendezvous (highest random weight) hashing, which needs no ring and gives each key a deterministic server ranking, and jump consistent hash, which needs no memory but only supports numbered buckets added or removed at the end.

Real-world users include Amazon Dynamo and Apache Cassandra for data partitioning, Discord's chat backend, Akamai's CDN, and load balancers such as Maglev that use a related table-based scheme to keep connections on the same backend.