How RocksDB compacts data with LSM trees

The Interview Question

Interviewer: "Your team uses RocksDB as the storage engine behind a high-throughput event ingestion service. You are seeing periodic write stalls where latency spikes from 1ms to 500ms. The disk I/O looks fine between stalls. Walk me through how RocksDB organizes data on disk, why compaction is necessary, and what could cause these stalls."

This question tests whether you understand the Log-Structured Merge-tree (LSM tree) architecture that powers RocksDB, and more specifically, the compaction process that keeps the system healthy over time. The interviewer wants to hear you explain memtables, SSTables, levels, and why compaction is both essential and the primary source of performance problems. Candidates who just say "RocksDB is a key-value store" without explaining the write path and compaction lifecycle miss what makes storage engines interesting.

What to Clarify Before Answering

You: "Before I walk through the internals, let me scope this..."

• "Are we talking about RocksDB embedded directly, or as the engine underneath something like CockroachDB or MyRocks? The tuning context changes significantly."
• "Is the workload write-heavy, read-heavy, or mixed? Compaction strategy choice depends on this."
• "How large is the dataset relative to available memory? This determines how much of the read path hits disk."
• "Are there many deletes or overwrites, or mostly inserts? Tombstone accumulation affects compaction pressure differently."
• "Is the storage SSD or spinning disk? RocksDB's default settings assume SSD."

Why this matters: RocksDB's behavior changes dramatically based on workload pattern, hardware, and how the engine is embedded. A candidate who asks these questions shows they understand that "how RocksDB works" is really "how RocksDB works for your specific workload."

The 30-Second Answer

RocksDB is a persistent key-value store built on an LSM tree architecture. Writes go first to an in-memory write-ahead log (WAL) for durability, then to an in-memory memtable (a sorted skip list by default). When the memtable fills up, it becomes an immutable memtable and gets flushed to disk as a Sorted String Table (SSTable) at Level 0. Over time, SSTables accumulate across multiple levels (L0 through L6), with each level being roughly 10x larger than the previous one. Compaction is the background process that merges SSTables from one level into the next, removing duplicate keys, applying deletes (tombstones), and maintaining sorted order. Without compaction, reads would slow to a crawl because every read might need to check dozens of files. The tradeoff is write amplification: each byte of user data may be rewritten 10-30x as it moves through levels.

The Architecture Overview

The LSM tree architecture separates writes from reads in a fundamental way. Writes always go to memory first (fast), and background processes organize data on disk over time. This is the opposite of B-tree based engines like InnoDB, where writes update pages in place.

I find the key insight is that L0 is special. Files in L0 can have overlapping key ranges because they are direct flushes from memtables. Every other level (L1 through L6) maintains a strict invariant: files within the same level never overlap in key range. This is what makes reads efficient at deeper levels (you only need to check one file per level) but makes L0 the bottleneck (you must check every L0 file).

The size ratio between levels is typically 10x. If L1 holds 256MB, L2 holds ~2.5GB, L3 holds ~25GB, and so on. Most of your data lives in the deepest levels. This means compaction at deeper levels moves enormous amounts of data, which is the primary source of write amplification.

The Write Path: From Put() to Disk

Every write in RocksDB follows the same sequence, and understanding it explains both the performance characteristics and the failure modes.

Step 1: WAL append. The write-ahead log gets the entry first. This is a sequential append to a file, which is fast on any storage medium. By default, RocksDB groups multiple writes and issues a single fsync for the batch (group commit). If the process crashes after the WAL write but before the memtable insert, recovery replays the WAL.

Step 2: Memtable insert. The key-value pair goes into the active memtable, which is a skip list by default. Skip lists give O(log n) insert and lookup with good concurrent read performance. The memtable keeps entries sorted by key, which is critical because the eventual SSTable on disk must be sorted.

Step 3: Freeze and switch. When the memtable reaches its size limit (default 64MB, controlled by write_buffer_size), RocksDB freezes it into an immutable memtable and creates a fresh active memtable. You can have multiple immutable memtables waiting to be flushed (controlled by max_write_buffer_number).

