Lab 06 — Compaction and K-way Merge

• What this lab adds
• Concept: The read-amplification problem
• Concept: K-way merge with a min-heap
• nodeHeap: Go container/heap integration
• MergedIterator: annotated implementation
  • next() step-by-step
  • Deduplication proof
  • Tombstone proof
• Deduplication traced: 3 versions of “name”
• Tombstone traced: Delete(“color”) after Put(“color”,“red”)
• compact() execution trace
• Space and write amplification analysis
  • Space amplification (during compaction)
  • Write amplification (per level)
  • K-way merge complexity proof
• Running the tests
  • TestCompactionDeduplicates walkthrough
  • TestTombstoneNotVisible
• Running the demo
• FoundationDB parallel

What this lab adds

Lab 05 continuously produces L0 SSTable files. Without compaction, Get must search all of them, and disk usage grows without bound (old deleted keys are never reclaimed). Lab 06 adds:

1. MergedIterator — a min-heap–based K-way merge that combines multiple sorted iterators (MemTable and/or SSTable) into one globally-sorted, deduplicated, tombstone-respecting stream.
2. compact() — triggered when L0 reaches 4 files: merges all L0 files + existing L1 files into new non-overlapping L1 SSTables, then atomically updates the MANIFEST.
3. NewIterator() — full-database range scan via a MergedIterator over all live data.

Concept: The read-amplification problem

After 4 MemTable flushes, there are 4 L0 SSTables. Every Get("apple") must open and search all 4 files — 4 random reads — because L0 files can have overlapping key ranges:

L0 (newest → oldest):
  000008.sst: contains apple@seq=30 ("yellow"), date@seq=29
  000006.sst: contains apple@seq=20 ("green"),  age@seq=19
  000004.sst: contains apple@seq=10 ("red"),    name@seq=9
  000002.sst: contains apple@seq=1  ("blue"),   zip@seq=1

The correct answer for Get("apple") is "yellow" (seq=30), found in the newest L0 file. But the engine doesn’t know which file contains the answer, so it searches all 4 — worst-case O(K) reads per Get.

Compaction solves this by merging all L0 files into a set of L1 files with non-overlapping key ranges:

L1 (after compaction, non-overlapping):
  000010.sst: age, apple (one winner: "yellow" at seq=30)
  000011.sst: date, name
  000012.sst: zip

Now Get("apple") is a binary search over L1 file boundary keys → exactly 1 file to open → O(1) disk reads.

Concept: K-way merge with a min-heap

Merging K sorted sequences requires finding the global minimum at each step. Naively, comparing the current-front element of each sequence takes O(K) per step, giving O(NK) total for N elements. A min-heap reduces this to O(N log K):

Step 1: Push the first element of each of K sequences into the heap.
         Heap size = K.  Cost: O(K log K) to build.

Step 2: Repeat until all sequences are exhausted:
  a. Pop the minimum element.  Cost: O(log K).
  b. Advance that sequence.  Push its next element (if any).  Cost: O(log K).
  c. Process the popped element (deduplication, tombstone check).

Total: N steps × O(log K) = O(N log K).

For K=4 (our compaction trigger) and N=200,000 records (4 × 50K):

• O(N log K) = 200,000 × log₂(4) = 400,000 comparisons
• vs O(NK) = 200,000 × 4 = 800,000 comparisons

The heap halves the work at K=4 and the advantage grows as K increases.

nodeHeap: Go container/heap integration

Go’s container/heap package provides heap.Push, heap.Pop, and heap.Init but delegates actual storage and comparisons to a user-supplied type that implements the heap.Interface:

type heapNode struct {
    src   rawIter  // the source iterator for this element
    key   []byte
    value []byte
}

type nodeHeap []heapNode

// Len, Less, Swap: required by sort.Interface (embedded in heap.Interface)
func (h nodeHeap) Len() int  { return len(h) }
func (h nodeHeap) Less(i, j int) bool {
    return lab02.CompareInternal(h[i].key, h[j].key) < 0
}
func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

// Push: heap.Push calls this with the new element already appended.
func (h *nodeHeap) Push(x any) { *h = append(*h, x.(heapNode)) }

