If you’ve ever wondered why Cassandra, RocksDB, LevelDB or HBase write at speeds a relational database can only dream of, the answer lives in a structure called the LSM-tree (Log-Structured Merge Tree). It is the engine that has made writing nearly free in the NoSQL world.
The starting idea is counterintuitive: to write fast, you first write unsorted and sort things out later. That sidesteps the classic bottleneck of disks and RAM.
The problem it came to solve
A classic relational database (MySQL, or PostgreSQL with its B-tree engine) keeps its data in sorted branches. When you insert a row, it must find its exact spot in that tree and, if the page is full, split it in two. That involves seeks (disk head movement) and random writes — the two slowest operations a hard drive can do, and expensive on SSDs too.
The LSM-tree flips the script: instead of finding each datum’s position right away, it accumulates writes in memory and flushes them in bulk, in sequential writes that are tens of times faster.
The pieces of an LSM-tree
The design rests on three components working in cycles:
- Memtable: an in-memory structure (usually a sorted tree or table) where all new writes land. It’s fast but volatile: if the process crashes, it’s gone.
- Write-Ahead Log (WAL): the operation journal. Before touching the memtable, each write is recorded append-only on disk. If the machine shuts down, the memtable is rebuilt by replaying the log. It is the system’s safety net.
- SSTable: when the memtable fills up, it is flushed to disk as an immutable, already-sorted file called an SSTable (Sorted String Table). Each flush produces a new one, and immutability is the key: files never change, enabling stable reads and cheap compression.
Over time, many SSTables accumulate. To find a specific key, the system must scan them all, newest to oldest, until it finds the valid version.
Compaction: the system’s vacuum cleaner
If SSTables grew without bound, reads would become a nightmare of searches across dozens of files. That’s where compaction comes in: the process that merges several SSTables into one, discarding obsolete and deleted values and regrouping data into levels (L0, L1, L2, …).
There are two classic strategies. In size-tiered compaction (Cassandra’s), SSTables that have reached the same size are merged. In leveled compaction (RocksDB’s), each level is kept small and only compacted when needed. You write fast up front; then, in the background, the system gradually restores order. Because SSTables are immutable, compaction is safe and can run without blocking reads.
Cheap writes, expensive reads: the trade-off
The LSM-tree is a deliberate exchange: it optimizes writes and pays the cost on reads. Reads may require checking several SSTables and, in the worst case, walking multiple levels. Two tricks mitigate this:
- Bloom filters: a probabilistic structure that, using very little memory, tells you whether a key is not in an SSTable. If it says “no”, the entire file is skipped. This trims useless reads to almost nothing.
- Block index: each SSTable stores a map of the keys it contains, skipping straight to the right region of the file.
That extra read cost is the price you pay in exchange for massive ingestion: event logs, telemetry, sensor data — any stream where a lot arrives and little is queried.
Where you’ll really find it
LevelDB (Google) popularized it as an embedded store; RocksDB (Facebook/Meta) inherited it and took it into production at Facebook and into the storage layer of many modern databases; Cassandra and HBase use it in distributed systems; and SQLite even adopted it as an optional mode alongside its classic B-tree. Next time you see a Kafka or a time-series store under heavy load, you’ll know why it keeps its pace.
The LSM-tree shows that sometimes the winning strategy isn’t doing things better, but doing them in a different order: accepting chaos up front and tidying it up calmly afterward.
