13-1-Spanner Continued

Spanner continued

13-0-Strictly Serializable Globally-Distributed System & Spanner established the central invariant:

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

Spanner enforces it by:

1. Choosing a commit timestamp at least as large as TT.now().latest.
2. Waiting until TT.after(commit_timestamp) is true before externally finishing.

Spanner continued answers the implementation questions:

• How are multi-shard read-write transactions executed?
• How does every shard agree on one commit timestamp?
• How does a read-only transaction select its snapshot?
• When can a shard safely answer a historical read?
• Why might a lock-free read still have to wait?

Three different mechanisms

Spanner combines three major mechanisms:

Mechanism	Purpose
2PL	Isolation and serializability between conflicting transactions
2PC	Atomic commit across multiple shards
Paxos	Fault-tolerant replication within each shard

It is useful to separate them.

Suppose a transaction updates shards A, B, and C.

• 2PL controls conflicting reads and writes.
• 2PC ensures A, B, and C all commit or all abort.
• Each shard uses Paxos to replicate its prepare and commit records across replicas.

A compact description is therefore:

2PL + 2PC across Paxos-replicated shards

2PC runs among the leaders of shards A, B, and C. Each leader uses its local Paxos group to make its part of the decision durable.

How multi-shard read-write transactions are done

There are three phases:

Execute -> Prepare -> Commit

Suppose an example multi-shot transaction request:

T = {
	a = read(A),
	write(A = a + 1),
	write(B = a + 1),
	write(C = a + 1)
}

Phase1: Execute

During execution:

1. The client asks to read A
2. The shard serving A acquires a shared/read lock
3. It returns the newest available value, such as A = a
4. The client computes the new values
5. The writes are buffered rather than immediately applied

Conceptually:

read A -> a

buffer:
    A = a + 1
    B = a + 1
    C = a + 1

The writes depend on the value returned by the read. Thus, the reads are protected by locks so that another transaction cannot invalidate the transaction’s assumptions before it commits.

Phase2: Prepare

One shard is chosen as the 2PC coordinator.

The client sends each shard:

• Its buffered write
• The transaction identity
• The coordinator’s identity

Each participant then:

1. Attempts to acquire the required exclusive/write lock
2. Writes a prepare record through its Paxos group
3. Waits for that prepare record to become durable
4. Sends Ok to the coordinator once preparation succeeded

The prepare record means:

“I have reserved the required resources, and I promise that I can commit this transaction later if the coordinator instructs me to.”

The participant must not forget this promise after a machine failure, which is why the prepare record is replicated through Paxos.

Phase 3: Commit or abort

After collecting all participant responses:

if every participant replied OK:
    decision = COMMIT
else:
    decision = ABORT

For a commit:

1. The coordinator durably logs the commit decision through Paxos, applies writes and release all locks
2. It sends the decision to the participants
3. Each participant logs the decision through its own Paxos group, applies writes and release the locks
4. The coordinator sends result to client either afeter its log commit or after ack

For an abort:

• The writes are discarded and locks are released.

How the transaction receives one timestamp

Every committed read-write transaction needs one global commit timestamp to ensure consistent external serializability, even if it modifies several shards.

The participants help establish a timtstamp that is safe for every shard.

Participant timestamp proposal

Participants B and C prepare timestamps such as:

ts_B
ts_C

Each proposal must be greater than the timestamps of writes already applied at that participant.

Coordinator timestamp selection

The coordinator receives all participant proposals and chooses one final timestamp s satisfying all constraints:

s >= TT.now().latest
s > ts_B
s > ts_C
s > timestamps already applied at the coordinator

This final timestamp is sent to every participant:

T.commit_ts = s

Thus the transaction has one position in the global serialization order, not a separate position at each shard.

Commit wait overlaps useful work

After selecting s, the coordinator must ensure:

TT.after(s) == true

This doesn’t mean the coordinator sits idle.

Instead, the commit wait overlaps Paxos commit logging:

                 ┌──── commit wait ────┐
choose s ────────┼── replicate commit ─┼── safe completion
                 └─────────────────────┘

because the transaction needs both conditions:

1. Durability condition: the commit decision has been safely logged
2. Time condition: actual time has definitely passed s

Once both are satisfied, the transaction can safely progress to external completion.

