Designing Log Record Data Structures

The Anatomy of a Log Record: Common Fields

Before diving into specific record types, let's look at the fields that are common to nearly every log record in ARIES. These fields provide the fundamental context and linkage needed to navigate the log.

Every log record is assigned a unique, monotonically increasing Log Sequence Number (LSN). Think of the LSN as the primary key for the log file. It establishes a total order for all logged operations.

To track all the operations belonging to a single transaction, log records are chained together like a linked list, pointing backward in time.

So, the three common fields are:

1. LSN (Log Sequence Number): The unique address of this log record.
2. transID (Transaction ID): The ID of the transaction that generated this record.
3. prevLSN (Previous LSN): The LSN of the previous log record generated by this same transaction. The first record for a transaction has a null prevLSN.

Beyond just being an ID, LSNs are integrated throughout the database system to coordinate recovery. For instance, every data page on disk stores the LSN of the latest update that touched it (pageLSN). The system also tracks the LSN of the last log record flushed to disk (flushedLSN). This allows the buffer manager to enforce the WAL UNDO rule: it can only write a dirty page to disk if that page's pageLSN is less than or equal to the flushedLSN.

The image below shows an example log file just before a crash. You can clearly see the structure: each row is a log record with its LSN, TxnID, and Type, among other fields.

UPDATE Records: Capturing the Change

The most frequent log records are UPDATE records. Each time a transaction modifies data on a page, an UPDATE record is generated. For the recovery algorithm to work, this record must contain enough information to both redo the change (for durability) and undo it (for atomicity).

Therefore, an UPDATE record contains additional fields beyond the common ones:

• type: Set to UPDATE.
• pageID: The identifier of the page that was modified.
• offset & length: Specifies the exact location and size of the change on the page.
• before-image: The value of the data before the modification. This is essential for UNDO.
• after-image: The value of the data after the modification. This is essential for REDO.

This is often called physiological logging: it's physical in that it describes byte-level changes (before/after images), but logical in that it's constrained to a single page.

Transaction Lifecycle Records: COMMIT and END

When a transaction successfully finishes, it must be marked as durable.

• A COMMIT record is written to the log. As we learned in the last lesson, the REDO rule of WAL states that the log, up to and including this COMMIT record, must be flushed to disk before notifying the client of success.

After a transaction commits or aborts, the system may need to do some internal cleanup.

• An END record is written to the log to signify that this transaction is completely finished and will generate no more log records. This allows the DBMS to safely remove the transaction from its internal data structures, like the Active Transaction Table. Unlike COMMIT records, END records are for internal bookkeeping and don't need to be flushed to disk immediately.

Aborts and Compensation Log Records (CLRs)

What happens when a transaction aborts, or when the recovery manager needs to undo a transaction that was active during a crash? The system can't just silently delete its changes. ARIES follows a key principle: all actions, including undo actions, must be logged.

When an UPDATE from an aborted transaction needs to be reversed, the system doesn't modify the original log. Instead, it writes a new log record called a Compensation Log Record (CLR).

A CLR has a structure similar to an UPDATE record, but it documents the action of reversing a previous update. A crucial property of CLRs is that they are never undone. If the system crashes while writing CLRs, it simply continues the undo process upon restart. This prevents infinite loops of undoing an undo action.

To make the undo process efficient, a CLR contains one more special pointer:

• undoNextLSN: This points to the prevLSN of the record being compensated. This allows the system to quickly jump to the next record that needs to be undone for this transaction, skipping over any intermediate records from other transactions.

Checkpoint Records: Making Recovery Fast

If a system crashes, it theoretically has to scan the entire log from the beginning of time. For a long-running system, this is impractical. Checkpoints are a mechanism to limit the amount of work needed for recovery.

ARIES uses a "fuzzy checkpoint" that doesn't require pausing the entire system. When a checkpoint is initiated, the DBMS writes a BEGIN_CHECKPOINT record. When it's finished, it writes an END_CHECKPOINT record. The END_CHECKPOINT record is the important one; it contains a snapshot of two key data structures at the time the checkpoint began:

1. Active Transaction Table (ATT): A list of all transactions that were running at the start of the checkpoint. For each transaction, it stores the transID, its status (e.g., running, committing), and the lastLSN it wrote.
2. Dirty Page Table (DPT): A list of all pages in the buffer pool that were dirty (had unpersisted changes) at the start of the checkpoint. For each page, it stores the pageID and the recLSN—the LSN of the log record that first made the page dirty.

During recovery, the system finds the last END_CHECKPOINT record and can use its ATT and DPT to dramatically reduce the amount of the log it needs to analyze.

Conclusion

In this lesson, we dissected the fundamental data structures that power database recovery. We've seen that a log file is far more than a simple history; it's a highly structured file where every field is engineered for the specific demands of the ARIES recovery algorithm.

Key Takeaways:

• Log records share common fields: a unique LSN, a transID, and a prevLSN pointer to chain a transaction's operations together.
• UPDATE records are the core, containing before-image and after-image data to enable both UNDO and REDO operations.
• COMMIT and END records manage the transaction lifecycle, separating the guarantee of durability from internal system cleanup.
• Compensation Log Records (CLRs) are written to log UNDO actions. They are never undone themselves and contain an undoNextLSN pointer to efficiently traverse the chain of updates that must be reversed.
• CHECKPOINT records contain snapshots of the Active Transaction Table (ATT) and Dirty Page Table (DPT) to limit the portion of the log that must be processed during recovery.

Preview of the Next Lesson

Now that we have designed the building blocks, we are ready to construct the building. In the next lesson, we will see how the ARIES algorithm uses these very log records to orchestrate recovery. We will walk through the three phases of ARIES—Analysis, Redo, and Undo—and see exactly how the information we've structured today is put into action to bring a crashed database back to a perfect, consistent state.