Hello! Welcome back.
In our last lesson, we explored how LSM-Trees handle insertions and deletions, introducing the concept of compaction as the background process responsible for cleaning up old data and tombstones. You learned that this process is essential for reclaiming disk space and maintaining read performance.
Today, we'll focus entirely on this crucial process. The learning outcome for this lesson is to describe and compare tiered versus leveled compaction strategies. You'll discover that there isn't just one way to perform compaction; different strategies offer distinct trade-offs. Understanding these is fundamental to designing and tuning high-performance, write-optimized storage systems. We will explore how these strategies impact three key metrics: write amplification, read amplification, and space amplification.
1. The Need for a Compaction Strategy
As a quick recap, compaction involves merging multiple on-disk SSTables to produce new ones. The goals are to:
- Remove duplicate or updated values, keeping only the most recent version of each key.
- Physically delete data corresponding to tombstones.
- Reduce the number of SSTables that must be checked during a read.
The question is, which SSTables should be merged, and when? The answer to this is the compaction strategy. Let's dive into the two most prevalent approaches.
2. Tiered Compaction
Tiered compaction, also known as size-tiered compaction, is one of the most straightforward strategies. The core idea is to group SSTables of similar sizes into "tiers" (or levels) and, once a tier accumulates enough SSTables, merge them all into a single, new SSTable in the next, larger tier.
This video from the developers at DataStax provides an excellent, practical explanation of how size-tiered compaction works in Apache Cassandra, a popular database system that uses this approach.
DS210.16 Size-Tiered Compaction | Operations with Apache Cassandra
This video, 'Size-Tiered Compaction', explains the mechanics of the tiered strategy. It visualizes how SSTables are grouped and merged, and introduces some of the key trade-offs.
Watch the following segments: (00:00 - 02:22): Focus on the basic mechanism of merging a set of smaller SSTables (e.g., four 100MB files) into a single, larger one (a 400MB file). (04:14 - 06:00): Observe how SSTables of various sizes are organized into different 'buckets' or tiers, which are then compacted independently. This is the essence of the tiered approach.
As you saw, the process is conceptually simple: collect, merge, and promote. An important characteristic of tiered compaction is that a single tier can contain multiple, overlapping SSTables. When a read request comes in for a key, the system might have to check every single SSTable in a tier (and across all tiers) to find the most recent version of that key.
3. Leveled Compaction
Leveled compaction takes a more structured approach, primarily designed to optimize read performance. It enforces a strict invariant: within each level (except for Level 0), the SSTables are guaranteed to have non-overlapping key ranges.
This means that for any given key, its data can exist in at most one SSTable per level. This drastically reduces the number of files that need to be checked during a read operation.
To maintain this invariant, the compaction process is different:
- Level 0 is special; it acts as the landing zone for new SSTables flushed from the memtable and can have overlapping files (similar to a tier).
- When Level 0 fills up, its SSTables are merged with the SSTables in Level 1 that they overlap with.
- For any other level
L_ithat grows too large, the system selects one of its SSTables, finds all the SSTables in levelL_{i+1}that have an overlapping key range, and merges them all together. - The result of this merge is then split into new, non-overlapping SSTables that replace the old ones in
L_{i+1}.
Log Structured Storage - MyDistributed.Systems
The article 'Log Structured Storage' on MyDistributed.Systems gives a concise technical description of leveled compaction.
Read the section titled 'Leveled Compaction'. Pay close attention to the process described for compacting from level L_i to L_{i+1} and how it differs from the simpler merge-and-promote of tiered compaction.
The diagram you saw earlier also illustrates this. In the leveling strategy on the right, each level from L1 downwards consists of a single, large sorted run (conceptually, a set of non-overlapping SSTables). Compaction involves merging a run from an upper level into the run of the level below it.
4. Comparing the Strategies: The Amplification Trade-Off
The choice between tiered and leveled compaction is a classic engineering trade-off. We can analyze it through three "amplification" factors. This technical blog post offers a great conceptual overview before we dive into the specifics.
The blog post 'Tiering vs. Leveling' by Justin Jaffray provides a clear, high-level comparison of the two designs. It's a great example of the kind of analysis done by database engineers.
Read the post starting from the 'quick review of the basics of LSMs'. Focus on: The description of 'leveling' and its invariant of non-overlapping SSTs. The alternative design of 'tiering' where this invariant is dropped. The final discussion on trade-offs and the RocksDB hybrid approach.
Now, let's break down the comparison based on the three key metrics.
a) Write Amplification
Write amplification is the ratio of the total data written to disk versus the data written by the application. A high write amplification can wear out SSDs faster and consume I/O bandwidth.
- Tiered: Has low write amplification. In the ideal case, each piece of data is written to disk once when the memtable is flushed, and then re-written once per tier during compaction. Since data is only ever merged downwards into a new tier, existing data in lower tiers isn't re-read and re-written.
- Leveled: Has high write amplification. When compacting an SSTable from
L_itoL_{i+1}, you must read the overlapping SSTables inL_{i+1}and re-write them along with the new data. If levelL_{i+1}is 10 times larger thanL_i(a typical "fanout" factor), you might rewrite 10MB of data inL_{i+1}just to merge 1MB of data fromL_i.
b) Read Amplification
Read amplification refers to the number of disk pages or files that must be accessed to satisfy a single read query.
- Tiered: Has high read amplification. Since tiers can have many overlapping SSTables, a point read might have to check every SSTable (in the worst case) to find the key. Bloom filters significantly mitigate this for non-existent keys, but for existing keys, the potential for multiple checks remains.
- Leveled: Has low read amplification. Thanks to the non-overlapping invariant, a read needs to check at most one SSTable per level. This makes point lookups much more predictable and efficient.
c) Space Amplification
Space amplification is the ratio of the total disk space used by the database versus the actual size of the data.
- Tiered: Has high space amplification. Because compaction within a tier might happen infrequently, many old versions of data and tombstones can accumulate across multiple overlapping SSTables, consuming significant extra disk space.
- Leveled: Has low space amplification. The more aggressive compaction strategy of merging overlapping ranges ensures that old data is garbage-collected more quickly, keeping space usage closer to the actual data size.
This image shows a concrete example of how data flows through the levels in both strategies during an insertion, highlighting the structural differences that lead to these trade-offs.
Summary of Trade-offs
| Metric | Tiered Compaction | Leveled Compaction | Best for... |
|---|---|---|---|
| Write Amplification | Low | High | Write-heavy workloads, SSD longevity |
| Read Amplification | High | Low | Read-heavy workloads, predictable query latency |
| Space Amplification | High | Low | Storage-constrained environments |
Test your understanding!
You are designing a database system for a time-series monitoring application. The workload consists of a massive, constant stream of incoming data points (writes), but relatively infrequent queries that typically look up recent data. Which compaction strategy, tiered or leveled, would you choose as a starting point, and why? Justify your choice based on the amplification trade-offs.
Show answer
For a write-heavy, time-series workload, tiered compaction is the better choice.
Justification:
- Low Write Amplification: The primary characteristic of this workload is the massive volume of writes. Tiered compaction is optimized for this, as it minimizes the amount of data re-written during compaction. This reduces I/O load on the storage system and improves write throughput, which is critical for keeping up with the data stream. It also helps extend the life of the underlying SSD storage.
- Tolerable Read/Space Amplification: The queries are infrequent, so the higher read amplification of the tiered strategy is an acceptable trade-off. Similarly, time-series data often benefits from high-capacity, lower-cost storage, so the higher space amplification is usually manageable.
Choosing leveled compaction would be detrimental because its high write amplification would likely create a bottleneck, preventing the system from ingesting data at the required rate.
Conclusion
You now have a solid understanding of the two primary compaction strategies used in LSM-Trees. You can see that there is no single "best" strategy; the choice is a critical engineering decision that depends on the specific workload characteristics.
Key Takeaways:
- Tiered Compaction merges groups of similarly-sized SSTables. It excels at handling write-heavy workloads due to its low write amplification, but at the cost of high read and space amplification.
- Leveled Compaction maintains non-overlapping SSTables within each level to optimize reads. It provides low read and space amplification, making it ideal for read-heavy workloads, but this comes at the cost of high write amplification.
- The choice between them is a fundamental trade-off between write performance, read performance, and disk space usage.
- Practical systems like RocksDB sometimes use a hybrid approach, for example using tiered compaction for Level 0 and leveled for all subsequent levels, to get some of the benefits of both.
Preview of the Next Lesson
In this lesson, we described and qualitatively compared the amplification factors. In our next lesson, we will build on this by learning to analyze the write amplification, read amplification, and space amplification trade-offs in LSM-Trees. We will move towards a more quantitative understanding, exploring how factors like the number of levels and the size ratio between them influence the overall performance of an LSM-Tree.