Commentary: consistent-hashing

"Adding a node only reshuffles 1/N of the keys" is true on average and nearly useless per instance. Eight nodes, a perfectly good hash function, and one node holds 74× the keys of another. A study guide for hash_ring.py.

cd consistent-hashing
python3 demo.py            # the aha (§6) — about 5 seconds
python3 test_hash_ring.py  # pins every number this page claims

1. Orientation

This toy implements a hash ring — the routing layer under Dynamo, Cassandra, Riak, memcached client libraries, Envoy's ring_hash balancer, and most sharded caches you have ever used. Nodes get positions on a circle of 2³² slots; a key belongs to the first node position clockwise from the key's own position. Add a node and only the keys in the arc it cuts off change owner.

The sentence everyone knows about it is: "adding a node only reshuffles about 1/N of the keys." That sentence is true. It is also, taken as the lesson, close to useless — and this toy exists to show you why.

The demo measures the actual distribution instead of the average, and three things fall out:

• With one point per node, 8 nodes and a perfectly good hash function, the busiest node holds 4003 of 10,000 keys and the lightest holds 54. A 74× spread. At 32 nodes the lightest node holds one key.
• "About 1/N" is right on average and close to meaningless per instance. Over 100 possible 9th nodes, the fraction of keys that move ranges from 0.00% (a node that joined and got nothing at all) to 36.17% — against a fair share of 11.11%.
• Adding a 9th node to relieve the overloaded one leaves it completely untouched in 64 of 100 placements, because every moved key comes from a single donor arc, and it is usually somebody else's.

By the end you should be able to:

• work out, from a list of node names alone, which node is about to be your hot shard — before any traffic arrives;
• explain why more keys, a better hash function, and a wider hash space all fail to fix the imbalance, and say what the ceiling is;
• state what virtual nodes buy in one sentence that is not "they balance the load";
• read num_tokens in a Cassandra config and know what number you are choosing, and what it costs.

2. The problem this mechanism exists to solve

You have a lot of keys and a handful of servers, and you need a rule for which server holds which key. The rule must be computable by every client independently — a lookup table that all of them agree on is a distributed consensus problem you were trying to avoid.

The obvious rule is server = hash(key) % N. It is one line, it is perfectly balanced when the hash is uniform, and it has one catastrophic property: N appears in the formula. Change N and almost every key changes owner. Not some. Almost all:

The arithmetic behind 88.89%: a key keeps its home only if h % 9 == h % 8, which for a uniform h happens with probability 1/9. So 1 − 1/9 = 88.89% move, and the measured 89.06% is that with 10,000 samples of noise on it. For a cache, that is a total flush at the moment you were adding capacity to survive load. For a database, it is a full data migration.

So there are two goals, and they are in genuine tension:

• Minimal disruption. Changing the membership should move as few keys as possible — ideally the 1/(N+1) that the new node has to own by definition.
• Even load. Every node should own about 1/N of the keyspace, so you can provision them identically.

hash(key) % N gets the second perfectly and the first catastrophically. Consistent hashing is the design that gets the first almost perfectly — and the whole point of this toy is that the second does not come along for free, and the standard explanation quietly implies that it does.

3. Background you need

None of it is deep, but the argument below leans on all five rows.

The two that carry the result are the third and the fourth, and they are the same idea twice. A uniform hash function distributes points uniformly; it does not distribute the gaps between those points uniformly, and it is the gaps that are your shards. Everything a reader gets wrong about consistent hashing, they get wrong by silently substituting one for the other.

The arithmetic for row three, since it is the one doing the work: place N uniform points on a circle. The expected size of the largest gap is H_N/N, where H_N is the Nth harmonic number. For N = 8 that is 2.7179/8 = 33.97% of the ring — against a fair share of 12.50%. The biggest node is expected to be nearly 2.7× oversized by construction, before any bad luck at all.

4. The mental model

Before any code. Below is the real 3-node ring this toy builds — every percentage is ring_hash(label) / 2**32, printed by a scratch run against hash_ring.py, not drawn to make a point.

That picture is the entire toy. Two consequences follow from it, and only one of them is famous.

The famous one. Adding node3 inserts one new point. It steals the arc between its predecessor and itself, and nothing else in the picture changes. No key that wasn't in that arc has any reason to move. Compare % N, where the whole assignment is recomputed. This is the property the name refers to.

The one this toy is about. The arcs are 73.01%, 22.33% and 4.66%. They were never going to be 33.3% each. The hash spread the three points uniformly and that is all it promised; the gaps between uniform points are lopsided, and the gaps are the shards.

Virtual nodes attack exactly this. Instead of hashing node0, hash node0#0, node0#1, … node0#149 and give every one of those positions to node0. Below are both rings the demo builds, drawn 70 columns wide from their real points() output — each column shows the owner of the last ring point falling inside that 1/70th of the circle, and . means no point at all:

Watch what that does to node6 — the G that owned 39.75% of the ring on the top map. On the bottom map it owns 11.72% and is the lightest node. Nothing about node6 changed. Its old arc was never a property of node6 in the first place; it was a property of where its one neighbour happened to land.

It is worth knowing that this is not a later patch. Karger et al.'s 1997 paper specifies κ·log C points per bucket in the original construction, because the balance property it proves does not hold with one (§10). The one-point-per-node ring that §6 takes apart — the one in every tutorial diagram, including the one above — is a simplification introduced by the people explaining it, not by the people who invented it.

5. Reading the source

140 lines, one class. Read it in this order.

5.1 ring_hash — where the "randomness" comes from

def ring_hash(label):
    """Map a label onto the ring: SHA-1, keep the top 4 bytes as a big-endian
    unsigned int. Truncation is safe here because every bit of a SHA-1 digest
    is equally good; we just need 32 of them."""
    digest = hashlib.sha1(label.encode("utf-8")).digest()
    return int.from_bytes(digest[:4], "big")

There is no random import in this file and no seed anywhere. That is a deliberate and slightly unusual choice for a toy that is fundamentally about statistical behaviour, and it buys two things.

The first is the obvious one: every number on this page is reproducible on your machine, exactly, forever. You can check the 4003 yourself.

The second is the point of the toy. If the imbalance came from an RNG, the honest reading would be "well, that's just a bad seed." It doesn't. It comes from SHA-1, which is as close to a uniform function as this argument needs, and the imbalance is not a defect of it. So the first thing to check is whether SHA-1 is the culprit. I swapped the hash function and re-ran:

Every one of them is lopsided, and the "best" cryptographic hash in the list still puts 23× more keys on one node than another. max/fair — the number you actually provision for — sits between 2.28 and 3.20 for all five. Changing the hash function is not a fix, because the hash function was never the problem.

The truncation to 32 bits deserves a note, since it looks like a corner cut. I widened the ring and re-ran:

Byte-identical, and it has to be: two values that agree in their top 32 bits are the only case where the extra bits could change an ordering, and with 1200 points and 10,000 keys that never happens. The truncation costs nothing and makes every position printable as a readable percentage. What it does cost is collision headroom — see §7.1.

5.2 _labels — the one method that makes virtual nodes exist

    def _labels(self, node):
        """The labels whose hashes become this node's ring positions. The
        label, not the node name, is what gets hashed — that is the only
        reason one node can sit in many places."""
        return [f"{node}#{i}" for i in range(self.vnodes)]

One line, and it is the entire virtual-node feature. Everything else in the class is indifferent to how many positions a node has.

The # looks like it might matter — a naming scheme where one node's label could collide with another's would be a real bug. It does not otherwise matter, and I checked rather than assumed:

This is the shape of result the counterfactual step exists to produce. The exact digits are entirely a function of the separator — and the conclusion is completely insensitive to it. Every format gives max/fair between 2.19 and 3.20 at one point per node, and between 1.13 and 1.21 at 150. If you rerun this toy with : instead of # you will get different numbers and the same page.

The node names are equally irrelevant, which is worth knowing before you suspect node0..node7 of being rigged:

Real hostnames (10.0.0.1) do it. Single letters do it, harder. The best of the four still runs 17× between its lightest and heaviest node.

5.3 add — the ring is one sorted list

    def add(self, node):
        if node in self.nodes:
            raise ValueError(f"{node!r} is already on the ring")
        self.nodes.append(node)
        for label in self._labels(node):
            pos = ring_hash(label)
            i = bisect_right(self._points, pos)
            self._points.insert(i, pos)
            self._owners.insert(i, node)

Two parallel lists — positions and owners — kept in ring order, rather than a dict or a tree. Parallel arrays are usually a smell; here they are the right shape, because the hot path is a binary search over the positions and bisect wants a plain sorted sequence.

