The Merge Iterator: Range Scans Across Sources

The Merge Iterator: Range Scans Across Sources

A real LSM tree never has just one sorted source — a read might need to see the active memtable, one or more immutable memtables waiting to flush, and dozens of SSTables spread across every level. The merge iterator is what stitches all of those single-source iterators (from the previous lesson) into one logical, sorted, deduplicated view. This is the read-path counterpart to the k-way merge you used for compaction — same algorithm, different purpose: compaction writes the merged result to a new file; a merge iterator serves it live to a query, without ever writing anything.

Snapshots: reading as of a point in time

LSM trees give every write a monotonically increasing sequence number (seq). A snapshot is just a seq value: "show me the database as it looked once writes up to seq had happened, and no later ones." This is what gives you consistent reads even while background compaction and concurrent writes are happening — a long-running range scan pins a snapshot at the start and ignores anything with a higher seq, no matter what mutates underneath it afterward.

visible(entry) := entry.seq <= snapshot

Any entry whose seq is above the snapshot is treated as if it doesn't exist yet.

Merging + snapshot filtering + dedup, together

For a range query [start, end], the merge iterator must, per key:

1. Collect every entry across every source whose key falls in range.
2. Discard entries with seq > snapshot (not yet visible).
3. Among the remaining (visible) versions of that key, keep only the one with the largest seq — the most recent write that's still within the snapshot.
4. If that winning entry is a tombstone, the key is deleted as of this snapshot — skip it entirely from the output.

Notice this is subtly different from plain compaction dedup: compaction always keeps the globally-latest version, but a snapshot-aware read must ignore versions written after the snapshot was taken, even though they're "newer" in absolute terms. A version invisible to this snapshot might still be perfectly visible to a different, later snapshot reading the same data concurrently — that's exactly how MVCC (multi-version concurrency control) lets reads and writes proceed without blocking each other.

Why this matters for correctness, not just style

Get the seq-filtering wrong and you get classic MVCC bugs: a long-running scan that sees a write that happened after the scan started (a "read your future" bug), or — worse — sees a half-applied set of changes from a multi-key transaction because some of its writes landed above the snapshot and some below. The discipline of "filter by seq <= snapshot, then pick max seq among survivors" is what keeps a scan's view internally consistent even as compaction rewrites files underneath it, because compaction itself must preserve any seq that's still visible to an active snapshot (this is why compaction can't safely drop tombstones or old versions if an open snapshot might still need them — a detail you'll meet again later).

Where this plugs into the engine

Structurally, the merge iterator is the same min-heap k-way merge from the compaction lesson, just parameterized by (range, snapshot) instead of running unconditionally to completion. Every read API your LSM tree exposes — point get, range scan, iterator-based cursors — is built by configuring this one component differently.