Distributed Key-Value Store — System Design Academy

Complete System Design Tutorial

The design separates the latency-sensitive online path, the correctness-critical durable transition, and asynchronous projection or repair work. Each chapter below explains one decision shown in the diagrams.

1. Requirements and scope

Functional requirements

Execute the primary distributed key-value store workflow and return an observable result.
Expose the concrete operations shown below with stable retry identities.
Allow operators to inspect, disable, repair, or replay ambiguous state.
Keep derived analytics and notifications off the correctness-critical path.

Non-functional requirements

Design for PB-scale · millions ops/s · configurable consistency.
Protect the named business invariant under concurrency and partial failure.
Scale by an explicit aggregate/partition key without one global mutex.
Degrade intentionally when cache, queue, store, or regional ownership is unavailable.

Primary invariant: acknowledged writes survive the configured failure model and replicas converge.

↑ top

2. Capacity assumptions

State assumptions before choosing technology. The supplied workload is PB-scale · millions ops/s · configurable consistency. Convert it into peak throughput, retained records, bandwidth, and failure budget; then connect each number to a component.

Dimension	Working estimate	Design implication
Traffic	PB-scale · millions ops/s · configurable consistency	Separate online compute, durable state, and asynchronous consumers.
Peak factor	5–10× average	Admission control, autoscaling headroom, and hot-key protection.
Stored state	write rate × retention × record bytes	Partition count, indexes, compaction, backup, and archival tier.
Network	peak operations × payload size	Batching, compression, edge placement, and egress budget.
Availability	99.9–99.99%	Multi-zone replicas, tested failover, and dependency error budgets.
Recovery	RPO/RTO by invariant	Ack boundary, replay retention, reconciliation, and operator runbooks.

Do not cargo-cult the numbers: show the arithmetic, name the uncertain variable, and say which production metric will replace the interview estimate.

↑ top

3. API and data model

PUT /v1/kv/{key}?consistency=QUORUM

GET /v1/kv/{key}?consistency=ONE

DELETE /v1/kv/{key}versioned tombstone

GET /admin/ringtoken ownership

Authoritative records and indexes

cell(key, value, vector_or_timestamp, tombstone, expires_at)

token_range(start, end, replicas, epoch)

hint(target_node, mutation, expires_at)

sstable(range, min_version, max_version, checksum)

Command and event envelopes

# Command envelope
operation: PUT /v1/kv/{key}?consistency=QUORUM
request_id: req_01J...
idempotency_key: idem_7f2...
aggregate_key: distributed-kv-store_123
expected_version: 17
payload: {...}

# Durable event
event_id: evt_01J...
aggregate_key: distributed-kv-store_123
event_type: distributed_kv_store_committed
schema_version: 3
trace_id: tr_8ac...

The authoritative aggregate and idempotency record share a transactional or conditional-write boundary. Event streams, search indexes, caches, analytics, and dashboards are rebuildable projections.

↑ top

4. Why this architecture and what it costs

The boxes are not a shopping list. Each boundary exists because it owns a different invariant, scaling dimension, data lifecycle, security policy, or failure domain. The table makes those choices explicit and shows when the design should remain simpler.

