ARIS Concept

Scenario Setup:

• Pages: P$1$, P$2$
• Transactions: T$1$, T$2$, T$3$
• Initial State: Both P$1$ and P$2$ on disk have some initial data. Their PageLSN on disk is $0$. The buffer pool is initially empty/clean.

Simulated Log Sequence (Normal Operation + Crash):

Assume the following log records are written sequentially to stable storage. We also note the state of the relevant data structures (in memory) as things progress before the crash.

1. LSN $10$: Update(T1, P1, PrevLSN=0, Redo=Op1, Undo=UndoOp1)
   • Effect: T1 modifies P1 in the buffer pool.
   • TxnTable: { T1: {Status: Running, LastLSN: $10$} }
   • DPT: { P1: {RecLSN: $10$} } (P1 becomes dirty)
2. LSN $20$: Update(T2, P2, PrevLSN=0, Redo=Op2, Undo=UndoOp2)
   • Effect: T2 modifies P2 in the buffer pool.
   • TxnTable: { T1: {Status: Running, LastLSN: $10$}, T2: {Status: Running, LastLSN: $20$} }
   • DPT: { P1: {RecLSN: $10$}, P2: {RecLSN: $20$} } (P2 becomes dirty)
3. LSN $30$: Update(T1, P2, PrevLSN=10, Redo=Op3, Undo=UndoOp3)
   • Effect: T1 modifies P2 in the buffer pool.
   • TxnTable: { T1: {Status: Running, LastLSN: $30$}, T2: {Status: Running, LastLSN: $20$} }
   • DPT: { P1: {RecLSN: $10$}, P2: {RecLSN: $20$} } (P2 already dirty, RecLSN doesn’t change)
4. LSN $40$: BeginCheckpoint
5. LSN $50$: EndCheckpoint( ActiveTxn=[T1(LastLSN=$30$), T2(LastLSN=$20$)], DirtyPages=[P1(RecLSN=$10$), P2(RecLSN=$20$)] )
   • Effect: Checkpoint written, recording the current TxnTable and DPT state.
6. LSN $60$: Update(T3, P1, PrevLSN=0, Redo=Op4, Undo=UndoOp4)
   • Effect: T3 starts and modifies P1 in the buffer pool.
   • TxnTable: { T1: {Status: Running, LastLSN: $30$}, T2: {Status: Running, LastLSN: $20$}, T3: {Status: Running, LastLSN: $60$} }
   • DPT: { P1: {RecLSN: $10$}, P2: {RecLSN: $20$} } (P1 already dirty, RecLSN doesn’t change)
7. LSN $70$: Commit(T2)
   • Effect: T2 successfully commits. Its log records (LSN $20$, $70$) are stable.
   • TxnTable: { T1: {Status: Running, LastLSN: $30$}, T2: {Status: Committed, LastLSN: $20$}, T3: {Status: Running, LastLSN: $60$} }
8. LSN $80$: Update(T1, P1, PrevLSN=30, Redo=Op5, Undo=UndoOp5)
   • Effect: T1 modifies P1 again.
   • TxnTable: { T1: {Status: Running, LastLSN: $80$}, T2: {Status: Committed, LastLSN: $20$}, T3: {Status: Running, LastLSN: $60$} }
   • DPT: { P1: {RecLSN: $10$}, P2: {RecLSN: $20$} }
9. CRASH! Assume the system crashes now. All log records up to LSN $80$ are safe on disk. Assume no pages were flushed to disk after the checkpoint (so P$1$ and P$2$ on disk still have PageLSN = 0).

---

Recovery Process:

Phase 1: Analysis

1. Find Checkpoint: Locate the last complete checkpoint (LSN $40$ - $50$).
2. Load State: Initialize the TxnTable and DPT from the EndCheckpoint record (LSN $50$):
   • TxnTable: { T1: {Status: Running, LastLSN: $30$}, T2: {Status: Running, LastLSN: $20$} }
   • DPT: { P1: {RecLSN: $10$}, P2: {RecLSN: $20$} }
