How Cloud Spanner Works Internally: TrueTime, Paxos Replication, and the Globally-Distributed Architecture Behind Consistent Reads at Any Scale

Most distributed databases pick two out of three: strong consistency, high availability, horizontal scalability. Cloud Spanner picks all three, and understanding how it manages that without violating the CAP theorem requires looking at what it actually does rather than what the marketing says. The short answer: it relies on a hardware-backed clock abstraction that bounds time uncertainty to a few milliseconds, and it builds its entire transaction protocol on top of that bound.

This article traces Spanner’s architecture from data placement through transaction execution through schema evolution. It is aimed at engineers who need to reason about what Spanner is actually doing when they use it, not at engineers evaluating whether to use it.

Data Model: Directories, Splits, and Interleaving

Spanner organizes data into tables, but the physical unit of placement is a directory. A directory is a contiguous key range within a table, and every directory maps to exactly one Paxos group. Key ranges stay together unless Spanner decides to split them.

Splits happen automatically based on load and size. Spanner’s background processes monitor each directory and split it when it exceeds roughly 8 GB or when request throughput concentrates on a narrow key range. The split point selection tries to find a natural boundary that distributes load evenly across the available replicas.

This matters because it defines where hotspots form. If your primary key is a monotonically increasing integer (auto-increment, timestamp-prefixed, UUID v1), all inserts land on the same split and overwhelm a single Paxos group leader. The standard advice is to use bit-reversed sequence numbers or hash-prefix keys to scatter writes across splits from the start.

Interleaved tables are Spanner’s mechanism for co-locating parent and child rows physically. When you declare a child table with INTERLEAVE IN PARENT, rows from the child table are stored adjacent to their parent row in the same sorted file structure. The result is that a read joining a parent to its children requires no cross-machine round-trip, which is a significant win when the join selectivity is high (fetch one user and all of their orders, not all users and all orders).

CREATE TABLE Users (
  UserId  INT64 NOT NULL,
  Email   STRING(255) NOT NULL,
) PRIMARY KEY (UserId);

CREATE TABLE Orders (
  UserId   INT64 NOT NULL,
  OrderId  INT64 NOT NULL,
  Amount   FLOAT64,
) PRIMARY KEY (UserId, OrderId),
  INTERLEAVE IN PARENT Users ON DELETE CASCADE;

The catch: interleaving forces both tables to share the same key prefix, which means they split together. You cannot interleave a table that generates dramatically different write volume than its parent without accepting that both will follow the same split trajectory.

TrueTime: Bounded Clock Uncertainty as a First-Class Primitive

Most distributed systems avoid relying on wall clocks for correctness. NTP drift is unpredictable, and two machines claiming the same timestamp can actually be microseconds to milliseconds apart. Spanner takes a different approach: it quantifies the uncertainty and builds it into the protocol.

The TrueTime API exposes three methods: TT.now(), TT.after(t), and TT.before(t). The critical one is TT.now(), which returns an interval [earliest, latest] rather than a point. The interval represents the range within which the true current time is guaranteed to fall. The width of this interval, called epsilon (ε), is typically 1 to 7 milliseconds in Google’s deployments and is bounded by a combination of GPS receivers and atomic clocks deployed in each datacenter.

The GPS receiver and atomic clock serve different failure modes. GPS receivers are accurate but can be jammed or denied. Atomic clocks drift at a known, bounded rate (a few microseconds per day for cesium standards). By cross-referencing both sources at each Time Master server and having those servers serve time to every Spanner process, the system achieves a clock synchronization uncertainty that is small enough to use as a correctness mechanism rather than something to be avoided.

The key invariant is: if transaction T1 commits before T2 starts (in real time), then T1’s commit timestamp is less than T2’s commit timestamp. This property is called external consistency, and it is strictly stronger than serializable isolation. Serializable databases order transactions logically; externally consistent databases ensure that logical order matches the real-world order that clients observe.

