Walkthrough: Designing a Distributed Database

The problem

You’re asked to design a distributed database — the system underneath Spanner, CockroachDB, or TiDB. The interviewer says something like: “Your company’s relational database is out of headroom. Design a database that scales horizontally, survives machine and zone failures without losing committed data, and still gives developers SQL with real transactions.”

Sounds like the KV store question again. It isn’t — it’s its mirror image. The requirements (cross-row transactions, secondary indexes, consistent reads) demand exactly the contract the Dynamo-style design traded away. The trap is reaching for the AP toolkit — quorums, vector clocks, eventual convergence — when the question’s center of gravity is: how do you keep ACID when the rows of one transaction live on different machines?

Below is how I’d walk through this, start to finish.

1. Requirements

First 3–5 minutes. Questions I’d ask to pin down what we’re building:

Functional requirements

• R1. SQL reads and writes — point queries, range scans, joins.
• R2. ACID transactions, including across rows on different machines.
• R3. Secondary indexes, kept consistent with the data transactionally.
• R4. Committed data survives node and zone failures — RPO of zero, failover without operator action.
• R5. Horizontal scale — add nodes, get capacity — and multi-region: reads near users, configurable write homes.

Scope

Explicitly out of scope:

• The query optimizer and SQL execution engine (a database career, not a section — I’ll treat “SQL → plan of point reads and scans” as given)
• Analytical workloads (columnar/HTAP is a different storage engine bolted to this one; named, not designed)
• Backup/restore and change-data-capture pipelines (consumers of the replication this design already has)
• Schema migration tooling (a product on top)

Non-functional requirements

• Consistency default. Is serializable the contract, or is snapshot isolation acceptable? This decides the concurrency-control design.
• Latency. Single-row transaction p99? Cross-region transaction budget?
• The loss contract. Is “asynchronous replica, lose the last second on failover” acceptable? (If yes, this is a much cheaper design — worth asking precisely because the answer “no” justifies everything that follows.)
• Workload shape. OLTP point-access dominant? Scan-heavy? Sequential-key inserts (the hot-range trap)?

Say the interviewer confirms: OLTP, 100K transactions/sec peak (mostly single-digit-row), 50 TB growing 2×/year, p99 ≤ 10 ms for single-region single-row transactions, RPO = 0 (no committed write may ever be lost), failover in seconds without humans, serializable isolation as the default, three regions with most traffic in one.

2. Capacity estimate

• Data: 50 TB now, 200 TB in two years. Split into ~512 MB ranges → ~100K–400K ranges, each independently replicated and placed.
• Writes: 100K txn/sec × ~3 rows ≈ 300K row writes/sec. Each row write costs: WAL append + Raft replication ×3 + MVCC version + (per secondary index) another replicated write — ~10× write amplification between SQL row and physical bytes. Provision for ~3M replicated writes/sec.
• Fleet: ~100 nodes for storage and IOPS — but the number I’d flag is the range count: hundreds of thousands of consensus groups to lease, balance, split, and heal.

I’d say out loud: “Two conclusions. The write path is expensive by design — every committed byte is a consensus round, that’s what RPO-zero costs, and it’s why this database should never host workloads that don’t need it. And the real management problem isn’t bytes, it’s the fleet of a few hundred thousand little Raft groups — the database is substantially a scheduler for them.”

3. High-level architecture

Three logical layers:

1. SQL layer — stateless: parses, plans, and turns SQL into KV operations against ranges. Any node can serve any query.
2. Range layer — the keyspace, sorted, in ~512 MB ranges; each range is a Raft group of 3+ replicas with one leaseholder serving its reads and coordinating its writes.
3. Transaction & time layer — the machinery that makes multi-range operations atomic (transaction records, write intents) and reads consistent (MVCC timestamps from a disciplined clock).

