There is an idea that sounds like a contradiction in any modern database engine: to write fast, you must avoid modifying what is already written. LSM engines (short for Log-Structured Merge) take that idea to the limit. Instead of finding a record’s exact slot in a file and rewriting it in place, the way a classic B+ tree index does, they buffer writes in memory and flush them out sorted, in new blocks, over and over.
A byte written is a byte never touched again
On a spinning disk or in flash memory, rewriting a single byte is not free: you have to read the whole block, change it and write it back. That inflates the real write cost by the block size and wears the cell out. LSM engines lean on a property of storage media: writing fresh data, well packed in large blocks, is far cheaper than modifying scattered data. The direct consequence is that LSM data files are immutable. Once closed, a file is never edited again; if a value changes, the new version is written elsewhere and the reader decides which one wins.
The journey of a write: WAL, memtable and the jump to disk
Every write operation follows the same path. First it is appended to the WAL (write-ahead log), a sequential file that is fsync-ed when durability matters: if the process crashes, the operation can be rebuilt. Then it goes into the memtable, an ordered in-RAM structure — usually a skiplist, or a balanced tree with counters — that keeps keys in lexicographic order so they can later be walked sequentially. The client already has its acknowledgement; the disk barely knows anything yet.
When the memtable crosses a threshold (say 64 MB and a cap on live entries), it becomes a frozen memtable: it stops accepting writes and a background thread flushes it to disk as an SSTable (Sorted String Table), an immutable block of sorted key-value pairs, compressed and paired with an internal index and, often, a per-block Bloom filter.
Fields of files and the art of compaction
Over time many sorted “runs” pile up: each holds valid data, but also stale versions of keys that live in more recent files as well. This is where compaction comes in: a background thread reads several files, merges their sorted keys (the same operation as a merge sort), drops superseded versions and discards what is no longer needed. The result is a new, cleaner file. It is the same trick as a transaction log that gets summarised every so often.
The classic strategy is leveled compaction (popularised by LevelDB and RocksDB): L0 holds the direct memtable flushes, which may overlap; from L1 upwards each level is sorted and split into disjoint key ranges, with a typical growth factor of 10×. A piece of data “moves up a level” only when it has to, and since each level is ten times larger than the previous one, the total cost of pushing a byte from memory to the bottom level is a geometric series that stays a small multiple. The alternative, tiered compaction, merges several files of the same level at once, writing less often but leaving more space occupied by redundant versions.
The price of writing fast: three amplifications
Nothing is free. LSM engines are judged by three uncomfortable numbers. Write amplification is how many bytes end up stored for every logical byte written: if a piece of data crosses seven levels, it is rewritten seven times. Space amplification measures how much disk the data occupies compared with its useful size, stale versions awaiting compaction included. And read amplification counts how many files must be consulted to answer a query. Tuning compaction is about pushing those three values in opposite directions.
Reading costs more: tombstones, filters and caches
To read a key, the engine checks the memtable and then the files from newest to oldest, level by level. To avoid opening all of them it uses a per-file Bloom filter, which rules out impossible candidates in one shot: if the filter says “not here”, the disk is never touched. When the filter says “maybe”, the block index is searched and the compressed block is read. Deletes in an immutable world remove nothing: they write a tombstone, a record marking the key as dead; compaction decides when it physically disappears. And if snapshot consistency is required, the engine keeps several versions of each key with a sequence number — the basis of multiversion concurrency control (MVCC), which lets readers work without blocking writers.
Where it fits and where it does not
The list of engines built this way is long: LevelDB, RocksDB (and everything that embeds it, from MySQL with MyRocks to the key-value stores of distributed systems), Cassandra, ScyllaDB, HBase, and variants such as ClickHouse’s MergeTree. They shine under write-heavy workloads, with hot recent keys and data that grows without end. They struggle with sustained random key lookups on old records, which is exactly where a B+ tree with its always-current structure keeps the edge. NVMe block flash, with its large writes and per-cell wear, tips the balance towards LSMs: writing in sequence and sorting later is, more and more, the natural way to deal with solid-state memory. Some designs go further and use zoned drives (ZNS) so the hardware itself aligns with the write order. The next time an engine takes two seconds on a query while swallowing a million rows per second without breaking a sweat, now you know why: it is betting that today’s mess will be fixed tomorrow by a merge.
