Overview

---

In this project, we implemented write-ahead logging and support for savepoints, rollbacks, and ACID compliant restart recovery in Java. The project consisted of two parts: forward processing where we perform logging and maintain some metadata such as the dirty page table and transaction table during normal operation of the database, and restart recovery (a.k.a. crash recovery), which consists of the processes taken when the database starts up again.

Section I: Forward Processing

---

When the database runs for the first time, it will call recoveryManager.initialize() and initialize the master record marking the 0th chekpoint. We store the master record as the very first log record in the log, at LSN 0. The master record stores the LSN of the begin checkpoint record of the most recent successful checkpoint

Transaction Status: The recovery manager is notified of changes in transaction status through three methods: commit(), abort() and end(). In these methods, we set updated the status of the transaction (COMMITTING/ABORTING/COMPLETE), append appropriate log record to the logManager and update the lastLSN in the transaction table. In commit(), the commit record needs to be flushed to disk and in end(), if the transaction ends in an abort, we roll back all changes through helper method rollbackToLSN(long transNum, long LSN) before an EndTransaction record is written. The code for rollbacktoLSN is attached below.

Savepoints and Checkpoints: We implemented savepoints for partial rollbacks whose logic was extremely similar to undoing changes in rollbacktoLSN(). In case of checkpoints, we implemented a fuzzy checkpoint using the helper function EndCheckpoint.fitsInOneRecord(# of dpt entries, # of txnTable entries) to check the page where EndChekpoint is located. The code for checkpoint is attached below.

Section II: Restart Recovery

---

In restart, the ARIES algorithm is used for data recovery, the committed transaction is ended, and the uncommitted transaction is aborted and rolled back. We implemented three stages: restartAnalysis(), restartRedo() and restartUndo(). In addition to the three phases of recovery, the restart method does two things:

• Between the redo and undo phases, any page in the dirty page table that isn't actually dirty (has changes in-memory that have not been flushed) should be removed from the dirty page table. These pages may be present in the DPT as a result of the analysis phase, if we are uncertain about whether a change has been flushed to disk successfully or not.
• After the undo phase, recovery has finished. To avoid having to abort all the transactions again should we crash, we take a checkpoint.

Process:

Analysis Phase : restartAnalysis() reconstructs the dirty page table and transaction table from the log.
Redo Phase : restartRedo() restores the database to the exact state at the crash, including all the changes of uncommitted transactions that were running at that point time.
Undo Phase: restartUndo() undoes all uncommitted changes, leaving the database in a consistent state

You can find my code for restartAnalysis(), restartRedo() and restartUndo() here