SystemExperts
SystemExperts
Browse all content

On this page

Navigation

  • 1The Problem: Structured Data at Google Scale
  • 2Data Model: The Multi-Dimensional Sorted Map
  • 3Row Key Design: Encoding Locality
  • 4Architecture: Tablets and Tablet Servers
  • 5Tablet Location: A Three-Level Hierarchy
  • 6Tablet Representation: SSTables and Memtable
  • 7Compaction: Merging SSTables
  • 8Tablet Serving
  • 9Refinements: Compression and Caching
  • 10Locality Groups: Co-Locating Column Families
  • 11Real-World Applications
  • 12Performance Characteristics
  • 13Bigtable's Legacy: NoSQL Movement
  • 14Trade-offs

14 sections in this document

TermsPrivacy© 2026 SystemExperts
distributed-systemsstoragedatabasenosqlgooglelsm-treewide-columnadvanced

Bigtable: A Distributed Storage System for Structured Data

The sparse, distributed, persistent multi-dimensional sorted map that powers Google Search, Maps, YouTube, and Gmail

Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber
Google
2006
35 min read
View Original Paper

Summary

Bigtable is a distributed storage system for managing structured data designed to scale to petabytes across thousands of commodity servers. It provides a simple data model: a sparse, distributed, persistent multi-dimensional sorted map indexed by row key, column key, and timestamp. Bigtable doesn't support a full relational model, but gives clients dynamic control over data layout and format, allowing them to reason about locality. Built on GFS for storage and Chubby for coordination, Bigtable became the foundation for Google's most critical services and inspired an entire generation of NoSQL databases including HBase, Cassandra, and Cloud Bigtable.

Key Takeaways

Sparse Multi-Dimensional Sorted Map

Data is indexed by (row, column, timestamp) and stored in lexicographic row order. Rows are the unit of transactional consistency. This simple abstraction supports wildly different data—from web pages to satellite imagery—with the same API.

Tablets: The Unit of Distribution

Tables are split into tablets (100-200 MB), each holding a contiguous range of rows. Tablets are the unit of distribution and load balancing. As tables grow, tablets split automatically. This enables horizontal scaling without application changes.

Column Families for Locality

Columns are grouped into column families, which are the unit of access control and storage. Data in the same column family is stored together on disk. This allows applications to co-locate related data for efficient access patterns.

LSM-Tree Storage Engine

Writes go to an in-memory buffer (memtable), then flush to immutable sorted files (SSTables) on GFS. Reads merge data from memtable and SSTables. Compaction merges SSTables to reclaim space and reduce read amplification.

Single-Row Transactions

Bigtable provides atomic read-modify-write operations on single rows. No cross-row transactions—this constraint enables horizontal scaling. Applications requiring multi-row atomicity must implement it at the application layer.

Client-Controlled Locality

Row key design determines data distribution and access patterns. Applications encode locality into keys (e.g., reversed URLs: com.google.www). This gives clients direct control over performance characteristics.

Deep Dive

The Problem: Structured Data at Google Scale

By 2006, Google needed to store and query structured data across dozens of services:

  • Web Search: Billions of URLs, each with content, links, anchors, PageRank, crawl history
  • Google Earth: Petabytes of satellite imagery with spatial indexes
  • Google Finance: Time series of stock prices, news, financial data
  • Personalization: Per-user preferences, history, recommendations

Each project faced similar challenges but had different data patterns.

Why not use a relational database?

  1. Scale: No RDBMS could handle Google's data volume on commodity hardware
  2. Cost: Commercial databases at this scale would cost billions
  3. Flexibility: Fixed schemas don't fit rapidly evolving products
  4. Control: Google needed to tune storage for specific access patterns

Why not use raw files (GFS)?

  1. No structure: Files don't support efficient point queries
  2. No indexing: Full scans for every query
  3. No locality: Related data scattered across files
  4. Application complexity: Every team reimplements storage logic

Bigtable sits between these extremes: more structure than files, more flexibility than RDBMS.

Data Model: The Multi-Dimensional Sorted Map

Bigtable is a sparse, distributed, persistent multi-dimensional sorted map:

(row:string, column:string, timestamp:int64) → string

That's it. Everything else is built on this simple abstraction.

