Google Bigtable

01 · CONTEXT

A sorted map for structured data at scale

Bigtable is a distributed storage system for structured data, designed to scale to petabytes of data across thousands of commodity servers. Many Google projects store data in it, including web indexing, Google Earth, and Google Finance, and the paper cites more than sixty products and projects.

These applications have very different demands: they vary in data size, from URLs to web pages and satellite imagery, and in latency, from backend batch processing to real-time data serving. Even so, the paper presents Bigtable as a flexible, high-performance solution for all of these products.

Bigtable does not offer a full relational data model model. A Bigtable is a sparse, distributed, persistent, multidimensional, sorted map, indexed by row key, column key, and timestamp, and each value is an uninterpreted array of bytes.

Because data is sorted by row key, the client can choose keys to get good locality of access. In Webtable, the paper's example, pages from the same domain land in contiguous rows because the host name components of the URLs are reversed.

Each cell can hold multiple versions of the same data, and the client can ask, per column family, to keep only the last n versions or only versions recent enough. Bigtable supports single-row transactions, but not general transactions across row keys.

02 · ARCHITECTURE

Master, tablet servers, GFS, and Chubby

The implementation has three main components: a library linked into every client, one master server, and many tablet servers. The master assigns tablets to servers, detects the arrival and expiration of servers, balances load, and garbage-collects files in GFS. The tablet server serves reads and writes for the tablets it has loaded and splits those that have grown too large.

Client data does not pass through the master: clients talk directly to tablet servers to read and write. Because clients do not rely on the master for tablet location information, most never communicate with it.

Each table starts with a single tablet and is automatically split into several as it grows, each about one hundred to two hundred megabytes by default. Each tablet server typically manages between ten and a thousand tablets, and each tablet is assigned to one server at a time.

A tablet's persistent state lives in GFS, which stores the log and data files. Data is written in the SSTable format, a persistent, sorted, immutable map from keys to values. Chubby, the distributed lock service, uses the Paxos algorithm to keep its replicas consistent, and Bigtable uses it, among other tasks, to ensure at most one active master and to discover tablet servers.

1. The client reads and writes directly on the tablet server that serves the row range, without going through the master.

2. The master assigns tablets to servers and tracks which servers are alive and which tablets are unassigned.

3. On startup, the tablet server creates and locks a file in Chubby; the master monitors the servers directory to discover them.

4. Each tablet's persistent state lives in GFS.

5. If a tablet server loses its exclusive lock, it stops serving its tablets; the master, upon acquiring the lock, deletes the server's file and can move its tablets to the set of unassigned ones.

6. If Chubby becomes unavailable for an extended period, Bigtable becomes unavailable.

The paper measured this effect across 14 Bigtable clusters over 11 Chubby instances. The average percentage of server hours during which some data was unavailable due to Chubby unavailability was 0.0047%, and in the most affected cluster it was 0.0326%.

03 · LOCATION

How the client finds the right tablet

Tablet locations are stored in a three-level hierarchy, analogous to a B+ tree. The first level is a file in Chubby containing the location of the root tablet; the root tablet contains the locations of all tablets of the special METADATA table; each METADATA tablet contains the location of a set of user tablets.

The root tablet is just the first tablet of METADATA, but it is treated specially to ensure that the location hierarchy never exceeds three levels.

1. The client library caches tablet locations.

2. With an empty cache, the client starts from the file in Chubby, which points to the root tablet.

3. The root tablet contains the locations of the METADATA table's tablets.

4. The METADATA tablet contains the location of the user tablet, and the client reaches the server that serves it.

5. With a stale cache, the error is only discovered when the query fails; the client then moves up the hierarchy, which can cost up to six network round trips.

6. To reduce this cost in the common case, the library does prefetching: when reading METADATA, it reads the metadata of more than one tablet.

With an empty cache, the location algorithm requires three network round trips, including one read in Chubby. Because locations are held in memory, no GFS accesses are needed.

04 · STORAGE

Log, memtable, SSTables, and compactions

A tablet's updates are committed to a commit log with redo records. The most recently committed ones are kept in memory in a sorted buffer called a memtable, and the older ones are kept in a sequence of SSTables.

1. When a write arrives, the tablet server checks that it is well formed and that the sender is authorized.

2. A valid mutation is written to the commit log; group commit improves the throughput of many small mutations.

3. Once committed, the write is inserted into the memtable.

4. A valid read is executed over a merged view of the memtable and the sequence of SSTables, which can be formed efficiently because both are sorted.

