Chang et al (2006) - Bigtable: A Distributed Storage System for Structured Data

Background

By 2006 Google ran dozens of services — search indexing, Maps, Gmail, Analytics — each needing a scalable store, and each team used to build one from scratch. Bigtable was the answer: one distributed storage system designed to serve Google's diverse workloads over thousands of commodity servers, described in this OSDI paper by Chang, Dean, Ghemawat and colleagues.

The Data Model

Bigtable is a sparse, distributed, persistent, multi-dimensional sorted map. Data is addressed by (row key, column key, timestamp) to a value. Rows are sorted lexicographically, which makes row ranges the locality primitive; columns are grouped into column families with common properties; timestamps provide versioning. This single abstraction served everything from web crawl (rows = URLs) to Maps (rows = geographic regions).

Deep Dive

The system splits rows into tablets — contiguous ranges, the unit of load balancing. A master assigns tablets to tablet servers, which serve reads and writes; data lands first in a memtable and is flushed to SSTable files on the Google File System, with a commit log for durability. Compactions merge files in the background, and Bloom filters avoid disk reads for absent keys. The paper reports serving thousands of servers with high availability, and the design directly influenced HBase, Cassandra, and the NoSQL movement's vocabulary — though Bigtable itself offers only eventual consistency across tablets.

Why It Matters

Bigtable proved that a simple sparse sorted-map model could hold Google-scale data with operational simplicity, and it is the missing link between the relational era and NoSQL. Its row-key design lesson — locality is a choice you make at write time — still governs schema design in HBase, Cassandra, and columnar lakehouse tables.

Key Takeaways

• Row-key design determines locality and scan performance — design for the read pattern, not the write pattern.
• Column families define storage and memory semantics; overloading them mixes access patterns.
• Versions via timestamps are cheap in model, expensive in practice — bound them.