F1: A Distributed SQL Database That Scales

✨ Summary

Overview

F1 is a distributed relational database developed at Google to replace a sharded MySQL deployment supporting AdWords. Its central design objective is to combine NoSQL-style scalability and availability with SQL usability, secondary indexes, ACID transactions, and strong consistency. F1 is implemented above Spanner, which supplies sharding, synchronous replication, fault tolerance, transaction processing, and globally ordered timestamps. The paper reports that F1 was managing AdWords campaign data in production from early 2012, with more than 100 TB of data, workloads reaching hundreds of thousands of requests per second, and availability of approximately five nines. (static.googleusercontent.com)

System design

The system separates mostly stateless F1 servers from the replicated Spanner storage layer. F1 servers can be added or removed without moving data, while additional Spanner capacity triggers transparent data redistribution. Distributed query workloads can use a shared pool of worker processes, and large-scale extraction can integrate with MapReduce.

A key design decision is hierarchical data clustering. Child tables use ancestor keys as prefixes of their primary keys, causing related rows to be stored together in the same Spanner directory. This improves locality, permits range reads and streaming merge-style joins, and reduces the number of participants in common transactions. Protocol Buffer-valued columns provide structured data types that more closely match application objects and can replace child tables when repeated data has a bounded size.

F1 maintains transactionally consistent secondary indexes. Local indexes are co-located with root rows and generally have low incremental transaction cost; global indexes are distributed independently and may introduce additional two-phase-commit participants. The paper identifies large transactions involving global indexes as a scalability limitation and therefore recommends using global indexes selectively and keeping such transactions small.

Schema changes are performed asynchronously and without blocking queries or updates. The protocol restricts the cluster to compatible current and next schemas and decomposes changes into phases. For example, an index can first be introduced for maintenance operations, then enabled for writes, backfilled, and finally exposed for reads. This avoids corruption while different servers transition at different times.

F1 supports snapshot, pessimistic, and optimistic transactions. Optimistic transactions perform an unlocked read phase and validate row modification timestamps during a short commit phase, enabling long-running transactions, transparent server failover, and server-side retries. Their principal weaknesses are insertion phantoms and poor throughput under high contention; parent-table locks or batching can address some of these cases. Flexible lock columns allow concurrency to be tuned from row-level to column-level or deliberately reduced across related child rows.

Change History is implemented as a database-level feature. Transactions record before-and-after values in clustered ChangeBatch records, and publish/subscribe notifications allow consumers to process changes incrementally. The same mechanism supports cache repair: a cache can apply changes after a checkpoint instead of reloading an entire object or dataset.

Query processing and performance

F1 offers both centralized execution for short OLTP queries and distributed execution for larger analytical workloads. Its query engine assumes that data is remote, arbitrarily partitioned, and not usefully co-partitioned. It therefore relies heavily on batching, asynchronous reads, streaming operators, hash repartitioning, distributed hash joins, and distributed aggregation. Lookup joins collect large batches of keys before issuing concurrent remote reads, while cluster joins exploit the physical ordering of hierarchically clustered tables.

The design accepts higher low-level storage latency in exchange for scale and consistency. The deployment described in the paper reports read latencies of approximately 5–10 ms and commit latencies of approximately 50–150 ms, with multi-group transactions typically adding further latency through two-phase commit. The authors report that careful schema clustering and application-level batching, parallelism, and asynchronous access kept average end-user latency for the principal AdWords application comparable to the former MySQL system, while improving tail behavior. The cost was higher resource consumption: F1 queries could use roughly an order of magnitude more CPU than comparable MySQL queries because of compression, decompression, distributed processing, and network transfer. (static.googleusercontent.com)

Influence

The paper helped establish a concrete production example of strongly consistent distributed SQL combining relational interfaces with geo-replication and elastic execution. A documented downstream example is CockroachDB: its SIGMOD 2020 paper explicitly identifies F1 as a source of inspiration for CockroachDB’s distributed execution engine and online schema-change infrastructure, and describes adapting the incremental schema-transition approach used by F1. (cockroachlabs.com)