Bigtable Paper Explained: Tablets, SSTables and Distributed Storage

Historical Context

Published by Fay Chang et al. at Google in 2006 (OSDI), Bigtable was built to manage petabytes of structured data across Google's products — web indexing, Google Earth, Google Finance, and Gmail all used it. Google needed something between a raw file system (GFS) and a full relational database: a system that could store billions of rows with flexible schemas, scale horizontally, and integrate with MapReduce for batch analytics. Traditional RDBMS could not scale to Google's data volumes, and key-value stores lacked the structure needed for efficient scans.

Core Problem

How do you store and serve petabytes of sparse, semi-structured data with predictable low-latency access, while scaling to thousands of machines and integrating with existing batch processing infrastructure?

Key Innovation

Bigtable organizes data as a sorted map indexed by (row key, column key, timestamp). Rows are sorted lexicographically by key, enabling efficient range scans. Columns are grouped into column families, which are the unit of access control and compression. Each cell can hold multiple timestamped versions.

The table is split into tablets — contiguous ranges of rows, typically 100-200 MB each. Each tablet is served by exactly one tablet server, and tablets are automatically split or merged as data grows or shrinks. A master server assigns tablets to tablet servers and handles load balancing.

The storage layer uses an LSM-tree approach: writes go to an in-memory memtable; when the memtable reaches a threshold, it is flushed to an immutable SSTable file on GFS. Reads merge data from the memtable and one or more SSTables. Periodic compaction merges SSTables to reclaim space and reduce read amplification. Bloom filters on SSTables reduce unnecessary disk reads for keys that do not exist.

Bigtable relies on Chubby (a Paxos-based lock service) for master election, tablet server registration, and schema storage.

Architecture / Algorithm

• Data Model: Sparse, distributed, persistent sorted map (row, column, timestamp) to value.
• Column Families: Groups of related columns; the basic unit of access control.
• Tablets: Row-range partitions, each served by one tablet server.
• Memtable + SSTables: LSM-tree write path for high write throughput.
• Compaction: Minor (memtable flush), major (merge multiple SSTables).
• Bloom Filters: Probabilistic data structure to avoid reading SSTables that lack a requested key.
• Chubby: External lock service for coordination.

Strengths

• Scales to petabytes across thousands of servers
• Flexible schema: columns can be added per-row without migration
• High write throughput via LSM-tree storage
• Efficient range scans due to sorted row keys

Weaknesses

• No cross-row transactions (addressed later by Spanner)
• Single tablet server per tablet can create hotspots for popular key ranges
• Schema design is critical: poor row key design leads to unbalanced tablets
• Eventual consistency for replication across clusters

Modern Systems Influenced

Apache HBase is a direct open-source clone. Cassandra borrowed Bigtable's column-family data model and SSTable storage format (combined with Dynamo's partitioning). Google Cloud Bigtable is the managed public offering. The memtable + SSTable + compaction pattern is now standard in LevelDB, RocksDB, and most LSM-based stores.

Interview Relevance

Reference Bigtable when designing a wide-column store, time-series database, or any system requiring fast writes with range-scan capability. Know the tablet-splitting strategy, the LSM write path (memtable to SSTable to compaction), and why sorted row keys matter for scan performance. Bigtable's architecture is the expected answer structure for "design a distributed NoSQL database."

Plain-English Summary

Bigtable stores massive tables of data sorted by row key, split into tablet-sized chunks across many servers. Writes land in memory first, then flush to sorted files on disk. Reads merge in-memory and on-disk data. Column families let you group related data for efficient access. The design handles petabytes by automatically splitting and rebalancing tablets as data grows.

Original DosiBridge notes for Bigtable Paper Explained: Tablets, SSTables and Distributed Storage

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Bigtable Paper Explained: Tablets, SSTables and Distributed Storage is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Practice Loop: For Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, decide the practice loop before choosing tools; otherwise the design looks clean but fails when bigtable changes.
• Implementation Exercise: For Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, decide the implementation exercise before choosing tools; otherwise the design looks clean but fails when bigtable changes.
• Review Checkpoint: For Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, decide the review checkpoint before choosing tools; otherwise the design looks clean but fails when bigtable changes.
• Failure Drill: For Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, decide the failure drill before choosing tools; otherwise the design looks clean but fails when bigtable changes.
• Comparison Target: For Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, decide the comparison target before choosing tools; otherwise the design looks clean but fails when bigtable changes.

Production review question

If a team adopts Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track bigtable health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Bigtable Paper Explained: Tablets, SSTables and Distributed Storage, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.

Sources

• Bigtable: A Distributed Storage System for Structured Data — Chang et al., 2006