The sparse, distributed, persistent multi-dimensional sorted map that powers Google Search, Maps, YouTube, and Gmail
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.
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.
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.
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.
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.
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.
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.
By 2006, Google needed to store and query structured data across dozens of services:
Each project faced similar challenges but had different data patterns.
Why not use a relational database?
Why not use raw files (GFS)?
Bigtable sits between these extremes: more structure than files, more flexibility than RDBMS.
Bigtable is a sparse, distributed, persistent multi-dimensional sorted map:
(row:string, column:string, timestamp:int64) → stringThat'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 is the most important decision when using Bigtable. The key determines:
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)
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
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:
Caching is critical:
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
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:
Read path:
SSTable format:
Why LSM-tree?
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.
When a tablet server starts serving a tablet, it must recover its state from GFS:
Tablet load steps:
What happens on tablet server failure?
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
Bigtable includes several refinements to improve performance and reduce costs:
Compression:
Caching (two levels):
Bloom filters:
Commit log optimization:
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:
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
Bigtable powers some of Google's most critical and largest services:
Google Analytics:
Google Earth:
Personalization:
Web Crawl (Webtable):
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 didn't just solve Google's storage problems—it sparked the NoSQL movement and influenced a generation of databases:
Direct descendants:
Inspired systems:
Lessons for system design:
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
| Aspect | Advantage | Disadvantage |
|---|---|---|
| Single-Row Transactions Only | Enables horizontal scaling without distributed coordination; simple programming model for most cases | Applications requiring multi-row atomicity must implement it themselves or use a different database |
| LSM-Tree Storage | Excellent write throughput; sequential I/O patterns; compression-friendly | Read amplification (check multiple SSTables); write amplification from compaction; space amplification |
| Sparse Column Model | Schema flexibility; efficient storage of sparse data; dynamic columns without DDL | No schema enforcement; application must handle missing columns; harder to reason about data model |
| Row Key Determines Distribution | Client controls data locality and access patterns; predictable performance with good key design | Poor key design causes hot spots; changing access patterns may require key redesign |
| Built on GFS + Chubby | Leverages battle-tested infrastructure; separation of concerns; fault tolerance built in | Requires running complex distributed systems (or using managed service); operational overhead |