Google Cloud Spanner is a fully managed, horizontally scalable, globally distributed, and strongly consistent database service, which provides both traditional relational capabilities and the horizontal scalability typical of NoSQL databases. To understand how Spanner manages to provide linearizability and serializability across distributed transactions, it's crucial to delve into two of its foundational components: atomic clocks and a synchronization primitive known as TrueTime.

Understanding TrueTime

TrueTime is an API provided by Google Spanner that gives access to a globally synchronized clock, leveraging both GPS and atomic clocks across Google's data centers. TrueTime provides two critical timestamps:

• TT.now(): This gives the current time as an interval [earliest, latest]. It asserts that the real time will be within this interval when we call TT.now().
• TT.after() and TT.before(): These provide timestamps that are definitively after or before any observed TT.now().

How TrueTime Enables Consistency

To guarantee consistency, Spanner uses two time-related procedures:

1. Commit Wait: Every transaction commit in Spanner undergoes a "commit-wait" phase toward its end. It waits until TT.after(max_commit_timestamp), ensuring that any transaction observing a timestamp later than max_commit_timestamp sees all effects of the committed transaction. This helps maintain linearizability, where the system appears as if all transactions were executed in some sequential order consistent with their real-time ordering.
2. Timestamp Assignment for Read Transactions: When a read transaction starts, it receives a timestamp from TT.now().latest. This timestamp represents a point in history and ensures the transaction reads a consistent snapshot of the database at that point, maintaining serializability by providing order to overlapping transactions.

Linearizability in GCP Spanner

Linearizability in the context of distributed transactions ensures that all operations appear instantaneously at some point between their start and end times. Given Spanner’s commit-wait phase, which ensures that writes within a transaction become visible only after a globally acknowledged timestamp, the system ensures that no stale reads occur. This is particularly vital because Spanner operates across regions, and without such synchronization, data anomalies might arise.

Serializability in GCP Spanner

Serializability ensures that transactions result in a state that could be achieved if the transactions were executed serially. Spanner uses timestamps derived from TrueTime to order transactions globally. By providing each transaction a unique, globally meaningful commit timestamp, Spanner can serialize transaction execution and effectively order transactions as if they were executed one after another.

Examples

Consider a situation where Transaction A writes to a database record at 10:02:30, and Transaction B reads the same record at 10:02:31. Even if Transaction A and B are happening on different continents, Spanner’s use of TrueTime ensures:

• A receives a commit timestamp t1 with TT.after(t1).
• B receives a read timestamp t2 with t2 > t1 due to TrueTime synchronization.

This ensures B reads the data as modified by A, respecting transactional order.

Summary Table

Conclusion

Spanner's architecture cleverly uses hardware (atomic clocks), unique software mechanisms (TrueTime), and innovative transaction-processing protocols to achieve consistency models such as linearizability and serializability, which are typically challenging in distributed systems. The end result is a system that offers the benefits of both relational and NoSQL databases, suitable for a range of applications requiring high availability, durability, and consistent cross-region transactions.