WAL and Checkpoints

Write-Ahead Logging (WAL) is the foundation of database recovery. Every modern database — PostgreSQL, MySQL, SQL Server, Oracle — uses WAL to guarantee durability and atomicity.

A checkpoint is a recovery optimization that limits how much of the log must be scanned after a crash.

---

Learning Objectives

After completing this chapter, you will be able to:

• Explain the WAL rule and why it is critical.
• Describe log record structure and Log Sequence Numbers (LSN).
• Explain different checkpoint types.
• Understand how checkpoints reduce recovery time.
• Answer WAL and checkpoint interview questions.

---

Write-Ahead Logging (WAL)

The WAL Rule

Before any change is written to the database (data pages on disk), the corresponding log record must be written to stable storage (the WAL log on disk).

In other words:

1. Write the log record to the WAL (disk).
2. Write the data change to the data page (disk or memory).

If the system crashes after step 1 but before step 2, the DBMS can redo the change from the log during recovery.

---

Why WAL Matters

Without WAL, consider this scenario:

1. A transaction updates Account A’s balance.
2. The database writes the updated page to disk.
3. The system crashes before the commit record is written to the log.

On restart: The data page shows the update, but there is no commit record. The DBMS does not know whether to keep the change or undo it.

With WAL: The log is written first. If the commit record is in the log, the change is redone. If not, it is undone. The database is always consistent.

---

Log Record Structure

Each log record contains:

Field	Description
LSN	Log Sequence Number (unique, monotonically increasing)
Trans ID	Transaction that generated this record
Page ID	The database page being modified
Prev LSN	Link to the previous log record of the same transaction (backward chain)
Type	UPDATE, COMMIT, ABORT, CHECKPOINT
Undo	Old value (for undoing the change)
Redo	New value (for redoing the change)

Example Log

LSN 100: T1 BEGIN
LSN 101: T1 UPDATE Page 5, Undo: [A=100], Redo: [A=90]
LSN 102: T1 UPDATE Page 7, Undo: [B=200], Redo: [B=180]
LSN 103: T1 COMMIT
LSN 104: T2 BEGIN
LSN 105: T2 UPDATE Page 5, Undo: [A=90], Redo: [A=80]

---

Log Sequence Number (LSN)

An LSN is a unique, monotonically increasing identifier for each log record.

Properties

• Every log record has an LSN.
• Every database page stores the LSN of the most recent log record that modified it (called pageLSN).
• During recovery, comparing pageLSN with the log LSN determines if a change needs to be redone.

Why LSN Matters

If pageLSN >= logLSN, the page already contains the update — no redo needed. If pageLSN < logLSN, the update has not been applied — redo from log.

This comparison prevents re-applying changes that were already written to disk (idempotent recovery).

---

WAL Protocol Steps

A transaction follows these steps:

BEGIN TRANSACTION
    ↓
Perform operation
    ↓
Write log record to WAL buffer (in memory)
    ↓
(Optional) Flush WAL buffer to disk
    ↓
Modify data page (in buffer pool)
    ↓
(Optional) Flush data page to disk
    ↓
COMMIT
    ↓
Flush all log records up to commit to disk (FORCE)

At commit: All log records must be on disk. Data pages may still be in the buffer pool (in memory).

---

WAL Flushing Strategies

Strategy	WAL Flush	Data Flush	Durability	Performance
Always	Every operation	Every operation	Highest	Lowest
At commit	At commit only	At commit only	High	Medium
Group commit	Batch multiple commits	Background	High	High
Asynchronous	Background	Background	Risk of losing committed data	Highest

Real databases: Use group commit with periodic WAL flushes (e.g., PostgreSQL commit_delay, MySQL innodb_flush_log_at_trx_commit).

---

Checkpoints

A checkpoint is a point in the log where all data modifications up to that point have been flushed to disk.

Purpose

• Limit recovery time: The DBMS only needs to replay log from the last checkpoint, not from the beginning of time.
• Reduce log space: Log records before the checkpoint can be truncated (archived or deleted).

How It Works

1. The DBMS suspends normal operations briefly.
2. All dirty pages in the buffer pool are flushed to disk.
3. A checkpoint log record is written: CHECKPOINT [LSN of first dirty page].
4. Old log records can now be recycled.

---

Types of Checkpoints

Consistent Checkpoint

• Halts all transactions.
• Flushes ALL dirty pages.
• Writes checkpoint record.
• Simple but disruptive.

Used by: Older databases (System R).

Fuzzy Checkpoint

• Does NOT halt transactions.
• Flushes only the dirty pages that existed at checkpoint start.
• Writes a checkpoint record noting which log records can be discarded.
• Non-disruptive.

Used by: All modern databases (PostgreSQL, InnoDB, SQL Server).

---

Checkpoint Frequency

Frequent Checkpoints	Infrequent Checkpoints
Faster recovery (less log to scan)	Slower recovery (more log to scan)
Higher I/O during normal operation	Lower I/O during normal operation
More disk writes	Fewer disk writes

Rule of thumb: Balance based on recovery time requirements and workload characteristics.

---

PostgreSQL Checkpoint Example

Checkpoint detail:
- WAL position: 0/16B37428
- Number of dirty buffers: 47
- Write duration: 0.134 seconds
- Sync duration: 0.027 seconds

PostgreSQL checkpoints are triggered by:

• checkpoint_timeout (default: 5 minutes).
• max_wal_size is exceeded.
• Manual CHECKPOINT; command.

---

ARIES Recovery Algorithm

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) is the standard recovery algorithm used by most databases.

Three Phases

1. Analysis Phase:  Scan log from last checkpoint → determine dirty pages and in-flight transactions.
2. Redo Phase:      Reapply all changes (from analysis LSN onward), making data consistent.
3. Undo Phase:      Roll back all transactions that did not commit (using undo log records).

ARIES is covered in detail in the next chapter.

---

Interview Deep Dive

---

Key Takeaways

• WAL: Log records must be on disk before data changes.
• Every log record has an LSN (Log Sequence Number) for ordering and idempotent recovery.
• Pages store pageLSN to track the last applied change.
• Checkpoints limit the log that must be scanned during recovery.
• Fuzzy checkpoints allow normal operation to continue during checkpointing.
• Group commit batches WAL flushes for better throughput.
• The WAL rule ensures both atomicity and durability (part of ACID).
• Modern databases use Steal + No-Force buffer management with WAL for recovery correctness.