Design a Key-Value Store: System Design Interview 2026

Amazon's 2007 Dynamo paper is a useful case study for workloads that value high write availability and can reconcile conflicting object versions. It is not a universal template for sessions, counters, or every key-value API. This walkthrough studies its combination of partitioning, quorum-like reads and writes, sloppy quorum, version vectors, hinted handoff, and anti-entropy - then marks the assumptions under which each mechanism works.

This walkthrough assumes the 6-step system design framework and applies it at senior-plus depth. It is Part 14 of an extended system design series.

Table of Contents

1. The Problem
2. Step 1 - Clarify Requirements
3. Step 2 - Estimate Scale
4. Step 3 - API and Data Model
5. Step 4 - High-Level Design
6. Step 5 - Deep Dive: Tunable Quorum, Vector Clocks, and Anti-Entropy
7. Step 6 - Bottlenecks and Trade-offs
8. Reference Architecture
9. Common Mistakes in the Interview
10. Quick Reference
11. Frequently Asked Questions
12. Sources
13. Related Articles

The Problem

We are designing a distributed key-value store with a deliberately narrow contract - get, put, and delete by key - and Dynamo-style application-visible versioning. The default path favours availability and eventual convergence. We do not claim that every node can accept every write in every partition or that changing R and W alone produces linearizability.

Under a network partition, the design is willing to accept writes on a reachable side when its configured sloppy-write requirement can be met, even though another side may accept a concurrent version. That is the availability choice in CAP's partition scenario. Finite capacity, overload, authentication, unavailable fallback nodes, or an unsatisfied W can still reject a request. The contract is “highly available within declared failure assumptions”, not “never refuses”.

Step 1 - Clarify Requirements

Functional requirements:

• get, put, and delete by primary key.
• Configurable read and write response thresholds, exposed as named consistency profiles or explicit R/W only if the product can support that API safely.
• No transactions across keys, no joins, no secondary indexes. The narrow contract is the design.

Out of scope (name, then defer): SQL-style transactions, range scans across arbitrary keys, and secondary indexes. Systems influenced by Dynamo may add different contracts; this case study does not.

Non-functional requirements:

• High write availability for the declared node, rack, and partition failures.
• Horizontal scale to the scenario target: billions of keys and hundreds of nodes.
• Measured latency SLOs per operation and consistency profile.
• Durability stated separately from availability, with placement across failure domains.
• Eventual convergence plus explicit conflict, delete, repair, and metadata-retention policies.

The decisive questions are more concrete than “AP or CP”: which clients may write during which partition, what counts as a successful write, when must a later read observe it, how are concurrent versions resolved, and how long can repair lag? If a subset of operations needs linearizable compare-and-set, design a separate consensus-backed path instead of relabelling quorum intersection as strong consistency.

Step 2 - Estimate Scale

Treat these as candidate assumptions, then benchmark encoded records and the storage engine.

Data. 100 billion values at 1 KB is about 100 TB decimal before keys, version metadata, indexes, logs, tombstones, compaction amplification, and free-space headroom. Three replicas make the value payload about 300 TB. At 10 TB of usable capacity per node that payload alone needs 30 nodes, not 100; the physical cluster count comes only after applying measured overhead, target occupancy, failure-domain placement, repair headroom, and throughput constraints.

Throughput. Peak around 1 million reads/sec and 100,000 writes/sec - the read-write ratio is firmly read-heavy, but every write fans out to W replicas.

Latency budget. Define separate p99 targets for read and write profiles. R = 1 often waits for fewer responses than R = 3, but tail latency also depends on coordinator placement, speculative requests, reconciliation, payload size, overload, and network topology; a universal 50 ms promise is not justified by quorum numbers.

The defining shape is large partitioned state and multiple replicas per key. The placement policy may be rack-local, region-local, or multi-region; it must match the latency, durability, and partition semantics established above.

Step 3 - API and Data Model

The API is intentionally tiny and surfaces the quorum knobs:

get(key, R)              -> value(s) + context
put(key, value, context, W, requestId)
delete(key, context, W, requestId)  // writes a versioned tombstone

