Bigtable: A Distributed Storage System for Structured Data
📜 Abstract
Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size: petabytes of data across thousands of commodity servers. Many projects at Google store data in Bigtable, including web indexing, Google Earth, and Google Finance. These applications place very different demands on Bigtable, both in terms of data size (from URLs to web pages to satellite imagery) and latency requirements (from backend bulk processing to real-time data serving). Despite these varied demands, Bigtable has successfully provided a flexible, high-performance solution for all of these Google products. In this paper we describe the simple data model provided by Bigtable, which gives clients dynamic control over data layout and format, and we describe the design and implementation of Bigtable.
✨ Summary
Summary
Bigtable presents a distributed storage system for large-scale structured and semi-structured data. Its data model is a sparse, persistent, multidimensional sorted map indexed by row key, column key, and timestamp. Rows are maintained in lexicographic order and are atomically readable and writable, while column families provide a manageable unit for access control, compression, memory placement, and schema organization. Versioned cells and configurable garbage collection allow applications to retain either a fixed number of versions or values within a specified time interval.
The system partitions tables into tablets, each covering a contiguous range of rows. Tablets are dynamically split, assigned to tablet servers, and rebalanced by a master. Clients communicate directly with tablet servers for data operations, avoiding the master as a request bottleneck. Tablet locations are maintained through a three-level metadata hierarchy, with client-side caching and prefetching reducing lookup overhead.
Persistent tablet state is stored in Google File System using immutable SSTables, a commit log, and an in-memory memtable. Writes are logged and later incorporated into SSTables through minor, merging, and major compactions. Reads merge the memtable with the relevant SSTables. Immutable files simplify concurrency, tablet splitting, deletion cleanup, and recovery. Additional optimizations include locality groups, in-memory data placement, block and scan caches, Bloom filters, grouped commit logging, log sorting during recovery, and staged compaction before tablet migration.
The evaluation shows that Bigtable scales substantially as tablet servers are added, although scaling is limited by shared network capacity, CPU contention, load imbalance, and the cost of transferring large storage blocks for small random reads. Sequential access, scans, writes, and memory-resident reads perform considerably better than disk-based random reads. Production examples demonstrate the model’s applicability to web crawling, analytics, satellite imagery, personalized search, batch processing, and latency-sensitive serving workloads.
The authors emphasize operational lessons: distributed systems must account for corruption, clock skew, hung machines, asymmetric partitions, dependency failures, quota exhaustion, and maintenance events; monitoring must cover both infrastructure and client behavior; and simple, clear protocols are preferable to unnecessarily general mechanisms. The paper deliberately favors single-row atomicity and schema-level control over a full relational model or general distributed transactions.
Influence
The paper became a foundational reference for wide-column and large-scale NoSQL storage. Apache HBase describes itself as an open-source distributed database modeled after Google Bigtable and implements Bigtable-like capabilities on Hadoop and HDFS. (hbase.apache.org) Google also identifies Bigtable as an inspiration for HBase and Cassandra. (cloud.google.com)
The design subsequently became available as Google Cloud Bigtable, a managed service that exposes Bigtable-style storage through client libraries and an HBase-compatible interface, connecting the original research design to cloud production workloads and the broader Hadoop ecosystem. (docs.cloud.google.com) The paper was presented at OSDI ‘06 on November 7, 2006, and was recognized as a Best Paper. (usenix.org)