Bigtable: One Sparse Table That Grows to Petabytes

In one sentence

Bigtable is a distributed storage system for structured data from Google. It organizes data as a sparse, sorted, multidimensional table — every cell located by a (row key, column, timestamp) triple, its value an uninterpreted string of bytes. The table spans thousands of machines and grows to petabytes: it slices the table into tablets by row-key range across many machines, reads and writes with an LSM-tree-style engine (an in-memory memtable + a stack of read-only SSTables on GFS + periodic compaction), stores files on GFS, and uses Chubby for coordination and leader election. It deliberately gives up the general transactions and SQL of relational databases in exchange for near-infinite horizontal scale. It is the third of Google's "big three," and the direct source of wide-column NoSQL (HBase, Cassandra).

Glossary

Where it sits

The authors are Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Mike Burrows, and other Google engineers; the paper appeared at OSDI 2006. It is the capstone of Google's "big three" distributed-systems papers, standing on the first two: its data files and logs live on GFS (Paper 17), much of its bulk data prep is done with MapReduce (Paper 18), and coordination and leader election go to Chubby (Burrows, Chubby's author, is on this byline too). Its influence outward is deep: the open-source world cloned it into HBase, and Facebook fused its data model with Dynamo's decentralized distribution into Cassandra; its single-node engine was later distilled by Dean and Ghemawat into the open-source LevelDB, which grew into Facebook's RocksDB, now a storage foundation under countless databases. Google itself kept evolving on top of it — Percolator (adding transactions), Spanner (global consistency) — and exposed it publicly as Cloud Bigtable.

Problem and motivation

By the mid-2000s Google was full of use cases that both needed to store enormous data and had unusual demands on shape and access: one row per each of billions of web pages, keeping a timestamped version per crawl; Google Earth's terabytes of satellite and map tiles; personalized-search preferences for hundreds of millions of users; assorted intermediate data from crawlers and analysis. What they shared —

• Scale far beyond one machine, even beyond parallel databases' comfort zone: tens of billions of rows, hundreds of terabytes, must be spread across thousands of cheap machines, and must scale by simply adding more.
• Loose, sparse shape: different pages have different fields; the kinds of columns can be enormous and ever-growing; most "cells" are actually empty. A fixed-schema relational table stores this awkwardly and wastefully.
• Multiple versions needed: the same page crawled at different times must all be kept — a built-in time dimension.
• But the query pattern is actually simple: the overwhelming majority of accesses are "read/write a row by its key" or "scan a range of rows," with almost no need for the complex joins and general transactions of a relational database.

Relational databases are built for "medium scale + complex queries"; forcing them onto this "huge scale + simple queries + loose, multi-version" load is both expensive and hard to scale. So Google decided not to be general, but to solve only this class of its own problems: build a store that scales out to thousands of machines, targets sparse multi-version data, and keeps only the barest necessary semantics — trading generality for extreme scale and simplicity.

Core idea / method

The data model: a sparse, sorted, multidimensional table

Bigtable's most elegant move is its data model. The paper defines it in one line: a sparse, distributed, persistent multidimensional sorted map. This map's "key" is a triple; what the "lock" opens to is a string of bytes:

(row key, column, timestamp) → value (uninterpreted bytes)

Its four dimensions, unpacked:

• Row key: an arbitrary string (up to 64 KB, usually tens of bytes). The whole table is kept in lexicographic order by row key, and reads/writes of a single row are atomic. That "sorted" property is the whole system's bedrock: encode logically related data into adjacent row keys and they sit together physically, making range scans very fast. The classic trick — Webtable reverses URLs by host into the row key (maps.google.com/index.html becomes com.google.maps/index.html), so all pages of one site fall into a contiguous range.
• Column family: columns aren't just loose columns — they're grouped into families, and a column name is written family:qualifier, e.g. anchor:cnnsi.com. The column family is the basic unit of access control, and of disk/memory accounting; families should be few (a few hundred at most) and rarely change, while the columns (qualifiers) within a family can be unbounded and added at any time. This satisfies "controllable structure" and "infinitely extensible fields" at once.
• Timestamp: a single cell can hold multiple versions, distinguished by a 64-bit timestamp and stored in decreasing time order (most recent read first). Automatic garbage collection can be set: keep the last N versions, or versions from the last N days. In Webtable, each crawl of a page leaves one version.
• Sparse: a cell never written takes up no space. So even a table with logically millions of columns wastes nothing if a given row uses just a few — exactly what lets it hold "loose, field-varying" data.

