LSM-Tree: Fast Writes, Later Merges

WHY IT EXISTS Traditional databases using B-trees often update data in place, which requires slow random disk I/O that becomes a bottleneck in systems with massive write volumes. LSM-trees were invented to solve this by converting many small, random writes into large, sequential writes, which are much faster for both spinning disks and SSDs.

THE MENTAL MODEL Think of an LSM-tree like a busy receptionist managing a large filing cabinet. Instead of immediately filing every new document into the huge, sorted cabinet (a slow task), they first jot notes on a fast, temporary notepad. Periodically, they sort the notepad's contents and merge them into the main cabinet in one organized batch. The notepad is the fast, in-memory table (memtable); the cabinet is the permanent, on-disk storage (SSTables).

HOW IT WORKS All incoming writes go to a sorted, in-memory data structure called a memtable, making them extremely fast. When the memtable reaches a certain size, it is written to disk as a new, immutable, sorted file called an SSTable. This is a fast, sequential write operation. Reads first check the memtable for the data, then check the SSTables on disk, starting with the newest. A background process called compaction periodically merges smaller SSTables into larger ones, cleaning up old or deleted data to keep read performance from degrading over time.

WHEN TO USE IT Use LSM-trees for write-intensive workloads where high throughput is the primary concern. This is common in distributed databases, logging systems, time-series databases, and message queues. Systems like Apache Cassandra, RocksDB, and LevelDB are built on this principle to handle high insert volumes.

WHEN NOT TO USE IT Avoid LSM-trees for read-heavy workloads that demand the lowest possible and most predictable read latency. Because a read might have to check multiple files on disk (a phenomenon called read amplification), performance can be less consistent than with a B-tree, which offers a more balanced structure for lookups.

ONE CANONICAL EXAMPLE A database backing a high-traffic application's event logging service is a perfect fit. Every user action generates an event that must be stored quickly and reliably. An LSM-tree-based engine can ingest millions of these writes per second by batching them in memory before efficiently flushing them to disk in sequence.