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;