Back
+30 XP
Concept

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 πŸ’ΎπŸ§±βš‘.

python
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>

Checkpoint

Why are SSTable files on disk designed to be strictly immutable once written? 🧠

Practice

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. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks