Weighted Ring

Real fleets are heterogeneous: this rack has 64 GB boxes, that one 128 GB; the new generation handles twice the QPS of the old. A uniform ring would hand every machine the same share and let the small ones fall over first. The fix costs one multiplication — give each node vnodes proportional to its capacity:

Twice the vnodes means twice the expected keyspace share. This one knob covers three production maneuvers:

• Mixed hardware: weight by RAM (caches) or by disk/CPU (stores). libketama does exactly this — each memcached server's point count is scaled by its share of total configured memory.
• Gradual decommission: step a node's weight 2 -> 1 -> 0 over hours. Each step drains a slice of its arcs to the survivors; traffic bleeds away smoothly instead of remapping in one spike. (The reverse — warming a new node in with a small weight — is the same trick.)
• Canary sizing: give unproven hardware weight 1 in a weight-4 fleet and watch it before trusting it with a full share.

Cassandra expresses the same idea through num_tokens: a node configured with more tokens owns proportionally more of the ring.

Weights are expectations, not contracts

Here is the visible test of this exercise: A with weight 1, B with weight 2, six keys — and the split comes out A: 3, B: 3. The double weight bought nothing. Why: B's ten vnodes occupy 149..158, A's five occupy 148..152; keys k1..k3 (156..158) land on B's high vnodes, while k4..k6 (159..161) sail past the top of the ring and wrap to A's 148. At this scale, who owns the wrap-around region matters more than who has more vnodes. That is the general small-sample rule from the vnodes lesson wearing a new hat: weighting converges to the configured ratio only with enough vnodes and a mixing hash. With 10 real nodes and 5*w vnodes each, expect the realized ratio to wander; with hundreds of nodes and 100+ vnodes each, it tracks the weights closely.

One more toy-hash artifact worth noticing: a weight-3 node generates suffixes #0..#14, and the two-digit suffixes carry an extra byte — big#0..big#9 sit at 389..398 but big#10..big#14 jump to 438..442. Even the byte sum's "scatter" is deterministic and checkable by hand.

Your exercise

ADD_NODE <name> [weight] inserts 5 * weight vnodes at hsum(f"{name}#{v}"); KEYS records the tracked set; STATS prints <name>: <count> per owning node, sorted by name, omitting zero counts. The grader-caught mistakes: the default — ADD_NODE A with no weight must mean weight 1; indexing parts[2] unconditionally is an IndexError, and weight 0 gives A no vnodes at all (the second visible test expects exactly A: 3). The omission rule — in that same test B owns nothing, and printing B: 0 fails string comparison; only owners appear. And the hidden n1 2 / n2 2 test expects n1: 4 alone: equal weights don't split keys evenly here (all four keys wrap to n1's lowest vnode), so don't "fix" your output to match intuition — match the ring.