# Design a Globally-Distributed SQL Database (Spanner / CockroachDB) > SQL transactions that are ACID across continents. How Spanner shards into Paxos groups, runs 2PC on top, and uses TrueTime to give you external consistency — the CP counterpart to Dynamo. Canonical: https://ironclad.academy/system-design/articles/design-spanner | Difficulty: advanced | Topics: Interview, Distributed Systems, Databases, Transactions, Consensus, Consistency, Staff Asked at: Google, Uber, CockroachDB, YugabyteDB, Amazon ## Key takeaways - Consensus is per shard, not per cluster: thousands of independent Paxos groups each fail over and commit without coordinating with the rest. - TrueTime exposes clock uncertainty as an interval, and commit-wait (roughly 2 times epsilon, or 2-14 ms in practice) converts that uncertainty into an airtight external-consistency guarantee. - Layering 2PC on Paxos groups eliminates the blocking-coordinator failure: both prepared votes and the commit decision are durably replicated, so no crash can leave participants locked forever. - MVCC snapshot reads are lock-free and can be served by any replica that has caught up to the read timestamp, keeping the read path fast even though the write path pays full consensus cost. - Co-locating rows that are transacted together into the same split is the critical data-modeling move: it turns a multi-shard 2PC into a cheaper single-group commit. > **In one line:** Shard data into many **Paxos replication groups** (open-source variants use Raft), run **two-phase commit across groups** for multi-shard transactions, and use synchronized clocks (**TrueTime**) to stamp commits so the whole planet agrees on one global order — external consistency, at the cost of cross-region latency. **The problem.** Give applications a familiar relational database — SQL, secondary indexes, and **ACID transactions that span rows, tables, and regions** — that also scales horizontally and survives datacenter loss. This is the apex distributed-systems problem because it sits squarely on the CAP fault line: it deliberately chooses **consistency over availability** and engineers around the latency that choice imposes. **Requirements that drive the design.** - Horizontally scalable SQL with multi-row, multi-table, **cross-region** transactions. - **External consistency** (= strict serializability): if T1 commits before T2 starts, every reader sees them in that order, everywhere. - Survive node and whole-region failures with automatic failover. - Read-heavy workloads should get fast, lock-free snapshot reads. **Scale.** | Dimension | Estimate | How we got there | |---|---|---| | Splits per deployment | Thousands | Each split is one Paxos group; Google runs millions of ranges across the fleet | | Replicas per split | 3 (single-region) / 5+ (multi-region) | 3 tolerates 1 failure; 5 tolerates 2 across regions | | Single-shard commit latency | A few ms | One inter-zone quorum round-trip within a region; commit-wait mostly overlaps it | | Cross-region commit latency | Tens of ms | Bounded by WAN RTT to majority; 50–100 ms typical US↔EU | | Commit-wait overhead | ~2–14 ms | 2ε where ε (≈ 1–7 ms) is TrueTime uncertainty; kept tight via GPS/atomic clocks | **Takeaway:** The dominant latency cost is the quorum round-trip — one inter-zone RTT for a single-region commit, one WAN RTT for cross-region. Commit-wait is bounded by ~2ε (2–14 ms) but overlaps the Paxos replication the leader is already doing, so it usually adds little on top. Co-locating transacted rows in the same split converts expensive 2PC into a cheap single-group commit. **The architecture in one diagram.** ```mermaid flowchart TD APP[Client / SQL] --> FE[Query layer
plan + route] FE --> G1[Split A
Paxos group] FE --> G2[Split B
Paxos group] G1 --> L1[Leader] --> R1[(replicas in
3+ zones)] G2 --> L2[Leader] --> R2[(replicas)] TT[TrueTime
GPS + atomic clocks] -. commit timestamps .-> L1 TT -.-> L2 COORD[2PC coordinator] --> G1 COORD --> G2 style L1 fill:#ff6b1a,color:#0a0a0f style TT fill:#a855f7,color:#fff style COORD fill:#15803d,color:#fff ``` **Key design decisions.** | Decision | Choice | Why | | --- | --- | --- | | Replication | **Paxos/Raft per shard** (not per cluster) | Majority quorum survives minority failure; each shard fails over independently | | Multi-shard txn | **2PC layered on top of Paxos** | Atomicity across groups; Paxos makes each participant durable so 2PC doesn't block forever | | Global ordering | **TrueTime** (bounded clock uncertainty) + commit-wait | Assign ts = TT.latest, wait until TT.earliest > ts → external consistency (strict serializability) | | Reads | **MVCC snapshot reads** at a timestamp | Lock-free, consistent reads from any replica; no read locks | | CAP stance | **CP** — reject writes during partition | Correctness over availability; the explicit trade-off | **If you have 60 seconds, say this.** "I shard the keyspace into many ranges, and replicate *each shard* with its own Paxos group — so a majority quorum keeps each shard available through minority failures, and shards fail over independently. Single-shard transactions commit via the group's leader in one quorum round-trip. Multi-shard transactions use **two-phase commit across the groups**, and because each 2PC participant is itself Paxos-replicated, the protocol doesn't block forever if a coordinator dies. The hard part is global ordering: I use **TrueTime** — clocks with a *bounded uncertainty* — to assign commit timestamps at the *latest* possible bound, then wait until the *earliest* bound surpasses that timestamp before acking, which gives external consistency (strict serializability). Reads are MVCC snapshots at a timestamp, so they're lock-free. The whole thing is a deliberate **CP** choice: under a partition it rejects writes rather than diverge." ## The problem Google Spanner manages the relational data for products that touch hundreds of millions of users — ads, payments, commerce — across every continent. CockroachDB and YugabyteDB exist precisely to bring the same model to the rest of the industry. The pitch is simple: a familiar SQL database with real ACID transactions, that also scales horizontally across machines and survives the loss of an entire datacenter. The delivery is anything but simple. The core tension is that distributed databases have always forced a choice between correctness and availability. The [Dynamo-style key-value store](/system-design/articles/design-key-value-store) sits at one end: always writable, eventually consistent, conflicts resolved after the fact. That tradeoff is fine for shopping cart contents or social-graph edges. It is not fine for a payment ledger or an order-fulfillment system, where a dropped write is a lost dollar or a double-shipped order. Uber's engineering team learned this the hard way when they [migrated off Cassandra and Redis to Spanner](https://eng.uber.com/fulfillment-platform-rearchitecture/) because they needed strong consistency for multi-row, multi-table transactions that span regions — something you cannot retrofit onto an availability-first store after the architecture is set. What makes this problem genuinely hard is the combination of two requirements that pull in opposite directions. External consistency — the guarantee that the entire planet's readers agree on one commit order that matches real-time order — demands synchronized clocks and commit coordination. Horizontal scale demands that data be split across thousands of shards on hundreds of machines. Every write touching more than one shard needs an atomic commit protocol. Every commit needs a globally valid timestamp. And any solution that is too slow or too expensive to operate doesn't ship. This is the staff/architect-level question because it sits squarely on the CAP fault line: Spanner deliberately chooses **consistency over availability** and then engineers as hard as possible against the latency that choice imposes. The rest of this article is about how. ## Functional requirements - **SQL** with schemas, secondary indexes, and joins. - **ACID transactions** spanning multiple rows, tables, and shards — including across regions. - **Horizontal scale**: capacity grows by adding nodes; data auto-splits and rebalances. - **Strongly consistent reads**, plus cheaper bounded-staleness/follower reads as an option. - **Survive** zone and region failures with automatic failover, no data loss of committed writes. ## Non-functional requirements - **External consistency** (Google's term for strict serializability): the strongest practical guarantee — the system behaves as if every transaction executed instantaneously at a single point in time, and this serial order is consistent with real-time commit order. - **Durability**: a committed transaction survives *f* replica failures (majority quorum). - **Availability within a region** even if a minority of replicas fail; **CP under partition** (sacrifice availability of the minority side). - **Latency**: single-shard, single-region commits in a few ms; cross-region commits bounded by WAN RTT — and reads that *don't* pay write-path latency. ## The crux: CAP, and why this is a CP system CAP says under a network **P**artition you choose **C** or **A**. Dynamo chose A (stay writable, reconcile later). A globally-consistent SQL database chooses **C**: if a shard's leader can't reach a majority, it stops accepting writes there rather than risk two sides diverging. [PACELC](/system-design/articles/cap-theorem-deep-dive) extends this: *else* (no partition), you still trade **L**atency for **C**onsistency — quorum writes and commit-wait cost milliseconds you wouldn't pay in an eventually-consistent store. Saying this explicitly — *"this design deliberately sacrifices availability and latency for consistency, and here's exactly where"* — is the move that signals staff-level judgment. The rest of the article is *how* you pay that bill as cheaply as possible. ## Building up to the design ### V1: One SQL node Start with a single Postgres primary. You get full ACID and zero distributed-systems pain — but one machine caps your write throughput and storage, and it's a single point of failure. Lose the box, lose the database. ### V2: Primary + read replicas Add async followers and route reads to them. Read scale goes up and you have a warm standby. But writes still funnel to one primary, and async replicas are *stale* — read-your-writes breaks, and a primary failover can lose the un-replicated tail. Not acceptable for anything touching money. ### V3: Shard the data Split tables into ranges across many nodes; each node owns a slice. Writes now scale horizontally. Two new problems surface immediately: each shard is still a single point of failure, and a transaction touching two shards has no atomicity — you can commit on shard A and crash before shard B. You've lost ACID across shards. ### V4: Replicate each shard with Paxos/Raft Make every shard a **replication group** of (say) 3 replicas (single-region, across 3 zones) or 5 replicas (multi-region), kept in sync by a consensus protocol. The group elects a leader; writes are committed once a **majority** acknowledges. A 3-replica group tolerates 1 failure; a 5-replica group tolerates 2 ([Raft's quorum property](/system-design/articles/leader-election-and-consensus)). This is the key structural idea: **consensus is per-shard, not per-cluster** — thousands of independent Paxos groups, each small enough to be fast. Each shard now fails over automatically. But multi-shard atomicity is still unsolved, and you still need a global order across shards so reads are consistent. ### V5: Two-phase commit across groups + TrueTime ordering For a transaction spanning groups, run **2PC** with the participant leaders as cohorts. Crucially, each participant is *itself* a Paxos group, so a "prepared" vote is durably replicated — the classic 2PC "coordinator dies and everyone blocks forever" failure is defanged because participants don't lose their prepared state. Then use **TrueTime** to assign a commit timestamp that respects real-time order, giving external consistency. This is the production design (Google Spanner; CockroachDB and YugabyteDB are Spanner-inspired open-source systems using Raft rather than Paxos, and HLCs instead of GPS/atomic-clock TrueTime). The diagram below picks up here. ```mermaid flowchart LR V1[V1: single SQL
SPOF, no scale] --> V2[V2: read replicas
stale, no write scale] V2 --> V3[V3: shard
write scale, no cross-shard ACID] V3 --> V4[V4: Paxos per shard
durable + HA shards] V4 --> V5[V5: 2PC + TrueTime
global ACID + external consistency] style V1 fill:#0e7490,color:#fff style V3 fill:#15803d,color:#fff style V4 fill:#ff6b1a,color:#0a0a0f style V5 fill:#a855f7,color:#fff ``` ## Architecture ```mermaid flowchart TD C[Client] --> QP[Query layer
parse, plan, route to splits] subgraph "Split A (range [a,m))" LA[Leader A] --> A1[(Replica zone1)] LA --> A2[(Replica zone2)] LA --> A3[(Replica zone3)] end subgraph "Split B (range [m,z))" LB[Leader B] --> B1[(Replica zone1)] LB --> B2[(Replica zone2)] LB --> B3[(Replica zone3)] end QP --> LA QP --> LB LA <-->|"2PC: prepare/commit"| LB TT["TrueTime API
now() → interval"] -.->|"assign commit ts"| LA TT -.-> LB PLACE[Placement driver
split / rebalance / move leaders] -.-> LA PLACE -.-> LB style LA fill:#ff6b1a,color:#0a0a0f style LB fill:#ff6b1a,color:#0a0a0f style TT fill:#a855f7,color:#fff style PLACE fill:#0e7490,color:#fff ``` Four layers hold this together. The **query/SQL layer** is stateless — it plans queries and routes each piece to the right split. The **splits** are the range-partitioned shards, each a Paxos group with a leader that does the actual work. The **placement driver** watches for hot or oversized ranges and continuously splits them, rebalances replicas, and moves leaders closer to load. And the **TrueTime service** feeds bounded-uncertainty timestamps to every leader so commits land in a provably correct global order. How many splits does that imply, and what does a commit cost? Back-of-the-envelope for one deployment: ```text data volume 10 TB split size target ~512 MB (Spanner keeps ranges in this ballpark) → number of splits 10 TB / 512 MB ≈ 20,000 independent Paxos groups per-split write ceiling bounded by 1 inter-zone RTT (~1–2 ms) → O(1k) serial commits/s per group before pipelining fleet write throughput 20,000 groups × ~1k/s ≈ 2 × 10^7 commits/s ceiling (hot-shard skew pulls the real number well below this) cross-region commit 1 WAN RTT (~70 ms US↔EU) + 2ε (~8 ms) ≈ 80 ms single-region commit 1 inter-zone RTT (~1–2 ms) + overlapped commit-wait ``` The split count is why "consensus per cluster" is a non-starter: 20,000 groups is fine when each is independent, and impossible if every write has to coordinate across all of them. ## TrueTime: the idea that makes it work Here's the deep problem. To impose a global order on commits, every commit needs a timestamp. But clocks on different machines disagree — not by much, but enough. If you just read local wall-clock time, two transactions can get timestamps that contradict their real-time order, breaking consistency in a way that's nearly impossible to debug. Spanner's insight is to **expose clock uncertainty as a first-class value.** `TrueTime.now()` returns not a point but an **interval** `[earliest, latest]` guaranteed to contain the true time, with uncertainty ε kept tight by GPS receivers and atomic clocks in every datacenter — a few milliseconds in practice. The trick is **commit-wait**: the leader assigns a commit timestamp `t = TT.now().latest` (the upper bound of the current uncertainty interval), replicates the commit via Paxos, then **waits until `TrueTime.now().earliest > t`** before releasing locks and acking the client. The wait duration is roughly 2ε, though much of it overlaps the Paxos replication the leader is already running, so the latency actually added is usually small. By the time any observer sees the commit, `t` is unambiguously in the past everywhere. The guarantee follows: if T1 commits before T2 begins in real time, `t1 < t2` always — **external consistency**. ```mermaid sequenceDiagram participant L as Leader participant TT as TrueTime L->>TT: now() → [earliest, latest] Note over L: commit ts = latest (upper bound) L->>L: replicate commit via Paxos loop commit-wait (~2ε) L->>TT: now() → [e', l'] Note over L: wait until e' > commit_ts end L-->>L: release locks, ack client ``` The cost is real: every commit pays roughly 2ε of commit-wait latency. Google spends serious money on GPS/atomic-clock infrastructure to keep ε small (~1–7 ms, so the wait is ~2–14 ms). **CockroachDB and YugabyteDB can't assume that hardware**, so they use **Hybrid Logical Clocks (HLC)** — wall-clock combined with a logical counter. The consistency consequence: CockroachDB provides **serializable** isolation by default, not strict serializability / external consistency — meaning a "causal reverse" anomaly across causally-dependent transactions is theoretically possible (though rare in practice). It compensates via **uncertainty restarts**: if a read encounters a value whose timestamp falls within the uncertainty window, the transaction retries at a higher timestamp rather than risking a stale read. That trade — *dedicated time infrastructure for external consistency vs. commodity clocks for serializability* — is worth raising in any interview on this topic. ## Reads: MVCC snapshots, no locks Multi-version concurrency control stores each row as **timestamped versions**. A read executes "as of" a timestamp and sees the latest version `≤ t`. This gives you three things. Read-only transactions take no locks and never block writers (and vice versa) — a huge win for read-heavy workloads. A snapshot read at a past timestamp is consistent and can be served by *any* replica that has caught up to `t`, including a nearby follower, so you can dodge a cross-region hop entirely. Strong reads go to the leader; stale/bounded-staleness reads trade a little freshness for local latency. This separation — strongly consistent *writes* via Paxos+2PC, lock-free consistent *reads* via MVCC — is what keeps a CP database usable under heavy read load rather than grinding to a halt on lock contention. ```mermaid flowchart LR R[Read request] --> Q{"Strong or
stale?"} Q -->|"strong read"| LEADER[Shard leader
latest committed version] Q -->|"bounded-staleness"| FOLLOWER[Nearby follower
version at ts T] LEADER --> MVCC[(MVCC versions
row@t1, row@t2, ...)] FOLLOWER --> MVCC MVCC --> OUT[Consistent snapshot
no locks held] style LEADER fill:#ff6b1a,color:#0a0a0f style FOLLOWER fill:#0e7490,color:#fff style MVCC fill:#15803d,color:#fff style OUT fill:#a855f7,color:#fff ``` ## Two-phase commit, made non-blocking Vanilla 2PC has a notorious flaw: if the coordinator crashes after participants vote "prepared," they hold locks forever waiting for a decision. Layering 2PC on Paxos groups fixes both failure modes. A "prepared" vote is written through the participant's Paxos group, so it survives the participant leader crashing — a new leader takes over already knowing it's prepared. The coordinator's decision is also Paxos-replicated, so a crashed coordinator is replaced by a peer that can finish the commit. Neither side can lose its state. Underneath 2PC is the lock story, and it's pessimistic. As a read-write transaction reads and writes, it acquires locks at the leader of each participant split under **two-phase locking (2PL)**, and those locks are held until commit-wait finishes and the client is acked. That means cross-shard transactions can deadlock, which Spanner avoids with **wound-wait**: an older transaction wounds (forces an abort of) a younger one holding a lock it needs, while a younger transaction simply waits — so cycles can't form. This is exactly why the lock-free MVCC read path from the previous section matters so much: strong reads take a snapshot at a timestamp and never touch these write locks, so read-heavy load doesn't queue behind write-path contention. ```mermaid sequenceDiagram participant Co as Coordinator (Paxos group) participant A as Participant A (Paxos group) participant B as Participant B (Paxos group) Co->>A: prepare Co->>B: prepare A->>A: replicate "prepared" (Paxos) B->>B: replicate "prepared" (Paxos) A-->>Co: vote yes B-->>Co: vote yes Co->>Co: replicate "commit" decision (Paxos) Co->>A: commit @ ts Co->>B: commit @ ts ``` It's still 2PC — it still blocks the specific rows under contention, and adds a round-trip — which is exactly why **data modeling matters**: co-locate rows that are transacted together (Spanner's *interleaved tables* / table families) into the same split so the common transaction is single-group and skips 2PC entirely. ## Placement, splitting, and rebalancing Ranges aren't static. A **placement driver** continuously splits a range that grows too large or too hot, rebalances replicas across nodes to even out load and storage, moves leaders toward the region generating the writes (leader locality cuts latency), and repairs under-replicated groups when a node dies by re-replicating to restore the quorum margin. This is how the system scales smoothly instead of requiring manual resharding — the operational pain that [hand-rolled sharding](/system-design/articles/database-sharding) inflicts. ## Edge cases and follow-ups ### Hot rows / write skew A single hot row (a global counter) serializes on one Paxos leader. Mitigate by sharding the counter, or accept the bottleneck. **Write skew** (two transactions each reading-then-writing disjoint rows that violate an invariant together) requires `SERIALIZABLE` isolation — which these systems provide, unlike default Postgres `READ COMMITTED`. ### Clock skew beyond ε If a machine's true clock drifts outside the guaranteed uncertainty, the external-consistency guarantee is violated. The TrueTime architecture defends against this: each GPS/atomic clock *master* continuously cross-checks its own drift and evicts itself from serving time (stops advertising) if it diverges substantially — causing ε to temporarily grow on that datacenter until other masters compensate, which in turn makes Spanner's commit-wait longer, not undefined. Correctness depends on the time infrastructure actually meeting its bound — a rare but real operational assumption worth naming. ### Cross-region write latency A transaction whose leader is in `us-east` but must reach a majority across regions pays inter-region RTT per commit. Designs minimize this by placing all replicas of latency-sensitive data in one region (giving up some disaster tolerance), or using leader leases so reads stay local. ### Schema changes without downtime Online schema changes use a multi-version, staged protocol so old and new schema coexist during rollout — a hard sub-problem Spanner solved with timestamped schema versions. ### When NOT to use this If you don't need cross-row/cross-region atomicity, this is overkill — you're paying consensus + commit-wait latency for guarantees you don't use. The judgment call is recognizing that **most workloads are fine with a single-region SQL DB + read replicas**, and reserving globally-consistent SQL for the genuinely transactional, genuinely global use cases (payments, inventory, fulfillment). ## What interviewers look for Interviewers probe three areas. First, **framing and tradeoffs**: did you open with an explicit **CP / consistency-over-availability** stance (CAP/PACELC), and did you name the latency cost and when the design is the wrong tool? Second, **the core mechanisms**: consensus per shard (not per cluster) and why that limits blast radius; 2PC layered on Paxos and why the Paxos layer makes 2PC non-blocking; TrueTime + commit-wait and what external consistency actually guarantees; MVCC snapshot reads and why they stay lock-free. Third, **open-source alternatives**: how CockroachDB and YugabyteDB substitute HLC for GPS/atomic-clock TrueTime and what consistency level they achieve as a result. ## Things you should now be able to answer - Why can't you retrofit cross-region ACID onto a Dynamo-style AP store? - Why is consensus done per-shard instead of across the whole cluster? - What does commit-wait actually wait for (TT.now().earliest > commit_ts), and what does it buy you? - How does layering 2PC on Paxos avoid the blocking-coordinator problem? - Why can read-only transactions avoid locks entirely? - When is a globally-distributed SQL database the wrong choice? ## Further reading - "Spanner: Google's Globally-Distributed Database" (Corbett et al., OSDI 2012) — TrueTime, commit-wait, the whole design - "Spanner, TrueTime and the CAP Theorem" (Eric Brewer, 2017) - Uber Engineering, "Building Uber's Fulfillment Platform" — a real Cassandra/Redis → Spanner migration for cross-region transactions - CockroachDB and YugabyteDB design docs — Spanner-style consistency on commodity clocks via Hybrid Logical Clocks - Martin Kleppmann, *Designing Data-Intensive Applications*, ch. 7 & 9 (transactions, consistency & consensus) ## Frequently asked questions Q: What is external consistency in Spanner, and how does TrueTime enforce it? A: External consistency (Google's term for strict serializability) means the system behaves as if every transaction executed instantaneously at a single point in time, and that serial order matches real-time commit order. Spanner enforces it by assigning each commit a timestamp equal to TrueTime.now().latest, then performing commit-wait: the leader holds the commit until TrueTime.now().earliest exceeds that timestamp, guaranteeing the commit timestamp is unambiguously in the past everywhere before any observer sees it. Q: Why does Spanner run consensus per shard rather than across the whole cluster? A: Each shard (split) runs its own independent Paxos group so that shards fail over independently and a failure in one range has no blast radius on others. It also keeps each consensus group small and fast: a 3-replica single-region group needs only one intra-region (inter-zone) round-trip per quorum write, whereas a cluster-wide consensus protocol would require every node to coordinate on every write. Q: How does layering 2PC on Paxos prevent the classic blocking-coordinator problem? A: In vanilla 2PC, a crashed coordinator leaves participants holding locks forever because they cannot know the final decision. When each participant is itself a Paxos-replicated group, a prepared vote is durably written to the participant's log before the vote is sent, so a new participant leader can recover already knowing it voted yes. The coordinator's commit or abort decision is also Paxos-replicated, so a failed coordinator is replaced by a peer that can finish the protocol without losing state. Q: How do CockroachDB and YugabyteDB differ from Spanner on clock-based consistency? A: Spanner relies on GPS receivers and atomic clocks in every datacenter to keep TrueTime uncertainty small (roughly 1-7 ms), which allows true external consistency at the cost of ~2-14 ms commit-wait per write. CockroachDB and YugabyteDB use Hybrid Logical Clocks (HLC) on commodity hardware instead; as a result they provide serializable isolation rather than strict serializability, and compensate with uncertainty restarts when a read encounters a value whose timestamp falls within the clock uncertainty window. Q: When is a globally-distributed SQL database the wrong choice? A: If the workload does not require cross-row or cross-region atomicity, the consensus and commit-wait overhead is unjustified cost. Most workloads are fine with a single-region SQL database plus read replicas; reserve globally-consistent SQL for genuinely transactional, genuinely global use cases such as payments, inventory, and fulfillment.