The insert is O(P) in the number of ring points (Python has to shift the tail), so building an 8×150 ring costs 1200 shifting inserts. That is fine here and would be fine in production too: membership changes are rare and route is not.

The property this buys is the one that makes consistent hashing usable at all, and it is easy to miss because nothing in the code announces it: the ring has no memory of the order operations happened in. A position is a pure function of its label, so two clients that learn about the same node set in different orders build byte-identical rings. I verified the round trip:

Removing node3 moves exactly the 164 keys node3 was holding (§6.1: that is its whole load), and putting it back restores the routing exactly. A node that reboots comes back to its own keys, not to a reshuffled cache.

5.4 route — the successor lookup, and the wrap

    def route(self, key):
        """The successor lookup: first ring position >= hash(key), wrapping
        past the top of the ring back to the first position."""
        if not self._points:
            raise ValueError("the ring is empty")
        i = bisect_left(self._points, ring_hash(key))
        if i == len(self._points):
            i = 0  # past the last point: wrap to the first
        return self._owners[i]

The hot path, and the only part of the algorithm most descriptions bother with. bisect_left returns the index of the first element >= x, which is the clockwise successor by definition.

The three-line wrap is what makes it a ring rather than a line. Without it, keys hashing above the highest node point have no successor and the lookup falls off the end of the array. Deleting it is not a subtle degradation:

147 keys in 10,000 — 1.5%, because the topmost node point sits at 98.7% of the ring. That is the shape of bug that passes every unit test written against small key sets and pages you at 3am. It is pinned by test_route_wraps_past_the_last_point (test_hash_ring.py lines 26–34), which asserts both the count and that all 147 land on the first owner.

By contrast, the choice of bisect_left over bisect_right — a key hashing exactly onto a node point going to that node rather than the next one — looks like the same class of decision and is not:

Zero keys. The tie needs a 32-bit collision between a key and a node label, and with 10,000 keys against 1200 points the expected number is about 0.003. The line is a correctness statement, not a behavioural one — worth getting right, not worth a paragraph claiming it decides anything.

5.5 arcs — the measurement that turns the result from luck into arithmetic

    def arcs(self):
        """Fraction of the ring's 2**32 slots each node owns. This is the
        thing that actually determines load; the key counts merely sample
        it. A point at p owns the half-open arc (previous point, p]."""
        share = {node: 0 for node in self.nodes}
        for i, pos in enumerate(self._points):
            if len(self._points) == 1:
                span = HASH_SPACE
            else:
                span = (pos - self._points[i - 1]) % HASH_SPACE
            share[self._owners[i]] += span
        return {node: span / HASH_SPACE for node, span in share.items()}

This method is not part of a hash ring. No production implementation has it, and routing never calls it. It is here because without it the headline number is an anecdote.

A distribution over 10,000 keys is a sample. Someone reading "node6 got 4003 keys" is entitled to ask whether that is the hash function being unlucky with this particular key set. arcs() answers by measuring the partition itself, in ring slots, with no keys involved at all — and §6.2 uses it to show the key count converging on the arc share. The claim stops being "we measured 4003" and becomes "node6 owns 39.75% of the ring, so it will hold 39.75% of any uniformly-hashed key set, and 4003/10000 = 40.03% is that."

Two details worth the ink. self._points[i - 1] at i = 0 indexes -1, which in Python is the last element — the wrap-around comes free, and the % HASH_SPACE turns the resulting negative difference into the correct distance round the circle. And the len == 1 branch exists because a one-point ring is the degenerate case where (pos - pos) % HASH_SPACE is 0 when the true answer is "everything."

5.6 balance — choosing which number to be scared by

def balance(counts):
    """Summarise a distribution: (min, max, max/fair-share, max/min).

    `fair` is what a perfectly even partition would give each node, so
    max/fair is "how much more than its share the busiest node holds" — the
    number an operator actually has to provision for."""
    values = list(counts.values())
    total = sum(values)
    fair = total / len(values)
    lo, hi = min(values), max(values)
    return lo, hi, hi / fair, (hi / lo if lo else float("inf"))

Two ratios, deliberately, because they tell different stories and the dramatic one is the less useful one.

