How Database Log Systems Work and Their Data Recovery Mechanisms

How Database Log Systems Work and Their Data Recovery Mechanisms

Problem Description:
The database log system is a core component that ensures data consistency and durability. Please explain in detail the working principles of database logs (such as redo logs and undo logs) and describe how these logs are used to implement crash recovery and transaction rollback.

Knowledge Point Explanation:

I. Core Functions of the Log System
Database logs record all modification operations performed on data, primarily addressing two key issues:

  1. Crash Recovery - After an abnormal database shutdown, logs are used during restart to restore data to a consistent state.
  2. Transaction Rollback - When actively rolling back a transaction, logs are used to undo modifications that have been made.

II. Detailed Explanation of Redo Log (重做日志)

Working Principle:

  1. Write-Ahead Logging (WAL): Before modifying any data page, a redo log must be written first.

    • Example: UPDATE users SET balance=100 WHERE id=1 (original balance=50)
    • Log content: [Transaction ID, Tablespace ID, Page Number, Offset, Old Value 50, New Value 100]

  2. Sequential Writing: Redo logs are written in an append-only manner.

    • Avoids random I/O, improving write performance.
    • Log files are reused circularly (overwriting the oldest logs when full).

  3. Flush Mechanism:

    • When a transaction is committed, the corresponding redo log must be persisted to disk.
    • Optimizes frequent flush overhead through group commit.

Example Scenario:

Transaction T1: UPDATE account A (100→200)
1. Write redo log: "T1 modified A from 100 to 200"
2. Modify the data page in the buffer pool (A=200)
3. Upon commit, force flush the redo log to disk
4. Data pages are flushed lazily (via checkpoint mechanism)

III. Detailed Explanation of Undo Log (回滚日志)

Working Principle:

  1. Record Old Versions: Before modifying data, the old value is first written to the undo log.

    • Log structure: [Rollback Pointer, Transaction ID, Copy of data before modification]

  2. Build Version Chain: Each row of data contains a DB_ROLL_PTR pointer.

    • Points to the previous version of that row's data.
    • Forms a multi-version chain, supporting MVCC (Multi-Version Concurrency Control).

  3. Rollback Operation:

    • Undo modifications step-by-step according to the undo log chain.
    • Delete the corresponding undo log after rollback is complete.

IV. Crash Recovery Process

Recovery Phases:

  1. Analysis Phase:

    • Scan the logs to identify the set of active transactions at the time of the crash.
    • Determine the range of transactions that need redo and undo.

  2. Redo Phase (REDO):

    • Starting from the most recent checkpoint, replay the redo logs of all committed transactions.
    • Ensure modifications of committed transactions are not lost.
    -- Redo Rule: Re-execute even if the data page is already updated
FOR EACH redo_log IN logs_since_checkpoint:
    IF redo_log.transaction_id IN committed_set:
        APPLY(redo_log)  -- Redo unconditionally

  3. Undo Phase (UNDO):

    • Perform rollback operations for uncommitted transactions.
    • Use undo logs to reverse data modifications.
    -- Undo Rule: Execute the undo chain in reverse
FOR EACH transaction_id IN active_set:
    WHILE has_undo_log(transaction_id):
        UNDO(prev_version)  -- Restore to the old version

V. Example Demonstration

Scenario: Fund transfer transaction (A transfers 100 to B)

START TRANSACTION;
UPDATE accounts SET balance=balance-100 WHERE id='A';  -- Step 1
UPDATE accounts SET balance=balance+100 WHERE id='B';  -- Step 2
COMMIT;

Log Recording Process:

  1. Before Step 1 executes:

    • Write undo log: [T1, accounts table, id=A row, balance=old value 1000]
    • Write redo log: [T1, modified A's balance from 1000 to 900]

  2. Before Step 2 executes:

    • Write undo log: [T1, accounts table, id=B row, balance=old value 500]
    • Write redo log: [T1, modified B's balance from 500 to 600]

  3. At commit: Flush redo log to disk, mark the transaction as committed.

Crash Handling:

  • If a crash occurs after Step 1: Use undo log to roll back the modification to A.
  • If a crash occurs during the commit process: Restore modifications to A and B during the redo phase.

VI. Log Optimization Techniques

  1. Checkpoint: Periodically flush dirty pages to disk, reducing the amount of log that needs to be replayed during recovery.
  2. Log Compression: Merge multiple operation records.
  3. Asynchronous Flushing: Non-critical logs can be persisted with delay.

Through this sophisticated logging mechanism, databases can guarantee ACID properties even in the event of failures, ensuring data is not corrupted due to unexpected circumstances.