Paxos Replication: Leader Leases and Long-Lived Groups

Each Spanner directory lives in a Paxos group: a set of replicas (typically 5, spanning at least 3 zones) that run the Paxos consensus protocol to agree on a log of mutations. Paxos requires a quorum (3 of 5) to commit any write.

Vanilla Paxos requires a leader election for every log entry. That is too slow for a transactional database. Spanner uses leader leases: the current Paxos leader holds a timed lease (10 seconds by default) during which it can accept writes and generate commit timestamps without re-electing. The leader renews its lease before it expires using a quorum acknowledgment. Followers grant their lease extension votes unconditionally as long as they have not voted for a different leader.

The lease mechanism means reads can be served locally from the leader without contacting followers, as long as the timestamp being read falls within the lease period. This is how Spanner achieves low-latency reads despite being a multi-replica system.

One important constraint: when a leader lease expires and a new leader is elected, the new leader must wait until its TrueTime interval is entirely after the old leader’s maximum possible lease end time. This avoids any window where two replicas believe they are the leader simultaneously, which would violate the single-writer guarantee.

Read/Write Transactions: Two-Phase Locking with Wound-Wait

Spanner’s read/write transactions use a two-phase locking (2PL) protocol. A transaction acquires shared locks on rows it reads and exclusive locks on rows it writes. Locks are held at the granularity of cell (single column value), row, or key range, depending on what the transaction touches.

Deadlock prevention uses wound-wait: when a higher-priority transaction (one that started earlier) waits for a lock held by a lower-priority transaction, the lower-priority transaction is aborted (wounded). This prevents circular wait cycles without requiring a global deadlock detector, at the cost of aborting some transactions that would not have deadlocked.

The transaction execution flow is:

1. The client sends reads to the appropriate Paxos group leaders, acquiring shared locks.
2. The client buffers writes locally.
3. On commit, the client selects one participant as the transaction coordinator.
4. The coordinator runs two-phase commit (2PC): it sends PREPARE messages to all participant Paxos groups (any group that holds a lock for this transaction), waits for acknowledgments, then sends COMMIT once a quorum responds.
5. Before the coordinator can commit, it calls TT.now() and waits until TT.after(s) is true for the assigned commit timestamp s. This commit wait ensures that no future transaction can be assigned a timestamp less than s, even on a clock that is running slightly fast. The wait is typically bounded by 2ε (twice the current clock uncertainty), which is 2 to 14 milliseconds in practice.

The commit wait is the cost of external consistency. It is not optional: without it, a transaction that reads after T2 commits could observe a state that appears to predate T1, violating the “writes are visible in the order they happened” guarantee.

// Pseudocode illustrating commit wait
s = TT.now().latest          // assign commit timestamp
prepare_all_participants()   // 2PC prepare phase
wait_until(TT.after(s))      // commit wait: block until true wall time > s
commit_all_participants()    // 2PC commit phase
release_locks()

Read-Only Transactions: Snapshot Reads Without Locking

Read-only transactions are where Spanner’s design really pays off. They acquire no locks, generate no log entries, and can be executed on any up-to-date replica.

Every Spanner replica tracks a value called t_safe: the maximum timestamp at which it can guarantee that no future write will arrive with a lower timestamp. A replica can serve a read at timestamp t if t <= t_safe. The replica computes t_safe as the minimum of two values: the safe time from the Paxos log (the timestamp of the last applied log entry from the leader) and the safe time from prepared but not yet committed transactions (a pessimistic bound based on what might still commit).

The client specifies a read timestamp when initiating a read-only transaction. There are two useful strategies:

Strong reads: Use TT.now().latest as the timestamp. This guarantees reading the most recently committed state, but may require waiting for follower replicas to catch up. Strong reads are served only by the leader or a replica that has applied all log entries up to that timestamp.

Bounded staleness reads: Allow the client to specify a maximum staleness (e.g., “no more than 15 seconds old”). The system can then route to any replica that satisfies the staleness bound, reducing latency and allowing load balancing across replicas in distant regions.

