#3 Low-Latency Persistence
Key-Value Store (Dynamo-like)
A key-value store that stays writable through node and network failures, by spreading data across a ring of nodes and reconciling conflicts later.
What is being asked
Design a store with put(key, value) and get(key) that is always available for writes, scales by adding machines, and answers in a few milliseconds. This is the design behind Dynamo and Cassandra.
Requirements
Functional
- Get, put and delete by key; values are opaque blobs up to about a megabyte.
- Tunable consistency per request.
Non-functional
- No single point of failure; survives the loss of nodes and of a whole rack.
- Adding a node moves only a small share of the data.
- Low, predictable latency at the 99th percentile.
Design
- Partitioning. Keys are hashed onto a ring. Each node owns many small ranges (virtual nodes), so load spreads evenly and a new node takes a little from everyone.
- Replication. A key is stored on the next N nodes clockwise, placed in different racks.
- Quorums. A write succeeds after W replicas acknowledge; a read asks R replicas. With R + W > N, a read overlaps the latest write.
- Storage engine. Each node appends to a commit log and an in-memory table, flushed to immutable sorted files that are merged in the background (an LSM tree), which makes writes fast.
- Failure handling. If a replica is down, another node keeps a hint and delivers it later. Background anti-entropy with Merkle trees repairs replicas that drifted. Nodes learn of each other's state by gossip.
Key decisions and trade-offs
- Availability over consistency. Concurrent writes to one key can conflict. Options are last-write-wins by timestamp (simple, can lose an update) or version vectors that hand both versions to the application.
- Choosing N, R, W. N=3, R=2, W=2 is the usual balance. W=1 is faster and more available but may read stale data.
- Deletes are written as tombstones, since a missing key cannot be told apart from one not yet replicated; tombstones are removed after a grace period.
- Read cost. LSM reads may check several files; Bloom filters skip files that cannot contain the key.
Follow-up questions
- How does a read detect and fix a stale replica?
- What goes wrong if clocks differ between nodes under last-write-wins?
- How would you add range queries to a hash-partitioned store?
- How do you rebalance when one node is much larger than the rest?