13-0-Strictly Serializable Globally-Distributed System & Spanner

Motivation of Spanner

Spanner is trying to combine four difficult properties:

1. Data is geographically replicated.
2. Data is divided across many shards.
3. Transactions are strictly serializable.
4. Read-only transactions are extremely efficient.

The key question is:

Can a global, sharded database provide strict serializability while letting read-only transactions complete without locks, aborts, or several rounds of coordination?

Background

The traditional way to support distributed transactions:

• Two-phase locking, or 2PL, provides isolation.
• Two-phase commit, or 2PC, provides atomic commitment across machines.

A read-only transaction does not modify anything, but traditional concurrency control can still make it expensive:

• Under 2PL, reads acquire shared locks.
• A long-running read may hold those locks and delay writers.
• A multi-shard read requires a coordinator.
• Lock interactions may contribute to deadlocks.
• Under OCC, the read may need validation and could abort if concurrent writes invalidate its observations.
• Wide-area round trips are especially expensive because datacenters may be geographically distant.

This is excessive overhead for a workload dominated by reads, which usually is.

Goal of Spanner

• Make read-only transactions efficient
  • One round trip
    • Even works for wide-area shards
  • Lock-free
    • No deadlocks
    • Processing reads do not block writes
  • Always succeed without abort
• Achieves strict serializability through TrueTime - time as an interval

Leveraging the Notion of Time

Spanner in short perform several tasks

• Task 1: when committing a write, tag it with the current physical time
• Task 2: when reading the system, check which writes were committed before the time this read started
• How about the serializable requirement?
  • Physical time naturally gives a total order

Invariant

If T2 starts after T1 commits, then T2 must have a greater timestamp

However, here we encounter challenges:

• Clocks are not perfect
  • Clock skew: some clocks are faster/slower
    • Clock skew may not be bounded
    • Clock skew may not be known a priori
• Thus, T2 may be tagged with a smaller timestamp than T1 due to T2’s slower clock

Therefore, it seems impossible to have perfect clocks in distributed systems.
We solve this problem via Nearly perfect clocks

Nearly perfect clocks

• Partially synchronized
  • Clock skew is bounded and known a priori
  • We don’t know the absolute time, but the range is between 1:20PM and 1:30PM
• Clock skew is short
  • A small range: [T - x, T + x]

This nearly perfect clock API enables Spanner

Questions for Strictly Serializable Multi-shard Transactions

• How are clocks made “nearly perfect”?
• How does Spanner leverage these clocks?
  • How are writes done and tagged?
  • How read-only transactions efficiently and correctly read timestamped writes?

TrueTime - time as an interval

TT.now

TrueTime does not claim to return the exact current time. It returns an interval guaranteed to contain the actual time:

TT.now() = [earliest, latest]

which guarantees:

earliest <= actual_time_of_event <= latest

The width of the interval is:

latest - earliest = 2ε

Here, ε represents the clock uncertainty or worst-case divergence.

TT.after(t)

TT.after(t) is true when TT.now().earliest > t

Because actual time is at least earliest, this implies:

actual time > t

TT.before(t)

TT.before(t) is true when TT.now().latest < t

Since actual time is no greater than latest, this proves:

actual time < t

For TrueTime to obtain a bounded interval, Google uses specialized time infrastructure, including:

• Sateliite-based clocks
• Atomic clocks
• Regular synchronization

How to enforce the Invariant using TrueTime

Why merely choosing lastest as timestamp is not enough

Let T1 write Sa and T2 write Sb:

A first attempt is:

transaction timestamp = TT.now().latest

Suppose:

T1 gets [3, 6]   -> timestamp 6
T2 gets [8, 12]  -> timestamp 12

Then, everything works as 6 < 12.

However, this only works because those intervals are conveniently separated.

Consider the wider and overlapping intervals:

T1 gets [3, 15]  -> timestamp 15
T2 gets [1, 12]  -> timestamp 12

Even if T2 physically starts after T1, the resulting timestamps are:

timestamp(T2) = 12 < 15 = timestamp(T1)

TrueTime intervals can overlap. Therefore, choosing the upper endpoint alone doesn’t automatically establish external serializability, also known as strict serializability.

To resolve this problem, we need a second mechanism: Commit wait

How commit wait enforces external serializability

The solutions to enforce strict serializability using is:

1. Choose the transaction timestamp using TT.now().latest
2. Do not report the transaction as finished until TrueTime proves that this timestamp is in the past

In simplified form:

s = TT.now().latest

perform commit work

wait until TT.after(s) == true

return commit success to the client

This guarantees:

commit timestamp < externally visible finish time

This pause is called commit wait.

Concurrency is still preserved

Consider this timeline:

Real time ──────────────────────────────────────────────>

T1:  execute ─ prepare ─ choose ts ─ commit wait ─ response
T2:              execute ─────────────────── commit
T3:                                                execute

• T2 overlaps T1, so they execute concurrently.
• T3 begins only after T1’s commit response.
• Strict serializability requires T1 to be ordered before T3.
• Because T1 and T2 overlap, real time alone does not determine their order.
  • Concurrency control will determine a valid serialization order for these concurrent transactions.

Commit wait delays only the point at which T1 is declared finished. It does not prevent other transactions from running during the wait.

Why the wait matters

Suppose T1 chooses:

TT.now() = [3, 15]
T1.timestamp = 15

At the moment of timestamp assignment, actual time could be less than 15. Spanner therefore waits until:

TT.now().earliest > 15

At that point, actual time is definitely greater than 15. Only then may T1 externally finish.

The system has effectively waited for physical time to “catch up” to the timestamp it assigned.

Internal commit versus external completion

This distinction is important:

• Spanner may have already selected the timestamp and performed internal commit operations.
• It must not tell the client that the transaction has finished until commit wait is satisfied.

The invariant refers to the transaction’s externally observable completion.

Proof that commit wait enforce the invariant

Variable	Meaning
[a, b]	TrueTime interval obtained by T1
b	T1’s selected timestamp
x	Actual time when T1 finishes
y	Actual time when the later T2 begins
[c, d]	TrueTime interval obtained by T2
d	T2’s selected timestamp

Because T2 starts after T1 finishes, we assume:

x < y

TrueTime guarantees that T2’s actual start time is inside its interval:

c <= y <= d

Because T2 selects the upper endpoint:

T2.timestamp = d

Commit wait ensures that T1 cannot finish until actual time has passed its timestamp:

b < x

Combining the relationships gives:

b < x < y <= d

Therefore:

b < d

and thus:

T1.timestamp < T2.timestamp

The proof has two essential halves:

• T1 waits until its timestamp is before its external finish time
• T2 chooses a timestamp that is at or after its actual start time

TrueTime supplies both safe comparisons even though neither machine knows the exact absolute time.

How this supports efficient read-only transactions

Once commit timestamps respect external real-time order, a read-only transaction can conceptually do the following:

1. Select one snapshot timestamp.
2. Send that timestamp to all relevant shards (for multiple item reads).
3. At each shard, read the newest committed version at or before that timestamp.
4. Combine the results into one consistent snapshot.

This requires timestamped, multi-version data.

Conclusion

TrueTime and Commit wait enable Spanner to assign each operation nearly perfect clock and enforce external serializability based on that logical time.
How read-write and read-only transactions are done utilizing these techniques are explained in 13-1-Spanner Continued