Cross-Shard Transactions Beyond Spanner

1. The Centralized Timestamp Oracle: Google's Percolator

Before Spanner, Google addressed the need for distributed transactions with a system called Percolator, designed for incrementally updating the web search index on top of Bigtable. Understanding Percolator is valuable not only for its historical context but also because its architectural pattern—using a centralized Timestamp Oracle (TSO)—is found in many modern distributed databases like TiDB.

Percolator implements a 2PC protocol to provide Snapshot Isolation, a slightly weaker guarantee than Spanner's serializability. Instead of TrueTime, it relies on a single, highly-available service—the Timestamp Oracle—to issue monotonically increasing timestamps.

To understand the architecture and its implications, let's turn to an article that compares Percolator and Spanner.

As you've read, Percolator's design makes a few key trade-offs:

• Centralized TSO: While the TSO is made fault-tolerant (e.g., using Paxos), it remains a potential scalability bottleneck and a single point of contention for all transactions, which must contact it twice. This contrasts with Spanner's TrueTime, where time reading is a local API call on every machine.
• Snapshot Isolation: Percolator provides Snapshot Isolation, which is vulnerable to certain anomalies like write skew that serializability prevents.
• Lazy Cleanup: The system's tolerance for higher latency, acceptable for its offline indexing workload, allows for a "lazy" approach to cleaning up failed transaction locks, which would be unacceptable in a user-facing OLTP system.

The architecture of Percolator is shown in the diagram below, highlighting its relationship with Bigtable and other core Google infrastructure components of that era.

Percolator represents a successful but specialized solution. Its design choices were tailored for a high-throughput, non-interactive system, paving the way for the more general-purpose, low-latency design of Spanner.

2. Deterministic Ordering: The Calvin Approach

While Spanner and Percolator use variants of 2PC and optimistic concurrency, a different school of thought argues for a deterministic approach. The Calvin protocol, developed at Yale University, is the leading example of this philosophy.

The core idea of Calvin is to separate transaction ordering from transaction execution.

1. Sequencing/Logging: All transaction requests are first sent to a global, replicated log. This log establishes a single, definitive serial order for all transactions in the system before they are even executed. This sequencing layer is typically built using a consensus protocol like Paxos or Raft.
2. Deterministic Execution: Once the order is set, each node in the database can execute the transactions from the log. Since the execution is deterministic (i.e., the transaction code has no external dependencies like now()), all nodes will reach the exact same state without needing to communicate with each other during execution.

This design cleverly avoids the need for 2PC for cross-shard transactions. Atomicity is guaranteed by the log; a transaction is either in the log or it isn't. If a node executing a transaction fails, it can recover by re-reading the log and replaying the transactions.

Let's examine a comparison of the Calvin and Spanner architectures.

The key differences boil down to a trade-off between optimistic and pessimistic approaches:

Calvin's architecture is a powerful alternative when strict serializability is required but specialized clock hardware is unavailable. Systems like FaunaDB have adopted this approach.

3. Decoupled and Optimistic: The FoundationDB Approach

FoundationDB, an open-source project now managed by Apple, presents another compelling architecture for providing strictly serializable, cross-shard transactions on commodity hardware. Its design is notable for its clear separation of concerns into a "control plane" and a "data plane."

FoundationDB uses an optimistic concurrency model similar to Spanner but with a different implementation. The key components of its transaction subsystem are:

• Master: A singleton process responsible for assigning commit versions.
• Proxies: The entry point for client transactions. They obtain commit versions from the master.
• Resolvers: A sharded, stateless layer that checks for read-write conflicts.
• Transaction Logs: A write-ahead log for durably storing committed transactions before they are moved to permanent storage.
• Storage Servers: The ultimate home for the data, organized into shards.

A transaction proceeds as follows:

