In June I read Bigtable: A Distributed Storage System for Structured Data. I wanted to see how one storage system could support both latency-sensitive services and large analytical jobs without pretending to be a relational database.
The paper’s answer is a narrow data model combined with careful control over physical locality.
Paper: Bigtable: A Distributed Storage System for Structured Data (PDF)
The data model is a sorted multidimensional map
The paper defines Bigtable as:
(row key, column key, timestamp) → bytesRows are kept in lexicographic order. Columns are grouped into named column families, and each cell can keep multiple timestamped versions.
This is not a table in the relational sense. Values are uninterpreted bytes. There are no joins or general SQL queries. The application designs row keys and column families around the access pattern.
That restriction creates useful locality. Rows with nearby keys are stored together. If a web crawl uses reversed host names—com.example.www/page—pages from one domain share a prefix and are likely to occupy nearby storage.
Schema design is physical design
Bigtable gives the application control over data placement indirectly:
- Row keys determine ordering and tablet boundaries.
- Column families are the unit of access control and storage configuration.
- Locality groups keep selected column families in separate SSTables.
- Timestamps retain versions and support time-based cleanup.
A poor row key can create a hotspot. A monotonically increasing timestamp at the beginning of the key sends all new writes to the same tablet. Salting, hashing a prefix or reversing part of a key can distribute writes, but those choices affect scan patterns.
The main lesson is that logical schema and physical workload cannot be separated completely in a distributed store.
Tablets partition the row space
A table is split into tablets, each covering a contiguous range of rows. Tablet servers host many tablets and serve reads and writes. As a tablet grows, it splits into smaller ranges. This makes scale incremental: the unit of movement is a tablet, not a whole table.
The architecture has three main roles:
- Clients discover where a row range lives.
- A master assigns tablets, detects tablet-server changes and balances load.
- Tablet servers handle data operations directly.
The master is not on the normal read or write path. Clients cache tablet locations and communicate with tablet servers. This avoids turning the master into a data-plane bottleneck.
Locating a tablet
Tablet metadata is itself stored in Bigtable using a hierarchy. A special root tablet points to metadata tablets, which point to user tablets. The location of the root tablet is stored in Chubby.
Conceptually:
Chubby → root tablet → metadata tablet → user tabletThe client library caches locations, so most requests do not traverse the full hierarchy. A stale cache entry causes another lookup rather than corrupting placement.
This is a recurring distributed-systems pattern: keep a tiny stable root, then use it to find larger, more frequently changing metadata.
The write path
When a tablet server accepts a mutation, it first validates it and records it in a commit log. It then updates an in-memory sorted structure called a memtable.
write → commit log → memtable → immutable SSTableWhen the memtable reaches a threshold, it is frozen and written as an SSTable. SSTables are immutable, sorted files. Their immutability makes concurrent reads, caching and recovery simpler.
The commit log provides durability before the in-memory state reaches an SSTable. After a crash, a tablet server can reconstruct recent changes by replaying the log.
The read path
A read may need data from the memtable and several SSTables. The tablet server merges those sorted sources and returns the newest visible cell versions.
Reading every SSTable would become expensive as files accumulate. Bigtable uses Bloom filters to avoid disk reads for SSTables that definitely do not contain the requested row and column. A Bloom filter can produce false positives, but never false negatives.
Caching operates at different levels. A scan-oriented cache can retain SSTable blocks, while a row-oriented cache can retain reconstructed values. The right cache depends on whether the workload repeatedly fetches individual rows or scans ranges.
Compaction pays the deferred cost
Writing immutable files is fast, but it creates multiple versions and deletion markers across SSTables. Compaction combines files and removes obsolete data.
The paper describes:
- Minor compaction: convert a memtable into an SSTable.
- Merging compaction: combine a few SSTables and the memtable.
- Major compaction: rewrite all SSTables for a tablet, reclaiming deleted data.
Compaction is not free background housekeeping. It consumes disk bandwidth and CPU and can compete with foreground traffic. An LSM-style system moves work away from random writes, then has to budget that work later.
Chubby’s role
Bigtable depends on Chubby for a small but critical set of coordination tasks:
- Ensuring at most one active master.
- Storing the bootstrap location of metadata.
- Discovering tablet servers and detecting their departure.
- Storing schema information and access-control lists.
Tablet servers hold exclusive Chubby locks on files representing their membership. Losing the session and lock means the server must stop serving tablets.
Bigtable does not put all metadata traffic through Chubby. Chubby is a coordination root, not the database’s high-volume storage layer.
Recovery and reassignment
When a tablet server disappears, the master detects the lost Chubby lock and reassigns its tablets. Tablet data lives in the distributed file system, so a replacement server can open the existing SSTables and replay relevant log entries.
A shared commit log improves write throughput because one append can serve many tablets, but recovery then needs to extract mutations for specific tablets. Bigtable sorts log content during recovery so replacement servers do not each scan the entire log independently.
This shows a useful tension: batching makes the common path efficient, while recovery needs extra indexing or reorganisation to undo the batch.
What aged well
Several ideas appear repeatedly in later systems:
ordered key space → efficient range scansrange partitions → incremental splitting and movementWAL + memtable + SSTable → durable high-throughput writesBloom filters → avoid unnecessary file readscompaction → reconcile immutable storage over timesmall coordination root → keep the data plane decentralizedThe system also makes its non-goals clear. It is not a general relational database and it does not hide physical effects from schema designers.
What I keep from the paper
Bigtable is easier to understand as two cooperating systems:
- A distributed control plane assigns ordered row ranges.
- An LSM-like storage engine serves each range.
Most of the interesting behaviour comes from the boundary between them: splitting tablets, locating ranges, replaying logs, moving ownership and keeping metadata available.
When evaluating a similar design, I would ask how row keys distribute real traffic, what the compaction budget is, how quickly a lost range can be reassigned and whether the metadata root can fail safely without entering the data path.