Consistent hashing
A way to assign keys to servers so that adding or removing one server moves about 1/N of the keys instead of nearly all of them. It is how caches, partitioned stores and sticky routing survive a changing fleet.
What it is
Consistent hashing is a way of mapping keys to a changing set of servers. With an ordinary hash table you take hash(key) % N, and when N changes almost all keys land somewhere new, because the mapping depends on the modulus. With consistent hashing, a resize moves about K/N of the K keys on average, where N is the number of servers, and the rest stay put. The term comes from a 1997 paper by David Karger and colleagues at MIT, written for distributed web caching; two of its authors founded Akamai in 1998, whose content delivery network uses the technique to balance load inside a cluster of servers.
How the ring works. Both servers and keys are hashed onto the same circle, often described as positions from 0 to 1 or as tokens in a fixed integer range. A key is owned by the first server you meet walking clockwise from the key's position, so each server owns the arc between its predecessor and itself. Lookups keep the server positions sorted and binary-search them, which costs O(log N) per key. When a server is removed, the keys on its arc pass to the next server clockwise and nothing else changes. When a server is added, it takes over the part of its successor's arc that now sits before it.
Virtual nodes. One position per server has two weaknesses: random positions give uneven arcs, and with a small fleet there is no spot for a new server that keeps the ring balanced. Cassandra 5.0's documentation gives the example of eight evenly spaced tokens, where a ninth token has nowhere to go without imbalance, and says that uneven ranges turn into uneven request load. The fix, which it attributes to the Dynamo paper, is to give each physical node several tokens (vnodes), so a small cluster behaves like a large one: a joining node takes small slices from many neighbors, a leaving node hands small slices to many neighbors, and a failed node's reads spread over many others. The cost is more neighbors per node, which means more combinations of failures that lose part of the ring, and slower cluster-wide work such as repair. In version 2.x tokens were picked at random, so the default was 256 per node to stay balanced; 3.x added a deterministic allocator that balances the ring with far fewer tokens.
Weights and proxies. A load balancer can use the same ring to send requests with the same hash key to the same backend. Envoy's ring hash balancer, as its current documentation describes it, places each host on the ring a number of times proportional to its weight, and notes that a handful of entries is not enough: two hashes can land close together, so it inserts hundreds of entries per host to approximate the intended split. With a well-sized ring, adding or removing one of N hosts affects about 1/N of requests. Maglev, offered there as a drop-in alternative, is a fixed lookup table of 65537 entries that is roughly 10x faster to build and 5x faster to query than a 256K-entry ring, at the price of about twice as many keys moving when a host is removed.
When to use it
Partitioned stores and caches whose members change. This is the original use: a pool of cache servers where machines fail and are replaced, and a full reshuffle would turn into a wall of misses. Systems that partition data this way include Amazon's Dynamo, Cassandra, ScyllaDB, Riak, Couchbase and OpenStack Swift, and Discord uses it in its chat infrastructure. A content delivery network such as Akamai uses it to spread requests across a rotating population of servers.
Sticky routing to stateful servers. When a backend holds per-key state in memory (an open connection, a warm cache, a session), a proxy can hash a request property and route to the owning host, so the state is reused instead of rebuilt. This works when the protocol gives the proxy a value to hash on; Envoy, for example, lets you hash hosts by hostname or by a metadata key instead of their address, which ties a host's ring position to a stable name rather than to an address. Routing messages between stateful servers covers what to do once you know which server owns a key.
Our test for reaching for it: the set of servers changes more often by failure than by plan, you want any node or client to compute an owner locally without asking a directory, and the data behind a key is expensive enough to rebuild that moving most of it at once would hurt. If all three hold, a ring with virtual nodes is a good default.
When not to
Stateless workers behind a load balancer. If nothing is kept per key on the server, there is nothing to keep stable, and a hash can send a burst of one key to one host. Envoy ships weighted round robin, least request and random balancers alongside the hash-based ones; for a stateless fleet one of those spreads load better and needs no hash key.
When you want to move data on purpose. A fixed slot table is a directory, not a ring: it says which node owns each slot and lets operators move chosen slots between nodes. Redis Cluster's specification splits the key space into 16384 slots, each master owning a subset, and a node change means moving chosen slots rather than whatever the hash decides. The price is a table of slot owners that the nodes keep in sync, which clients either cache or learn through redirections, and a cluster size bounded by the slot count.
A few servers and simple code. Rendezvous hashing, designed by Thaler and Ravishankar in 1996, skips the ring: for each key you score each server with hash(key, server) and pick the highest score. Adding or removing a server still moves about 1/N of the keys, there is no sorted structure to maintain, and in its basic form each server gets an equal share. Each lookup scores all N servers, which is fine for a few dozen servers and wasteful for thousands.
Hot keys and range reads. The ring spreads keys, not the load behind one key: a celebrity's conversation hashes to one owner and stays there. Splitting or replicating that key is a separate problem, covered in Hot keys and hot partitions. Hashing also scatters neighboring keys, so a store that needs range scans by time or by prefix is usually better served by range partitioning. And if clients connect to whatever server a balancer picked, a hash tells you where a key should live, not where it is; a registry of who is connected where is then the honest answer.
Compared
| Approach | How a key finds its node | What moves on a node change | Pick it when |
|---|---|---|---|
Hash mod N |
| Nearly all keys | N is fixed, or the data is cheap to rebuild (stateless workers, a cache you can refill) |
Ring with virtual nodes | Hash to a circle, binary-search the sorted positions, take the next one clockwise | About K/N keys, taken from or given to many neighbors | Nodes join and leave often and each node should compute owners locally |
Rendezvous (HRW) | Score each (key, node) pair, take the highest | About K/N keys; no ring to maintain, just the node list | Few nodes, O(N) lookups are fine and you want the least code |
Maglev table | Index into a fixed table of 65537 entries | More than the ring: about double on a removal | Lookups must be very fast and hosts change rarely |
Fixed slots and a directory | Hash to one of 16384 slots, look up the slot's owner | Exactly the slots an operator moves | You want to control rebalancing step by step and accept a shared table |
In a picture
Step 1 of 4
Three servers and one key on the ring
Servers A, B and C hash to 0.15, 0.70 and 0.90 on a circle. A key that hashes to 0.62 walks clockwise and stops at B, so B owns it, along with all of the arc from 0.15 to 0.70.