vault

Distributed SQL Database System Design

27 min read

Distributed SQL Database System Design

The distributed SQL database — sometimes called NewSQL — is the class of system that delivers the API and consistency guarantees of a single-machine relational database (full SQL with joins; ACID transactions; serializable or stronger isolation) on a horizontally-scaled, geo-distributed cluster. The class was crystallized by Google’s Spanner (Corbett et al. OSDI 2012) and now includes the open-source CockroachDB (Taft et al. SIGMOD 2020), YugabyteDB, TiDB, and Microsoft’s Azure Cosmos DB SQL API. The architectural ingredients: data sharded by key range into “tablets” / “ranges” / “regions”, each shard’s write-ahead log replicated by Paxos or Raft, distributed transactions implemented as Two-Phase Commit over the consensus groups (so even the 2PC decisions are durably replicated), and timestamps from a globally-coordinated clock — Spanner’s TrueTime API (GPS + atomic clocks for bounded uncertainty) or CockroachDB’s Hybrid Logical Clock (HLC, logical Lamport-style counter combined with the local wall clock). The headline Spanner contribution is external consistency (linearizability across the entire database, not just per-shard), which, in plain English, means: if transaction T₁ commits before transaction T₂ begins, T₂ sees T₁’s effects — a guarantee that previously required either a centralized coordinator (which doesn’t scale) or special clock hardware (which Spanner has).

1. Functional and Non-Functional Requirements

Functional.

  • Full SQL. SELECT, JOIN (including across shards), GROUP BY, aggregations, common table expressions (CTE), window functions. Most distributed SQL systems target a PostgreSQL-compatible dialect.
  • ACID transactions. Atomicity (all or nothing), Consistency (constraints preserved), Isolation (concurrent transactions don’t interfere — typically serializable), Durability (committed data survives crashes).
  • Distributed transactions across shards. A single transaction can read and write rows that live on different machines; the database must coordinate.
  • Geo-distribution. Replicas in multiple regions; transactions can span regions; configurable per-table replica placement.
  • Online schema changes. ADD COLUMN, ADD INDEX without taking the database offline. The challenge: rolling out a schema change to a 1000-node cluster atomically is impossible; the F1 paper (Rae et al. VLDB 2013) describes the multi-phase protocol.
  • Secondary indexes. Both local (per-row) and global (cluster-wide).
  • Follower reads. Stale reads from local replicas (within bounded staleness) for reduced latency without crossing regions.
  • Pessimistic and optimistic locking. SELECT FOR UPDATE; optimistic compare-and-set.
  • Backup, restore, point-in-time recovery.

Non-functional.

  • External consistency. The strongest practical correctness guarantee: every operation appears to take effect at a single instant between its start and finish, and that ordering matches real time. Spanner achieves this; CockroachDB achieves serializable + close-to-external-consistency under good conditions.
  • Linearizable cross-region. Transactions that span continents commit consistently. Cross-region commit latency is roughly 2 × inter-region network round-trip — typically 100–300 ms for transatlantic.
  • Millions of QPS. Spanner serves Google’s F1 (AdWords) at multi-million QPS; CockroachDB benchmark numbers similar at large clusters.
  • Five nines availability (99.999%) — survive AZ failure with automatic failover; survive region failure with cross-region replication.
  • Horizontal scaling. Add nodes to grow capacity; data automatically rebalances.
  • Strong durability. Writes ack only after they are persisted on at least a majority of replicas in their consensus group.

2. Capacity Estimation

A representative cluster:

  • Cluster: 100 nodes across 3 regions (33-34 nodes per region).
  • Replication factor: 3 (one replica per region for the paxos group).
  • Data shards: every table is divided into “ranges” (CockroachDB) / “tablets” (Spanner) of ~64–512 MB. A 100-TB cluster has 100 TB / 256 MB ≈ 400,000 ranges.
  • Per-node ranges: 400,000 / 100 ≈ 4,000 ranges per node, each replicated 3×.
  • Per-node memory: 128 GB. RocksDB / Pebble (storage engine) caches are sized for ~30 GB hot working set per node.
  • Per-node SSD: 4 TB. Total raw: 400 TB. Effective unique storage: 100 TB after 3× replication.
  • Single-node QPS: 50–200 K ops/sec depending on workload mix. Cluster total: 5–20M ops/sec.

