Replication on the Ring

A ring that maps each key to one node loses data on every disk failure. In this lesson your ring will choose N distinct nodes for each key, which is how Dynamo-style stores keep a copy alive when a machine dies.

The preference list

Real stores keep each key on N distinct nodes (the replication factor, usually 3). The ring gives a simple rule for choosing them, called the preference list: start at the key's position, walk clockwise, and collect the first N distinct real nodes you meet. The first one is the key's primary (the node LOOKUP returns); the rest are its replicas.

Here is a ring of three nodes P, Q and R with three points each, listed clockwise:

P#1  Q#0  P#2  R#2  P#0  Q#2  R#1  Q#1  R#0

The key x5 hashes to a position just after Q#0, so the walk starts at P#2:

entry:    P#2   R#2   P#0   Q#2
node:      P     R     P     Q
action:   take  take  skip  take      -> replicas of x5 for N = 3: P, R, Q

Two details carry all the correctness

Distinct means distinct real nodes. With virtual nodes, consecutive ring entries often belong to the same machine, as P#2 and P#0 above. Taking "the next three entries" would give P, R, P and put two of the three copies on one machine, which protects against nothing. Skip any node you already have.

Bound the walk. If the caller asks for more replicas than the ring has nodes, return every node and stop. A loop that keeps walking until it has N distinct nodes never ends when there are fewer than N. Walk at most once around the ring.

The replicas are returned in walk order, not sorted. Walk order is what keeps the list stable: when membership changes, the list changes only where the change happened.

Where the guarantees come from

This is the Dynamo design (Amazon, 2007) that Cassandra, Riak and Voldemort inherited. A write goes to all N replicas (or enough of them) and a read consults R of them. If R + W > N, every read quorum overlaps every write quorum in at least one node, so a read sees the newest write. With R + W <= N you get lower latency and eventual consistency. Cassandra exposes this per request as the consistency levels ONE, QUORUM and ALL.

Production preference lists add one filter this course skips: skip replicas that share a rack or availability zone with one already chosen (Cassandra's NetworkTopologyStrategy), so one power failure cannot take out all three copies.

Common mistakes

• No dedupe. On a ring with 4 points per node, REPLICAS order:17 2 must print A,B. Walking raw entries prints A,A.
• An unbounded search. REPLICAS foo 5 on a three-node ring must print three names and stop, not hang.
• Sorting the result. B,C and C,B are different lists; the order is the order the walk met them.
• Starting at the wrong entry. The walk begins at the first point at or after the key, wrapping past the end of the ring, and the primary is the first node met.
• An empty ring. REPLICAS on a ring with no nodes prints NONE, not an empty line.

Your exercise

The ring is in the starter, with a configurable number of points per node. You write the preference list, and SPREAD, which checks how evenly replicas land across the nodes.