Back
+30 XP
Concept

Capstone Compaction: Background Merge Sort & Tombstone GC

As SSTable segments accumulate on disk, read amplification worsens and obsolete DELETE tombstones consume disk space. The Capstone background compactor performs multi-way merge sorts across aging SSTable files, retaining newest revisions and purging tombstoned records entirely ๐Ÿงน๐Ÿ“ฆโšก.

python
TOMB = "__DEL__"

def merge_compact(old_seg, new_seg):
    # Merge newest over oldest
    combined = {**old_seg, **new_seg}
    # Garbage collect tombstoned keys
    return {k: v for k, v in sorted(combined.items()) if v != TOMB}

s1 = {"k1": "val1", "k2": "val2"}
s2 = {"k2": TOMB, "k3": "val3"}
print("Compacted Table:", merge_compact(s1, s2))

# 115. Capstone Compaction: Background Merge Sort & Tombstone GC In an LSM-Tree storage engine, updates and deletions do not modify existing data blocks on disk. If a user deletes an account, the engine appends a **tombstone** record (`TOMBSTONE = '__DELETED__'`) to the active MemTable and WAL ๐Ÿ›‘. ```python # The Tombstone Necessity: # SSTable 0 (Old): {"user:42": "alice"} # SSTable 1 (New): {"user:42": "__DELETED__"} # # If you didn't write the tombstone to SSTable 1: # When reading "user:42", the engine wouldn't find it in SSTable 1, # fall back to SSTable 0, and resurrect deleted user Alice! ``` ### Background Compaction Mechanics Over time, having dozens of SSTable files creates severe **read amplification** (every read must check multiple files). The background compactor solves this: 1. **Multi-Way Merge Sort**: Merges $N$ sorted files into 1 consolidated segment in $O(N)$ streaming time. 2. **Deduplication**: When the same key appears in multiple segments, only the newest value is retained. 3. **Tombstone Garbage Collection**: If a key contains a tombstone and no older SSTables exist below this compaction level, the key and its tombstone are completely eradicated from disk ๐Ÿงน๐Ÿ“ฆโšก. --- ### Interactive Pop-Quiz ๐Ÿง  #### Why can't a storage engine immediately delete a key from disk when a client issues a DELETE command? - [ ] Because older immutable SSTable files on disk still contain previous versions of that key; without writing a tombstone, older values would reappear during reads ๐Ÿ›‘ - [ ] Because the Linux filesystem prohibits file deletion at runtime - [ ] Because deleted keys must be preserved for TCP protocol compliance - [ ] To allow the CPU to run reverse calculations --- ### Practical Challenge ๐ŸŽฏ Implement `SSTableCompactor.compact(segments_old_to_new: list[dict[str, str]]) -> dict[str, str]`. Process segments in order so newer values overwrite older ones, then discard any keys whose final value equals `TOMBSTONE = '__DELETED__'`. Test with `seg1 = {'a': '1', 'b': '2', 'c': '3'}`, `seg2 = {'b': '20', 'c': '__DELETED__'}`, and `seg3 = {'d': '4'}`. Verify `'b'` is `'20'` and `'c'` is purged. Print results. <details> <summary>Solution</summary> ```python TOMBSTONE = "__DELETED__" class SSTableCompactor: @staticmethod def compact(segments_old_to_new: list[dict[str, str]]) -> dict[str, str]: merged = {} for seg in segments_old_to_new: for k, v in seg.items(): merged[k] = v return {k: v for k, v in sorted(merged.items()) if v != TOMBSTONE} seg1 = {"a": "1", "b": "2", "c": "3"} seg2 = {"b": "20", "c": TOMBSTONE} seg3 = {"d": "4"} out = SSTableCompactor.compact([seg1, seg2, seg3]) assert out == {"a": "1", "b": "20", "d": "4"} assert "c" not in out print(f"SSTableCompactor verified: tombstone 'c' purged, compacted={out}") ``` </details>

Checkpoint

Why can't a storage engine immediately delete a key from disk when a client issues a DELETE command? ๐Ÿง 

Practice

Implement `SSTableCompactor.compact(segments_old_to_new: list[dict[str, str]]) -> dict[str, str]`. Process segments in order so newer values overwrite older ones, then discard any keys whose final value equals `TOMBSTONE = '__DELETED__'`. Test with `seg1 = {'a': '1', 'b': '2', 'c': '3'}`, `seg2 = {'b': '20', 'c': '__DELETED__'}`, and `seg3 = {'d': '4'}`. Verify `'b'` is `'20'` and `'c'` is purged. Print results. ๐ŸŽฏ

Terminal
01
Tap code blocks below to assemble
Available Blocks