LSM Tree

Log-Structured Merge Tree

Overview

It's a data structure for storing key-value data on disk or in memory. The data is stored in leveled blocks. This structure stores the data sequentially—that's the meaning of log. When a new write arrives, it's written to the Memtable (a table running in memory) and also to a WAL (Write-Ahead Log) to keep the structure information if needed to recover the database.

When a Memtable is full, the data is written to an SSTable. When an SSTable is full, a new SSTable is created.

To retrieve a value, the engine searches for the key that contains the value across the blocks. First, it looks in the Memtable. If it doesn't find the key there, it passes to the most recent SSTable level and keeps doing that until it finds the key.

        ┌────────────────────────────┐
        │        Write-Ahead Log     │  (changelog for durability)
        └─────────────┬──────────────┘
                      │
               ┌──────▼──────┐
               │  MemTable   │   (in memory, sorted)
               └──────┬──────┘
                      │ flush
        ┌─────────────▼────────────────────────┐
        │          SSTable (level 0)           │
        ├──────────────────────────────────────┤
        │          SSTable (level 1)           │
        ├──────────────────────────────────────┤
        │          SSTable (level 2)           │
        └──────────────────────────────────────┘
                       ↓
                 Compaction merge

Key Concepts

SSTables (Sorted String Table)

They are immutable and sorted string tables that keep the information after the memtable is filled and needs to write the data to disk. This process is called Flushing.

Compaction

Over time, multiple SSTables may contain older versions of the same keys. A compaction process combines SSTables, removing duplicates and maintaining order. When a key is deleted, it is marked using a tombstone record. With that, in the next compaction, the key is omitted.