max/min is the number that makes the demo shocking — 74× at 8 nodes, 1529× at 32. It is also unbounded and fragile: it is dominated by the emptiest node, and an empty node costs you nothing. At 32 nodes the lightest holds one key, and one more key would halve the ratio.

max/fair is the number you provision for. If every node is sized for 1/N of the keyspace and max/fair is 3.20, you need 3.2× that everywhere, or you accept that one node melts. It is bounded below by 1 and it is the honest headline. The demo prints both so you can watch them disagree about which configuration is worse: from 8 nodes to 32, max/min explodes from 74 to 1529 while max/fair moves from 3.20 to 4.89.

6. The demo, and what it proves

python3 demo.py

6.1 The imbalance, and where it comes from

Table 1b is the derivation. node6's ring arc is 39.75% of 2³² slots, and it holds 40.03% of the keys — the key count is sampling the arc, to within 0.28 percentage points. node5's arc is 0.52% and it holds 0.54%. Every row matches to two significant figures. Nothing here is luck about which keys were chosen; the partition was decided the moment the eight node names were hashed.

The headline ratio, derived: 4003 / 54 = 74.13. And max/fair: a fair share of 10,000 keys across 8 nodes is 1250, so 4003 / 1250 = 3.20.

One fairness check, because "we picked node names that produce a 39.75% arc" is a legitimate accusation. I generated 200 different 8-node name sets and measured the largest arc in each:

The measured mean, 34.92%, lands on the theoretical H₈/8 = 33.97% from §3. Our ring sits at roughly the 72nd percentile — mildly unlucky, not cherry-picked, and 55 of 200 randomly-named 8-node clusters are worse than the one on this page. The typical case is a node owning 2.8× its share; the bad case, which one cluster in two hundred draws, is 65.91% of the ring on one machine.

6.2 More keys will not fix it, and this is the surprising part

The instinct on seeing 4003-vs-54 is that 10,000 keys is a small sample and the law of large numbers will sort it out. Table 1c is that instinct being tested to a million keys:

max/fair does not fall. It converges, on 3.1799, and that number is 8 × 0.39748643 — eight times node6's arc share, computed in ring slots by arcs() with no keys involved.

6.3 The single join everyone quotes, and why it is a trap

Table 2, one point per node: adding a 9th node to an 8-node ring moved 19.76% of the keys, against a fair share of 11.11%. With 150 points per node it moved 11.08%. So far this looks like the familiar story — vnodes brought the number closer to fair.

Look at the last two columns instead:

With one point per node, every single one of the 1976 moved keys came out of node0. Not "mostly"; all of them, and test_vnodes_change_who_the_keys_come_from_not_how_many (test_hash_ring.py lines 74–90) asserts the donor Counter is exactly {"node0": 1976}. That is forced by the geometry: a new node with one point lands inside exactly one existing arc and takes the part of it that precedes the new point. One arc, one owner, one donor. It cannot be otherwise.

With 150 points, the new node lands in 150 different arcs, and at 8 existing nodes that is enough to hit all of them. The largest single donation drops from 1976 keys to 193. Same migration, spread over the whole cluster instead of falling on one machine — which, if the migration is real bytes over a real network, is the difference between a rolling operation and an outage on node0.

At 32 nodes the pattern is identical and sharper: 1 donor at one point per node, 31 of the 32 at 150.

6.4 "1/N of keys move" is a statement about a mean you get to draw once

Table 2 is one join. Table 3 is the same join tried with 100 different candidate node names — which is exactly what you are doing when you name a new server, whether you know it or not:

The means are 14.80% and 10.77%, against a fair share of 11.11%. Read only that column and virtual nodes look like a rounding correction — a 4-point improvement on a number that was roughly right already.

The ranges are the result:

• One point per node: [0.00%, 36.17%]. One candidate moved zero keys. Another moved 3617 — 3.3× its fair share, every one of them off a single machine. Even ignoring the zero, the second-smallest moved 34 keys, so the range still spans 106×. These outcomes differ only in what you typed into a config file.
• 150 points per node: [8.76%, 12.36%]. A 1.4× spread, and every outcome is within 12% of fair.

The inf in the max/min column is not a formatting bug. It is a division by an honest zero, and it is my favourite number in this toy:

