Google Spanner: The Globally Distributed Database

In 2012, Google unveiled something that distributed systems researchers had considered theoretically impossible: a globally distributed database that provided strong consistency, SQL semantics, and horizontal scalability—all simultaneously. That database was Google Spanner.

Traditional distributed database wisdom held that you had to choose between consistency and availability (the CAP theorem), between SQL and scale (the NoSQL movement), between geographic distribution and transactional guarantees. Spanner broke these tradeoffs not by disproving the theorems, but by engineering around them in ways that shifted the boundaries of what was achievable.

Today, Google Spanner serves as the backbone for some of the world's most demanding applications: Google Ads, Google Play, Google Cloud's internal infrastructure, and thousands of external deployments. It processes millions of transactions per second across continents, maintaining the illusion that the entire planet is a single, coherent database.

Before we can appreciate Spanner's solution, we must understand the problem in depth. Global distribution of databases isn't simply about placing servers in different locations—it's about reconciling fundamental physical constraints with application requirements.

The Speed of Light Constraint:

The most fundamental constraint in global distribution is physics itself. Light travels at approximately 299,792 kilometers per second in a vacuum, which sounds fast until you consider the distances involved:

• San Francisco to New York: ~4,100 km → minimum ~14ms one-way latency
• San Francisco to London: ~8,600 km → minimum ~29ms one-way latency
• San Francisco to Tokyo: ~8,300 km → minimum ~28ms one-way latency
• San Francisco to Sydney: ~12,000 km → minimum ~40ms one-way latency

These are theoretical minimums. In practice, network latencies are 2-4x higher due to routing, switching, and the fact that fiber optic cables don't follow straight lines across the Earth.

Why This Matters:

If your database must coordinate between nodes in San Francisco and Sydney before committing a transaction, you're looking at a minimum of 80ms round-trip latency (and realistically 150-300ms). For a database handling thousands of transactions per second, this coordination overhead becomes the dominant factor in system performance.

The Coordination Dilemma:

Traditional databases solve consistency through coordination—nodes agree on transaction ordering before committing. In a global system, this coordination must happen across continental distances, introducing unavoidable latency. The naive approach of requiring all nodes to agree on every transaction simply doesn't scale.

Consider what happens when a user in Tokyo and a user in London both try to update the same bank account simultaneously:

1. Both transactions must be ordered (who goes first?)
2. The ordering must be agreed upon globally
3. The agreement requires round-trips across continents
4. The result: hundreds of milliseconds for each transaction

This is unacceptable for applications requiring sub-100ms response times.

Spanner's architecture is built on several interlocking concepts that, together, enable global distribution with strong consistency. Understanding each component and how they interact is essential for grasping why Spanner works.

Zones and Zone Sets:

At the physical level, Spanner is deployed across multiple zones. A zone is the unit of administrative deployment and roughly corresponds to a datacenter or a distinct failure domain within a larger datacenter complex. Zones are independent—a failure in one zone (power outage, network partition, software bug) shouldn't affect other zones.

Zones are grouped into zone sets based on geographic proximity. A zone set typically contains zones within a single metropolitan area or region. Data is replicated within and across zone sets according to configurable policies.

Spanservers and Directories:

Within each zone, spanservers hold the actual data. Each spanserver manages multiple tablets—ranges of rows from the database, similar to shards in a traditional distributed database. However, Spanner adds another layer: directories.

A directory is the unit of data movement and replication. Directories contain contiguous ranges of rows that share common access patterns and replication configurations. When Spanner moves data for load balancing or fault tolerance, it moves entire directories.

The Replication Hierarchy:

Understanding Spanner's replication requires thinking in layers:

1. Tablets contain directories
2. Directories contain rows with shared replication configs
3. Paxos groups manage consensus for each directory
4. Each zone has replicas of directories assigned to it
5. Zone configuration determines which zones hold replicas of which directories

Paxos Groups and Consensus:

Each directory in Spanner is managed by a Paxos group—a set of replicas that use the Paxos consensus protocol to agree on transaction ordering and ensure data is consistently replicated. The Paxos group has one leader (which accepts writes) and multiple followers (which participate in consensus and can serve reads).

Paxos ensures that once a transaction is committed, it's committed on a majority of replicas before returning success to the client. This provides durability even if individual replicas fail—as long as a majority survives, the data is safe.

Why Paxos, Not Raft?

Spanner was designed before Raft became popular (Raft was published in 2014, Spanner in 2012). Both protocols provide similar guarantees, but Spanner uses Multi-Paxos with several optimizations:

• Leader leases: Leaders maintain leases to reduce the frequency of leader elections
• Parallel proposals: Multiple transactions can be proposed simultaneously
• Batching: Multiple transactions are batched into single Paxos rounds to amortize coordination overhead

Spanner's data model is specifically designed to support global distribution while maintaining relational semantics. Two key innovations make this possible: interleaved tables and hierarchical primary keys.

Interleaved Tables: Co-locating Related Data

In a traditional relational database, related tables (like users and orders) are stored independently. Joining them requires accessing potentially different physical locations. In a globally distributed system, this could mean cross-continental round trips for every join.

Spanner solves this with interleaved tables. An interleaved table is physically co-located with its parent table—rows from the child table are stored next to the parent row they reference. This ensures that operations involving a user and their orders never require cross-datacenter communication.