The context lets a client say which versions its update descends from. Omitting or truncating it may intentionally create a concurrent sibling. requestId handles an ambiguous retry separately; causal context alone does not prove that a replay is the same logical command. Deletes need versioned tombstones retained until repair and garbage-collection safety conditions are satisfied, otherwise an old replica can resurrect deleted data.

Step 4 - High-Level Design

flowchart TD
    Client([Client]) -->|get/put| Coord[Coordinator<br/>any node]
    Coord -->|hash key -> ring| Ring[(Consistent Hash Ring)]
    Ring -->|preference list of N nodes| R1[(Replica 1)]
    Ring -->|preference list of N nodes| R2[(Replica 2)]
    Ring -->|preference list of N nodes| R3[(Replica 3)]
    Coord -->|forward request| R1
    Coord -->|forward request| R2
    Coord -->|forward request| R3
    Coord -->|"wait for W (writes) or R (reads) acks"| Client
    Hint[Hinted Handoff Node]
    R1 -.target down.-> Hint
    AE[Anti-Entropy / Merkle] -.background.-> R1
    AE -.background.-> R2
    AE -.background.-> R3
    Gossip[Gossip Membership] -.cluster view.-> Coord

Figure 1. A simplified 2007 Dynamo-style topology. A request coordinator uses a versioned membership and placement view to choose a preference list. Hinted handoff and anti-entropy repair address different failure windows; neither replaces the other.

In the case-study design, a consistent-hash ring and failure-domain-aware preference list map a key to intended replicas. A coordinator sends requests in parallel and waits for the configured response threshold, while a versioned membership view prevents arbitrary routing disagreement. Hints shorten some outages; scheduled anti-entropy provides durable convergence. Modern products may use different placement, metadata, consensus, conflict-resolution, and repair mechanisms, so do not infer their guarantees from the Dynamo name.

Step 5 - Deep Dive: Tunable Quorum, Vector Clocks, and Anti-Entropy

This is the core. Five mechanisms cooperate: partitioning plus replication, response thresholds, version vectors for conflict detection, sloppy quorum with hinted handoff for higher write availability, and Merkle-tree anti-entropy for background repair.

Part A - Partition and replication

The ring partitions the key space into many tokens, and a failure-domain-aware preference list chooses N intended replicas for each key. Virtual nodes are one balancing technique, not a guarantee: token ownership, node capacity, key distribution, hot keys, topology changes, and repair cost still need measurement. Use N = 3 only as the running example.

Choosing distinct physical nodes and failure domains reduces correlated loss. Whether a rack failure loses an acknowledged write also depends on W, which replicas acknowledged, hint durability, placement constraints, and simultaneous failures. Consistent hashing alone supplies none of those guarantees.

Part B - Tunable quorum and R + W > N

For each request the client (or system) chooses R and W independently from N:

flowchart LR
    subgraph Cfg["N = 3 - common configurations"]
        direction TB
        S1["W=2, R=2: R+W=4 > 3"] --> Strong["Fixed-set quorum intersection"]
        S2["W=1, R=1: R+W=2 (less than 3)"] --> Eventual["Eventual: fastest, may read stale"]
        S3["W=3, R=1: R+W=4 > 3"] --> WriteHeavy["All intended write replicas; one read"]
        S4["W=1, R=3: R+W=4 > 3"] --> ReadHeavy["One write acknowledgement; all intended reads"]
    end

Figure 2. Response thresholds for N = 3. R + W > N proves set intersection only when both operations use the same fixed replica set. The application still needs a version ordering and clearly stated behavior for concurrency, failed writes, sloppy fallback, and membership change.

For a successful write and later read over the same fixed N intended replicas, R + W > N forces at least one overlapping replica. If the coordinator receives and reconciles a causally newer version from that overlap, the completed write can be visible to that read. The arithmetic alone does not order concurrent writes, turn a failed partial write into a completed one, fence an old placement epoch, or guarantee overlap when sloppy operations used different fallback nodes. It is not a proof of linearizability.

Higher W usually waits for more write acknowledgements and reduces availability under failure; higher R waits for more read responses and has more versions to reconcile. Low thresholds can reduce latency while increasing stale-read and durability risk. Expose named profiles unless callers can reason about topology and failure semantics; raw per-request integers are easy to misuse.

Part C - Vector clocks and sibling resolution

Without coordination on every write, two replicas can accept writes to the same key concurrently and produce conflicting versions. The store must be able to tell which case it is in:

