database: undo log and redo log
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
-
log ops;
-
flush ops;
-
log commit (saying: flushed);
recovery steps
-
scan undo log and find uncommitted transactions (those without a
commit
record); -
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
-
log ops;
-
log commit (saying: logged);
-
flush ops;
recovery steps
-
scan redo log and find committed transactions (those with a
commit
record); -
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 acommit
record in undo log) for a transaction after all its ops are flushed; then replay only needs to start from the first transaction without aflushed
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
-
log ops;
-
log redo commit (saying: logged);
-
flush ops;
-
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;