Virtual Nodes

One position per node makes a lopsided ring. N random positions cut the circle into N arcs of wildly unequal size — the expected largest arc is about ln(N)/N of the circle, several times the fair share, and some node inherits it. With three nodes it's routine for one to own well over half the keyspace.

The fix is statistical. Give each real node K positions instead of one: hash "{name}#0", "{name}#1", ... "{name}#K-1" and place all K virtual nodes (vnodes) on the ring, each mapping back to its real node. A real node's share is now the SUM of K small arcs, and sums of independent pieces concentrate: the relative spread of its total share shrinks like O(1/sqrt(K)). K=100 gets you within roughly 10% of perfectly fair. Production values: libketama places 160 points per memcached server; Cassandra historically used 256 tokens per node (newer releases default to 16 plus a smarter token allocator); Riak uses 64-256. Cost: 100 nodes x 200 vnodes is just 20,000 ring entries, and lookup is O(log(N*K)).

The idiom — store tuples, not a position-to-name dict:

Vnodes of different nodes can collide on one position — with our byte-sum hash they constantly do (hsum("A#1") == hsum("B#0") == 149). A position -> name dict silently clobbers one of the two, and the corruption surfaces later, when REMOVE_NODE deletes positions that partly belong to another node. Tuples keep both entries. Bisect with (hsum(key), ""): the empty string sorts before every real name, so a key that lands exactly on a vnode's position selects that vnode.

The honest caveat your own tests demonstrate

Vnode smoothing assumes the hash SCATTERS. Our hand-checkable byte sum does not: A#0..A#4 land on 148..152, B's vnodes on 149..153, C's on 150..154 — every vnode of every node crammed into one tiny cluster inside a 10,000-slot keyspace. Nearly every key hashes outside the cluster and wraps to the very first tuple, (148, A). That is why the hidden STATS test over ten keys prints A: 9 and E: 1: with a linear toy hash, vnodes buy you nothing, and node names one byte apart decide everything. Run the same code with MD5 or Murmur3 and it balances beautifully. Keep the two responsibilities straight: the ring ALGORITHM guarantees minimal key movement; only a well-mixing HASH delivers uniform load.

Your exercise

Five vnodes per node, hsum(s) = sum(s.encode()) % 10000, vnode position hsum(f"{name}#{v}") for v in 0..4. LOOKUP returns the owning REAL node; STATS prints <name>: <count> per owning node, sorted by name, omitting zero counts. The grader-caught mistakes: the boundary rule — hsum("k1") = 156 equals E's vnode E#4 exactly, so the five-node hidden test expects A: 9 then E: 1; a strictly-greater-than lookup (bisect_right) prints A: 10 and fails. The wrap — k2 through k10 hash above the highest vnode and must come back around to A. And removal — after REMOVE_NODE alpha, a hidden test expects LOOKUP key1 to print beta; all five alpha tuples must leave the ring, or beta never gets its keys.