Bigtable: what the distributed storage paper actually says

Reading Chang et al. (Google OSDI 2006) after tracing a production hot-spot to a timestamp-prefixed row key.

The alert was a tablet server CPU spike: one node at 100%, the other five at 12%. The workload was supposedly distributed. It wasn't — every write was going to the same tablet because row keys were structured as <timestamp>:<user_id>, and Bigtable sorts row keys lexicographically. All new writes clustered at the leading edge of the keyspace. The fix took twenty minutes. Understanding why the fix worked took reading the original paper.

Bigtable — "Bigtable: A Distributed Storage System for Structured Data", Chang et al., Google, OSDI 2006 — is one of those papers that gets cited more than it gets read. Most engineers who work with HBase, Cassandra, Cloud Bigtable, or Azure Table Storage are using systems that directly inherited Bigtable's design. The paper is worth reading because the design decisions made in 2006 are still live in production systems today, and the failure modes in those systems trace back to specific choices the paper documents.

The data model is three lines

Bigtable stores data as a sparse, distributed, persistent, multidimensional sorted map. The map is indexed by:

(row key, column key, timestamp) → byte array

That's it. Everything else is implementation.

Row keys are arbitrary byte strings up to 64 KB. Bigtable sorts them lexicographically and partitions the data into contiguous row ranges called tablets. Scans over a row range are efficient because the data is physically co-located. Cross-row operations are not — there's no join, no query planner, no secondary index. Your row key is your only handle on the data.

Column keys have the form family:qualifier. Column families must be declared upfront when the table is created. Within a family, qualifiers are arbitrary strings and can be created on the fly. This distinction matters: column families affect physical storage layout. All data in a column family is stored together, compressed together, and cached together. The number of distinct column families should be small (the paper says "a few hundred at most"). Qualifiers are where the flexibility lives.

Timestamps are 64-bit integers. Each cell can contain multiple versions, identified by timestamp. The Bigtable API lets you specify "keep the most recent N versions" or "keep versions newer than T" on a per-column-family basis. The paper uses a web crawl as the motivating example: contents: stores the page content, and each crawl is a new version timestamped with the crawl time. You can read the current page or any historical version with the same API.

The result is a schema that looks nothing like a relational table and nothing like a document store. It's closer to a sorted, versioned key-value store where values are organized into named groups. The power comes from the sorted row key and the physical locality of column families. The constraint is that your access patterns have to be expressible as row key lookups or row key range scans.

SSTables, memtables, and the write path

To understand Bigtable's performance characteristics, you need to understand how writes work.

Writes go to two places simultaneously: a commit log (append-only, stored in GFS) and an in-memory buffer called the memtable. The commit log provides durability; the memtable provides fast reads of recent writes. When the memtable reaches a size threshold, it's frozen and flushed to GFS as an SSTable — an immutable, sorted file of key-value pairs with a block index at the end for fast lookups.

SSTables are immutable. Once written, they never change. Updates are new entries; deletes are tombstone markers. Reads must merge data from the memtable and potentially multiple SSTables to reconstruct the current value of a cell.

This creates read amplification: the more SSTables exist for a tablet, the more files need to be consulted per read. Bigtable addresses this through compaction:

Minor compaction: flushes the memtable to a new SSTable. Reduces memory pressure, doesn't reduce the number of SSTables.
Merging compaction: rewrites several SSTables into one. Reduces read amplification without removing deleted data.
Major compaction: rewrites all SSTables for a tablet into a single SSTable. Removes tombstones and reclaims space from deleted data.

Major compactions are expensive — they read and rewrite the entire tablet. They run in the background, but they compete for disk I/O with foreground reads and writes. The paper notes that Bigtable periodically scans all tablets and performs major compactions. In production systems, this shows up as periodic latency spikes.

Tablets, tablet servers, and the master

The cluster topology is worth understanding because it determines failure behavior.

Tablet servers serve reads and writes for a set of tablets. They own the tablets assigned to them. A tablet is served by exactly one tablet server at a time — there's no multi-master serving in the original design.

The master handles tablet assignment and load balancing. It tracks which tablet servers are alive (using Chubby) and which tablets are assigned to which server. Critically, the master never serves data. Client reads and writes go directly to tablet servers, bypassing the master entirely after the initial tablet location lookup. The master is a metadata service, not a data path.

