LSM-Trees vs B+ Trees: MemTables, SSTables, Compaction & RUM Conjecture

The LSM Write/Read Pipeline, Tombstones & Compaction Strategies

Because SSTables on disk are strictly immutable, an LSM-Tree never modifies an existing file in place:

• Updates & Deletions (Tombstones): Updating key $K$ simply appends a newer version (K, v_new, seqNo) to the MemTable. Deleting key $K$ appends a special Tombstone marker (K, TOMBSTONE, seqNo). The obsolete older record is only physically reclaimed later when a background compaction merges the SSTable containing the tombstone with the older SSTable at the bottommost level!
• Point Lookups (MemTable $\to L_0 \to L_1 \dots \to L_k$): To read key $K$, we search the active MemTable, then immutable MemTables awaiting flush, then every overlapping $L_0$ SSTable (because $L_0$ files are raw MemTable flushes whose key ranges overlap!), and finally at most one SSTable per level $L_1 \dots L_k$ (since levels $\ge 1$ are partitioned into non-overlapping key ranges). To avoid reading SSTable blocks from disk for keys that are not present, every SSTable embeds an in-memory Bloom Filter (or Ribbon Filter) and fence-pointer sparse index!

Implementation: LSM Compaction Stream Merger with MVCC Sequence & Tombstone Elision

// C++20: LSM Compaction K-Way Deduplicator & Bottommost-Level Tombstone Elision
#include <vector>
#include <string>

struct LSMRecord {
    std::string key;
    std::string value;
    uint64_t seqNo;     // Monotonically increasing MVCC transaction timestamp
    bool isTombstone;   // True if this record is a DELETE marker
};

// Given sorted records from K merged SSTable runs (ordered by key ASC, then seqNo DESC),
// deduplicates shadowed versions and drops tombstones if compacting into the bottommost level.
std::vector<LSMRecord> compactSortedStream(
    const std::vector<LSMRecord>& mergedStream,
    uint64_t oldestActiveSnapshotSeq,
    bool isBottommostLevel
) {
    std::vector<LSMRecord> output;
    for (size_t i = 0; i < mergedStream.size(); ++i) {
        const auto& rec = mergedStream[i];
        // Skip older versions of the same key if shadowed by a version <= oldestActiveSnapshotSeq
        if (!output.empty() && output.back().key == rec.key &&
            output.back().seqNo <= oldestActiveSnapshotSeq) {
            continue;
        }
        // Physical deletion: only drop a tombstone when it reaches the bottommost level
        // AND no older snapshot can see past it!
        if (rec.isTombstone && isBottommostLevel && rec.seqNo <= oldestActiveSnapshotSeq) {
            continue;
        }
        output.push_back(rec);
    }
    return output;
}