Row keys: - Arbitrary strings up to 64KB (typically 10-100 bytes) - Sorted lexicographically - Single-row operations are atomic - Determines data distribution (adjacent rows → same tablet)

Column keys: - Grouped into column families (e.g., `anchor:cnnsi.com`) - Family must be created before use; qualifiers are dynamic - Family is the unit of access control and storage - Designed for tens-to-hundreds of families, unlimited columns

Timestamps: - 64-bit integers (microseconds or application-assigned) - Multiple versions stored per cell - Garbage collection: keep last N versions or versions newer than T

The "sparse" property:

Unlike relational tables, rows don't need the same columns. A row might have 3 columns while another has 3,000. Empty cells don't consume storage.

Row Key Design: Encoding Locality

Row key design is the most important decision when using Bigtable. The key determines:

  1. Which tablet stores the row (distribution)
  2. Which rows are adjacent (locality)
  3. Query efficiency (scans vs. point lookups)

Web table example:

Google's web crawl uses reversed URLs: - Key: `com.cnn.www/sports/index.html` - All pages from `cnn.com` are adjacent - Efficient scan: "all pages from cnn.com"

Time-series example:

For logs or metrics: - Bad key: `timestamp` (hot tablet at current time) - Good key: `user_id#timestamp` (distributed across users) - Or: `timestamp_bucket#user_id` (recent data on fewer tablets)

Key design patterns:

| Pattern | Use Case | Example | |---------|----------|--------| | Reversed domain | Web pages | `com.google.www` | | Hash prefix | Avoid hot spots | `md5(user)[:4]#user_id` | | Composite key | Range scans | `user#timestamp#action` | | Padded numbers | Correct sort | `user#00000123` |

Anti-patterns: - Monotonically increasing keys (hot tablet) - Putting highly variable data at key start - Very long keys (storage overhead)

Architecture: Tablets and Tablet Servers

Bigtable has three major components: a library linked into every client, one master server, and many tablet servers.

Master responsibilities: - Assigning tablets to tablet servers - Detecting tablet server additions and expirations - Balancing tablet server load - Garbage collection of GFS files - Handling schema changes (table/column family creation)

What the master does NOT do: - Route client data requests (clients go directly to tablet servers) - Store any tablet data (all data on GFS) - Become a bottleneck (clients cache tablet locations)

Tablet server responsibilities: - Manages a set of tablets (typically 10-1000 tablets) - Handles read and write requests to its tablets - Splits tablets that have grown too large

Chubby (distributed lock service): - Ensures at most one active master - Stores bootstrap location of tablet metadata - Discovers tablet servers and tracks liveness - Stores schema information and ACLs

Tablet Location: A Three-Level Hierarchy

Clients need to find which tablet server holds a given row. Bigtable uses a three-level hierarchy similar to a B+ tree:

How lookup works:

  1. Client reads ROOT tablet location from Chubby (cached)
  2. Client queries ROOT tablet for METADATA tablet location
  3. Client queries METADATA tablet for user tablet location
  4. Client queries user tablet directly

Caching is critical:

  • Client caches tablet locations
  • On cache miss or stale entry, walk up the hierarchy
  • Typical operation: 0 RPCs (cache hit) or 3 RPCs (cold start)

METADATA table structure:

Each METADATA row stores: - Row key: `table_id + end_row` - Location: tablet server address - Log info: for recovery

Scale: - ~128 MB METADATA tablets with 1KB rows - Each METADATA tablet tracks ~128K user tablets - 2^17 METADATA tablets → 2^34 user tablets - At 128MB each → ~2^61 bytes = 2 exabytes

Tablet Representation: SSTables and Memtable

Each tablet is stored as a collection of SSTables (Sorted String Tables) plus an in-memory memtable. This is the Log-Structured Merge-tree (LSM-tree) architecture.

Write path:

  1. Write arrives at tablet server
  2. Append to commit log (WAL) on GFS
  3. Insert into memtable (in-memory sorted buffer)
  4. Acknowledge to client
  5. When memtable reaches threshold (~200MB), flush to new SSTable on GFS

Read path:

  1. Check memtable first (most recent data)
  2. Check SSTables from newest to oldest
  3. Merge results, return latest version for each cell
  4. Bloom filters avoid checking SSTables that don't have the key

