LSM-Tree Amplification Trade-offs

Hello! Welcome to our next lesson on write-optimized storage.

In our previous lesson, we described and compared tiered and leveled compaction strategies, introducing the qualitative trade-offs of write, read, and space amplification. We saw that tiered compaction is good for writes, while leveled is better for reads and space usage.

Today, we'll deepen that understanding by moving from a qualitative description to a more formal and quantitative analysis. The learning outcome for this lesson is to analyze the write amplification, read amplification, and space amplification trade-offs in LSM-Trees. We'll precisely define these metrics, introduce a powerful mental model called the RUM conjecture to frame our thinking, and then explore how a key tuning parameter—the size ratio—numerically impacts these trade-offs.

1. Formalizing the "Amplifications"

To analyze trade-offs, we first need precise definitions. In database systems engineering, performance is often discussed in terms of "amplification" factors, which measure how much work the system does behind the scenes for a single application request.

How do LSM Trees work?

The blog post 'How do LSM Trees work?' provides clear and standard definitions for these key metrics. We'll use these as our foundation.

Read just the short section 'Formalizing our understanding of performance' to get the definitions for read, write, and space amplification.

Based on that reading, let's establish our working definitions:

Write Amplification: The ratio of the total bytes written to the storage device versus the bytes written by the application. If your application writes 1 KB but the database writes 10 KB to disk due to compaction, the write amplification is 10. This is critical for write-heavy workloads and for managing the lifespan of SSDs.
Read Amplification: The ratio of total bytes read from the storage device to satisfy a query versus the actual size of the data requested. If you need to read 100 KB from disk to find a 1 KB value, the read amplification is 100. This directly impacts query latency.
Space Amplification: The ratio of the total disk space used by the database to the actual "live" size of the user's data. If you have 1 GB of data but the database files occupy 3 GB on disk (due to old versions waiting for compaction), the space amplification is 3. This affects storage costs.

Let's visualize write amplification. As data is compacted from smaller, "higher" levels to larger, "lower" levels, it is re-read and re-written at each step.

LSM-Tree Write Amplification during Compaction — This diagram illustrates how a single update operation (the red line) is physically rewritten multiple times as it migrates through the LSM-Tree during compaction. It is first written to a small SSTable, then merged into a 0.4 GB SSTable, then a 1.6 GB SSTable, and finally a 6.4 GB SSTable. Each merge involves rewriting the data, thus amplifying the initial write.

2. The RUM Conjecture: A Framework for Trade-offs

The tension between these amplification factors is not unique to LSM-trees; it's a fundamental challenge in data systems design. The RUM Conjecture provides an excellent framework for understanding these inescapable trade-offs.

Understanding Database Trade-offs - The RUM Conjecture - Paper Explained

The video 'Understanding Database Trade-offs - The RUM Conjecture' by Arpit Bhayani offers a fantastic and accessible explanation of this core concept.

Watch the following segments: (00:00 - 02:11): Pay close attention to the main idea: you can optimize for at most two of Reads, Updates (writes), and Memory (space), but the third will be negatively impacted. (02:11 - 04:46): Listen to the examples for read-optimized (B-Trees) and write-optimized (LSM-Trees) systems to see the conjecture in action. (06:54 - 07:51): This final part summarizes how to use the RUM conjecture as a mental model for analyzing any database system.

As the video explains, the RUM conjecture posits a three-way trade-off:

Read performance
Update (write) performance
Memory/storage overhead

When you design a data structure, you can pick two to optimize, but you will have to make a compromise on the third.

A classic B+Tree is optimized for Reads (logarithmic lookup) and Memory/Space (in-place updates keep space amplification low), but it sacrifices Update performance (high write amplification from random I/O and page splits).
An LSM-Tree, by contrast, is optimized for Updates (writes are fast appends to an in-memory table), but it compromises on Reads (potential to check many files) and/or Memory (space amplification from old data versions, or memory for Bloom filters and indexes).

This framework formalizes the intuition that there's "no free lunch" in database design. Now, let's see how this plays out quantitatively within the LSM-tree design space itself.

3. Quantitative Analysis of the Amplification Trade-offs

The choice between tiered and leveled compaction is really a choice of where to sit on the RUM spectrum. The key tuning parameter that governs this is the size ratio.

The Size Ratio (R)

The size ratio (often denoted R, or sometimes T or fanout) is the factor by which each level in the LSM-tree grows. For example, if R=10, Level 1 is 10 times larger than Level 0, Level 2 is 10 times larger than Level 1, and so on.

The size ratio is the main knob you turn to navigate the read-write trade-off. This next video is quite advanced, but it contains an exceptionally clear analysis of how the size ratio impacts performance.

Scaling Write-Intensive Key-Value Stores

The talk 'Scaling Write-Intensive Key-Value Stores' from Microsoft Research provides a detailed, quantitative breakdown of LSM-Tree costs. We will focus on the segments that analyze the fundamental performance trade-offs.

This is a dense, academic talk, so focus carefully on these specific parts: (05:55 - 09:01): This section explains how the size ratio (R) controls the fundamental read-write trade-off and defines the core difference between tiered and leveled designs. The key takeaway is that R determines how many runs can exist per level in a tiered design, and how aggressively a leveled design must merge. (00:23:45 - 00:27:10): This is the most important part. The speaker breaks down the I/O cost for writes and reads. Focus on the logic used to derive the write amplification bound of R * log(N) for leveled compaction. This analysis is the core of this lesson.

