F1: A Distributed SQL Database That Scales

Jeff Shute Radek Vingralek Bart Samwel Ben Handy

F1: A Distributed SQL Database That Scales

Chad Whipkey Eric Rollins Mircea Oancea Kyle Littlefield

Traian Stancescu Himani Apte

Google, Inc.

*University of Wisconsin-Madison

ABSTRACT

F1 is a distributed relational database system built at

Google to support the AdWords business. F1 is a hybrid

database that combines high availability, the scalability of

NoSQL systems like Bigtable, and the consistency and us- ability of traditional SQL databases. F1 is built on Span- ner, which provides synchronous cross-datacenter replica- tion and strong consistency. Synchronous replication im- plies higher commit latency, but we mitigate that latency

by using a hierarchical schema model with structured data

types and through smart application design. F1 also in- cludes a fully functional distributed SQL query engine and

automatic change tracking and publishing.

1. INTRODUCTION

F11

is a fault-tolerant globally-distributed OLTP and

OLAP database built at Google as the new storage system

for Google’s AdWords system. It was designed to replace a

sharded MySQL implementation that was not able to meet

our growing scalability and reliability requirements.

The key goals of F1’s design are:

1. Scalability: The system must be able to scale up,

trivially and transparently, just by adding resources.

Our sharded database based on MySQL was hard to

scale up, and even more difficult to rebalance. Our

users needed complex queries and joins, which meant

they had to carefully shard their data, and resharding

data without breaking applications was challenging.

2. Availability: The system must never go down for any

reason – datacenter outages, planned maintenance,

schema changes, etc. The system stores data for

Google’s core business. Any downtime has a signifi- cant revenue impact.

3. Consistency: The system must provide ACID trans- actions, and must always present applications with

1Previously described briefly in [22].

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are

not made or distributed for profit or commercial advantage and that copies

bear this notice and the full citation on the first page. To copy otherwise, to

republish, to post on servers or to redistribute to lists, requires prior specific

permission and/or a fee. Articles from this volume were invited to present

their results at The 39th International Conference on Very Large Data Bases,

August 26th - 30th 2013, Riva del Garda, Trento, Italy.

Proceedings of the VLDB Endowment, Vol. 6, No. 11

Copyright 2013 VLDB Endowment 2150-8097/13/09... $ 10.00.

consistent and correct data.

Designing applications to cope with concurrency

anomalies in their data is very error-prone, time- consuming, and ultimately not worth the performance

gains.

4. Usability: The system must provide full SQL query

support and other functionality users expect from a

SQL database. Features like indexes and ad hoc query

are not just nice to have, but absolute requirements

for our business.

Recent publications have suggested that these design goals

are mutually exclusive [5, 11, 23]. A key contribution of this

paper is to show how we achieved all of these goals in F1’s

design, and where we made trade-offs and sacrifices. The

name F1 comes from genetics, where a Filial 1 hybrid is the

first generation offspring resulting from a cross mating of

distinctly different parental types. The F1 database system

is indeed such a hybrid, combining the best aspects of tradi- tional relational databases and scalable NoSQL systems like

Bigtable [6].

F1 is built on top of Spanner [7], which provides extremely

scalable data storage, synchronous replication, and strong

consistency and ordering properties. F1 inherits those fea- tures from Spanner and adds several more:

• Distributed SQL queries, including joining data from

external data sources

• Transactionally consistent secondary indexes

• Asynchronous schema changes including database re- organizations

• Optimistic transactions

• Automatic change history recording and publishing

Our design choices in F1 result in higher latency for typi- cal reads and writes. We have developed techniques to hide

that increased latency, and we found that user-facing trans- actions can be made to perform as well as in our previous

MySQL system:

• An F1 schema makes data clustering explicit, using ta- bles with hierarchical relationships and columns with

structured data types. This clustering improves data

locality and reduces the number and cost of RPCs re- quired to read remote data.