Capstone Storage: Memory-Mapped Segment Ring & SSTable Flush
Directly writing random disk blocks bottlenecks throughput. The Capstone storage layer buffers mutations in an active in-memory MemTable. Once the MemTable reaches byte capacity, it freezes into an immutable segment and flushes sequentially to disk as an immutable SSTable file πΎπ§±β‘.
class StorageEngine:
def __init__(self, limit=3):
self.limit = limit
self.memtable = {}
self.segments = []
def write(self, k, v):
self.memtable[k] = v
if len(self.memtable) >= self.limit:
# Freeze and flush sorted snapshot
self.segments.append(dict(sorted(self.memtable.items())))
self.memtable = {}
eng = StorageEngine(limit=2)
eng.write("x", "100")
eng.write("y", "200")
print(f"Flushed SSTables: {len(eng.segments)} π")
# 108. Capstone Storage: Memory-Mapped Segment Ring & SSTable Flush Random writes to disk are the number one killer of database performance. Spinning disks have seek latency, and even NVMe SSDs suffer write amplification and garbage collection stalls when random blocks are repeatedly overwritten π. ```python # The LSM Storage Architecture: # Writes: [Client] -> [WAL Append (Sequential)] -> [MemTable (In-Memory)] # (Sync disk safety) (O(1) fast mutation) # # Flushes: [MemTable Full] -> [Freeze Immutable] -> [Sequential SSTable on Disk] ``` ### The Power of Immutable Segments When the in-memory MemTable exceeds its size threshold, it is frozen. A background thread streams its sorted key-value pairs to disk in a single continuous write. 1. **Zero Lock Contention**: Once written, an SSTable is NEVER modified in-place. Reader queries can scan SSTable segments concurrently without acquiring read/write locks! 2. **Crash Recovery Integration**: Once the SSTable flush completes, the engine safely advances its WAL checkpoint offset, reclaiming log disk space πΎπ§±β‘. --- ### Interactive Pop-Quiz π§ #### Why are SSTable files on disk designed to be strictly immutable once written? - [ ] Immutability allows lock-free concurrent reads, eliminates write-race conditions, and simplifies sequential compaction π‘οΈ - [ ] Because the Linux filesystem deletes mutable files automatically - [ ] To allow the CPU to run Python without electricity - [ ] Because mutable files cannot be transferred over TCP --- ### Practical Challenge π― Implement `MemTableRing(flush_threshold: int = 2)` with `active_table: dict`, `flushed_segments: list[dict]`, `put(key, val) -> bool` (returns True if flush triggered), and `get(key) -> val | None`. `get` checks active table first, then searches `flushed_segments` in reverse (newest first). Add `'k1'`, then `'k2'` (triggering flush), verify segment count 1 and active size 0, add `'k3'`, assert lookup for `'k1'` and `'k3'`, and print state. <details> <summary>Solution</summary> ```python class MemTableRing: def __init__(self, flush_threshold: int = 2): self.flush_threshold = flush_threshold self.active_table = {} self.flushed_segments = [] def put(self, key: str, value: str) -> bool: self.active_table[key] = value if len(self.active_table) >= self.flush_threshold: snapshot = dict(sorted(self.active_table.items())) self.flushed_segments.append(snapshot) self.active_table.clear() return True return False def get(self, key: str) -> str | None: if key in self.active_table: return self.active_table[key] for seg in reversed(self.flushed_segments): if key in seg: return seg[key] return None ring = MemTableRing(flush_threshold=2) flushed_1 = ring.put("k1", "val_one") assert flushed_1 is False flushed_2 = ring.put("k2", "val_two") assert flushed_2 is True assert len(ring.flushed_segments) == 1 assert len(ring.active_table) == 0 ring.put("k3", "val_three") assert ring.get("k1") == "val_one" assert ring.get("k3") == "val_three" assert ring.get("unknown") is None print(f"MemTableRing verified: 1 flushed segment, active key count={len(ring.active_table)}") ``` </details>