newnode32 joined the cluster, was accepted by every client, appears in every routing table — and owns 0.002916% of the ring, which contains no keys. You bought a machine and it is serving nothing. Meanwhile all three of the biggest joins took their keys from node6, the 39.75% node, because a uniformly-placed new point is most likely to land in the biggest arc. That is the one genuinely encouraging fact in this section, and §6.5 is about how little it helps.

6.5 The shock: adding a node need not relieve the node that needed relieving

node6 holds 4003 keys and is your hot shard. You add a 9th node. Table 4 enumerates all 100 candidate names:

In 64 of 100 placements, node6's load is not reduced by a single key. Not reduced a little. Identical — 4003 before, 4003 after.

The mechanism is §6.3's, read backwards. With one point per node, a join has exactly one donor. If that donor is not node6, node6 is untouched. So the question "does adding capacity help my hot node?" reduces to "did the new point happen to land in the hot node's arc?", which happens with probability equal to the hot node's arc share — 39.75%. So the join misses node6 with probability 100% − 39.75% = 60.25%. Predicted 60.25 of 100 unchanged; measured 64. That is well inside the noise of 100 draws.

The counterfactual is the whole point of virtual nodes:

At 150 points per node, no placement leaves the busiest node untouched, because the newcomer lands in all 8 arcs and therefore necessarily takes some of the busiest one. Adding capacity does what you expected it to do. That guarantee — not the balance, not the movement count — is what you are buying.

The vnodes=1 "best placement" row is its own small horror: some candidate name existed that would have cut node6 from 4003 keys to 386, a 90% reduction, by landing just before it. The difference between that outcome and 64% of outcomes is a string.

Two facts that keep this from being worse than it is, both measured:

A join can be useless but never harmful — a new point only ever takes an arc, so no existing node's load can go up. And §5.3 showed removal is the exact inverse of addition, so a placement that did nothing can be undone for free.

6.6 It is not an artifact of small N

Eight nodes is a small cluster and it would be fair to suspect the whole effect of being a small-numbers illusion. Table 1 runs 32 nodes as well, and the effect gets worse:

At 32 nodes with one point each, the lightest node holds one key out of 10,000 while the heaviest holds 1529 — 4.89× its fair share of 312. This is H_N/N doing exactly what §3 said: H₃₂/32 = 4.058/32 = 12.7% of the ring for the expected largest arc, against a fair share of 3.1%, so the expected max/fair is 4.06. This ring's largest arc gives 4.75, and the 10,000-key count measures 4.89 on top of that. Since H_N grows with N, more nodes makes the relative imbalance worse, not better.

6.7 The tests

python3 test_hash_ring.py

Because there is no RNG, these can assert exact integers rather than bounds: ring_hash("key0") == 2914119475, counts["node5"] == 54, unchanged == 64. Every headline on this page is one of them. If a future edit changes the label format or the hash, the suite fails loudly instead of the page rotting quietly.

6.8 Where the effect vanishes

Worth naming precisely, because the demo is tuned to make the effect vivid and you should be able to tell whether it applies to you.

The imbalance vanishes with enough virtual nodes, and the rate is 1/sqrt(vnodes). Measured on arc shares alone, with no key sampling:

The rule of thumb 1 + 2.9/sqrt(vnodes) tracks the N=256 column to within 0.03 across three orders of magnitude, and is a safe upper bound for smaller clusters. Read it as: to halve your imbalance you must quadruple your virtual nodes. 150 buys you about 1.23×. Getting to 1.05× needs several thousand points per node, and §8 explains why nobody does that.

The disruption story vanishes at large N. Everything alarming in §6.4 and §6.5 is a statement about relative spread around a fair share of 1/(N+1). At 32 nodes the fair share is already only 3.03%, so even the worst placement moves a few percent of your data. The effect is loudest exactly where clusters are smallest — which is where most people first meet it, and where Cassandra's docs say vnodes matter most: they "make small clusters look larger."

It vanishes when keys per node gets small, in the other direction. At 256 nodes and 10,000 keys, each node's fair share is 39 keys, and key sampling noise dominates the arc variance so completely that no vnode count can help:

Only at a million keys does the measured 1.23 settle onto the arc-based 1.226 from the E5 table. Below that you are measuring your key set, not your ring.

And it vanishes if your load is not proportional to key count at all. The whole toy assumes every key is equally expensive. One celebrity key on the best-balanced ring in the world is still a hot shard, and no amount of vnode tuning touches it. That is what §7.4's bounded-load variant exists for.