// Pop: heap.Pop calls this to remove the minimum (already at index len-1).
func (h *nodeHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

heap.Pop first swaps h[0] (the minimum) with h[len-1], calls down to restore the heap property on the remaining n-1 elements, then calls our Pop() to extract h[len-1]. The result is always the globally smallest element across all K sequences — proved by the min-heap invariant: h[i] ≤ h[2i+1] and h[i] ≤ h[2i+2] for all i.

MergedIterator: annotated implementation

type MergedIterator struct {
    h           nodeHeap
    key, value  []byte
    valid        bool
    readSeq      uint64    // MVCC visibility cutoff
    lastUserKey  []byte    // for deduplication
}

func NewMergedIterator(sources []rawIter, readSeq uint64) *MergedIterator {
    m := &MergedIterator{readSeq: readSeq}
    // Seed the heap with the first element from each valid source:
    for _, src := range sources {
        if src.Valid() {
            heap.Push(&m.h, heapNode{src: src, key: src.Key(), value: src.Value()})
        }
    }
    m.next()   // advance to the first visible record
    return m
}

next() step-by-step

func (m *MergedIterator) next() {
    for len(m.h) > 0 {
        // 1. Pop the globally smallest internal key:
        node := heap.Pop(&m.h).(heapNode)

        // 2. Advance that source and re-push its next element:
        node.src.Next()
        if node.src.Valid() {
            heap.Push(&m.h, heapNode{
                src:   node.src,
                key:   node.src.Key(),
                value: node.src.Value(),
            })
        }

        // 3. Extract seqNum and keyType from the last 8 bytes of the internal key:
        ikey := node.key
        tag := binary.LittleEndian.Uint64(ikey[len(ikey)-8:])
        seqNum := tag >> 8
        kt := keyType(tag & 0xff)
        userKey := ikey[:len(ikey)-8]

        // 4. Skip records beyond the snapshot horizon:
        if seqNum > m.readSeq {
            continue
        }

        // 5. Skip older versions of already-emitted user keys:
        if bytes.Equal(userKey, m.lastUserKey) {
            continue
        }
        // Record this user key so subsequent versions are skipped:
        m.lastUserKey = append(m.lastUserKey[:0], userKey...)

        // 6. Skip tombstones (the key was deleted at this seqNum):
        if kt == typeDelete {
            continue   // tombstone suppresses all older versions too
        }

        // 7. Emit this record:
        m.key = userKey
        m.value = node.value
        m.valid = true
        return
    }
    m.valid = false   // all sources exhausted
}

Deduplication proof

Because CompareInternal sorts by (userKey ASC, seqNum DESC), all versions of “apple” are adjacent in the merged stream, with the highest seqNum first. When next() pops the first “apple” entry (highest seqNum ≤ readSeq), it records lastUserKey = "apple". All subsequent “apple” entries are popped in order and hit the bytes.Equal(userKey, m.lastUserKey) check — skipped.

This ensures each user key is emitted at most once, with the latest visible version.

Tombstone proof

If Delete("k") was written at seqNum=50 and Put("k","v") was written at seqNum=10, the merged stream yields:

• ("k", seq=50, TypeDelete, "") ← popped first (50 > 10)

next() records lastUserKey = "k", then hits kt == typeDelete → continue. The next iteration pops ("k", seq=10, TypeValue, "v"), but it hits the lastUserKey == "k" guard → skipped. The iterator moves past all “k” entries without ever emitting a value — the deletion is correctly visible.

Deduplication traced: 3 versions of “name”

Sources (each is a sorted iterator):
  src0 (MemTable):  ("name", seq=30, TypeValue, "Charlie")
  src1 (L0 file):   ("name", seq=20, TypeValue, "Bob")
  src2 (L0 file):   ("name", seq=10, TypeValue, "Alice")

readSeq = 30

Initial heap:
  [("name",30), ("name",20), ("name",10)]
  After heapify: h[0] = ("name",30) is smallest (seqNum DESC → 30 = lowest tag)

Step 1:
  Pop ("name",30): src0 exhausted; advance src0 → nothing to push.
  seqNum=30 ≤ readSeq=30: pass visibility check.
  lastUserKey was "": not equal to "name": pass dedup check.
  kt=TypeValue: pass tombstone check.
  Emit: key="name", value="Charlie"
  lastUserKey = "name"

Step 2:
  Pop ("name",20): src1 advanced; no more elements from src1.
  seqNum=20 ≤ readSeq=30: pass visibility check.
  lastUserKey = "name" == "name": SKIP (step 5)

Step 3:
  Pop ("name",10): src2 advanced; no more elements.
  lastUserKey = "name" == "name": SKIP

Heap empty. done.
Final output: key="name", value="Charlie" (only the newest version)

Tombstone traced: Delete(“color”) after Put(“color”,“red”)

Sources:
  src0: ("color", seq=25, TypeDelete, "")
  src1: ("color", seq=15, TypeValue,  "red")

readSeq = 30

Step 1:
  Pop ("color",25): seqNum=25 ≤ 30 ✓; lastUserKey="" ≠ "color" ✓
  kt=TypeDelete → continue  (tombstone! suppress and advance)
  lastUserKey = "color"

Step 2:
  Pop ("color",15): seqNum=15 ≤ 30 ✓; lastUserKey="color" == "color" → SKIP

Heap empty. MergedIterator sees no "color" record.

This is the tombstone cascade: the delete at seq=25 acts as a sentinel, and the dedup guard silently drops all older values in a single pass.

compact() execution trace

Triggered when len(Levels[0]) >= CompactL0Trigger (4 files):

func (db *DB) compact() {
    // 1. Snapshot L0+L1 under lock:
    db.mu.Lock()
    l0 := append([]string{}, db.manifest.Levels[0]...)
    l1 := append([]string{}, db.manifest.Levels[1]...)
    readSeq := db.seqNum
    db.mu.Unlock()   // lock released; I/O runs concurrently with writes

    allFiles := append(l0, l1...)

    // 2. Open all readers:
    var sources []rawIter
    for _, path := range allFiles {
        r, _ := lab04.Open(path)
        sources = append(sources, &sstIterAdapter{r.NewIterator()})
    }

    // 3. K-way merge:
    merged := NewMergedIterator(sources, readSeq)

    // 4. Write new L1 files (split at L1SplitSize = 2 MiB):
    var newL1 []string
    var bld *lab04.Builder
    var curSize int64

    for merged.Valid() {
        if bld == nil || curSize >= L1SplitSize {
            // Close current builder (if any) and open a new one:
            if bld != nil { bld.Finish(); bld.Close(); newL1 = append(newL1, curPath) }
            curPath = fmt.Sprintf("%s/%06d.sst", db.dir, db.nextFileNum.Add(1))
            bld, _ = lab04.NewBuilder(curPath)
            curSize = 0
        }
        bld.Add(merged.Key(), merged.Value())
        curSize += int64(len(merged.Key()) + len(merged.Value()))
        merged.Next()
    }
    if bld != nil { bld.Finish(); bld.Close(); newL1 = append(newL1, curPath) }

    // 5. Atomically update manifest:
    db.mu.Lock()
    db.manifest.replaceFiles(0, l0, nil)    // clear L0
    db.manifest.replaceFiles(1, l1, newL1)  // replace old L1 with new L1
    db.manifest.NextSeq = db.seqNum
    db.manifest.Save()
    db.mu.Unlock()

    // 6. Delete old files:
    for _, path := range allFiles { os.Remove(path) }
}

Why is I/O outside the lock? The SSTable write for 4 × 4 MiB = 16 MiB of input data may take 16–100 ms on an HDD. Holding db.mu for that duration would block every Put and Get for 100 ms — unacceptable. The merged stream reads from files that are still referenced in the manifest (not yet deleted), so reads are safe. New writes go to the new db.mem, unaffected by compaction.

Non-overlap guarantee: The merged stream yields keys in globally sorted order (proven by the heap invariant). The L1 files are written in the order keys appear in that stream. Each file starts where the previous one ended. Therefore, the key ranges of the resulting L1 files are non-overlapping and cover the entire compacted keyspace.

Space and write amplification analysis

Space amplification (during compaction)

At peak — while the new L1 files are being written but before the old L0 files are deleted — both sets exist simultaneously:

Before: L0 = 4 × 4 MiB = 16 MiB, L1 = varies
During: L0 (16 MiB) + new L1 being built (up to 16 MiB) = 32 MiB peak
After:  L0 deleted, new L1 = ~16 MiB (deduplicated)

Peak space amplification ≈ 2×. If the working set is W MiB, we need 2W MiB disk space to be safe during compaction.

Write amplification (per level)

Each value is written once to the MemTable (in-memory, “free”), once to L0 during flush, and once to L1 during compaction. That is 2 disk writes per value. In a full multi-level engine (5 levels), a key might be rewritten at each level: write amplification ≈ L (number of levels). For L=5 on RocksDB: WA ≈ 10–30× depending on compaction strategy. Our 2-level engine achieves WA = 2×.

Proof that WA = 2 for our engine:

Write path: Put("k","v") at seqNum=N
  1. WAL (lab01): 1 write (can amortize; WAL is sequential and large)
  2. MemTable: in-memory, no disk write
  3. Flush to L0: 1 disk write (the SSTable record)
  4. Compaction L0→L1: 1 disk write (the new L1 SSTable record)
     Old L0 record is deleted.
Total disk writes per logical Put: 2 (L0 + L1)

K-way merge complexity proof

For N total records across K sources and a binary heap of size K:

• Building the heap: O(K) by heapify, or O(K log K) by K insertions
• Per record: 1 pop + (0 or 1) pushes = 2 heap operations × O(log K) = O(log K)
• Total: O(N log K)

For N=200,000, K=5 (4 L0 + 1 L1 iterator):

• O(N log K) = 200,000 × log₂(5) ≈ 200,000 × 2.32 ≈ 464,000 operations
• O(N) = 200,000 (lower bound: must read every record)
• Overhead of the heap: ~2.3× the minimum, negligible in practice

Running the tests

cd leveldb
go test ./lab06/... -v -count=1

Expected output:

=== RUN   TestMergedIterator
--- PASS: TestMergedIterator (0.00s)
=== RUN   TestCompactionDeduplicates
--- PASS: TestCompactionDeduplicates (0.21s)
=== RUN   TestTombstoneNotVisible
--- PASS: TestTombstoneNotVisible (0.08s)
=== RUN   TestNewIterator
--- PASS: TestNewIterator (0.06s)
PASS
ok      github.com/10xdev/leveldb/lab06

TestCompactionDeduplicates walkthrough

1. Write 3 versions of “apple” across 3 separate flushes (each flush > threshold).
2. Wait for the 4th flush (or trigger manually) which causes compaction.
3. After compaction, Get("apple") returns only the newest version.
4. Open all L1 SSTable files directly and verify each user key appears exactly once — no duplicate versions survive in L1.

TestTombstoneNotVisible

1. Put("ghost","value") → flush.
2. Delete("ghost") → flush.
3. Trigger compaction.
4. Get("ghost") returns (nil, false).
5. Scan the L1 files directly — “ghost” appears 0 times (both the value and tombstone were dropped by the compaction’s merged iterator).

Running the demo

go run ./lab06/demo

Expected output:

wrote 8000 records across multiple flushes
L0 files after flush: 4
compaction triggered…
L1 files after compaction: 4
L0 files after compaction: 0
iterating all records…
records seen: 8000 (0 duplicates)

FoundationDB parallel

FDB’s compaction equivalent is the storage server’s data distribution and shard splits/merges. When a shard (key range) grows beyond a target size (~100 MB in production), the data distributor splits it into two shards, each with non-overlapping key ranges — exactly the L1 non-overlap guarantee we achieve via K-way merge + sequential write.

FDB does not use a leveled compaction tree like LevelDB. Instead, it uses a B-tree (or in newer FDB versions, a Redwood B+-tree) within each storage server, with copy-on-write pages. The equivalent of our K-way merge happens during background page compaction when multiple versions of a key exist on the same page: old MVCC versions are garbage-collected, similar to our tombstone suppression.

The K-way merge algorithm itself appears in FDB’s transaction log recovery: each log server holds a prefix of the write history; recovery reads from all log servers simultaneously (K sources) and merges them in seqNum order — exactly NewMergedIterator(sources, maxReadSeq).