LSM Trees: Memtables, Immutable Sorted Files, Write Amplification, and Read Amplification

Learning outcomes

AtlasMart telemetry accepts bursts of writes faster than a single page-oriented update path can comfortably absorb. An LSM-style storage engine changes the shape of the work: append recovery information, update an ordered in-memory memtable, flush immutable sorted files, and later compact them. Fast foreground writes therefore create background obligations rather than eliminating storage cost.

1. The LSM write path converts random update pressure into append/batch work

A Log-Structured Merge (LSM) tree maintains recent writes in memory and periodically flushes them as immutable sorted runs. A common path is: append to a recovery log; update a memtable; acknowledge according to durability policy; freeze the memtable when a threshold is reached; write it as an immutable SSTable (sorted-string-table style file); then compact files in the background.

Because flushed files are immutable, updating sku-1 does not necessarily rewrite its older on-disk file immediately. Newer versions can coexist across runs until compaction. That improves foreground write locality but introduces version search and background merge work.

2. Reads must reconcile recency across several possible locations

A point read typically checks the mutable memtable, immutable memtables waiting to flush, and candidate SSTables from newest to oldest or according to level metadata. Index blocks/key ranges can rule out files; Bloom filters can cheaply say “definitely not here” for many absent keys; block caches avoid repeated device reads. Yet a miss can still probe multiple candidates, especially when many overlapping runs exist.

Read amplification is the extra physical lookup/read work required per logical read. It is not simply “number of SSTables,” because filters, indexes, cache hits, compression blocks, and storage layout matter.

3. Flushes and compaction create write and space amplification

Flushing writes logical data once into an SSTable; later compactions may rewrite it multiple times. Write amplification compares physical bytes written with logical bytes accepted. Space amplification compares physical footprint with live logical data, including stale versions, tombstones, temporary compaction outputs, indexes, filters, and metadata.

Leveled strategies generally constrain overlap to improve reads/space at the cost of more rewriting; tiered/universal strategies can reduce some rewrite pressure while retaining more overlapping runs. Exact behavior is product-specific and configuration-sensitive.

4. Wrong approach: disable compaction because it “steals I/O”

Turning off or starving compaction can briefly raise foreground write throughput, but the debt accumulates: more files overlap, misses inspect more candidates, stale versions consume space, deletion reclamation stalls, and eventually the engine may throttle/stall writes to protect itself. The apparent optimization moves cost into the future and often worsens tail latency.

The safe response is to measure incoming write rate versus sustainable flush+compaction throughput, file counts by level/tier, compaction backlog, bytes rewritten, cache/filter effectiveness, and storage headroom. Rate-limit or scale background work before the debt becomes an incident.

5. AtlasMart lab — memtable flush, overlapping runs, and compaction

class ToyLSM:
    def __init__(self, flush_limit=3):
        self.flush_limit = flush_limit
        self.wal = []
        self.mem = {}
        self.sstables = []  # oldest -> newest
        self.flush_entries_written = 0
        self.compaction_entries_written = 0

    def put(self, key, value):
        self.wal.append((key, value))
        self.mem[key] = value
        if len(self.mem) >= self.flush_limit:
            self.flush()

    def flush(self):
        if not self.mem:
            return
        run = dict(sorted(self.mem.items()))
        self.sstables.append(run)
        self.flush_entries_written += len(run)
        self.mem.clear()

    def get(self, key):
        probes = 0
        if key in self.mem:
            return self.mem[key], probes, "memtable"
        for i, run in enumerate(reversed(self.sstables), start=1):
            probes += 1
            if key in run:
                return run[key], probes, f"sstable-newest-{i}"
        return None, probes, "absent"

    def compact_all(self):
        merged = {}
        for run in self.sstables:
            merged.update(run)
        self.compaction_entries_written += len(merged)
        self.sstables = [dict(sorted(merged.items()))]

lsm = ToyLSM(flush_limit=3)
for kv in [
    ("sku-1", 10), ("sku-2", 20), ("sku-3", 30),
    ("sku-1", 11), ("sku-4", 40), ("sku-5", 50),
    ("sku-1", 12), ("sku-2", 21), ("sku-6", 60),
]:
    lsm.put(*kv)
lsm.flush()

print("SSTables before compaction:")
for i, run in enumerate(lsm.sstables, 1):
    print(i, run)
print("read sku-1:", lsm.get("sku-1"))
print("read missing sku-99:", lsm.get("sku-99"))
print("flush entries written:", lsm.flush_entries_written)

lsm.compact_all()
print("SSTables after compaction:", lsm.sstables)
print("read missing after compaction:", lsm.get("sku-99"))
print("compaction entries rewritten:", lsm.compaction_entries_written)
print("logical puts:", len(lsm.wal))
print("simple write-amplification numerator:", lsm.flush_entries_written + lsm.compaction_entries_written)

SSTables before compaction:
1 {'sku-1': 10, 'sku-2': 20, 'sku-3': 30}
2 {'sku-1': 11, 'sku-4': 40, 'sku-5': 50}
3 {'sku-1': 12, 'sku-2': 21, 'sku-6': 60}
read sku-1: (12, 1, 'sstable-newest-1')
read missing sku-99: (None, 3, 'absent')
flush entries written: 9
SSTables after compaction: [{'sku-1': 12, 'sku-2': 21, 'sku-3': 30, 'sku-4': 40, 'sku-5': 50, 'sku-6': 60}]
read missing after compaction: (None, 1, 'absent')
compaction entries rewritten: 6
logical puts: 9
simple write-amplification numerator: 15

Interpretation

Before compaction, sku-1 has several historical versions across sorted runs, while an absent lookup checks all runs in this toy model. After compaction, the miss probes one run and only the newest version remains. The cost is the extra entries rewritten during compaction. A real LSM uses file-range metadata, Bloom filters, block indexes, snapshots, sequence numbers, and sophisticated compaction selection, so the simulator is a mechanism map—not a performance model.

6. Production judgment

LSM families are strong candidates for high write rates, append-heavy workloads, and designs where background compaction can be provisioned explicitly. They are not automatically superior for every point read, range scan, delete-heavy workload, or latency SLO. Evaluate amplification under a long-running steady state with realistic key skew and retention—not an empty-database ingest test.

Bridge to Lesson 4: Compaction policy, tombstone lifetime, Bloom-filter behavior, and caches decide much of the real LSM operating envelope. We now make those components—and their failure modes—observable.

Authoritative references

• Apache Cassandra — Storage Engine — current LSM write path, Bloom-filter, SSTable, and compaction overview
• RocksDB Architecture Guide — implementation example of memtable flushes, immutable SST files, and compaction
• RocksDB Compaction — implementation-specific leveled/universal compaction terminology
• The Log-Structured Merge-Tree (LSM-Tree) — foundational O’Neil et al. paper