SSTable format:

  • Immutable once written
  • Sequence of data blocks (~64KB each)
  • Sparse index: one entry per block (not per key)
  • Optional Bloom filter: false positives OK, false negatives not
  • Optional compression per block

Why LSM-tree?

  • Writes are fast: Always sequential (memtable + append-only log)
  • Reads are acceptable: Bounded by number of SSTables (reduced by compaction)
  • Space efficient: Compression works well on sorted data
  • GFS-friendly: Large, immutable files (no random writes)

Compaction: Merging SSTables

As memtables flush to SSTables, the number of SSTables grows. Compaction merges SSTables to bound read amplification and reclaim space from deleted data.

Minor compaction: - Triggered when memtable reaches size threshold - Converts memtable to SSTable - Reduces memory usage - Bounds recovery time (fewer log entries to replay)

Merging compaction: - Merges a few SSTables into one - Runs in background continuously - Bounds number of SSTables (bounds read cost) - Doesn't remove deleted data (deletions are tombstones)

Major compaction: - Merges ALL SSTables for a tablet into one - Removes deletion tombstones and old versions - Only way to truly reclaim space - Periodic (e.g., weekly) or triggered by space pressure

Compaction trade-offs:

| Aspect | More Compaction | Less Compaction | |--------|-----------------|----------------| | Read latency | Better (fewer files) | Worse (more files) | | Write amplification | Higher (rewrite data) | Lower | | Space amplification | Lower | Higher (tombstones) | | CPU usage | Higher | Lower |

Tuning compaction is one of the main operational concerns with LSM-tree systems.

Tablet Serving

When a tablet server starts serving a tablet, it must recover its state from GFS:

Tablet load steps:

  1. Acquire lock: Tablet server gets exclusive lock from Chubby
  2. Read metadata: Location of SSTables and end of commit log
  3. Load SSTable indexes: Index blocks and bloom filters into memory
  4. Replay commit log: Reconstruct memtable from recent writes
  5. Ready to serve: Tablet is now online

What happens on tablet server failure?

  1. Master detects via Chubby (lock expiration)
  2. Master reassigns tablet to another server
  3. New server loads tablet from GFS (data is durable)
  4. Replays commit log entries
  5. No data loss (GFS replication protects SSTable and logs)

Tablet splits:

When a tablet grows too large (> 200MB typically): 1. Tablet server picks a split key 2. Notifies master 3. Master creates two new tablets 4. Both tablets served by same server initially 5. Master may reassign for load balancing

Refinements: Compression and Caching

Bigtable includes several refinements to improve performance and reduce costs:

Compression:

  • Applied per SSTable block
  • Two-pass scheme: first pass finds long repeated strings (common in web pages), second pass compresses
  • Typical compression: 10:1 for web content
  • Decompression on-demand per block (not whole file)

Caching (two levels):

  • Scan Cache: Caches key-value pairs returned by SSTable interface. Good for repeated reads of same data.
  • Block Cache: Caches SSTable blocks from GFS. Good for spatial locality (reading adjacent rows).

Bloom filters:

  • Small data structure that probabilistically answers "is key in this SSTable?"
  • False positives possible (check SSTable unnecessarily)
  • False negatives impossible (never miss data)
  • Dramatically reduces disk reads for non-existent rows

Commit log optimization:

  • One log per tablet server, not per tablet
  • Reduces disk seeks (one write stream)
  • Complicates recovery (log contains multiple tablets)
  • Recovery parallelized across tablet servers

Locality Groups: Co-Locating Column Families

Locality groups allow clients to group column families that are typically accessed together. Each locality group is stored in a separate set of SSTables.

Why locality groups matter:

Consider a web crawl table with: - `contents`: Large HTML blobs (~100KB) - `anchor`: Small link text (~100 bytes) - `language`: Tiny metadata (~10 bytes)

Without locality groups: - Reading `language` for all pages loads `contents` too (huge I/O waste)

With locality groups: - `language` in separate SSTable files - Can scan language data at near-disk bandwidth - `contents` never loaded

In-memory locality groups:

  • Mark a locality group as in-memory
  • Loaded entirely into tablet server memory
  • Good for small, frequently accessed data (metadata, indexes)
  • Reduces latency from milliseconds to microseconds

