Consistent Hashing

Consistent hashing places both nodes and keys on one circular token space. A key belongs to the first active node token encountered clockwise. Because a membership change edits only one neighboring interval, most keys keep their owner—a useful property when a cache cluster, shard map, or storage ring gains or loses a machine.

Think of the ring as a clock with 360 marks. Nodes pin their name to a few marks. Keys pin small dots to other marks. To find a key's owner, start at its dot and walk clockwise until a node marker appears. If the walk passes 359, it continues at 0. The circle has no final bucket.

How consistent hashing works

This lesson uses a right-inclusive successor rule: the owner of a key is the first active node token greater than or equal to the key token. A key at token 260 therefore belongs to a node token exactly at 260. If no active node is at or above the key token, the search wraps to the smallest active token.

The important separation is between a key token and its owner. Hashing K5 puts it at token 155. Adding or removing a node does not hash K5 again; its dot remains at 155. What may change is the first active node encountered clockwise from that fixed position.

With N1@20, N2@140, and N3@280, the ownership intervals are:

• N1 owns (280, 20], which wraps through 0.
• N2 owns (20, 140].
• N3 owns (140, 280].

The open left edge and closed right edge prevent a boundary token from having two owners. They also make successor lookup and interval ownership say the same thing.

Consistent hashing step by step

The default Node joins run fixes 12 key tokens at 10, 35, 60, 95, 125, 155, 185, 205, 235, 260, 310, 345. Nothing in the run changes those numbers.

1. Build the three-node ring. N1 is at 20, N2 at 140, and N3 at 280. Their loads are 3, 4, and 5 keys.
2. Probe and certify the wrap boundary. K11 sits at 345. There is no active node token at or above 345, so the lookup crosses 359 and 0 before stopping at N1@20. The owner changes color; K11 stays at 345.
3. Stage the new node. N4 receives token 220, between predecessor N2@140 and old successor N3@280. No key has changed owner yet.
4. Insert N4@220. The new marker joins the ring. Only one ownership boundary has been added.
5. Claim the adjacent interval. N4 takes (140, 220], which previously belonged to N3.
6. Prove one reassignment in full. K5 remains at 155, but its clockwise successor changes from N3 to N4.
7. Sweep the repeated cases. K6@185 and K7@205 lie in the same claimed interval, so both follow K5 to N4 without another full lookup lesson.
8. Check the complement. K0-K4 and K8-K11 lie outside (140, 220], so all nine keep their original owner.
9. Read the certificate. The loads change from N1=3, N2=4, N3=5 to N1=3, N2=4, N3=2, N4=3. Three keys moved and nine stayed; every key token remained fixed.

Switch to Node leaves to run the inverse kind of change. The ring starts with N1@20, N2@140, N4@220, and N3@280. Removing N2 transfers its old interval (20, 140] to the next clockwise active node, N4. Exactly K1, K2, K3, and K4 move. The other eight keys keep their owner, and the loads change from 3/4/3/2 to 3/7/2 across N1, N2, N4, and N3 before the departed node is omitted.

Virtual nodes and load skew

Local remapping does not guarantee even load. In the Virtual nodes preset, one token per physical node lands at N1@20, N2@80, and N3@300. N3 owns the large interval (80, 300] and receives 7 of the 12 keys. N1 receives 3; N2 receives 2. The load spread is five keys.

The lesson then gives each physical node three token positions:

• N1: 20, 140, 260
• N2: 80, 200, 320
• N3: 100, 240, 300

Those nine positions cut the largest gaps into smaller intervals. Five keys—K4, K5, K6, K9, and K10—find a different physical successor. The final physical loads are N1=4, N2=5, N3=3, shrinking the spread from five keys to two.

A virtual node is a position, not a new machine. All three N1 tokens still point to the same physical N1. More positions make an unlucky large interval less likely and make weighted capacity possible, but they do not promise a perfectly even sample.

Why consistent hashing remaps less than modulo sharding

Keep the active tokens in sorted order. Finding the clockwise successor then costs O(log V) with binary search, where V is the total number of physical and virtual tokens. A lookup also needs a constant-time wrap to the first entry when the search falls off the end.

