Spanner Internals

Why Spanner Exists

Spanner Architecture

Key Numbers

TrueTime — Time as a Bounded Interval

Every distributed database has to deal with clock skew. Most pretend it doesn't exist, then patch over the symptoms with vector clocks, hybrid logical clocks, or last-write-wins. Spanner took the opposite path: expose the uncertainty.

The TrueTime API has three calls:

TT.now()    → returns interval [earliest, latest]   // truth lies somewhere inside
TT.after(t) → true if t is definitely in the past
TT.before(t)→ true if t is definitely in the future

Under the hood, TrueTime is implemented by a fleet of GPS receivers and atomic clocks in every data center, with a daemon on every machine that polls them and computes a tight bound on its own clock's drift. The half-width of the interval, ε ("epsilon"), is typically around 4 ms on average and bounded under 7 ms even in worst case. By making clock uncertainty explicit and small, Spanner can use timestamps as the global ordering mechanism.

The trick is the commit-wait protocol: when a transaction commits at timestamp s, the leader waits until TT.after(s) returns true before acknowledging the commit to the client. That guarantees no concurrent transaction can be assigned a later timestamp than s while still appearing earlier in real time. Total wait is roughly 2ε ≈ 7 ms — the cost of external consistency.

Paxos Groups and the Replication Layer

Data in Spanner is partitioned into tablets (key ranges within a table). Each tablet is owned by a Paxos group — a set of replicas in different zones running Multi-Paxos with a stable leader. The leader serializes writes, the replicas vote, and a write commits once a majority quorum has logged it. Stable leadership (vs naive single-decree Paxos) means the leader can pipeline writes without re-electing every round.

Reads have three flavors that reflect the consistency dial:

• Strong reads — Routed to the leader; serve the latest committed state. Cost: cross-zone RTT to the leader.
• Read-only transactions — Pick a timestamp s in the recent past and serve from any replica caught up to s. No locks, no leader contention.
• Stale reads — Explicitly bounded staleness (e.g. "as of 5 seconds ago"), always servable locally with no coordination. The cheapest read mode.

Because every replica's log advances monotonically and TrueTime gives each tablet's leader a safe time (a timestamp below which all transactions have committed), any replica can answer a read at timestamp s as long as s ≤ safe_time. This is what makes Spanner reads cheap in the common case despite being a globally consistent system.

Two-Phase Commit Across Paxos Groups

A transaction that touches a single Paxos group commits in one Paxos round. Cross-group transactions (the harder case) use two-phase commit on top of Paxos:

1. The client picks one participant leader as the coordinator.
2. Each participant leader acquires read/write locks on the keys it touches and replicates a prepare record through its Paxos group. Once the prepare is durable, it sends a prepare-ack to the coordinator with a prepare timestamp.
3. The coordinator picks a commit timestamp ≥ all prepare timestamps and ≥ TT.now().latest, then replicates the commit decision through its own Paxos group.
4. The coordinator waits out commit-wait, then notifies participants. Each participant replicates the commit through its Paxos group and releases locks.

The key correctness property: because each participant chose a prepare timestamp ≥ its safe time and the coordinator chose a commit timestamp ≥ all prepare timestamps, the commit timestamp lies in the future of every event the transaction observed. Combined with commit-wait, this gives external consistency: if transaction T1 commits before T2 starts in real time, T1's commit timestamp is strictly less than T2's. No external database achieves this property without atomic clocks or some equivalent.

Interleaved Tables and Locality

A naive sharded SQL system pays for joins between parent and child rows that live on different shards. Spanner exposes interleaved tables as a first-class concept: child rows are stored physically adjacent to their parent.

CREATE TABLE Customers (
  customer_id  INT64 NOT NULL,
  name         STRING(MAX),
  email        STRING(MAX),
) PRIMARY KEY (customer_id);

CREATE TABLE Orders (
  customer_id  INT64 NOT NULL,
  order_id     INT64 NOT NULL,
  total        NUMERIC,
  status       STRING(20),
) PRIMARY KEY (customer_id, order_id),
  INTERLEAVE IN PARENT Customers ON DELETE CASCADE;

