Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Transactions and recoverable execution
Page 15 of 20

Recovery and Logging

Derive crash recovery from durable log prefixes, page LSNs, transaction outcomes, and verified restore paths.

Lesson briefTransactions and recoverable execution · 8 h · 4 outcomes

Required knowledge

  • Pages, dirty buffers, checksums, and write-ahead ordering
  • Transactions, commit/abort outcomes, and strict handling of uncommitted writes
  • Basic failure models: process crash, storage loss, accidental deletion, and corruption

Learning outcomes

  • Determine which log and page state is durable at a crash point and what recovery may safely expose.
  • Trace redo and undo decisions using transaction status and page/log sequence numbers.
  • Explain why a replica, a WAL archive, and a backup answer different recovery questions.
  • Design a restore drill that tests an RPO/RTO claim with integrity evidence.

Assessment target

Given a crash image with page LSNs, log records, transaction states, and a recovery objective, derive the legal redo/undo result and propose a restore test that could falsify the claim.

Scope boundary

  • ARIES is taught at the protocol level: analysis, redo, undo, page LSNs, and compensation log records. A complete industrial implementation, filesystem journaling, storage-controller failure modes, and proprietary backup products are deferred.
  • Multi-region quorum durability is treated as a distributed-system contract rather than inferred from local WAL alone.

A commit response is a promise about a failure boundary. If a power loss follows an acknowledged order but precedes the page write, the order must still be recoverable. If a data page reaches storage before the log record explaining it, recovery loses its evidence. Logging is therefore a protocol for reconstructing a legal state, not an audit trail added after the fact.

A durable log prefix orders safe writes

LSNTransactionRecordDurable before crash?
900T1beginyes
901T1set stock 20 → 13yes
902T1commityes
903T2beginyes
904T2set stock 13 → 6yes
905T2commitno
Code
participant "transaction" as T
participant "log manager" as L
participant "buffer page 42" as B
database "durable storage" as D
T -> L : append update LSN 901
T -> B : change page; pageLSN=901
L -> D : force log through 901
B -> D : flush page 42
T -> L : append commit
L -> D : force commit before acknowledgement
transactionlog managerbuffer page 42durable storagetransactiontransactionlog managerlog managerbuffer page 42buffer page 42durable storagedurable storageappend update LSN 901change page;pageLSN=901force log through 901flush page 42append commitforce commit beforeacknowledgement

The stable log prefix ending at 904 supports T1’s commit. A crash before 905 becomes durable cannot honestly expose T2 as committed. A data page may contain an update before its transaction commits; recovery’s transaction status decides whether to preserve, undo, or hide it. Page LSNs make redo idempotent: if a page already reflects LSN 901 or later, reapplying 901 is unnecessary.

Prediction — a page beats its log

A page reflecting LSN 911 reaches storage, but the log is durable only through 910. Why is this STEAL-without-WAL failure mode an error even if the update happens to be correct?

HintExpand

Recovery needs a durable explanation for every durable page effect.

Worked solutionExpand

The durable page contains an effect whose redo/undo record may be absent. After a crash, recovery cannot determine whether the change belonged to a committed transaction, reconstruct an overwritten older value, or repeat the operation safely on another page. WAL forbids this ordering; correctness is not established by observing one lucky final value.

Redo repeats history; undo removes losers

Interactive exploration

Crash between log records; derive redo and undo

Move the crash point through a small write-ahead log. T1 changes A and commits; T2 changes B but never commits. Inspect which updates recovery may retain.

Crash after durable log record 5: COMMIT T1
Durable log prefix: 5 of 5
  1. 1. BEGIN T1
  2. 2. UPDATE A: 10 → 7
  3. 3. BEGIN T2
  4. 4. UPDATE B: 20 → 30
  5. 5. COMMIT T1

Possible page values at crash

A ∈ {10, 7}
B ∈ {20, 30}

A durable update log permits, but does not prove, its page write.

Winner / loser

T1: winner — ensure A = 7
T2: loser — roll back B if present

After recovery

A = 7
B = 20

Model scope: WAL forces each log record before its corresponding page write, but log durability does not reveal whether a page write happened before the crash. Log records are durable in the order shown; updates include before/after images; no torn pages or concurrent transactions appear. ARIES also performs analysis, tracks page LSNs, and repeats history before undo.

Crash between log records; derive redo and undo

Possible page values at crash

A ∈ {10, 7}
B ∈ {20, 30}

A durable update log permits, but does not prove, its page write.

Winner / loser

T1: winner — ensure A = 7
T2: loser — roll back B if present

After recovery

A = 7
B = 20

