Design a distributed key-value store (like DynamoDB)

Keys are hashed onto a ring. In the original Dynamo paper each physical node owns many virtual nodes (tokens), so load spreads evenly and a new node takes small slices from many peers rather than half of one neighbour. Modern systems such as DynamoDB and Cassandra-like stores often use explicit partitions instead: the key space is split into ranges of hashed keys, each partition is limited to around 10 GB (DynamoDB documents that a partition serves up to about 3,000 read units and 1,000 write units per second), and a partition is split when it grows too big or too hot. A controller then moves partitions to balance disk and traffic across nodes. Moving a 10 GB partition means: create a new replica, stream an SSTable snapshot, then tail the log until caught up, then switch the partition map version. Because routers cache the map, nodes must reject requests for partitions they no longer own with a 'wrong owner, epoch X' error, so routers refresh. Hashing keys spreads load but kills range scans across keys; DynamoDB offers a sort key inside a partition key to keep ordered data together, which is the right compromise.

With N replicas, writes wait for W acks and reads query R replicas. If R + W > N (e.g. N=3, W=2, R=2), every read set overlaps every write set, so a read sees the latest acknowledged write, assuming no failures move writes to other nodes. This is why N=3, W=2, R=2 is the classic choice; W=1, R=1 is fastest but only eventually consistent. Leaderless quorums (Dynamo, Cassandra) stay writable during failures using sloppy quorums: if a home replica is down, another node accepts the write with a hint. That boosts availability but breaks the R + W > N guarantee during the failure, a point many candidates miss. The alternative is a leader per partition chosen by Multi-Paxos or Raft (DynamoDB, Spanner, CockroachDB): writes go to the leader, are committed when a majority (2 of 3) has them in the log, and strongly consistent reads go to the leader. This gives linearizable per-key operations and simple conditional writes, at the cost of leader elections (a few seconds of unavailability for one partition) and leader hotspots. For a product that offers conditional writes and 'consistent read' options, the leader-based design is easier to make correct.

Each node needs fast writes and decent reads on NVMe. An LSM tree appends each write to a write-ahead log (sequential, fsync batched every few ms), inserts it into an in-memory sorted memtable, and when the memtable reaches ~64-128 MB flushes it to an immutable sorted SSTable. Reads check the memtable, then SSTables from newest to oldest; per-file Bloom filters (around 10 bits per key gives ~1% false positives) avoid touching files that cannot contain the key, and a block cache keeps hot blocks in memory. Background compaction merges SSTables, discarding overwritten versions and tombstones older than a grace period. Leveled compaction keeps read amplification low (good for read-heavy tables) at the cost of more write amplification; size-tiered compaction is cheaper for writes but uses more disk and more files per read. Deletes are tombstones: they must live long enough to reach all replicas, otherwise a replica that missed the delete can bring the data back during repair. B-trees (InnoDB, Postgres) are the alternative: better for read-heavy, in-place updates, worse for heavy random writes.

With leaderless replication, two clients can write the same key on different replicas during a partition. Options: last-write-wins using timestamps (simple; Cassandra does this; but clock skew can silently drop a newer write), or vector clocks that detect concurrent writes and return both siblings to the client to merge (the original Dynamo shopping cart). Vector clocks are correct but push complexity to every client, which is why most products avoid them. With a leader per partition, the leader assigns a monotonically increasing version per key, so there are no siblings, and conditional puts (expected_version) give safe read-modify-write. Recommend the leader design for a general-purpose product, and mention CRDTs (counters, sets) for the cases where merge semantics are natural.

Leaderless (Dynamo, Cassandra) gives always-writable behaviour and no election pauses, but conflict handling and weaker guarantees. Leader-based (DynamoDB today, Spanner, TiKV) gives strong per-key consistency and simple conditional writes, but a partition is briefly unavailable for writes during leader failover. Choose based on whether the product needs 'consistent read' and compare-and-set, which most do.

LSM trees turn random writes into sequential ones, compress well and handle heavy writes; they pay with read and write amplification and compaction tuning. B-trees give predictable reads and in-place updates but suffer under heavy random writes. A KV store for mixed, write-heavy workloads usually chooses LSM (RocksDB).

Hashing spreads load evenly and avoids hot ranges from sequential keys (timestamps), but loses ordered scans. Range partitioning (Bigtable, HBase, Spanner) supports scans but needs automatic splitting and can create hot spots for monotonic keys. A composite key (hash partition key + sorted sort key) gives most of both.

One key or one partition getting 50k ops/s exceeds a single replica set. Split hot partitions by key range, cache hot reads in front (DynamoDB Accelerator-style), and advise write sharding (append a random suffix to the key and aggregate on read) for counters.

Under heavy writes, compaction debt grows, reads touch more files and disk fills. Monitor pending compaction bytes, throttle writes (backpressure) when debt is too high, and add nodes before disks pass ~70%.

Gossip or the controller detects it in seconds. In a leader design, partitions it led elect new leaders among the 2 remaining replicas (still a majority). Hints accumulate for short outages; if the node is gone for good, the controller creates new replicas elsewhere from the healthy ones.

Each partition has one replica per AZ, so 2 of 3 replicas remain, which is still a majority for W=2 and leader election. Capacity drops by a third, so normal load must stay under ~65% of total to survive. When the AZ returns, replicas catch up via logs or Merkle-tree repair.

Bit rot or missed writes leave replicas different. Checksums on every block catch corruption on read, and periodic Merkle-tree anti-entropy finds and repairs differing key ranges without comparing every key.