Component	Owned responsibility	Why separate it	Rejected alternative	Cost and evolution trigger
KV Client	Owns client protocol, request identity, retry, and resume behavior. In this design it participates in: Hash the key to a token and route using the current ring epoch.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents the external caller from also owning the contract and failure behavior of Token-Aware Router.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Sloppy quorum accepts divergent concurrent writes” to the external caller.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the KV Client boundary before extracting or scaling it.
Token-Aware Router	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Coordinator writes WAL/memtable on replica set and waits for configured acknowledgments.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents KV Client from also owning the contract and failure behavior of Membership / Gossip.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Tombstone removed before lagging replica returns” to KV Client.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Token-Aware Router boundary before extracting or scaling it.
Membership / Gossip	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Reads gather enough replicas, reconcile versions, and schedule read repair.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Token-Aware Router from also owning the contract and failure behavior of Partition Coordinator.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Node joins and streams stale range” to Token-Aware Router.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Membership / Gossip boundary before extracting or scaling it.
Partition Coordinator	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Unavailable targets receive bounded hints; anti-entropy compares Merkle ranges later.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Membership / Gossip from also owning the contract and failure behavior of WAL / Memtable.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Compaction saturates disk” to Membership / Gossip.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Partition Coordinator boundary before extracting or scaling it.
WAL / Memtable	Owns authoritative versioned state or immutable evidence. In this design it participates in: Compaction merges versions while retaining tombstones until every replica repair horizon passes.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Partition Coordinator from also owning the contract and failure behavior of SSTable Engine.	Let each service persist its own interpretation. That removes one clear commit boundary and makes retries, support, and reconciliation ambiguous. Here that simpler choice would couple “Ring partitions disagree on ownership epoch” to Partition Coordinator.	Costs schema migration, replication, backup, and shard ownership. Split storage only when access patterns, retention, or compliance boundaries materially differ. Measure the latency, saturation, lag, or mismatch at the WAL / Memtable boundary before extracting or scaling it.
SSTable Engine	Owns authoritative versioned state or immutable evidence. In this design it participates in: Hash the key to a token and route using the current ring epoch.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents WAL / Memtable from also owning the contract and failure behavior of Primary Replica.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Sloppy quorum accepts divergent concurrent writes” to WAL / Memtable.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the SSTable Engine boundary before extracting or scaling it.
Primary Replica	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Coordinator writes WAL/memtable on replica set and waits for configured acknowledgments.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents SSTable Engine from also owning the contract and failure behavior of Follower Replicas.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Tombstone removed before lagging replica returns” to SSTable Engine.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Primary Replica boundary before extracting or scaling it.
Follower Replicas	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Reads gather enough replicas, reconcile versions, and schedule read repair.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Primary Replica from also owning the contract and failure behavior of Quorum Tracker.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Node joins and streams stale range” to Primary Replica.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Follower Replicas boundary before extracting or scaling it.
Quorum Tracker	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Unavailable targets receive bounded hints; anti-entropy compares Merkle ranges later.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Follower Replicas from also owning the contract and failure behavior of Hinted Handoff.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Compaction saturates disk” to Follower Replicas.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Quorum Tracker boundary before extracting or scaling it.
Hinted Handoff	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Compaction merges versions while retaining tombstones until every replica repair horizon passes.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Quorum Tracker from also owning the contract and failure behavior of Read Repair.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Ring partitions disagree on ownership epoch” to Quorum Tracker.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Hinted Handoff boundary before extracting or scaling it.
Read Repair	Executes idempotent asynchronous work under lease and retry policy. In this design it participates in: Hash the key to a token and route using the current ring epoch.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Hinted Handoff from also owning the contract and failure behavior of Merkle Anti-Entropy.	Perform the work before acknowledging the caller. This gives simpler consistency but unbounded tail latency and fragile retries. Here that simpler choice would couple “Sloppy quorum accepts divergent concurrent writes” to Hinted Handoff.	Costs leases, checkpoints, retries, DLQs, and lag operations. Separate once execution time or burstiness no longer fits the request deadline. Measure the latency, saturation, lag, or mismatch at the Read Repair boundary before extracting or scaling it.
Merkle Anti-Entropy	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Coordinator writes WAL/memtable on replica set and waits for configured acknowledgments.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Read Repair from also owning the contract and failure behavior of Compaction.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Tombstone removed before lagging replica returns” to Read Repair.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Merkle Anti-Entropy boundary before extracting or scaling it.
Compaction	Owns one bounded domain decision, transition, or operational capability. In this design it participates in: Reads gather enough replicas, reconcile versions, and schedule read repair.	Separates a distinct scale, ownership, policy, or failure boundary. It prevents Merkle Anti-Entropy from also owning the contract and failure behavior of Backup / Restore.	Keep this behavior inside an adjacent service. Prefer that simpler option until independent scale, ownership, policy, or failure isolation is measurable. Here that simpler choice would couple “Node joins and streams stale range” to Merkle Anti-Entropy.	Costs an interface, deployment, telemetry, ownership, and failure mode. Keep it in-process first; extract when independent scale or reliability pays for the boundary. Measure the latency, saturation, lag, or mismatch at the Compaction boundary before extracting or scaling it.
Backup / Restore	Owns authoritative versioned state or immutable evidence. In this design it participates in: Unavailable targets receive bounded hints; anti-entropy compares Merkle ranges later.	Defines the source of truth and commit boundary. It prevents Compaction from also owning the contract and failure behavior of operators and repair tooling.	Let each service persist its own interpretation. That removes one clear commit boundary and makes retries, support, and reconciliation ambiguous. Here that simpler choice would couple “Compaction saturates disk” to Compaction.	Costs schema migration, replication, backup, and shard ownership. Split storage only when access patterns, retention, or compliance boundaries materially differ. Measure the latency, saturation, lag, or mismatch at the Backup / Restore boundary before extracting or scaling it.