1. One version happened after the other - keep the later one.
2. The versions happened concurrently - neither is more authoritative.

A version vector records a counter for each logical actor represented in the version metadata. The 2007 Dynamo design used coordinator nodes as actors and returned the context to clients. Comparing two vectors:

• If A's entries are all >= B's, and at least one is strictly greater, A descends from B - B is obsolete for this object history.
• Otherwise the writes are concurrent; both versions are kept as siblings, and a subsequent read returns both. The client merges them per its domain - the canonical example is a shopping cart whose merge is the union of items.

sequenceDiagram
    participant C1 as Client 1
    participant C2 as Client 2
    participant N1 as Node A
    participant N2 as Node B
 
    Note over N1,N2: clock for key K starts: {}
    C1->>N1: put K = "cart with [book]"
    N1-->>C1: ok, clock {A:1}
    Note over N1,N2: network partition - replicas diverge
    C2->>N2: put K = "cart with [pen]" (saw {})
    N2-->>C2: ok, clock {B:1}
    Note over N1,N2: partition heals
    C1->>N1: get K
    N1->>N2: read replica K
    N2-->>N1: "cart with [pen]" @ {B:1}
    N1-->>C1: SIBLINGS: ["cart with [book]" @ {A:1}, "cart with [pen]" @ {B:1}]
    Note over C1: merge by union -> "cart with [book, pen]"
    C1->>N1: put K = "cart with [book, pen]" (context: {A:1, B:1})
    N1-->>C1: ok, clock {A:2, B:1}

Figure 3. A simplified version-vector example. Neither concurrent vector dominates, so both versions survive until a domain-aware write descends from both. Real systems must bound actor metadata and define what truncation does to causality.

Version vectors detect concurrency; they do not decide the business merge. A shopping-cart union preserves concurrent additions but can resurrect removals, so real cart semantics often track operations or item identities more carefully. Last-write-wins is simpler but may discard a concurrent update and depends on its ordering rule. Other choices include a leader with conditional writes, CRDTs, domain-specific merge, or rejecting unresolved concurrency. Also budget metadata growth: actor selection, pruning, and context truncation can make some causal relationships indistinguishable.

Part D - Sloppy quorum and hinted handoff

A strict quorum fails when fewer than W intended replicas acknowledge. A Dynamo-style sloppy quorum may use reachable fallback nodes from the wider preference list. A fallback stores a hint naming the intended owner; after successful handoff it can remove the temporary copy according to retention policy.

The trade-off is explicit: a later read restricted to the intended N replicas may miss a successful sloppy write, so coordinators need a consistent preference-list policy and may contact fallback holders. Sloppy quorum increases availability only while enough healthy fallback capacity and network paths remain. Hints are temporary and can expire or be lost; they reduce inconsistency duration but do not replace anti-entropy repair.

Part E - Merkle-tree anti-entropy

Replicas drift because writes, deletes, or hints are missed. Anti-entropy compares corresponding token ranges using Merkle trees so it can localise differing subranges before streaming versions:

• Matching roots give hash-based evidence that the same range snapshots agree, subject to the hash and tree construction.
• Differing roots prompt recursion into the differing subtrees.
• Only the genuinely differing leaves are exchanged.

Only mismatched ranges need value-level comparison, but building trees and scanning, hashing, and streaming data still consume disk, CPU, memory, and network. Token changes can invalidate trees, and a mismatch says nothing about which version should win. Schedule and observe repair; do not describe it as free or automatically proportional only to divergent keys. End-to-end checksums and replication policy are also needed to reason about corruption.

Consistency model

The model prioritises high availability and eventual convergence under repair assumptions. R and W tune how many responses are required. Fixed-set quorum intersection can provide useful visibility guarantees, but sloppy fallback, concurrent writers, changing membership, failed partial writes, and conflict policy define the actual semantics. The system may reject writes when it cannot meet W, is overloaded, lacks durable capacity, or intentionally protects a tenant or failure domain.

This is one design point, not the automatic opposite of a payment system. A product may use eventual reads for catalog data and a consensus-backed conditional path for reservations in the same architecture. State guarantees per operation and failure mode.

Failure modes

