BigTable

Google needed to store structured data at enormous scale: web pages with many versions, user data, satellite imagery, geographic maps. Relational databases could not reach petabytes across thousands of machines, and a plain file system offers no way to look up a record by key. Bigtable is the answer: a distributed storage system for structured data that scales to petabytes and thousands of machines, built on top of two other systems, the Google File System for storing files and Chubby for coordination.

It is not a relational database. It does not offer joins or general transactions. It offers a simple, flexible data model that applications can use to build what they need.

Bigtable is described as a sparse, distributed, persistent, multidimensional sorted map. Each cell is addressed by three coordinates:

(row key, column key, timestamp) maps to a value, which is an uninterpreted array of bytes.

Rows. A row key is a string, and the table is kept sorted by row key. Reads and writes of a single row are atomic, whatever number of columns are involved, which simplifies reasoning about concurrent updates. Because rows are sorted, nearby keys are stored together, so you control locality by choosing keys. A web table stores pages keyed by reversed domain name, such as com.example.www/index, so pages from the same site sit next to each other.

Column families. Column keys are grouped into families, written family:qualifier. A family must be created in advance, but qualifiers within it can be created freely, so a row can have thousands of different columns, and different rows can have completely different columns. That is what makes the table sparse: empty cells cost nothing. Families are the unit of access control and of storage tuning, such as compression.

Timestamps. Every cell can hold multiple versions, indexed by a 64-bit timestamp, sorted newest first. A per-family policy chooses what to keep, such as the last 3 versions, or versions newer than a week, and old versions are garbage collected.

The table is divided into contiguous ranges of rows called tablets, each about 100 to 200 MB. A tablet is the unit of distribution and load balancing. A table starts as one tablet. As it grows, tablets split automatically, and each is assigned to a tablet server. A server typically handles ten to a thousand tablets. Because tablets are small, a failed server's load spreads quickly across many others, and a reading of a short range of rows contacts few machines.

A cluster has three parts.

• A client library, linked into applications.
• One master, which assigns tablets to tablet servers, detects when servers join or fail, balances load across servers, garbage collects files in GFS, and handles schema changes. The master is not on the data path: clients read and write by talking directly to tablet servers.
• Many tablet servers, each managing a set of tablets, serving reads and writes, and splitting tablets that grow too large.

All persistent data lives in GFS, not on the tablet servers' own disks. This is a powerful choice. Because GFS already replicates the files, a tablet server holds no irreplaceable data, and if it fails, any other server can pick up its tablets by reading the same files.

Bigtable relies on Chubby for the coordination jobs that need consensus.

• Ensuring there is only one active master at a time, by holding a Chubby lock.
• Discovering tablet servers: each server acquires an exclusive lock on a uniquely named file in a Chubby directory. The master watches that directory to find live servers. If a server loses its Chubby session, it loses the lock, and the master knows it is gone and reassigns its tablets.
• Storing the location of the root tablet, which bootstraps finding all other data.
• Storing schema information, such as the column families of each table.

If Chubby is unavailable for long, Bigtable becomes unavailable, which makes Chubby's own reliability crucial.

Clients need to know which server holds a given row. Bigtable uses a three level hierarchy, like a B+ tree.

1. A Chubby file holds the location of the root tablet.
2. The root tablet is the first tablet of a special METADATA table, and holds the locations of all the other METADATA tablets.
3. Each METADATA tablet maps a range of user tablets, by table name and last row, to the server serving them.

Capacity: each METADATA row is about 1 KB, so a 128 MB METADATA tablet holds about 2 to the 17 rows, 131,072 entries. Two levels of this fan-out address 2 to the 34 tablets, and at 128 MB each, that is 2 to the 61 bytes, about 2 exabytes. Clients cache locations aggressively, so most reads need no lookup at all, and the hierarchy is walked only when the cache is stale.

A tablet's data is stored in SSTables, an immutable, ordered map of keys to values, stored as a series of 64 KB blocks with an index at the end that locates the block holding a key. Since SSTables never change, they are easy to cache, copy and read concurrently.

The write path should look familiar from Cassandra, whose engine descends from this design.

1. The write is checked for validity, then appended to a commit log stored in GFS, for durability. Log appends from all tablets on a server are mixed into one log per server, which keeps the number of files being written small.
2. The write is inserted into an in-memory sorted buffer, the memtable.
3. When the memtable reaches a size threshold, it is frozen and written out as a new SSTable. This is a minor compaction. The commit log up to that point can then be discarded.

A read sees a merged view of the memtable and all the SSTables of the tablet, and returns the newest value. Because SSTables and the memtable are sorted, the merge is efficient.

Each minor compaction adds an SSTable, and too many would slow reads. A merging compaction periodically merges the memtable and a few SSTables into one. A major compaction rewrites all the SSTables of a tablet into exactly one, and discards deleted data entirely, which reclaims space.

• Locality groups: group several column families that are read together into one group, with its own SSTables. A web table can keep small metadata in one group and large page contents in another, so scanning metadata never reads the contents.
• Compression: applied per SSTable block, with schemes chosen per locality group. Similar pages from one site, stored adjacently by the key design, compress very well.
• Two levels of caching: a scan cache of key-value pairs for repeated reads of the same data, and a block cache of SSTable blocks for reads near recently read data.
• Bloom filters: for each SSTable, a filter tells whether a row and column might be present, so a read skips SSTables that definitely lack the key, avoiding many disk reads.
• Fast recovery: when a tablet moves, the new server replays only the part of the shared log relevant to that tablet, after the logs are sorted by tablet once, so the work is not repeated by every server.

Cassandra borrows Bigtable's data model, memtable, SSTables and compaction, but replaces the architecture with Dynamo's peer-to-peer ring.

• Bigtable: one master and tablet servers, strong consistency per row, storage in GFS, coordination in Chubby. A tablet is served by exactly one server at a time.
• Cassandra: no master, every node equal, data replicated by the node itself, with tunable consistency and gossip for membership.

• Gains: massive scale, a flexible sparse schema, efficient range scans by key, and automatic load balancing through tablet movement.
• Costs: no joins or multi-row transactions, a hard dependency on GFS and Chubby, and key design is essential, since a bad key causes hot tablets, such as sequential timestamps all writing to the last tablet.
• Lesson: building on layered services, GFS for durability, Chubby for coordination, Bigtable for structure, let each system stay simple. Bigtable's own code does not need to implement replication or consensus at all.