Compression per locality group:

Different data compresses differently: - `contents`: High compression (similar HTML structure) - `anchor`: Medium compression (variable text) - Binary data: Low or no compression

Real-World Applications

Bigtable powers some of Google's most critical and largest services:

Google Analytics:

  • Row key: `website_id#reversed_timestamp`
  • Columns: page views, referrers, geographic data
  • Access pattern: Time-range scans per website
  • Scale: ~200 billion rows

Google Earth:

  • Row key: Spatial encoding (e.g., S2 cell ID)
  • Columns: Image tiles at different resolutions
  • Access pattern: Spatial range queries
  • Locality group: Different resolutions in different groups

Personalization:

  • Row key: User ID
  • Columns: Preferences, history, recommendations
  • Access pattern: Point lookups by user
  • Scale: Billions of users, low latency requirement

Web Crawl (Webtable):

  • Row key: Reversed URL
  • Column families: `contents:`, `anchor:`, `pagerank:`
  • Access pattern: URL lookup + domain scans
  • Scale: Hundreds of petabytes
  • "The original Bigtable use case"

Performance Characteristics

The paper reports performance benchmarks from a 2006 deployment:

Key performance observations:

Random reads vs. writes: - Random reads: 1212 ops/sec/server (limited by disk seeks) - Random writes: 8850 ops/sec/server (memtable absorbs writes) - Writes are 7x faster because they go to memory first

Sequential access: - Sequential reads: 14972 ops/sec/server (disk bandwidth) - Sequential writes: 8547 ops/sec/server (commit log + memtable) - Scans: 94518 rows/sec/server (max disk bandwidth)

Scaling: - Near-linear scaling up to hundreds of servers - Per-server throughput decreases slightly due to load imbalance - Aggregate throughput increases linearly with servers

Production clusters (2006):

| Metric | Range | |--------|-------| | Clusters | 388 | | Tablet servers per cluster | 1 to 500+ | | Total tablets | 24,500+ | | Total data | 200+ TB per cluster | | Read throughput | 1M+ ops/sec aggregate |

Bigtable's Legacy: NoSQL Movement

Bigtable didn't just solve Google's storage problems—it sparked the NoSQL movement and influenced a generation of databases:

Direct descendants:

  • HBase: Open-source Bigtable on HDFS. Used by Facebook, Twitter, Adobe.
  • Cloud Bigtable: Google's managed service. Same API as original.
  • Hypertable: C++ Bigtable clone (less popular now).

Inspired systems:

  • Cassandra: Combined Bigtable's data model with Dynamo's distribution. Wide-column + masterless.
  • LevelDB/RocksDB: LSM-tree storage engines. Powers countless databases.

Lessons for system design:

  1. Right abstraction level: Not as flexible as files, not as structured as RDBMS. Sweet spot for many workloads.
  1. Client-controlled locality: Row key design puts optimization in client hands.
  1. Build on proven foundations: GFS for storage, Chubby for coordination. Don't reinvent everything.
  1. Optimize for your workload: Single-row transactions aren't a bug, they're a feature enabling scale.
  1. LSM-trees work: Write-optimized storage is practical. Read costs manageable with compaction.

When to use Bigtable-style systems: - High write throughput needed - Wide, sparse rows - Range scans by key prefix - Single-row atomicity sufficient - Horizontal scaling required

Trade-offs

AspectAdvantageDisadvantage
Single-Row Transactions OnlyEnables horizontal scaling without distributed coordination; simple programming model for most casesApplications requiring multi-row atomicity must implement it themselves or use a different database
LSM-Tree StorageExcellent write throughput; sequential I/O patterns; compression-friendlyRead amplification (check multiple SSTables); write amplification from compaction; space amplification
Sparse Column ModelSchema flexibility; efficient storage of sparse data; dynamic columns without DDLNo schema enforcement; application must handle missing columns; harder to reason about data model
Row Key Determines DistributionClient controls data locality and access patterns; predictable performance with good key designPoor key design causes hot spots; changing access patterns may require key redesign
Built on GFS + ChubbyLeverages battle-tested infrastructure; separation of concerns; fault tolerance built inRequires running complex distributed systems (or using managed service); operational overhead