7. Design decisions and roads not taken

7.1 No RNG, and a 32-bit ring

The usual way to write this toy is random.seed(42) and uniform positions. That would be simpler and it would have destroyed the argument, because the first honest question about a 74× spread is "is your randomness bad?" Deriving positions from SHA-1 makes the answer checkable rather than assertable, and CF1 in §5.1 checks it against five hash functions.

The cost is the 32-bit space, which is genuinely small: by the birthday bound, 1200 ring points in 2³² slots collide with probability about 1200²/2³³ ≈ 0.017%. Two node labels landing on the same integer would give one of them a zero-length arc — harmless here, because add uses bisect_right and both points simply coexist. Production rings use the full 128 or 160 bits, and CF2 showed the choice is invisible at this scale.

7.2 A sorted list and bisect, not a tree or a dict

A dict from position to node cannot answer "smallest key ≥ x", which is the only query the ring ever makes. A balanced BST or skip list can, and is what you would use if membership churned constantly, since it gets O(log P) insertion instead of the O(P) list shift.

For a ring, the list wins, and the reason is the read/write ratio. Memberships change on the order of once a week; routes happen millions of times a second. A flat sorted array is cache-friendly in a way no pointer-chasing tree is, and Python's bisect is C. Envoy, Ketama and most Go implementations all do the same thing.

7.3 vnodes is a ring-wide knob, so weighted nodes are out

Ring.__init__ takes one vnodes for the whole ring, and _labels gives every node the same count. Making it per-node would be a two-line change — and it is exactly how weighted consistent hashing works: a machine with twice the RAM gets twice the ring points and therefore twice the keys. Dynamo says this explicitly, that a node's virtual node count can be chosen "based on its capacity, accounting for heterogeneity."

It is left out because heterogeneous capacity is a second mechanism, and this toy has one. Add a weights dict and re-run demo.py if you want to see it.

7.4 Three alternatives that beat the ring, all absent on purpose

Naming these matters, because the ring's imbalance is a solved problem and a reader should not leave thinking otherwise.

• Rendezvous hashing (HRW). For each key, hash (key, node) for every node and take the highest. No ring, no vnodes, no positions — and much better balance, because it is not sampling a partition, it is scoring every node directly. It costs O(N) per lookup instead of O(log P), which is why the ring survived. GitHub's load balancer and Kafka use it.
• Jump consistent hash (Lamping and Veach, 2014). Zero storage, faster than a ring, and near-perfect distribution — with one crippling limitation: buckets must be numbered 0..N-1, so you can only remove the last node. Fine for sharding a fixed pool, useless when arbitrary machines die.
• Consistent hashing with bounded loads (Mirrokni, Thorup and Zadimoghaddam, 2016). Keep the ring, but cap each node at (1+ε)× the average and spill overflow to the next node clockwise. This attacks the imbalance directly rather than statistically, and it is the only one of the three that also handles unequal key weights.

All three are one mechanism each. Implementing any of them would have made this a survey, and a survey cannot make you feel the 64%.

7.5 No replication factor

