Wide-column stores (Bigtable)
Sorted rows with sparse columns: range scans over petabytes.
01The intuition
The problem it solves
A school keeps attendance for 2,000 students over 200 days in one big grid, students down the side, days across the top. Most cells are empty (nobody is absent most days), and the questions asked are always "show me Rao's row" or "show me all students from Rao to Sharma". Storing the grid as a spreadsheet wastes space on empty cells and makes a row of one student a scatter of disk reads.
Many large datasets have this shape: a huge number of rows, each with a different, sparse set of columns, read by row and by row range. Web pages by URL with dozens of optional attributes, users by id with hundreds of possible settings, sensor readings by device and time. A wide-column store is built for exactly that: rows sorted by key, columns sparse and grouped, range scans cheap.
Build it one piece at a time
Step 1: a sorted map of rows. Every row has a key, and rows are kept sorted by that key. A row is itself a map from column name to value. Rao's row holds only the days Rao was absent; empty cells do not exist.
Step 2: group columns into families. Columns that are read together go in a family stored together on disk: attendance: for the days, profile: for name and class. Reading Rao's attendance never touches the profile bytes.
| Row key | profile:name | attendance:2026-07-14 | attendance:2026-09-02 |
|---|---|---|---|
| class10/rao | Rao | absent | |
| class10/sharma | Sharma | absent |
Step 3: design the row key for the scans you need. Because rows are sorted, "all students in class 10" is a range scan if the key starts with the class. For web pages, Bigtable's famous trick is to reverse the domain (com.google.maps/index) so all pages of one site sit together.
Step 4: keep versions. Each cell can hold several timestamped values. "Rao's attendance as of last month" is a read at an older timestamp; old versions are garbage-collected by a per-family rule (keep 3 versions, or keep 30 days).
Step 5: split into tablets. The sorted key space is cut into contiguous ranges called tablets, each served by one server and stored as LSM files (LSM versus B-tree). When a tablet grows past 1 GB it splits; a master assigns tablets to servers and moves them when a server dies. Single-row operations are atomic because a row lives in exactly one tablet; multi-row transactions are not offered.
Why it works, with the numbers
Sparsity is free: a row costs only the cells it has. For the attendance grid:
spreadsheet: 2,000 × 200 = 400,000 cells; wide-column: about 2,000 × 8 absences = 16,000 cells, 25 times smaller
Range scans are sequential: 500 consecutive rows come from one or two tablets as one disk sweep instead of 500 random lookups. Writes scale with tablets: each tablet server absorbs tens of thousands of writes a second, and tens of thousands of tablets spread a petabyte over a few thousand machines. The guarantees are sorted order, atomic single-row updates, and cheap versioned reads. The failure modes are a hot row range (sequential keys like timestamps put every new write on the last tablet; salt or reverse the key), a row that grows without bound (one key with a million columns), and the master as a point of failure (it only assigns tablets, so reads continue while it is replaced).
The trade-off you must say out loud
You give up joins, secondary indexes and multi-row transactions, and you must know your scans in advance to design the key. In return you get petabyte tables with predictable per-row latency. Say what the row key is, what the families are, and which scan the key order serves. The next question is nearly always "how do you avoid a hot tablet with time-ordered keys?", and the answer is to prefix the key with a hash or a device id so writes spread across tablets.
Where it shows up in the 100 Google problems
- Design Bigtable: the question is the data model and the tablet machinery above, plus the LSM engine under each tablet.
- Design Google Search: the crawl table keyed by reversed URL, with families for content, links and crawl status, is the classic use.
- Design a metrics and monitoring system: a key of metric name plus time bucket turns "the last hour of this metric" into one short range scan.