Step 4-5: Flush to SSTable. A background flush thread iterates through the immutable memtable in sorted order and writes an SSTable file to L0. Each SSTable contains data blocks (typically 4KB), an index block for binary search, metadata blocks, and a bloom filter.

For your interview: the write path is "WAL, memtable, flush." Three words. Say them, then elaborate on whichever part the interviewer cares about.

Deletes Are Writes

This trips up many candidates. When you call Delete(key), RocksDB does not find and remove the key. It writes a tombstone marker, a special entry that says "this key is deleted as of sequence number N." The actual removal happens later during compaction when the tombstone meets the original entry and both are discarded.

This means a workload with heavy deletes can temporarily increase disk usage, not decrease it. I have seen teams confused by this: "We deleted 50% of our data but disk usage went up." The tombstones are the reason.

The Read Path: Finding a Key Across Levels

Reads in RocksDB must check multiple locations because the most recent version of a key could be anywhere in the LSM tree. The search follows a strict order, and several optimizations make this practical.

Memtable check. The active memtable is checked first because it has the most recent writes. This is a skip list lookup: O(log n) in the memtable size. If found, we are done.

Immutable memtable check. If there are immutable memtables waiting for flush, check them in reverse chronological order. Still in-memory, still fast.

L0 search. This is the expensive part. Because L0 files can have overlapping key ranges, you must check every L0 file. If there are 10 files in L0, that is 10 potential disk reads. This is why L0 file count is a critical metric: more L0 files means slower reads.

L1+ search with bloom filters. For L1 and deeper, RocksDB first consults the bloom filter for each SSTable. A bloom filter is a probabilistic data structure that can tell you "this key is definitely not in this file" or "this key might be in this file." With a 1% false positive rate (10 bits per key), bloom filters eliminate ~99% of unnecessary disk reads.

When the bloom filter says "maybe," RocksDB does a binary search on the SSTable's index block to find the right data block, then reads that single data block (typically 4KB) from disk (or block cache).

Block cache. RocksDB maintains an LRU block cache in memory (default 8MB, but you should size this to 30-50% of available RAM in production). Hot data blocks stay cached, making repeated reads for popular keys hit memory instead of disk.

The Block Cache and Compression

Data blocks in SSTables are typically compressed (using LZ4, Snappy, or Zstd). RocksDB stores compressed blocks on disk but caches uncompressed blocks in the block cache. This means:

• Disk I/O reads compressed data (less bandwidth needed)
• CPU decompresses on read (small cost on modern CPUs)
• Block cache holds uncompressed data (faster access, more memory used)

You can also enable a secondary compressed block cache for cold data, which trades CPU for memory efficiency. I recommend Zstd compression for production: it gives the best compression ratio with acceptable CPU overhead.

Compaction Strategies: Leveled vs Universal vs FIFO

This is where RocksDB gets interesting and where most of the tuning complexity lives. The compaction strategy determines how SSTables move between levels and directly controls the tradeoff between write amplification, read amplification, and space amplification.

Leveled Compaction (Default)

Leveled compaction is the default and the right choice for most workloads. Here is how it works:

1. L0 trigger. When the number of L0 files reaches a threshold (default 4, controlled by level0_file_num_compaction_trigger), compaction picks one or more L0 files.
2. Find overlapping files. RocksDB identifies which files in L1 overlap with the key range of the selected L0 files.
3. Merge-sort. The L0 and L1 files are merge-sorted together, producing new L1 files with non-overlapping key ranges.
4. Cascading. If L1 now exceeds its size limit, the same process triggers for L1-to-L2, then L2-to-L3, and so on.

The invariant at each level (except L0): files within a level have non-overlapping key ranges, and each level is at most 10x the size of the previous level.

Write amplification math. In leveled compaction, each byte of data is rewritten roughly once per level. With a 10x multiplier and 7 levels, that is theoretically up to 10 * 6 = 60x write amplification in the worst case. In practice, it averages 10-30x depending on workload.

Universal Compaction (Size-Tiered)

