What is an LSM Tree? The Log-Structured Merge Tree Explained

Every database eventually faces the same problem: applications insist on writing randomly while disks, even the fastest on the market, prefer sequential writes. 

The log-structured merge tree (LSM) is one of the two great answers to this problem, and it is the answer that RocksDB chose.

The first article in this series introduces the LSM tree, while this article gives it the full treatment: what the structure is, what actually happens to a write between the function call and the file on disk, and why the design wins on modern hardware. 

What is an LSM tree?

A log-structured merge tree (LSM) is a data structure that buffers incoming writes in memory and merges them onto disk in sorted, immutable batches. It never modifies data in place. Instead, it accumulates changes and defers the work of organizing, trading read-side simplicity for write throughput.

The LSM tree was formalized in a 1996 paper by Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil titled The log-structured merge-tree (LSM-tree). It spent about a decade as a relatively obscure academic structure before Google’s Bigtable built its storage layer on the concept. Bigtable’s design begat LevelDB, LevelDB begat RocksDB, and some flavor of LSM tree sits underneath most of the systems built for heavy ingest.  

The name suggests a single tree, which is very misleading. 

An LSM tree is better understood as a choreography of three components:

• A memtable: an in-memory buffer holding the most recent writes
• A write-ahead log (WAL): an append-only file on disk that makes those writes durable
• A growing collection of sorted string table files (SSTs): immutable, sorted files that hold everything older

Nearly everything interesting about LSM behavior follows from how data moves between these three components. All of that movement begins with a single, deceptively simple function call, typically referred to as a put.

What is a put? 

Put is a convenience wrapper that, internally, constructs a WriteBatch containing exactly one record and hands it to Write(), which handles mutations. 

The natural place to start is Put(key, value), but, strictly speaking, RocksDB has no such operation. Every write is a batch, and a lone put is simply a batch of one. Atomic multi-key writes come for free in RocksDB because this is a native operation.

A WriteBatch is a compact byte string with a fixed shape. That is, a 12-byte header holding an 8-byte sequence number and a 4-byte record count, followed by the records themselves. Each record is a one-byte type tag, a length-prefixed key, and, for writes, a length-prefixed value.

The claim from the first article in this series—keys and values are arbitrary byte arrays—becomes literal. The batch encoding neither knows nor cares what the bytes mean. The only structure imposed is the length prefixes. 

Every batch is stamped with a monotonically increasing counter known as a sequence number. It establishes a total order over every write the database has ever accepted. Sequence numbers are what make snapshots, consistent reads, and crash recovery possible. The WAL is replayable because every record in it knows its place in line.

Put, Delete, Merge

An important thing to note is that a Put is kTypeValue and a Delete is kTypeDeletion, which means a delete is not a removal. Instead, it is a write—a tombstone—that records the fact of deletion, with the actual reclamation deferred to compaction.

Put and Delete share the WriteBatch format with kTypeMerge, written by the Merge operation. Merge exists because read-modify-write is poison for a write-optimized store. Incrementing a counter with Put requires reading the current value, adding one, and writing the result back. That accounts for two traversals of the database to change a single number, with the read paying the full cost of the read path. 

Merge skips the read entirely. 

Instead, it appends an operand (i.e., a description of the change, such as “add one”) and returns. Nothing is computed at write time. The database folds operands into a final value later using an application-provided merge operator, either when the key is next read or when compaction encounters the chain.

Deletes defer reclamation whereas merges defer computation. 

The LSM tree’s entire personality is visible in these three type tags: every mutation, including the ones that logically depend on existing state, becomes a blind append. In an LSM tree, everything is an append. 

The LSM Tree Write Path Explained

The clearest way to understand LSM trees is to follow a single Put(key, value) from a function call to disk.

Step One: The Write-Ahead Log

The write is first appended to the WAL. This append happens before touching the memtable, and this ordering forms the durability contract. That is, once the WAL append completes, the write exists on disk in a form that survives a crash, even though it has not yet been organized for reading.

Appending to a log is the cheapest possible disk operation, which is the entire point. Durability is bought at sequential-write prices.