A membership change inserts or removes a token in that sorted set and transfers the keys in one adjacent interval. The exact transfer work depends on how many keys landed there. Under uniform independent hashes, equally weighted nodes, and enough keys to smooth sampling noise, adding one of N physical nodes moves roughly 1 / (N + 1) of the keyspace on average. The default trace proves locality for one fixed sample; it does not pretend that every join moves exactly that fraction.

Plain modulo sharding behaves differently. If ownership is hash(key) % serverCount, changing the server count changes the divisor in every placement calculation. In the Modulo contrast preset, the same 12 hashes move from three servers to four. Ten keys change owner; only K2@60 and K7@205 stay put. The consistent-hash join moves three of those 12 keys because N4 claims one adjacent interval. Same hashes, same extra server, very different moving bill.

When to use consistent hashing—and when not to

Consistent hashing earns its keep when membership changes and moving data is expensive: cache clusters, application-managed shard maps, object stores, and request routers are the usual examples. You need a stable key hash, a membership view that every participant can agree on, and a transfer process for the interval that changes owner.

What consistent hashing does not solve

The ring chooses placement; it does not move the bytes for you. Replication, failure detection, ring-version rollout, and streaming data to a new owner are separate protocols.

Virtual-node counts can represent capacity by giving a larger machine more token positions. Do not pick a token count from folklore and call it done. Measure the load spread, metadata cost, and movement cost with your key distribution. A hot key is a different failure: more token positions still send that one key to one owner, so use replication, request coalescing, or application-level splitting.

When another placement scheme is simpler

Use rendezvous hashing when you want the same low-remapping idea without maintaining a sorted ring: rank each candidate node for the key and choose the highest score. Static modulo sharding is simpler when the server set is genuinely fixed. If your database already owns replication and online resharding, use its placement machinery unless you have a concrete reason to replace it; a hand-rolled ring is not a free infrastructure upgrade.

Consistent hashing edge cases

• Wrap-around. K11@345 has no successor before token 359, so it wraps to N1@20. Forgetting the wrap leaves part of the ring unowned.
• Exact token equality. In the virtual-node trace, K9@260 belongs to N1's token at 260. The right endpoint is included.
• A node leaves. Its entire old interval goes to the next clockwise active token, not to its predecessor and not to every remaining node.
• Uneven token spacing. One token per machine can leave a large arc on one owner. Consistent remapping and balanced load are separate properties.
• A hot key. Virtual nodes spread many distinct key tokens; they do not split one extremely popular key across owners. Replication or application-level partitioning is needed for that.
• Very small rings. With one active node, every key wraps to it. With two, one failure sends every key to the survivor even though the successor rule still works.
• Hash collisions. A production system needs a deterministic tie policy when node and key hashes collide. This lesson uses distinct fixed positions except for the deliberate right-inclusive K9 boundary.

Common Mistakes

These are the consistent hashing mistakes that most often break the ring's guarantees:

• Rehashing keys when membership changes. The key's token must be independent of the active node list. The owner may change; the key dot does not move.
• Walking counterclockwise. This lesson assigns the first clockwise successor. Reversing direction changes every interval definition.
• Giving a departed interval to the predecessor. The next active token clockwise inherits it, because that token becomes the first successor for those keys.
• Using closed intervals on both sides. [a, b] and [b, c] both claim b. The lesson uses (a, b] to give every token exactly one owner.
• Treating virtual nodes as extra servers. They are several ring positions that route back to one physical node.
• Promising perfect balance. Virtual nodes reduce variance. Capacity weights, token count, the hash function, and the actual key sample still matter.
• Equating consistent hashing with replication. The ring shown here chooses one owner. Replicas, failover copies, and consistency between copies are separate design decisions.

A note on simplifying consistent hashing

The animation uses a normalized 0–359 ring, fixed node tokens, 12 fixed key tokens, and one copy per key. It omits replication, weighted capacity, concurrent membership changes, transfer cost, failure detection, data streaming, and hot-key mitigation. Virtual nodes are added in one visible beat rather than through a production membership protocol. These choices keep the ownership proof exact: membership can change an adjacent interval without changing hash(key).