How Consistent Hashing Works: Rings, Virtual Nodes, and Why Keys Move

A cache cluster, a sharded database, and a content-delivery edge all share one problem: given a key, which machine should own it?

The naive answer is hash(key) mod N, where N is the number of servers. That mapping is simple and even. It is also brittle. Add one server and almost every key changes owner. Remove one server and the same thing happens. The cluster spends its time moving data instead of serving it.

Consistent hashing is the family of mappings that keep most keys where they are when N changes. Only a sliver of the keyspace is supposed to move — ideally about 1/N of it when a node joins or leaves. This article explains the ring construction, why virtual nodes exist, what still goes wrong under load, and how related algorithms differ.

The contract

A placement function maps each key to exactly one current node. Useful properties:

• Stability. When the set of nodes changes by one member, only keys that belonged to the departing node (or that must fill the new node) should remapped.
• Balance. Each live node should receive a similar fraction of keys, unless you deliberately weight nodes by capacity.
• Locality of lookup. A client that knows the current membership should compute the owner without asking a coordinator on every request.

hash(key) mod N gives balance and cheap lookup. It fails stability. That is the problem consistent hashing was designed to fix, first in the context of web caches in the late 1990s and later in systems such as Dynamo, Cassandra, Riak, and many partitioners in front of caches and message queues.

Why modulo hashing reshuffles everything

Suppose keys hash to integers and you have three nodes, numbered 0, 1, and 2. Key user:42 hashes to 14. Then 14 mod 3 = 2, so node 2 owns it.

Add a fourth node. Now 14 mod 4 = 2 — this particular key happens to stay. Another key that hashed to 11 moves: 11 mod 3 = 2, but 11 mod 4 = 3. Across the whole space, the new modulus re-slices every residue class. Empirically, most keys change owner when N changes by one.

That cost is not academic. Moving a key means reading it from the old node, writing it to the new one, and serving stale or missing data until the copy finishes. At cluster scale the transfer saturates disks and networks.

The hash ring

Place both nodes and keys on the same circle.

1. Choose a hash function whose output is a large integer range, for example 0 through 2³²−1 or 2¹²⁸−1. Treat the range as a circle: the highest value wraps to zero.
2. Hash each node’s name (or address) onto that circle. The result is that node’s position.
3. Hash each key onto the same circle.
4. Walk clockwise from the key until you hit a node. That node owns the key. Equivalently: the owner is the first node whose position is greater than or equal to the key’s hash, wrapping around if needed.

Each node therefore owns the arc that ends at its position and starts just after the previous node. The keyspace is partitioned into contiguous arcs, one per node.

When a node joins, it is hashed onto the circle and takes ownership of the keys that fall on the arc between itself and its clockwise predecessor. Those keys previously belonged to the clockwise successor. Every other arc is untouched.

When a node leaves, its successor inherits that arc. Again, other nodes keep their keys.

That is the stability property in geometric form: a membership change affects only the neighboring arc, not the whole ring.

A compact example

Imagine a circle marked 0–99 for readability (real systems use a much larger space).

Nodes land at 10, 40, and 75.

• Keys hashing to 11–40 belong to the node at 40.
• Keys hashing to 41–75 belong to the node at 75.
• Keys hashing to 76–99 and 0–10 belong to the node at 10.

Insert a node at 55. It steals the range 41–55 from the node at 75. Ranges 11–40 and 76–10 do not move.

Remove the node at 40. Its range 11–40 is absorbed by 75. Nothing else moves.

The fraction that moves is the size of the stolen or inherited arc divided by the whole circle — on average about 1/N if positions are uniform.

Virtual nodes

Hashing a node once is not uniform enough. With a handful of physical machines, random positions on the circle produce arcs of very different lengths. One unlucky node can own twice the average keyspace. When that node dies, its large neighbor inherits an even larger shock.

Virtual nodes (vnodes, or tokens) fix this by placing each physical server at many positions.

Instead of hashing server-A once, hash server-A#0, server-A#1, …, server-A#127. Each physical machine now owns many small arcs scattered around the ring. The law of large numbers pulls per-server totals toward the mean. When a machine leaves, its many small arcs are inherited by many different successors, so the load spreads instead of dumping onto one neighbor.

Typical production counts are tens to hundreds of vnodes per core or per disk, chosen so that:

• the coefficient of variation of load stays acceptable,
• a departing node fans its keys out across most of the remaining cluster,
• the membership table still fits in memory and can be gossiped or published without becoming the bottleneck.

Weighted vnodes are the usual way to express capacity. A host with twice the RAM publishes twice as many tokens. You do not need a separate weighted-hash formula if token counts already encode weight.

Lookup implementation

Clients and coordinators keep a sorted list of token positions and the physical node behind each token. Lookup is:

1. Hash the key.
2. Binary-search the sorted token list for the first token ≥ that hash (or wrap to the first token).
3. Return the node that owns that token.

The list is small: a few thousand integers for a mid-size cluster. Updating it is an ordinary membership event. No per-request consensus is required for the mapping itself, though replication and hinted handoff still need failure detection.

Some libraries store tokens in a balanced tree or a skip list. The asymptotic cost stays logarithmic in the number of tokens, which is effectively constant for the sizes people actually run.

Replication on the ring

Storage systems rarely keep one copy. A common pattern, used by Dynamo-style stores, walks clockwise from the primary and picks the next distinct physical nodes as replicas. Virtual nodes belonging to a machine already chosen are skipped so that two replicas do not land on the same host.

The replication set for a key is therefore a short clockwise walk. When a node fails, reads and writes can continue on the remaining replicas. When it returns, hinted handoff or anti-entropy repair copies missing data back.

This is placement, not consensus. Quorum rules (R + W > N copies) decide whether a read or write is considered successful. The ring only answers “which N machines?”

What the basic ring still gets wrong

Hot keys. Consistent hashing balances key identities, not request rates. One celebrity user ID can pin a shard. The ring will not save you; you need caching, key salting, or an explicit hotspot splitter.

Bounded imbalance. Even with vnodes, random placement can leave a node a bit over the mean. Algorithms such as consistent hashing with bounded loads reject a node that is already over a multiplier of fair share and walk to the next token. The extra walk is rare if the multiplier is modest (for example 1.25) and vnodes are plentiful.

Correlated failures. If tokens are assigned without rack awareness, a single switch failure can take several consecutive physical owners. Production partitioners often constrain replica walks to different racks or availability zones.

Membership churn during lookup. Two clients that briefly disagree on who is alive will send a key to different owners. Systems treat that as a transient: sloppy quorums, hinted handoff, and read repair exist because the ring is an approximation of live membership, not a linearizable directory.

Related mappings

Rendezvous hashing (highest random weight) does not use a ring. For each key it computes hash(key, node) for every live node and picks the maximum. Adding or removing a node changes the winner only for keys that preferred that node. Balance is excellent. The cost is O(number of nodes) per lookup unless you add an approximation layer. It is a good fit when N is small — a handful of cache proxies — and you want no extra vnode configuration.

Jump consistent hashing maps a key to an integer bucket in 0..N-1 with very little compute and almost no memory. It assumes buckets are numbered and that you only grow N by appending. It does not name arbitrary hosts. Use it when shards are contiguous integers, not when servers have stable identities that come and go in the middle of the set.

Maglev and similar lookup tables, used in front-end load balancers, build a large permutation table so that each backend owns a nearly equal number of slots and a backend failure reshuffles only its slots. Lookup is an array index. The table is rebuilt when membership changes. That trade — more memory, faster lookup, controlled churn — is what you want on a packet path.

Where this shows up

Partitioning a key-value store or a cache is the textbook case. The same idea appears in:

• request routing at a reverse proxy when backends are not identical and you want session-ish stickiness without a shared session store,
• assigning Kafka-like partitions to consumers is not usually consistent hashing — consumer groups rebalance partitions as ranges — but assigning partition leaders across brokers often is a related token problem,
• sharding a search index or a time-series store so that adding a node copies a fraction of segments rather than rebuilding the world,
• content-addressed storage, where the key already is a hash and the ring decides which disk pack holds the blob.

If the working set is tiny or N almost never changes, modulo hashing is simpler and fine. Consistent hashing earns its complexity only when membership is expected to change while the service stays up.

Misconceptions

“Consistent hashing guarantees even load.” It guarantees a stable mapping. Evenness depends on hash quality, vnode count, and whether keys are equally popular.

“The ring is stored on disk as a circle.” The circle is a way to think about ordered tokens. On disk you have ordinary files, SSTables, or heap pages. The ring lives in the membership view.

“Adding a node always moves exactly 1/N of keys.” That is the expected fraction under uniform tokens. A specific join can steal a larger or smaller arc. Vnodes shrink that variance; they do not delete it.

“Clients must talk to a hash coordinator.” They must agree on membership. Once they do, the owner is a local computation. Gossip, config services, and DNS can all carry that view.

Takeaways

Modulo hashing is a good partitioner only for a frozen cluster. Consistent hashing puts keys and nodes on one ordered space so that a join or leave remaps a neighboring slice instead of the entire table. Virtual nodes exist because one random point per machine produces ugly arcs and ugly failure domains. Replication is a clockwise walk over distinct physical owners, not a second hash. Hot keys, rack topology, and bounded-load variants are the practical patches once the basic ring is in place.

If you already know how a cache or a sharded store decides ownership, the ring is the piece that lets that decision survive the next hardware change.

Related reading on this site: How Caching Works, SQL vs NoSQL Explained, and How Databases Work Internally.