A relational database keeps its data in neat tables and answers any question with SQL. That is wonderful until your data is a copy of the whole web, or a billion users' settings, and no single machine can hold it. Google needed something that spread over thousands of ordinary servers and kept working when some of them died.
Bigtable is what they built. It is not a relational database. It is a giant sorted map that scales to petabytes, and its design is a sampler of ideas you will meet in every large storage system: sorted rows, splitting into tablets, a write log, and memory tables flushed into immutable files.
Bigtable is a sparse, sorted, multi-dimensional map from (row, column, time) to bytes. Rows are split into ranges called tablets that live on different servers. Writes go to a log and a memory table first, then are flushed to immutable files that are merged in the background.
A big sorted map
The paper describes Bigtable as a "sparse, distributed, persistent multidimensional sorted map." That is a mouthful. Break it down:
- Map: you look up a value by a key made of a row key, a column key and a timestamp.
- Sorted: rows are kept in order by their key, so neighboring keys live together.
- Sparse: a row can use any columns it likes. Empty columns cost nothing.
- Versioned: each cell can hold several timestamped versions, newest first.
The paper's running example is a table of web pages. The row key is the page's address with the domain reversed (com.cnn.www). One column family holds the page contents, another holds the link text other pages used to point at it.
Think of a huge, sorted phone book that grows forever. You find a person by looking up the name (row), then the kind of number (column), and each entry keeps its history. You cannot ask "all people whose number ends in 7" quickly, only "all people in this range of names."
Tablets: how a table spreads over machines
Bigtable cuts the sorted rows into contiguous ranges called tablets. A tablet is the unit of distribution and load balancing. Each tablet server owns many tablets, and a table starts as one tablet and splits as it grows.