5. When the memtable reaches a threshold, it is frozen, a new one is created, and the frozen one becomes an SSTable written to GFS.

6. To recover a tablet, its metadata is read and the memtable is reconstructed by applying the committed updates since the redo points in the log.

When the memtable reaches a threshold, a minor compaction converts it into an SSTable. The paper points to two goals: reducing the tablet server's memory usage and reducing the amount that must be read from the commit log during recovery if the server dies. Reads and writes continue during compactions.

SSTables from compactions other than major ones can contain deletion entries that suppress deleted data in older SSTables that are still live; a major compaction, by contrast, produces an SSTable with no deletion information or deleted data.

Because the generated SSTables are immutable, there is no need to synchronize file system accesses when reading them, and the only mutable structure accessed by reads and writes is the memtable. Immutability also allows tablets to be split quickly: the child tablets share the parent tablet's SSTables.

The paper compares this design to the Log-Structured Merge Tree: in both systems, sorted data is buffered in memory before going to disk, and reads must merge data from memory and disk.

05 · REFINEMENTS

Locality, caches, single log, and performance

Column families can be grouped into locality groups, and each group generates a separate SSTable in each tablet. Separating families that are not normally accessed together makes reads more efficient: in Webtable, page metadata and contents can sit in different groups. A group can also be declared in-memory, which the paper uses internally for the METADATA location family.

Tablet servers use a two-level cache: the Scan Cache, the higher level, holds the key-value pairs returned by the SSTable interface; the Block Cache, the lower level, holds SSTable blocks read from GFS. A Bloom filter lets you ask whether an SSTable may contain data for a row/column pair, and with it most queries for nonexistent rows or columns do not need to touch the disk.

The tablet server appends the mutations of all its tablets to a single commit log. This brings significant performance gains in normal operation, but complicates recovery: when a server dies, its tablets move to many other servers, and one approach would be for each new server to read the whole log and apply only the entries it needs. Bigtable avoids these duplicate reads by first sorting the log entries by key, so that a tablet's mutations are contiguous.

In an experiment with Webtable, the two-pass compression scheme reduced space by 10 to 1, against typical reductions of 3 to 1 or 4 to 1 for Gzip on HTML. The paper attributes the difference to the row layout, in which pages from the same host sit close together.

In the benchmarks, with 1000-byte values, random reads are slower than all other operations by an order of magnitude or more. Each one transfers a 64 KB SSTable block from GFS to the tablet server, and only a 1000-byte value is used; most applications with this pattern reduce the block size, typically to 8 KB.

Aggregate throughput grows by more than a factor of a hundred when tablet servers go from 1 to 500, but performance does not scale linearly. The paper attributes the drop in per-server throughput to load imbalance, often due to other processes competing for CPU and network.

06 · USAGE AND LESSONS

What production taught

As of August 2006, the paper counts 388 non-test Bigtable clusters, with about 24,500 tablet servers in total. Many of these clusters are used for development and sit idle for significant periods.

Two examples show row key design. In Google Analytics, the raw-click table keeps one row for each end-user session, and the row name is a tuple of the site name and the session creation time, which keeps sessions of the same site contiguous and in chronological order. In Personalized Search, each user has a unique userid and gets a row named by it, with a separate column family for each type of action.

Personalized Search data is replicated across several Bigtable clusters to increase availability and reduce latency caused by distance from clients. The team originally built a client-side replication mechanism that guaranteed eventual consistency among the replicas; the current system uses a replication subsystem built into the servers.

Among the paper's lessons is that large distributed systems are vulnerable to many kinds of failure, not only the network partitions and fail-stop failures assumed by many protocols. Among the causes observed are memory and network corruption, large clock skew, hung machines, extended and asymmetric network partitions, and bugs in other systems used, such as Chubby. One of the responses was to add checksums to the RPC mechanism.

Another lesson was about transactions. The team planned general-purpose transactions in the API but, with no immediate use, did not implement them; it later found that most applications need only single-row transactions. Where there was a request for distributed transactions, the most important use was maintaining secondary indexes, and the paper plans a specialized mechanism for that.

The paper calls the most important lesson the value of simple designs. The first tablet server membership protocol was simple: the master periodically issued leases and the servers killed themselves if the lease expired; but it significantly reduced availability in the presence of network problems. The protocol that resulted from the redesigns was too complex, and the team discarded it for a simpler one that depends only on widely used Chubby features.