RocksDB batches concurrent writes into group commits to amortize cost further, and the sync option controls whether it flushes the append through the OS page cache to stable storage before the call returns.

Step Two: The Memtable

With durability secured, the write is inserted into the memtable. By default, RocksDB’s memtable is a skiplist. It uses a skiplist because the memtable needs to absorb concurrent writes and hand back its contents in sorted key order, both for reads and for the later flush.

A skiplist supports lock-free concurrent inserts while keeping everything sorted at all times. It is the data-structure equivalent of filing paperwork as it arrives, rather than letting it pile up.

Step Three: The Memtable Fills

The memtable grows until it hits a configured threshold (i.e., write_buffer_size), which defaults to 64 MB. At this point, it is marked immutable, a fresh empty memtable is swapped in, and incoming writes continue without interruption. The full, frozen memtable waits its turn to be flushed in the background. 

Writes never block on the flush itself.

Step Four: The Flush

A background thread writes the immutable memtable out to disk as an SST file in level 0 (L0) of the tree. Since the skiplist is already sorted, the flush is a single sequential pass that walks the entries in order and writes them out.

The memtable’s job is done, and the corresponding WAL entries can eventually be discarded. The data now survives on disk in its permanent, readable form.

What is inside an SST file?

The SST file is where data spends the rest of its life. It is organized into three blocks and a footer:

• Data blocks: the sorted entries themselves, a few kilobytes each, individually compressed
• Index blocks: mapping key ranges to block offsets, so a lookup can jump straight to the right block
• An optional bloom filter block: a compact probabilistic summary that can answer “this key is definitely not in this file” without reading anything else
• A footer: it locates all of the above

Every element of this layout exists to let future reads touch as few bytes as possible, especially the index and bloom filter.

A Walkthrough of the Write Path

Everything explained above is directly observable. What follows in this section is a quick trace of one Put through a database using ldb and sst_dump, the inspection tools that ship with RocksDB. The example uses Rust and the rocksdb crate, though any binding will do.

Prerequisites

To follow along, install the RocksDB command-line tools and a Rust toolchain. 

On macOS, brew install rocksdb provides both ldb and sst_dump. On Debian/Ubuntu, the package is rocksdb-tools.

With those installed, create a fresh project:

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

The rocksdb crate compiles the RocksDB C++ library from source on the first build, so expect the initial cargo run to take several minutes.

Step One: Write and Stop

Replace the contents of src/main.rs with the following code:

use rocksdb::{Options, DB}; 

fn main() { 
    let mut opts = Options::default(); 
    opts.create_if_missing(true); 
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap(); 

    db.put(b"slot:0001", b"hello").unwrap(); 
// Deliberately no flush. Let the process exit. 
} 

Run it once with cargo run, and then list the database directory it created:

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007 

CURRENT and the MANIFEST file track the database’s file inventory, while OPTIONS records the configuration it was opened with. LOG, without any number, is a human-readable text log for debugging, not to be confused with 000004.log, which is the write-ahead log itself.

Exact file numbers will differ from run to run, while the shape will not.

Note that we don’t have a single .sst file in the directory. The write is durable, since it survived the process exiting, but it only exists as a WAL record. This is the durability/organization split in action.

Step Two: Dump the WAL

Point ldb at whatever .log file the directory contains:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031 

We have one batch: sequence number 1, containing 1 record (29 bytes), which is a PUT whose key is the hex encoding of slot:0001. 

The size checks out against the encoding from earlier: a 12-byte header plus a 17-byte record, which encompasses one type tag, two length prefixes, a 9-byte key, and a 5-byte value.

Step Three: Flush and Dump the SST

First, delete the database directory (i.e., rm -rf /tmp/lsm-trace) so this run starts clean.

Add one line to main.rs after the put:

db.put(b"slot:0001", b"hello").unwrap(); 
db.flush().unwrap(); 

Calling db.flush().unwrap(); forces the memtable to be written out as an SST file rather than waiting for it to fill.

Run the file again, and then list the directory. 

We can now see that there’s a new .sst file in our output. We can inspect it with both of sst_dump’s useful modes, substituting the actual file name:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello 

Note that sst_dump prints a few preamble lines about the file format before the scan output; they are trimmed here and in the outputs below.

