Papers
Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber · USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2006, 2006
The problem: structured data at petabyte scale for very different workloads
Inside Google, products such as web indexing, Google Earth and Google Finance needed to store structured data at petabyte scale, spread across thousands of commodity servers. The demands were very heterogeneous: item sizes ranged from URLs to satellite images, and the required latency ranged from throughput-oriented batch processing to real-time serving of end users. The authors report that more than sixty Google products and projects already used Bigtable. The central design decision was not to offer a full relational model. Instead, the system exposes a simple model in which rows and columns are arbitrary strings and values are uninterpreted bytes; users decide how to serialize structured data inside those strings. This simplicity gives the client dynamic control over the data format and over locality, that is, over which data is stored physically close together. Schema parameters also let you choose whether a dataset is served from memory or from disk. The paper admits that Bigtable resembles a database in several implementation strategies, but purposely has a different interface, trading expressiveness for scale and performance.
The data model: a sorted, sparse, multidimensional map
Bigtable defines a table as a sorted, sparse, distributed and persistent map, indexed by row key, column key and timestamp; each value is an uninterpreted array of bytes. Row keys are arbitrary strings and the data is kept in lexicographic order by that key. Every read or write under a single row key is atomic, no matter how many columns it involves, which makes it easier to reason about concurrent updates to the same row. The table's row range is dynamically partitioned into tablets, the unit of distribution and load balancing. Because neighboring rows are stored together, the client chooses keys that give good locality: in the paper's example, the URL's hostname is reversed, so that pages from the same domain are contiguous and certain per-host or per-domain analyses become more efficient. Columns are grouped into families, the basic unit of access control and of memory and disk accounting; the family must be created before use, and after that any qualifier can be used. Each cell can have several versions indexed by 64-bit timestamp, stored from most recent to oldest. Per family, the client can request automatic garbage collection of old versions, keeping only the last n or only those recent enough.
Architecture: tablets, master, Chubby, and the location hierarchy
Bigtable relies on other pieces of Google's infrastructure. GFS stores the log and the data files; the SSTable format stores the data as an immutable, sorted map from keys to values; Chubby, a highly available distributed lock service, ensures at most one active master, stores the starting point for locating the data, helps discover live tablet servers, and stores schema information. The implementation has a library linked into every client, one master, and many tablet servers. The master assigns tablets to servers, detects their arrival and departure, balances load, and handles schema changes. Each tablet server serves reads and writes for the tablets it has loaded and splits those that grow too large. Client data does not flow through the master, and most clients do not even depend on it to know where the data is, so it stays lightly loaded. To locate a tablet, the paper uses three levels, analogous to a B+ tree: a file in Chubby points to the root tablet, which points to tablets of a special table called METADATA, which in turn locate the user tablets. The client caches these locations; with an empty cache, the lookup costs three network round trips.
Writes, reads, and compactions: memtable, log, and immutable SSTables
A tablet's persistent state lives in GFS. Every valid write is first recorded in a commit log, with redo records, and then inserted into the memtable, a sorted in-memory buffer; older updates live in a sequence of SSTables. A read is executed over the merged view of the memtable and the SSTables, which is efficient because everything is sorted. To recover a tablet, the server reads its metadata, loads the SSTable indexes, and rebuilds the memtable by reapplying the updates from the log since the redo points. When the memtable reaches a threshold, it is frozen, a new one is created, and the old one is written as an SSTable in GFS: the minor compaction, which reduces memory usage and the amount of log to re-read after a failure. Since each one creates a new SSTable, merging compactions run in the background to limit that number. The major compaction rewrites all the SSTables into exactly one, with no deletion entries or deleted data, which frees resources and guarantees that deleted data actually disappears, something important for services with sensitive data. Because SSTables are immutable, the only mutable structure accessed by reads and writes is the memtable, which simplifies concurrency control.
Refinements and trade-offs: locality, compression, Bloom filters, and transactional scope
The paper describes refinements that made the system viable. Locality groups make it possible to group column families that are usually read together; each group generates its own SSTable per tablet, and a group can be declared in-memory. Compression is chosen by the client per group and applied per SSTable block, so that small portions can be read without decompressing the whole file, at the cost of some space. In an experiment with web pages, a two-pass scheme achieved a 10-to-1 reduction, well above the 3-to-1 or 4-to-1 typical of Gzip on HTML, because pages from the same host end up adjacent. Tablet servers use two levels of cache (Scan Cache and Block Cache), and optional Bloom filters avoid disk accesses for rows and columns that do not exist. Each server uses a single commit log for all its tablets, rather than one per tablet, to avoid many simultaneous files and preserve group commit; the cost is a more complex recovery, solved by sorting the log by tablet. In terms of guarantees, Bigtable offers atomic read-modify-write transactions within a single row, but not general transactions across different rows.
Measured scale, real usage, and legacy
In the evaluation, the authors varied the number of tablet servers from 1 to 500 and measured reads and writes of 1000-byte values. Aggregate throughput grew by more than a hundredfold over that range, but not linearly: per-server throughput dropped considerably going from 1 to 50 servers, partly because of load imbalance and because rebalancing is limited so as not to move too many tablets. The worst scaling was for random reads, because each 1000-byte read brings a 64 KB SSTable block over the network, saturating the 1 Gbit links; for this reason many applications reduce the block size. In August 2006, the paper counted 388 non-test Bigtable clusters, with about 24,500 tablet servers in total. Usage examples include Google Analytics, with a raw click table of about 200 TB, and Google Earth, with a table of about 70 TB of images served from disk. As a legacy, the Apache HBase project describes itself as modeled after Google Bigtable. The pattern of memtable, log, immutable SSTables and compactions appears in other storage systems, and the choice of row key remains the modeling decision that defines locality and load distribution.
See the ideas at work
Practice the designs that use this paper in the System Design school.