1. The client starts a transaction and gets a read version from a proxy. All reads during the transaction are performed against the database snapshot at this version.
2. The client buffers its writes locally.
3. Upon commit, the client sends its read set and write set to a proxy. The proxy gets a commit version from the master.
4. The proxy sends the read set to the resolvers, which check if any of the keys read by the transaction have been written to between the read version and commit version.
5. If there are no conflicts, the transaction is committed to the transaction logs and eventually propagated to the storage servers. If there is a conflict, the transaction is aborted, and the client must retry.

The following video provides a technical overview of this architecture from one of its engineers.

FoundationDB's design cleverly handles cross-shard transactions because the transaction subsystem (Master, Proxies, Resolvers) provides a single, unified view of the entire keyspace. The client and proxies don't need to reason about shards; they submit the transaction, and the system resolves conflicts across the entire database. This provides strong guarantees without specialized hardware, at the cost of requiring applications to handle transaction retries in cases of high contention.

4. Loosening the Reins: The Saga Pattern

All the strategies we've discussed so far aim to provide ACID guarantees, particularly atomicity and isolation. However, in many modern architectures, especially those built on microservices, enforcing strong consistency via protocols like 2PC is often impractical due to tight coupling and performance overhead.

The Saga pattern offers an alternative. A Saga is a sequence of local transactions where each transaction updates data within a single service. If a local transaction fails, the saga executes a series of compensating transactions to undo the changes made by the preceding successful transactions.

This pattern trades ACID properties for what is sometimes called BASE (Basically Available, Soft state, Eventual consistency). It guarantees business-level atomicity ("all or nothing" from a user's perspective) but not technical atomicity, allowing for temporary inconsistencies.

There are two main ways to implement Sagas:

• Orchestration: A central coordinator (the orchestrator) tells each participant what to do and when. If a step fails, the orchestrator is responsible for triggering the compensating transactions.
• Choreography: There is no central coordinator. Each service publishes events when it completes its work. Other services subscribe to these events and trigger their own local transactions in response.

This video provides an excellent introduction to the Saga pattern and contrasts it with 2PC.

The image below provides a useful summary of the trade-offs between 2PC, Saga, and the related Outbox pattern (which ensures that events are reliably published after a database commit).

Choosing the Saga pattern is a significant architectural decision. It's well-suited for long-running business processes that can tolerate eventual consistency and where service autonomy is a primary goal. However, it introduces considerable complexity in implementation, especially around defining, testing, and ensuring the reliability of compensating transactions.

Conclusion

In this lesson, we have explored a diverse set of strategies for handling cross-shard transactions in systems that cannot rely on Spanner's unique TrueTime infrastructure. You are now equipped to analyze the trade-offs between these different approaches.

Our key takeaways are:

• Percolator-style systems use a centralized Timestamp Oracle (TSO) to provide strong consistency (typically Snapshot Isolation) with a 2PC protocol. This is a common pattern but introduces a potential scalability bottleneck.
• Calvin-style systems use a deterministic ordering log to establish a global transaction order before execution. This avoids the need for 2PC and is resilient to clock skew but can introduce higher baseline latency.
• FoundationDB's architecture provides strict serializability via a decoupled, optimistic concurrency model with a Master, Proxies, and Resolvers. It handles cross-shard transactions transparently but relies on client-side retries to manage contention.
• The Saga pattern abandons strong consistency in favor of eventual consistency through local transactions and compensating actions. It is highly flexible and scalable, making it ideal for many microservice applications, but requires careful design to manage the logic of compensation.

Your role as a senior engineer is not to know a single "best" answer but to understand this landscape of trade-offs. The choice between these strategies depends entirely on the specific requirements of the system: the required consistency level, latency tolerance, development complexity, and operational environment.

In our next lesson, we will zoom in on a more granular coordination problem: designing a strategy for ensuring the exclusive execution of a critical task using a distributed lock. This is a fundamental building block in many distributed systems, often used to protect shared resources where a full distributed transaction is unnecessary or too heavyweight.