Making B-Trees Reliable — WAL, Crash Recovery, Checksums

Making B-Trees Reliable — WAL, Crash Recovery, Checksums A lifecycle diagram generated by Archify. Write path Buffers and caches Crash recovery Terminal Dirty Page · modified in memory · Write path · not on disk yet 01 Dirty Page modified in memory not on disk yet WAL Appended · log entry written first · Write path · sequential write 02 WAL Appended log entry written first sequential write WAL Synced · fsync returns · Write path · now durable 03 WAL Synced fsync returns now durable Page Written · update in place on disk · Write path · random write 04 Page Written update in place on disk random write Checkpoint · old log discarded · Write path · restart is fast 05 Checkpoint old log discarded restart is fast Unsynced Write · still in the OS cache · Buffers and caches · power loss loses it Unsynced Write still in the OS cache power loss loses it Redo from WAL · roll forward on startup · Crash recovery · idempotent replay Redo from WAL roll forward on startup idempotent replay Torn Write · checksum mismatch · Terminal · partial page on disk Torn Write checksum mismatch partial page on disk Write Lost · never reached the disk · Terminal · rolled back Write Lost never reached the disk rolled back append to log fsync later, in background periodically crash before fsync nothing to recover crash after fsync recovery completes crash mid-write rewrite from log Legend initial state active waiting decision success failure / exit final state