This is fundamentally different from eventually consistent reads in other databases. The staleness in Spanner is a bound on real time, not an approximation. If you request data no older than 15 seconds, you are guaranteed to never see data that is 16 seconds old.

Query Execution: Distributed Query Optimizer

Spanner’s query engine compiles SQL into a distributed execution plan. The planner is aware of the physical data placement, so it generates plans that minimize data movement across the network.

Key behaviors worth knowing:

Local joins via interleaving: When two tables are interleaved, Spanner can execute a merge join locally on the same Paxos group leader, pushing join execution to the data layer. For joins that require cross-split access, Spanner uses a Distributed Union operator that fans out sub-reads to multiple groups and assembles the result.

Scan avoidance: Spanner can push filter predicates down to the storage layer. For indexed columns, the query planner uses secondary indexes to avoid full table scans. Secondary indexes in Spanner are themselves tables stored as separate directories, which means they can end up in different Paxos groups from their base table. Reads that need to join a secondary index back to the base table may require a distributed operation.

Parallel query execution: For analytical queries that touch many splits, Spanner uses a distributed sort and aggregation model similar to MapReduce. This is generally less efficient than column-oriented systems like BigQuery for pure analytics workloads, but it provides reasonable performance for mixed OLTP/OLAP patterns at the expense of compute cost.

Schema Changes: Non-Blocking and Phased

Schema changes in Spanner are non-blocking by design. Adding a column, creating an index, or changing a constraint does not lock the table or interrupt reads and writes.

The mechanism is a phased schema change protocol. When you issue a DDL statement (like CREATE INDEX or ALTER TABLE ADD COLUMN), Spanner enters a series of phases where both the old and new schema are simultaneously valid. During the transition, reads and writes are served under whichever schema phase they are in. The database converges to the new schema only after all replicas have applied all writes under the old schema.

For CREATE INDEX, the process looks roughly like this:

1. Index is created as empty. New writes populate the index going forward.
2. A background backfill process reads the existing base table and populates the index for historical data.
3. Once backfill completes and all pending writes are indexed, the index becomes active.
4. Reads can use the index.

The implication: index creation on a large table takes time proportional to the table size, and you can observe writes to the base table completing during the backfill. This is safe because the write protocol writes to both the base table and the index atomically within the same Paxos group.

The tradeoff against systems like PostgreSQL’s CREATE INDEX CONCURRENTLY is that Spanner handles this globally across all splits and all replicas without any blocking, but the convergence time scales with data size and replica spread. A large schema change on a globally distributed table with millions of splits can take hours.

Production Considerations

Split management and hotspots: Monitor spanner.googleapis.com/api/request_count by operation type and watch for latency spikes on narrow key ranges. If 95th_percentile write latency on one split diverges from others, you likely have a hotspot. Rotate primary keys to use hash-prefixed or bit-reversed sequences. Spanner’s auto-split will eventually relieve the pressure, but it lags behind write bursts by design.

IAM and access control: Spanner uses IAM roles at the instance, database, and table level. Fine-grained table-level permissions (read-only on specific tables, write on others) are important for multi-tenant databases. The spanner.databaseUser role grants read/write on all tables; for tighter control, use VPC-SC (VPC Service Controls) to restrict which networks and identities can reach the Spanner endpoint.

Backup and PITR: Spanner offers two recovery mechanisms. Database backups are full consistent snapshots that can be restored to a new database in the same instance or a different region. Point-in-time recovery (PITR) retains the change log for up to 7 days and allows restoring to any second within that window. PITR storage costs are proportional to the change rate; high-write workloads accumulate PITR log quickly. Set retention to the shortest window your SLA requires.

