TrueTime's Role in Externally Consistent Transactions

The Challenge of Time and Causality

In a distributed system, achieving a consistent view of data is fundamentally a problem of ordering. For transactions, serializability ensures that there exists some serial order equivalent to the concurrent execution. However, it doesn't say that this order must match the real-world, wall-clock order of events.

External consistency (also called linearizability or strict serializability) is a much stronger guarantee. It requires that if transaction T1 commits before transaction T2 begins, then the serial order must place T1 before T2.

This seems simple, but it's incredibly difficult to achieve in a global system. Consider two transactions, T1 and T2, handled by different servers, potentially thousands of miles apart. A user's application observes that T1 has completed, and based on that result, initiates T2. This establishes a clear causal link: T1 happens-before T2. The problem arises from clock skew. If the server for T2 has a clock that is running slightly behind the server for T1, it might assign T2 a commit timestamp that is earlier than T1's timestamp.

You might think that logical clocks, like Lamport clocks, would solve this. However, they only track causality that is passed through direct messages within the system. They cannot capture "out-of-band" causality, such as the user in our example who connects the two transactions.

The following video from Martin Kleppmann provides an excellent explanation of why both standard physical clocks and Lamport logical clocks are insufficient for this task.

TrueTime: A Clock API with Bounded Uncertainty

Google's solution to this problem is not a perfectly synchronized clock, but rather a service and API called TrueTime that acknowledges and quantifies clock uncertainty. This is the conceptual breakthrough. Instead of pretending clocks are perfect, TrueTime provides a guarantee about their maximum error.

The core of the API is the TT.now() method. It does not return a single point in time. Instead, it returns an interval: [earliest, latest]. TrueTime guarantees that the absolute, real-world time of the TT.now() invocation lies somewhere within this interval. The width of this interval, latest - earliest, represents the clock uncertainty, denoted as $ϵ$.

To provide these guarantees, TrueTime is implemented as a robust, redundant service.

The uncertainty $ϵ$ is derived from two main sources:

1. The communication delay when a node contacts the time masters.
2. The worst-case clock drift of the local quartz crystal clock on the server since its last synchronization. Servers sync with masters roughly every 30 seconds, causing $ϵ$ to follow a "sawtooth" pattern, typically varying between 1ms and 7ms.

The seminal Spanner paper provides the definitive description of this system.

Achieving External Consistency with Commit Wait

Now we have an API that gives us a time interval [earliest, latest]. How does Spanner use this to assign timestamps that respect external consistency? The solution lies in a two-part protocol for assigning a commit timestamp, s, to a transaction T.

1. Timestamp Assignment (The "Start" Rule): When a transaction is ready to commit, the coordinator leader assigns it a commit timestamp $s_T$ by choosing $s_T=\text{TT.now().latest}$. This chooses a time that is guaranteed to be at or after the real moment the timestamp was chosen.

2. Commit Wait Rule: After assigning the timestamp $s_T$, the coordinator does not immediately make the transaction's writes visible. Instead, it waits until TT.now().earliest is greater than $s_T$. This step is the "commit wait."

Let's see why this works. The commit wait forces the system to pause until the real, absolute time has definitively passed the chosen commit timestamp $s_T$. This ensures $s_T<t_{abs}(\text{commit})$, where $t_{abs}(\text{commit})$ is the absolute time when T's commit becomes visible to other transactions.

Now consider our original scenario: T1 commits, and then a client observes this and starts T2.

• T1 gets timestamp $s_1$ and enters commit wait. It becomes visible only after absolute time has passed $s_1$.
• T2 starts after T1 is visible. The absolute time of T2's start, $t_{abs}({\text{start}}_2)$, is therefore greater than $s_1$.
• When T2 commits, it gets timestamp $s_2=\text{TT.now().latest}$. This value is guaranteed to be greater than or equal to the absolute time when the timestamp was chosen, which is after T2 started. So, $s_2\ge t_{abs}({\text{start}}_2)$.
• By transitivity, we have $s_1<t_{abs}({\text{start}}_2)\le s_2$, which gives us the required property: $s_1<s_2$. External consistency is preserved.

This mechanism of using an uncertainty interval and enforcing a wait is the linchpin of Spanner's consistency model. The following video segment from one of the Spanner paper's authors provides an excellent visual explanation of this process.

Performance Implications

A mandatory "wait" in a commit protocol sounds like a performance killer. However, its impact is carefully managed.

First, the uncertainty $ϵ$ is kept very small—typically just a few milliseconds. The cost of the commit wait is on the order of $2ϵ$, which amounts to less than 10ms in the common case.

Second, and more importantly from a system design perspective, the commit wait can be overlapped with other work. When a transaction commits, the coordinator leader must replicate the commit decision to the other replicas in its Paxos group. This replication involves network round-trips. Spanner initiates the Paxos replication in parallel with the commit wait. For a globally replicated system where network latency to other datacenters can be 100ms or more, the small commit wait is often entirely hidden by the much larger replication latency.

By keeping clock uncertainty low and overlapping the wait with existing network latency, Spanner provides external consistency without a significant performance penalty compared to systems with weaker guarantees.

Conclusion

In this lesson, we have uncovered the mechanism that allows Spanner to provide its strongest and most famous guarantee: external consistency. We saw that naive use of physical or logical clocks is insufficient to preserve causal orderings that happen outside the database system itself.

The key takeaways are:

• External consistency requires that the transaction serialization order respects the real-world (wall-clock) order of non-overlapping transactions.
• TrueTime is a clock API that solves this problem not by providing a perfect clock, but by exposing a bounded uncertainty interval [earliest, latest].
• Spanner uses a two-part protocol: it assigns a commit timestamp from the future-most end of the interval ($s=\text{TT.now().latest}$) and then enforces a commit wait until the present-most end of a new interval has passed that timestamp ($\text{TT.now().earliest}>s$).
• This "commit wait" ensures that the absolute time advances past a transaction's commit timestamp before its effects are made visible, guaranteeing that commit timestamps correctly reflect the flow of real-world time.
• The performance overhead of the wait is minimized by keeping clock uncertainty low (via GPS and atomic clocks) and by overlapping the wait with the unavoidable network latency of replication protocols like Paxos.

We have now examined 2PC, 2PL, Paxos, and TrueTime in relative isolation. In our next lesson, we will synthesize this knowledge to analyze how Spanner implements a globally distributed read-write transaction from start to finish, seeing how all these components work together in concert.