Back
+35 XP
Concept

Module 44 Capstone: High-Performance WAL Storage Engine

Enterprise transactional databases achieve ACID durability via Write-Ahead Logging (WAL). Every mutation appends a CRC-checksummed, log-sequence-numbered (LSN) record to disk and calls fsync before mutating in-memory tables. On system crash, replaying the WAL recovers all committed state.

python
# WAL record framing:
# [CRC32: 4B, LSN: 8B, OP: 2B, KLEN: 2B, VLEN: 4B, KEY, VAL]
entry = struct.pack('>IQHHI', crc, lsn, op, klen, vlen) + payload

# Module 44 Capstone: High-Performance WAL Storage Engine When a power cord gets kicked out or an AWS physical host suffers a hardware kernel panic, any data sitting in volatile RAM vanishes forever. If a database directly updates complex on-disk B-trees, an untimely crash leaves trees half-balanced and corrupted. 🏆💾 The golden standard of database durability is **Write-Ahead Logging (WAL)**: 1. **Durability First**: Before touching any in-memory tables or disk B-trees, serialize the mutation as a binary log record containing a monotonic **Log Sequence Number (LSN)**, operation code, payload, and a **CRC-32 checksum**. 2. **Immediate Flush**: Write the record to the append-only WAL file and execute `os.fsync(fd)`. Only once the disk controller acknowledges physical persistence do we commit to memory. 3. **Crash Recovery**: When the database boots, scan the WAL file sequentially. Verify each record's CRC-32 checksum, discard trailing incomplete writes, and replay operations in order to restore 100% of committed state. ```python import struct import zlib ENTRY_FORMAT = ">IQHHI" # CRC32(4), LSN(8), OP(2), KLEN(2), VLEN(4) = 20 bytes ``` ## Pop Quiz Why must a database engine write and fsync mutations to a Write-Ahead Log before updating memory or B-tree tables? - [ ] If the machine loses power, any state in memory is lost; replaying the durable WAL log on reboot guarantees zero data loss. - [ ] Writing to a WAL log automatically compresses database indexes using hardware zstd instructions. - [ ] Because memory pages can only be updated if an active TCP socket is established. - [ ] To prevent operating systems from swapping active database memory to virtual swap files. ## Real-World Challenge Build a production-grade `WALEngine`: - `set(key: str, value: bytes) -> int`: Appends a SET record (`op=1`), calls `os.fsync`, updates the in-memory dictionary, and returns the assigned LSN. - `delete(key: str) -> int`: Appends a DELETE record (`op=2`), calls `os.fsync`, removes from in-memory dictionary, and returns LSN. - `get(key: str) -> bytes | None`: Returns the in-memory value. - `recover()`: Replays records from disk, validating CRC-32 checksums and ignoring incomplete records at EOF. <details> <summary>Solution</summary> ```python import struct import zlib import os class WALEngine: ENTRY_FORMAT = ">IQHHI" # CRC32(4B), LSN(8B), OP(2B), KLEN(2B), VLEN(4B) = 20B HEADER_SIZE = struct.calcsize(ENTRY_FORMAT) OP_SET = 1 OP_DEL = 2 def __init__(self, wal_path: str): self.wal_path = wal_path self._table = {} self.last_lsn = 0 self._file = open(wal_path, "a+b") self.recover() def recover(self): self._file.seek(0) while True: header_bytes = self._file.read(self.HEADER_SIZE) if len(header_bytes) < self.HEADER_SIZE: break crc, lsn, op, klen, vlen = struct.unpack(self.ENTRY_FORMAT, header_bytes) key_bytes = self._file.read(klen) val_bytes = self._file.read(vlen) if len(key_bytes) < klen or len(val_bytes) < vlen: # Incomplete write at end of crash log break # Validate CRC32 payload = struct.pack(">QHHI", lsn, op, klen, vlen) + key_bytes + val_bytes calculated_crc = zlib.crc32(payload) & 0xFFFFFFFF if crc != calculated_crc: # Corrupted record, halt replay break key = key_bytes.decode("utf-8") if op == self.OP_SET: self._table[key] = val_bytes elif op == self.OP_DEL: self._table.pop(key, None) self.last_lsn = lsn def set(self, key: str, value: bytes) -> int: self.last_lsn += 1 kbytes = key.encode("utf-8") payload = struct.pack(">QHHI", self.last_lsn, self.OP_SET, len(kbytes), len(value)) + kbytes + value crc = zlib.crc32(payload) & 0xFFFFFFFF entry = struct.pack(">I", crc) + payload self._file.seek(0, os.SEEK_END) self._file.write(entry) self._file.flush() os.fsync(self._file.fileno()) self._table[key] = value return self.last_lsn def delete(self, key: str) -> int: self.last_lsn += 1 kbytes = key.encode("utf-8") payload = struct.pack(">QHHI", self.last_lsn, self.OP_DEL, len(kbytes), 0) + kbytes crc = zlib.crc32(payload) & 0xFFFFFFFF entry = struct.pack(">I", crc) + payload self._file.seek(0, os.SEEK_END) self._file.write(entry) self._file.flush() os.fsync(self._file.fileno()) self._table.pop(key, None) return self.last_lsn def get(self, key: str) -> bytes | None: return self._table.get(key) def close(self): if not self._file.closed: self._file.flush() self._file.close() # Verification wal_test_path = "/tmp/test_durability_wal.log" if os.path.exists(wal_test_path): os.remove(wal_test_path) # Phase 1: Write committed mutations engine1 = WALEngine(wal_test_path) engine1.set("user:1", b"ALICE_ACTIVE") engine1.set("user:2", b"BOB_PENDING") engine1.delete("user:2") engine1.set("user:1", b"ALICE_UPDATED") engine1.close() # Phase 2: Simulate crash and reboot recovery engine2 = WALEngine(wal_test_path) assert engine2.get("user:1") == b"ALICE_UPDATED" assert engine2.get("user:2") is None assert engine2.last_lsn == 4 engine2.close() os.remove(wal_test_path) ``` </details>