Design a globally consistent database
Imagine one bank ledger kept in Mumbai, Frankfurt and Virginia at the same time. A customer moves money in Mumbai, and a second later someone in Frankfurt checks the balance. Frankfurt must see the new balance, not the old one, even though the copy in Frankfurt is thousands of kilometres away.
Most distributed databases ask you to give something up to get there: availability, or transactions, or knowing whether the row you just read is current. This question asks whether you can have real SQL transactions (a group of reads and writes that all happen or none do) across continents, with a guarantee strong enough that nobody using the database has to think about copies at all. Watch one transaction go through.
Begin. A client opens a transaction at the nearest front end. Front ends hold no state, so any of them will do.
A few words carry this whole page:
- A region is one group of datacentres in one part of the world, like Mumbai.
- A replica is one full copy of a piece of the data. Copies live in several regions so that losing one region loses nothing.
- Consensus is how a small group of replicas agrees on one order of writes, even when some of them crash. Raft and Paxos are the two well known ways to do it, and Consensus with Raft walks through one.
- Two phase commit (2PC) is how several groups agree to commit one transaction together: first everyone promises, then everyone commits.
The system this design is modelled on is Google's Spanner. What makes it worth studying is that the hard part is not consensus. Consensus is solved. The hard part is time: two machines cannot agree on what "now" means, and every strong ordering guarantee across regions comes down to that.
- SpannerGoogle, described in a 2012 paper
Step 1: Understand the problem#
This question is won or lost on scope. Ask what the guarantee has to be, because "consistent" means several different things, and only the strongest one costs you a wait on every commit. (The strong vs eventual consistency article lays out the range.)
| You ask | They say | What it settles |
|---|---|---|
| What is the consistency guarantee, exactly? | External consistency. If A commits before B starts, every reader sees them in that order. | The whole page. In plain words: the order in the database matches the order things happened in the real world. This is stricter than serialisable, and it is the requirement that forces a clock with known error bounds into the design. |
| Do transactions span regions, or just rows? | They span regions. | Two phase commit on top of consensus groups, and write latency measured in round trips between regions rather than single milliseconds. |
| What is the read to write ratio? | Heavily read, as always. | Where to spend the cleverness. Reads that take no locks and never wait are worth more here than making writes faster. |
| How much write latency is acceptable? | Tens of milliseconds. Users are doing one thing at a time. | Permission for a commit wait and a cross region majority. If the answer had been single digit milliseconds, you would have to give up the guarantee. |
| Who runs the hardware? | We do. Every machine, every clock, every switch. | You can install atomic clocks and GPS receivers. Say this assumption out loud, because it is why you cannot build Spanner on rented machines. |
| What happens when a region is cut off? | Refuse writes rather than let the copies disagree. | A CP system: the cut off minority stops serving. That is the correct answer for a database people put money in. |
Serialisable means the result is the same as if the transactions had run one at a time in some order. Any order. External consistency adds "and that order is the real time order". The difference sounds small and is the whole design. The consistency models chapter calls this pair strict serialisability, and the CAP theorem chapter explains why a CP system refuses writes during a split.
What you are building#
- SQL transactions across rows that live in different regions. Serialisable, not eventually consistent.
- External consistency. If A commits before B starts in real time, every observer sees A before B. This is the strongest ordering guarantee, and it is the product.
- Survive losing a region. Without data loss and without a person having to decide on a failover.
- Reads that do not block writes. Every row keeps several versions, so a read never takes a lock.
- Data in at least three regions.
- Reads served from a nearby replica where possible.
- Commit latency measured in tens of milliseconds, not hundreds.
- No lost writes on the failure of any single region.
- Query planning and optimisation, a whole discipline of its own and unrelated to the distribution problem.
- Coordinating schema changes, which is genuinely hard and would take the whole session.
- Analytical queries. This is a transactional store, and mixing the two is a separate design (see OLTP vs OLAP).
Back of the envelope: the problem is time#
A commit pays for three things. A worked example first, with round numbers. Say the regions holding the replicas are 60ms apart for a round trip, the transaction touches two partitions, and every clock may be off by up to 7ms either way.
- Copying the write to a majority of replicas: one round trip, 60ms.
- Two phase commit across the two partitions: about one more round trip, 60ms.
- Commit wait: twice the clock uncertainty, 2 x 7 = 14ms. Why twice is the first deep dive.
Total: about 134ms. A transaction that stays inside one partition skips step 2 and lands near 74ms. Now move the sliders. (The method behind these estimates is in back of the envelope.)
Drag the clock uncertainty slider. At 7ms either side, the bound GPS receivers and atomic clocks in every datacentre are there to hold, commit wait costs about 14ms, small next to the network. At 100ms either side it costs 200ms and dominates everything. Ordinary NTP gives no hard bound at all, so you would have to assume a wide one. That is why this design comes from a company that could put atomic clocks in its own buildings: a tight clock bound is what makes the guarantee affordable.
That slider is the whole insight. Every strong ordering guarantee across regions is paid for in either talking or waiting, and the cost of waiting grows with how badly you know the time. The round trip term depends on where you put the replicas: keep the regions that form a majority close together and it stays small, put them on different continents and the total climbs fast.