Part 6 of 8 · 3 min read
Compaction, Bloom filters and write amplification
The background work that keeps reads fast, and what it costs.
Think of cleaning a desk covered with stacks of papers. Sorting them into one pile takes time away from other work. But if the clerk never tidies, finding a letter means looking through every stack.
Reads in an LSM-tree get slower as files pile up, since a read may have to check many of them. The book adds that a lookup for a key that does not exist is the worst case: the engine must check the memtable and every file, back to the oldest, before it can be sure.
Bloom filter
A Bloom filter is a small in-memory structure that can say "this key is definitely not in the file" or "it might be". It never gives a wrong "not present".
Example: before reading a file from disk to look for key zebra, the engine asks the file's Bloom filter. If it answers "definitely not", the read is skipped.
The book notes that Bloom filters save many unnecessary disk reads for missing keys. A few bits per key are enough to cut false alarms to about one in a hundred (a standard figure, not from the book).
A worked example. A key is looked up in an LSM-tree with 8 files, and it is absent.
- Without filters: 8 file reads (one per file).
- With filters that wrongly say "might be present" 1 time in 100: expected reads = 8 × 0.01 = 0.08. Almost none.
The compaction choices, as the book names them:
- Size-tiered compaction. Newer, smaller SSTables are merged into older, larger ones. HBase uses this, and Cassandra supports it.
- Leveled compaction. The key range is split into small SSTables, and older data is moved to separate levels. This allows compaction to go in small steps and use less disk space. LevelDB and RocksDB use it, and Cassandra supports it.
Compaction has a price: data is written more than once.
Write amplification
Write amplification is the ratio of bytes the engine writes to disk over the lifetime of the data, to the bytes the application wrote.
Example: the application writes 1 GB. Over time, compaction rewrites it ten times, so the disk receives 10 GB. The write amplification is 10.
The book explains that both designs have it. A B-tree writes data at least twice (log and page), plus whole pages and splits. An LSM-tree rewrites data in each compaction. Amplification matters most on SSDs, which can be overwritten only a limited number of times before wearing out, and it limits the writes per second the disk can accept.
A worked example. An application writes 20 MB per second of new data. Disk bandwidth is 400 MB per second.
- Leveled compaction with write amplification of 15: the disk must write 20 × 15 = 300 MB per second. This uses 75 percent of the bandwidth.
- If the application grows to 30 MB per second: 30 × 15 = 450 MB per second, which is above 400. Compaction cannot keep up.
The book describes the danger. When compaction falls behind, unmerged files pile up until the disk is full, and reads slow because there are more files to check. Such engines usually do not slow down incoming writes, so the operator needs to monitor the backlog.
Another cost is delay in the tail. Compaction can interfere with ongoing reads and writes, and the book says the effect is small on average but can be large at high percentiles (Level 0, module 4), where B-trees are more predictable.
| B-tree | LSM-tree | |
|---|---|---|
| Write cost | Page rewrite plus log | Log plus memtable, then compaction rewrites |
| Write pattern on disk | Random | Sequential |
| Typical write amplification | High for small changes | Often lower, depends on tuning |
| Disk space | Some wasted in half-empty pages | Compact, rewritten without gaps |
For the curious For the curious
SSDs often run a log-structured algorithm inside their firmware to turn random writes into sequential ones, so the gap between the two designs is smaller on SSDs. Lower write amplification and less wasted space remain useful there.
Check yourself:
- What can a Bloom filter say for certain?
- In the worked example, why does compaction fail at 30 MB per second?