Latency budget for cross-region transactions.

  • Local read (no consensus needed): < 1 ms.
  • Local write (consensus within region): 5–15 ms (one Paxos / Raft round-trip locally).
  • Cross-region read at snapshot timestamp (read from local follower): 1–5 ms (bounded-staleness read).
  • Cross-region transaction commit: 100–300 ms (one inter-region round-trip for Paxos quorum).
  • Two-phase commit across multiple Paxos groups: ~ 2 × inter-region round-trip + serial Paxos commit on each group.

The capacity story: “data sharded into thousands of consensus groups, each cheap individually, with 2PC layering on top for cross-shard atomicity, and clocks coordinated tightly enough to give external consistency without a central coordinator.”

3. Application Programming Interface

Distributed SQL systems expose vanilla SQL — the whole point is that an application that worked against PostgreSQL or MySQL works against the distributed SQL database without code changes (modulo dialect quirks).

BEGIN;
 
UPDATE accounts SET balance = balance - 100 WHERE id = 'alice';
UPDATE accounts SET balance = balance + 100 WHERE id = 'bob';
INSERT INTO transactions (from_id, to_id, amount, ts)
       VALUES ('alice', 'bob', 100, NOW());
 
COMMIT;

This 3-statement transaction may touch 3 different shards on 3 different physical nodes in 3 different regions. The system handles:

  • Acquiring write intents on each row.
  • Coordinating a transaction-wide commit (2PC, see Two-Phase Commit).
  • Choosing a commit timestamp such that the transaction is externally consistent with all other committed transactions.
  • Replicating each shard’s portion of the change via Paxos / Raft to a quorum of replicas.

The application sees a single COMMIT returning success or rollback. The complexity is hidden.

3.1 Spanner-Specific Extensions

Spanner exposes additional primitives:

  • Read-only transactions at a snapshot timestamp. SELECT ... AS OF SYSTEM TIME 2026-05-08T10:00:00Z returns a snapshot consistent with that wall-clock time. Powers analytics queries that don’t lock anything.
  • Bounded-staleness reads. “Give me a result no more than 5 seconds stale.” Lets clients read from local followers without waiting for the leader.
  • Strong reads. “Give me a result that reflects all committed transactions.” Always served from the leader (or after a lease check).

CockroachDB exposes similar primitives via its own SQL extensions (AS OF SYSTEM TIME, WITH (PRIORITY = LOW), etc.).

4. Data Model — Ranges, Replicas, Consensus Groups

4.1 Range / Tablet Partitioning

Tables are partitioned by primary-key range, not by hash. Concretely, a table’s rows are sorted by primary key; the sort order is split into contiguous ranges, each ~64 MB to 512 MB. Each range is the unit of placement, replication, and load balancing. For a users table with primary key user_id, ranges might be:

range_001: user_id ∈ [0, 1_000_000)        → replicas on nodes [N3, N7, N11]
range_002: user_id ∈ [1_000_000, 2_400_000) → replicas on nodes [N1, N4, N9]
...

When a range exceeds a size threshold (default 512 MB in CockroachDB), it splits into two new ranges; when two adjacent ranges are both small, they may merge. Splits and merges are online — no downtime.

The choice of range partitioning (vs hash partitioning as in Dynamo) is deliberate. Range partitioning makes range scans (WHERE user_id BETWEEN A AND B) cheap because consecutive keys live on the same range. Hash partitioning would make every range scan a fan-out across the entire cluster. The trade-off: range partitioning is vulnerable to hot ranges when the workload writes monotonically increasing keys (timestamps, sequential IDs). Mitigations include load-based splits (split a range that’s serving disproportionate traffic) and inserting a hash prefix in the key design.

4.2 Per-Range Consensus Group

Each range’s writes are replicated by a Raft (Spanner uses Paxos, CockroachDB uses Raft) consensus group of size N (default 3). The group has a leader (one of the N replicas) which serializes all writes and is the read source for strong reads. The other N-1 are followers that apply the leader’s log; they can serve stale-but-consistent reads (“follower reads”).

