Skip to content

    System Design

    Consistent Hashing: Rings, Virtual Nodes, Rendezvous and Jump Hash

    Learn why hash mod n moves almost every key when a node is added, how a hash ring with virtual nodes fixes it, and when rendezvous or jump hash fits better.

    By Published 18 min read

    Share

    Flagship lessonintermediateJava labBackend System Design

    Before this: Sharding and Partitioning

    What you'll learn: By the end of this lesson you will be able to show why hash(key) mod n moves 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.

    A client library routes each key to the ring ownerApplication to Ring lookup (key); Ring lookup to Node A (if first point is A's); Ring lookup to Node B; Ring lookup to Node CPLACEMENT RULE (NO NETWORK CALL)STORAGE NODESApplication: calls get(key)Applicationcalls get(key)Ring lookup: hash, then first point clockwiseRing lookuphash, then firstpoint clockwiseNode ANode ANode BNode BNode CNode Ckeyif first point is A's

    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.

    sequenceDiagram accTitle: A node joins a ring accDescr: A new node announces its points on the ring. Each existing node whose arc is cut offers the affected keys. After the new node confirms, the keys are copied and the old owners stop serving them. participant X as New node X participant R as Ring membership participant O as Old owners of the cut arcs X->>R: announce my points on the ring R-->>O: arcs now owned by X O->>X: offer keys in those arcs X-->>O: confirm O->>X: transfer the keys Note over O,X: keys outside the cut arcs never move

    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.

    Replicas are the next distinct nodes clockwise, skipping repeatsKey to Node A (first point); Node A to Node B (next distinct); Node B to Node C (next distinct); Node A to A again (same node)REPLICA SET, N = 3 DISTINCT NODESKey: hashes to a ring positionKeyhashes to a ringpositionNode A: ownerNode AownerNode B: replica 2Node Breplica 2Node C: replica 3Node Creplica 3A again: another point of A, skippedA againanother point ofA, skippedfirst pointnext distinctnext distinctsame node

    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.

    flowchart TD accTitle: Choosing a placement rule accDescr: Start by asking whether nodes can leave in any order. If not and shards are numbered in order, jump hash fits. If nodes can leave in any order, ask whether the node count is small enough to hash every node per lookup. If yes, rendezvous hashing. If not, a ring with virtual nodes. Modulo only fits a node count that never changes. S["Placement rule needed"] --> Q0{"Does the node count ever change?"} Q0 -->|"never"| MOD["hash mod n is enough"] Q0 -->|"yes"| Q1{"Must any node be removable, or do shards only grow and shrink at the end?"} Q1 -->|"only the end"| JUMP["Jump hash: no memory, balanced, numbered buckets"] Q1 -->|"any node"| Q2{"Is one hash per node per lookup affordable?"} Q2 -->|"yes, tens of nodes"| RDV["Rendezvous hash: stateless, ordered fallbacks"] Q2 -->|"no, many nodes or very hot path"| RING["Ring with virtual nodes: tokens, arcs, ranges"]

    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).

    sequenceDiagram accTitle: A node fails and its keys move to the next owners accDescr: A cache node stops answering. Clients that have the updated node list route its keys to the next owners. Those owners miss and read from the database. Clients with an older node list keep sending those keys to the dead node and time out. participant C1 as Client with current list participant C2 as Client with old list participant D as Dead node participant N as Next owner participant DB as Database Note over D: stops answering C2->>D: get(key) with old list D--xC2: timeout C1->>N: get(key) after list update N->>DB: miss, read through DB-->>N: value N-->>C1: value

    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

    ShopStream product cache tier: modulo placement in the application serversApp servers to Cache node 1; App servers to Cache node 2; App servers to New node 11 (after the change); Cache node 2 to PostgreSQL (miss)App servers: mod n placementApp serversmod n placementCache node 1Cache node 1Cache node 2: ... up to 10Cache node 2... up to 10New node 11New node 11PostgreSQL: product cataloguePostgreSQLproduct catalogueafter the changemiss

    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 n placement 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 n balances well and moves almost every key when n changes: 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.

    Official documentation

    Ask about this article

    Get answers grounded in this post. AI-generated — based on this article, and may be imperfect.

    Scaled AI Weekly

    Enjoyed this? Get more like it every Monday.

    Real architecture decisions, LLMOps patterns that survive production, and engineering leadership advice — from 12+ years of building at enterprise scale. Free. No spam. Unsubscribe anytime.

    Get new articles by email

    Free. We email a confirmation link first, and you can unsubscribe from any email.

    Join engineers building production AI systems

    Comments