Chubby is used for three things: master election (ensuring only one master runs), tablet server liveness detection (servers hold Chubby sessions; if the session expires, the master reassigns their tablets), and storing the root of the tablet location hierarchy.

Tablet location is a three-level hierarchy:

Chubby stores the location of the root tablet
The root tablet stores the location of METADATA tablets
METADATA tablets store the location of user tablets

Clients cache tablet locations. On a cache miss, they walk this hierarchy. The paper reports that for a table with 128 MB tablets, the three-level hierarchy can address 2^34 bytes of storage, roughly enough for practical deployments.

What the performance numbers actually show

The paper's benchmarks are synthetic (sequential read, random read, sequential write, random write, scan) run on a 500-tablet-server cluster. The numbers are from 2006 hardware, so the absolute values are less interesting than the relative ratios.

Random reads from disk come in at roughly 1,200 rows/second per tablet server in the benchmark — limited by rotational disk seek time, each read requiring a disk seek. Random reads from memory (in-memory column families) run at ~100,000 rows/second — the entire dataset fits in the tablet server's block cache.

Sequential reads (scans) are substantially faster than random reads because Bigtable prefetches blocks ahead of the scan. The paper notes that scan performance scales nearly linearly as tablet servers are added.

The key production insight from the benchmarks: Bigtable is fast when your access patterns look like sequential scans, and it requires careful design when they don't. Random point reads at high QPS from disk are expensive in the original design. Systems that need low-latency random reads at scale — like Cassandra deployments — have often added bloom filters, tiered storage, and more aggressive caching precisely because the random read case is hard.

Production tradeoffs no one mentions in the benchmark post

Row key design is the entire schema. Bigtable has no secondary indexes. If you don't structure your row key correctly for your access patterns at design time, you can't add a secondary index later without a full table rewrite. The paper is clear about this: all operations are efficient only when they can be expressed as a lookup or range scan on the primary row key. Teams that come from relational databases frequently underestimate this constraint and design schemas that look relational, then discover that their most common query requires a full scan because it predicates on a non-key attribute.

Monotonic keys cause hot spots. Because Bigtable splits tablets at the boundary of the lexicographic sort, all recent writes cluster together if your key starts with a monotonically increasing value (timestamp, auto-increment ID, UUID v1). One tablet server gets all new writes; the rest idle. The standard mitigation is salting: prepend a hash of the key (or the key itself, reversed) to distribute writes. The tradeoff is that range scans by time no longer work on a single tablet — you have to scatter-gather across all salt values, which is expensive.

Column family count affects compaction overhead. Each column family is stored in a separate set of SSTables. A tablet with 20 column families has 20 sets of SSTables to compact, 20 bloom filters to consult on reads, and 20 potential disk seeks for a full-row read. The paper recommends a small number of column families, but production schemas routinely accumulate column families over time as the system evolves. The compaction burden grows with each addition.

Chubby is a hard dependency with a tight SLA. If Chubby is unavailable for longer than the configured tablet server session timeout (typically 60 seconds), tablet servers lose their locks, the master detects them as dead, and it begins reassigning tablets. During this transition, affected tablets are unavailable. The paper notes this: "Bigtable depends on Chubby for a variety of tasks." In practice this means that any Bigtable deployment needs Chubby (or its equivalent in managed offerings) to be highly available, with tight network latency between them. Teams that colocate Bigtable with Chubby in the same availability zone have lost both when the zone failed.

Major compaction is a stop-the-world event at the tablet level. Major compactions read and rewrite the entire tablet's data. For a 200 MB tablet (the default split threshold), this is significant I/O. During a major compaction, that tablet serves reads more slowly because the tablet server is competing for disk bandwidth. Clusters with many large tablets experience compaction-induced latency spikes that show up as P99 read latency degradation. The standard mitigation is to size tablets smaller and distribute compaction over more nodes, but this increases the metadata overhead.

Failure modes in practice

The most common production failure mode I've seen: the compaction backlog spiral.

Write throughput increases gradually — a new feature, a higher-traffic event, a new client. Minor compactions keep up, so the memtable flushes correctly. But merging compactions start falling behind because they share disk I/O with reads. The number of SSTables per tablet grows. Reads slow down because each read must consult more SSTables. The tablet server CPU spikes on read path merging. The team adds capacity and sees throughput recover temporarily, then the same pattern repeats as write load increases. The fix is throttling write throughput or triggering forced major compactions during off-peak hours — but diagnosing the root cause requires understanding that SSTable count, not just disk utilization, is the relevant metric.

The second failure mode is cross-row operation expectations. Teams migrating from relational databases expect to be able to do multi-row transactions: read-modify-write across several rows atomically. Bigtable supports atomic operations only at the row level. ReadModifyWrite is atomic for a single row; cross-row consistency is the application's problem. The paper is explicit about this constraint, and Spanner was built in part to address it. But teams deploying Bigtable (or HBase) often discover this after they've built application logic that assumes stronger guarantees, and the debugging is painful because the race condition is intermittent.

The third failure mode is schema rigidity masquerading as flexibility. Bigtable looks schema-less because column qualifiers can be anything. Teams use this to store heterogeneous data: different entities with different attributes all go into the same table, with the entity type encoded in the column qualifiers. This works until you need to query by attribute — which requires a full scan — or until the number of distinct qualifiers per row gets large enough that reads require many block fetches. What looked like schema flexibility turns out to be an obstacle to efficient access.

When not to use Bigtable

Multi-row transactions. If your workload requires atomic operations spanning multiple rows — a financial transfer, an inventory update, any operation that has to read several rows and write back consistently — Bigtable's single-row atomicity is insufficient. You'll be implementing distributed locking in the application layer, and you'll get it wrong eventually. Use Spanner, CockroachDB, or a relational database.

Ad-hoc query patterns. If your team frequently says "I want to query all rows where attribute X is Y," Bigtable is the wrong tool. There are no secondary indexes, no query planner, and no optimizer. Every new access pattern that doesn't fit the row key requires either a full scan or a separate index table that you maintain manually. Use a relational database or a column store with proper indexing.

Small datasets. The operational complexity of Bigtable (GFS dependency, Chubby dependency, master process, tablet server fleet, compaction management) is only justified at scale. If you have less than a few terabytes, the operational overhead almost certainly exceeds the benefit. A well-tuned PostgreSQL instance handles more QPS than most teams realize.

Frequent full-table scans. Bigtable is optimized for row key lookups and range scans on a portion of the key space. If your workload requires scanning the entire table regularly — batch analytics jobs, aggregations over all data — you're better served by a columnar store (BigQuery, Redshift, Parquet on object storage) that can push down predicates and read only the columns you need.

When you can't design the row key upfront. If your access patterns are unknown or will change frequently, Bigtable's performance will degrade as the key design becomes mismatched to actual usage. The key can't be changed without a full table migration. Systems where requirements are still evolving need schema flexibility that Bigtable doesn't provide.

What the paper actually gives you

Bigtable is a demonstration that a single careful data model decision — a sorted, versioned map — can be the foundation for a surprisingly large class of applications, if you're willing to structure your data to fit the model rather than the other way around.

The SSTable-based storage model (immutable files, compaction-based cleanup) became the backbone of LevelDB, RocksDB, and from there almost every modern key-value store. The tablet server / master separation — where the master handles metadata and assignment, and tablet servers handle the actual data path without master involvement — became a pattern for distributed databases at Google and beyond. Spanner uses a similar split. The reason the master doesn't serve data is simple: putting it on the critical read/write path would make it a bottleneck. This seems obvious in retrospect but wasn't the design of earlier systems.

The column family model — physical co-location of related attributes, with qualifiers as a flexibility layer within families — is a cleaner design than what most teams arrive at independently. It forces explicit decisions about access locality: which attributes are read together should be stored together. That discipline, applied at schema design time, matters more than the specific technology.

For your specific situation: if you're building a system with high-throughput writes, mostly range-scan reads, and data that fits into a (row, column, timestamp) model, Bigtable or its descendants are a natural fit. The paper's lessons that transfer directly are: design your row key first, keep column families small in number, expect compaction to be a background cost that needs operational attention, and don't assume single-row atomicity is enough for your consistency requirements.

The hot-spot fix from the incident at the top? We reversed the timestamp component: <reversed_timestamp>:<user_id>. Newest writes scatter across the keyspace; range scans for recent data still work by reading from the front of the reversed keyspace. The compaction load balanced across all tablet servers within a few minutes. The change was four characters in a key serialization function. Understanding why it worked took the paper.

Bigtable: A Distributed Storage System for Structured Data — Chang, Dean, Ghemawat, Hsieh, Wallach, Burrows, Chandra, Fikes, Gruber. OSDI 2006.