ARIES

This post is a short summary of the ARIES recovery algorithm with Fuzzy checkpoints, most of the explanations on this algorithm are tedious and hard to understand with a lot of notation, so I am summarizing it in a short and sweet way here

Objective: Retrieve Database state after a crash. Desired State has the following properties:

• A committed transaction needs to be durable
• An aborted transaction needs all its changes undone
• A transaction that was running needs to be aborted on crash

You must be wondering why 1 and 2 are even needed. That is because of ‘STEAL + NO FORCE’ policy, where we give total freedom to the Buffer pool to evict any page whenever it wants at whatever time (for the purpose of a higher throughput) So even a commit or an abort does not mean that pages are written/removed from disk.

Okay, so when are we safe to flush changes of a dirty page to disk?

Of course when the log of the change has already been written (if this did not happen, then it would be impossible to recover from a change that was just flushed to disk). When you see a transaction commit, all the changes(logs) associated with that transaction are flushed to disk.

So it makes sense to keep track of the latest log that has been written to disk for a particular page. That is denoted as pageLSN.
Where is the Log of the latest flushed change/log to any page? That is denoted as flushedLSN. What is the earliest un-recorded change to a disk to a page in memory (the earliest change that has not been recorded on disk)? That is called recLSN.

Analysis Phase

The goal of this phase is to determine:

Which transactions were active at the time of the crash (to later undo them), Which pages in memory were dirty (so we know which ones need to be redone), The most recent checkpoint.

Starting from the last fuzzy checkpoint, we scan forward in the log, updating information like the Transaction Table and Dirty Page Table. At the end of this phase, we know the state of the system just before the crash, i.e. we now now what pages may be dirty and what transactions need to be undone/redone

Redo Phase

We redo only changes only for committed transactions. Here, we replay log records to ensure that all effects of committed transactions are reflected in the database. But we don’t start from the beginning of the log—we start from the smallest recLSN in the Dirty Page Table (since that is the earliest un-recorded change to a page that is dirty and might need to be redone) For every log record after that, we only redo it if:

• The page it affects is dirty, and
• The LSN of the log record ≥ the page’s pageLSN (i.e. this change has not already been flushed to disk)

This is efficient because we skip unnecessary replays and only reapply the changes that might not have made it to disk before the crash.

Undo Phase

We undo changes for uncommitted or aborted transactions. Using the Transaction Table and the log’s backward chaining via prevLSN, we generate Compensation Log Records (CLRs) as we roll back each change. These CLRs are important for supporting idempotent recovery—if there’s a crash during recovery, we can just redo the CLRs safely.