This is the key-value pair in its new permanent home, still carrying its sequence number. 

We can then see its properties using the following command:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties 

The properties output is the SST anatomy from earlier in the article itemized: data block count and size, index block size, filter presence, compression algorithm, and entry count. 

Even though we only have a single key, the structural elements are all itemized with one instructive exception. The filter block size is zero, and the filter policy is N/A because bloom filters are opt-in in RocksDB, configured via filter_policy, and the default options do not set one. 

The next article in this series will cover why production deployments almost always turn them on. 

Step Four: Reopen and Check the Log

Comment out the put and flush lines, leaving only the DB::open line, and run once more. Listing the directory now shows the old 000004.log gone, replaced by a fresh, nearly empty log with a higher number. Its contents were flushed to the SST in step three, so the records became obsolete and RocksDB discarded the file on reopen.

This is the entire WAL-memtable lifecycle coupling. 

To go one layer deeper, we can run step one’s binary under strace -e trace=write,fdatasync on Linux to show the durability contract at the syscall boundary. That is, the sequential write calls append to the .log file, with fdatasync appearing only when WriteOptions.sync is set.

Step Five: Delete the Key and Look at What Remains

The claim from earlier that a delete is a write can be observed directly. 

Modify main.rs to delete the key and force another flush:

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Run it and then list the directory. 

There will now be two .sst files. The older one is untouched because it is immutable, meaning it still contains the key and its value. We can verify this with a scan:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Now scan the newer file:

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

It is the same key, but with a higher sequence number, is type:0 instead of type:1, and it carries no value. This is a tombstone: the kTypeDeletion record from the WriteBatch section flushed into its own SST. The database now contains both the value and the record of its deletion, side by side in separate files.

Reading the key will resolve the contradiction in the tombstone’s favor. 

We can verify this by adding a lookup to the program:

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

It’ll print not found because the read path checks newer data first, and a sequence number of 2 outranks a sequence number of 1. From the database’s point of view, the value is gone, yet it is still sitting on disk in the older SST file. 

Nothing has been reclaimed, meaning the deletion has merely been recorded, and it will keep shadowing the value until compaction eventually merges the two files and drops both the tombstone and the shadowed value.

Step Six: Delete the Key and Look at What Remains

The Merge record type can be observed too. It requires configuring a merge operator, since RocksDB has no idea what an operand means without one.

Delete the database directory once more and replace main.rs with the following code:

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

Dumping the WAL shows three separate MERGE records. That is, three appends instead of a single read:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

The merge operator folded the chain at read time with the results as raw bytes. The program prints Some([51]) because 51 is the ASCII code for the character 3. Again, this is because keys and values are arbitrary byte arrays.

We can also add db.flush().unwrap(); before the lookup, delete the directory, and run the program again. A scan of the SST shows a single record:

'counter' seq:3, type:2 => 3

The flush applied the operator and collapsed them into a single operand.

Why is level 0 special?

New SST files land in level 0. They are direct snapshots of memtables, each one covering whatever key range that memtable happened to absorb, so L0 files can, and often do, overlap each other. This differs from every deeper level, as those files are non-overlapping; each file owns a distinct key range, so at most one file per level can contain a given key.

The consequence of this is that every L0 file is a separate place a key might hide, which makes the L0 file count a direct tax on read performance. This is why RocksDB watches the number of L0 files closely and begins throttling, or even stalling, writes when the count climbs too high.

Keeping L0 small is one of the main jobs of compaction.

Why do LSM trees beat B-trees for writes?

B-trees pay the cost of organization at write time so that reads find everything exactly where it belongs, while LSM trees defer organization to background compaction, which is paid later in bulk.

The B-tree is the structure that underlies most traditional databases. It updates data in place, meaning that every write finds the page that owns the key, reads it, modifies it, and writes it back. The pages involved are scattered across disk, so a stream of logically random writes becomes a stream of physically random I/O.

The LSM tree refuses to pay at write time. It appends (to the WAL), buffers (the memtable), and batches (flushes). Every disk write is sequential, and the organizational debt is deferred to compaction. The work does not disappear. Rather, it is paid later in bulk, consolidated into a form that disks handle really well.

