Design a Distributed Key-Value Store

System Design Interview•~40 min read•hard

Design a distributed, highly available key-value store similar to DynamoDB or Cassandra. The system must support put(key, value) and get(key) across multiple storage nodes with configurable consistency, automatic data partitioning, and failure recovery.

1. Understand Requirements & Scope

Distributed KV stores partition data across nodes using Consistent Hashing, replicate each key across N nodes, and use quorum voting (R + W > N) for strong consistency or eventual consistency.

Functional Requirements:

put(key, value): store or update key-value pair.
get(key): retrieve value associated with key.
High availability and fault tolerance: survive node failures without data loss.
Horizontal scalability: scale storage and throughput by adding nodes.
Tunable consistency: support configurable R (read quorum) and W (write quorum).

2. Back-of-the-Envelope Capacity Estimation

• Key size: up to 256 bytes; value size: up to 1 MB.

• Low latency: p99 read and write under 10 ms within same datacenter.

• Handle network partitions (CAP theorem AP system with eventual consistency).

3. High-Level Architecture Flow

Dynamo-style decentralized architecture with Consistent Hashing ring and virtual nodes.

[ Client Read ]
       |
       v
[ Coordinator Node ] ---> (Queries R=2 Replicas in parallel)
       |
       +---> Node A: { value: "v2", timestamp: 1042 }  <-- Newest vector timestamp chosen!
       +---> Node B: { value: "v1", timestamp: 998 }   <-- Asynchronous Read Repair triggered!

Fig 1. Architecture data flow and component topology.

4. Production Implementation & Code

// Tunable Quorum Consistency Evaluation (R + W > N)
export interface QuorumConfig {
  N: number; // Total replicas across cluster
  W: number; // Write quorum size
  R: number; // Read quorum size
}

export function evaluateQuorum(config: QuorumConfig): { isStronglyConsistent: boolean; model: string } {
  const { N, W, R } = config;
  if (R + W > N) {
    return {
      isStronglyConsistent: true,
      model: `Strong Consistency: R(${R}) + W(${W}) > N(${N}) guarantees read/write quorum overlap.`
    };
  } else {
    return {
      isStronglyConsistent: false,
      model: `Eventual Consistency: R(${R}) + W(${W}) <= N(${N}) allows stale reads for high availability.`
    };
  }
}

Hardened Implementation Sequence

Consistent Hash Ring: Map key to ring position using hash(key). The first N distinct physical nodes clockwise from the key position store replicas.
Virtual Nodes (tokens): Each physical node owns V virtual positions on the ring to distribute data uniformly.
Write Path: Coordinator sends write to all N replicas. Waits for W ACKs before returning success. On local node: write to Commit Log (WAL) -> MemTable in RAM -> flush to SSTables on disk (LSM-Tree).
Read Path: Coordinator requests data from R replicas. Compares version timestamps/vector clocks. Returns most recent version and triggers read repair asynchronously.

5. Key Decisions & Operational Mitigations

Architectural Decisions & Trade-Offs

•R + W > N (Strong Consistency): At least one node in read quorum overlaps with write quorum, guaranteeing the latest value is read.
•W=1, R=1, N=3 (Eventual Consistency / Fast): Low latency and high availability, but high risk of reading stale data.
•Last-Write-Wins (LWW) vs Vector Clocks: LWW uses wall-clock timestamps (simple, but clock drift can overwrite valid concurrent writes). Vector Clocks preserve concurrent versions for client reconciliation, but add metadata size.

Operational Hazards & Mitigations

•Hinted Handoff: During node outage, neighboring nodes store writes tagged with a hint. When the node recovers, neighbors deliver the hinted writes.
•Anti-Entropy with Merkle Trees: Nodes compare hierarchical hash trees (Merkle Trees) of their key ranges. Only branches with differences are synchronized across the network, minimizing transfer bandwidth.
•Gossip Protocol failure detection: Nodes exchange heartbeats randomly with neighbors. If a node fails to heartbeat within timeout, consensus marks it down without central health monitor.

Interactive Knowledge Check • Question 1 of 3↓

Interactive Practice Quiz•Question 1 of 3

intermediate

Consistent Hashing: fundamentals

When is Consistent Hashing the right default for a production team?