Day 21 Exercises
Distributed KV Store Design
Apply consistent hashing, quorum reads/writes, and gossip protocol to real distributed storage challenges.
Consistent Hashing Ring Expansion
A distributed KV store has 4 nodes arranged in a consistent hash ring. You need to add a 5th node to handle growing traffic. The ring uses virtual nodes (150 vnodes per physical node).
Tasks
- Draw (describe) which key ranges move to the new node.
- Why do virtual nodes reduce the number of keys that need to move vs. a simple ring?
- What is the minimum fraction of keys that must migrate when adding 1 node to a 4-node ring?
- How do you perform this migration without downtime?
Quorum Tuning for a Social Network
Your distributed KV store has 5 replicas (N=5) for user profile data. Profiles are read 100× more than they're written. You need to choose R (read quorum) and W (write quorum).
Tasks
- Give the R/W values for a "write-optimized" configuration and explain the risk.
- Give the R/W values for "strong consistency" and its trade-off.
- What happens with R=1, W=5 during a network partition that isolates 2 nodes?
- Why does N=5 give you better failure tolerance than N=3?
Gossip Protocol Convergence
A 12-node cluster uses gossip to propagate health information. Each round, every node contacts 3 random peers and shares its full state. A node crashes at t=0.
Tasks
- After how many gossip rounds will the crash likely be known by all nodes? (Estimate using log base fanout.)
- What information does each gossip message contain? Design the message schema.
- How do you handle "zombie" nodes that appear alive but aren't responding to client requests?
- Describe "anti-entropy" and when you'd use it alongside gossip.
Sloppy Quorum and Hinted Handoff
Your DynamoDB-style store (N=3, R=2, W=2) serves a region where the network splits: nodes A and B can see each other, but not node C. A write comes in for a key owned by nodes A, B, C.
Tasks
- With strict quorum (W=2), can the write succeed? Why?
- With sloppy quorum: how does hinted handoff work? Which node stores the hint?
- When node C recovers, how does it receive the data it missed?
- Design the hinted handoff message format and the anti-entropy repair process.