• Single-node failure. A write can use fallback capacity if W is still achievable; hints and later repair restore intended placement. Reads must follow the same expanded preference-list rules to find recent sloppy writes.
• Network partition. A side accepts a write only if its reachable set satisfies the configured policy. If multiple sides accept concurrent versions, version comparison surfaces or resolves them after communication returns.
• Rack failure. Failure-domain-aware placement preserves only the replicas outside that rack; acknowledged-write durability depends on which domains acknowledged and what else failed.
• Coordinator failure mid-request. The result may be unknown even if some replicas stored it. Retry with the same request ID and causal context; a version vector alone is not an idempotency key.
• Corruption or operator error. Checksums and anti-entropy can reveal disagreement, but automatic repair needs a trusted version/majority or backup; copying the wrong replica is still possible.
• Delete resurrection. Retain tombstones until all relevant replicas are repaired and the garbage-collection safety window has passed.

Multi-region

Choose multi-region semantics from the product's latency, RPO, residency, and partition requirements. Region-local replica sets with asynchronous multi-active replication favour local latency but need cross-region conflict handling and accept lag. Synchronous cross-region writes trade availability and latency for a stronger acknowledgement boundary. Some modern services expose multi-region strong modes; therefore “keep N local” is an option, not a universal rule. Document where R/W are counted and which regions may accept writes during a WAN partition.

Evolution path

Do not expose R/W or siblings from day one unless they are truly part of the product contract. A managed or open-source store with suitable conditional writes, repair, topology, and consistency profiles is usually safer than recreating the 2007 architecture. What is hard to retrofit is an undefined contract: stable request IDs, delete semantics, conflict ownership, and measurable recovery guarantees should be explicit early.

Observability

Track latency and errors by operation and consistency profile, successful and timed-out acknowledgements, unknown write outcomes, hint age/bytes/drop rate, sibling creation and merge failures, tombstone age, repair coverage/age/streaming load, checksum mismatches, ownership-epoch disagreement, hot partitions, rebalancing, capacity headroom, and membership convergence. Sample or protect key dimensions so observability does not leak tenant keys or create unbounded cardinality.

Step 6 - Bottlenecks and Trade-offs

• Latency, availability, durability, and visibility all move with R/W; quorum intersection is not synonymous with linearizability.
• Hot keys are a Part 4 problem unchanged - the per-key load is on the preference list, regardless of quorum maths.
• Sibling resolution shifts domain work to a client or service; version metadata can grow, and LWW may discard valid concurrent work.
• Repair competes with foreground traffic and must finish before delete/retention safety windows; Merkle trees reduce comparison scope but do not remove scanning and streaming cost.
• Cross-region design must choose local latency versus acknowledgement strength and declare behavior during WAN partitions.

Reference Architecture

The pattern this problem teaches, reusable beyond key-value stores:

Partition with versioned, failure-domain-aware placement; define fixed versus sloppy response sets; carry causal context and stable request IDs; retain concurrent versions for explicit merge; use hints only as temporary repair acceleration; and run observable anti-entropy before tombstone and retention safety windows expire.

flowchart LR
    subgraph Hot["Hot path"]
        H1[Consistent hash -> preference list of N] --> H2[Coordinator]
        H2 --> H3["Replicas (wait for R or W)"]
    end
    subgraph Bg["Background"]
        B1[Hinted handoff] --> B2[Merkle anti-entropy]
        B2 --> B3[Replicas converge]
    end
    Hot -.high availability with deferred repair.-> Bg

Figure 4. The hot path and repair path have different jobs. Response thresholds control when the client receives a result; hints accelerate recovery for intended owners; anti-entropy finds remaining range divergence. Eventual convergence depends on repair completing and conflict/delete rules being correct.

The Dynamo paper influenced Cassandra and many later stores, but descendants do not expose identical semantics. Cassandra uses consistency levels and timestamp-based reconciliation rather than the client-visible vector-clock API shown here. DynamoDB offers its own eventual/strong read and transaction contracts, including distinct multi-region modes. Compare documented guarantees, not product family resemblance.

Common Mistakes in the Interview