How read-only transactions works

Spanner retains timestamped versions of data. A read-only transaction chooses one timestamp t_read and reads every shard at that same logical time.

The client chooses:

t_read = TT.now().latest

It then asks all required shards for:

newest committed version with commit_timestamp <= t_read

Using the same timestamp across all shards is crucial. Otherwise, the transaction could combine states from incompatible moments.

How read timestamp is externally consistent

Suppose write transaction W finished before the read-only transaction began.

Commit wait guarantees:

W.commit_ts < W.finish_time

Because the read starts later:

W.finish_time < read_start_time

TrueTime gurantees:

read_start_time <= TT.now().latest

Therefore:

w.commit_ts < W.finish_time < read_start_time <= t_read

So the read’s snapshot necessarily includes W.

Example

Suppose a read-only transaction:

T = read(A, B, C)
t_read = 10

Shard A

For a read at timestamp 10:

W1.ts = 5 <= 10
W2.ts = 13 > 10

No waiting is necessary since W1 is committed.
Therefore, A returns W1.

Shard B

Even if W2 eventually commits, it will be ordered after the requested snapshot. It will be ordered after the requested snapshot. It cannot change what the database contained at timestamp 10.

The shard can therefore ignore W2 for this read and return W0 immediately.

Shard C

Shard C has:

W0 committed at 0
W3 prepared with timestamp bound 8

The read timestamp is 10:

8 < 10

At this point, the shard does not yet know the final outcome of W3.

Possibilities include:

• W3 aborts: return W0
• W3 commits with final timestamp at or before 10: return W3
• W3 commits with final timestamp after 10: return W0

The shard cannot safely choose until W3 is resolved, so the read waits. This safety borderline is determined by Safe-time.

In above example, W3 eventually commits at timestamp 15, so the shard return W0.

Why this read is efficient

Spanner read-only transaction is efficient becuase:

• It’s lock-free because it does not acquire shared locks that could delay writes
• One round trip
• Never aborts because of concurrent writes. It may wait, but once safe, it returns the appropriate historical versions

Safe-time

tsafe is a certainty boundary.

If a shard says:

tsafe = 12

It promises:

“Everything at timestamp 12 or earlier has been completely decided.

Therefore:

read timestamp <= tsafe -> safe to answer
read timestamp > tsafe -> may have to wait

Two things determine safe time

1. Paxos log replication progress

The shard’s Paxos log orders replicated writes monotonically.

Conceptually:

Paxos write at 5
Paxos write at 8
Paxos write at 13

If Paxos has safely processed a write at timestamp 13, then—because writes are ordered monotonically—it knows an ordinary Paxos write at timestamp 7 cannot suddenly be inserted later.

This produces:

tsafe_Paxos

which means:

“The replicated log has definitely progressed this far.”

2. Unresolved prepared transactions

A distributed transaction might be prepared but not yet committed or aborted:

W3 prepared with timestamp lower bound 8
final result: unknown

Until the outcome is known, it may affect a snapshot at timestamp 10. This limits:

tsafe_TM

Here, TM means transaction manager.

It means:

“Every prepared transaction that could affect history through this point has been resolved.”

We take the minimum safe time

Both systems must agree that the history is safe through:

tsafe = min(tsafe_Paxos, tsafe_TM)

For example:

tsafe_Paxos = 18
tsafe_TM = 8

Paxos has progressed far enough, but an unresolved transactions still threatens the history after its timestamp 8.

So a read at timestamp 10 must wait until the write is resolved.

Serializable stale snapshot reads

A stale snapshot read deliberately asks about an old time.

Suppose the current time is 100:

current time = 100
requested snapshot = 40
shard safe time = 85

The shard already knows its complete history through timestamp 40. It can answer immediately without waiting for current transactions.

• Why is it not strictly serializable?
  • Old timestamp cannot ensure real-time order, therefore not externally consistent.
• Better perfrmance: one-round and non-blocking
  • No waiting in any cases
• Can we have this performance but still strictly serializable?
  • e.g., one-round, non-blocking, and strictly serializable
  • This question is answered in 14-SNOW Theorem

Tradeoff

Read type	Requested time	May wait?	Strictly serializable?
Current snapshot	Around now	Possibly	Yes
Stale snapshot	Far in the past	Usually not	No