Crash Recovery Using WAL and Checkpoints

Write a C program that implements crash recovery for a key-value store using WAL.

Requirements:

• Define a LogRecord: lsn, key, old_value, new_value, committed (int)
• Define a database state: array of 8 key-value pairs, initially zeros
• Define a WAL as an array of 6 log records:
  1. LSN=1, key=0, old=0, new=10, committed=1
  2. LSN=2, key=1, old=0, new=20, committed=1
  3. LSN=3, key=2, old=0, new=30, committed=0 (uncommitted — transaction active at crash)
  4. LSN=4, key=0, old=10, new=15, committed=1
  5. LSN=5, key=3, old=0, new=40, committed=0 (uncommitted)
  6. LSN=6, key=1, old=20, new=25, committed=1
• Simulate a checkpoint at LSN=2: mark that pages for keys 0 and 1 were flushed
• Simulate crash recovery:
  • Redo phase: replay all log records from LSN=1 onwards. For each record, if committed=1, apply new_value to the key
  • Track which keys were modified by uncommitted transactions
  • Undo phase: for uncommitted transactions, restore old_value
• Print database state after checkpoint, after crash (some pages not flushed), and after recovery
• Print which log records were redone and which were undone
• Verify that the final state is consistent: committed changes persist, uncommitted changes are rolled back