Spanner's Globally Distributed Transactions

The Spanner Transactional Machinery

Before diving into the protocol steps, let's visualize the key architectural components involved. A Spanner cluster is composed of spanservers, each managing multiple data partitions called tablets. For fault tolerance, the replicas for each tablet form a Paxos group.

Within a transaction that touches multiple Paxos groups, several roles emerge:

• Client: The application initiating the transaction.
• Participant Leader: The Paxos leader of a group involved in the transaction. It manages locks and the transaction state for its shard.
• Coordinator Leader: One of the participant leaders is designated as the coordinator for the transaction. It drives the second phase of the two-phase commit protocol.

The following diagram from the Spanner paper illustrates the software stack on a single spanserver. Note the distinct layers: the transaction manager (for distributed transactions), the lock table (for 2PL), and the Paxos layer that replicates the state of the tablet.

With this structure in mind, let's walk through the life of a distributed read-write transaction.

Anatomy of a Read-Write Transaction

A read-write transaction in Spanner proceeds through a sequence of steps orchestrated between the client and the leaders of the involved Paxos groups. The protocol is effectively a carefully integrated 2PC+2PL over Paxos, augmented by TrueTime to ensure external consistency.

The Spanner paper provides the definitive description of this process. As an aspiring Principal Engineer, being able to parse and internalize the details from such primary sources is a critical skill.

Let's break down the flow you just read about, step-by-step.

Step 1: Client-Side Buffering and Reads

A transaction begins on the client.

1. Reads: The client sends read requests to the leader replicas of the appropriate Paxos groups. These leaders acquire read locks on the requested key ranges using their local lock table. This is the first part of two-phase locking.
2. Buffering: Writes are not sent to the database immediately. Instead, they are buffered within the client library.
3. Keepalives: While the transaction is active, the client sends periodic keepalive messages to the participant leaders to prevent them from timing out and aborting the transaction.

Step 2: Two-Phase Commit - Phase 1 (Prepare)

Once the client has performed all its reads and buffered all its writes, it initiates the commit process.

1. The client chooses one of the participant leaders to act as the coordinator and sends a commit message to every participant leader. This message contains the identity of the coordinator and the buffered writes for that participant.
2. Non-Coordinator Participants: Upon receiving the commit message, each non-coordinator leader:
   • Acquires write locks for the data being modified. This completes the lock acquisition phase of 2PL.
   • Chooses a prepare timestamp, $s_{prepare}$, which must be greater than any timestamp it has assigned previously to ensure monotonicity.
   • Logs a prepare record to its replicated log via Paxos. This makes the prepare decision durable.
   • Notifies the coordinator that it is prepared, sending along its $s_{prepare}$.
3. Coordinator Participant: The coordinator leader also acquires its write locks. However, as an optimization, it does not need to write a prepare record for itself; it can move directly to the commit phase once it has heard back from all other participants.

Step 3: Two-Phase Commit - Phase 2 (Commit)

This phase is driven entirely by the coordinator leader.

1. Timestamp Selection: After receiving "prepare" confirmations (and prepare timestamps) from all participants, the coordinator chooses the final, global commit timestamp, $s$. This is a critical step governed by several rules:
   • $s$ must be greater than or equal to all participant prepare timestamps ($s\ge s_{prepare}$ for all participants).
   • $s$ must be greater than TT.now().latest at the time the coordinator received the client's commit request. This is the "Start" rule we discussed in the previous lesson.
   • $s$ must be greater than any timestamp this leader has assigned to previous transactions (monotonicity).
2. Commit Wait: The coordinator logs a commit record via Paxos. But before making the commit visible, it executes the "Commit Wait" rule: it waits until TT.after(s) is true, which means it waits until TT.now().earliest > s.
3. Overlapping Work: The latency of this wait (typically < 10ms) is almost always hidden. The coordinator initiates the Paxos replication of the commit record in parallel with the commit wait. For transactions spanning datacenters, the network latency for Paxos far exceeds the wait time.
4. Notification: After the commit wait completes, the coordinator sends the commit timestamp $s$ to the client and all other participant leaders.
5. Finalization: Each participant leader logs the final outcome, applies the writes at the exact timestamp $s$, and finally releases all locks.

The following clip from the original OSDI presentation on Spanner provides an excellent visualization of how the commit wait is integrated with 2PC.

Synthesizing the Components

The protocol you've just analyzed is a masterclass in distributed systems design, combining multiple mechanisms to achieve a powerful end result. Let's explicitly state the role of each component:

• Two-Phase Commit (2PC): Provides atomicity across shards. It ensures that the transaction either commits everywhere or aborts everywhere, even though the data is managed by different Paxos groups.
• Two-Phase Locking (2PL): Provides serializability. By acquiring read and write locks at the leaders and holding them until the transaction concludes, Spanner prevents conflicting concurrent operations and ensures an equivalent serial execution order.
• Paxos: Provides fault tolerance. Every critical state change—the prepare records, the commit/abort decision, the transaction manager's state—is written to a replicated log. If a leader fails, a new leader is elected, reads the log, and can resume the protocol exactly where the old one left off. This makes the 2PC coordinator non-blocking in practice.
• TrueTime: Provides external consistency. The "Start" and "Commit Wait" rules, enforced by the coordinator using TrueTime's uncertainty interval, guarantee that the globally assigned commit timestamps respect the real-world, wall-clock order of non-overlapping transactions.

This combination of 2PC+2PL over Paxos provides fault-tolerant serializability. Adding TrueTime elevates this to fault-tolerant external serializability, Spanner's signature guarantee.

To reinforce this complex interaction, let's review an alternative explanation. The following blog post provides a clear, concise summary of the same process.

Conclusion

In this lesson, we have finally assembled the complete puzzle of a Spanner distributed transaction. We traced the entire lifecycle of a read-write transaction, from the client buffering writes to the final, globally consistent commit.

Key takeaways from this synthesis are:

• Spanner implements a protocol that can be described as Two-Phase Commit and Two-Phase Locking over Paxos leaders.
• The client drives the first phase of 2PC by sending writes and a coordinator identity to all participants.
• The coordinator leader drives the second phase, where it is responsible for choosing a globally unique and externally consistent commit timestamp using TrueTime.
• The crucial "Commit Wait" step, performed by the coordinator, ensures that the real-world time advances past the chosen commit timestamp before the transaction's effects become visible, thus guaranteeing external consistency.
• Paxos underpins the entire process, ensuring that the state of the transaction managers and lock tables is durable and available, allowing the system to recover from leader failures without violating correctness.

You now have a deep, integrated understanding of Spanner's core transactional engine. This knowledge is not only crucial for your goal of operating at a Principal Engineer level but also provides a robust mental model for reasoning about the trade-offs in any large-scale, strongly consistent database.

In our next lesson, we will step back and compare Spanner with its predecessor, Bigtable. This comparison will highlight the evolution of Google's database philosophy and clarify the distinct use cases, data models, and consistency guarantees offered by each system.