Design a Distributed Key-Value Store (Dynamo-Style)

A Distributed Key-Value Store provides high-velocity, highly available, linearly scalable storage for unstructured data, inspired by Amazon's seminal 2007 Dynamo paper and Apache Cassandra.

Functional Requirements

1. Core Operations: put(key, value, context) and get(key).
2. Tunable Consistency: Configurable read and write consistency levels per operation (N, W, R).
3. Automatic Partitioning & Replication: Keys are partitioned uniformly across nodes with automated replication factor N.
4. Conflict Resolution: Support client-side vector clock reconciliation or Last-Write-Wins (LWW).

Non-Functional Requirements

• Always-Writable High Availability: 100% write availability even during datacenter network partitions (AP system in CAP theorem).
• Sub-10ms Latency: Single-digit millisecond p99 latency for reads and writes at millions of QPS.
• Decentralized & Masterless: Zero single point of failure (SPOF); all nodes have identical responsibilities.
• Linear Horizontal Scalability: Adding nodes increases cluster throughput and storage capacity linearly.

Amazon Dynamo solved each fundamental distributed systems problem using dedicated mathematical primitives:

Dynamo allows developers to tune the trade-off between consistency and latency on a per-request basis:

• N (Replication Factor): Number of distinct physical nodes storing a replica of the key (typically N = 3).
• W (Write Quorum): Number of replica nodes that must acknowledge a write before returning success.
• R (Read Quorum): Number of replica nodes that must respond to a read request before returning data.

Quorum Math & Consistency Guarantees:

1. Strong (Linearizable) Consistency (W + R > N):
   • Example: N = 3, W = 2, R = 2 \implies W + R = 4 > 3.
   • The Pigeonhole Principle: The read set and write set are mathematically guaranteed to overlap on at least one node containing the latest version.
2. Fast High-Availability Writes (W = 1, R = N):
   • Ultra-fast write latency (1 acknowledgment), but reads are slower.
3. Fast High-Availability Reads (W = N, R = 1):
   • Ultra-fast read latency (1 acknowledgment), ideal for read-heavy caches.

When network partitions occur, concurrent writes to different replicas can diverge. Dynamo captures causality using Vector Clocks:

• A Vector Clock is a list of [Node_ID, Counter] pairs (e.g., D_1 = [(S_a, 1)]).
• When Node B updates D_1, the clock becomes D_2 = [(S_a, 1), (S_b, 1)]. Because D_2 subsumes D_1, D_2 is a direct descendant (no conflict).
• If two concurrent writes occur independently:
  • Client 1 updates on Node B \implies D_3 = [(S_a, 1), (S_b, 2)]
  • Client 2 updates on Node C \implies D_4 = [(S_a, 1), (S_c, 1)]
• D_3 and D_4 are concurrent/divergent. When a client reads this key, the coordinator returns both sibling versions, and the client application reconciles them (e.g., merging shopping cart items) and writes back the resolved version.

1. Transient Failures: Sloppy Quorums & Hinted Handoff

• If Node 3 (a primary replica) is temporarily unreachable due to network glitch, the coordinator writes the payload to Node 4 with a metadata "Hint" (hint: deliver_to_node_3).
• Node 4 stores the hint locally in a separate staging queue.
• When Gossip indicates Node 3 is healthy again, Node 4 delivers the data back to Node 3.

2. Permanent Failure Recovery: Anti-Entropy with Merkle Trees

• If a node was offline for days (or hinted handoff dropped packets), replicas must synchronize divergent data without transferring gigabytes of identical records over the WAN.
• Merkle Tree: A hierarchical binary hash tree where leaf nodes represent hashes of individual key-values, and parent nodes are hashes of their children.
• Two nodes compare only the root hashes of their Merkle trees. If root hashes match, data is 100\% identical (O(1) verification). If roots differ, traverse children down the tree to isolate and sync only the specific mismatched key range.

Dynamo nodes do not use B-Trees (which require random disk writes). Instead, they employ an LSM-Tree for blazing sequential write speeds:

1. Write-Ahead Log (WAL): Write request appends to WAL on disk for crash durability.
2. MemTable: Data inserts into an in-memory sorted skip list (MemTable) in RAM. Write returns success immediately (< 0.5 ms).
3. SSTable Flush: When MemTable reaches capacity (e.g., 64 MB), it flushes sequentially to disk as an immutable SSTable (Sorted String Table).
4. Bloom Filter: Each SSTable has an in-memory Bloom filter to prevent disk seeks for non-existent keys during reads.
5. Compaction: Background threads merge and deduplicate multiple SSTables, purging tombstone markers (deleted keys).