Putting It All Together

Time to assemble the ring you've been building piece by piece into one structure with every feature switched on:

The capstone ring supports weighted adds (5 * weight vnodes), complete removal, primary lookup, and Dynamo-style replica walks — the same feature set as memcached's ketama ring (weights included) plus the replication rule Cassandra and Riak layer on top of theirs.

What separates this from a production ring is worth naming precisely: a real hash (MD5/Murmur3, not byte sums), persistence of ring state across restarts, rack/AZ-aware replica placement, streaming of data alongside ownership, and membership agreement between clients (gossip or a config service) — every client must build the same ring or they route to different owners.

And three modern variants replace the ring entirely when its trade-offs pinch; each gets its own lesson next:

• Jump consistent hash (Lamping & Veach 2014): zero memory, O(log N) expected time — not O(1) — but buckets must be numbered 0..N-1.
• Maglev (Google, NSDI 2016): O(1) lookups from a precomputed table, built for line-rate load balancers.
• Bounded-load (Mirrokni et al. 2016): the ring plus a hard per-node cap, killing hot-shard tail latency.

The classic ring with vnodes remains the right default: it handles named nodes, arbitrary add/remove, weights, and replication with one data structure.

Composition subtleties the grader checks

Removal must erase every vnode. A weight-2 node owns 10 tuples; REMOVE_NODE must delete them all (keep positions[name] so you know what to delete). One survivor is a ghost that still wins lookups.

Replication ignores weights. The replica walk dedupes by real node — a heavy node's extra vnodes make it the primary more often, but never twice in one preference list.

Dispatch must tolerate unknown input. One hidden test includes a stray KEYS ... line among the commands. The starter's if/elif chain simply falls through and prints nothing for it — keep that behavior; a strict parser that raises on unknown commands fails the test.

Your exercise

ADD_NODE <name> [weight] (default 1), REMOVE_NODE, LOOKUP (primary owner or NONE), REPLICATE <key> <n> (comma-joined, walk order). The grader-caught mistakes: ghost vnodes — the hidden test adds A, B, C, D, removes A, and expects LOOKUP foo -> B and REPLICATE foo 3 -> B,C,D; leave any A tuple behind and foo wraps to it, printing A and A,B,C. The weighted-removal variant — ADD_NODE a 2, ADD_NODE b 2, REMOVE_NODE a, LOOKUP key must print b, which requires deleting all ten of a's tuples. And the default weight — the visible test's bare ADD_NODE A must produce five vnodes, not zero and not a crash.