← Back to all questions
StaffDatabasesConsistency
Design a Multi-Region Strongly Consistent Database
A Staff-level walkthrough of a Spanner-like database that keeps data externally consistent across regions — using TrueTime (or HLC) to globally order transactions, 2PC layered over per-shard Paxos for cross-region writes, and a multi-phase state machine for zero-downtime schema changes. It trades a few milliseconds of commit-wait latency for real-time transaction ordering at petabyte scale. Follow it top to bottom, or jump to any step.
100% free · No login required
WHAT THIS QUESTION TESTS
·External consistency via bounded-uncertainty clocks (TrueTime)
·Cross-region commit: 2PC across shards, Paxos within each
·Commit-wait — why writes pause ~ε before acknowledging
·Online DDL: multi-phase schema rollout with async backfill
★ STAFF-LEVEL SIGNALS
★Chooses TrueTime vs HLC deliberately, naming the hardware-vs-restart tradeoff
★Explains why commit-wait (not just timestamps) yields real-time ordering
★Reasons about nodes at adjacent schema versions coexisting safely
★Sequences rollout single-region → followers → cross-region writes, migrating via CDC
0
Scope & ambiguity
“This builds on the KV store question but specifically targets the globally consistent SQL database challenge. The core innovation is using TrueTime (or HLC) to provide external consistency across regions. I’ll focus on how cross-region transactions work with 2PC + Paxos, and how to do online schema changes without downtime.”
1
Requirements
Requirement
Target
Consistency
External consistency (linearizability + serializability)
Cross-region write latency
p50 < 150ms
Read latency (stale)
p50 < 5ms (from local replica)
Read latency (strong)
p50 < 50ms (from leader)
Scale
Petabytes, millions of QPS
Online DDL
Schema changes with zero downtime
6
Deep dives
WHERE STAFF IS WONTrueTime Deep Dive
TrueTime API:
TT.now() → returns TTInterval{earliest, latest}
TT.after(t) → returns true if t is definitely in the past
TT.before(t) → returns true if t is definitely in the future
Implementation:
- GPS receivers on each server (provides UTC, accuracy ~1μs)
- Atomic clocks (rubidium oscillators, drift ~200μs/30s between syncs)
- Multiple time sources, take intersection → bounded uncertainty
Typical uncertainty: ε = 1-7ms (average ~4ms)
Why this matters:
With bounded uncertainty, we can ORDER transactions globally.
Without TrueTime, two transactions in different regions cannot
determine which happened first without communication.
Cross-Region Write Transaction
Transaction touches data in US-East and EU-West:
1. BEGIN: Client starts transaction, reads from local leaders
2. PREPARE: Coordinator sends 2PC PREPARE to both shard leaders
- Each shard leader runs Paxos within its shard's replica group
- Followers in the shard must agree to prepare
- Each shard responds with a prepare timestamp
3. COMMIT TIMESTAMP: Coordinator picks s = max(all prepare timestamps, TT.now().latest)
4. COMMIT WAIT: Coordinator waits until TT.now().earliest > s
(This guarantees s is in the past for ALL servers globally)
5. COMMIT: Coordinator sends commit with timestamp s to all shards
6. APPLY: Each shard applies at timestamp s via Paxos
7. DONE: Client receives commit confirmation
The COMMIT WAIT is the key innovation:
- It adds ~4ms (average TrueTime uncertainty) to every write
- But it guarantees that any transaction starting AFTER this commit
will see this commit's effects
- This is "external consistency" — real-time ordering of transactions
Hybrid Logical Clocks (Alternative to TrueTime)
For organizations without GPS/atomic clock infrastructure:
HLC = max(physical_time, last_known_HLC) + logical_counter
Properties:
- Always moves forward (even if physical clock jumps back)
- Captures causality (if A→B, then HLC(A) < HLC(B))
- Bounded by clock skew (uncertainty = NTP accuracy ~10-100ms)
CockroachDB approach:
- Use HLC for transaction timestamps
- On read, if uncertainty interval overlaps: restart transaction at higher timestamp
- Trade-off: more transaction restarts vs no special hardware
Online Schema Changes
Challenge: ALTER TABLE on a table with billions of rows, zero downtime.
Spanner approach (F1 algorithm):
1. Schema change is a multi-phase state machine:
Phase 1: DELETE_ONLY (new column exists but only delete operations use it)
Phase 2: WRITE_ONLY (new column written to but not read from)
Phase 3: PUBLIC (new column fully visible)
2. Each phase transition: update schema version in metadata
3. All nodes must be on same phase ±1 (use leases to enforce)
4. Backfill: asynchronously populate new column from existing data
5. Total time: minutes to hours depending on table size
Why multi-phase:
- If we went directly from "no column" to "column exists":
Node A (old schema) writes row without new column
Node B (new schema) reads row, expects column → error
- Multi-phase ensures nodes at different schema versions can coexist safely
7-8
Rollout & evolution
Rollout: Single-region deployment first → add followers in other regions → enable cross-region writes. Migration from existing single-region databases using CDC (Change Data Capture) + dual-write.
Evolution: Year 1: Core database with cross-region transactions. Year 2: SQL query optimizer for distributed execution, change streams (CDC), point-in-time recovery. Year 3: Multi-tenant managed service, automatic sharding recommendations, integration with ML pipelines.
★
Rubric — Senior vs Staff
Dimension
Senior signal
Staff signal
Global ordering
Uses timestamps to order transactions.
Bounds clock uncertainty with TrueTime/HLC and justifies commit-wait for external consistency.
Cross-region writes
Runs 2PC across regions.
Layers 2PC over per-shard Paxos; sets commit ts = max(prepare timestamps, TT.latest).
Clock infrastructure
Assumes clocks are synced.
Compares GPS+atomic TrueTime against NTP-based HLC; accepts more restarts to avoid special hardware.
Online schema change
Locks the table or takes downtime.
Multi-phase DELETE_ONLY → WRITE_ONLY → PUBLIC with async backfill and ±1-version leases.
Rollout & migration
Deploys all regions at once.
Phases regions in and migrates from single-region DBs via CDC + dual-write.
★ MORE WALKTHROUGHS
Want more breakdowns like this?
Join free early access for upcoming RAG, LLM eval, agents, and AI infrastructure walkthroughs.