Commit latency vs. external consistency: If your application can tolerate weaker ordering guarantees between transactions that do not share causal dependencies, you can use ISOLATION_LEVEL = SERIALIZABLE with LOCK_MODE = SHARED for read-only transactions and minimize commit wait overhead. For most OLTP workloads, the 2 to 14 ms commit wait is below client round-trip time and not noticeable in practice. It matters most for high-frequency write pipelines where you are measuring individual commit latency.

Instance configuration: Single-region configurations offer lower latency (within-zone replica propagation) but no regional failover. Multi-region configurations (nam6, eur3, nam-eur-asia1, etc.) add 5 to 40 ms to commit latency due to cross-region Paxos quorum but provide 99.999% availability guarantees and survive zone and region outages.

Tradeoffs Comparison

Dimension	Cloud Spanner	CockroachDB	TiDB	YugabyteDB	Aurora (MySQL/Postgres)
Consistency model	External consistency (stronger than serializable)	Serializable	Snapshot isolation + serializable opt-in	Serializable	Read committed (MySQL default), Serializable available
Distribution model	Paxos groups per split, automatic sharding	Raft groups per range, automatic sharding	TiKV Raft groups, PD placement driver	Tablet-based Raft, shard leader election	Single-region primary; read replicas optional
Clock mechanism	TrueTime (GPS + atomic clock, hardware-backed)	Hybrid logical clock (HLC, software)	Centralized TSO (TiDB PD single timestamp oracle)	Hybrid logical clock (HLC, software)	NTP (single-node clock, no distribution concern)
Cost model	Per-node + per-operation; expensive for write-heavy workloads	Self-hosted or cloud; more predictable at scale	Self-hosted; low cost on-prem	Self-hosted or cloud; competitive for mid-scale	Serverless or provisioned; cost-effective for single-region
MySQL/Postgres compatibility	ANSI SQL (not MySQL or Postgres wire protocol)	Postgres wire protocol (pgwire)	MySQL wire protocol	Postgres wire protocol (YSQL) + Cassandra (YCQL)	Native MySQL or Postgres
Horizontal write scaling	Yes, across splits/regions automatically	Yes, across ranges	Yes, TiKV handles sharding	Yes, tablet splitting	No (single-writer primary)
Schema change model	Non-blocking phased DDL, global backfill	Online schema changes (declarative DDL)	Online DDL via F1 paper approach	Online DDL with backfill	Requires pt-online-schema-change or gh-ost for large tables
Sweet spot	Global OLTP requiring strict consistency with multi-region HA; acceptable per-operation cost	Postgres-compatible global OLTP; teams who want self-hosted or cloud-portable	Existing MySQL workloads needing horizontal scale; HTAP with TiFlash	Postgres-compatible global OLTP; teams wanting Cassandra-style multi-region	Single-region relational workloads; existing MySQL/Postgres apps; cost-sensitive deployments

The clearest differentiator between these systems is the clock mechanism. TrueTime’s hardware backing is what allows Spanner to provide external consistency without a centralized timestamp oracle and without waiting for a fixed epoch. CockroachDB and YugabyteDB use hybrid logical clocks, which are software-based and add uncertainty; they achieve serializability but not external consistency. TiDB uses a centralized TSO in the Placement Driver, which provides a global timestamp but is a single point of contention and requires careful HA configuration. Aurora sidesteps the problem entirely by not distributing writes.

For teams building global applications where the correctness of read-after-write semantics across regions is a hard requirement, Spanner’s architecture is the most defensible. For teams that need Postgres compatibility or predictable infrastructure costs, CockroachDB and YugabyteDB are the serious alternatives. TiDB is the right choice when you have an existing MySQL workload that needs to scale beyond what a single-writer primary can handle.

Understanding Spanner’s internals is useful even if you never run it in production. The TrueTime insight (quantify uncertainty rather than ignore it) and the split-based directory model (explicit co-location via interleaving) are design principles that apply to any system that needs to coordinate state across machines. Most distributed system bugs trace back to implicit assumptions about time and data locality, the same assumptions Spanner was built to eliminate.