Static state: T1’s commit record is durable, so recovery ensures its update is reflected if necessary. T2 has no commit record, so recovery rolls its update back if it reached a page.

Advance the durable prefix in the playground and state the committed state before revealing it. The model intentionally exposes one committed transaction and one unfinished transaction; it is a small reasoning model, not a complete implementation of checkpoints or compensation log records.

Code
rectangle "analysis\nclassify winners and losers" as A
rectangle "redo\nrepeat missing durable effects" as R
rectangle "undo\nremove loser effects" as U
rectangle "consistent restart state" as S
A --> R
R --> U
U --> S
note right of R
A page LSN prevents
duplicate redo.
end note
analysisclassify winners and losersredorepeat missing durable effectsundoremove loser effectsconsistent restart stateA page LSN preventsduplicate redo.

Worked trace — crash after page flush

T1 writes stock 20 → 13 at LSN 901 and commits at 902. The page flushed at LSN 901 before the crash. T2’s update at 904 may be present in the buffer, but its data-page effect has not reached durable storage; T2 has no durable commit. Recovery sees page LSN 901, skips redundant redo of 901, and starts from a state that includes T1 but not T2. If T2’s update had reached the page, recovery would undo or make it invisible because T2 is a loser.

ARIES makes undo repeatable

The three-phase sketch above becomes a real recovery protocol only when an interrupted undo can itself survive a crash. ARIES adds compensation log records (CLRs) and a per-transaction undo-next LSN so that recovery never repeats an undo it already performed.

Worked trace. T2 begins at LSN 903, updates stock at 904, and crashes without a durable commit. During undo, recovery appends CLR 906 for the reversal with undoNextLSN = 903 and applies the undo. WAL requires that CLR to be durable before its changed page is flushed. Suppose 906 is durable and recovery crashes again before finishing. On restart, redo can repeat 906 if its effect is missing from the page; undo resumes at 903 instead of undoing 904 again. If the CLR was not durable, recovery follows the durable log instead: WAL prevents the corresponding undo page effect from having been safely flushed first.

PhaseReadsProducesKey invariant
Analysislog from the last checkpointtransaction table, dirty-page tableevery loser is identified before any undo
Redolog forward from the smallest dirty-page recLSN found during analysispages brought to their logged historypage LSN skips changes already present
Undolosers’ log records backwardCLRs and restored pre-imagesundoNextLSN advances exactly once per action

Analysis starts from the checkpoint designated by the master record and reconstructs transaction and dirty-page state. A fuzzy checkpoint records active transactions and dirty pages while work continues; the dirty-page table can contain a recLSN older than the checkpoint, so redo can start earlier. The correctness claim depends on WAL and the recovery protocol, not merely checkpoint frequency.

Why undo needs its own log record

0 / 4 answered

Transaction T3 has updates at LSN 20 and LSN 30. Recovery writes a durable CLR for undoing 30 with undoNextLSN = 20, then crashes. Evaluate which recovery principles apply:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Upon restart, the undo pass follows undoNextLSN to LSN 20, avoiding redundant re-undo of the modification at LSN 30.
2
The CLR is a redo-only log record during the redo phase to bring the data page up to its logged post-undo state.
3
Recovery must undo LSN 30 a second time because the original update record remains in the durable log history.
4
Appending a CLR automatically marks the transaction committed and releases all locks before restart.

Recovery objectives require distinct artifacts

ArtifactMain question answeredCannot replace
WAL / transaction loghow to recover changes after a base statea base copy once retention is exhausted
full or incremental backupwhat durable base can be restoredrecent changes without logs or later backups
replicahow quickly can service continue after a node lossan independently retained historical restore point
checksum / invariant testdid restored bytes and domain facts survive?the data copy itself

A stated recovery point objective (RPO) is acceptable data loss, measured in time or transactions. A recovery time objective (RTO) is acceptable restoration time. They are claims until a restore drill measures them. A backup file existing in object storage is not evidence that it restores, replays logs, starts, and passes business invariants.

Application — design a restore drill

The product claims RPO ≤ 5 minutes and RTO ≤ 60 minutes after a bad migration. State a drill that can disprove either number.

Worked solutionExpand

Capture a known workload and timestamps, take the documented base backup, retain the required WAL/archive interval, then introduce the bad migration. Restore into an isolated environment to a target time no more than five minutes before the declared incident boundary. Measure elapsed time through startup and validation, compare row checksums where appropriate, and test domain invariants such as tenant ownership and nonnegative stock. Failure to reach the time target disproves RPO; exceeding the measured recovery budget disproves RTO.

Corruption and accidental change need different responses

