Build a Spanner-style strongly consistent distributed database

External consistency at global scale. Build a database where a Paxos group per shard agrees on every write, TrueTime turns a clock interval into a serialization point, and 2PC across shards stays correct because everyone honors the same wait. Feel why CockroachDB and YugabyteDB diverge from Spanner precisely where TrueTime sits.

stub

SavedSaved on this device

The problem

External consistency at global scale. Build a database where a Paxos group per shard agrees on every write, TrueTime turns a clock interval into a serialization point, and 2PC across shards stays correct because everyone honors the same wait. Feel why CockroachDB and YugabyteDB diverge from Spanner precisely where TrueTime sits.

Build a Spanner-style strongly consistent distributed database. External consistency at global scale. Build a database where a Paxos group per shard agrees on every write, TrueTime turns a clock interval into a serialization point, and 2PC across shards stays correct because everyone honors the same wait. Feel why CockroachDB and YugabyteDB diverge from Spanner precisely where TrueTime sits.

What you will cover

Paxos / Raft group per shard (one consensus layer per range)
TrueTime API — bounded clock uncertainty as a primitive
commit wait — pay the uncertainty to publish a write at a real instant
external consistency vs linearizability vs serializability
2PC across shards layered over per-shard consensus
read-only transactions at a snapshot timestamp (no locks)
directory / range-based sharding + dynamic splits
snapshot reads vs strong reads vs stale reads
schema change as a globally-coordinated transaction
Paxos leader leases tied to TrueTime

Reading

Corbett et al. — Spanner: Google's Globally-Distributed Database (OSDI 2012)
Bacon et al. — Spanner: Becoming a SQL System (SIGMOD 2017)
Google Cloud Spanner whitepaper — TrueTime and external consistency
Daniel Abadi — Correctness Anomalies Under Serializable Isolation
CockroachDB blog — Living Without Atomic Clocks (HLC vs TrueTime)
YugabyteDB docs — Distributed transactions and consistency

No scenes authored for this problem yet.

About Build a Spanner-style strongly consistent distributed database

Difficulty: advanced
Time: about 100 minutes
Stages: 9
Topic: Transactions, Concurrency & Money

How this problem is worked

Nine stages, from what the thing is for to how it compares with the real implementations. Each asks one question, and the simulator runs the architecture you draw against the requirements you wrote.

01Purpose & invariantsWhat is this for, and what must always be true of it?
02Workload characterizationWho writes, who reads, and in what shapes?
03Data model & on-disk formatWhat does the data look like at rest?
04Core algorithmsHow do the write path and the read path actually work?
05Distribution & replicationHow does this scale out and survive losing a machine?
06Consistency & correctnessUnder concurrency and failure, what is guaranteed?
07Failure modes & recoveryWhat actually happens when each part fails?
08Operational characteristicsCan a human run this at three in the morning?
09Trade-offs & comparisonWhere does this sit against the alternatives?

Primary sources for this problem

Corbett et al. — Spanner: Google's Globally-Distributed Database (OSDI 2012)
Bacon et al. — Spanner: Becoming a SQL System (SIGMOD 2017)
Google Cloud Spanner whitepaper — TrueTime and external consistency
Daniel Abadi — Correctness Anomalies Under Serializable Isolation
CockroachDB blog — Living Without Atomic Clocks (HLC vs TrueTime)
YugabyteDB docs — Distributed transactions and consistency

More in Transactions, Concurrency & Money

Correctness when two writers collide and money is involved: serializability, two-phase commit versus sagas, hold-then-confirm, single-writer matching, and the databases that give you external consistency.

Browse the full problem catalog, or see what the simulator does and does not model.