Log-Structured Merge-Trees: Optimizing Storage Engines for Write-Heavy Workloads

Traditional relational database management systems use B-Trees or B+ Trees as their primary on-disk indexing structure. While B-Trees provide optimal $O(\log N)$ point lookups and range scans, updating an in-place B-Tree requires mutating random disk pages spread across storage. On modern SSDs and NVMe drives (as well as legacy HDDs), random write operations cause significant write amplification, flash block erase overhead, and limited throughput.

Introduced by Patrick O'Neil, Edward O'Neil, and Gerhard Weikum in 1996, the **Log-Structured Merge-Tree (LSM-Tree)** trades point-lookup simplicity to maximize write performance. By converting all modifications (inserts, updates, and deletes) into sequential append-only disk operations, LSM-Trees provide write throughput orders of magnitude higher than traditional B-Trees.

Core Architectural Anatomy

An LSM-Tree consists of memory-resident buffers coordinated with multi-layered, immutable on-disk structures:

1. Write-Ahead Log (WAL)

When a write arrives, it is first written sequentially to an append-only WAL file on disk to guarantee durability in the event of an abrupt system crash.

2. Active MemTable (In-Memory Buffer)

Concurrently with the WAL write, the data is inserted into an in-memory sorted structure called a **MemTable** (typically implemented using a concurrent Skip List or Red-Black Tree). Writes are acknowledged to the client immediately after updating the MemTable and appending to the WAL.

3. Immutable MemTable (Flush Phase)

Once the active MemTable reaches a configurable memory size threshold (e.g., 64 MB), it transitions into an **Immutable MemTable** (read-only), a fresh empty MemTable is allocated for new client writes, and a background thread sequentially flushes the immutable data to disk as a new Sorted String Table (SSTable).

4. Sorted String Tables (SSTables)

An **SSTable** is an immutable on-disk file containing sorted (key, value) pairs organized into data blocks with an accompanying index block, block-level compression, and an embedded Bloom Filter.

The Read Path: Mitigating Read Amplification

Because updates do not overwrite existing records in-place, keys may exist across multiple SSTable files on disk. Reading a key requires traversing the hierarchy in reverse chronological order:

1. Check the active in-memory MemTable.
2. Check any in-memory Immutable MemTables awaiting flush.
3. Search the on-disk SSTables from Level 0 (newest) down to Level L (oldest) using binary search across SSTable index blocks.
4. Return the first (newest) match encountered. If a special **Tombstone** marker is found, treat the key as deleted.

Bloom Filter Read Acceleration

To prevent issuing physical I/O requests to every SSTable file for missing keys, every SSTable contains a built-in Bloom Filter loaded into RAM. The Bloom Filter can decisively determine if a key is definitely absent from an SSTable file, eliminating unnecessary disk read operations for over 99% of negative queries.

Compaction Strategies: Maintaining Bounded Storage and Latency

As SSTables accumulate on disk, the system experiences **Read Amplification** (checking multiple files per query) and **Space Amplification** (storing obsolete overwritten versions and tombstones). Background **Compaction** processes merge and deduplicate SSTables into new sorted files.

1. Size-Tiered Compaction Strategy (STCS)

• Mechanism: Groups SSTables into tiers of similar file sizes. When a tier accumulates a threshold number of files (e.g., 4), all files in that tier are merged into a single larger SSTable.
• Trade-off: Fast, low-overhead writes, but high space amplification (often requires 50% free disk headroom during large merges).

2. Leveled Compaction Strategy (LCS - RocksDB / LevelDB Style)

• Mechanism: Divides disk storage into numbered levels ($L_0, L_1, L_2, \dots, L_k$), where each level's total capacity is 10x larger than the previous level. Within each level above $L_0$, key ranges between SSTables are strictly non-overlapping.
• Trade-off: Superior read latency and predictable space footprint (~10% overhead), at the cost of higher background write amplification during multi-way merges.

C++ Conceptual Simulation Blueprint (MemTable & SSTable Flush)

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <memory>

struct SSTable {
    std::vector<std::pair<std::string, std::string>> entries;

    bool get(const std::string& key, std::string& value) const {
        // Binary search across sorted on-disk entries
        int left = 0, right = entries.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (entries[mid].first == key) {
                value = entries[mid].second;
                return true;
            } else if (entries[mid].first < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

class LSMStorageEngine {
private:
    size_t memtableThreshold;
    std::map<std::string, std::string> memTable;
    std::vector<std::shared_ptr<SSTable>> sstables; // Ordered newest to oldest

    void flush() {
        auto sstable = std::make_shared<SSTable>();
        for (const auto& [k, v] : memTable) {
            sstable->entries.push_back({k, v});
        }
        sstables.insert(sstables.begin(), sstable); // Prepend to newest
        memTable.clear();
    }

public:
    LSMStorageEngine(size_t threshold = 4) : memtableThreshold(threshold) {}

    void put(const std::string& key, const std::string& value) {
        memTable[key] = value;
        if (memTable.size() >= memtableThreshold) {
            flush();
        }
    }

    void del(const std::string& key) {
        put(key, "__TOMBSTONE__");
    }

    bool get(const std::string& key, std::string& value) const {
        // 1. Check active MemTable
        auto it = memTable.find(key);
        if (it != memTable.end()) {
            if (it->second == "__TOMBSTONE__") return false;
            value = it->second;
            return true;
        }

        // 2. Check SSTables in reverse chronological order
        for (const auto& table : sstables) {
            std::string foundVal;
            if (table->get(key, foundVal)) {
                if (foundVal == "__TOMBSTONE__") return false;
                value = foundVal;
                return true;
            }
        }
        return false;
    }
};

Real-World Engineering and Production Implementations

1. Meta RocksDB & Google LevelDB: High-performance embedded key-value storage engines backing systems like Kafka Streams, Ceph, CockroachDB, and TiKV.
2. Apache Cassandra & ScyllaDB: Distributed NoSQL databases using LSM-Tree storage per column family to handle millions of writes per second per node.
3. ClickHouse & Apache Doris: Real-time analytical OLAP databases storing column chunks using log-structured merge variants (MergeTree engine family).
4. Google Bigtable & Apache HBase: Distributed sparse multidimensional storage engines utilizing SSTables on Google File System (GFS) and HDFS.