Design a Key-Value Store (DynamoDB/Cassandra)

The Dynamo lineage: scale by trading away single-machine transactions

A distributed key-value store is the Dynamo-lineage system (DynamoDB, Cassandra, Riak) that gives you horizontal scale and no single point of failure by trading away single-machine transactions. The interview tests four internals: partitioning, replication and quorums, conflict resolution, and the write path (LSM).

Partitioning and quorums

Partitioning uses consistent hashing again. Keys map onto a ring, each node owns a range, and a replication factor N means each key is stored on the N nodes clockwise from its position (the preference list). Virtual nodes even out the load.

Replication and quorums are the heart. With N replicas, a write is acknowledged after W replicas confirm and a read waits for R replicas to respond. The tunable rule is: if R + W > N, a read quorum and a write quorum must overlap in at least one node, so a read is guaranteed to see the latest acknowledged write. Common settings: N=3, W=2, R=2 gives strong-ish reads with tolerance for one node down. W=1 is fast writes but risky; R=1 is fast reads that may be stale.

Interview nuance: the classic trap is claiming R + W > N gives linearizability. It does not. It guarantees you read a value at least as new as the last acknowledged write on the overlapping node, but concurrent writes, read-repair timing, and sloppy quorums (hinted handoff writing to fallback nodes) mean you can still see anomalies. Say "quorum overlap gives read-your-writes-ish freshness, not linearizability; for true linearizability you need consensus like Paxos or Raft."

Conflicts and reconciliation

Conflicts happen because two clients can write the same key on different replicas during a partition. Resolution options: last-write-wins (LWW) by timestamp is simple but silently drops one write and is vulnerable to clock skew. Vector clocks track causality so you can detect true concurrency and either merge or hand both versions (siblings) to the application. Cassandra uses LWW; Dynamo used vector clocks. Replicas that drift are reconciled two ways: read-repair (on a read, if replicas disagree, push the newest to the stale ones) and anti-entropy using Merkle trees (nodes exchange hash trees of their ranges and only sync the differing subtrees, avoiding a full scan).

The LSM write path

A write appends to a commit log for durability, then updates an in-memory sorted structure (memtable). When the memtable fills, it flushes to an immutable sorted file on disk (SSTable). Reads may check several SSTables, so a bloom filter per SSTable skips ones that cannot contain the key. Background compaction merges SSTables, drops tombstones (deletes), and keeps read amplification bounded. This design makes writes sequential and fast.

Membership uses gossip: nodes periodically exchange state so the cluster learns of joins and failures without a central coordinator. Hinted handoff keeps writes available during a brief node outage: a neighbor accepts the write with a hint and replays it when the owner returns.

write k=v -> coordinator -> replicas [N1,N2,N3]
   commit log -> memtable -> (flush) SSTable ; bloom filter per SSTable
   ack after W replicas ; read waits for R ; R+W>N overlaps

Recap: partition with consistent hashing and replication factor N, tune consistency with R + W > N (which is freshness, not linearizability), resolve conflicts with vector clocks or LWW plus read-repair and Merkle anti-entropy, and store writes in an LSM (commit log, memtable, SSTable, compaction).