3. Scan Forward from Checkpoint (LSN $40$):
   • LSN $60$: Update(T3, P1, ...)
     • Add T3 to TxnTable: { ..., T3: {Status: Running, LastLSN: $60$} }
     • P1 already in DPT, no change to DPT.
   • LSN $70$: Commit(T2)
     • Update T2 status in TxnTable: { ..., T2: {Status: Committed, LastLSN: $20$}, ... }
   • LSN $80$: Update(T1, P1, ...)
     • Update T1 LastLSN in TxnTable: { T1: {Status: Running, LastLSN: $80$}, ... }
     • P1 already in DPT, no change to DPT.
4. End of Log: Scan finishes.
5. Analysis Outcome:
   • Final TxnTable: { T1: {Status: Running, LastLSN: $80$}, T2: {Status: Committed, LastLSN: $20$}, T3: {Status: Running, LastLSN: $60$} }
   • Final DPT: { P1: {RecLSN: $10$}, P2: {RecLSN: $20$} }
   • Loser Transactions: T1, T3 (Status is ‘Running’).
   • redoLSN: min(RecLSN values in DPT) = min($10,20$) = $10$.

Phase 2: Redo (“Repeating History”)

1. Start Scan: Begin scanning the log forward from `redoLSN = $10$.
2. Process Log Records:
   • LSN $10$: Update(T1, P1, ...)
     • Is P$1$ in DPT? Yes. Is RecLSN(P$1$)=$10\le$ LSN $10$? Yes.
     • Fetch P$1$ (Disk PageLSN=$0$). Is PageLSN($0$) < LSN($10$)? Yes.
     • Redo Op1 on P$1$ (in buffer). Set P$1$’s buffer PageLSN = $10$.
   • LSN $20$: Update(T2, P2, ...)
     • Is P$2$ in DPT? Yes. Is RecLSN(P$2$)=$20\le$ LSN $20$? Yes.
     • Fetch P$2$ (Disk PageLSN=$0$). Is PageLSN($0$) < LSN($20$)? Yes.
     • Redo Op2 on P$2$ (in buffer). Set P$2$’s buffer PageLSN = $20$.
   • LSN $30$: Update(T1, P2, ...)
     • Is P$2$ in DPT? Yes. Is RecLSN(P$2$)=$20\le$ LSN $30$? Yes.
     • Fetch P$2$ (Buffer PageLSN=$20$). Is PageLSN($20$) < LSN($30$)? Yes.
     • Redo Op3 on P$2$ (in buffer). Set P$2$’s buffer PageLSN = $30$.
   • LSN $40$: BeginCheckpoint - Skip.
   • LSN $50$: EndCheckpoint - Skip.
   • LSN $60$: Update(T3, P1, ...)
     • Is P$1$ in DPT? Yes. Is RecLSN(P$1$)=$10\le$ LSN $60$? Yes.
     • Fetch P$1$ (Buffer PageLSN=$10$). Is PageLSN($10$) < LSN($60$)? Yes.
     • Redo Op4 on P$1$ (in buffer). Set P$1$’s buffer PageLSN = $60$.
   • LSN $70$: Commit(T2) - Skip (no data modification).
   • LSN $80$: Update(T1, P1, ...)
     • Is P$1$ in DPT? Yes. Is RecLSN(P$1$)=$10\le$ LSN $80$? Yes.
     • Fetch P$1$ (Buffer PageLSN=$60$). Is PageLSN($60$) < LSN($80$)? Yes.
     • Redo Op5 on P$1$ (in buffer). Set P$1$’s buffer PageLSN = $80$.
3. End of Log: Redo phase finishes.
4. Redo Outcome: The buffer pool now reflects the exact state at the moment of crash.
   • P$1$ contains effects of Op1 (LSN $10$), Op4 (LSN $60$), Op5 (LSN $80$). Buffer PageLSN = $80$.
   • P$2$ contains effects of Op2 (LSN $20$), Op3 (LSN $30$). Buffer PageLSN = $30$.

Phase 3: Undo

1. Identify Losers: From Analysis, losers are T1 and T3.
2. Initialize ToUndo: Get LastLSN for each loser: ToUndo = { $80$ (from T1), $60$ (from T3) }.
3. Scan Backward: Start processing from max($80,60$) = $80$.
   • Process LSN $80$: Update(T1, P1, PrevLSN=30, ...)
     • Is LSN $80$ in ToUndo? Yes.
     • Write CLR: Append CLR(T1, P1, UndoNextLSN=30, Redo=None, Undo=UndoOp5) to log. Let’s say this gets LSN $90$. (Log LSN $90$ must be stable).
     • Apply Undo: Perform UndoOp5 on P$1$ in the buffer.
     • Set PageLSN: Set P$1$’s buffer PageLSN = $90$ (the LSN of the CLR).
     • Update ToUndo: Remove $80$. Add UndoNextLSN ($30$) to ToUndo.
     • ToUndo = { $60,30$ }. Next LSN = max($60,30$) = $60$.
   • Process LSN $70$: Commit(T2) - Skip (not in ToUndo).
   • Process LSN $60$: Update(T3, P1, PrevLSN=0, ...)
     • Is LSN $60$ in ToUndo? Yes.
     • Write CLR: Append CLR(T3, P1, UndoNextLSN=0, Redo=None, Undo=UndoOp4) to log. Let’s say this gets LSN $100$. (Log LSN $100$ must be stable).
     • Apply Undo: Perform UndoOp4 on P$1$ in the buffer.
     • Set PageLSN: Set P$1$’s buffer PageLSN = $100$.
     • Update ToUndo: Remove $60$. Add UndoNextLSN ($0$) (i.e., add nothing).
     • ToUndo = { $30$ }. Next LSN = $30$.
   • Process LSN $50$: EndCheckpoint - Skip.
   • Process LSN $40$: BeginCheckpoint - Skip.
   • Process LSN $30$: Update(T1, P2, PrevLSN=10, ...)
     • Is LSN $30$ in ToUndo? Yes.
     • Write CLR: Append CLR(T1, P2, UndoNextLSN=10, Redo=None, Undo=UndoOp3) to log. Let’s say this gets LSN $110$. (Log LSN $110$ must be stable).
     • Apply Undo: Perform UndoOp3 on P$2$ in the buffer.
     • Set PageLSN: Set P$2$’s buffer PageLSN = $110$.
     • Update ToUndo: Remove $30$. Add UndoNextLSN ($10$) to ToUndo.
     • ToUndo = { $10$ }. Next LSN = $10$.
   • Process LSN $20$: Update(T2, P2, ...) - Skip (T2 is not a loser).
   • Process LSN $10$: Update(T1, P1, PrevLSN=0, ...)
     • Is LSN $10$ in ToUndo? Yes.
     • Write CLR: Append CLR(T1, P1, UndoNextLSN=0, Redo=None, Undo=UndoOp1) to log. Let’s say this gets LSN $120$. (Log LSN $120$ must be stable).
     • Apply Undo: Perform UndoOp1 on P$1$ in the buffer.
     • Set PageLSN: Set P$1$’s buffer PageLSN = $120$.
     • Update ToUndo: Remove $10$. Add UndoNextLSN ($0$).
     • ToUndo = {}.
4. ToUndo is Empty: The main backward scan is complete.
5. Write Abort Records: Append Abort(T1) and Abort(T3) log records (e.g., LSN $130$ and LSN $140$).
6. Undo Outcome:
   • All effects of loser transactions T1 and T3 have been undone.
   • P$1$ is back to its initial state (UndoOp4 undid Op4, UndoOp5 undid Op5, UndoOp1 undid Op1). Its PageLSN is $120$.
   • P$2$ now only contains the effects of the committed transaction T2 (Op2 from LSN $20$). UndoOp3 undid Op3 (from LSN $30$). Its PageLSN is $110$.
   • The database is now consistent, reflecting only the committed work of T2.

Recovery is complete. The database can now accept new transactions. Note how CLRs ensured that undo operations were logged and wouldn’t be re-attempted incorrectly if a crash happened during the Undo phase itself.