Module 25 / Real-world systems

Module 25 · lesson 3 of 5 · Read 13 min

Bigtable: a sorted map across thousands of machines

Tablets, an LSM storage engine, and a lock service holding it together.

What you'll learn

  1. The data model: a sorted map
  2. The architecture
  3. Finding a row
  4. Inside a tablet server: an LSM tree on GFS
  5. Decision 1: lean on GFS and Chubby, keep tablet servers disposable
  6. Decision 2: one commit log per server, not per tablet
  7. Decision 3: transactions on a single row only
  8. What changed later
  9. Where you meet it today

GFS gave Google somewhere to put huge files. But many products didn't have files; they had structured data, lots of it. The web crawler kept every page it had fetched, with several versions of each. Google Earth stored imagery. Google Analytics stored per-site statistics for a huge number of websites. These workloads needed petabytes of storage on thousands of machines, high write rates, and fast lookups by key, and some needed big scans too. A traditional relational database couldn't stretch across thousands of commodity machines, and building a custom store for every product didn't scale either.

So Google built one storage system for all of them, and described it in "Bigtable: A Distributed Storage System for Structured Data" (Chang and others, OSDI 2006, Google). By then it was used by more than sixty Google products and projects. It's built on top of the previous lesson's GFS and the next lesson's Chubby, and its storage engine is the LSM tree you've already met. Its design also inspired HBase and Cassandra.

The data model: a sorted map

Bigtable is not a relational database. The paper describes it as a sparse, distributed, persistent, multidimensional sorted map. Unpack that one word at a time:

(row key, column key, timestamp) -> value (an uninterpreted string of bytes)
  • Row keys are arbitrary strings, up to 64 KB, though typically 10 to 100 bytes. Every read or write of a single row is atomic, however many columns it touches.
  • Columns are grouped into column families, written family:qualifier. Families are declared up front and are few. Qualifiers are unlimited and can be created on the fly, so one row can have millions of columns and its neighbour almost none. That's the "sparse".
  • Timestamps let each cell hold several versions. You tell Bigtable to keep, say, the last three versions, or only versions from the last week, and it garbage-collects the rest.
  • The whole table is sorted by row key. That's the most important property, because it decides what is fast.