The LSM Tree: The Fast Journalist

Append-Only Writes

Imagine a journalist covering a breaking story. When new information arrives, they don't erase their old notes and rewrite them — they just write the new information at the bottom of their notepad. The notepad is always written sequentially, from top to bottom. This is the core insight of the LSM Tree: never overwrite data in place; always append.

When you update a user's email in an LSM-based database, the engine does not find the old record and change it. It simply writes a new record at the end of a log: {user_id: 123, email: "[email protected]", timestamp: T2}. The old record {user_id: 123, email: "[email protected]", timestamp: T1} still exists on disk. The database now has two versions of the same row, and the read path is responsible for figuring out which one is current (the one with the higher timestamp).

The Write Path: MemTable → SSTable → Levels

Stage 1: MemTable (in RAM)
All writes go to an in-memory sorted data structure called the MemTable (typically a red-black tree or skip list). Writes to RAM are essentially instant — no disk I/O at all. The MemTable is also backed by a sequential on-disk commit log for crash recovery.

Stage 2: SSTable Flush (RAM → Disk)
When the MemTable reaches a size threshold (e.g., 64 MB), it is sorted and flushed to disk as an immutable file called an SSTable (Sorted String Table). This flush is a single large sequential write — exactly the kind of I/O that storage devices love.

Stage 3: Compaction (Disk → Disk)
Over time, many SSTables accumulate on disk. A background process called Compaction periodically reads multiple SSTables, merges them (like merge sort), discards old versions of updated records and tombstones for deleted records, and writes a new, consolidated SSTable. This is also sequential I/O.

Write Path:
  Client Write
       │
       ▼
  [MemTable] ──── (also written to) ──── [Commit Log on Disk]
  (in RAM, sorted)
       │
       │ (when full, ~64MB)
       ▼
  [SSTable L0] ← immutable, sorted, flushed to disk
       │
       │ (background compaction)
       ▼
  [SSTable L1] ← merged, deduplicated
       │
       │ (background compaction)
       ▼
  [SSTable L2] ← larger, fewer files

The Read Path: Checking Multiple Locations

To read a record, the engine must check every place the record might exist:

1. MemTable (RAM) — most recent writes are here.
2. Level 0 SSTables on disk — recently flushed files.
3. Level 1 SSTables on disk.
4. Level 2 SSTables on disk.
5. ... and so on until the record is found or all levels are exhausted.

This is the fundamental read cost of LSM Trees: data is fragmented across multiple files, and finding the latest version requires checking all of them.

Key Point: LSM Trees achieve low write latency by converting random writes into sequential writes. The trade-off is that reads become more expensive (requiring checks across multiple files) and background compaction consumes significant CPU and disk I/O. In production, compaction storms — where compaction falls behind the write rate — are one of the most common operational problems with LSM-based databases like Cassandra and RocksDB.