Bigtable: Distributed Storage for Structured Data

Google's wide-column distributed database powering Search, Gmail, Maps, and YouTube. Deep dive into the data model, tablet hierarchy, read/write paths, and fault tolerance.

Published by Google in 2006, Bigtable is a distributed storage system for structured data designed to scale to petabytes across thousands of commodity servers. It underlies Google Search (web index), Gmail (email storage), Google Maps (geo data), and Google Analytics.

💡 Core idea

Bigtable is a sparse, distributed, persistent, multidimensional sorted map. The map is indexed by a (row key, column family:qualifier, timestamp) triple and each value in the map is an uninterpreted array of bytes.

Data Model

The fundamental unit of data is a cell identified by three coordinates: row key, column (family:qualifier), and timestamp. Multiple timestamped versions of a cell are kept automatically.

bigtable-data-model.sql

-- Bigtable data model: (row, column family:qualifier, timestamp) → value

Table: "webtable"

Row Key                  Column Family: "contents"        Column Family: "anchor"
─────────────────────────────────────────────────────────────────────────────────
"com.cnn.www"            contents:html@t9  → "<html>…"   anchor:cnnsi.com@t8  → "CNN"
                         contents:html@t8  → "<html>…"   anchor:my.look.ca@t5 → "CNN.com"
"com.google.www"         contents:html@t6  → "<html>…"
"com.nytimes.www"        contents:html@t11 → "<html>…"   anchor:slate.com@t9  → "NYT"

Key insight: rows sorted lexicographically by row key
Reversed domains → com.google.* groups all Google pages together

Row Key

Arbitrary string up to 64 KB. Rows sorted lexicographically. A row range is called a tablet.

Column Family

Must be declared at table creation. Unit of access control and compression. Example: contents, anchor.

Timestamp

64-bit integer (usually µs since epoch). Multiple versions per cell; configurable retention (last N or last T seconds).

Three-Level Tablet Location Hierarchy

Finding which tablet server holds a given row key requires traversing three levels of indirection. Clients cache locations aggressively — after the first lookup, reads go directly to the tablet server with zero extra RPCs.

Bigtable 3-Level Hierarchy

Cache:

Chubby

Root Tablet (Level 1)

METADATA Tablets (Level 2)

User Tablets (Level 3)

Click any node for details

Why exactly 3 levels?

• 1 level: Chubby would need to store all tablet locations — doesn't scale.

• 2 levels: Would limit total tablets to ~128 K (insufficient for Google scale).

• 3 levels: 128 K METADATA tablets × 128 K user tablets each = ~17 billion user tablets. Sufficient for petabytes.

• 4+ levels: Adds latency with no benefit at Google's data scale.

Client Read Request — Step by Step

The master is never in the read path. Clients find tablet servers autonomously through the 3-level hierarchy and then communicate directly.

Cache check

Check client cache

Does the client have a cached tablet location for this row key? If yes, skip steps 2–7 entirely.

Level 0

Query Chubby (if cold)

Read the single Chubby file storing the network address of the root tablet server. This is the only Chubby read in the entire flow.

Level 1

Root Tablet Server

Send: "Where is the METADATA tablet for row R?" The root tablet responds with the network address of the responsible METADATA tablet server.

Cache

Cache root tablet location

Client caches the root tablet location. Future requests skip step 2.

Level 2

METADATA Tablet Server

Send: "Where is the user tablet for row R?" The METADATA tablet server responds with (tablet_server_host, port, key_range).

Cache

Cache METADATA result

Client caches the user tablet location. Future reads for rows in this tablet skip steps 2–5.

Level 3

Tablet Server — GET

Client sends GET(rowKey, column, timestamp) directly to the user tablet server. No master involved!

Merge

Merge memtable + SSTables

Tablet server checks memtable, then SSTables (using Bloom filters to skip empty ones). Returns merged result.

Tablet Internals: Write & Read Paths

Write Path

WRITE PATH (SSTable + WAL): 1. Client → Tablet Server: PUT (rowKey, column, value) 2. Tablet Server: Write to WAL (Write-Ahead Log) on GFS — ensures durability 3. Tablet Server: Write to Memtable (in-memory sorted buffer) 4. Return success to client ← fast! (just memory + sequential disk write) When memtable is full → Minor Compaction: • Freeze current memtable • Write to new SSTable on GFS • Create fresh empty memtable Periodically → Major Compaction: • Merge ALL SSTables + memtable into one SSTable • Only time deleted data is physically removed (tombstones eliminated)

Read Path

READ PATH (SSTable merge): 1. Client → Tablet Server: GET (rowKey) 2. Check memtable first (most recent writes, in-memory, fast) 3. Check SSTable files in order (newest first): a. Use Bloom filter: "Does this SSTable possibly contain the key?" → NO → skip this SSTable (save I/O!) → YES → check SSTable index → seek to block → read value 4. Merge results from memtable + all SSTables: • SSTable files are immutable and sorted • Use a merge iterator (heap-based) • Return most recent version (by timestamp) Note: more SSTables = more merge work → compactions keep count low

