Log-Structured Merge-Trees: The In-Memory MemTable
B-Trees choke on write-heavy workloads because updating leaves requires random I/O writes. LSM-Trees (RocksDB, ClickHouse) route all writes sequentially into an append-only commit log and an in-memory sorted MemTable, turning random mutations into sequential speed 📝⚡.
import bisect
class MemTable:
def __init__(self, flush_threshold=3):
self.flush_threshold = flush_threshold
self.keys = []
self.values = []
def put(self, key, value):
idx = bisect.bisect_left(self.keys, key)
if idx < len(self.keys) and self.keys[idx] == key:
self.values[idx] = value
else:
self.keys.insert(idx, key)
self.values.insert(idx, value)
return len(self.keys) >= self.flush_threshold
memtable = MemTable(flush_threshold=2)
memtable.put("user_99", "active")
needs_flush = memtable.put("user_12", "pending")
print(f"Sorted MemTable: {memtable.keys}, Flush required: {needs_flush} 🚀")
# 56. Log-Structured Merge-Trees: The In-Memory MemTable When a database performs 100,000 writes per second, a B-Tree must locate and overwrite 100,000 distinct 4KB disk pages. This causes severe disk thrashing and high write amplification 🛑. ```python # The LSM Storage Architecture: # Write Pipeline: # 1. Append raw write to Write-Ahead Log (WAL on disk for durability) # 2. Insert into MemTable (In-memory sorted tree: Red-Black or Skiplist) # 3. Client receives SUCCESS in 0.01ms! # (No random disk page overwrites occurred!) ``` ### The MemTable Invariants 1. **Sorted In-Memory Structure**: As items arrive out of order, the MemTable inserts them in sorted key order using binary search or skiplist pointers. 2. **Instant Point Lookups**: Reading the newest writes checks the MemTable first before hitting disk files. 3. **Threshold Flushing**: When the MemTable reaches its memory limit (e.g. 64MB), it is frozen, converted to an immutable SSTable, and flushed sequentially to disk in a single burst 📝⚡. --- ### Interactive Pop-Quiz 🧠 #### Why do LSM-Trees achieve significantly higher write throughput than B-Trees? - [ ] LSM writes append strictly to RAM and sequential commit logs, avoiding random in-place disk page rewrites 📝 - [ ] LSM trees run without using RAM or CPU caches - [ ] LSM trees bypass the operating system filesystem driver using GPU shaders - [ ] LSM trees convert binary strings into uncompressed text --- ### Practical Challenge 🎯 Implement `MemTable` with `put(k, v)` and `get(k)` keeping `keys` and `values` sorted using `bisect.bisect_left`. If a key already exists, overwrite its value in place. Insert `'k3': 'v3'`, `'k1': 'v1'`, `'k2': 'v2'`, then overwrite `'k2': 'v2_updated'`. Assert `keys == ['k1', 'k2', 'k3']` and `get('k2') == 'v2_updated'`. Print `keys`. <details> <summary>Solution</summary> ```python import bisect class MemTable: def __init__(self): self.keys = [] self.values = [] def put(self, k, v): idx = bisect.bisect_left(self.keys, k) if idx < len(self.keys) and self.keys[idx] == k: self.values[idx] = v else: self.keys.insert(idx, k) self.values.insert(idx, v) def get(self, k): idx = bisect.bisect_left(self.keys, k) if idx < len(self.keys) and self.keys[idx] == k: return self.values[idx] return None mt = MemTable() mt.put('k3', 'v3') mt.put('k1', 'v1') mt.put('k2', 'v2') mt.put('k2', 'v2_updated') assert mt.keys == ['k1', 'k2', 'k3'] assert mt.get('k2') == 'v2_updated' print(mt.keys) ``` </details>