Distributed Systems System Design
By Imran M ·
· 9 min read
Consistent Hashing: How Distributed Systems Place Data
Consistent hashing explained: the hash ring, virtual nodes, and the rendezvous hashing alternative; the placement scheme that lets a cluster change size while remapping only about a 1/N share of keys.
A cache fleet, a sharded database, a set of storage nodes, all of them face the same placement question: given a key, which node holds it? The answer must satisfy two demands that fight each other. The mapping should be computable by anyone who knows the membership, with no central directory in the loop. And it must be stable when membership changes, because in a distributed system the membership always changes; nodes are added for capacity, removed on failure, replaced for maintenance.
Consistent hashing is a key-placement scheme in which keys and nodes are mapped onto the same circular hash space, each key belongs to the next node clockwise from its position, and a membership change moves only the keys on the affected node’s segment, about a 1/N share of the keyspace.
The problem: modulo placement
The obvious scheme is modulo placement: hash the key, divide by the number of nodes, take the remainder, node = hash(key) mod N. Anyone can compute it, nothing needs coordinating, and it spreads keys evenly. It fails at exactly the point where distributed systems live: membership change.
Remove one node from a ten-node fleet and N becomes nine. The divisor changed, so nearly every remainder changed; a key keeps its node only when both divisions happen to land the same way. On average about one key in ten survives, and the other ~90 percent are suddenly assigned elsewhere. Every reassigned key is a miss: cached values must be fetched from the source again, and in a storage system the data itself must physically move. A routine event (one node down) invalidates the placement of nearly the whole keyspace.
The hash ring
Consistent hashing (introduced by Karger and colleagues in 1997 to spread load across web caches) changes the geometry of the mapping. Instead of dividing a hash by N, it places both keys and nodes onto one large circular number space. Picture a hash the size of a 64-bit range arranged into a ring:
- Hash each node’s identity onto the ring. Ten nodes produce ten points on the circle.
- Hash each key onto the same ring.
- The key belongs to the next node clockwise from its point; that node owns the arc stretching back to the previous node’s point.
Placement is still computed, not stored: hash the key, find the next node clockwise, done. But membership change now costs almost nothing. Remove a node and only the arc it owned transfers to the node that takes over the arc, about a 1/N share of the keys. Add a node and it receives one arc, again about a 1/N share. In the ten-node fleet, losing one node reassigns ~10 percent of keys instead of ~90 percent, and adding an eleventh migrates ~9 percent. The two words in the name mean exactly this: “hashing” (the mapping is a pure hash computation anyone can run) and “consistent”; the placement stays consistent across membership changes.
One requirement hides in the setup: the hash function must be stable across processes and restarts, and it must spread points evenly. Language built-ins betray the first demand; Python’s built-in hash() is randomized per process, so two clients would disagree about placement. Ring implementations use fixed, well-distributed functions: MD5, a SHA variant, or fast non-cryptographic hashes such as xxHash or MurmurHash, keyed by node names or addresses.
Virtual nodes: why the raw ring is not enough
One honest ring with ten nodes has a flaw you can see by drawing it: the arcs are random. One node may own a sliver of the circle while its neighbor owns a fat arc: hash points spread evenly in expectation, and badly in any single arrangement. With few nodes the imbalance is striking: the largest arc is routinely several times the smallest, and the node owning it carries several times the load.
The standard fix is to stop mapping physical nodes directly and map many virtual nodes instead: give each physical node a hundred or so identities, hash all of them onto the ring, and let the physical node inherit the arcs of all its virtual positions. Many small arcs average out the way one big arc cannot, and two side benefits arrive free:
- Weighted capacity. A powerful machine gets more virtual nodes than a weak one, so hardware differences become placement shares.
- Gentler failure. A node’s load scatters across many small arcs belonging to many other nodes, so losing one machine spreads its load thinly over the fleet instead of dumping it on one neighbor.
The pattern is not theoretical. Dynamo’s storage nodes own many virtual positions on the ring, and Memcached clients such as the widely ported ketama library place hundreds of points per server. The trade is a larger ring table to search and slightly more bookkeeping when membership changes. In practice, every serious ring implementation uses virtual nodes.
Rendezvous hashing: the ringless alternative
Consistent hashing is not the only scheme with the 1/N property. Rendezvous hashing (highest random weight, from Thaler and Ravishankar in 1996) reaches the same guarantee by a simpler rule: for each key, hash the key together with the name of every node, and the node with the highest hash wins. Removing the winning node re-runs the same computation without it, and only the keys that node won change ownership: the same ~1/N share as the ring, with no ring, no arcs, and no virtual nodes.
The comparison is a genuine trade, not a ranking:
| Dimension | Hash ring + virtual nodes | Rendezvous hashing |
|---|---|---|
| Lookup cost | Binary search over ring positions | One hash per node, per key |
| Cluster view | Ordered table of ring positions | Plain list of node names |
| Balance quality | Needs many virtual nodes | Near-perfect with none |
| Membership updates | Rebuild ring segments | Trivial; the list changes |
| Best fit | Large clusters, stored placement metadata | Small clusters, simple code, frequent reconfiguration |
At small N, rendezvous hashing is hard to beat: the code is a few lines, balance is excellent, and the per-key cost of hashing against every node is irrelevant with a handful of nodes. As clusters grow, that linear per-key cost starts to matter and the ring’s binary search wins. Both schemes share the property that makes either acceptable: membership changes cost a 1/N share, not a keyspace.
Where it is used
The scheme earned its keep in infrastructure whose names are worth knowing:
- Distributed caches. Memcached clients since the ketama library have placed keys on a ring; the cache fleet is the original problem the scheme was invented for, and distributed caching covers the whole architecture it enables.
- Key-value stores. Amazon’s Dynamo popularized the ring with virtual nodes for storage placement, and the idea spread through the NoSQL generation of stores.
- Sharded databases. Placement is placement: database sharding uses the same machinery to decide which shard holds which row: the partitioning question, specialized.
- CDNs. Anything that must pick one of N servers per key without a central directory eventually lands on a ring, how a CDN works covers the edge-delivery version.
What consistent hashing does not fix
The scheme’s guarantee is about key counts, and that is a narrower promise than it first appears:
- A hot key stays hot. Placement balances keys, not load. One key receiving a hundred thousand requests a second lands on one node and stays there; no placement scheme redistributes a single key’s traffic. The hot-key counters (splitting, replicas, local tiers) belong to the cache architecture, not the placement.
- The membership view is shared state. Every participant holds a view of the ring, and views can disagree; the same key computed against two different ring views lives in two places. In practice this is managed with small membership changes and careful client rollout, but it makes placement a consistency problem in disguise, not a solved problem.
- Hash quality is assumed, not guaranteed. A poorly distributed hash function makes ring arcs uneven, virtual nodes or not; the scheme inherits every weakness of its hash.
Common mistakes
- Using the language’s built-in hash. Randomized per process in Python, unstable across versions elsewhere: the quietest way to split a fleet’s keyspace in two.
- Too few virtual nodes. A ring with ten nodes and ten points each still has fat and thin arcs; balance arrives with the many-small-averages effect, typically hundreds of points per node.
- Treating key count as load. A fleet where every node holds exactly one million keys can still have one node doing most of the work.
- Changing membership in big steps. One node in, then measured, then the next. Membership storms are how fleets discover cold misses.
- Storing the ring in one mutable place. A central ring service adds a directory and a single point of failure to a scheme whose entire point was to need neither.
FAQ
What is consistent hashing?
A key-placement scheme that maps keys and nodes onto one circular hash space, with each key owned by the next node clockwise from its position. Its guarantee: when a node joins or leaves, only the keys on the affected arc (about a 1/N share) change ownership, instead of the near-total reassignment modulo placement produces.
Why is modulo hashing a problem?
Because the node count is inside the formula: hash(key) mod N changes for every key whenever N changes. Removing one node from ten reassigns roughly 90 percent of keys; every reassigned cache key is a miss, every reassigned storage key is data to move. Consistent hashing takes N out of the formula and replaces division with position on a ring.
What are virtual nodes?
Multiple hash positions owned by one physical node, typically hundreds per machine. They fix the raw ring’s random imbalance, because many small arcs average out where few large ones do not; they allow weighting stronger machines with more arcs; and they spread a dead node’s load thinly across the fleet instead of onto one neighbor.
What is the difference between consistent hashing and rendezvous hashing?
Both keep membership changes to a ~1/N share of keys. A hash ring stores an ordered table of positions and finds a key’s owner by searching it; rendezvous hashing computes a hash of the key against every node’s name and takes the winner, with no stored ring. Rendezvous is simpler and better balanced at small cluster sizes; the ring’s cheaper lookups win as clusters grow.
Does consistent hashing fix hot keys?
No. Placement balances the number of keys per node, not the requests per node; a single hot key lands on exactly one node no matter how the ring is drawn. Hot keys are an architecture problem: key splitting, replicas, or local caching tiers absorb them.
Related articles
- Next read: distributed caching; the architecture consistent hashing makes possible: tiers, hot keys, and invalidation across a cache fleet.
- what is a distributed system, the pillar article this one builds on: partial failure, clocks, and the fallacies.
- database sharding, placement applied to durable data: hash and range strategies, hot shards, resharding.
- data partitioning, the general partitioning concept that sharding specializes.
- how a CDN works: edge delivery, another consumer of ring-style placement.
