Replication on the Ring

A ring that maps each key to ONE node loses data with every disk failure. Real stores keep each key on N distinct nodes (the replication factor, typically 3), and the ring gives a beautifully simple rule for choosing them — the preference list: start at the key's position, walk clockwise, and collect the first N distinct real nodes you meet.

Two details carry all the correctness:

Distinct means distinct real nodes. With vnodes, consecutive ring entries very often belong to the same machine — in our clustered toy ring the walk from hsum("foo") wraps to (148, A), then meets (149, A) before (149, B). Naively taking "the next two vnodes" replicates foo onto A twice, which protects against nothing. Dedupe by real node.

Bound the walk. If the caller asks for more replicas than there are nodes, you return every node — a while len(reps) < n loop with no exhaustion check spins forever.

This is the Dynamo model (Amazon's 2007 paper), the design Cassandra, Riak, and Voldemort inherited. The first node in the list is the key's coordinator/primary; the rest are its replica set. Writes go to all N (or enough of them); reads consult R of them; and the knobs obey one inequality: if R + W > N, every read quorum overlaps every write quorum in at least one node, so reads see the newest write — strong consistency. R + W <= N buys latency at the price of eventual consistency. Cassandra exposes this per request as consistency levels: ONE, QUORUM, ALL.

Production preference lists add one more filter we skip here: skip replicas that share a rack or availability zone with one already chosen (Cassandra's NetworkTopologyStrategy), so one power failure can't take out all three copies.

Your exercise

ADD_NODE builds the usual 5-vnode ring; REPLICATE <key> <n> prints the first n distinct real nodes clockwise from hsum(key), comma-joined, no spaces. The grader-caught mistakes: the dedupe — the visible test expects REPLICATE foo 2 to print exactly A,B; walking vnodes without deduplicating prints A,A (foo wraps to A's 148 and A's 149 comes before B's). The exhaustion bound — REPLICATE foo 5 on a three-node ring must print A,B,C and stop; an unbounded distinct-hunt never terminates and times out. And the ordering — replicas print in walk order, not sorted: a hidden four-node test expects n1,n2,n3 because that is the clockwise sequence of first encounters, and the single-node test expects only for both REPLICATE foo 1 and REPLICATE foo 3.