💡 Bloom filters: the secret to read performance

Each SSTable has a Bloom filter — a compact probabilistic data structure that answers "does key K exist in this SSTable?" in O(1) with ~1% false positive rate. Without Bloom filters, every SSTable file would need to be scanned for every read. With them, reads typically touch only 1–2 files regardless of how many SSTables exist.

Master Responsibilities

The master handles only metadata and control operations. All data reads and writes go directly between clients and tablet servers — the master never touches actual data.

Bigtable master responsibilities and failure impact
Responsibility	Details	Impact if Master Fails
Tablet assignment	Assigns unassigned tablets to tablet servers on startup or after failure	New assignments blocked; existing tablets still serve requests
Server health monitoring	Monitors tablet server heartbeats via Chubby; detects failures	Cannot detect new failures; existing tablets unaffected
Load balancing	Moves tablets between servers based on load metrics	No rebalancing; hot spots persist until master recovers
Schema management	Handles table creation, deletion, column family changes	Schema changes blocked; reads/writes continue
GC of SSTable files	Removes orphaned SSTables from GFS	Storage may grow; no correctness impact

Chubby Integration

Four ways Bigtable uses Chubby

📍

Root tablet location

A single Chubby file stores the network address of the root tablet server. This is the entry point for all clients.

💓

Tablet server liveness

Each tablet server acquires an exclusive lock on a unique file in /bigtable/servers/. If the lock is lost, the tablet server commits suicide (kills itself). The master detects failure by watching this directory.

🏆

Master election

The master acquires a master lock at startup to prevent split-brain. Only one active master can exist at a time.

📋

Schema and ACL storage

Table schemas and access control lists are stored in Chubby, making them highly available and consistent.

Chubby unavailability is catastrophic

If Chubby becomes unavailable, new clients cannot perform their initial lookup. Tablet servers that lose their Chubby session suicide (to prevent split-brain). The master cannot detect failures. However, existing clients with cached locations can continue to read/write for some time.

Real-World Uses at Google

🌍 In the Wild:Google Maps

Geo data at planetary scale

Google Maps stores satellite imagery, map tiles, and Points of Interest in Bigtable. The row key encodes the geohash of the location, enabling efficient range scans for a bounding box query. Column families separate different resolutions and data types. At peak, Maps serves billions of tile requests per day from Bigtable.

🌍 In the Wild:Gmail

Email storage

Each user's email is stored with the user ID as the row key prefix. Column families separate message headers, body, attachments (stored in GFS with pointer in Bigtable), and labels. Timestamps provide automatic versioning for drafts and edits. Bigtable's sorted row keys allow efficient mailbox scans (newest-first via reverse timestamps).

🌍 In the Wild:Google Analytics

Time-series click data

Analytics stores event data with reversed timestamp row keys (so newest events are first in sort order). Column families separate different event types (pageview, click, conversion). Range scans on row key prefixes efficiently retrieve a time window for a given website. Bigtable's multi-version cells store historical snapshots.

Python HappyBase API Example

HappyBase provides a Pythonic interface to HBase (which shares Bigtable's API). The same patterns apply to Google Cloud Bigtable via the official client library.

bigtable_client.py

1import happybase
2
3# Connect to HBase (compatible with Bigtable API)
4connection = happybase.Connection('bigtable-host', port=9090)
5
6# Create a table with two column families
7connection.create_table(
8    'webtable',
9    {'contents': {}, 'anchor': {'max_versions': 10}}
10)
11
12table = connection.table('webtable')
13
14# Write a row
15table.put(
16    b'com.google.www',
17    {
18        b'contents:html':     b'<html>...</html>',
19        b'anchor:nyt.com':    b'Google',
20        b'anchor:reddit.com': b'Google Search',
21    }
22)
23
24# Read a single row
25row = table.row(b'com.google.www', columns=[b'contents', b'anchor'])
26print(row)  # {b'contents:html': b'...', b'anchor:nyt.com': b'Google', ...}
27
28# Scan a range (uses sorted row keys efficiently)
29for key, data in table.scan(
30    row_start=b'com.google.',
31    row_stop=b'com.googlez.'      # exclusive upper bound
32):
33    print(key, data[b'contents:html'][:100])
34
35# Delete a specific cell version
36table.delete(b'com.google.www', columns=[b'anchor:nyt.com'])
37
38# Read specific version (timestamp)
39row = table.row(
40    b'com.google.www',
41    columns=[b'contents:html'],
42    timestamp=1672531200000      # Unix ms
43)

Bigtable Exam Questions

These 6 questions cover the core Bigtable concepts tested in the exam. Click any question to reveal the hint, then follow the link for a full model answer.

View all 9 Bigtable questions →