Universal compaction groups SSTables into "sorted runs" and merges them when enough runs accumulate or when the size ratio between consecutive runs exceeds a threshold.

I reach for universal compaction when:

• The workload is write-heavy with few reads (logging, time-series ingestion)
• You can tolerate temporarily higher space amplification
• Write amplification must be minimized (flash storage with limited write endurance)

Universal compaction typically achieves 2-3x lower write amplification than leveled, but read amplification is higher because there are more sorted runs to check.

FIFO Compaction

FIFO compaction is the simplest: it never merges files. When total data exceeds a limit, it deletes the oldest SSTable files. This only works for time-series data where old data has no value.

I use FIFO for metrics buffers and temporary event logs that have a fixed retention window. Do not use it for anything that requires point lookups on old keys.

Choosing the Right Strategy

Compaction Mechanics: The Merge-Sort Process

Let me walk through exactly what happens during a single leveled compaction job, because this is where the CPU and I/O costs live.

File picking. The compaction scheduler selects which files to compact. For leveled compaction, it picks L0 files and finds all L1 files whose key ranges overlap. The goal is to minimize the total amount of data read and written.

Merge-sort with deduplication. RocksDB creates a merge iterator that reads from all input files simultaneously, producing keys in sorted order. When the same key appears in multiple files, only the newest version (highest sequence number) survives. This is where updates and overwrites get resolved.

Tombstone handling. Tombstones (delete markers) can only be dropped when compaction reaches the bottommost level. At higher levels, the tombstone must be preserved because there might be an older version of the key at a deeper level. If you drop the tombstone too early, old data "resurrects."

I find tombstone handling to be the subtlest part of compaction. If your workload has heavy deletes and compaction is not reaching the bottom level frequently, tombstones accumulate and both inflate disk usage and slow down range scans (the iterator must process and skip every tombstone it encounters).

Installation. After merge-sort completes, RocksDB atomically swaps in the new files and removes the old ones. This is done via a MANIFEST file that records the current set of live files. The swap is atomic: at no point do readers see an inconsistent state.

Write Amplification vs Read Amplification vs Space Amplification

This is the central tradeoff in any LSM tree engine, and the interviewer often directly asks about it. You cannot optimize all three simultaneously. Every design choice picks two and sacrifices the third.

Write amplification measures how many times each byte of user data gets physically written to disk. A write amplification of 20x means each 1KB put results in 20KB of total disk writes (across flush, compaction, and WAL).

Read amplification measures how many disk reads are needed to satisfy a single point lookup. Fewer levels and more aggressive compaction mean lower read amplification but higher write amplification.

Space amplification measures the ratio of actual disk usage to logical data size. Obsolete key versions, pending tombstones, and temporarily duplicated data during compaction all contribute.

For your interview: say "LSM trees have a three-way tradeoff between write amplification, read amplification, and space amplification. Leveled compaction optimizes for reads and space at the cost of writes. Universal optimizes for writes at the cost of reads and space." That single sentence shows you understand the design space.

Column Families and Concurrent Compactions

RocksDB supports multiple column families within a single database instance. Each column family has its own memtable, set of SSTables, and compaction pipeline, but they share a single WAL.

Think of column families as logically separate key spaces that share a transaction log. I use them to separate data with different access patterns. For example, a metadata column family (small values, frequent reads) can use aggressive leveled compaction with large bloom filters, while a data column family (large values, write-heavy) uses universal compaction with minimal bloom filters.

Each column family compacts independently, which means you can have 3-4 concurrent compaction threads working on different column families without contention. The shared WAL ensures atomicity for cross-column-family writes (WriteBatch).

What Happens When Things Break

Performance Characteristics

Throughput. On a modern NVMe SSD, RocksDB can sustain 200K-500K writes/sec for small values (100B) and 50K-200K point reads/sec with a well-tuned block cache. These numbers drop significantly with large values, spinning disks, or poorly tuned compaction.

Memory budget. I allocate memory roughly as: 50% to block cache, 20% to memtables (write_buffer_size * max_write_buffer_number * column_families), 20% to bloom filters and index blocks, 10% to OS page cache headroom.

How This Compares to Alternatives

I reach for RocksDB when the workload is write-heavy and I need an embeddable engine with production-grade tuning. For read-heavy workloads where write amplification matters (flash wear), I look at WiscKey-style engines like BadgerDB. For server-mode databases where I do not need embedding, PostgreSQL or MySQL with InnoDB gives you B-tree performance with less operational complexity.

The honest answer: if you do not know whether you need RocksDB's specific characteristics, you probably want a B-tree engine. LSM trees require more tuning, more monitoring, and more understanding to run well in production.

Interview Cheat Sheet

• When asked "what is RocksDB?": "RocksDB is an embedded persistent key-value store built on an LSM tree. Writes go to a memtable in memory, flush to sorted SSTables on disk, and background compaction merges and sorts data across levels."
• When asked "why not just use a B-tree?": "B-trees do random I/O on writes. LSM trees convert random writes to sequential I/O, giving 5-10x better write throughput on SSDs. The tradeoff is read amplification and background compaction work."
• When asked "what is compaction?": "Compaction is the background process that merge-sorts SSTables from lower to higher levels, deduplicates keys, resolves tombstones (deletes), and maintains sorted order within each level."
• When asked "what is write amplification?": "Each byte written by the user gets rewritten multiple times as it moves through LSM levels. In leveled compaction, write amplification is typically 10-30x. Universal compaction reduces this to 2-4x."
• When asked about compaction strategies: "Leveled optimizes for reads and space (non-overlapping files per level). Universal optimizes for write throughput (fewer total merges). FIFO is for time-series data with no merging."
• When asked "why do reads slow down?": "The main culprit is L0 file count. L0 files can overlap, so every read must check all L0 files. Bloom filters help at deeper levels but not at L0 with overlapping ranges."
• When asked about write stalls: "Write stalls happen when compaction cannot keep up with incoming writes. L0 file count exceeds thresholds, and RocksDB throttles or stops writes to let compaction catch up."
• When asked about tombstones: "Deletes write a tombstone marker. The actual data is only removed when compaction processes the tombstone at the bottommost level. Until then, tombstones inflate disk usage and slow range scans."
• When asked about column families: "Column families share a WAL but have independent memtables and compaction pipelines. Use them to separate data with different access patterns and tune each independently."
• When asked about memory tuning: "Allocate ~50% to block cache, ~20% to memtables, ~20% to bloom filters and indexes. The block cache hit ratio should be above 90%."

Test Your Understanding

Quick Recap

1. RocksDB uses an LSM tree: writes go to a WAL and memtable in memory, then flush to sorted SSTables on disk across multiple levels.
2. Compaction is the background merge-sort process that moves data from L0 to deeper levels, deduplicating keys and resolving tombstones.
3. L0 is special because files can have overlapping key ranges, making it the primary bottleneck for read performance.
4. Leveled compaction optimizes reads and space (10-30x write amplification). Universal optimizes writes (2-4x write amplification, higher space usage).
5. Bloom filters eliminate ~99% of unnecessary disk reads for point lookups, making them essential for read performance.
6. Write stalls occur when compaction cannot keep up with flush rate, causing L0 file count to hit throttle thresholds.
7. Tombstones (delete markers) are not reclaimed until compaction reaches the bottommost level, which can temporarily increase disk usage after bulk deletes.
8. The three-way tradeoff between write, read, and space amplification is the fundamental design tension in all LSM tree engines.

Related Concepts

• B-tree storage engines work with in-place updates instead of append-only writes, giving lower write amplification but higher random I/O on writes.
• Write-ahead logging is the durability mechanism shared by virtually all database engines, ensuring committed writes survive crashes.
• Bloom filters are the probabilistic data structure that makes LSM tree reads practical by eliminating unnecessary disk I/O.
• Key-value separation (WiscKey) is an alternative LSM design that stores large values in a separate log, reducing write amplification for workloads with large value sizes.
• Database indexing concepts apply to understanding how SSTable index blocks and bloom filters trade memory for read performance.