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 ๐งน๐ฆ.
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>