A distributed key-value store

1 · Clarifying questions

2 · Capacity math, on a napkin

32 nodes is enough for 4 TB at this load with comfortable headroom. The choice scales linearly with virtual nodes (vnodes) — at 256 vnodes per physical, we can grow to 256 nodes without re-hashing.

3 · API and data model

Endpoints

PUT /v1/keys/{key} # write
 Body: raw bytes, ≤ 1 MB
 Headers: X-Quorum-W: 2 # require 2 acks
 X-Vector-Clock: <ctx> # optional, returned on prior get
→ 200 {"vc": "<ctx>"} # opaque vector clock context
→ 409 {"siblings": [...]} # if conflict and W met but quorum split

GET /v1/keys/{key} # read
 Headers: X-Quorum-R: 2 # require 2 replicas
→ 200 {"value": <bytes>, "vc": "<ctx>"}
→ 200 {"siblings": [{value, vc}, ...]} # caller resolves
→ 404 {"vc": "<tombstone-ctx>"}

DELETE /v1/keys/{key} # tombstone, GC after grace period
→ 200

The API exposes the consistency knobs (R, W) per call. Most product code calls with R=2, W=2, N=3 — the Dynamo defaults. Strong-read code calls R=3 (read quorum equals replica count).

On-disk layout, per node

Storage engine: RocksDB (LSM, native-code, well-instrumented)

key bucket value
─────── ─────
md5(user-key) → vnode -> SST files (sorted by key, compacted in tiers)

Per record:
 key (≤ 256 B)
 value (≤ 1 MB)
 vector_clock (~8 B per actor, ~64 B typical)
 timestamp (8 B, last-write tiebreaker)
 tombstone_flag (1 B)

4 · High-level architecture

A coordinator (any node) hashes the key into the ring and forwards the request to the N replicas. Each node is identical software; the differences are which vnodes they own, what's in their hint queue, and what the gossip layer has told them about peers.

5 · The hard part — placement, replication, quorum

Consistent hashing with vnodes

Consistent hashing puts each node and each key on a ring. A key belongs to the next N nodes clockwise from its hash. Vnodes — many tokens per physical node — even out the load and make rebalancing cheap.

Sloppy quorum: R + W > N

Each request specifies how many replicas must ack — R for reads, W for writes — against the N replicas. The classic settings:

"Sloppy" means the W replicas don't have to be the canonical N — if a primary is down, a substitute (next clockwise) accepts the write and adds a hint. This improves availability under partial failure at the cost of a brief inconsistency window.

6 · Vector clocks and conflict resolution

Concurrent writes can produce siblings — values that neither dominates the other in the partial order. Vector clocks track causality so the system knows when this has happened.

Time: T0 T1 T2 T3
Alice writes A, Bob writes B,
both see {} sees {Alice:1} Coordinator merge — concurrent: siblings

VC(A) = {Alice:1}
VC(B) = {Bob:1, Alice:1} Bob saw Alice's prior write — B dominates A
VC(B) = {Bob:1} Bob did NOT see A — concurrent → siblings

On read:
 if exactly one value has the maximal VC → return it.
 else → return ALL siblings; client resolves and writes back with combined VC.

In production, the VC for a key with N=3 has at most a few entries (one per frequently-writing actor). Garbage-collect entries past a depth bound to keep the VC small.

7 · Hinted handoff and anti-entropy

Hinted handoff (short-term)

A node can't reach replica N5 for key k. The coordinator picks a substitute (N6), which durably stores the write plus a hint: "this belongs to N5; deliver when you can". When N5 returns, N6 hands the data over and deletes the hint.

Bounded by hint-queue size. If the queue overflows, the system falls back to anti-entropy. The hint queue itself is durable — a node restarting must not lose pending handoffs.

Anti-entropy with Merkle trees (long-term)

Periodically, replica peers compare Merkle trees of their key ranges. Differing subtrees are walked top-down until the divergent keys are isolated, then the missing values are pulled. This catches:

• Hint-queue overflows that dropped writes.
• Bit-rot or silent corruption.
• Replicas that fell behind during long partitions.

Tune the comparison cadence (every N hours per range) and the leaf granularity (rows vs. blocks). Too frequent → wasted bandwidth. Too sparse → recovery is slow.

8 · Membership and gossip

Nodes join, leave, and crash. The cluster needs an eventually-consistent view of membership without a coordinator. Gossip — each node periodically picks a random peer, exchanges versioned membership state, picks the higher version — converges in O(log N) rounds.

φ-accrual is more nuanced than a fixed timeout: it computes a confidence score that the peer is dead, accommodating noisy networks. A node with phi above ~8 is marked suspect; above ~15, dead.

9 · Failure modes & runbook

10 · Cost & SLOs

SLOs

• Read availability: 99.999%. 5 minutes/year. Multi-AZ + region failover make this achievable.
• Write availability: 99.99%. ~52 min/year. Slightly tighter because writes need quorum.
• Read P99 in-region: 10 ms. Three replicas, network + RocksDB miss is the worst case.
• Write P99 in-region: 50 ms. W=2 acks; the slowest of the two.
• Eventual-consistency window: P99 ≤ 1 s in-region, ≤ 10 s cross-region. Tracked via injected probe writes.

11 · Trade-offs & "what would you change at 10×"

Further reading

• DeCandia et al — "Dynamo: Amazon's Highly Available Key-value Store" (2007). The paper. Read it. Twice. The architectural blueprint for everything in this design.
• Lakshman & Malik — "Cassandra: A Decentralized Structured Storage System" (2010). Dynamo + Bigtable's row model. The most-deployed Dynamo descendant.
• Hayashibara et al — "The φ Accrual Failure Detector" (2004). The math behind the failure detector mentioned above. ~10 pages.
• Shapiro et al — "A comprehensive study of CRDTs" (2011). The other route to conflict-free replication. Useful contrast with vector clocks.
• Brewer — "Pushing the CAP" (2012). A decade after CAP, the tradeoff in production language. Worth re-reading before any design with quorum in it.
• Adjacent: Replication. The theoretical foundation of this section.
• Adjacent: Consistent hashing. The placement scheme, with diagrams.
• Adjacent: Vector clocks. A standalone walkthrough.