Let's use the logic from that video to build a quantitative model for our amplification factors. Assume a total of N items in the database and a size ratio of R. The number of levels will be approximately log_R(N).

Write Amplification Analysis

Leveled Compaction:
- To merge data from level L_i into L_{i+1}, we must read all overlapping data in L_{i+1} and rewrite it.
- Since L_{i+1} is R times larger than L_i, for every 1 byte of data we move from L_i, we rewrite about R bytes of data in L_{i+1}.
- This happens at each of the log_R(N) levels.
- Therefore, the worst-case write amplification is O(R * log_R(N)). This is why leveled compaction is considered expensive for writes.
Tiered Compaction:
- Here, we merge a group of R runs from Tier_i into a single new run in Tier_{i+1}. We don't touch the existing data in Tier_{i+1}.
- Each piece of data is rewritten once as it moves from one tier to the next.
- With log_R(N) tiers, the worst-case write amplification is O(log_R(N)). This is significantly better than leveled compaction.

Read Amplification Analysis (for point reads)

Leveled Compaction:
- Because SSTables within a level (L1+) do not have overlapping key ranges, we only need to check at most one file per level.
- With log_R(N) levels, the worst-case read amplification is O(log_R(N)). This is very efficient and predictable.
Tiered Compaction:
- A tier can have up to R SSTables, all with potentially overlapping key ranges.
- In the worst case, a point read has to check all R files in each of the log_R(N) tiers.
- Therefore, the worst-case read amplification is O(R * log_R(N)). This is much higher than leveled and highlights why Bloom filters are essential for making tiered designs practical.

Space Amplification Analysis

Leveled Compaction:
- Compaction is aggressive and continuously reclaims space from obsolete records. The amount of "stale" data is relatively small, usually a fraction of the total database size.
- The worst-case space amplification is low, typically around O(1) (e.g., 10-20% overhead).
Tiered Compaction:
- A tier only compacts when it has accumulated R runs. This means you can have up to R-1 runs containing old, stale data.
- In the worst case, this means the database size can be almost R times the live data size.
- The worst-case space amplification is O(R).

Summary Table of Trade-offs

This table summarizes our quantitative analysis.

Metric	Leveled Compaction	Tiered Compaction	Advantage
Write Amplification	`O(R * log N)`	`O(log N)`	Tiered
Read Amplification	`O(log N)`	`O(R * log N)`	Leveled
Space Amplification	`O(1)`	`O(R)`	Leveled

Note: The base of the logarithm is R, but this is omitted in Big-O notation.

Test your understanding!

You are tuning a database that uses leveled compaction. Your workload has become extremely write-heavy, and the high write amplification is causing performance bottlenecks and wearing out your SSDs. You have plenty of cheap disk space available.

How could you adjust the size ratio R to alleviate the write pressure? What would be the primary negative consequence of this change on your system's performance?

Show answer

To alleviate write pressure in a leveled compaction strategy, you should increase the size ratio R.

Justification:

The write amplification for leveled compaction is O(R * log_R(N)). While increasing R increases the linear R term, it simultaneously decreases the logarithmic log_R(N) term (fewer levels). In practice, for a given amount of data moved between levels, a larger R means you compact less frequently, reducing the overall write amplification over time. For example, moving from R=10 to R=20 means level L_{i+1} is now 20x larger than L_i, so a merge from L_i is a smaller portion of L_{i+1} and these merges happen less often for the database as a whole.
The primary negative consequence would be an increase in read amplification. The read amplification is O(log_R(N)). By increasing R, you decrease the number of levels, which seems like it should improve reads. However, this analysis is for point reads. For range scans, a larger R means each level is much bigger, potentially increasing the cost of scans. More fundamentally, a larger R means the in-memory indexes (like fence pointers) for each level will be much larger, increasing the Memory part of the RUM trade-off. If memory is constrained, this could hurt performance. The more direct answer is that a larger R generally pushes the system towards being more tiering-like, trading better write performance for worse read performance.

Conclusion

In this lesson, we moved from a qualitative to a quantitative understanding of the core trade-offs in LSM-tree design. By analyzing the amplification factors, you can now reason about why and how different compaction strategies are suited for different workloads.

Key Takeaways:

Write, Read, and Space Amplification are the key metrics for analyzing the performance of storage engines.
The RUM Conjecture (Read, Update, Memory) provides a universal framework for understanding that these factors are in constant tension.
The size ratio (R) is a critical tuning parameter that directly controls the trade-offs within an LSM-Tree.
Leveled compaction has high write amplification (O(R*logN)) but low read (O(logN)) and space (O(1)) amplification.
Tiered compaction has low write amplification (O(logN)) but high read (O(R*logN)) and space (O(R)) amplification.

Preview of the Next Lesson

We saw that read amplification, especially in tiered compaction, can be very high (O(R*logN)). In practice, systems cannot afford to check every single file for every single read. How is this problem solved? In our next lesson, we will investigate the answer: Bloom filters. We will cover the learning outcome: "Explain how Bloom filters are used in LSM-Trees to reduce I/O for point lookups of non-existent keys." This is a crucial optimization that makes LSM-trees practical for a wide range of applications.

Recommended resources