Design Bigtable: a wide-column store

01The design, in the six-step framework

1. Requirements

Functional

• Tables of rows keyed by an arbitrary byte string, kept sorted by key; each row has column families, and each cell may keep several timestamped versions.
• Operations: read a row or a range of rows, write or delete cells in one row atomically, scan a key range.
• Out of scope: multi-row transactions, secondary indexes, SQL.

Non-functional

• Petabytes per table, thousands of machines, millions of reads and writes per second.
• Single-row writes are atomic; a reader never sees half of a row mutation.
• Range scans stream at disk bandwidth; a point read is a few milliseconds.
• Machines fail routinely; a tablet is unavailable for at most seconds during reassignment.

2. Core entities

• Table: name, column families (each with compression and version-retention settings).
• Tablet: table, start key, end key, assigned tablet server, list of sorted files, log position.
• Cell: row key, column family, column qualifier, timestamp, value.
• Tablet server: id, lease in the lock service, tablets served, memtable size.

3. API

• Mutate(table, row, [set(family:qualifier, value, ts) | delete(...)]) → applied atomically to one row.
• Read(table, row, filter) → the cells of one row matching a column and version filter.
• Scan(table, startKey, endKey, filter) → a stream of rows in key order.
• Admin: CreateTable, AddFamily, SplitTablet(key).

4. High-level design

A write and a read of row com.example.www/index.html:

1. The client finds the tablet: root tablet location from the lock service, then the METADATA tablet that covers the table, then the user tablet's server. All three are cached; a cold client makes three lookups, a warm one none.
2. The tablet server appends the mutation to a commit log on the distributed file system (one log per server, shared by its tablets), then applies it to the in-memory memtable. The write is acknowledged. Because the whole row mutation is one log record, it is atomic.
3. A read merges the memtable with the tablet's sorted files on disk, newest first, filtering versions.
4. When the memtable reaches a threshold it is written as a new sorted immutable file; periodic compactions merge files and discard deleted or superseded cells.

5. Deep dives

How does a tablet move to another server in seconds when a machine dies?

Each tablet server holds an exclusive lease in the lock service; the master watches those leases. When a server's lease lapses, the master knows its tablets are orphaned and assigns them to live servers. The new server reads the tablet's sorted files straight from the shared file system (nothing to copy) and replays the tail of the dead server's commit log since the last flush to rebuild the memtable. Replay is the only cost, and it is bounded by the flush interval; sorting the shared log by tablet first lets several servers replay their parts in parallel. The master itself is stateless apart from what it can rebuild by asking servers and reading the METADATA table, and election through the lock service ensures there is exactly one.

Why sorted keys and one-row atomicity, and what do they buy?

Sorting by key is the feature. Reverse-domain row keys put every page of a site next to each other, so a crawl scan of one host is one contiguous range on one or two tablets, and clients control locality by designing keys. Single-row atomicity falls out of the write path (one log record, one memtable update) and is enough for a huge class of workloads: a row holds everything about one page or one user. Multi-row transactions would need coordination across tablet servers and were deliberately left out; later systems (Spanner) added them with a very different cost. Column families are the unit of compression and access control; versions with timestamps give cheap history and a garbage-collection policy per family.

The metadata hierarchy: how does a client find one of 300,000 tablets without a bottleneck?

A three-level tree: the lock service holds the location of a single root tablet; the root tablet holds the locations of all METADATA tablets; each METADATA tablet holds locations of user tablets, keyed by (table, end key). With 1 KB per entry and 128 MB tablets, two levels address 2³⁴ tablets, far beyond need. Clients cache locations and only refresh on a miss (a stale cache produces a "not my tablet" error from the server, which triggers one more lookup). The result is that the master and the lock service are off the read and write path entirely; a lock-service outage stops new assignments and cold lookups but not traffic to tablets whose locations are cached.

Hot tablets and splits

A tablet that grows past about 1 GB, or receives far more traffic than its neighbours, is split at a middle key: the server writes two METADATA entries and tells the master, with no data copied because sorted files are immutable and both children reference the same files until compaction. Load balancing then moves one child to a quieter server. The remaining hot spot is a single hot row (one page everyone writes to), which no split cures; the answer is in the key design (salt the key, or spread counters across many rows) and in the application, and a strong candidate says so rather than promising the system handles it.

Reads at scale: why most point reads never touch a disk file

A read must merge the memtable with every sorted file of the tablet, which could be a dozen files after a burst of flushes. Two caches keep that cheap: a block cache holding recently read file blocks, and a Bloom filter per file that answers "this row is not in this file" with no disk access for almost all files. A scan does not benefit from Bloom filters but reads each file sequentially, which is what disks do best. Compaction keeps the file count low; a tablet server throttles it so a compaction never steals all the disk bandwidth from live reads, and that throttle is a tuning knob worth mentioning.

6. What a strong answer sounds like

• Explain the data model first (sorted rows, families, versions) and what each choice is for.
• Do the tablet arithmetic and show why a three-level metadata tree with client caching keeps the master off the hot path.
• Describe recovery as "replay the log tail from shared storage", and why leases in the lock service make reassignment safe.
• Be clear about what is not offered (cross-row transactions, secondary indexes) and why.
• Expect follow-ups on compaction amplification, Bloom filters for reads, read caches, and the LSM trade-offs in LSM trees and B-trees.
• Common mistake: proposing a hash-partitioned key space and losing the range scans that make the system useful.

02Where this question was reported

• resumegeni.com · Canonical L5+ problem; 2006 paper called required reading.