What you'll learn: By the end of this lesson you will be able to show why
hash(key) mod nmoves almost every key when the node count changes, explain how a hash ring and its virtual nodes move only about 1/n of the keys and smooth the load, describe how a ring picks the next N distinct nodes for replicas, compare rendezvous (highest random weight) hashing and jump consistent hash and say what each one cannot do, and read the measurements from two Java labs that put all four placement rules side by side.
A theatre coat-check hangs coats on numbered racks and sends you to rack ticket mod 10. It works until the theatre adds an eleventh rack: every ticket now maps to ticket mod 11, so nearly every coat must be carried to a new rack. A better rule lets the new rack take a few coats from its neighbours and leaves the rest where they hang.
That second rule is consistent hashing. Sharding and partitioning explains why data is split across nodes; this lesson is the dedicated treatment of the placement rule that decides which node owns which key.
Verified on 2026-11-19: both labs' tests pass (12 and 18 tests) and each demo reproduces its committed golden output. Sources are listed under Official documentation.
The core idea
Consistent hashing is a placement rule whose answer changes as little as possible when the set of nodes changes. Karger and colleagues, who introduced it in 1997, describe it as a hash function that changes minimally as the range of the function changes. Each scheme below gets that property and pays for it somewhere else.
Three kinds of example run through the lesson, each labelled:
- Minimal example: the two Java labs in "Build it": a ring with virtual nodes, and a four-way comparison.
- Realistic example: ShopStream's product-page cache tier, in "In practice".
- Failure example: a ring with one point per node, where the busiest node holds three times its share.
Why hash mod n fails
The simplest placement rule hashes the key and takes the remainder: owner = hash(key) mod n. It balances well. In the lab below, with 10 nodes and 100,000 keys, the fullest node holds 1.010 times its ideal share. Its problem is not balance but what happens when n changes.
The jump consistent hash paper gives the example: with 10 shards a key goes to h(key) mod 10, with 12 shards to h(key) mod 12, "which is probably not the same", so the data would need to be completely rearranged, although only 1/6 of it has to move to end up balanced. The rendezvous hashing paper says the same: when the number of active servers changes, almost all objects will need to be reassigned.
The arithmetic is short. For an evenly spread hash, the remainders mod 10 and mod 11 agree for 10 of every 110 values, one in eleven. About 1/11 = 9.09% of keys stay and about 90.9% move. A cache that loses 91% of its entries at once is empty for the next few minutes; a store must copy 91% of its data. The goal is the opposite: node 11 takes roughly 1/11 of the keys, and no key moves between two old nodes.
The ring: keys and nodes on the same circle
The Dynamo paper (section 4.2) describes the construction: the output range of the hash function is a fixed circular space or ring, so the largest hash value wraps around to the smallest. Each node gets a random position in that space; a key is hashed to a position and assigned by walking clockwise to the first node with a larger position. Each node is responsible for the region between it and its predecessor, so departure or arrival of a node only affects its immediate neighbors.
Figure 1. The lookup is local. How to read this: the application hands a key to a function that hashes it, finds the next point on the ring and returns that point's node. No node is asked where a key lives, so any client holding the same list of points gets the same answer.
The lab's HashRing is that rule in a sorted map from ring position to node. Its lookup is five lines:
public String nodeFor(String key) {
if (ring.isEmpty()) {
throw new IllegalStateException("the ring has no nodes");
}
Map.Entry<Long, String> entry = ring.ceilingEntry(hash(key));
return (entry != null ? entry : ring.firstEntry()).getValue(); // wrap around past the largest point
}
ceilingEntry returns the first point at or after the key's hash, and when there is none the lookup wraps to the smallest point. The hash is SHA-256 cut to 64 bits: used for spreading, not security, and identical on every JVM, so the lab's numbers are reproducible.
Joining and leaving
A joining node adds only its own points, so it takes over only the arcs those points cut. In the Dynamo paper's bootstrap example (section 4.9), a node X added between A and B takes over ranges held by B, C and D, which offer the keys to X and transfer them once X confirms. Removal runs in reverse.
Figure 2. A join, simplified. How to read this: only the owners of the cut arcs take part. Keys move from old nodes to the new node, never between old nodes. Protocol details differ per system.
Virtual nodes: smoothing the load
One random point per node is a poor design. The Dynamo paper names the two challenges of the basic algorithm: random positions lead to non-uniform data and load distribution, and the algorithm is oblivious to the heterogeneity in the performance of nodes. Its answer is virtual nodes: each node gets multiple positions ("tokens") on the ring.
The paper lists three advantages: when a node becomes unavailable its load is evenly dispersed across the others, a new or returning node accepts a roughly equivalent amount of load from each of the others, and the number of virtual nodes can follow a node's capacity. The cost is bookkeeping. Karger's construction replicates each bucket log(C) times, and the jump hash paper says the ring needs thousands of bytes of storage per candidate shard for a fairly even distribution. With v points per node and n nodes, the lab's ring holds n x v entries that every client must keep in step.
Failure example: the unlucky ring. The first demo section below sets v = 1. Ten nodes each hash to one point, the arcs between points differ wildly, and the lab's fullest node holds 30,936 of 100,000 keys, 3.09 times its ideal 10,000, while the emptiest holds 258. Every lookup works and the ring is perfectly consistent; it is an outage waiting for the node with 3.09 times its share.
Replication: the next N distinct nodes
A ring also answers "where do the copies go?" The Dynamo paper (section 4.3) has the coordinator for a key store it locally and replicate it at the N-1 clockwise successor nodes. The list of nodes responsible for a key is the preference list, and because of virtual nodes, the first N successor positions may belong to fewer than N distinct physical nodes, so the list is built by skipping positions to contain only distinct physical nodes. Cassandra's documentation describes the same walk: "walk" the ring clockwise until three distinct nodes are found for a replication factor of three, and replicas are always chosen to be distinct physical nodes.
Figure 3. Why the walk skips. How to read this: with virtual nodes one physical node owns many points. Walking clockwise, a second point of node A is passed over, because two copies on one machine are not two copies. The dashed edge marks the skipped point.
Alternatives: rendezvous and jump hash
Two other schemes get the same movement property without a ring.
Rendezvous (highest random weight) hashing. Thaler and Ravishankar's 1998 paper derives a random weight for each server from the object name and the server address and sends a request to the active server with the highest weight. It is stateless: it depends only on the identities of the object and the servers. When a server goes down only its objects are reassigned, evenly divided among the survivors, and unequal capacity can be handled by scaling a server's weights by a constant. The second-highest weight is the natural fallback, so the same rule gives an ordered replica list. The lab's core is one hash per node:
for (String node : nodes) {
long weight = Hash64.of(node, key);
if (best == null || beats(weight, node, bestWeight, best)) {
best = node;
bestWeight = weight;
}
}
Jump consistent hash. Lamping and Veach (Google, 2014) present it as a fast, minimal memory algorithm in about five lines with no storage: a 64-bit key and a bucket count in, a bucket number from 0 to n-1 out. The lab's loop:
while (j < buckets) {
b = j;
key = key * 2862933555777941757L + 1; // 64-bit linear congruential step
j = (long) ((b + 1) * ((double) (1L << 31) / (double) ((key >>> 33) + 1))); // key >> 33 is unsigned
iterations++;
}
The idea: going from n to n+1 buckets a key stays with probability n/(n+1) and otherwise jumps to the new bucket, so the code computes only the jumps, and the expected loop count is less than ln(n) + 1. The paper's stated limitation is that the buckets must be numbered sequentially, which makes it more suitable for data storage than for distributed web caching.
Figure 4. A decision, not a ranking. How to read this: each question is a capability one scheme lacks. Jump hash cannot remove an arbitrary node, rendezvous costs time per node, the ring costs memory and needs many virtual nodes to balance.
Build it: one ring, then four rules side by side
The labs are plain Java with no dependencies, outside the site build.
Goal. Measure how many keys move when a node is added or removed, whether they move only where they must, how evenly load spreads, and what a lookup costs.
Setup. From the repository's examples/backend folder:
./gradlew :labs:consistent-hash-ring:test
./gradlew -q :labs:consistent-hash-ring:run
./gradlew :labs:rendezvous-and-jump-hash:test
./gradlew -q :labs:rendezvous-and-jump-hash:run
The ring lab runs 12 tests and the comparison lab 18. The code is in examples/backend/labs/consistent-hash-ring/src/main/java/buildingai/labs/consistenthashring/HashRing.java and in examples/backend/labs/rendezvous-and-jump-hash/src/main/java/buildingai/labs/rendezvousjump/.
Part 1: the ring
How it works. Every node is hashed onto a 64-bit ring at many points (node-3#0, node-3#1, and so on). A key belongs to the first point at or after its hash. The demo places 100,000 keys, adds an eleventh node to a ten-node cluster, removes node-3, and measures balance.
Expected output, captured from a real run:
Consistent hashing with 100000 keys
1. Add a node to a 10-node cluster (ideal share for the new node: 1/11 = 9.09%)
hash(key) mod n, 10 -> 11 nodes moved 91124 of 100000 keys (91.12%)
ring, 1 virtual node(s) each, 10 -> 11 moved 8745 of 100000 keys ( 8.75%)
ring, 10 virtual node(s) each, 10 -> 11 moved 10539 of 100000 keys (10.54%)
ring, 100 virtual node(s) each, 10 -> 11 moved 8402 of 100000 keys ( 8.40%)
ring, 500 virtual node(s) each, 10 -> 11 moved 8818 of 100000 keys ( 8.82%)
2. Where the moved keys went (ring, 100 virtual nodes, 10 -> 11 nodes)
moved to node-10: 8402, moved between old nodes: 0
3. Remove node-3 from the 11-node ring
keys owned by node-3 before: 8333
keys that moved moved 8333 of 100000 keys ( 8.33%)
4. Load balance across 10 nodes (ideal: 10000 keys each)
1 virtual node(s): min= 258 max= 30936 max/ideal=3.09
10 virtual node(s): min= 6921 max= 13525 max/ideal=1.35
100 virtual node(s): min= 8505 max= 11770 max/ideal=1.18
500 virtual node(s): min= 9235 max= 10442 max/ideal=1.04
| Section | What it shows |
|---|---|
| 1 | Ideal for the new node: 1/11 = 9.09%. Modulo moves 91.12%; the ring with 100 virtual nodes 8.40%. Few virtual nodes make it noisy (10.54% with 10): the new node's share of the ring is random. |
| 2 | All 8,402 moved keys went to node-10; none moved between old nodes. |
| 3 | Removing node-3 moves exactly the 8,333 keys it owned. |
| 4 | Busiest node against ideal: 3.09 with one virtual node, 1.35 with ten, 1.18 with 100, 1.04 with 500. |
Part 2: four rules compared
How it works. hash(key) mod n, the ring from part 1, rendezvous hashing and jump hash, each behind one interface, on the same 100,000 keys. For jump hash, removing a node that is not last is done the only way it can be: the last node takes the removed node's bucket number.
Expected output, captured from a real run:
Four ways to place 100000 keys on nodes, compared
1. Add node-10 to a 10-node cluster (ideal: 1/11 = 9.09% of the keys move, all of them to node-10)
hash(key) mod n moved 91124 (91.12%) to node-10: 9096 between old nodes: 82028
ring, 100 virtual nodes moved 8402 ( 8.40%) to node-10: 8402 between old nodes: 0
rendezvous (highest weight) moved 9103 ( 9.10%) to node-10: 9103 between old nodes: 0
jump consistent hash moved 9039 ( 9.04%) to node-10: 9039 between old nodes: 0
2. Remove node-3 from an 11-node cluster (ideal: only node-3's own keys move, 1/11 = 9.09%)
hash(key) mod n moved 91028 (91.03%) keys node-3 owned: 9028 moved although not node-3's: 82000
ring, 100 virtual nodes moved 8333 ( 8.33%) keys node-3 owned: 8333 moved although not node-3's: 0
rendezvous (highest weight) moved 9024 ( 9.02%) keys node-3 owned: 9024 moved although not node-3's: 0
jump consistent hash moved 17280 (17.28%) keys node-3 owned: 9182 moved although not node-3's: 8098
3. Balance across 10 nodes (ideal: 10000 keys each)
hash(key) mod n min= 9846 max= 10100 max/ideal=1.010 std dev=0.77% of ideal
ring, 100 virtual nodes min= 8505 max= 11770 max/ideal=1.177 std dev=10.01% of ideal
rendezvous (highest weight) min= 9857 max= 10123 max/ideal=1.012 std dev=0.80% of ideal
jump consistent hash min= 9758 max= 10170 max/ideal=1.017 std dev=1.07% of ideal
ring, 1000 virtual nodes min= 9751 max= 10535 max/ideal=1.054 std dev=2.21% of ideal
4. Work per lookup
rendezvous: one hash per node, so n hashes (n = 10 -> 10, n = 1000 -> 1000)
jump hash: loop iterations per lookup, averaged over 100000 keys (the paper's bound is ln(n) + 1)
n= 10 average iterations= 2.92 ln(n)+1= 3.30
n= 100 average iterations= 5.17 ln(n)+1= 5.61
n= 1000 average iterations= 7.47 ln(n)+1= 7.91
n= 10000 average iterations= 9.77 ln(n)+1=10.21
5. Rendezvous gives an ordered replica list: the top 3 nodes for each key (11 nodes, then node-3 is removed)
first key whose set changed: user:0 [node-3, node-0, node-8] -> [node-0, node-8, node-4]
replica sets that changed: 27385 of 100000 (27.39%; ideal 3/11 = 27.27%)
changed sets that kept both surviving replicas: 27385 of 27385
| Section | What it shows |
|---|---|
| 1 | Adding a node: the three consistent schemes move about the ideal 9.09% (8.40%, 9.10%, 9.04%), all to node-10. Modulo moves 91.12%, 82,028 of them between old nodes. |
| 2 | Removing node-3: ring and rendezvous move only its keys. Jump hash moves 17.28%, with 8,098 keys moved although not node-3's: about twice the ideal. |
| 3 | Balance: modulo, rendezvous and jump hash are within about 2% of ideal. The ring with 100 virtual nodes is at 1.177 and needs 1,000 to reach 1.054. |
| 4 | Rendezvous does one hash per node. Jump hash's average loop count stays below the paper's ln(n) + 1 bound for every n shown. |
| 5 | Removing node-3, 27.39% of three-node replica sets changed (ideal 3/11 = 27.27%), and every changed set kept both surviving replicas. |
All numbers are for this lab's 100,000 keys and its hash. They are measurements of this code, not benchmarks of any product.
Break it. In HashRing.nodeFor, replace the ring lookup with modulo placement over the node list. The three movement tests fail and the demo shows most keys moving. Restore the line afterwards and re-run the lab tests.
Stretch. Add weights (twice the capacity, twice the points or weight) and check the share.
What the model leaves out. No networking, data copying or membership protocol, and SHA-256 is chosen for reproducibility, not speed: the demo counts operations, not nanoseconds.
What each approach cannot do
| Rule | Cannot do | Cost in this lab | Lookup | State |
|---|---|---|---|---|
hash mod n |
Survive a change of n |
91% of keys move | One hash | None |
| Ring with virtual nodes | Balance well with few points | 1.177 at 100 points | Sorted-map search | n x v points on every client |
| Rendezvous | Skip the per-node work | n hashes per lookup |
O(n) |
The node list only |
| Jump hash | Remove an arbitrary node, or name nodes | 17.28% moved on a middle removal | About ln(n) + 1 steps | None |
Two limits apply to all of them. They say where a key belongs, not how to copy the data, which is the real cost of rebalancing. And they need clients to agree on the node list: Karger's paper was built for clients that see different subsets of caches, while Dynamo spreads token ranges by gossip so each node learns its peers' ranges (section 4.8.1). The rule is only as consistent as the membership view it is fed.
How real systems use it
Dynamo. The paper uses a ring with virtual nodes and a preference list of distinct physical nodes. Its initial strategy, T random tokens per node, caused operational pain (section 6.2): a joining node had to scan other nodes' stores to steal its ranges, and during the busy shopping season bootstrapping took almost a day; Merkle trees had to be recalculated when ranges changed; and a snapshot of the key space was hard to take. Later strategies divided the hash space into Q equal partitions and decoupled partitioning from placement. The ring is the placement rule, not the whole operational story.
Cassandra. The documentation maps every node to one or more tokens on a continuous ring; a token is the hash of the key. In 2.x, random allocation needed a high default of 256 tokens per node; at the time of writing the num_tokens default in cassandra.yaml is 16, with a newer deterministic allocator. The default partitioner is Murmur3Partitioner, and it cannot be changed without reloading all data. Cassandra never removes a node from gossip state without explicit instruction from an operator: a dead node keeps its ranges until someone decommissions or replaces it.
Rendezvous and jump hash. The rendezvous paper reports adoption by the multicast routing protocols PIMv2 and CBTv2 to choose rendezvous points. The jump hash paper positions it for data storage, where a shard does not simply disappear and shards can be numbered in order.
Failure and rebalancing behaviour
When a node dies, the rule has a clean answer: its keys go to the next owners. On a ring with enough virtual nodes those owners are many different nodes, so the failed node's load is evenly dispersed; rendezvous divides the reassigned keys evenly among the survivors too. Every client that sees the same node list gets the same answer, and clients with different lists do not.
The harder part is what the answer implies. Once a node is removed, its keys live on nodes that do not hold them. For a cache that means misses that land on the database; for a store, data must be streamed or served from the surviving replicas. That is why systems separate "unreachable" from "removed": Cassandra waits for an operator. Adding a node has its own cost: it takes roughly 1/n of the keys, and the nodes giving them up scan and stream in the background. When a server comes back in rendezvous hashing, only objects whose weight beats the previous winner need to be reassigned (Thaler and Ravishankar).
Figure 5. Failure shows up as misses on the next owner. How to read this: both clients apply the same rule but start from different lists. Only the dead node's keys are affected; every other key still maps to the same node for both clients.
Misconceptions, corrected
| Claim | Correction |
|---|---|
| "Consistent hashing balances load." | Not by itself: one point per node gave a node with 3.09 times its share in the lab. |
| "It fixes hot keys." | One hot key still hashes to one place. Dynamo's design assumes enough popular keys that spreading keys spreads load (section 6.2). |
| "The ring moves exactly 1/n of keys." | About 1/n: 10.54% with 10 virtual nodes and 8.40% with 100, against an ideal 9.09%. |
| "Jump hash is a ring without memory." | It can only add or drop the last bucket and cannot name nodes. |
| "Adding a node moves the data automatically." | The rule says where keys belong. Copying them is a separate, expensive job. |
In practice: a product-page cache tier that must grow without a miss storm
This is the realistic example. It is an educational scenario on the course's running example, ShopStream, and nothing in it describes a real company. Every figure is illustrative.
This is a realistic scenario, not a case history.
The situation
ShopStream caches product and price-list entries on ten cache nodes in front of PostgreSQL (scaling reads). Application servers pick the node with hash(key) mod 10. Marketing plans a promotion and the team wants an eleventh node before it starts.
Starting architecture
Figure 6. The design before the change. How to read this: reads go to a cache node by hash mod n; a miss reads PostgreSQL. After adding node 11, the same rule sends about 91% of keys to a different node than before.
Options considered
| Option | Behaviour when node 11 is added | Cost | Risk |
|---|---|---|---|
| A. Keep mod n, add the node anyway | About 91% of keys change owner and miss | Nothing to build | A miss storm onto PostgreSQL |
| B. Rendezvous hashing in the application servers | About 1/11 of keys move, all to node 11 | n hashes per lookup; a shared node list |
List disagreement between clients |
| C. A ring with 200 virtual nodes per node | About 1/11 moves, with some noise | n x 200 points per client |
Imbalance if virtual nodes are too few |
The decision
Option B. With ten to a few tens of nodes, one hash per node per lookup is affordable, there is no ring state to keep in step, the lab's balance for rendezvous was the best of the consistent schemes, and a dead node's keys fall to the next-highest weight without a special case. The team would revisit it at hundreds of nodes or if the per-lookup cost showed up in profiles. Jump hash was rejected because cache nodes fail and must be removable in any order.
Illustrative arithmetic for the old rule: if the cache answered 95 of every 100 reads, the database saw 5. Moving 91% of the cached keys at once turns about 86 of those 95 hits into misses, so the database would see roughly 91 reads per 100, around 18 times its normal load, until the cache refills.
Rollout and verification
Replay a sample of recent keys through the old and new rules offline and check the two properties the lab's tests assert: the moved fraction is near 1/11 and every moved key goes to the new node. Roll the new rule out behind a flag, add node 11 only after every server runs it, and watch cache hit ratio, PostgreSQL read rate, keys per node and the number of node-list versions in use. Rate-limit refills so a surge of misses does not stampede the database (see cache stampede and hot keys).
The 2 a.m. failure
The page reads: cache hit ratio dropped and PostgreSQL CPU is climbing. A cache node crashed during the promotion, and some application servers still list it. They send its keys to a dead address and time out, while updated servers route the same keys to the next-highest weights, which miss and read the database (Figure 5). The checks: the node-list version on each server, the timeout rate per cache node, and the hit ratio per node. The mitigation is to push the corrected list everywhere, cap the database read rate and let the survivors refill. The lasting fix is one versioned source for the node list, a circuit breaker that skips a node after repeated timeouts (rendezvous gives the fallback for free), and headroom to absorb the dead node's roughly 1/11 of keys.
Architect's notes
- Choose the rule by what changes. Fixed size: modulo. Shards only grow at the end: jump hash. Arbitrary removal with few nodes: rendezvous. Many nodes or token ranges: a ring.
- Pick virtual nodes by the balance you need. The lab shows 1.35 at 10 and 1.04 at 500; more points cost memory.
- Version the node list. Every argument above assumes clients agree on it.
- Plan the data movement, not just the key movement. Throttle streaming and keep it off the serving path.
- Keep one hash everywhere. Changing the hash function reassigns every key, like changing
n.
Common mistakes
- Adding a node to a
mod nplacement at peak traffic. - Using one point per node and calling the ring balanced.
- Letting clients hold different node lists with no version.
- Treating a dead node and a removed node as the same event.
- Using jump hash for named nodes or for caches where any node can fail.
- Counting two points of one machine as two replicas.
Key takeaways
hash mod nbalances well and moves almost every key whennchanges: 91% for 10 to 11 nodes in the lab.- A ring, rendezvous hashing and jump hash all move about 1/(n+1) of keys on a join, only to the new node.
- A ring needs many virtual nodes: one point per node gave 3.09 times ideal, 500 gave 1.04.
- Replicas are the next distinct nodes clockwise on a ring, or the next-highest weights in rendezvous.
- Rendezvous costs one hash per node per lookup; jump hash keeps no state but only grows and shrinks at the end (17.28% moved on a middle removal).
- The rule only decides ownership. Copying data, agreeing on the node list and hot keys are separate problems.
Practice exercises
Exercise 1 (30 min). Run the ring demo and write one sentence per section on what a shopper's product page would notice.
Exercise 2 (45 min). For 20 nodes going to 21, compute the share of keys hash mod n keeps (remainders agree over 420 values) and compare with the ideal movement of a consistent rule.
Exercise 3 (1 hour). Run "Break it" in the ring lab, then restore the code and re-run the tests. Write down which three tests fail and what each protects.
Exercise 4 (1 hour). In the comparison output, find the best-balanced rule and the cheapest membership change, and explain why no single rule wins.
Exercise 5 (2 hours). Design node-list distribution for the ShopStream cache tier: who owns it, how clients learn of a change, how you detect clients on different versions, and what a client does when a node times out.
Related reading
- Sharding and Partitioning: why data is split and the strategies for choosing a shard key.
- Replication: leaders, followers and lag.
- Quorum Reads and Writes: the replicas a ring chooses, and how many must answer.
- Cassandra and DynamoDB Modelling: partition keys on a token ring.
- Cache Stampede and Hot Keys: what the miss storm does and how to damp it.
- ShopStream Stage 3: scale reads: the cache tier in context.
Official documentation
- Karger et al., Consistent Hashing and Random Trees (STOC 1997): the definition, monotonicity, spread and load.
- DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007): sections 4.2, 4.3, 4.9 and 6.2.
- Lamping and Veach, A Fast, Minimal Memory, Consistent Hash Algorithm (Google, 2014): jump consistent hash.
- Thaler and Ravishankar, Using Name-Based Mappings to Increase Hit Rates (IEEE/ACM Transactions on Networking, 1998): highest random weight.
- Apache Cassandra documentation: Dynamo architecture and cassandra.yaml.