Bigtable: A Sparse, Distributed, Multi-Dimensional Sorted Map

The Bigtable Data Model: A Deconstructed View

At its core, Bigtable presents a simple concept that you are very familiar with: it's a giant map. However, the true innovation lies in the specific characteristics of this map. The authors of the original Bigtable paper define it with a very precise phrase: "a sparse, distributed, persistent, multi-dimensional sorted map." Let's break this down, piece by piece, to understand the design implications.

• Map: The fundamental structure is a key-value store. However, the "key" is more complex than a simple string.
• Sorted: Unlike many key-value stores that use hash-based partitioning, Bigtable's data is maintained in lexicographical order based on its row key. This is a critical design choice that makes range scans highly efficient.
• Multi-dimensional: The key isn't just one value. To locate a specific piece of data, you need a three-part tuple: (row key, column key, timestamp). This structure gives the map its depth.
• Sparse: Think of a vast spreadsheet where most cells are empty. Rows are not required to have values for all columns. A given row can have a few columns, while another can have thousands, even if they don't share any columns in common (besides being in the same column families). This provides immense schema flexibility compared to a traditional relational database.
• Distributed & Persistent: The map is partitioned into manageable chunks (called tablets) and distributed across many machines, with its underlying data durably stored in a distributed file system like GFS or Colossus.

Let's now examine the dimensions of this map in more detail.

Dimension 1: The Row Key (The "Sorted" Aspect)

The row key is the primary index for all data in a Bigtable. Every read or write operation within a single row is atomic, providing a simple and powerful consistency guarantee for clients.

The most important property of the row key is that Bigtable keeps data sorted by it. This has profound implications for schema design. By carefully crafting your row keys, you can ensure that related data is stored physically close together. This enables highly efficient range scans, where you read a contiguous block of rows with a single query.

A classic example from the original paper is the Webtable, used for storing data about web pages. To group all pages from a single domain together, the row keys were constructed by reversing the domain's hostname. For instance, data for maps.google.com/index.html would be stored under the row key com.google.maps/index.html. A query for all pages under com.google would then become a simple and efficient scan over a contiguous range of keys.

Dimension 2: The Column Key (The "Sparse" Aspect)

The second dimension is the column key. Bigtable's schema is "sparse" because columns are not predefined for a table. Instead, columns are grouped into column families, which act as the basic unit for access control and physical storage configuration.

A column key is formed by combining a family and a qualifier, using the syntax family:qualifier.

• Column Families: These must be created when the table is defined. The number of column families in a table is expected to be small and relatively static (e.g., in the dozens or hundreds). Data within the same column family is typically of the same type and is compressed together.
• Column Qualifiers: Within a family, you can have a virtually unbounded number of qualifiers. These can be created dynamically by the application at runtime.

Returning to the Webtable example, one column family might be anchor. For a row representing cnn.com, there could be many columns in this family, such as anchor:cnnsi.com (with the value "CNN on SI") and anchor:my.look.ca (with the value "CNN News"), each representing a site that links to CNN. This allows the schema to adapt as new inbound links are discovered, without any central schema modification.

Dimension 3: The Timestamp (The "Multi-dimensional" Aspect)

The final dimension is time. Each cell in Bigtable, identified by a (row key, column key) pair, can contain multiple versions of a value. These versions are indexed by a 64-bit integer timestamp.

When you read a cell, by default you get the most recent version. However, you can also request the value at a specific timestamp or retrieve multiple versions. The versions are stored in decreasing order of timestamp, making reads of the latest data fast.

This feature provides built-in data versioning. Bigtable also allows you to configure automatic garbage collection policies on a per-column-family basis. For example, you can instruct Bigtable to only keep the most recent n versions of a cell, or to only keep versions written within the last seven days.

Putting It All Together

The combination of these three dimensions—row key, column key, and timestamp—creates the multi-dimensional map. A specific value is uniquely identified by the full coordinate (row, column, time).

The following diagram provides an excellent visual summary of this structure.

To solidify your understanding of these concepts directly from the source, it's time to read the relevant section of the original Bigtable paper.

To hear these concepts explained in a more conversational style, the following video provides a great overview.

Conclusion

In this lesson, we have dissected the definition of Bigtable's data model: a sparse, distributed, multi-dimensional sorted map. This is not just an academic definition; every term has significant practical implications for system design and performance.

Here are the key takeaways:

• The Three-Dimensional Key: Data is indexed by a (row, column, timestamp) tuple. Understanding this is fundamental to using Bigtable effectively.
• Sorted by Row Key: This design choice makes Bigtable exceptionally good at range scans, but it places the burden on you, the designer, to create row keys that co-locate related data.
• Schema Flexibility via Sparsity: Column families provide a loose structure, while column qualifiers allow rows to be wide and sparse, giving applications the freedom to evolve their data formats without rigid schema migrations.
• Built-in Versioning: The timestamp dimension provides a powerful, out-of-the-box mechanism for tracking data history and implementing time-based data retention policies.

We have now established a clear understanding of Bigtable's logical data model—the "what." In our next lesson, we will investigate the "how" by analyzing Bigtable's storage architecture, exploring how it leverages GFS/Colossus and Chubby to implement this model at massive scale.