Compaction: Merging SSTables

Merge SSTables to Reclaim Space

Repeated flushes create overlapping SSTables. Compaction merges sorted runs, dropping tombstoned keys and reducing read amplification. Size-tiered compaction merges files of similar size; leveled compaction organizes into levels with non-overlap invariants.

Two-Way Merge

Open iterators on two sorted SSTables, compare keys, emit smaller, handle duplicates by keeping newest.

c
Loading…

Compaction IO dominates LSM write amplification
Tombstones must survive until no older version exists
Background threads compact while serving reads from old files
Monitor pending compaction bytes in production systems

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will merge two SSTable files into one sorted output, resolving duplicate keys. This exercise requires keeping the newest value for colliding keys.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Write a C program that implements size-tiered compaction by merging two SSTables.

Requirements:

Define two input arrays representing SSTables (sorted by key): SSTable A: (1,10), (3,30), (5,50), (7,70), (10,100) SSTable B: (2,20), (3,35), (6,60), (8,80), (10,110)
Implement merge_sstables() that:
- Merges both inputs in sorted order (like merge sort)
- When the same key appears in both, keep the value from B (newer SSTable wins)
- Removes tombstones (key=-1 means deleted; do not include in output)
Print the input SSTables
Print the merged SSTable
Calculate and print:
- Input total key-value pairs: 10
- Output total key-value pairs (should be 8: 3 appears once, 10 uses B's value)
- Write amplification: output pairs / input unique keys
- Space reclaimed: input pairs - output pairs
Simulate adding a tombstone: key=5 with value=-1 in SSTable B, show it is removed during compaction
Include a note about why leveled compaction has better read amplification

Merge SSTables to Reclaim Space

Two-Way Merge

Open iterators on two sorted SSTables, compare keys, emit smaller, handle duplicates by keeping newest.

c
Loading…

Compaction IO dominates LSM write amplification
Tombstones must survive until no older version exists
Background threads compact while serving reads from old files
Monitor pending compaction bytes in production systems

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will merge two SSTable files into one sorted output, resolving duplicate keys. This exercise requires keeping the newest value for colliding keys.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Write a C program that implements size-tiered compaction by merging two SSTables.

Requirements:

Define two input arrays representing SSTables (sorted by key): SSTable A: (1,10), (3,30), (5,50), (7,70), (10,100) SSTable B: (2,20), (3,35), (6,60), (8,80), (10,110)
Implement merge_sstables() that:
- Merges both inputs in sorted order (like merge sort)
- When the same key appears in both, keep the value from B (newer SSTable wins)
- Removes tombstones (key=-1 means deleted; do not include in output)
Print the input SSTables
Print the merged SSTable
Calculate and print:
- Input total key-value pairs: 10
- Output total key-value pairs (should be 8: 3 appears once, 10 uses B's value)
- Write amplification: output pairs / input unique keys
- Space reclaimed: input pairs - output pairs
Simulate adding a tombstone: key=5 with value=-1 in SSTable B, show it is removed during compaction
Include a note about why leveled compaction has better read amplification

Topic Overview

Merge SSTables to Reclaim Space

Two-Way Merge

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Compaction: Merging SSTables

Topic Overview

Merge SSTables to Reclaim Space

Two-Way Merge

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source