flowchart TD
  Client[Client] --> SQL[SQL layer · any node]
  SQL --> LH[Range leaseholder]
  LH --> Raft[(Range · Raft ×3)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Raft store

The range layer decides the system’s character: ranges are sorted (SQL scans need adjacency — this is the range-partitioning choice the partitioning reference contrasts with hashing), small enough to move and split quickly, and each one fails over independently via its own consensus.

4. Architecture evolution

Each level is what teams actually migrate through, and naming Level 3’s pain precisely — the application owns atomicity — is what justifies Level 4’s complexity.

The design in this walkthrough is Level 4–5.

I’d say out loud: “I’m designing Level 4 — auto-sharded ranges with per-range consensus and distributed transactions — because the requirements (RPO zero, cross-row ACID, no manual resharding) are precisely the three things Level 3 can’t give. If any of those relaxed, I’d argue for stopping earlier.”

Target architecture (Level 4)

Every section that follows explains one part of this diagram:

flowchart TD
  Client[Client] --> SQL[SQL layer · any node]
  SQL --> LH1[Leaseholder · range A]
  SQL --> LH2[Leaseholder · range B]
  LH1 --> R1[(Range A · Raft ×3)]
  LH2 --> R2[(Range B · Raft ×3)]
  SQL --> TxnRec[(Txn record · on range A)]

  Meta[(Meta ranges · addressing)] -.-> SQL
  Placer[Placement & balancing] -.-> R1
  Placer -.-> R2
  Clock[Clock service · HLC/TrueTime] -.-> SQL

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class R1,R2,TxnRec,Meta store

5. Core design choice: how transactions cross machines

Three options:

(a) No cross-shard transactions. Shard so that transactions are single-shard (by tenant, by user), forbid the rest. Honest, fast — and it silently moves the problem into the application (sagas, reconciliation jobs), which is Level 3 with better marketing. Right when the data model truly partitions; our requirements say it doesn’t.

(b) 2PC over primary/replica shards. A coordinator prepares/commits across shard primaries. Two fragilities: the coordinator is a single point (its crash leaves participants holding locks, blocked), and each participant’s “prepared” promise lives on one primary — a failover can forget a vote. This is the design that gave 2PC its reputation.

(c) 2PC over per-range consensus. Every range is a Raft group; a transaction writes intents (provisional MVCC versions) to each range it touches — each intent Raft-committed — and the transaction’s fate lives in a transaction record, itself a Raft-replicated row. Commit = flipping that one record from PENDING to COMMITTED. Participants can’t forget (replicated), the coordinator can’t strand anyone (its state is the record, on a range, replicated; any node can resolve it), and the decision is atomic because it’s a single-key write.

Choice: (c) — the Spanner/Percolator lineage — because R2 (cross-row ACID) plus R4 (RPO zero, no-human failover) rules out anything with a forgettable vote or a blocking coordinator.

Tradeoff matrix

Architecture decisions

Core data structures

6. Write path: a transaction commits [R2, R4]

The slice of the target architecture a two-range transaction touches — UPDATE accounts ... (range A) and UPDATE balances ... (range B):

flowchart TD
  Client[Client] -->|BEGIN ... COMMIT| SQL[SQL layer · gateway node]
  SQL -->|"1 · intent + txn record (PENDING)"| LH1[Leaseholder · range A]
  SQL -->|"2 · intent"| LH2[Leaseholder · range B]
  LH1 --> R1[(Range A · Raft ×3)]
  LH2 --> R2[(Range B · Raft ×3)]
  SQL -->|"3 · flip record → COMMITTED"| LH1
  SQL -->|"4 · ack client, resolve intents async"| Client

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class R1,R2 store

Step by step:

1. The gateway assigns the transaction a timestamp and writes its first mutation as a write intent on range A — Raft-committed — alongside the transaction record (txn 42: PENDING, ts=T) on that same range. Co-locating the record with the first write makes single-range transactions (the 90% case) cost one consensus round total: intent and record commit together, and “commit” is local.
2. The second mutation writes an intent on range B (Raft-committed), pointing back at the transaction record. Any reader encountering this intent knows exactly where to learn the truth.
3. Commit is one write: flip the record to COMMITTED (Raft-committed on range A). The instant that entry is in range A’s log, the transaction is durably, atomically decided — both intents are now logically real, even though neither range B nor any reader knows yet.
4. Acknowledge the client. Intent resolution — rewriting intents as ordinary versions — happens asynchronously; until then, readers who hit an intent check the record and resolve on the spot (helping, not waiting).

Why this never strands: every piece of protocol state — intents, votes (an intent is a Raft-committed prepare vote), the decision — lives in replicated ranges. Gateway dies before step 3: the record times out as PENDING, any contender marks it ABORTED (a Raft write that wins or loses cleanly), intents roll back lazily. Gateway dies after step 3: the decision is already in the log; whoever finds the intents finishes the paperwork. There is no machine in this story whose death leaves the system unsure.

7. Read path: MVCC and the clock [R1, R2]

flowchart TD
  Client[Client] --> SQL[SQL layer]
  SQL -->|"read keys as of ts=T"| LH1[Leaseholder · range A]
  LH1 --> R1[(MVCC versions)]
  LH1 -->|intent found?| TxnRec[(Txn record)]
  SQL -.->|follower read, ts ≤ closed| F1[Follower replica]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class R1,TxnRec store

Step by step:

1. Every transaction reads as of its timestamp: for each key, the newest MVCC version ≤ T. Point queries and scans go to each range’s leaseholder — the one replica with the range’s read lease, which can serve without a consensus round because the lease (itself Raft-coordinated) guarantees no other replica is accepting writes.
2. Hit an intent? Check its transaction record: committed-with-ts ≤ T → it counts; pending → conflict handling (wait briefly, or push the younger transaction — priority rules prevent livelock); aborted → ignore and clean it.
3. The clock question. “Newest version ≤ T” across machines is only meaningful if timestamps are comparable across machines. Perfectly synced clocks don’t exist, so: TrueTime (Spanner) buys a bounded uncertainty interval with GPS/atomic hardware and waits out the bound (~few ms) at commit so timestamp order matches real-time order; hybrid logical clocks (CockroachDB) track an uncertainty window without special hardware — a read that encounters a version inside its uncertainty window restarts at a higher timestamp rather than risk missing a causally-prior write. Same invariant, different payment: Spanner pays at every commit; HLC pays only on actual close calls.
4. Follower reads (R5). Leaseholders periodically publish a closed timestamp — “no new writes below T’.” Any follower can then serve reads at ts ≤ T’ locally — this is what makes a remote region’s reads fast-and-slightly-stale by contract rather than by accident, the disciplined version of the replication reference’s lag anomalies.

8. Deep dives

Secondary indexes are just more ranges [R3]

An index is a table mapping (indexed_cols, pk) → presence, living in its own key space — which means its own ranges, possibly on different machines than the row. The elegant consequence: index maintenance is automatically transactional — updating a row and its index entries is a multi-range transaction through the §6 machinery, no special index protocol needed. The honest cost: every indexed write becomes a distributed transaction (one more intent, often one more range), so each index multiplies write amplification — “indexes are cheap” is single-box intuition that doesn’t travel.

Hot ranges and sequential keys [R5]

Sorted ranges resurrect the problem hashing solved: monotonically increasing keys (auto-increment IDs, timestamps) aim every insert at the last range — one Raft group becomes the whole database’s write throughput. Defenses, in order: design keys (UUIDs/bit-reversed IDs) where scan order isn’t needed; load-based splitting (split ranges on traffic, not just size — though splitting a last-range hotspot just moves it); hash-sharded indexes (hash(key) % 16 prefix — buying insert spread at the cost of 16-way scan fan-out, the partitioning tradeoff made consciously). The meta-point to say: ranges make scans cheap and sequential inserts dangerous; hashing is the reverse; this database picked scans, so key design is now a schema review item.

Multi-region placement [R5]

Three dials, all built from machinery that already exists:

• Replica placement — a range’s replicas spread across zones/regions (survive a region loss → quorum must span regions → cross-region commit latency; survive only zone loss → region-local quorum, fast commits).
• Leaseholder placement — reads and write coordination happen at the leaseholder, so pin it where the table’s traffic lives: EU users’ rows lease in the EU. Per-table or per-row (partition by a region column) homes turn “multi-region” from a deployment fact into a schema-level decision.
• Follower reads — everyone else reads slightly-stale locally (§7).

The sentence that shows the tradeoff is understood: a row has one home for writes; every other region chooses between paying the round trip and reading the recent past — physics offers nothing else, and the database’s job is to make the choice explicit per table.

9. API design [R1, R2]

The API is SQL; the design surface is the transaction contract:

BEGIN;                              -- ts assigned; serializable by default
  SELECT ... ;                      -- reads at txn ts (may refresh/restart)
  UPDATE ... ;                      -- write intents, Raft-committed
COMMIT;                            -- txn record flip; or:
                                   -- ERROR 40001 serialization_failure → RETRY

SET TRANSACTION AS OF SYSTEM TIME '-5s';   -- explicit stale read, any replica

Two non-obvious decisions:

Retries are the client’s contract. Serializable-via-MVCC means conflicts surface as 40001 restart errors by design — the client must wrap transactions in a retry loop (and the docs must say so on page one). Hiding retries server-side works only for single-statement transactions (the gateway holds the whole statement and can replay it); the moment results have been streamed to a client mid-transaction, only the client can replay. This is the API admitting how optimistic concurrency works rather than pretending to be a single-box lock manager.

Staleness is opt-in and explicit. AS OF SYSTEM TIME routes to any nearby replica via closed timestamps — the API makes “fast and 5 seconds old” a choice with syntax, not a surprise (the exact opposite of Level 2 read replicas, where staleness is ambient and unbounded).

The API hides ranges, leases, intents, and the clock discipline completely — it looks like Postgres. That’s the point: the abstraction boundary is “SQL with a retry loop,” and everything in §5–8 can rebalance, split, and fail over behind it.

10. Data model and storage

Requirements → components

Access frequency

Storage technology choices

Access pattern matrix

Schemas

MVCC layout [R1, R2] — the physical heart:

/table/42/pk=alice @ ts=170    → {balance: 90}          # committed versions
/table/42/pk=alice @ ts=165    → {balance: 100}
/table/42/pk=alice @ intent    → {balance: 75, txn: 42} # provisional, points at record

/txn/42                        → {status: PENDING|COMMITTED|ABORTED,
                                  ts, heartbeat, in_flight_writes}

Range descriptor [R5]

/meta2/<end_key>               → {range_id, span: [start, end),
                                  replicas: [(node, store), ...×3],
                                  leaseholder, closed_ts}

11. Failure modes

Grouped by what they threaten. The pattern: name what fails, name what degrades, name what doesn’t.

Durability and availability failures

A node dies

Fails: its replicas’ participation — including some leaseholders and Raft leaders. Degrades: affected ranges elect new leaders and acquire new leases in seconds; in-flight statements retry transparently below SQL. After a grace period, the placer re-replicates the dead node’s ranges from survivors, fleet-wide in parallel. Doesn’t degrade: committed data — every commit was on a majority before any client saw it. RPO zero is not a recovery procedure; it’s the write path. (The contrast with Level 2 — where this same event is “page a human, pick a replica, hope the lag was zero” — is the whole argument for the design.)

A zone or region partitions away

Fails: minority-side quorums. Degrades: asymmetrically by design — ranges with majority on the connected side keep working; the minority side serves only stale follower reads and refuses writes. This is the CP choice made explicitly in §1, and it’s the opposite corner from the KV-store walkthrough — same fork, other branch, chosen by the loss contract. Doesn’t degrade: consistency, anywhere, ever — no split brain because no range can have two quorums.

Transaction failures

Gateway dies mid-transaction

Fails: that transaction’s driver. Degrades: nothing system-wide — the txn record’s heartbeat lapses, a contending transaction (or GC) marks it ABORTED via a clean Raft write, intents unwind lazily. Locks-held-forever — classic 2PC’s nightmare — can’t happen because the record’s fate is contestable and replicated (§6). Doesn’t degrade: any other transaction beyond a brief intent-resolution pause on touched keys.

Contention storm

Fails: throughput on hot rows — optimistic MVCC means conflicting serializable transactions restart, and under heavy contention restart loops ratchet (each retry holds intents longer, causing more conflicts). Degrades: latency on the hot keys; the database self-protects with txn priorities (aged transactions win) and bounded backoff — but the real fix is the schema’s (a counter row that everything updates is a design bug at any layer; shard it or queue it). Doesn’t degrade: disjoint workloads — contention is per-key, not global.

Time failures

Clock skew exceeds assumptions

Fails: the uncertainty bound’s honesty. Degrades: with HLC — more uncertainty restarts (a latency wobble, correctness intact) up to the configured max offset; nodes detecting skew beyond it self-fence and crash rather than serve possibly-causality-violating reads — the same err-unavailable instinct as the lock walkthrough’s step-down margin. With TrueTime: commit-wait stretches with the interval; correctness rides the hardware’s honesty. Doesn’t degrade: anything silently — both schemes convert clock failure into visible latency or visible unavailability, never invisible anomalies.

Hot range from sequential inserts

Fails: one Raft group’s throughput becomes the table’s insert ceiling (§8’s trap sprung). Degrades: insert latency on that table while load-based splitting chases a moving hotspot — splitting helps reads, barely helps a last-key insert storm. The durable fixes are schema-side (key design, hash-sharded index). Doesn’t degrade: other tables/ranges; reads at closed timestamps.

12. What I’d skip, and say I’m skipping

Time check — five minutes left. Things I’d explicitly defer:

• SQL planning and execution. Distributed joins, vectorized execution, statistics — a second interview. I’ve kept the boundary at “SQL becomes range reads and transactional writes.”
• Changefeeds/CDC and backup. Consumers of the Raft logs and MVCC history this design already maintains; the one coupling worth naming is GC TTL (§10’s warning).
• HTAP. Bolting columnar replicas onto the ranges (TiFlash-style) for analytics — a real direction, a different storage engine.
• Schema changes online. Backfilling an index transactionally across 100K ranges without blocking writes is a protocol of its own (state-machine DDL); named, deferred.
• When not to use this. Worth thirty seconds, not skipping entirely: append-only event firehoses (the queue walkthrough’s log is cheaper), cache workloads, analytics — anything that doesn’t need the loss contract shouldn’t pay consensus on every write. The strongest Staff signal on this question is knowing what the expensive machine is for.

Saying “I’d skip this, and here’s why” is a strong signal. It shows you know the full surface and are making deliberate scoping choices.

Interview flow summary

Architecture at a glance

WRITE (transaction)                     READ
BEGIN → ts assigned                     Statement at ts=T
 ↓                                       ↓ meta ranges: key → leaseholder
intent on range A + txn record           ↓
(PENDING) — one Raft commit             Leaseholder: newest version ≤ T
 ↓                                       ↓ intent found → check txn record
intent on range B — Raft commit          ↓
 ↓                                      Remote region: follower read
COMMIT = flip record → COMMITTED        at closed timestamp (stale, local)
 ↓ ack client
resolve intents async                   Conflict → 40001 → client retries

The walkthrough order for your whiteboard

1. Requirements        — the loss-contract question; serializable default
2. Capacity            — write amplification; 100K Raft groups to manage
3. Evolution           — primary/replica → manual shards → ranges+consensus
4. Core choice         — 2PC over consensus; why the txn record is the txn
5. Write path          — intents, record flip, who-knows-the-outcome test
6. Read path           — MVCC, leases, clock discipline, follower reads
7. Deep dives          — indexes-as-ranges, hot ranges, region placement
8. API                 — the retry contract; explicit staleness
9. Data model          — MVCC layout, meta ranges, GC coupling
10. Failure modes      — durability / transactions / time groups

If the interviewer pushes deeper

13. Wrap-up

One crisp sentence before the interviewer’s next question:

This design buys zero-loss durability and seconds-level failover by paying consensus on every write, then layers two-phase commit over those replicated ranges so that atomicity has no single point of failure — and the residual costs surface honestly, as a client retry contract and a per-table choice about where writes live and how stale remote reads may be.

What separates levels on this question

• SDE II designs primary/replica with read replicas and manual shards, and handles cross-shard writes with “we’d use 2PC” — naming the protocol without its failure story.
• SDE III derives the architecture from the loss contract; walks a two-range commit through intents and the record flip; passes the who-knows-the-outcome test at every crash point; explains why reads need a clock story and what HLC restarts are; and names the retry contract as API, not bug.
• Staff/Principal treats placement as the schema-level product decision (leaseholder homes, follower-read staleness budgets); prices write amplification per index and consensus per write; couples GC TTL to backups and changefeeds before it bites; pushes contention fixes into schema design; and — the differentiator — states plainly which workloads shouldn’t be on this database at all.

The difference isn’t knowledge. It’s the chain of custody for a commit — strong answers can say, at any instant of any failure, exactly which replicated structure knows whether the transaction happened.

Further reading

• Spanner: Google’s Globally-Distributed Database — the paper that proved global SQL with external consistency was buildable, and what TrueTime costs and buys.
• Large-scale Incremental Processing Using Distributed Transactions and Notifications — Percolator: 2PC layered on Bigtable, the intent/record pattern in its original form.
• In Search of an Understandable Consensus Algorithm — Raft. The per-range replication primitive; read it once properly.
• CockroachDB Architecture: Life of a Distributed Transaction — the production documentation of §6–7’s machinery, including HLC uncertainty restarts.
• Logical Physical Clocks (HLC) — the clock discipline that makes Spanner-style reads possible without Spanner’s hardware.
• Designing Data-Intensive Applications — Kleppmann. Chapters 7 (transactions) and 9 (consistency and consensus) are the textbook under this entire walkthrough.
• System Design Interview Vol. 1 — Alex Xu. Chapter 6 (the KV store) is the sibling design — read the two together as the AP and CP branches of the same fork.