Decision 01

Chosen boundary vs simpler monolith

Use consistent hashing or range partitions; replicate each partition across failure domains.

A single deployable with one transactional store is the right starting point for a small distributed key-value store workload. The proposed boundary becomes justified when use consistent hashing or range partitions; replicate each partition across failure domains. Separating it contains the named failure “Sloppy quorum accepts divergent concurrent writes” without placing unrelated work on the critical path.

Decision 02

Correctness vs availability

Expose quorum parameters or a fixed consistency contract; explain read repair and conflict resolution.

The design coordinates only where acknowledged writes survive the configured failure model and replicas converge. Everywhere else it accepts bounded staleness or asynchronous propagation. The alternative—strong coordination for every projection—simplifies the mental model but increases tail latency and turns partitions into broad write unavailability.

Decision 03

Operational cost and evolution

Use hinted handoff, anti-entropy, tombstones, and compaction carefully to avoid resurrected deletes.

This choice adds dashboards, ownership, schema compatibility, capacity planning, and recovery runbooks. Start with the minimum topology that supports “Reads gather enough replicas, reconcile versions, and schedule read repair.” and extract another service only when measured throughput, blast radius, data lifecycle, or team ownership changes independently.

Why this design: the synchronous path contains only the decisions required to protect acknowledged writes survive the configured failure model and replicas converge. Durable projections, notifications, indexing, analytics, and repair are isolated so their load or failure cannot corrupt the acknowledged operation.

Correctness boundary

Use consistent hashing or range partitions; replicate each partition across failure domains.

Scale boundary

Expose quorum parameters or a fixed consistency contract; explain read repair and conflict resolution.

Operational boundary

Use hinted handoff, anti-entropy, tombstones, and compaction carefully to avoid resurrected deletes.

↑ top

5. Critical flow and algorithm

Hash the key to a token and route using the current ring epoch.

Coordinator writes WAL/memtable on replica set and waits for configured acknowledgments.

Reads gather enough replicas, reconcile versions, and schedule read repair.

Unavailable targets receive bounded hints; anti-entropy compares Merkle ranges later.

Compaction merges versions while retaining tombstones until every replica repair horizon passes.

Retry-safe mutation skeleton

identity = authenticate(request)
prior = idempotency.get(identity, request.key)
if prior: return prior.result

current = authoritative_store.read(partition_key)
next_state, events = domain.transition(current, request)
authoritative_store.compare_and_set(current.version, next_state)
idempotency.commit(request.key, next_state.result)
outbox.append(events)
return next_state.result

