Back
+20 XP
Concept

LSM Compaction: Merging SSTables & Tombstone Purging

As SSTables accumulate on disk, reads slow down and deleted keys linger as tombstones. Compaction runs a background multi-way merge across sorted SSTables, deduplicating updates to the newest timestamp and permanently garbage-collecting tombstones ๐Ÿงน๐Ÿ“ฆ.

python
def compact_segments(segment_list):
    latest_entries = {}

    for segment in segment_list:
        for key, timestamp, value in segment:
            if key not in latest_entries or timestamp > latest_entries[key][0]:
                latest_entries[key] = (timestamp, value)

    # Build compacted table, discarding None tombstones:
    compacted = []
    for k in sorted(latest_entries):
        ts, val = latest_entries[k]
        if val is not None:
            compacted.append((k, val))
    return compacted

s1 = [("k1", 1, "old_val"), ("k2", 1, "delete_me")]
s2 = [("k1", 2, "new_val"), ("k2", 2, None)] # None is a tombstone!

print(f"Compacted SSTable: {compact_segments([s1, s2])} ๐Ÿš€")

# 58. LSM Compaction: Merging SSTables & Tombstone Purging Because SSTables on disk are strictly immutable, you cannot delete a key by opening an existing file and deleting its bytes. Doing so would destroy the sparse index and corrupt byte offsets ๐Ÿ›‘. ```python # The Tombstone Deletion Protocol: # 1. User calls db.delete("user_42") # 2. Engine writes ("user_42", TOMBSTONE) to MemTable and WAL # 3. Reads hitting this key see TOMBSTONE and return NOT_FOUND # 4. Background Compaction physically removes the key forever! ``` ### The Compaction Engine 1. **Multi-Way Merge Sort**: Because each input SSTable file is already sorted internally, merging $K$ SSTables into 1 new SSTable takes $O(N \log K)$ time using a min-heap or priority queue. 2. **Deduplication**: When the merge sees duplicate keys from different SSTable generations, it discards older versions, saving massive amounts of disk space. 3. **Tombstone Removal**: If a key has value `TOMBSTONE` (or `None`) and exists in the lowest compaction level (meaning no older SSTable can possibly hold that key), the entry is completely dropped from disk ๐Ÿงน๐Ÿ“ฆ. --- ### Interactive Pop-Quiz ๐Ÿง  #### How does an LSM storage engine represent key deletions without performing slow random seeks to overwrite historical SSTables? - [ ] It appends a deletion record called a Tombstone, which masks older versions until background compaction purges them ๐Ÿงน - [ ] It truncates the file system partition up to the deleted byte - [ ] It shifts all subsequent bytes on disk backward by the key's width - [ ] It restarts the database server to clear operating system caches --- ### Practical Challenge ๐ŸŽฏ Implement `compact(tables)` merging sorted `(key, ts, value)` tuples from multiple tables. Given Table A (older): `[('a', 10, 'A1'), ('b', 10, 'B1'), ('c', 10, 'C1')]` and Table B (newer): `[('b', 20, None), ('c', 20, 'C2')]`. Compact them, assert the result is `[('a', 'A1'), ('c', 'C2')]`, and print the compacted list. <details> <summary>Solution</summary> ```python def compact(tables): latest = {} for t in tables: for k, ts, v in t: if k not in latest or ts > latest[k][0]: latest[k] = (ts, v) return [(k, latest[k][1]) for k in sorted(latest) if latest[k][1] is not None] t_a = [('a', 10, 'A1'), ('b', 10, 'B1'), ('c', 10, 'C1')] t_b = [('b', 20, None), ('c', 20, 'C2')] res = compact([t_a, t_b]) assert res == [('a', 'A1'), ('c', 'C2')] print(res) ``` </details>

Checkpoint

How does an LSM storage engine represent key deletions without performing slow random seeks to overwrite historical SSTables? ๐Ÿง 

Practice

Implement `compact(tables)` merging sorted `(key, ts, value)` tuples from multiple tables. Given Table A (older): `[('a', 10, 'A1'), ('b', 10, 'B1'), ('c', 10, 'C1')]` and Table B (newer): `[('b', 20, None), ('c', 20, 'C2')]`. Compact them, assert the result is `[('a', 'A1'), ('c', 'C2')]`, and print the compacted list. ๐ŸŽฏ

Terminal
01
Tap code blocks below to assemble
Available Blocks