A 100-TB cluster has ~400,000 ranges, hence ~400,000 independent consensus groups, each Paxos-replicated to 3 replicas. The cost of consensus is amortized: the amount of data each group manages is small, but the number of groups is huge. This is the architectural lever distributed SQL systems pull — split the global database into millions of independent strongly-consistent shards, then layer distributed transactions on top via 2PC.

4.3 Storage Engine — LSM Tree

Each replica’s local storage is typically an LSM-backed key-value store — RocksDB in Spanner internally, Pebble (Go reimplementation of RocksDB) in CockroachDB. Tables are encoded into the KV store as (table_id, primary_key_bytes) → row_bytes; secondary indexes are encoded as separate KV pairs.

The LSM choice is for write-throughput under heavy transactional load. Some distributed SQL systems (notably YugabyteDB) use a hybrid where tables can opt into B+ Tree-backed storage for read-heavy workloads.

5. High-Level Architecture

flowchart TB
    subgraph Apps
        App[App Server / SQL Client]
    end

    subgraph Gateway["Stateless SQL Gateway Layer"]
        SG[SQL Parser + Planner + Executor]
    end

    subgraph Cluster["Storage Cluster (peer-to-peer)"]
        N1[(Node 1)]
        N2[(Node 2)]
        N3[(Node 3)]
        N4[(Node 4)]
        N5[(Node 5)]
        N6[(Node 6)]
    end

    subgraph PG1["Paxos/Raft Group for Range R1"]
        L1[Leader]
        F1a[Follower]
        F1b[Follower]
    end

    subgraph PG2["Paxos/Raft Group for Range R2"]
        L2[Leader]
        F2a[Follower]
        F2b[Follower]
    end

    subgraph TT["Time Service"]
        TrueTime[TrueTime API<br/>or HLC clock]
    end

    App --> SG
    SG -->|range R1 read/write| L1
    SG -->|range R2 read/write| L2
    L1 --> F1a
    L1 --> F1b
    L2 --> F2a
    L2 --> F2b
    SG <-.consult.- TrueTime
    L1 <-.consult.- TrueTime
    L2 <-.consult.- TrueTime
    SG -->|2PC across R1 and R2| L1
    SG -->|2PC across R1 and R2| L2

What this diagram shows. The application talks SQL to a stateless gateway layer (CockroachDB calls these “gateway nodes”; Spanner calls them “spanservers”). The gateway parses the query, plans it (cost-based optimizer, knows about range placement), and dispatches read/write operations to the appropriate consensus-group leaders. Each range has its own Paxos / Raft group of typically 3 replicas, geographically distributed across regions. Within a single range, writes go to the leader, are replicated to a quorum of followers via the consensus log, and are then applied. Across multiple ranges, the gateway runs a distributed transaction protocol (2PC over the Paxos groups) to ensure all-or-nothing semantics. The time service at the side is what distinguishes Spanner-class systems from naive distributed SQL: it provides a globally-comparable timestamp for every transaction, enabling external consistency without a centralized coordinator. The gateway and the leaders both consult the time service (Spanner: TrueTime API; CockroachDB: HLC) at transaction boundaries to choose commit timestamps.

6. Request Flow — A Read-Write Distributed Transaction

sequenceDiagram
    actor App
    participant GW as Gateway (Coordinator)
    participant TT as TrueTime / HLC
    participant L1 as Leader of Range R1 (alice)
    participant L2 as Leader of Range R2 (bob)
    participant F1 as R1 Followers
    participant F2 as R2 Followers

    App->>GW: BEGIN; UPDATE alice -100; UPDATE bob +100; COMMIT;
    GW->>TT: now() -> [t_lo, t_hi]
    Note over GW: pick start timestamp t_start = t_hi (or HLC now)

    GW->>L1: read alice, write intent at t_start (with txn_id, amount=-100)
    L1->>F1: replicate write intent via Paxos
    L1-->>GW: OK
    GW->>L2: read bob, write intent at t_start (with txn_id, amount=+100)
    L2->>F2: replicate write intent via Paxos
    L2-->>GW: OK

    Note over GW: Phase 1 of 2PC -> all participants prepared

    GW->>TT: now() -> [t_lo', t_hi']
    Note over GW: pick commit timestamp t_commit = t_hi'
    Note over GW: COMMIT WAIT: sleep until TT.now().earliest > t_commit

    GW->>L1: COMMIT(txn_id, t_commit)
    L1->>F1: replicate commit decision via Paxos
    L1->>L1: convert intent into committed write at t_commit
    L1-->>GW: OK
    GW->>L2: COMMIT(txn_id, t_commit)
    L2->>F2: replicate commit decision via Paxos
    L2->>L2: convert intent into committed write at t_commit
    L2-->>GW: OK

    Note over GW: Phase 2 of 2PC complete on both groups
    GW-->>App: COMMIT OK