The Orders rows are physically clustered by customer_id with the matching Customer row. A query like "all orders for customer 42" reads contiguous bytes from one tablet. A transaction that updates a customer and inserts an order touches a single Paxos group, avoiding 2PC entirely. Cascading deletes are equally local. This is the SQL analog of DynamoDB's PK/SK colocation, but expressed as a foreign-key relationship rather than as a key prefix convention.

The placement driver respects this: tablets for an interleaved hierarchy stay together as the key range splits. A "directory" — Spanner's name for an interleaved hierarchy under one root key — is the unit of placement and movement.

Schema Changes Without Locks

Most distributed databases lock or rebuild tables for non-trivial schema changes. Spanner's schema evolution protocol uses a future-dated DDL timestamp:

1. The DDL operation is assigned a timestamp t safely in the future (e.g. now + 30 s).
2. The schema change is broadcast to every Paxos group leader. Each acknowledges that it has received the new schema definition.
3. Once all leaders have ack'd, the change becomes effective at t: any transaction with timestamp ≥ t sees the new schema, anything earlier sees the old.
4. For schema changes that need data movement (column type widening with a default, index creation), a background populator works in the new schema's view while the old schema continues to serve reads.

The result is online ALTER for everything: add columns, drop columns, create indexes, change types, all with no impact on running queries. A new index becomes visible to queries only after the populator is fully caught up; until then, planner statistics ignore it.

The SQL Frontend — F1's Legacy

F1, described in the 2013 paper, is the SQL layer Google built on top of Spanner to retire its sharded MySQL fleet for AdWords. Modern Cloud Spanner inherits much of F1's design:

• Pushdowns — Predicates, projections, and even partial aggregations are pushed to tablet servers so the SQL coordinator only sees pre-filtered, pre-aggregated data.
• Distributed query execution — Joins are planned with locality in mind (interleaved tables → local hash-merge), shuffles use streaming RPCs across tablet leaders.
• Change streams — Cloud Spanner exposes a CDC API (Spanner Change Streams) that streams committed mutations in commit-timestamp order, similar in spirit to DynamoDB Streams or PostgreSQL logical replication.
• Optimistic + pessimistic concurrency — Read-write transactions take pessimistic locks; read-only transactions never block writers because they read at a chosen past timestamp.

-- Cross-table aggregate that runs locally on each tablet
SELECT
  c.country,
  COUNT(*) AS order_count,
  SUM(o.total) AS revenue
FROM Customers c
JOIN Orders o USING (customer_id)
WHERE o.created_at > '2025-04-01'
GROUP BY c.country;

Because Customers and Orders are interleaved, the join executes on each tablet that holds a directory; each tablet emits a partial aggregate, the coordinator merges them. The plan is what you'd expect from any decent MPP planner, but the storage layer makes it cheap.

Strengths and Tradeoffs

Spanner buys you serializability + global distribution + SQL — a combination almost no other system offers. The cost is non-trivial:

• Write latency floor — Cross-zone Paxos commit is ~30-50 ms. Cross-region commits are 100-200 ms. You cannot beat the speed of light, and Spanner does not pretend to. For sub-millisecond write workloads, use a single-region OLTP database.
• Cost — Cloud Spanner pricing scales with provisioned compute capacity (in "processing units" or "nodes"). Even a small instance is hundreds of dollars per month; production instances run into thousands.
• Vendor lock-in — Spanner is GCP-only. The closest open-source analogs are CockroachDB and TiDB, but neither replicates TrueTime's external-consistency guarantees without atomic clocks. They use HLCs and slightly weaker consistency.
• Schema rigidity — Despite online schema changes, you still have a relational schema. Document-shaped data fits awkwardly. Use Firestore or Spanner's JSON column type for flexible attributes.
• Hot rows — A single key under heavy contention bottlenecks on the leader replica. Application-level batching, sharding row counters, or interleaved tables can help.

Spanner vs CockroachDB vs TiDB

The clock is what separates them. Without atomic clocks, CockroachDB and TiDB cannot offer external consistency without extra coordination. CockroachDB compensates with retry-based conflict detection; TiDB uses a placement driver as a global timestamp oracle. Both work, but their consistency stories are weaker than Spanner's by definition.

Frequently Asked Questions