Spanner's Data Distribution and Replication: Directories and Paxos

Introduction

In our previous lesson, we established the high-level architecture of Spanner, identifying the Spanservers as the workhorses that store and serve data, and the Placement Driver as the global orchestrator responsible for automated data movement. We introduced two crucial concepts: Paxos groups as the mechanism for synchronous replication, and directories as the unit of data placement.

Today, we will connect these concepts to address the learning outcome: Explain how Spanner manages data distribution and replication using directories and Paxos groups. We will move from the "what" to the "how," dissecting the relationship between the physical reality of replication groups and the logical abstraction of data directories. This understanding is fundamental to grasping how Spanner achieves both global scale and fine-grained control over data locality and availability.

The Foundation of Replication: Paxos Groups

As we reviewed, Spanner uses Paxos to ensure that any changes to data are replicated consistently and durably. A set of replicas for a given piece of data forms a Paxos group. Since you have a theoretical background in consensus protocols, you'll recognize that this means all writes must be coordinated through a leader to achieve consensus among a majority of replicas. This is the core of Spanner's synchronous replication.

These replicas are not arbitrary. They are distributed across different spanservers, which are themselves located in different physical zones (datacenters) to provide fault tolerance. The state of each replica in a Paxos group is stored in a data structure called a tablet. Therefore, a tablet is the physical container for a replica's data on a single spanserver.

The diagram below illustrates this arrangement. Notice how "Paxos Group 1" is formed by three replicas, each residing on a different spanserver in a different zone. This geographic distribution is what allows Spanner to survive datacenter-level failures.

This diagram shows how replicas forming a Paxos group are distributed across multiple spanservers, often in different zones, to achieve fault tolerance. Each replica manages its state within a tablet.

This structure raises a key question: what data, exactly, does a Paxos group replicate? The answer lies in a logical grouping called a directory.

The Unit of Placement: The Directory Abstraction

While a Paxos group is the mechanism for replication, it doesn't define what data gets replicated together or where it lives. For this, Spanner uses a logical abstraction called a directory.

A directory is a set of contiguous keys that share a common prefix. Think of it as a logical "bucket" for related data. The key insight is that a directory is the unit of data placement. This means two things:

Shared Replication Policy: All data within a single directory has the same replication configuration. An application can specify, for example, that "all data for User A belongs to a directory that must have 3 replicas in North America and 2 in Europe."
Atomic Movement: When the Placement Driver needs to rebalance load or move data closer to users, it moves data directory by directory.

This abstraction is incredibly powerful. It gives application developers control over data locality—which is critical for performance and for complying with data residency regulations like GDPR—without having to manage the underlying replication mechanics.

To dive deeper into these concepts, we'll consult both the original Spanner paper and a helpful summary that clarifies the terminology.

Spanner: Google's Globally-Distributed Database

This is the definitive source on Spanner's design. We'll focus on the sections that formally define Paxos groups, tablets, and the directory abstraction.

First, in Section 2.1, "Spanserver Software Stack," review the relationship between tablets and Paxos. Read from this paragraph to reinforce how the Paxos state machine is built on top of the tablet. Next, read all of Section 2.2, "Directories and Placement." This is the core of today's lesson. Pay close attention to how it defines a directory as the unit of placement and movement, and how it enables application-controlled locality.

The concept of a directory as a "bucket" of related data that moves together is a central theme. The following blog post offers a very clear explanation of this idea.

Spanner: Google's Globally-Distributed Database - Anant Jain

This article provides a more accessible breakdown of the concepts from the paper. Its explanation of directories is particularly effective.

Please read the section titled "Directories and Placement." Focus on the definition of what a directory is and the practical example provided for customer-specific placement.

Putting It All Together: From Directories to Fragments

Now we can connect the physical and logical layers. A spanserver hosts tablets. A set of tablets across different spanservers forms a Paxos group. This Paxos group, in turn, is responsible for managing the data for one or more directories.

A crucial design point from the paper is that a single Paxos group can contain multiple directories. This allows Spanner to colocate data that is frequently accessed together, improving performance, even if that data doesn't belong to the same contiguous key range.

But what happens when a directory grows too large? If a single customer's data becomes enormous, a single Paxos group (and the servers backing it) might not be able to handle the load. To solve this, Spanner will automatically shard a large directory into multiple fragments. While logically part of the same directory, these fragments can be served from different Paxos groups, and therefore different sets of servers. This is a key mechanism that allows Spanner to scale individual hot directories beyond the capacity of a single machine set.

Dynamic Management: Moving Directories

The Placement Driver is the service that continuously monitors the system and orchestrates the movement of directories (or fragments) between Paxos groups. This movement, illustrated in the image below, is triggered for several reasons:

Load Balancing: To move data away from an overloaded Paxos group.
Locality: To move a directory closer to the clients that access it most frequently.
Constraint Enforcement: To add or remove replicas to meet an application's updated replication policy.

This image visualizes the core concept of data movement in Spanner. The directory "dir2" is being migrated from Paxos Group 1 to Paxos Group 2, a process orchestrated by the Placement Driver to balance load or meet placement constraints.

The paper mentions that this movement is handled by a background task called movedir. From a Principal Engineer's perspective, it's interesting to note that this is not implemented as a single, massive transaction, which would block ongoing operations. Instead, movedir moves the bulk of the data in the background and then uses a small, final transaction to atomically update the metadata for the two Paxos groups, minimizing disruption to the live system.

Conclusion

In this lesson, we have detailed the mechanics of how Spanner distributes and replicates its data. You can now explain the distinct but interconnected roles of Paxos groups and directories in this process.

Here are the key takeaways:

Data replication is handled by Paxos groups, which are sets of replicas distributed across different spanservers and physical zones for fault tolerance. Each replica's state is stored in a tablet.
Data is logically organized into directories, which are sets of contiguous keys. A directory is the fundamental unit of placement, and all data within it shares a single replication policy defined by the application.
A single Paxos group can manage multiple directories, and a large directory can be sharded into fragments that are served by different Paxos groups, enabling immense scalability.
The Placement Driver automates the movement of directories and fragments between Paxos groups to balance load and enforce data placement policies, ensuring the system adapts to changing workloads and requirements.

We have established how data is physically grouped and replicated. In our next lesson, we will build directly on this by exploring the learning outcome: Describe Spanner's schema design, including interleaved tables, and its impact on query performance. You will see how an application's schema choices directly influence how data is organized into keys, which in turn determines how it is grouped into directories, creating a powerful link between logical data modeling and physical data locality.

Recommended resources