Exactly-once business effect: the network can duplicate requests. Stable identities, conditional state transitions, immutable event IDs, and reconciliation make the user-visible effect happen once.

↑ top

6. Caching, hot keys, and backpressure

Cache policy

Add a cache only for a measured repeated read; do not place mutable correctness state in a disposable layer.

Hot partition or tenant

Measure per-key and per-tenant skew. Replicate safe reads, isolate the offender, salt only when ordering permits, and enforce budgets.

Backpressure

Bound queues, buffers, connection pools, and concurrency. Shed low-priority work and scale from lag/oldest-item age rather than CPU alone.

Stampede and retry storms

Use single-flight/coalescing, jittered expiry, bounded retries, exponential backoff, and circuit breakers so one dependency failure does not multiply traffic.

Cache outage rule: never allow every miss to fall through simultaneously. Use local protection, request coalescing, circuit breakers, bounded pools, and controlled fallback.

↑ top

7. Partitioning and consistency

partition = stable_hash(primary_or_aggregate_key) → shard owner
write = conditional_update(expected_version)
read_projection = versioned and rebuildable

Strong boundary

acknowledged writes survive the configured failure model and replicas converge. Use a uniqueness constraint, serializable/conditional write, expected version, or fencing token at this boundary.

Eventual boundary

Analytics, notifications, search, read models, and operational dashboards may lag when freshness is observable and replay exists.

Operation	Consistency	Reason
Authoritative mutation	Conditional / serializable	Protect uniqueness, ownership, money, inventory, order, or legal state transition.
Read after own write	Primary, session token, or cache warm	The caller must observe the result it just committed.
Ordinary read projection	Bounded stale where safe	Replicas and caches improve latency when version/freshness is visible.
Analytics and operations	Eventual + replay	Freshness is less important than isolating the online path.

Route every mutation for one aggregate to one owner/partition epoch.
Use cursors rather than offsets for changing ordered collections.
Retain tombstones until replication and repair windows close.
Move shard ownership through versioned maps and dual-read verification.

↑ top

8. Failure drills and recovery

Failure	Runtime behavior	Recovery proof
Sloppy quorum accepts divergent concurrent writes	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Tombstone removed before lagging replica returns	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Node joins and streams stale range	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Compaction saturates disk	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.
Ring partitions disagree on ownership epoch	Stop unsafe progress, serve only explicitly safe degraded behavior, and recover from durable state.	Reconciliation returns zero invariant gaps; lag/replica health and user-visible SLO return to baseline.

Recovery checkpoint

# Recovery checkpoint
scenario: Sloppy quorum accepts divergent concurrent writes
operation_id: op_01J...
aggregate_key: distributed-kv-store_123
last_durable_version: 18
projection_checkpoint: partition-07@offset-482901
retry_policy: same_identity / bounded_backoff
reconciliation_status: pending
owner: Backup / Restore

Every dependency needs a timeout, retry budget, circuit policy, and explicit fail-open, fail-closed, stale, or read-only mode. “Highly available” is incomplete until degraded behavior is named.

↑ top

9. Security, regions, and observability

Security and abuse

Authenticate at ingress and authorize the exact resource/tenant on every operation.
Encrypt transport and durable data; tokenize or isolate sensitive material.
Rate-limit by tenant, actor, resource, and network; detect enumeration and anomalous fan-out.
Redact secrets and personal data before logs or analytical storage.
Audit privileged mutations, support access, policy changes, and forced recovery.

Signals that prove correctness

User-visible success rate and p50/p95/p99 latency.
Timeouts, circuit state, saturation, and replica health by dependency.
Queue lag, oldest-item age, retries, and dead-letter growth.
Conflict, duplicate-suppression, and reconciliation mismatch counts.
Business drill: Sloppy quorum accepts divergent concurrent writes — alert before the user-visible invariant is violated.

Regional evolution