This matters a lot on SSDs because they cannot overwrite data in place at all. 

Flash storage is erased in large blocks, spanning from hundreds of kilobytes to megabytes, and is written in smaller pages. This means that every small random overwrite forces the drive’s flash translation layer (FTL) to relocate live data and erase blocks behind the scenes. 

A B-tree’s random page writes make the FTL do this constantly. Write amplification is imposed by the device, stacked on top of whatever the data structure itself incurs, and is paid for both in throughput and drive lifespan. An LSM tree’s large sequential writes are close to the best case that flash hardware can be offered.

The best way to think about this is in the form of a loan. Deferred organization comes due as compaction I/O and reads must check more places than a B-tree would require. Thus, the LSM tree buys write throughput now and repays it later in the form of read and space amplification. 

For a more in-depth view on how the LSM tree compares to the B-tree with respect to read, write, and space amplification, see B-Tree vs LSM-Tree. 

What happens after RocksDB crashes?

The memtable is volatile memory, meaning that a crash erases it. This is precisely the reason the WAL exists.

On restart, RocksDB replays every write that had been acknowledged but not yet flushed to an SST. It inserts them into a fresh memtable to reconstruct the pre-crash state. Recovery cost is proportional to the un-flushed data, which is why the WAL and memtable lifecycles are linked. Once a memtable’s contents are safely flushed to an SST, the corresponding log entries are obsolete, and the WAL can be truncated.

A write is durable the moment the log append lands. It becomes cheaply readable later when the flush organizes it. B-trees couple these, while LSM trees split them apart, and most of the structure’s character follows from that split. 

How does Solana stress the write path?

The first article in this series described how Agave stores Solana’s ledger in RocksDB. Viewed from the write path, that workload is close to a purpose-built stress test. That is, shreds (i.e., the raw units of ledger data) arrive over the network continuously at line rate, and every one of them must clear the WAL-append-and-memtable-insert path before the validator’s storage layer has done its job.

The machinery involved is exactly the same as what this article traced, at production scale. When shreds arrive, the Blockstore’s insertion path in Agave validates a whole batch of incoming shreds, attempts Reed-Solomon recovery on any of the missing ones, and stages everything (i.e., shred payloads, slot metadata, erasure metadata, index updates) into a single RocksDB WriteBatch before committing it in one atomic write.

Simplified from insert_data_shred:

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

That comment is Agave’s engineers making this article’s point in nine words: the batch is the unit of atomicity, and a validator crash mid-insertion must never leave the ledger half-updated. 

The batch of one traced in the walkthrough is, inside a validator, a batch of thousands—shreds and their metadata across multiple column families, one sequence number range, one WAL append, and one group commit.

The nice part about this, though, is that shreds lead with the slot number (i.e., the (slot, index) tuple from the simplified code snippet is the ShredData key), and slots increase almost monotonically. Each memtable, therefore, absorbs a narrow, mostly consecutive band of the keyspace, and flushes produce L0 files that barely overlap.

We feel this write path directly. 

The archival systems we run at Helius ingest Solana’s full transaction history into RocksDB—hundreds of terabytes in an append-heavy, permanently growing workload—and the migration that produced that architecture is documented in our ClickHouse to RocksDB article.

Conclusion

An LSM tree is a bargain struck with hardware. All writes become sequential in exchange for deferring the work of keeping the data organized. This means that the read path is asked to look for data in more places than a B-tree, for instance. The memtable absorbs, the WAL guarantees, and the SSTs accumulate. On flash storage, where random overwrites are punished twice, this is an excellent bargain.

However, writes are the easy half. The price of this design is paid on reads since a key’s current value might exist in the memtable, an L0 file, or any level below. The machinery that keeps that price bounded is where LSM engineering gets rather interesting. 

The next article in the series will walk through the read path, covering memtables, bloom filters, the block cache, and the amplification triangle in action.

If following a single key-value pair through four distinct data structures sounds like a good afternoon, come build with us. The systems described in this series are the ones we deploy, operate, and tune at the scale of Internet capital markets. We’re hiring across our engineering team. See all of our open roles at helius.dev/careers.