Two crucial things in this flow:

  1. Each Paxos group’s commit decision is itself replicated. When the gateway tells L1 “COMMIT at t_commit,” that commit message is appended to L1’s Paxos log. If L1 crashes mid-commit, a follower takes over and replays the log; the commit either has happened or has not, but it is never half-done within a group. The 2PC layer thus runs on top of durable per-group decisions — much safer than naive 2PC over single-machine participants.

  2. The “commit wait” step. After picking t_commit, the gateway waits until TrueTime’s lower bound exceeds t_commit. This is what guarantees external consistency: by the time the transaction returns success to the application, real time has demonstrably passed t_commit, so any subsequent transaction (which will pick a later timestamp) will see this transaction’s effects. Without this wait, a transaction picking t_commit = 100 could return at real time 95; another transaction starting at real time 96 could pick t_commit = 98 and miss the first transaction’s write — violating external consistency.

The commit wait is on the order of 2ε — Spanner’s OSDI 2012 microbenchmarks measured it at about 5 ms (Corbett et al. OSDI 2012, §5.1), since the average uncertainty bound ε is ~4 ms (see §7.1).

7. Deep Dive — Selected Topics

7.1 TrueTime in Spanner

The Spanner paper’s most-discussed innovation. Standard wall clocks on cluster nodes can disagree by tens of ms (NTP slop, leap-second weirdness). Spanner deploys GPS receivers and atomic clocks in every datacenter and runs a time-coordination protocol such that every machine’s reported time is bounded:

TT.now() returns [earliest, latest]
guarantee: t_real ∈ [earliest, latest] at the moment of the call
ε = (latest - earliest) / 2  (half-width of the interval)

The OSDI 2012 paper reports concrete production numbers (§3 of the paper): the uncertainty bound ε “is typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval” and is therefore “4 ms most of the time” (Corbett et al. OSDI 2012, §3). The sawtooth shape comes from the time-coordination protocol: the daemon’s poll interval is 30 seconds, and between polls the bound grows at the applied drift rate of 200 microseconds/second — so over a 30 s interval the local-clock contribution to ε ramps from 0 to ~6 ms (30 s × 200 µs/s), and the remaining ~1 ms is the communication delay to the time masters. (Earlier statements that the typical width was ”≈ 1 ms” were wrong — the average ε is ~4 ms, and the interval width 2ε is correspondingly ~8 ms; the 1–7 ms figure is the range of ε itself, not the width.)

Two consequences:

  • External consistency comes from commit_wait: after picking t_commit, sleep until TT.now().earliest > t_commit, i.e., until every machine’s clock has advanced past t_commit. A subsequent transaction’s t_start ≥ TT.now().latest > t_commit, so it sees this transaction.
  • Snapshot reads at a timestamp t_read are safe to serve from any replica that has applied all writes up to t_read. Replicas track a per-range “safe time” for snapshot reads.

The paper also reports the measured cost of the wait: from the single-replica latency microbenchmarks (Table 3), commit wait is about 5 ms and the Paxos round adds about 9 ms (Corbett et al. OSDI 2012, §5.1). The commit wait is therefore on the order of the average 2ε, which is why driving ε down directly buys lower write latency — the paper lists getting ε below 1 ms as explicit future work.

The hardware investment is significant — every datacenter needs the receivers and clocks. This is why Spanner is internal-only at Google plus offered as Cloud Spanner; a normal cluster on commodity machines cannot replicate the TrueTime infrastructure. The external-consistency guarantee itself is stated crisply in the paper: “if a transaction T₁ commits before another transaction T₂ starts, then T₁’s commit timestamp is smaller than T₂’s,” which the authors note is “equivalently, linearizability” (Corbett et al. OSDI 2012, §1).

7.2 Hybrid Logical Clocks (HLC) in CockroachDB