• Claiming linearizability from R + W > N without fixed replica-set, version reconciliation, concurrency, failed-write, and membership assumptions.
• Using last-write-wins without accepting data loss, or assuming version vectors perform the domain merge themselves.
• Ignoring causal-metadata growth, context truncation, ambiguous retries, and stable request IDs.
• Pretending the client never sees siblings, hiding the conflict-resolution responsibility instead of acknowledging it.
• Calling sloppy quorum “always writable” without a reachable fallback, capacity, read-routing, and hint-retention model.
• Treating hints as durable repair or Merkle trees as free; omitting scheduled repair and tombstone safety can resurrect deletes.
• Generalising from Dynamo to Cassandra or DynamoDB despite different conflict, consistency, transaction, and multi-region contracts.

Quick Reference

Frequently Asked Questions

What does R + W > N mean in a distributed key-value store?

N is the intended replica count, W is the number of write acknowledgements, and R is the number of read responses. R + W > N forces intersection only when reads and successful writes choose quorums from the same fixed N replicas. The coordinator must also reconcile versions correctly. Sloppy quorums, failed writes, concurrent writers, clock-based conflict resolution, or changing replica sets can break the simple argument. Quorum intersection alone does not prove linearizability.

Why does a Dynamo-style store use vector clocks?

Without serialising every write, replicas can accept concurrent versions of one key. A version vector records counters for logical actors, allowing the store to determine whether one version descends from another or whether neither dominates. Concurrent versions can be retained as siblings for application-aware merge. The actor model, metadata growth, truncation policy, and client context are part of the design; a vector clock does not automatically resolve a conflict.

What is a sloppy quorum and hinted handoff?

A strict quorum uses only the intended replica set. A Dynamo-style sloppy quorum may use reachable fallback nodes from a wider preference list; a fallback stores a hint for an unavailable intended owner and later hands it off. This raises write availability but does not make writes unconditional: the coordinator still needs enough reachable, healthy capacity, and reads must know how to find recent fallback copies. Hints are temporary and best effort, so anti-entropy repair remains necessary.

Why use Merkle trees for anti-entropy?

Merkle trees let replicas compare hashes for corresponding token ranges and descend into mismatched subranges instead of transferring every value. Equal roots provide hash-based evidence that the compared snapshots match; unequal roots localise repair work. Trees still cost CPU, memory, disk reads, and network, membership changes can invalidate ranges, and a mismatch does not decide which value is correct. Repair scheduling, version reconciliation, and checksums are separate concerns.

Is a Dynamo-style store strongly consistent or eventually consistent?

The original Dynamo design prioritises high availability and eventual convergence, surfacing concurrent versions for application-assisted resolution. R and W tune latency, availability, durability, and quorum visibility, but R + W > N is not by itself a switch to linearizability, especially with sloppy quorum. A product that needs linearizable reads, compare-and-set, or transactions must add an appropriate consensus or single-authority path and state its failure behavior.

What is the difference between last-write-wins and vector clocks?

Last-write-wins chooses a winner using an ordering rule, often a timestamp, and can discard a concurrent update. Version vectors preserve causal order and identify concurrent siblings, but the application still needs merge semantics and metadata limits. A shopping-cart union preserves additions but may resurrect removed items. Other choices include conditional writes through a leader, CRDTs, domain-specific merge, or rejecting unresolved concurrency; LWW is not the only fallback.

Sources

• Amazon Science: Dynamo — Amazon's Highly Available Key-value Store (2007)
• Apache Cassandra: Dynamo techniques and tunable consistency
• Apache Cassandra: hints are best effort, not a replacement for repair
• Apache Cassandra: anti-entropy repair and tombstone safety
• Apache Cassandra: tombstone garbage collection and delete resurrection
• Amazon DynamoDB: eventual, strong, and global-table read consistency

Related Articles

• System Design Interview Problems: A Senior's Roadmap - the full series index and pattern library.
• System Design Interview Guide: The 6-Step Framework - the method this walkthrough applies.
• Design a Distributed Cache - Part 4; consistent hashing and virtual nodes reused for partitioning here.
• Design a Payment System - Part 11; the explicit CP counterpoint to this AP design.
• Design a Job Scheduler - Part 12; coordination-service mechanics complementary to gossip membership here.
• Design a Collaborative Editor - Part 15; the same causality machinery applied to text instead of values.

This is Part 14 of an extended system design series. Next: Design a Collaborative Editor.