Bigtable: A Distributed Storage System for Structured Data (2006)
The Bigtable paper defines the sparse sorted row/column/timestamp model and shows how tablets, logs, memtables, immutable SSTables, compaction, locality groups, and coordination turn schema choices into distributed storage behavior.
This 14-page OSDI 2006 paper is primary evidence for Bigtable’s original logical model and architecture. It is especially valuable because it connects what an application chooses—row keys, families, versions, locality groups—to what the storage system must do—range partitioning, logging, merge reads, compaction, placement, and recovery.
Durable contribution #
Bigtable models a table as a sparse sorted map:
Rows are ordered lexicographically and operations on one row are atomic. A column family is declared and finite in number; qualifiers are data-driven and may be numerous or sparse. Each cell can retain multiple timestamped versions. This is not a relational table with joins and arbitrary cross-row transactions. The application must encode its dominant queries into row-key prefixes and ranges.
Contiguous row ranges become tablets, the unit of placement and balancing. Within a tablet, writes append to a durable log and update a sorted in-memory memtable. Immutable SSTables hold flushed state. Reads merge the memtable with candidate SSTables; block/scan caches and Bloom filters reduce I/O. Minor and merging compactions bound recovery and read amplification, while a full major compaction can reclaim tombstoned or superseded data.
The paper also makes three operational lessons concrete:
- immutable files simplify concurrent reads, tablet splits, and garbage collection;
- shared infrastructure failures include corruption, clock skew, asymmetric partitions, quota exhaustion, maintenance, and dependency bugs—not only clean crashes;
- tracing an RPC across Bigtable and its dependencies finds failures that subsystem-only health metrics hide.
Current boundary #
Cloud Bigtable retains the sorted sparse model, tablets, SSTables, row-scoped atomicity, and schema-driven locality, but the physical service is no longer the exact 2006 GFS/Chubby/tablet-server deployment. Current documentation says tablets and a shared write log live on Colossus; serving nodes hold pointers and caches rather than the durable data itself. This makes node replacement and tablet reassignment metadata operations rather than bulk data copies.
Current replication is also richer. A single-cluster route is strongly consistent; multi-cluster routing is eventually consistent by default, with read-your-writes or strong-consistency configurations available under named routing constraints. Garbage collection remains asynchronous during compaction: a version eligible by age/count can remain readable until the background pass, so read filters and retention policy are separate controls.
Visual audit #
All 14 physical pages were read and rendered. The logical row/family/version diagram and the log → memtable/SSTable read path are independently redrawn in GTK, updated for the current storage boundary. The proprietary C++ API snippets and three-level Chubby lookup tree are historical implementation details. The benchmark graph and production tables are preserved in the paper but omitted from GTK because their 2006 hardware and fleet sizes are not current design guidance.