CockroachDB cannot assume TrueTime hardware. It uses HLC (Kulkarni et al. OPODIS 2014) — a hybrid of Lamport’s logical clock and the local wall clock. An HLC timestamp is (physical_time_ms, logical_counter). The update rule:

HLC.now():
    pt = wall_clock.now()
    if pt > self.last_pt:
        self.last_pt = pt
        self.last_lc = 0
    else:
        self.last_lc += 1
    return (self.last_pt, self.last_lc)

HLC.update(other_pt, other_lc):
    pt = max(self.last_pt, other_pt, wall_clock.now())
    if pt == self.last_pt and pt == other_pt:
        self.last_lc = max(self.last_lc, other_lc) + 1
    elif pt == self.last_pt:
        self.last_lc += 1
    elif pt == other_pt:
        self.last_lc = other_lc + 1
    else:
        self.last_lc = 0
    self.last_pt = pt
    return (self.last_pt, self.last_lc)

When node A sends an RPC to node B carrying its HLC timestamp, B updates its own HLC to be at least one tick ahead. The chained update means causal ordering is preserved (if event X causally precedes Y, X’s HLC < Y’s HLC). The wall-clock component keeps HLCs roughly synchronized to real time, so they are useful for AS OF SYSTEM TIME queries and bounded-staleness reads.

CockroachDB sets a maximum clock offset parameter (--max-offset, default 500 ms, per the CockroachDB clock-management docs). The mechanism is twofold. First, every read carries an uncertainty interval equal to [ts, ts + max_offset]: a value with a timestamp inside that window is ambiguous as to whether it is in the reader’s past or future, so the reader must restart at a higher timestamp (an uncertainty restart) to be safe — this is how CockroachDB preserves single-key linearizability without TrueTime’s hardware bound. Second, as a safety valve, a node spontaneously shuts down if it detects its clock has drifted past 80% of max_offset relative to at least half of the other nodes in the cluster — removing a badly-skewed node before it can violate the consistency guarantees. This is the operational substitute for TrueTime: rather than provably-bounded uncertainty, CockroachDB demands operator-bounded skew via NTP / chrony and self-ejects nodes that breach it.

The trade vs Spanner: HLC is software-only and runs on commodity hardware, but external consistency is not guaranteed if clocks skew beyond the configured maximum. Spanner’s external consistency is mathematical; CockroachDB’s is configuration-dependent.

7.3 Two-Phase Commit Over Paxos Groups

Naive 2PC (Gray & Reuter, 1992) has a famous failure mode: if the coordinator crashes between the prepare and commit phases, participants are stuck holding their locks until the coordinator recovers. This is why 2PC has a reputation as a “blocking protocol.”

Spanner-class 2PC sidesteps this by:

  1. The coordinator is itself a Paxos group leader. If the coordinator’s leader replica crashes, a new leader is elected from the same Paxos group; the new leader reads the consensus log, sees the in-flight transaction, and continues.
  2. Each participant’s prepare and commit decision is also replicated via Paxos. A participant that crashes can be replaced by a follower without losing its decision.

The resulting protocol is non-blocking in the sense that any single-machine failure is transparent; an entire-region failure may stall transactions whose participants live in that region until the region recovers.

The 2PC layer adds latency: a cross-region transaction commits in roughly 2 × inter-region RTT because phase 1 and phase 2 each take one round-trip. CockroachDB’s Parallel Commits optimization (enabled by default since v19.2, released 12 November 2019) cuts this to a single round of distributed consensus for the common case (Cockroach Labs, “Parallel Commits”). The trick is a new transaction-record state called STAGING: instead of waiting for write intents to replicate (round 1) and then replicating an explicit COMMITTED record (round 2), the coordinator replicates the staging record — which lists every key the transaction writes — in parallel with the intents. A transaction is then defined as implicitly committed if “its record is in the STAGING state and an observer can prove that all of the writes listed in its transaction record have successfully achieved consensus.” Any later transaction that encounters the staging record can verify commitment itself by checking those writes, so no separate commit round-trip is needed on the critical path; the explicit flip to COMMITTED happens asynchronously. Combined with transaction pipelining (replicating intents in the background as statements execute), this lets an interactive transaction commit in one inter-region RTT.

7.4 Online Schema Changes — The F1 Protocol

