Bigtable Compaction: Minor vs. Major

The Write Path and the Accumulation of SSTables

Every write operation in Bigtable targets a tablet server. The server appends the mutation to a commit log stored in GFS/Colossus to ensure durability and then applies the change to the memtable. This memtable is a sorted data structure in memory, allowing recent writes to be served quickly.

When the memtable reaches a configured size threshold, a process called minor compaction is triggered. The tablet server freezes the current memtable, creates a new one to accept incoming writes, and writes the contents of the frozen memtable to a new SSTable file in GFS.

This leads to a situation where a single tablet consists of:

• The current, mutable memtable in memory.
• One or more immutable SSTables on GFS, with the most recent SSTable containing the newest flushed data.

To satisfy a read request, Bigtable must query the memtable and all the SSTables for that tablet, merging the results to find the correct version of the data for a given key. As the number of SSTables grows, this "read amplification" makes reads progressively slower. Furthermore, since SSTables are immutable, updated or deleted data is not removed from older files; it is simply superseded by a newer value or a deletion marker (a "tombstone") in a more recent SSTable. This "space amplification" wastes disk space.

Compactions are the solution to both of these problems.

Minor Compaction: Checkpointing Memory to Disk

Let's begin with the formal definition and goals of minor compaction, as described in the original Bigtable paper.

As you've just read, a minor compaction is the process of writing the in-memory memtable to a new SSTable on disk. Its two primary purposes are:

1. To reduce the memory footprint of the tablet server. By flushing the memtable to disk, the server frees up memory to buffer new writes.
2. To reduce recovery time. The commit log only needs to be replayed for writes that are not yet persisted in an SSTable. By creating a new SSTable, the minor compaction acts as a checkpoint, significantly shortening the list of log entries that must be replayed if the tablet server fails and another one has to take over its tablet.

The Bigtable paper also notes a clever use case for this process in Section 6, "Refinements." When the master needs to move a tablet from one server to another, it instructs the source server to perform a minor compaction first. This minimizes the state that exists only in the commit log, allowing the new server to load the tablet much faster without needing to replay many log entries.

Merging and Major Compactions: Taming the SSTable Stack

Minor compactions solve the memory and recovery-time problems, but they create the read-amplification and space-amplification problems by continuously creating new SSTables. To solve these, Bigtable employs further compactions that merge existing SSTables.

The paper describes two types of merging compactions:

• A merging compaction reads a few SSTables and the memtable and merges them into a new, single SSTable.
• A major compaction is a specific type of merging compaction that merges all SSTables for a tablet into a single, definitive SSTable.

A major compaction is a garbage collection and optimization process with three key outcomes:

1. Improves Read Performance: By consolidating all data into a single SSTable, a read operation only needs to check that one file (and the memtable), drastically reducing read amplification.
2. Reclaims Disk Space: It physically discards data that has been overwritten or deleted. During the merge, only the most recent value for each key is kept. If the most recent entry is a tombstone, both the tombstone and the old data are discarded, reclaiming space.
3. Ensures Timely Deletion: For systems handling sensitive data, this process guarantees that deleted data is permanently removed from storage in a predictable timeframe, as Bigtable periodically runs major compactions on all tablets.

To see this in action, the following video provides a clear, practical example of how values from two SSTables are merged into one.

The Underlying Data Structure: Log-Structured Merge-Trees

The combination of an in-memory table for recent writes and a set of immutable, sorted files on disk that are periodically merged is not unique to Bigtable. This is a well-known data structure pattern called a Log-Structured Merge-Tree (LSM-Tree).

Given your background, recognizing this pattern is key. LSM-Trees are at the heart of many modern NoSQL databases like Apache Cassandra, RocksDB, and LevelDB (the latter two being open-source projects heavily inspired by Bigtable's design). They are designed to optimize for high write throughput by converting random write I/O into sequential I/O (appending to a log and flushing sorted files). The cost of this optimization is increased read complexity and space usage, which is then mitigated by the compaction process we've just discussed.

The following video from ByteByteGo provides an excellent, concise overview of the LSM-Tree concept from first principles.

As the video mentions, there are different strategies for compaction. The Bigtable paper describes a simpler form, often called "size-tiered compaction." Modern systems frequently use a more sophisticated approach called "leveled compaction," where SSTables are organized into levels of exponentially increasing size. Compaction then involves merging a file from Level N with overlapping files in Level N+1. This strategy provides more predictable performance bounds for reads and space usage.

Conclusion

In this lesson, we have explored the critical role of compactions in Bigtable's storage engine. You have learned how Bigtable balances high write throughput with the need to maintain read performance and manage disk space efficiently.

Here are the key takeaways:

• Minor Compaction is the process of flushing the in-memory memtable to a new SSTable on disk. Its primary goals are to free up memory and create a recovery checkpoint.
• Major Compaction merges all existing SSTables for a tablet into a single new SSTable. This is a garbage collection process that improves read performance, reclaims disk space from old or deleted data, and ensures sensitive data is permanently removed.
• This entire mechanism is an implementation of the Log-Structured Merge-Tree (LSM-Tree), a data structure that prioritizes high write throughput by transforming random writes into sequential ones, with compactions handling the resulting read and space amplification.

We have now covered Bigtable's data model and its core architectural components, including the specifics of its storage layer. Bigtable represents a landmark in scalable NoSQL design. Next, we will shift our focus to another titan of Google's infrastructure: Spanner. In the upcoming lesson, we will begin to analyze Spanner's high-level architecture, a system that takes on the even more ambitious goal of providing global-scale, externally consistent, relational database semantics.