Skip to content
Bigtable: A Distributed Storage System for Structured Data 4 min

Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber · OSDI 2006

Bigtable: A Distributed Storage System for Structured Data

Google's giant sorted map explained: rows, column families, tablets, and the commit log, memtable and SSTable recipe, with two playgrounds for row keys and compaction.

Read the original paper

Databases · Yellow Belt · Pro · 4 min read

Bigtable: A Distributed Storage System for Structured Data

A relational database keeps its data in neat tables and answers any question with SQL. That is wonderful until your data is a copy of the whole web, or a billion users' settings, and no single machine can hold it. Google needed something that spread over thousands of ordinary servers and kept working when some of them died.

Bigtable is what they built. It is not a relational database. It is a giant sorted map that scales to petabytes, and its design is a sampler of ideas you will meet in every large storage system: sorted rows, splitting into tablets, a write log, and memory tables flushed into immutable files.

Bigtable is a sparse, sorted, multi-dimensional map from (row, column, time) to bytes. Rows are split into ranges called tablets that live on different servers. Writes go to a log and a memory table first, then are flushed to immutable files that are merged in the background.

A big sorted map

The paper describes Bigtable as a "sparse, distributed, persistent multidimensional sorted map." That is a mouthful. Break it down:

  • Map: you look up a value by a key made of a row key, a column key and a timestamp.
  • Sorted: rows are kept in order by their key, so neighboring keys live together.
  • Sparse: a row can use any columns it likes. Empty columns cost nothing.
  • Versioned: each cell can hold several timestamped versions, newest first.

The paper's running example is a table of web pages. The row key is the page's address with the domain reversed (com.cnn.www). One column family holds the page contents, another holds the link text other pages used to point at it.

Think of a huge, sorted phone book that grows forever. You find a person by looking up the name (row), then the kind of number (column), and each entry keeps its history. You cannot ask "all people whose number ends in 7" quickly, only "all people in this range of names."

Tablets: how a table spreads over machines

Bigtable cuts the sorted rows into contiguous ranges called tablets. A tablet is the unit of distribution and load balancing. Each tablet server owns many tablets, and a table starts as one tablet and splits as it grows.

Because Bigtable keeps rows in sorted order, the row key is the main design decision. Reversed domain names such as com.google.maps keep related pages in the same tablet, so one scan touches few machines.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 3 interactive elements to play with

  • Inside a tablet server: log, memtable, SSTables
  • Why it matters

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.