Design a globally consistent, multi-region database (Spanner)

01The design, in the six-step framework

1. Requirements

Functional

• A relational database with SQL, schemas and secondary indexes, used by many products (an ads ledger, user accounts, a web index's metadata).
• Transactions across rows, tables and data centres that behave as if executed one at a time (serializable), with a consistent snapshot read at any past time.
• Online schema changes with no downtime, and data placed near the users who access it.
• Out of scope: analytics over petabytes (a warehouse), blob content.

Non-functional

• Petabytes per database across 3 to 5 regions on two or more continents; 99.999 percent availability.
• Survive the loss of a whole region with no data loss and automatic failover in seconds.
• Read-write transaction commit within a region in about 10 ms; cross-continent commits accepted at 100 to 200 ms.
• Strong reads served locally in a few milliseconds when possible; hot keys must not take down a shard.

2. Core entities

• Database and Table: schema, interleaving (child rows stored with their parent), secondary indexes, placement policy (which regions).
• Shard (split): a key range of a table, its consensus group, its leader, its location.
• Transaction: id, read set, write set, commit timestamp, status.
• Timestamp: a globally meaningful commit time with a known uncertainty bound.

3. API

• BeginTransaction(mode = read_write | read_only(at = now | timestamp))
• Read(table, key or range, columns), ExecuteSql(query) within a transaction.
• Commit(txn, mutations) → commit timestamp, or abort with a retryable code.
• Admin: UpdateSchema(ddl) executed online; SetPlacement(table, regions).

4. High-level design

A read-write transaction that moves money between two accounts on different shards:

1. The client reads both balances through the shards' leaders, which take read locks, then buffers the two writes.
2. On commit, the client picks one shard's leader as coordinator. Every participating leader acquires write locks, chooses a prepare timestamp, and logs a prepare record through its own consensus group (two-phase commit across groups, each phase made durable by consensus).
3. The coordinator chooses the commit timestamp as the latest prepare time, waits until that timestamp is definitely in the past according to the time service's uncertainty bound, then logs commit and releases locks. The wait is what makes timestamps agree with real time across the planet.
4. A read-only transaction picks a timestamp and reads from any replica that is caught up to it, with no locks: a report over a billion rows runs on local replicas without blocking writers.

5. Deep dives

How can a transaction be serializable across continents without a global lock manager?

Two mechanisms carry it. Within a shard, a single leader orders transactions with two-phase locking and makes its log durable through consensus, so a leader crash never loses a committed write. Across shards, two-phase commit runs over those leaders, and because each participant's prepare is itself replicated, the classic 2PC failure (a coordinator dying with participants blocked) is bounded: the coordinator state is in a replicated log and a new leader finishes the protocol. The commit timestamp comes from globally synchronized clocks with an explicit error bound; waiting out the bound before releasing locks guarantees that if transaction T2 starts after T1 commits anywhere in the world, T2's timestamp is larger. Without that, you would need every transaction to talk to every other, which is the global lock manager you cannot afford.

Why are local strong reads possible, and when are they not?

A replica knows the timestamp up to which it has applied the log. A read at timestamp t can be served by any replica that is caught up to t, which a replica in the reader's region usually is within tens of milliseconds. So a read that asks for "now" picks t = now (from the time service), and if the local replica lags behind t it waits a few milliseconds or goes to the leader. The costs to say out loud: a replica far from the leader lags more; a read of a key that was just written on another continent may wait for the log to arrive; and the time service's uncertainty bound adds directly to that wait.

Hot keys and hotspots: what does the system do and what must the schema do?

The split manager watches per-shard load and splits a busy key range, moving one half to another machine; that handles a hot range such as "today's rows". It cannot help a single hot row or a monotonically increasing key (a timestamp or auto-increment primary key), which funnels all inserts into the last shard. The schema must spread the load: hash a prefix into the key, use UUIDs, or interleave child rows under a parent so related rows share a shard and a transaction stays local. An interviewer who asks "the ads ledger has one row per advertiser and one advertiser is 20 percent of traffic" wants to hear sharded counters (N sub-rows summed on read) rather than a system feature.

Online schema change without downtime

Adding a column or index cannot stop 750,000 replica processes at once. The change is given a future timestamp; every server learns the new schema version and, because all reads and writes are timestamped, applies the old schema before that time and the new one after it, so the switch is atomic across the planet without a pause. Building a secondary index is a background backfill at a snapshot timestamp, with new writes maintaining the index from the schema-change time onward, and the index is marked readable only when the backfill passes the snapshot. Dropping a column is lazy: the data is simply ignored and reclaimed by compaction.

6. What a strong answer sounds like

• Start with the physics: round-trip times between the regions you chose, which fix the commit latency floor.
• Draw consensus groups per shard and two-phase commit over their leaders, and explain how replicated prepare records remove the blocking case.
• Explain why timestamps with an uncertainty bound and a commit wait give external consistency; derive the wait from the clock error.
• Show the snapshot-read path from local replicas; it is the reason the system is fast for the common case.
• Expect follow-ups on hot keys (schema design), on what happens in a region loss (quorum still exists, leaders migrate), and on the cost of 2PC for transactions that could have been single-shard.
• Common mistake: claiming strong consistency across regions with no account of latency or clocks.

02Where this question was reported

• IGotAnOffer · 'How would you design Google's database for web indexing?'
• IGotAnOffer · Same question, EM list
• IGotAnOffer · EM: 'Design a database'
• interviewkickstart.com · 'Google.com's database (customers, orders, products)'
• interviewkickstart.com · Q2, Q4, Q5 plus hot-key and hotspot practice questions
• PracHub · 'Diagnose distributed database inconsistency'; 'relational-to-NoSQL migration pipeline'
• Blind · Google can dive very deeply; harder than other companies
• resumegeni.com · 'Design Spanner' (TrueTime, external consistency) as canonical problem.
• gitgood.dev · L6 deep-dive example: consistency layer for a multi-region database.
• onsites.fyi · L6: globally consistent configuration management system (like Google FlagService).
• interviewkickstart.com · 'Design of a globally distributed database'; data consistency in globally distributed system.