How Interleaving Works:

Consider a schema with Users and Orders. In Spanner, you'd define Orders as interleaved in Users:

The Locality Benefit:

With interleaving, fetching a user and all their orders requires accessing only one directory—one Paxos group—in one datacenter (the one where the leader resides). Compare this to a non-interleaved design where user data might be in a US datacenter while their orders are split across Europe and Asia. The performance difference is dramatic.

Hierarchical Primary Keys:

Notice how the primary key of Orders includes user_id, and OrderItems includes both user_id and order_id. This hierarchical key structure serves multiple purposes:

1. Uniqueness: The full key (user_id, order_id, item_id) uniquely identifies each item
2. Ordering: Rows are stored in primary key order, so all data for a user is contiguous
3. Efficient Scans: Range scans for "all orders for user X" are extremely efficient
4. Directory Mapping: The key prefix determines which directory (and thus which Paxos group) owns the data

One of Spanner's most powerful features is its flexible replica placement. Unlike databases that treat replication as an afterthought, Spanner puts replica configuration at the center of its design.

Replication Configurations:

Spanner supports multiple replication configurations, each optimized for different use cases:

1. Regional Configuration:

• All replicas in a single region
• 3-5 replicas across zones within the region
• Lowest write latency (zone-to-zone, not continent-to-continent)
• Survives zone failures but not regional outages
• Best for applications with users concentrated in one geography

2. Multi-Regional Configuration:

• Replicas across multiple regions/continents
• Typically 5+ replicas for majority consensus
• Higher write latency (must coordinate across regions)
• Survives regional outages
• Best for applications requiring global availability

3. Dual-Region Configuration:

• Primary and secondary region
• Automatic failover between regions
• Balanced availability and latency

Witness Replicas:

For configurations requiring odd numbers for Paxos majority, Spanner offers witness replicas. A witness participates in voting (consensus) but doesn't store a full copy of the data. This allows achieving required replica counts without the storage costs of full replicas.

For example, in a configuration with 2 full replicas, you might add a witness to achieve a 3-replica Paxos group. The witness can vote on commits but doesn't need the storage capacity of a full replica.

Read-Only Replicas:

Spanner also supports read-only replicas—replicas that receive data updates but don't participate in write consensus. These are ideal for:n

• Serving read-heavy workloads in geographies distant from write replicas
• Analytics queries that shouldn't impact transactional performance
• Reducing read latency without affecting write quorum

Leader Placement:

Critically, Spanner allows specifying leader placement constraints. You can configure:

• Which regions are eligible to host leaders
• Preferred leader regions (Spanner will elect leaders there when possible)
• Leader-follower proximity requirements

Building a globally distributed database means accepting that failures are not exceptions—they are the norm. Network partitions, datacenter outages, and hardware failures happen constantly at Google's scale. Spanner's design assumes failure and builds recovery into every layer.

Google's Private Network Infrastructure:

One often-overlooked aspect of Spanner's success is Google's investment in private network infrastructure. Google operates one of the world's largest private networks, with:

• Undersea cables connecting continents
• Dedicated fiber links between datacenters
• Software-defined networking for traffic optimization
• Redundant paths for every critical route

This infrastructure dramatically reduces the probability of network partitions compared to relying solely on the public internet. When partitions do occur, they're typically brief and localized.

Failure Detection and Recovery:

Spanner uses aggressive failure detection with multiple mechanisms:

1. Heartbeat Monitoring: Replicas continuously exchange heartbeats. Missed heartbeats trigger investigation.

2. Lease Expiration: Leaders hold time-bounded leases. If a leader becomes unreachable, its lease expires and a new leader is elected.

3. Chubby Lock Service: Spanner uses Google's Chubby (similar to ZooKeeper) for coarse-grained coordination and leader election.

4. Automatic Recovery: When failures are detected, Spanner automatically:

   • Elects new Paxos leaders
   • Creates replacement replicas
   • Rebalances load across healthy servers

Consistency During Failures:

The critical property Spanner maintains is linearizability—even during failures, the database behaves as if there's a single copy of the data with operations executing atomically in some total order. This is achieved through:

1. Paxos Majority Commits: A transaction isn't considered committed until a majority of replicas acknowledge. This means committed data survives any minority failure.

2. Leader Leases with TrueTime: Leaders hold leases with precisely bounded durations. A new leader can only begin accepting writes after the old leader's lease definitely expired (accounting for TrueTime uncertainty). This prevents split-brain scenarios.

3. Read Timestamps: Every read receives a timestamp. The database guarantees that reads at a timestamp see all transactions committed before that timestamp—even if leader changes occurred.

The Result:

Applications using Spanner don't need to implement retry logic for consistency issues, handle stale reads after failover, or worry about lost transactions. The database provides the same guarantees during failures as during normal operation. This dramatically simplifies application code.

We've covered substantial ground in understanding how Spanner achieves planetary-scale distribution. Let's consolidate the key architectural principles:

What's Next:

Global distribution alone doesn't guarantee consistency—you still need a way to order transactions across continents. In the next page, we'll explore TrueTime—Spanner's revolutionary approach to global clock synchronization that makes external consistency possible. TrueTime is the innovation that truly sets Spanner apart from other distributed databases.