Begin multi-zone with tested failover, backups, and reconciliation.
Add global stateless ingress and regional read projections.
Keep one write owner per aggregate or partition where coordination is expensive.
Move ownership with epochs/fencing; avoid silent simultaneous writers.
Use expand/contract schemas, canaries, shadow reads, and reversible cutovers.

↑ top

10. Interviewer follow-ups

How do quorum reads work?

Use consistent hashing or range partitions; replicate each partition across failure domains. Walk the concrete lifecycle step “Hash the key to a token and route using the current ring epoch.” Then test it against “Sloppy quorum accepts divergent concurrent writes”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How are conflicting writes resolved?

Expose quorum parameters or a fixed consistency contract; explain read repair and conflict resolution. Walk the concrete lifecycle step “Coordinator writes WAL/memtable on replica set and waits for configured acknowledgments.” Then test it against “Tombstone removed before lagging replica returns”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How do you add a node?

Use hinted handoff, anti-entropy, tombstones, and compaction carefully to avoid resurrected deletes. Walk the concrete lifecycle step “Reads gather enough replicas, reconcile versions, and schedule read repair.” Then test it against “Node joins and streams stale range”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

What is a sloppy quorum?

Use consistent hashing or range partitions; replicate each partition across failure domains. Walk the concrete lifecycle step “Unavailable targets receive bounded hints; anti-entropy compares Merkle ranges later.” Then test it against “Compaction saturates disk”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

How do tombstones disappear safely?

Expose quorum parameters or a fixed consistency contract; explain read repair and conflict resolution. Walk the concrete lifecycle step “Compaction merges versions while retaining tombstones until every replica repair horizon passes.” Then test it against “Ring partitions disagree on ownership epoch”. State the retry identity, durable checkpoint, recovery signal, and cost of the alternative.

Answer pattern: state the invariant, choose a mechanism, walk one failure, name the recovery signal, and explain the cost of the alternative.

↑ top

11. How to present this in 45 minutes

Time	What to cover
0–5 min	Clarify scope, workload, SLOs, and the correctness invariant.
5–10 min	Estimate throughput/storage and define concrete APIs and records.
10–20 min	Draw online, durable-write, and asynchronous/repair paths.
20–30 min	Explain the exact lifecycle, partition key, and concurrency control.
30–38 min	Discuss caching, hot keys, replication, and backpressure.
38–43 min	Run failure drills, security, observability, and regional evolution.
43–45 min	Summarize the five most important choices and trade-offs.

Final decision summary

Invariant	acknowledged writes survive the configured failure model and replicas converge.
Partitioning	Stable aggregate/key hash with versioned ownership and measured hot-key isolation.
Commit	Expected version or uniqueness at the authoritative state boundary.
Async work	Durable outbox/log, idempotent consumers, checkpoints, and replay.
Recovery	Same operation identity, durable truth lookup, and business reconciliation.

Closing summary

CLOSING “The design protects acknowledged writes survive the configured failure model and replicas converge. The online path stays bounded, authoritative state is versioned and partitioned, and asynchronous work is replayable and observable.”

↑ top

KV Client

Token-Aware Router

Membership / Gossip

Partition Coordinator

Complete System Design Tutorial

1. Requirements and scope

Functional requirements

Non-functional requirements

2. Capacity assumptions

3. API and data model

Authoritative records and indexes

Command and event envelopes

4. Why this architecture and what it costs

Chosen boundary vs simpler monolith

Correctness vs availability

Operational cost and evolution

5. Critical flow and algorithm

Retry-safe mutation skeleton

6. Caching, hot keys, and backpressure

7. Partitioning and consistency

Strong boundary

Eventual boundary

8. Failure drills and recovery

Recovery checkpoint

9. Security, regions, and observability

Security and abuse

Signals that prove correctness

Regional evolution

10. Interviewer follow-ups

11. How to present this in 45 minutes

Final decision summary

Closing summary