LSM-Tree: Insertions, Deletions, and Tombstones

Hello! Welcome back to our exploration of write-optimized storage engines.

In our previous lesson, you learned about the high-level architecture of the Log-Structured Merge-Tree (LSM-Tree). We covered its core components: the in-memory Memtable for buffering writes, the on-disk SSTables that store immutable data, the Write-Ahead Log (WAL) for durability, and the multi-level structure maintained by a compaction process.

Today, we'll dive deeper into the operational mechanics. Your learning outcome is to implement insertions and deletions (using tombstones) in an LSM-Tree. We'll examine how these fundamental database operations are handled in a system where data on disk is never modified in place. This will give you a clear, engineering-focused view of how LSM-Trees achieve their impressive write performance.

1. Handling Insertions and Updates

In an LSM-Tree, both new data insertions and updates to existing data are handled by the same PUT operation. The process is designed to be extremely fast by converting all writes into sequential appends.

The flow of a PUT operation is as follows:

Log: The operation (e.g., PUT(key, value)) is first appended to the Write-Ahead Log (WAL) on disk. This is a sequential write and ensures that the operation won't be lost if the server crashes before the data is persisted in an SSTable.
Memtable: The key-value pair is then inserted into the in-memory Memtable. Since the Memtable is a sorted data structure (like a skip list or B-tree), this operation is very fast.

What if the key already exists in the Memtable? The new value simply overwrites the old one. Because this happens in memory, it's an inexpensive operation. This is how "updates" are handled—they are treated as new insertions that supersede previous versions.

When the Memtable becomes full, it is flushed to disk as a new, immutable SSTable. The following video provides a great walkthrough of this entire process.

#04 - Database Storage: Log-Structured Merge Trees & Tuples (CMU Intro to Database Systems)

Let's revisit the CMU Database Systems lecture series. This segment visualizes how put operations are handled in the Memtable and how a full Memtable is converted into an on-disk SSTable.

Watch from 25:59 to 34:01. Focus on: How new key-value pairs are added to the Memtable. How an update to an existing key (like key 101) is handled as an in-place update within the Memtable. The process of sorting and flushing the Memtable's contents into a new SSTable at Level 0.

As the video shows, the system doesn't differentiate between an "insert" and an "update." It just writes the new data. The most recent version of a key is always the one found first when searching from the newest component (Memtable) to the oldest (lowest-level SSTables).

From an implementation perspective, a single Set method in your Memtable data structure can handle insertions, updates, and even deletions, which we'll cover next.

Building an LSM-Tree Storage Engine from Scratch

This technical blog post, 'Building an LSM-Tree Storage Engine from Scratch,' provides Go code snippets that demonstrate how to implement these operations. Since you're proficient in C++/Java, the Go code should be quite readable.

Find the implementation section and read the subsections for 'Memtable' -> 'Set' and 'Skip List' -> 'Set'. Notice how the same Set function is used to handle both creating a new key and updating the value of an existing one.

2. Handling Deletions with Tombstones

Now for the tricky part: how do you delete a key in a system built on immutable files? You can't just find the key on disk and remove it. The solution is to use a special marker called a tombstone.

A tombstone is a record that indicates a key has been deleted. Instead of removing data, a DELETE operation writes a new entry—the tombstone—for that key.

LSM Tree + SSTable Database Indexes | Systems Design Interview: 0 to 1 with Google Software Engineer

This short video provides a very clear and concise explanation of how tombstones work in an LSM-Tree.

Watch from 05:57 to 06:40. Pay attention to how a tombstone in a more recent SSTable effectively hides the value in an older SSTable.

The process for a DELETE operation mirrors a PUT:

Log: A tombstone record for the key is appended to the WAL.
Memtable: The tombstone is added to the Memtable. This could be a special flag on the entry for that key.

When the system performs a read for a key, if the most recent entry it finds is a tombstone, it reports that the key does not exist. The actual data and the tombstone itself are only physically removed from disk during a future compaction cycle.

This image visualizes the life cycle of a tombstone, from its creation in the memtable to its propagation during compaction, which ultimately cleans up the old data.

Deletes in LSM-Trees using Tombstones — This diagram shows the three steps of deletion. First, a tombstone for key '6' (6\*) is written to the memtable. Second, during compaction, the tombstone is flushed to disk, shadowing and allowing for the removal of the old data for key '6'. Third, after further compaction, both the old data and the tombstone are gone.

