write-ahead-logging (wal) is a technique providing atomicity and durability (a and d in acid) in a database management system; write-ahead means operations in a transaction are logged durably before flushed to disk;

there are two types of write-ahead logs: undo log and redo log; both, in their simplest, involve 3 types of instructions:

  • log op: log an operation, durably;

    each log record contains the operands, and, their old values (in undo log) or new values (in redo log);

  • flush op: flush an operation to disk, durably;

  • log commit: log a commit record, durably;

undo log

undo log allows a dbms to undo a transaction;

transaction steps

  1. log ops;

  2. flush ops;

  3. log commit (saying: flushed);

recovery steps

  1. scan undo log and find uncommitted transactions (those without a commit record);

  2. for each uncommitted transaction, in reverse order:

    • revert each op (set operands to old values) using its undo log record, in reverse order;

rationale

the commit record in undo log marks a transaction as completely flushed and can be safely ignored during recovery;

  • if a transaction is committed, then it is guaranteed that all ops have been flushed (because transaction step 2 happens before step 3); so we dont need to treat committed transactions during recovery;

  • if a transaction is uncommitted, then some ops may not have been flushed; but it is still guaranteed that all flushed ops have been logged (because transaction step 1 happens before step 2); so we can revert all flushed ops using their old values recorded in the undo log;

redo log

redo log allows a dbms to redo a transaction;

transaction steps

  1. log ops;

  2. log commit (saying: logged);

  3. flush ops;

recovery steps

  1. scan redo log and find committed transactions (those with a commit record);

  2. for each committed transaction, in order:

    • replay each op (set operands to new values) using its redo log record, in order;

rationale

the commit record in redo log marks a transaction as completely logged and must be replayed during recovery;

  • if a transaction is committed, then we can replay all its ops because we have recorded the new values in all of them;

  • if a transaction is uncommitted, then we know we have not flushed any op yet (because transaction step 2 happens before step 3); so there is nothing to do;

during recovery, we dont need to replay from the first transaction:

  • we can log a flushed record (similar to a commit record in undo log) for a transaction after all its ops are flushed; then replay only needs to start from the first transaction without a flushed record;

  • we can regularly checkpoint the current state and log a checkpointed record after a checkpoint is successfully done; then replay only needs to start from the last successful checkpoint;

undo and redo log

undo log and redo log can be used together;

transaction steps

  1. log ops;

  2. log redo commit (saying: logged);

  3. flush ops;

  4. log undo commit (saying: flushed);

recovery steps

recovery is a combination of both undo and redo recovery, with a choice between undo and redo;

rationale

we can choose to either undo or redo because we have logged information for both types of recovery;