Adding a column or an index to a 1000-node distributed database without downtime is hard. Naive approach: lock the whole table, alter the schema, unlock — but locking a global table for the duration of a schema rewrite is unacceptable. The F1 paper (Rae et al. VLDB 2013) describes a multi-phase protocol:

  1. Schema versioning. Every node holds a version of the schema. Different nodes can hold adjacent versions during a rollout.
  2. Allowed-versions invariant. At any time, only schema versions {V, V+1} can coexist. No node can be at V while another is at V+2.
  3. Phase 1 — write-only mode. New column is added in “write-only” — writes set it, reads ignore it. No correctness risk because reads use the old schema.
  4. Phase 2 — backfill. A background job populates the new column for existing rows. Backfill is idempotent and resumable.
  5. Phase 3 — public mode. Once backfill completes and all nodes are at version V+1, the schema flips to “public” — reads now see the column.

The protocol requires careful coordination: rollouts are gated by all-nodes-at-current-version barriers, and a node must reject writes if its schema version is too old. Spanner and CockroachDB both implement variants of this; the F1 paper is the canonical source.

7.5 Follower Reads and Geo-Local Reads

A read at the leader requires either co-locating with the leader (potentially a cross-region hop) or paying a lease check (the leader must confirm it still holds the range’s lease, which can require a Paxos round-trip). Both are slow.

Follower reads let clients read stale-but-consistent data from a local follower. The follower returns “the snapshot at timestamp T”, where T is bounded — e.g., “no more than 5 seconds stale”. For analytics queries, dashboards, and many user-facing reads, this is exactly the right trade.

The mechanism: each follower tracks a closed timestamp — the latest timestamp at which it can guarantee no future writes will be ordered earlier. The leader periodically broadcasts new closed timestamps via the consensus log. A follower can serve a read at any timestamp ≤ closed_timestamp without coordinating with the leader.

7.6 Serializable Snapshot Isolation (SSI)

The isolation level question. Strong serializable + linearizability has a real cost. Many real workloads can use Snapshot Isolation (SI) — every transaction reads from a consistent snapshot of the database at its start time, so reads never block — at much lower cost. But plain SI suffers from the write-skew anomaly: two transactions reading overlapping data and writing disjoint rows can both commit even though the result is non-serializable.

Serializable Snapshot Isolation (SSI) (Cahill et al. SIGMOD 2009, Fekete et al. TODS 2005) extends SI by tracking anti-dependencies (one transaction reads what another writes) at runtime; if a problematic cycle is detected, one transaction is aborted. The runtime cost is small for most workloads.

CockroachDB defaults to SERIALIZABLE isolation using a version of SSI. Since v23.2 (released early 2024) it also offers READ COMMITTED as a weaker, opt-in isolation level — chosen to ease migrations from PostgreSQL/Oracle/SQL Server, whose default is READ COMMITTED, so high-concurrency applications port over without rewriting retry logic (Cockroach Labs, “What’s New in v23.2”; Read Committed Transactions docs). Spanner’s default is strict serializable (= serializable + linearizable, = external consistency). PostgreSQL’s SERIALIZABLE mode has been SSI since 9.1 (released 2011), the implementation of Ports & Grittner’s work (PGCon 2011, “Serializable Snapshot Isolation in PostgreSQL”).

7.7 Why Range Partitioning Beats Hash Partitioning Here

Dynamo-style KV stores use hash partitioning because their workload is single-key point queries and hash partitioning gives perfect load balance “for free.”

Distributed SQL systems use range partitioning because their workload includes range scans (WHERE created_at > X AND created_at < Y) and secondary-index lookups that need range semantics. Hash partitioning would make every range scan fan out across the cluster. The cost — hot ranges on monotonically increasing keys — is worth paying, and is mitigated with techniques like adding a hash-prefixed shard key or using a UUID instead of a timestamp.