The Danger of Data Resurrection

A critical challenge when implementing tombstones is avoiding a bug known as data resurrection. This happens if a tombstone is removed prematurely during compaction. If an older version of the data still exists in a lower level of the tree, that "deleted" data can reappear.

Build Your Own Key-Value Storage Engine—Week 4

The technical blog 'Build Your Own Key-Value Storage Engine' has an excellent, practical discussion of tombstones and the data resurrection problem. This is exactly the kind of systems-level detail that engineers must get right.

Read the first part of the article, down to the 'Your Tasks' section. Focus on the example that shows how compacting SST-3 and SST-4 can lead to data resurrection if the tombstone is dropped too early. Understand the fundamental rule: 'a tombstone can be evicted only after all data it shadows no longer exist on disk.'

3. Implementation Walkthrough

Now, let's bring it all together from an implementation standpoint. How would you modify a key-value store to handle insertions and deletions in an LSM-Tree? The following resource provides a set of concrete tasks.

Build Your Own Key-Value Storage Engine—Week 4

Let's continue with the same blog post, which lays out a clear plan for implementing these features.

Read the sections under 'Your Tasks': 'DELETE Endpoint', 'Flush', 'Compaction', and 'GET'. These sections provide a step-by-step guide on how to: Implement a DELETE API endpoint by writing a tombstone. Ensure tombstones are carried into new SSTables during a flush. Modify the compaction algorithm to correctly handle and eventually discard tombstones. Update the GET logic to respect tombstones.

This guide gives you a blueprint for the logic required.

The DELETE endpoint is straightforward: log the tombstone and add it to the memtable.
The GET logic is also clear: check the memtable first, then scan SSTables from newest to oldest. If you find a tombstone first, the key is deleted. If you find a value first, return it.
The most complex logic lies in compaction. The k-way merge algorithm must be aware of tombstones to ensure it only keeps the newest version of a key and correctly decides when a tombstone can finally be discarded.

Test your understanding!

Suppose your LSM-Tree has the following state:

Memtable: Empty
Level 1 SSTable: Contains (key="X", value="v1")
Level 2 SSTable: Contains (key="X", value="v0")

You then execute the command DELETE("X"). Describe the state of the system:

Immediately after the DELETE command completes.
After the Memtable is flushed to a new SSTable at Level 0.
After a full compaction merges all SSTables from all levels into a single new SSTable.

Show answer

Immediately after DELETE("X"):
- The Memtable will contain a tombstone record for key "X", like (key="X", tombstone=true).
- The WAL will have a corresponding DELETE entry.
- The SSTables at Level 1 and Level 2 remain unchanged. A GET("X") request at this point would find the tombstone in the memtable and return "Not Found".
After Memtable flush:
- The Memtable becomes empty.
- A new Level 0 SSTable is created containing (key="X", tombstone=true).
- Level 1 and Level 2 SSTables are still unchanged.
After full compaction:
- The compaction process will perform a merge on the SSTables from Levels 0, 1, and 2.
- For key "X", it sees three versions: the tombstone (newest), v1 (middle), and v0 (oldest).
- The merge logic keeps only the newest version, which is the tombstone.
- Because the tombstone now "shadows" all existing versions of the key, the compaction algorithm can safely discard all entries for key "X".
- The final, compacted SSTable will contain no entry for key "X". The key and its history have been physically deleted.

Conclusion

In this lesson, we moved from the high-level architecture of LSM-Trees to the concrete implementation of its core write operations. You now have a practical understanding of how inserts, updates, and deletes are managed in a write-optimized, immutable storage system.

Key Takeaways:

Inserts and Updates are both handled by a PUT operation, which writes the new key-value pair to the WAL and the in-memory Memtable. The latest write always wins.
Deletions are handled by writing a tombstone, a special marker that logically deletes a key without modifying on-disk files.
When reading, a tombstone masks any older versions of the data in lower levels of the tree.
During compaction, tombstones are propagated downwards. A tombstone and the data it shadows can only be physically garbage collected when no older versions of the data exist at deeper levels, preventing data resurrection.

Preview of the Next Lesson

The compaction process is clearly central to the performance and correctness of an LSM-Tree. In our next lesson, we will delve into the details of this crucial background process by learning to describe and compare tiered versus leveled compaction strategies. You will see how different approaches to compaction create different trade-offs between write amplification, read amplification, and space usage.