CS PAPERS DEEP-READ · PAPER 25
Shute et al. · Google · VLDB 2013
In 2013 a team at Google unveiled F1 — the database running under AdWords, Google's most lucrative product at the time. Its feat was holding two things at once that were long thought mutually exclusive: scaling out to any size like a big internet system, while keeping the full SQL, transactions, and strong consistency of an old-school relational database. It replaced the hand-sharded, maintenance-nightmare MySQL that AdWords used to run on.
For a couple of decades, anyone building large systems faced a forced choice. On one side, the classic relational database (speaks SQL, does transactions, data always adds up) — but once the data outgrows one machine, you must hand-split the tables into many chunks across many machines, after which cross-chunk transactions, cross-chunk queries, and re-splitting are all nightmares. On the other side, NoSQL (like Bigtable), born to spread across thousands of machines and scale freely — but at the cost of losing transactions, losing SQL, and often having data that's only "eventually" consistent. Google itself had fled from MySQL to NoSQL, and its engineers spent every day missing the good old days.
F1's bet is: you don't have to choose. First put down a storage layer that is natively scalable and natively strongly consistent — the previous paper's Spanner (Google's database that does globally consistent transactions using "honest clocks"). Then, on top of it, lay the relational database's full SQL, transactions, and indexes back down, untouched. In other words: hand the hard job of scaling off to Spanner below, and let F1 focus on making the "pleasant database" layer beautiful.
The catch is in one place: to keep data globally consistent, Spanner has every write cross data centers to take a vote before it's final — which is slow: a commit takes tens to over a hundred milliseconds, far slower than a local database. F1 uses three moves to spread that slowness thin:
One: pack a customer's whole data tree into "the same folder." An advertiser has many campaigns, each with many ad groups — F1 stores that whole tree physically next to each other, filed in one slot. So "fetch this customer's entire record" is one local pickup, and edits happen in place within one slot, no running around the data centers.
Two: don't lock the data while editing; check at save time. Like several people editing a shared document: you don't lock it and edit slowly — you read and edit freely, and only at the moment of "save" do you check whether anyone else touched what you read. Untouched? Commit. Touched? Redo. So a slow client never holds a lock and jams everyone else.
Three: since every round-trip is a slow "overseas call," don't ask one question at a time. F1 has the app ask many things at once, in batches and in parallel, cutting the number of trips and making them concurrent to hide each one's slowness. The result: AdWords web pages end up no slower than the old MySQL.
F1 proved that "scales to any size" and "full SQL + transactions + strong consistency" need not be a forced choice: hand scaling off to Spanner below, focus on rebuilding a pleasant relational database above; then use three moves — file a whole data tree in one slot, don't lock edits but verify at save time, and ask in batches and in parallel — to spread out the slowness of cross-data-center sync. It ran Google's most lucrative business, AdWords.
Want the architecture diagram, how hierarchical tables are laid out, how optimistic transactions run, and the real latency numbers? → switch to the deep read
F1 is the distributed relational database Google built for AdWords: it sits on top of Spanner, inheriting Spanner's "horizontally scalable + globally strongly consistent" storage foundation, and re-provides on top of it full SQL, ACID transactions, and consistent secondary indexes — squarely overturning the industry assumption that "to scale you must give up SQL and transactions." To swallow the high commit latency of synchronous replication, it uses a hierarchical schema (physically clustering related data into a tree), Protocol Buffer column types, optimistic transactions, and a batched + parallel client access pattern to spread the latency thin, and makes change history a first-class citizen to keep indexes consistent. It has managed all of AdWords' data in production since early 2012.
The authors are Jeff Shute and a large team of Google engineers; the paper appeared at VLDB 2013. It builds on Google's own Spanner (2012, which provides strongly consistent, scalable storage and transactions) — F1 is the SQL layer laid on top of Spanner. What it replaced was the hand-sharded MySQL under AdWords (a single re-sharding took a large team on the order of two years). It is also a landmark of the NewSQL wave: alongside contemporaneous Google Spanner, and the later CockroachDB, TiDB, and others, it answers the same question — can you have scale and SQL and transactions?
In the 2000s, builders of large systems were forced into a choice. Traditional relational databases give you SQL, transactions, and strong consistency, but don't scale: past one machine you hand-shard, and cross-shard transactions, cross-shard JOINs, and re-sharding as the business grows become huge operational burdens. Google's AdWords was stuck exactly here — running on a manually partitioned MySQL where a single re-sharding mobilized a team for roughly two years.
The other road is NoSQL (Google's own Bigtable being the exemplar): natively spreads across thousands of machines and scales freely, but at the cost of giving up cross-row transactions, giving up SQL, and offering only eventual consistency. Application developers who fled to NoSQL had to stitch transactions together themselves, keep indexes consistent themselves, and write query logic themselves — carrying on their own backs the dirty work the database should be doing.
F1's motivation is precisely this: the forced choice is false. As long as the lower layer can provide "scalable + strongly consistent" storage, you can reinstall the most valuable parts of a relational database (SQL, transactions, indexes) on top. And Google happened to have exactly such a lower layer — Spanner. The authors explicitly list four goals that must hold together: scalability, availability, consistency, and usability — with special emphasis on "usability," so that hundreds of engineers could smoothly migrate AdWords onto it.
F1's first design philosophy is division of labor. The hardest job — horizontal scaling + strongly consistent cross-data-center replication — goes to Spanner below: data is sliced into directories, each replicated synchronously by a group of replicas (typically 5, across data centers) via Paxos. F1 itself is a largely stateless SQL engine: a client can connect to any F1 server, the server holds almost no data, so servers can be added or removed freely and scaled on demand. Large queries are handed to an F1 slave pool (a pool of distributed query workers) for parallel execution.
This is F1's most crucial design, and it directly decides whether it can survive the latency. In the traditional relational model each table is independent and physically scattered; F1 lets you declare tables in a parent–child hierarchy: a child table's primary key is prefixed by the parent's primary key, so a parent row and all its descendant rows are physically clustered and interleaved together, filed into one Spanner directory — i.e., one Paxos group.
Take AdWords: Customer → Campaign → AdGroup. A customer's whole data tree lands in one slot. The payoff is decisive: fetching a customer's entire record is one local read (no scrounging across groups), and modifying data within that tree is one single-group local transaction (no need to launch an expensive cross-group distributed commit). Because in real business almost all transactions happen to be scoped to "one customer," this single step turns most writes into cheap local operations.
F1 columns store more than numbers and strings — they can directly hold Protocol Buffer objects, including repeated fields (one field holding a list of values). This means many one-to-many relationships that would otherwise be split into child tables and JOINed at query time can be embedded directly into a protobuf column on the parent row — fewer tables to build, fewer JOINs. And since Google's application code already uses protobufs to move data, having the database natively understand protobufs erases the impedance mismatch between objects and relational tables, for a smoother developer experience.
The cost can't be dodged: Spanner's synchronous replication makes a commit cross data centers for a vote, at roughly 50–150 ms (reads about 5–10 ms). F1 defuses this two ways.
First is the optimistic transaction, also the default mode. It runs in two parts: a read phase that can run arbitrarily long, takes no locks, and merely records the "last-modified timestamp" of every row it reads; then a very short write phase that packages the intended writes and, before committing, re-checks whether those timestamps changed — unchanged, it commits; changed (someone modified it first), it aborts and retries. The analogy is several people co-editing a shared document: don't lock it, just at save time check "was what I read touched by anyone." A string of benefits follows: a slow or crashed client never holds a lock jamming others; retries are idempotent and easy to implement server-side; it pairs naturally with the stateless F1 servers. (There are also snapshot transactions for consistent read-only snapshots, and pessimistic transactions that use Spanner's locking transactions directly, chosen as needed.)
Second is reshaping the application's access pattern. Since every access is like a slow overseas call, don't ask one serial question at a time: F1 encourages the app to issue reads in batches and in parallel, offsetting each call's slowness with "fewer trips, concurrent trips." Combined with the hierarchical schema (read back a whole tree at once), after AdWords migrated to F1 the end-to-end web latency was actually comparable to the old MySQL, and some pages were faster — individual operations are slower, but parallelism went up.
Indexes come in two physical forms: a local index lives in the same directory as the rows it indexes and is updated within the row's own transaction — cheap; a global index spans many directories and is sharded independently, so updating it requires launching a cross-group distributed transaction — expensive, which is why F1 limits how many global-index entries one transaction may change. Both kinds are maintained in step with the transaction and kept consistent — precisely the work NoSQL foists on the application layer and F1 shoulders for you. F1 also makes change history a first-class citizen: every transaction writes its modifications as change records in the same commit, and downstream consumers can subscribe to those changes to incrementally maintain indexes, invalidate caches, or sync to other systems — a built-in, consistent "change data capture."
The most convincing result is that it actually runs Google's most lucrative business: F1 has managed all of AdWords' data in production since early 2012, replacing the previously hand-sharded MySQL, at a scale of hundreds of terabytes under a sustained, high-concurrency OLTP load. On performance, the paper is honest with numbers: thanks to synchronous replication, commit latency is roughly 50–150 ms, clearly higher than a single-machine database; yet via the hierarchical schema, optimistic transactions, and batched parallel reads, AdWords' user-visible latency is comparable to the old system. On availability, resting on Spanner's multiple replicas (typically 5, across data centers), the system can survive an entire data center going offline with no data loss and almost no interruption. On scalability, adding machines scales it out — an end to "re-sharding measured in years."
Together with Spanner, F1 pulled the industry out of the fate that "to scale you must give up SQL and transactions," proving in practice that "scalable" and "strongly consistent + full SQL + transactions" can coexist — as long as you're willing to pay a little latency for consistency and engineer it away. It is a banner of the NewSQL wave, directly inspiring and validating a later crop of distributed SQL databases (CockroachDB, TiDB, YugabyteDB, etc.) that follow the same recipe: scalable, strongly consistent storage below, SQL recast above. Several concrete engineering moves it demonstrated — hierarchical clustering for data locality, optimistic transactions against high latency and misbehaving clients, and built-in change history to keep indexes consistent — became patterns that later systems borrowed again and again. For Google itself, it was a successful live transplant of its most core business's data foundation.
① In one line: F1 sits on Spanner, re-fitting a "scalable + strongly consistent" storage foundation with full SQL, ACID transactions, and consistent indexes — and ran AdWords.
② The pain: you used to have to choose — relational DBs have SQL/transactions but don't scale (hand-sharding, re-sharding measured in years), NoSQL scales but loses transactions, SQL, and strong consistency.
③ Skeleton: hand "scaling" to Spanner; F1 is a largely stateless, freely scalable SQL engine; large queries go to a slave pool to run in parallel.
④ Hierarchical schema: child keys prefixed by parent keys, so parent/child rows cluster physically into a tree in one Paxos group → one local read for the whole tree, single-group local transactions for edits within it.
⑤ Protobuf columns: embed one-to-many relationships into a row, building fewer tables and doing fewer JOINs, and erasing the object–relational impedance mismatch.
⑥ Latency defense: optimistic transactions by default (read without locks, only record timestamps, verify at commit whether anything was modified), plus a batched + parallel client access pattern; change history as a first-class citizen keeps indexes consistent.
⑦ Results: runs all of AdWords' data in production (hundreds of TB); commit latency 50–150 ms but user-visible latency comparable to the old system; survives a data center going offline with no data loss.
⑧ Limits: commit latency is inherently high and needs the app rewritten; higher resource cost; global indexes and optimistic transactions under high contention are constrained; heavy dependence on Spanner and TrueTime.