Paper · Distributed Systems

Bigtable: A Distributed Storage System for Structured Data

F. Chang et al. · OSDI · 2006

How Google stored structured data at planet scale, and a blueprint for many NoSQL systems.

Summary

Google needed to store petabytes of structured data for products such as web indexing and Google Earth, with high throughput and low latency, on commodity machines. Traditional relational databases did not scale this way, so Google built a simpler data model that could.

Bigtable is a sparse, distributed, persistent, sorted map indexed by row key, column and timestamp. Tables are split into tablets by row range and served by tablet servers. Each tablet is stored as a memtable plus immutable SSTables in the Google File System, and Chubby provides locking and coordination.

Bigtable inspired HBase and Cassandra's data model, and its memtable and SSTable design helped popularise LSM-style storage. It is a good case study of the trade-offs involved in giving up relational features to scale.

Key ideas

  • A sparse, sorted, multidimensional map keyed by row, column and timestamp.
  • Tables split into tablets by row range, served by tablet servers.
  • Memtables and immutable SSTables stored on a distributed file system.
  • A lock service (Chubby) for coordination and metadata.

More Distributed Systems papers