8. Scaling Considerations

  • Adding nodes. New node joins; existing ranges are load-balanced onto it (some replicas migrate; some leaderships transfer). Online and gradual.
  • Splits and merges. Ranges that grow past 512 MB split; small adjacent ranges may merge. Online.
  • Per-range consensus throughput. Each Paxos group can sustain a fixed write rate; cluster throughput scales with number of ranges (which scales with data size).
  • Leadership distribution. A node holding too many leaderships can be the bottleneck; the system rebalances leaders.
  • Multi-region. Leader placement per range can be configured (e.g., “this table’s leaders should live in us-east-1”), trading write latency for read locality.
  • Read-only replicas. Some tables can have additional read-only replicas for serving local reads at scale.
  • Geo-partitioned data. “Customer rows for EU customers should live in EU”; per-row constraints on replica placement (Spanner’s TABLEPARTITION; CockroachDB’s REGIONAL BY ROW).

9. Real-World Examples

  • Google Spanner (OSDI 2012, SIGMOD 2017) — internal Google. Powers F1 (VLDB 2013) which runs the AdWords business. Multi-region; 5 nines availability claimed.
  • Cloud Spanner — Spanner offered as a managed Google Cloud service since 2017. Customers include Niantic Pokemon Go, Sharetribe, JDA.
  • CockroachDB (SIGMOD 2020) — open-source Spanner-inspired SQL. Built by ex-Google engineers; uses Raft + HLC. Production at DoorDash (a published case study), Comcast, eBay shopping cart, plus thousands of others.
  • YugabyteDB (architecture docs) — open-source; Raft-replicated; supports both YSQL (PostgreSQL-compatible) and YCQL (Cassandra-compatible) APIs on the same storage.
  • TiDB (docs) — open-source MySQL-compatible distributed SQL from PingCAP. Storage is TiKV (Raft + RocksDB), transactions are Percolator-style (a 2PC variant from a Google paper). Used at Bytedance, Shopee, and others.
  • Azure Cosmos DB — Microsoft’s distributed multi-model database with a SQL API; uses a custom variant of Paxos plus tunable consistency levels (5 levels from “strong” to “eventual”).
  • Amazon Aurora — distinct lineage. Aurora is a distributed-storage replicated single-writer SQL (the writer is one PostgreSQL or MySQL process; storage is replicated across 6 nodes in 3 AZs with quorum reads and writes). Different architecture from Spanner-class but solves a similar “scale a SQL DB” problem.

10. Tradeoffs

DecisionChoiceAlternativeWhy
ConsistencyExternal (Spanner) / Serializable (Cockroach)Eventual (Dynamo)SQL semantics demand strong isolation
PartitioningRangeHashRange scans are first-class queries
Per-shard replicationPaxos / RaftAsync master-slaveStrong consistency requires consensus
Cross-shard transactions2PC over consensus groupsNoneMulti-row ACID is the SQL contract
Time serviceTrueTime (hw) / HLC (sw)Logical clocks onlyExternal consistency / bounded staleness
Default isolationSerializableRead-Committed (cheaper)The whole pitch is “real ACID at scale”
Schema changesMulti-phase async (F1)Take outageOnline is non-negotiable
Storage engineLSM (RocksDB / Pebble)B+ treeWrite throughput at scale
Geo-replicationPer-tableWhole-cluster onlyLatency vs locality choices per workload
Leader placementConfigurableRandomRead latency depends on leader region

