Google Bigtable: Distributed Structured Datastore (Part 1)

A look into Bigtable.

Last week I did a deep dive into Amazon’s DyanmoDB, a distributed key-value store. This series of posts will cover Bigtable.

Bigtable is Google’s take on the distributed datastore space. Google designed Bigtable in line with internal demands for services such as Google Search, Google Earth etc. These services had diverse workloads requirements, from batch processing in cases like web crawling to the latency-sensitive data serving in some services. In such workloads, it is often required to store models of data but not the full-blown expressivity of a relational model. Essentially, Bigtable enables users to store flat data, i.e. data with multiple columns but no relations between different models. Hence data is stored as indexed by rows, columns and timestamps. Such a model makes Bigtable into a distributed, persistent multidimensional map.

Let’s look at the Data Model first to understand what we can do with Bigtable:

Data Model

Each row key is an arbitrary string with a fixed max size (64KB). The keys are used to sort data in a lexicographic order, which is partitioned dynamically. The unit of such partitioning is a tablet consisting of a key range. Each read or write operation against a row is guaranteed to be atomic.

Column keys are also arbitrary strings but are grouped differently. Columns keys are grouped into sets of families. This unit of data is compressed together and typically contains similar data types. A column inside a family is determined as family:quantifier. Families of columns are access controlled, and both disk and memory accounting is done against families.

This peculiar grouping of data is intended to satisfy the internal requirements that we mentioned. In some cases, applications modify the base data; others will derive families of columns from this data. Additionally, sensitive services must hide some data from other services, which Bigtable can control across families.

The last piece of our data model are timestamps, associated with row data. These are 64-bit integers that Bigtable or the client can set. These timestamps make versioned data management possible and support housekeeping tasks such as removing unwanted versions, past versions post a deadline etc.

This data model is what makes Bigtable a structured data store. For example, it is possible to store a representation of a web page as follows.

The table is defined with a unique row string, and column family contents and anchor. If you are used to seeing relational models, you can see how the data has been flattened.

Operations

Much like DynamoDB, Bigtable only supports single-row operations but additionally allows for atomic read-write-update operations on single rows. Table definition modifications are also present, such as updating column families, iterating over rows, and column families covering typical use cases. There is support for executing client-side scripts that can transform data, summarize tables etc.

Now that we have seen what it is capable of and its data model, we can look at the underlying blocks.

Bigtable uses some internal services as its subsystems:

• Google File System: A distributed service that stores and retrieves data on commodity hardware. Bigtable uses this system to store the data files and log files.
• Chubby: A Paxos-based, highly available, distributed service that provides the locking functionality. This enables the atomic operations guaranteed by Bigtable.
• Cluster manager: An internal cluster manager (I suspect Borg) responsible for scheduling jobs, managing resources and monitoring failures.

File Format

SSTable (Sorted String Table) file format was developed by Google, which stores the data in Bigtable. This is required to provide an immutable map from keys to values. The format contains a sequence of data blocks, typically 64KB. The index of each block is stored at the end of the file, which is loaded when the file is opened.

(In our discussion of DynamoDB there was no mention of file formats as DynamoDB essentially assumes that data is opaque. In line with structural datastores though, a discussion of file formats and how they allow Bigtable to achieve its guarantees critical to understand.)

Why use SSTables you ask?

The primary idea of SSTables is the sorted property of indexes. Given that indexes are sorted we can load the index at the end of the file, binary search the index and quickly resolve the data block required. This makes it that data is only one seek away. Note that such a file is not optimized for writes/inserts as that will require a full rewrite (also the reason why we called it immutable).

The idea is not to write to disk, rather we only write in memory as that is faster. After a threshold is crossed, the memory will have to flush its data to an SSTable, but as it is sorted already, we can achieve quick writes. Periodically we will be required to merge different files into one.

I will cover how these blocks are put together, forming the Bigtable service in the next part; stay tuned.