Transfer — select the first safe action

A replica is healthy but has already replayed an accidental tenant-wide deletion. A nightly backup exists and WAL is retained. What is the first safe recovery plan?

HintExpand

Do not promote the replica merely because it is available; it has the same logical damage.

Worked solutionExpand

Preserve the primary, replica, backup, and WAL evidence; restore the backup plus WAL to an isolated target before the deletion; verify the tenant scope and invariants; then choose a controlled logical export/import or a promotion plan with client fencing. The replica can reduce outage time in a node-loss case, but here it is not an independent recovery source.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 4.4.1: ARIES Compensation Log Record and Idempotent Restart

Verificationapplication

An active transaction T1T_1 modifies page PP at LSN 100. During crash recovery, ARIES undo writes CLR 105 with undoNextLSN = null, updating page PP to LSN 105. Before recovery completes, a second power outage occurs. Verify how the subsequent recovery restart handles CLR 105 and whether page PP is undone again.

HintExpand

Check the repeating-history redo phase and CLR redo-only properties.

Worked solutionExpand

On the second restart, the analysis phase identifies CLR 105 in the log. During the repeating-history redo phase, if page PP‘s page LSN on disk is less than 105, CLR 105 is reapplied to restore the page image. Because CLR 105 has undoNextLSN = null, the undo phase recognizes that all actions of T1T_1 are already fully reversed and does not attempt any further undo on page PP The process is strictly idempotent.

Exercise 4.4.2: Redo vs. Undo Duality in Write-Ahead Recovery

Descriptionrecall

Explain why write-ahead logging recovery requires both a forward redo pass and a backward undo pass, and why neither pass can substitute for the other.

HintExpand

Contrast unwritten committed pages with written uncommitted pages.

Worked solutionExpand

The redo pass is necessary because a transaction may commit while its dirty modified data pages remain in the volatile buffer pool without reaching disk (No-Force policy); redo replays logged updates to bring disk pages up to the committed state. The undo pass is necessary because dirty pages from active or uncommitted transactions may have been flushed to disk to free buffer frames (Steal policy); undo rolls back those uncommitted modifications to preserve transaction atomicity.

Exercise 4.4.3: Falsifiable RPO/RTO Disaster Recovery Drill Design

Constructionapplication

An enterprise SLA specifies RPO≤5 minutes\text{RPO} \le 5\text{ minutes} and RTO≤30 minutes\text{RTO} \le 30\text{ minutes} Specify a rigorous disaster recovery test drill protocol that either experimentally proves compliance or produces a falsifying measurement.

HintExpand

Establish a baseline workload with known timestamps, simulate catastrophic primary failure, and time restoration.

Worked solutionExpand
  1. Baseline workload: Generate continuous synthetic transactions writing timestamped sequence rows.
  2. Simulated catastrophe: At timestamp T0T_0 ungracefully terminate the primary node (kill -9) and sever network storage.
  3. Restoration timing: At T0T_0 trigger restore automation using the latest base backup and WAL archives. Record elapsed wall-clock time until the recovered instance passes health checks and accepts read/write queries TreadyT_{\text{ready}} If Tready−T0>30 minT_{\text{ready}} - T_0 > 30\text{ min} the SLA fails RTO.
  4. Data loss audit: Query the maximum transaction timestamp TlastT_{\text{last}} present in the restored database. If T0−Tlast>5 minT_0 - T_{\text{last}} > 5\text{ min} the SLA fails RPO.

Exercise 4.4.4: Point-in-Time Recovery vs. Streaming Replication for Logical Corruption

Generalisationtransfer

A developer mistakenly executes DROP TABLE accounts; on production. Within 100 milliseconds, the command is replicated to the hot standby replica. Contrast why promoting the streaming replica fails to recover the data, and prescribe the exact point-in-time recovery (PITR) procedure.

HintExpand

Physical replication propagates logical drop commands immediately. PITR halts replay prior to the drop.

Worked solutionExpand

A physical streaming replica faithfully executes every WAL record emitted by the primary. The DROP TABLE command is immediately applied to the replica, destroying the table there as well. Prescribed PITR procedure:

  1. Preserve the WAL archive and base backup immediately; do not overwrite existing standby state.
  2. Provision an isolated recovery server and restore the latest full physical base backup taken prior to the incident.
  3. Configure recovery settings with recovery_target_time set to 1 second before the exact execution timestamp of the DROP TABLE statement (or target the transaction ID preceding the drop).
  4. Replay WAL archives up to the target boundary, verify table integrity, and export the recovered accounts relation back to the production environment.

References & Further Reading