11. Pitfalls

  1. Hot ranges from monotonic keys. A created_at timestamp PK or auto-increment ID concentrates all writes on the rightmost range. Mitigations: hash-prefix the key, use a UUID, or use Cockroach’s “load-based splitting.”

  2. Cross-region transaction latency. A transaction spanning us-east and eu-west pays inter-region RTT (~80 ms each way) twice for 2PC — 320 ms commit time is realistic. Workloads that do this on the critical path of user requests will feel slow.

  3. Clock-skew failures. CockroachDB will refuse to operate (or roll back transactions) if NTP-based clock skew exceeds the configured maximum. NTP outages, leap seconds, and VM clock drift have all caused outages.

  4. Schema-change rollbacks are hard. Once a backfill has begun, rolling back may require another backfill in reverse. F1’s protocol supports this but the operational burden is real.

  5. Long-running transactions. A transaction that holds read locks (or write intents) for minutes blocks other transactions on the same rows. SSI’s anti-dependency tracking grows with concurrency; a fleet of long transactions can exhaust memory.

  6. Read amplification from MVCC. Each row may have many uncollected versions (one per write in the GC window). Reads at a snapshot timestamp must walk versions to find the one valid at that timestamp. Tombstone garbage collection (gc_grace) trades storage vs query latency.

  7. 2PC blocking under sustained partition. Even with consensus-replicated 2PC, a partition that isolates a participant from the coordinator stalls the transaction’s participant locks until the partition heals. Multi-region transactions in geo-failure scenarios can hang for the duration of the outage.

  8. The cost of “strong reads.” A read at the leader needs a lease check (or a Paxos round-trip) to be sure no other replica has taken leadership. Heavy strong-read workloads bottleneck on lease renewal.

  9. Range-leaseholder thrashing. Contention on a single range bounces leadership between replicas; each switch is a Paxos protocol cost. Pin leaders to a region for hot ranges to avoid this.

  10. Online schema-change races. Two concurrent schema changes (say, ADD INDEX while ALTER COLUMN is in progress) require careful coordination; some systems serialize them, others allow interleaved versions only of certain types.

  11. Gateway-coordinator failure mid-transaction. If the gateway dies during 2PC, the transaction enters a recovery state on the participants; CockroachDB’s “transaction record” is the durable rendezvous point that allows another node to drive the transaction to completion.

  12. Optimizer regressions. Distributed query optimization is much harder than single-node; the optimizer must model network costs, range placement, and parallelism. Cardinality-estimate errors at scale produce dramatic plan regressions.

12. Common Interview Variants

  • “Design Spanner / CockroachDB” — the canonical full system. Hit: range partitioning, per-range Paxos/Raft, 2PC for cross-shard, TrueTime / HLC, external consistency, follower reads.
  • “Design a distributed transactional database” — same answer; pick the variant.
  • “How does Spanner achieve external consistency?” — TrueTime + commit-wait. Walk through the wait protocol.
  • “How does CockroachDB compare to Spanner?” — same architecture, different time service (HLC vs TrueTime), Raft vs Paxos, open-source vs Google-internal.
  • “Why range partitioning instead of hash?” — range scans + secondary indexes; trade hot-key risk for query expressiveness.
  • “How do you do distributed transactions across shards?” — 2PC over Paxos groups; explain the non-blocking variant.
  • “How does a schema change roll out without downtime?” — F1 multi-phase write-only → backfill → public.
  • “How does Spanner handle the FLP impossibility?” — Paxos handles consensus given an eventually-synchronous network; FLP is about pure async. In practice, networks are mostly synchronous; Paxos progresses.
  • “What’s the role of TrueTime in snapshot reads?” — gives every transaction a globally-comparable timestamp so any replica can serve historical snapshots without re-coordinating.
  • “What is serializable snapshot isolation?” — see §7.6; the runtime anti-dependency check.
  • “Why does Aurora differ from Spanner?” — Aurora is single-writer with replicated storage; Spanner is multi-writer with sharded consensus.

13. Open Questions / Uncertain

The TrueTime-epsilon and Parallel-Commits questions that previously lived here are now resolved against primary sources and folded into §7.1 and §7.3 — the OSDI 2012 paper pins ε at “1 to 7 ms, ~4 ms most of the time” with measured commit wait ~5 ms, and Parallel Commits is documented as shipping by default in CockroachDB v19.2. What remains genuinely open:

  • Whether F1’s schema-change protocol scales to schemas with hundreds of indexes (where the rollout barrier coordination cost grows). The VLDB 2013 paper does not benchmark this regime.
  • How TiDB’s Percolator-derived 2PC compares operationally to CockroachDB’s Parallel-Commits 2PC at large scale — no head-to-head primary benchmark located.
  • Production benchmarks comparing Spanner’s strict serializable to CockroachDB’s serializable under realistic, adversarial clock skew.

Uncertain

Verify: Spanner’s modern (post-2017) internals — subsequent SQL-optimizer evolution and the relationship to F1’s successors. Reason: not publicly documented; the citations here are to the OSDI 2012 and SIGMOD 2017 papers and the Google Cloud TrueTime docs (which describe the guarantee but disclose no current operational numbers). To resolve: a newer Google publication or Cloud Spanner engineering disclosure. The architectural fundamentals (per-tablet Paxos, TrueTime + commit-wait, external consistency) are confirmed against the OSDI 2012 paper and remain accurate; only fine-grained current internals are uncertain. #uncertain

14. See Also

Graph View

Backlinks