Bigtable: A Distributed Storage System for Structured Data

The problem: one storage system for everything Google had

By 2004 Google needed to store the raw crawl of the web, hundreds of terabytes of pages updated continuously; the satellite imagery of Google Earth; the click-streams of Google Analytics; and the per-user data of personalised search. Some workloads were throughput bound, streaming through billions of rows in batch. Others served a user who was waiting. No commercial database would scale to thousands of machines at an affordable price, and a file system alone, even one as good as GFS, offered no structure, no indexing and no way to update one row among billions.

The idea: a sparse, sorted map, split by row range

Bigtable is deliberately not a relational database. It is one enormous map from a key to a value, where the key is a row name, a column name and a timestamp, and the value is bytes. Rows are kept in sorted order by name; a contiguous range of rows is a tablet, the unit that gets spread across machines. Columns are grouped into a small number of column families declared in advance, within which any column name may be used without declaration, so the table is sparse: a row stores only the columns written to it. Each cell can hold several versions, by timestamp, with a policy for how many to keep.

How it works

A single master assigns tablets to tablet servers and balances them, but is not on the read or write path: clients find the right tablet server through a three-level lookup (a root tablet, located via Chubby, that lists metadata tablets, that list user tablets) and cache the result, so the master is rarely contacted. Each tablet server keeps recent writes in a memtable and the rest in SSTables on GFS, with a commit log also on GFS: this is the LSM-tree from the previous paper, made distributed and with compactions called minor, merging and major. Locks, master election and the bootstrap location live in Chubby, Google’s Paxos-based lock service, which is also how a tablet server proves it is alive.

Two design choices are worth noticing because of what they refuse. Bigtable offers transactions on a single row and nothing wider, and it does not try to hide replication lag between data centres; the paper argues that most of its users were happier with a simple, predictable model than with features they would pay for on every operation. Spanner was the eventual answer for the users who were not.

What it changed

Bigtable defined the wide-column category. HBase reimplemented it on Hadoop within a year and became the store under Facebook Messenger and much of the Hadoop ecosystem; Cassandra combined its data model with Dynamo’s ring; the SSTable and memtable design, extracted as LevelDB and then RocksDB, became the most reused storage engine in the world. Google sells the system itself as Cloud Bigtable. Row-key design, the one skill the paper demands of its users, is now the central question in any schema review for DynamoDB, Cassandra or HBase.

Where you meet it today

• HBase, Cassandra, ScyllaDB, Cloud Bigtable. Tablets became regions or ranges; the model is the paper’s.
• DynamoDB’s partition key and sort key. A different system with the same lesson: the key decides locality and hot spots.
• Time-series layouts. Keys like sensor#reversed-timestamp that put the newest readings first are a Bigtable idiom.
• Column families as a way to store hot and cold data of one entity on different disks, now in RocksDB under the same name.