Capstone WAL: Append-Only Binary Write-Ahead Log
Crash durability requires that mutations hit durable storage before memory state updates. The Capstone Write-Ahead Log (WAL) appends sequential binary records guarded by CRC32 checksums, enabling zero data loss recovery following power failure or process crashes 🛡️💾⚡.
import struct, zlib, io
class WALWriter:
# Frame: Length (4B), CRC32 (4B) = 8 bytes
HEADER = struct.Struct(">II")
def __init__(self, stream):
self.stream = stream
def write_record(self, data):
crc = zlib.crc32(data)
self.stream.write(self.HEADER.pack(len(data), crc) + data)
buf = io.BytesIO()
wal = WALWriter(buf)
wal.write_record(b"STATE_UPDATE_467")
print(f"WAL Size: {buf.tell()} bytes written 🚀")
# 107. Capstone WAL: Append-Only Binary Write-Ahead Log If a database writes mutations directly to random memory addresses or in-place table blocks, a sudden power failure or hardware fault midway through an update leaves blocks in an unrecoverable, corrupt half-state 🛑. ```python # The Write-Ahead Logging Invariant (ARIES Protocol): # "No modification to a database page shall be made until the log record # describing the update is written to non-volatile storage (fsync)." ``` ### The Binary Framing Pattern Every entry in our Capstone WAL is framed with an 8-byte header: - **Length (`uint32`)**: Byte size of the payload. - **CRC32 Checksum (`uint32`)**: Cyclical redundancy check calculated over the raw payload bytes. ### Crash Recovery & Torn Writes When recovering after a crash, the engine reads the WAL from byte 0. If a sudden crash occurred while the disk controller was flushing a 4KB page, the payload is abruptly truncated: - The parser detects that `remaining_bytes < length`. - The incomplete record is safely discarded without corrupting the committed database history 🛡️💾⚡. --- ### Interactive Pop-Quiz 🧠 #### What catastrophe does checking CRC32 checksums in a WAL prevent during engine crash recovery? - [ ] Torn writes: partially flushed blocks caused by sudden power cuts are detected and truncated instead of corrupting database state 🛡️ - [ ] It prevents SQL injection vulnerabilities - [ ] It converts disk drives from HDD to NVMe SSD - [ ] It forces the operating system to double RAM memory --- ### Practical Challenge 🎯 Implement `BinaryWAL` backed by an `io.BytesIO` buffer. Provide `append(record_bytes: bytes) -> int` packing `len(record)` and `zlib.crc32(record)` with `struct.Struct('>II')`. Provide `recover() -> list[bytes]` validating CRC32 per frame, stopping on truncated bytes, and raising `ValueError` on CRC mismatch. Append two records, recover them, assert content equality, and print recovered records. <details> <summary>Solution</summary> ```python import struct, zlib, io class BinaryWAL: FRAME = struct.Struct(">II") def __init__(self, stream: io.BytesIO = None): self.stream = stream or io.BytesIO() def append(self, record_bytes: bytes) -> int: crc = zlib.crc32(record_bytes) hdr = self.FRAME.pack(len(record_bytes), crc) offset = self.stream.tell() self.stream.write(hdr + record_bytes) return offset def recover(self) -> list[bytes]: self.stream.seek(0) records = [] raw = self.stream.getvalue() offset = 0 while offset + self.FRAME.size <= len(raw): length, expected_crc = self.FRAME.unpack_from(raw, offset) offset += self.FRAME.size if offset + length > len(raw): break payload = raw[offset : offset + length] if zlib.crc32(payload) != expected_crc: raise ValueError(f"Corrupt WAL frame at {offset}") records.append(payload) offset += length return records wal = BinaryWAL() wal.append(b"LSN:1:PUT:account_101=500") wal.append(b"LSN:2:PUT:account_102=1200") recovered = wal.recover() assert len(recovered) == 2 assert recovered[0] == b"LSN:1:PUT:account_101=500" assert recovered[1] == b"LSN:2:PUT:account_102=1200" print(f"BinaryWAL recovered {len(recovered)} valid records: {recovered}") ``` </details>