Slicing and three-level addressing: locating a row among thousands of machines

The table is sorted by row key, so it can be sliced by row-key range into tablets (about 100–200 MB each); the tablet is the basic unit of distribution and load balancing — one tablet server handles a set of tablets, and more machines just means more slices, spread wider. There are three kinds of role: one lightweight master (assigns tablets, monitors servers coming and going, balances load, garbage-collects GFS files, handles table/family creation), many tablet servers (that actually serve reads/writes), and a client library linked into each application.

The hard part: tens of billions of rows slice into a vast number of tablets — how does a client quickly find "which server owns a given row"? Bigtable borrows from the B+ tree with three-level addressing:

• Level 1: a fixed Chubby file holding the location of the "root tablet."
• Level 2 · root tablet: it is the first tablet of a special METADATA table, never split, and records the locations of all the METADATA table's other tablets.
• Level 3 · METADATA table: each row records the location of a user tablet (row key = table name + that tablet's last row).

Following "Chubby → root tablet → METADATA → user tablet" in three hops locates any row; the paper computes that this structure suffices to address 2³⁴ tablets. Clients also cache the locations they've looked up, so the vast majority of requests never touch the master — precisely why the master stays lightly loaded and never a bottleneck. Who owns a tablet is settled with Chubby locks: each tablet server creates and exclusively holds a lock on a uniquely named file in a Chubby "servers" directory; lock held means alive, lock lost means stop serving. The master watches that directory to discover new servers, and decides whether a server is truly dead or merely partitioned by whether it can grab that server's lock — then safely reassigns its tablets.

How a tablet is read and written: memtable + SSTable + compaction (the LSM engine)

This is the most beautiful engineering in the paper, and the most-copied trick since. A tablet's persistent state lives on GFS and consists of three things:

• Commit log: every update is first appended to a redo log written on GFS — a sequential write, extremely fast, and unlosable because GFS keeps multiple replicas.
• memtable: recent updates are additionally kept in a sorted in-memory buffer, blazing fast to read.
• SSTable: older updates are frozen into a series of SSTable files on GFS. An SSTable is a read-only, ordered, immutable "key→value" file, internally split into blocks (64 KB by default) with a block index at the end — one disk seek locates a key.

So the read/write path becomes:

• Write: check well-formedness and authorization (against ACLs in Chubby) → append the mutation to the commit log (batching many together, group commit) → then insert into the in-memory memtable. A write touches only "a sequential log + memory," so it's extremely fast.
• Read: form a merged view of the in-memory memtable and the stack of SSTables on disk (both sorted, so it's a merge) and read the value off it — newer versions naturally shadow older ones.

Since everything only appends to memory and log and never edits disk in place, memory eventually fills, so three kinds of compaction clean up:

• Minor compaction: when the memtable hits a threshold, freeze it, start a fresh one to keep writing, and write the frozen one out as a new SSTable to GFS. This both cuts memory use and shortens the log that must be replayed on recovery.
• Merging compaction: read a few SSTables + the memtable and write out one new SSTable, bounding the number of SSTables so it doesn't balloon (more files to merge means slower reads).
• Major compaction: rewrite all of a tablet's SSTables into exactly one, discarding all deletion markers — deleted data only truly vanishes from disk here, reclaiming space and letting sensitive data be cleared in a timely way.

This "write by append, old files read-only, background merges" is exactly the LSM-tree (log-structured merge tree) idea: trade "sequential writes + batch tidying" for very high write throughput and simple fault tolerance. Why this design is both fast and robust — writes never do random in-place disk edits (the most expensive operation on a distributed file system), only sequential appends; SSTables, once written, are immutable, so reading them needs no locking and concurrency is naturally safe, and after a crash recovery is clean: just reload SSTables from GFS and replay the log.

The tuning that makes it genuinely usable

The skeleton above isn't fast enough alone; the paper maxes out performance with a set of pragmatic optimizations:

• Locality groups: clients can group column families that are usually accessed together into a locality group, and each group is stored in its own SSTable. So reading just a page's metadata needn't drag its huge body off disk — separating rarely-co-accessed data physically makes reads cheaper. A group can also be declared in-memory (like the family storing tablet locations), for blazing lookups.
• Compression: SSTable blocks can be compressed. Many clients use a two-pass custom scheme (first find long repeated strings across a large window, then fast-compress over a 16 KB window), achieving about 10:1 on Webtable (far better than general Gzip's ~3:1) — because many near-identical versions of the same page mean lots of repetition.
• Bloom filters: reading a key would otherwise hunt through every SSTable. Giving SSTables Bloom filters lets the system first answer "this SSTable definitely lacks this row/column," skipping masses of pointless disk seeks.
• Two-level caching: a Scan Cache (caching key-value pairs returned by SSTables) + a Block Cache (caching SSTable blocks read from GFS), speeding "reading the same data repeatedly" and "reading nearby data" respectively.
• One commit log per server: if each tablet wrote its own log, one machine's thousands of tablets would write thousands of GFS files at once and lose group commit's benefit. So the whole tablet server shares one physical log, at the cost that recovery must sort the co-mingled log by (table, row, log sequence number) so one tablet's records form a contiguous run read in a single seek.
• Exploiting immutability: SSTables never change, so reading them needs no locking; deleted data is truly removed by mark-and-sweep garbage collection of SSTables; and tablet splitting is nearly free — the two child tablets simply share the parent's SSTables.

Key results

On a cluster scaling tablet servers from 1 to 500, the paper measured random reads, random writes, sequential reads/writes, and scans with 1000-byte values. The takeaways:

• Per-server throughput (values/sec, 1000-byte values) is roughly: random reads from disk slowest (~1,200), random writes and sequential reads/writes in the middle (~8,500 range), while in-memory random reads and scans are fastest (~10,000–15,000).
• Why disk random reads are slowest: for each 1000-byte value read, an SSTable must pull a whole 64 KB block from GFS — most of the bandwidth goes to "read 64 KB, use 1 KB." This also explains why random reads scale worst.
• Overall scaling is substantial but sublinear: from 1 to 500 servers aggregate throughput rises sharply, but per-server average falls with scale (load imbalance, GFS and network as shared bottlenecks), random reads most of all.
• Real-world scale: at publication Google was running 388 production Bigtable clusters on about 24,500 tablet servers; a single table could reach hundreds of terabytes (e.g. Google Analytics' raw-click table on the order of 200 TB), backing products like Google Earth, personalized search, and the crawler.

What these numbers convey isn't "it's the fastest database," but rather — under this kind of huge scale and simple load, a restricted but horizontally scalable design can fuse thousands of cheap machines into a near-infinite storage layer.

Why it matters / impact

Bigtable's contribution, like MapReduce's, lies mainly in abstraction and engineering trade-offs, not in any algorithm. It proved one thing: give up the generality of relational databases (general transactions, SQL, joins) and keep only the barest necessary semantics — read/write by row key, range scan, multi-version — and you buy near-infinite horizontal scale. The "wide-column" data model it pioneered — sorted row keys, families + unbounded qualifiers, sparse and multi-version — became a paradigm for a whole class of databases: open-source HBase is nearly a direct clone, Facebook's Cassandra grafted its data model onto Dynamo's decentralized distribution, plus Hypertable, Accumulo, and others. With GFS and MapReduce it forms Google's "big three," together defining what "big-data infrastructure" looks like. Deeper still is the set of ideas it popularized: turn logical locality into physical locality via sorted row keys, the LSM-style "sequential writes + read-only files + background merge" storage engine, trade immutable data for lock-free concurrency, and outsource coordination/leader-election to a small, reliable lock service like Chubby — all inherited by countless later systems. Its single-node engine was further distilled by Dean and Ghemawat into LevelDB, which evolved into RocksDB, now a common foundation under everything from MySQL storage engines to assorted NoSQL stores.

Limitations and criticism

• Single-row transactions only, no cross-row/cross-table transactions: the most-criticized point. To keep a consistent relationship across many rows, the application must fend for itself. Google itself soon added cross-row transactions and incremental processing atop Bigtable with Percolator, and global-scale distributed transactions with Spanner — both patching this very gap.
• No SQL, no secondary indexes, no relational queries: access is only by row key or row range. To query by "some non-row-key field," you must build your own index table or scan the whole table. Modeling requires denormalization and careful row-key design; the learning curve is steep.
• Hard dependence on Chubby and GFS: prolonged Chubby unavailability makes Bigtable unavailable (the paper honestly reports brief unavailability from Chubby outages); everything also rests on GFS's reliability.
• Tuning is a craft: how to split locality groups, whether to compress, Bloom filters, in-memory groups, row-key design — using Bigtable well takes experience, and using it poorly costs a lot of performance.
• The original is single-datacenter: the Bigtable of the paper works mainly within one cluster; cross-datacenter replication and global consistency came later (Megastore, Spanner).

Takeaways