LSM-Trees: SSTable & Sparse In-Memory Index
Flushing a MemTable writes an immutable Sorted String Table (SSTable) to disk. Because keys are sequentially ordered, you do not need an index for every row. A Sparse Index samples every $N$-th key in RAM, locating any block in $O(\log S)$ time πΎπ.
import bisect
class MockSSTable:
def __init__(self, sorted_pairs):
self.disk_data = sorted_pairs
# Sparse in-memory index: every 2nd key
self.sparse_idx = [(k, i) for i, (k, v) in enumerate(sorted_pairs) if i % 2 == 0]
def find(self, target_key):
idx_keys = [k for k, offset in self.sparse_idx]
slot = bisect.bisect_right(idx_keys, target_key) - 1
if slot < 0:
return None
start = self.sparse_idx[slot][1]
end = self.sparse_idx[slot + 1][1] if slot + 1 < len(self.sparse_idx) else len(self.disk_data)
# Local block scan:
for k, v in self.disk_data[start:end]:
if k == target_key:
return v
return None
sstable = MockSSTable([("a", 10), ("c", 20), ("e", 30), ("g", 40)])
print(f"SSTable lookup 'e': {sstable.find('e')} π")
# 57. LSM-Trees: SSTable & Sparse In-Memory Index In a B-Tree, if your index doesn't fit in RAM, you must read index pages from disk just to find the index page of the data page. In an LSM-Tree, an SSTable is immutable and strictly sorted π. ```python # SSTable On-Disk File: # ["apple": 1, "banana": 2, "cherry": 3, "date": 4, "elderberry": 5] # Sparse In-Memory Index (Tiny footprint in RAM): # {"apple": Offset 0, "cherry": Offset 2, "elderberry": Offset 4} # Search for "banana": # "banana" is between "apple" and "cherry" -> Read block at Offset 0! ``` ### The SSTable Architecture 1. **Immutability**: Once written to disk, an SSTable file is NEVER modified in-place. Reads do not acquire write locks, enabling massive parallel read throughput. 2. **Sparse Memory Index**: Storing 1 index entry per 4KB or 64KB block keeps the entire sparse index resident in RAM, consuming a fraction of the memory required by a full dense index πΎ. 3. **Bloom Filters**: Before even touching the sparse index or disk, an in-memory Bloom filter quickly checks whether a key definitely does NOT exist in the SSTable, skipping unnecessary disk I/O completely β‘. --- ### Interactive Pop-Quiz π§ #### Why can an SSTable use a compact sparse index rather than storing an index pointer for every single row? - [ ] Because keys are written in strict sorted order, allowing binary search between sparse boundary keys πΎ - [ ] Because the operating system automatically encrypts files into 16-bit blocks - [ ] Because SSTables do not allow duplicate keys across different tables - [ ] Because sparse indices bypass CPU instruction branching --- ### Practical Challenge π― Implement `SSTable` with `query(target_key)` using a sparse index that records every 2nd key. Given sorted pairs `[('b', 2), ('d', 4), ('f', 6), ('h', 8), ('j', 10)]`, query `'f'` and `'h'`. Assert both values match, and print `(query('f'), query('h'))`. <details> <summary>Solution</summary> ```python import bisect class SSTable: def __init__(self, pairs): self.data = pairs self.sparse = [(k, i) for i, (k, v) in enumerate(pairs) if i % 2 == 0] def query(self, target): keys = [k for k, pos in self.sparse] slot = bisect.bisect_right(keys, target) - 1 if slot < 0: return None start = self.sparse[slot][1] end = self.sparse[slot + 1][1] if slot + 1 < len(self.sparse) else len(self.data) for k, v in self.data[start:end]: if k == target: return v return None table = SSTable([('b', 2), ('d', 4), ('f', 6), ('h', 8), ('j', 10)]) vf = table.query('f') vh = table.query('h') assert vf == 6 and vh == 8 print((vf, vh)) ``` </details>