A real ring does not stop at the first successor; it walks the next R-1 distinct nodes to place replicas. That single change makes the ring a replica placement mechanism, brings in preference lists, and is the thing that makes vnodes complicated in practice (Cassandra's token allocator exists because naive vnodes wreck replica diversity across racks).

It is out of scope on purpose — it is the subject of a separate toy. What this one teaches is the partition itself, and the partition has to be understood before the replication of it makes any sense.

8. What's simplified vs. the real thing

• Membership is a local variable. Ring lives in one process and knows the node list because you passed it in. The hard part of a real ring is that every client must agree on the membership, which means gossip (Cassandra, Riak), a coordination service (ZooKeeper, etcd), or a control plane (Envoy's EDS). While they disagree, two clients route the same key to different nodes — and for a cache that is a stale read, while for a store it is a split brain. The ring itself is 140 lines; the agreement about what goes into it is the actual system.
• Nothing moves. add() changes where a key routes, instantly and for free. In production it schedules a data migration: bytes read off node0 and written to the newcomer, throttled so it does not saturate the network, with reads served from the old owner until the handoff completes. §6.3's "one donor" is precisely why that matters — 1976 keys leaving a single machine is a very different operation from 193 leaving each of eight.
• Ring points are recomputed from scratch. Every Ring(...) re-hashes every label. Cassandra persists its tokens, because a node that comes back with different tokens owns different data and has to move all of it. The determinism that makes this toy reproducible is, in production, a durability requirement.
• Virtual nodes cost memory, which this toy never feels. 8 nodes × 150 vnodes is 1200 points; 1000 nodes × 256 is 256,000, and every client holds the whole structure. Gryski puts a 1000-node ring at around 4MB. This is the real reason nobody sets vnodes to 10,000 to chase §6.8's 1/sqrt(v) curve.
• Token placement is random here, and deterministic in modern systems. Cassandra 2.x picked random tokens, which is what _labels does, and needed num_tokens: 256 to stay balanced. Cassandra 3.x added an allocator that chooses tokens to balance the ring, which gets the same balance from far fewer tokens — the default is now 16. Read that as: the industry looked at §6.8's 1/sqrt(v) curve, decided the memory price was too high, and stopped sampling.
• All keys weigh the same. Load is key count. Real load is requests and bytes, both wildly skewed, and a perfectly balanced key distribution can still leave one node melting under one hot key. §7.4's bounded-load variant is the answer.
• No failure detection. remove() is a method somebody calls. Deciding that a node is actually down — rather than slow, partitioned, or garbage-collecting — is a whole separate mechanism, and getting it wrong triggers exactly the mass reshuffle the ring was built to avoid.

9. Check yourself

Answer before expanding. Every answer is derivable from the source, and each one was verified by running it.

        if i == len(self._points):
            i = 0

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Karger, Lehman, Leighton, Levine, Lewin, Panigrahy: Consistent Hashing and Random Trees (STOC '97) — the original. Worth reading for the framing alone: it is a paper about web caching hot spots, not about databases, and the ring is one third of it. It also settles a question this toy raises. The paper defines Balance as "with high probability the fraction of items mapped to each bucket is O(1/|V|)" — and it gets that only because, three paragraphs earlier, it says "we actually need to have more than one point in the unit interval associated with each bucket … we will need [κ] log C points for each bucket … each bucket is replicated [κ] log C times." Virtual nodes are not a later fix bolted on by Dynamo. They are in the 1997 construction, because the balance proof does not work without them. The single-point ring that §6 takes apart is a simplification made by everyone who has explained this since.
• DeCandia et al.: Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007) — §4.2 states this toy's aha in one sentence: "the random position assignment of each node on the ring leads to non-uniform data and load distribution," and introduces virtual nodes as the fix. Also the source of the capacity-weighted variant from §7.3.
• Cassandra: Dynamo — virtual nodes and token allocation — the operational counterpart. Explains why 2.x needed num_tokens: 256 with random tokens, and what the deterministic allocator in 3.x changed. The line "make small clusters look larger" is §6.8's boundary condition in five words. The cassandra.yaml reference is where the current num_tokens default of 16 lives — the §8 claim that the industry stopped sampling, in one config line.
• Damian Gryski: Consistent Hashing — Algorithmic Tradeoffs — the best single survey of the alternatives named in §7.4: ring hashing, jump hash, multi-probe, rendezvous and Maglev, with the memory and lookup costs of each. The ~4MB-per-1000-node figure in §8 comes from here.
• Google Research: Consistent Hashing with Bounded Loads — the readable write-up of Mirrokni, Thorup and Zadimoghaddam (arXiv:1608.01350), which caps each node at (1+ε) of the mean and spills the rest clockwise. The direct attack on the problem this toy measures statistically.
• Lamping and Veach: A Fast, Minimal Memory, Consistent Hash Algorithm — jump consistent hash, five lines of code, zero storage, near-perfect balance, and the sequential-bucket limitation that keeps it out of general use. Read the code in the abstract before the proof.
• Wikipedia: Rendezvous hashing — the O(N)-lookup alternative that sidesteps arcs entirely by scoring every node per key. Note the claim that it is "now being preferred to consistent hashing in real-world applications" — this toy is a decent explanation of why.
• Wikipedia: Consistent hashing — the canonical statement of the folk claim, in its own words: "the addition of a nth server only causes 1/n fraction of the BLOBs to relocate." True on average. §6.4 is what that sentence leaves out.

Elsewhere in this repo, bloom-filter is the other toy where a uniform hash function produces a result nobody predicts correctly — and where, as here, the fix is "use more independent hashes."