Login
C Tutorials C++ Tutorials Java Tutorials Python Tutorials JavaScript Tutorials TypeScript Tutorials C# Tutorials Go Tutorials Rust Tutorials PHP Tutorials Kotlin Tutorials Swift Tutorials
HTML Tutorials CSS Tutorials Frontend Development Backend Development React Tutorials Next.js Tutorials Node.js Tutorials Django Tutorials Mobile App Development
Beginner Tutorials Advanced Guides Coding Roadmaps Interview Preparation DSA Tutorials Projects & Examples Cheat Sheets
About Us Contact Privacy Policy Terms & Conditions Disclaimer Sitemap

LSM-Trees: Storage Engines Optimized for High-Throughput Writes

Traditional database storage engines based on B+ Trees perform in-place updates, modifying data blocks directly on disk. While this delivers fast O(log N) point reads, it transforms random key insertions and updates into expensive random disk/SSD write I/O operations.

The Log-Structured Merge-Tree (LSM-Tree)—first introduced by Patrick O'Neil, Edward O'Neil, and Gerhard Weikum in 1996—solves this bottleneck by converting all write operations into purely sequential writes. By deferring and batching disk updates through an append-only architecture, LSM-trees maximize modern NVMe SSD and hard drive write throughput.

Core Architectural Components

An LSM-Tree storage engine coordinates four fundamental data structures across RAM and persistent disk storage:

1. Write-Ahead Log (WAL) — Disk

Every incoming write is first appended sequentially to an on-disk WAL file before any processing occurs. Because sequential disk appends are extremely fast, the WAL provides immediate durability and crash-recovery guarantees with near-zero latency overhead.

2. MemTable — RAM

Simultaneously, the key-value pair is inserted into an in-memory sorted data structure called the MemTable (commonly implemented using a Skip List or Red-Black Tree). The MemTable absorbs all real-time writes and serves the most recent reads directly from memory.

3. Immutable MemTable — RAM

When the active MemTable reaches a predefined capacity threshold (e.g., 64 MB), it freezes into an Immutable MemTable. A background worker thread flushes its sorted contents sequentially to disk as a new file, while a fresh active MemTable is initialized to handle incoming traffic without blocking.

4. Sorted String Tables (SSTables) — Disk

The persistent on-disk files produced by MemTable flushes. An SSTable consists of two primary elements: a sorted, immutable sequence of key-value data blocks and an in-memory sparse index storing the first key of each block along with its byte offset.

The Read and Write Execution Paths

The Write Path (Append-Only Speed)

  1. Append transaction to the Write-Ahead Log (WAL) on disk for durability.
  2. Insert key-value pair into the in-memory sorted MemTable.
  3. Return immediate success acknowledgement to the client (executed in sub-millisecond memory time).
  4. Updates and deletions are handled as appends: updates overwrite by writing a higher timestamped entry; deletions append a special deletion marker called a 'Tombstone'.

The Read Path (Multi-Layer Reconciliation)

  1. Check the active in-memory MemTable (contains the newest data).
  2. Check any flushing Immutable MemTables in RAM.
  3. Check Bloom Filters associated with on-disk SSTables to skip files that definitely do not contain the key.
  4. For remaining candidate SSTables, binary search their sparse index blocks to locate the candidate data block on disk and retrieve the latest record based on timestamp.

SSTable Compaction Strategies

Because flushed SSTables are immutable, multiple files on disk may contain duplicate or obsolete versions of the same key, as well as tombstone markers for deleted records. Over time, this causes disk space bloat and degrades read latency (Read Amplification). Compaction is the background process of merging multiple sorted SSTables into fewer, consolidated sorted files using K-way merge sort.

1. Size-Tiered Compaction

Groups SSTables of similar file sizes together. When a tier accumulates a set number of tables (e.g., 4), they are merged into a single larger SSTable in the next tier. Highly write-optimized with minimal write amplification, but carries higher disk space overhead during merges.

2. Leveled Compaction (RocksDB / LevelDB Default)

Organizes disk storage into exponential levels (L0, L1, L2...). Except for L0, all SSTables within a given level have strictly non-overlapping key ranges. When level L_i reaches capacity, one file is merged into overlapping files in level L_{i+1}. This provides predictable, bounded read amplification and optimal disk space utilization.

LSM-Tree vs. B+ Tree: Core Trade-Offs

  • Write Throughput: LSM-Trees significantly outperform B+ Trees on write workloads by eliminating random disk writes.
  • Read Latency: B+ Trees provide faster and more predictable point read latencies since keys reside at a single known leaf page without checking multiple SSTable layers.
  • Space Amplification: LSM-Trees achieve higher disk compression ratios because SSTable blocks are immutable and can be densely packed and compressed with algorithms like ZSTD/Snappy without internal fragmentation.
  • Write Amplification: Background compaction in LSM-Trees rewrites data across levels, requiring careful tuning of I/O budgets to prevent write stalls.

Real-World Distributed and Storage Systems

  1. Embedded Storage Engines: RocksDB (Meta), LevelDB (Google), and BadgerDB (Go) powering distributed key-value microservices.
  2. Distributed NoSQL Databases: Apache Cassandra, ScyllaDB, and Google Cloud Bigtable managing multi-terabyte analytical and time-series workloads.
  3. Modern Analytical OLAP Engines: ClickHouse and DuckDB write-buffers utilizing merge-tree variations for fast columnar batch ingestion.
  4. Distributed SQL Engines: CockroachDB and TiDB using RocksDB as their underlying distributed storage layer.