Consistent hashing with virtual nodes
Preference list (data replication)
- Key is replicated on M virtual nodes
- Similar to ‘r-successor’ in DHT
- All M virtual nodes are on distinct servers across different data centers
- M = 4
- Key 0’s preference list could be virtual nodes: {0, 1, 3, 5} mapping to servers {green, red, gold, blue}, including the coordinator server of key 0
Read and write requests
- Received by the coordinator
- Either the client knows the mapping or is re-routed to the coordinator
- This is not Chord
- Sent to the first N = 3 healthy servers in the preference list, including coordinator
- Durable writes: my updates are recorded on multiple servers
- Fast reads: possible to avoid straggler
- A write creates a new immutable version of the key instead of overwritting it
- Multi-versioned data store
- Quorum-based protocol: always send each operation to all N replicas
- A write is considered done if W out of N servers reply (write quorum)
- A read is considered done if R out of N servers reply (read quorum)
- W + R > N
Quorum Consensus implications (W, R, and N)
- N determines the durability of data (Dynamo N = 3)
- W and R plays around with the latency and consistency tradeoff
- W = 1 and R = 3: fast but less reliable write and slow read
- R = 1 and W = 3: slow but reliable write and fast read
- Dynamo: W = R = 2
- Why W + R > N => 2 + 2 > 4 ?
- Strong consistency is guaranteed because there must be at least one overlapping node that has the latest data to ensure consistency
An example of quorum reads and writes
A key is replicated on N = 3 nodes:
Replicas: A, B, C
Suppose:
W = 2 → a write succeeds after 2 replicas acknowledge it
R = 2 → a read collects responses from 2 replicas
Because W + R = 2 + 2 = 4 > N = 3, the write and read set must share at least one replica since there are only N = 3 replicas.
A write is stored on:
Write quorum: {A, B}
A later read could query any two replicas:
{A, B}
{A, C}
{B, C}
Every possible read quorum contains at least one node that received the write:
{A, B} overlaps at A and B
{A, C} overlaps at A
{B, C} overlaps at B
Therefore, the read always has access to at least one copy of the newly written value under no failure.
Failure Handling: sloppy quorum + hinted handoff
- Sloppy quorum: not always the same servers are used for N = 3
- First N servers in the prefererence list M are used without failures
- Later servers in the list take over if some of the first N fail
- Consequences
- Availability: no need to wait for failed servers to recover
- Provides Eventual Consistency: conflicts are possible, versions diverge during failiures
For example,
- Key 0’s preference list was {0, 1 ,3, 5}.
- Then, N = 3: {0, 1 ,3} servers are used if no failures
- If server 1 fails, requests go to {0, 3, 5}.
- First node in the list is the coordinator that receives requests from the client, and then the coordinator re-routes requests to the rest
Hinted handoff
- Node 5 was temporaily serving requests on behalf of Node 1
- Hinted that Node 1 is the original intended recipient
- Send replica back to node 1 when it is recovered
An example of conflicting writes (versions)
- Before CL2, A and B failed, thus writing item y to C and D
- After that, A and B are recovered
- CL1 read cart operation is sent to A and C
- If sent to A and B, item y won’t exist (eventual consistency)
- Since A and C reads conflict, we merge them using vector clock
- CL1 add item z creates a versioning to write z
Gossip: failure detection and ring membership
-
Server A considers B has failed if B doesn’t reply to A’s message
- Even if B replies to C
- A then tries alternative nodes
-
With servers join and leave
- Servers periodically send gossip messages to their neighbors to sync who are in the ring
- Some servers are chosen as seeds, i.e., common neighbors to all nodes
Conclusion
- Availbility is important
- Systems need to be scalable and reliable
- Dynamo is eventually consistent
- Many design decisions trade consistency for availability
- Core techniques:
- Consistent hashing: data paritioning
- Preference list, sloppy quorum, hinted handoff: handling transient failures
- Vector clocks: conflict resolution
- Gossip: ring membership