A different flavor of write-ahead logging than the Database Internals course's WAL Crash Recovery exercise: that one protects a single database's own transactions (row-level changes). This one models JBD2, the generic journaling layer underneath ext3/ext4 (and others) -- it protects filesystem metadata (inode updates, block bitmap changes, directory entries) at the block layer, below the level of any single file, shared by every process using the filesystem.

The same core WAL idea applies either way: a change is written to a circular journal and committed there before it's later checkpointed (written to its real, final on-disk location). If the system crashes after a commit but before the checkpoint, the change is not lost -- it gets replayed from the journal during recovery. If it crashes before the commit, the change never happened as far as anyone can tell.

begin_transaction(), write_block(), and read_block() are given. Implement:

• commit(txn_id) -- make txn_id's staged writes durable by appending them to self.journal_log as a single committed entry, and drop them from self._open_txns. This is the write-ahead durability point: the data survives a crash from here on, even though it hasn't reached self.disk yet.
• checkpoint() -- flush the OLDEST committed-but-not-yet-checkpointed transaction (journal_log's first entry) onto self.disk, and remove it from journal_log. Return the txn_id that was checkpointed, or None if journal_log is empty.
• crash_recover() -- simulate what happens when the system restarts after an unclean shutdown: any staged-but-uncommitted writes are gone (they only ever lived in memory) -- discard self._open_txns. Then replay every remaining committed transaction in journal_log onto self.disk, in commit order, clearing journal_log as you go. Return the list of txn_ids that were replayed, in order.

Example

j = Journal()
t1 = j.begin_transaction()
j.write_block(t1, 100, "inode-v1")
j.commit(t1)               # durable now, even though disk[100] is still unset
j.read_block(100)          # -> "inode-v1"  (read from the journal)
j.crash_recover()          # -> [t1]  (replayed onto disk -- nothing was lost)
j.disk[100]                # -> "inode-v1"

Constraints

• write_block calls for a transaction that's never committed must have zero effect on read_block or crash_recover -- as if they never happened.
• checkpoint always processes journal_log in commit order (oldest first) -- never checkpoint transaction N+1 while transaction N is still waiting.
• read_block must prefer a still-journaled (committed) value over whatever's on self.disk, since self.disk can be stale for a block that hasn't been checkpointed since a more recent commit.

Real-world grounding

• The actual commit path that appends a transaction's metadata buffers to the journal: fs/jbd2/commit.c (see jbd2_journal_commit_transaction()).
• Crash recovery -- replaying the journal to bring the filesystem back to a consistent state without a full fsck: fs/jbd2/recovery.c (see jbd2_journal_recover() and do_one_pass()).

Real JBD2 also has to handle a journal that's a genuinely CIRCULAR, fixed-size region of disk (checkpointing exists specifically to reclaim journal space once the real data has safely landed at its final location), plus a "revoke" mechanism for blocks that get freed and reused before their journal entry would otherwise be replayed -- both simplified away here so the core commit/checkpoint/replay relationship stays the focus.