How RocksDB and LevelDB read and write data
Follow writes through WAL and memtable, flushes into L0 SST files, leveled reads, compaction, stalls, and RocksDB versus LevelDB tradeoffs.
The whole story in 6 lines
Trace WAL and memtable writes into flushes, sorted levels, read probes, compaction work, and the different choices in RocksDB and LevelDB.
- One logical write reaches both the WAL for recovery and the sorted memtable for current reads before acknowledgement.
- A full memtable becomes immutable and flushes to an L0 SST while foreground writes continue in a fresh memtable.
- L0 files may overlap, while deeper levels partition key ranges to reduce the number of files a read must probe.
- Reads check mutable state, immutable memtables, and candidate SSTs, using Bloom filters to skip definite misses.
- Compaction merge-sorts selected SSTs, keeps the newest value, drops obsolete entries, and rewrites non-overlapping output files.
- LevelDB and RocksDB share the LSM core, but RocksDB exposes more parallelism, column families, and tuning controls.
Setup
Welcome. Before we start, let us cover the big picture. An LSM tree is the storage engine behind databases like RocksDB and LevelDB. Think of it like a multi-layer filing system: new papers land on your desk first, and you sort them into drawers later.
An LSM tree stands for Log-Structured Merge tree. Instead of updating data in place, it always writes new entries first and merges them in the background. This makes writes very fast.
A WAL is a Write-Ahead Log. Before any change reaches memory, it gets written to this log file on disk. If the machine crashes, the WAL lets the database recover everything that was in progress.
A memtable is a sorted buffer that lives in RAM. New writes land here first so the database can serve fresh data without touching disk. When the memtable fills up, its contents get flushed to a file.
An SST file is an immutable, sorted file on disk. Once the engine writes one, it does not edit that file in place. Later stages will show how these files accumulate and get reorganized.
Over the next six stages, we will trace writes, flushes, levels, reads, and compaction. We will also compare how LevelDB and RocksDB manage that lifecycle. Let us start with the first moment a write arrives.
Write Beat
Now that the filing system idea is clear, let us follow one write from the application. The engine must make it recoverable and readable before acknowledging success.
The writer groups nearby updates into one batch, which gives them one ordered place in the write stream. Think of the batch as one envelope carrying several key changes together.
The same batch now feeds two structures at once. The WAL appends a recovery record on disk while the mutable memtable inserts those keys into its sorted memory view.
The WAL is the crash safety net because its append survives a process restart. During recovery, the engine replays those records and rebuilds the missing in-memory state.
Meanwhile, the memtable exposes the newest value to reads and keeps keys ordered. That ordering lets a later flush stream a sorted SST file instead of sorting from scratch.
Only after the write is logged and inserted can the engine acknowledge it under this durable path. Next, we will follow the memtable when it runs out of space.
Freeze + Flush
The memtable from the last stage keeps accepting sorted writes until it reaches its configured size. The engine cannot keep growing one in-memory structure forever, so it prepares a rotation.
When the limit arrives, the engine freezes that memtable and places it in an immutable queue. A fresh mutable memtable takes over, which separates foreground writes from background file creation.
The full table still contains live data, but foreground writers need somewhere new to go. What happens after a memtable fills?
A background flush worker scans the frozen table in key order and streams those entries into a new Level 0 SST. New writes can continue in the replacement memtable.
Switch the Engine control through both choices. Notice how LevelDB reaches stall risk with one frozen table, while RocksDB can absorb more backlog in its configurable immutable queue.
Once the SST is installed safely, the engine can eventually retire the matching recovery records. Level 0 now holds a fresh file, so next we will examine how many such files fit together.
Level Shape
★ If you remember one thing · Overlapping Level 0 files make flushes cheap, while non-overlapping lower levels make point reads selective.
The flush from the last stage created one immutable Level 0 file. Repeated flushes add more files whose key ranges may overlap, because each memtable contains a different slice of recent writes.
Level 0 accepts each sorted flush result without first reorganizing every older file. This keeps the foreground path cheap, but several files may now claim the same part of the key space.
That overlap shifts work to readers because one key can fall inside several Level 0 ranges. The engine must inspect candidates from newest to oldest until it finds a current value.
Compaction begins merging those overlapping runs into a lower level. The next frame reveals the shape that makes lower-level point lookups cheaper. What shape will those files take?
Level 1 and deeper levels divide the key space into sorted, non-overlapping files. Their greater capacity holds older data, while one key range points to at most one file per level.
The top stays friendly to fast flushes, while deeper levels spend compaction work to become easier to search. Next, we will trace one read through this exact layered shape.
Read Search
Now that we understand the level shape, let us follow one point lookup from newest state to oldest storage. The search order protects correctness because newer values must hide older versions.
The mutable memtable comes first because it contains writes that may not exist in any SST yet. A hit here can return the newest value without touching a disk file.
After a mutable miss, the engine checks frozen memtables and then Level 0 files from newest to oldest. Bloom filters can reject impossible files before expensive data blocks are read.
The same key might exist in memory and in older SST files, so probe order decides which version wins. Where does a point read look for the newest value first?
In each lower level, sorted non-overlapping ranges let the key select at most one candidate file. Index blocks narrow the search further before the engine reads the matching data block.
The search stops when the newest visible entry proves a value or deletion, while filters help establish misses cheaply. Next, we will see how compaction prevents this search path from growing without bound.
Compaction Work
The read path showed why too many overlapping files become expensive. Compaction pays background read and write work now so later lookups face fewer files and fewer obsolete versions.
A compaction picker chooses an input range and includes every lower-level file that overlaps it. Taking the complete overlap window prevents two output files in one level from claiming the same keys.
The engine opens sorted iterators over all selected files and merges their entries by key. Sequence numbers break ties, so the newest visible version wins without loading every file into memory.
During that merge, overwritten values and deletion markers can disappear only when older snapshots no longer need them. This careful rule reclaims space without changing what a valid reader should observe.
LevelDB follows a simpler serial compaction path, while RocksDB can divide a large key range into parallel subcompactions. Both lanes preserve sorted, non-overlapping output within the destination level.
After the new SSTs are installed, the old input files can be removed when no reader needs them. The read path is cleaner, which sets up our comparison of the two engines.
LevelDB vs RocksDB
We have now followed writes, reads, and compaction through the complete LSM core. LevelDB and RocksDB share that foundation, but they offer different amounts of machinery around it.
LevelDB stays intentionally compact, with a focused database interface and a small tuning surface. Its implementation is useful when you want the core leveled LSM design without many operational controls.
RocksDB extends that core with configurable write buffers, column families, background job pools, caches, filters, and rate limiters. Those controls help operators shape memory use and storage work.
Under a heavy write load, RocksDB can keep more flush and compaction work in flight. This extra concurrency can delay stalls, although it also demands careful CPU, memory, and input-output tuning.
For read-heavy workloads, RocksDB offers richer block-cache and filter controls that can avoid storage access. LevelDB remains the simpler baseline when that larger control surface would add little value.
The important point is not that one engine always wins. They share the same LSM tradeoff, while RocksDB exposes more ways to tune it. Now let us connect the whole story.
Recap
We started at the front door. A write batch lands in the WAL for crash safety and the memtable for fast lookups, both at the same time. That dual-write trick is what makes LSM trees durable without being slow.
When the memtable fills up, the engine freezes it and a background worker flushes it into a new Level 0 file on disk. Remember, RocksDB can queue several frozen memtables while LevelDB allows only one.
Level 0 files can overlap because each flush is independent. Lower levels are partitioned by key range so reads only need to check one file per level. That layered shape is the "tree" in LSM tree.
A point read walks from newest to oldest: memtable first, then immutable tables, then L0, then deeper levels. Bloom filters let most files say "not here" without touching data blocks, which is why they matter so much for read speed.
Compaction is the janitor. It picks overlapping files, merge-sorts them, drops old versions, and writes clean output. Without it, reads would get slower and slower as files pile up.
LevelDB keeps the design simple with minimal knobs. RocksDB layers on more write buffers, parallel compaction lanes, rate limiters, and richer bloom and cache options for production workloads.
And the cycle repeats. New writes feed the memtable, flushes create files, levels grow, reads search down, and compaction keeps the whole machine balanced. That is the complete LSM story.
The whole story in 6 lines
Trace WAL and memtable writes into flushes, sorted levels, read probes, compaction work, and the different choices in RocksDB and LevelDB.
- One logical write reaches both the WAL for recovery and the sorted memtable for current reads before acknowledgement.
- A full memtable becomes immutable and flushes to an L0 SST while foreground writes continue in a fresh memtable.
- L0 files may overlap, while deeper levels partition key ranges to reduce the number of files a read must probe.
- Reads check mutable state, immutable memtables, and candidate SSTs, using Bloom filters to skip definite misses.
- Compaction merge-sorts selected SSTs, keeps the newest value, drops obsolete entries, and rewrites non-overlapping output files.
- LevelDB and RocksDB share the LSM core, but RocksDB exposes more parallelism, column families, and tuning controls.