External consistency, and what is verifiable

How is external consistency's real-time anchor bought?

External consistency, and why it exists

Strict serializability is serializability plus real time: if T1 commits before T2 begins in wall-clock terms, every observer sees T1 first. Equivalently, it is linearizability generalized from operations to transactions. Spanner calls it external consistency.

It needs its own name because neither parent is enough. Serializability has no recency: Transactional isolation showed that a system returning the initial state forever is serializable. Linearizability has no multi-object atomicity: Distributed consistency showed that it is defined per object. Their conjunction is strictly stronger than either, and it is the only cell in the combined table with no anomalies left.

It costs the union of both bills. The real-time anchor is bought in exactly one of three ways:

Bounded clock uncertainty, paid as commit wait (Spanner).
A communication round to an authority (a timestamp oracle; Percolator).
Optimism, paid as restarts (CockroachDB's uncertainty intervals).

The uncertainty ε is conserved. Only the invoice changes. How commit wait and uncertainty restarts work is Bounded clock uncertainty.

The justification most people never hear: almost nobody needs external consistency for reasons internal to the database. They need it because of a second channel (a human, a message queue, a separate service) that carries information faster than replication does. That is exactly the hidden-causality problem of Distributed consistency, and external consistency is the only model that closes it, because real time is the one reference frame that every out-of-band channel also inhabits. Buying external consistency is buying immunity to the causality you cannot observe.

So "do we need it?" becomes answerable: do information paths exist around your system that are faster than your replication lag? For anything user-facing across two regions, yes. (Example: Anika sends money, her app shows "sent", she phones Sam, and Sam opens his app in another region.)

What is actually verifiable

Closing this mechanism requires admitting how little of it can be checked.

Linearizability checking is NP-complete for general histories, and search-based checkers blow up on realistic traces. The practical approach inverts the problem. Record operations designed so that the version order can be recovered afterwards (list-append, monotone counters). Infer the dependency graph. Look for cycles. Then classify the cycles using exactly the shapes from Transactional isolation.

Example of a list-append test. Each transaction appends a unique number to a list stored in a row, and reads other lists. After the run, each list's final order reveals the order in which writes were applied, so the checker knows every write-write and write-read dependency without trusting the database. It then looks for a cycle and names it (for example a cycle with two anti-dependency edges is write skew).

What cannot be checked at all: any liveness claim, and any property requiring knowledge of operations that did not occur.

The operational consequence, stated bluntly: a vendor's isolation level is a hypothesis, and a cheap one to test. Independent testing has repeatedly found claimed levels unmet. The pattern is not incompetence. The levels were specified against one family of mechanisms and implemented with another, which is the same root cause as the naming mess in Transactional isolation. How to build a testing method is measurement's subject; this mechanism's contribution is knowing what to look for.

Case, resolvedConstructed case · Anika at Pebble

1,140 bonuses from a promotion of 1,000

During a 40-minute partition both regions kept handing out a 'first 1,000 sign-ups' bonus and gave 1,140, usernames had to stay unique across regions, and the CTO asked whether Pebble was CP or AP. Where it started: The unification and its price →

The promotion that gave 1,140 bonuses. "At most 1,000" is an upper bound on a quantity that sign-ups push upward. It is not I-confluent, so coordination is mandatory, and no choice of isolation level or consistency setting would have made two partitioned regions agree. She uses the one escape: partition the slack. Frankfurt gets 600 bonus tokens, Singapore gets 400 (matching expected sign-ups). Each region hands out its own tokens without talking to the other. When a region is down to 50, it asks the other region for more. Coordination rate falls from one per sign-up to about one per few hundred. The stranded slack is the price: during a partition, a region that runs out cannot give more bonuses, even if the other region has unused tokens. Pebble accepts that: better to disappoint a few users than to give away 140 extra bonuses.

Unique usernames. Also not I-confluent. She keeps username creation as a single linearizable compare-and-swap in the home region (one atomic item speaking for the rest); Singapore pays one round trip (160 ms) only at sign-up, once in a user's lifetime.

"Are we CP or AP?" Her answer to the CTO: "That is per operation. Transfers and usernames are CP: the minority side stops during a partition. Notes and reward counters are AP: they merge. And the question that costs us money every day is not the partition one. It is the E branch: what our p99 is on a normal Tuesday." She suggests looking at p99 of the balance screen in Singapore.

External consistency. She notes that "I sent it, check your app" over the phone is a faster channel than replication lag, so the transfer-confirmation flow in two regions would need external consistency, or at least a read that waits for the writer's token, and she adds a checker (list-append test with Elle-style analysis) to the integration environment, treating the database's advertised level as a hypothesis to test.