LSM-Tree Architecture: Memtables and On-Disk Levels

1. The Problem: The High Cost of In-Place Updates

Traditional database storage engines, often based on B+ Trees, perform in-place updates. When you update a record, the system finds the specific page on disk where the record lives and modifies it directly. While this is efficient for reads (since a record has one canonical location), it involves random I/O operations. On traditional Hard Disk Drives (HDDs), random seeks are extremely slow. On modern Solid-State Drives (SSDs), while much faster, random writes are still less efficient than sequential writes and contribute to "write wear," which can shorten the drive's lifespan.

LSM-Trees were designed to solve this very problem by avoiding in-place updates entirely. The core idea is simple: all modifications are buffered in memory and written to disk sequentially in batches.

2. The LSM-Tree Architecture: A Bird's-Eye View

At its heart, an LSM-Tree is a collection of data structures spread across main memory (RAM) and disk. Let's start with a high-level architectural diagram that we'll refer back to throughout this lesson.

As you can see, the architecture has two main arenas: RAM and Disk. Data flows from RAM to disk as it ages. Let's break down each component.

3. In-Memory Component: The Memtable

All incoming write requests (inserts, updates, and even deletes) are first sent to an in-memory data structure called the Memtable.

Because the Memtable lives entirely in RAM, writing to it is extremely fast—it's just a memory operation. This is the key to the high write throughput of LSM-Trees.

As the article explains, the Memtable isn't just a simple buffer. It's typically a sorted data structure (like a Skip List or a Red-Black Tree). Keeping the data sorted in memory is crucial for the next step of the process.

Durability and the Write-Ahead Log (WAL)

Since the Memtable is in volatile RAM, what happens if the system crashes? All the recent writes would be lost. To prevent this, LSM-Trees use a Write-Ahead Log (WAL).

Before a write operation is added to the Memtable, it is first appended to a log file on disk. This disk write is sequential and therefore very fast. If the system crashes, it can restore the contents of the Memtable by replaying the operations from the WAL.

The blog post you just looked at has another excellent section explaining this.

4. On-Disk Components: SSTables and Levels

The Memtable has a fixed size. Once it becomes full, the database needs to make room for new incoming writes. To do this, the current Memtable is "frozen" (made immutable), a new empty Memtable is created to accept new writes, and the contents of the full, immutable Memtable are flushed to disk.

The on-disk file created from this flush is called an SSTable (Sorted String Table). Because the data in the Memtable was already sorted by key, creating the SSTable is a highly efficient, single-pass sequential write to disk. These SSTables are immutable—once written, they are never modified.

The following video from CMU's Intro to Database Systems course explains this process visually.

As the video illustrates, over time, the system will accumulate many SSTables on disk. If a read request comes in, the database would have to check the Memtable, and then potentially every single SSTable on disk to find the latest version of a key. This would be very slow.

To manage this, SSTables are organized into levels.

• Newly flushed SSTables from the Memtable are typically placed in Level 0.
• As a level fills up with too many SSTables, a background process called compaction kicks in.
• Compaction merges several SSTables from one level (e.g., Level i) into a new, larger SSTable in the next level (e.g., Level i+1). This process also purges old or deleted data.

This hierarchical, leveled structure is the "Merge-Tree" part of the name. Each level is typically exponentially larger than the one before it. For example, Level 1 might be 10MB, Level 2 100MB, Level 3 1GB, and so on.

Let's watch another segment from the same video that focuses on the compaction process.

5. Summary of Operating Principles and Trade-offs

We can summarize the architecture of an LSM-Tree through a few key operating principles, as laid out in the research paper "Dissecting, Designing, and Optimizing LSM-based Data Stores":

• Batched Ingestion: Writes are buffered in the in-memory Memtable.
• Out-of-Place Updates: Updates and deletes are handled as new entries, not by modifying existing data on disk. A delete is often recorded as a special entry called a "tombstone."
• Immutable File Structure: SSTables on disk are never changed once written.
• Periodic Compaction: A background process merges SSTables across levels to bound read costs and reclaim space.

This design presents a fundamental trade-off.

• Writes are very fast (sequential I/O).
• Reads can be slower because the system might have to check the Memtable and multiple SSTables across several levels to find the latest version of a key.

A major engineering consideration is write amplification: a single logical update from the client can result in the same data being physically written to disk multiple times as it gets compacted down through the levels. This has cost implications for cloud storage and impacts the lifespan of SSDs.

Conclusion

In this lesson, we've dissected the fundamental architecture of the Log-Structured Merge-Tree. You now understand how it achieves high write throughput by transforming random writes into sequential ones.

Key Takeaways:

• LSM-Trees are optimized for write-heavy workloads by avoiding in-place updates.
• Writes are buffered in an in-memory sorted structure called the Memtable and made durable via a Write-Ahead Log (WAL).
• When the Memtable is full, it's flushed to disk as an immutable, sorted file called an SSTable.
• SSTables are organized into multiple on-disk levels, with each level being progressively larger.
• A background compaction process merges SSTables from upper levels into lower levels to control the number of files and clean up old data, which is crucial for maintaining read performance.

Preview of the Next Lesson

Now that you understand the high-level architecture, we will zoom in on the operational details. In the next lesson, we will focus on how to implement insertions and deletions (using tombstones) within this structure, laying the groundwork for understanding how queries are actually executed.