Recovery and Logging II

Data Science 310

Boston University

Review: Caching

• Recently accessed database pages are cached in memory so that subsequent accesses to them don’t require disk I/O.
• There may be more than one cache:
  • the DBMS’s own cache (called the memory pool in BDB)
  • the operating system’s buffer cache

Review: What Is Recovery?

• During recovery, the DBMS takes the steps needed to:
  • redo changes made by any committed txn, if there’s a chance the changes didn’t make it to disk
    • durability: the txn’s changes are still there after the crash
    • atomicity: all of its changes take effect
  • undo changes made by any txn that didn’t commit, if there’s a chance the changes made it to disk
    • atomicity: none of its changes take effect
    • also used when a transaction is rolled back
• In order for recovery to work, need to maintain enough state about txns to be able to redo or undo them.

Review: Write-Ahead Logging (WAL)

• The write-ahead logging (WAL) policy:
  • before a modified database page is written to disk, all update log records describing changes on that page must be forced to disk
    • the log records are “written ahead” of the database page
• This ensures that the recovery system can restore the database to a consistent state.

Review: Undo-Redo Logging

• Here’s how it would work on our earlier example:

Review: Logical Logging

• We’ve assumed that update records store the old + new values of the changed data element.
• It’s also possible to use logical logging, which stores a logical description of the update operation.
  • example: increment D1 by 1
• Logical logging is especially useful when we use pages or blocks as data elements, rather than records.
  • storing the old and new contents of a page or block would take up a lot of space
  • instead, store a logical description
    • for example: “add record r somewhere on D1”

Review: Logical Logging (cont.)

• When we store old and new data values, the associated undo/redo operations are idempotent.
  • can be performed multiple times without changing the result
• Problem: logical update operations may not be idempotent.
  • example: if “increment D1 by 1” has already been performed, we don’t want to redo it
  • example: if “increment D1 by 1” has not been performed, we don’t want to undo it
  • example: if “add record r to page D1” has already been performed, we don’t want to redo it
• To ensure that only the necessary undo/redos are made, the DBMS makes use of the log sequence numbers (LSNs) associated with the update log records.

Review: Storing LSNs with Data Elements

• When a data element is updated, the DBMS:
  • stores the LSN of the update log record with the data element
    • known as the datum LSN
  • stores the old LSN of the data element in the log record

Review: Recovery Using LSNs

• During recovery, there are three LSNs to consider for each update record:
  • the record LSN: the one for the update record itself
  • the on-disk datum LSN for the data item
    • the one associated with it in the database file
  • the olsn: the old datum LSN for the data item
    • the one associated with it when the update was originally requested

The Backward Pass Using LSNs

• During the backward pass, we undo an update if:
  • the txn did not commit
  • datum LSN == record LSN
• When we undo, we also set: datum LSN = olsn

Which updates will be undone?

The Forward Pass Using LSNs

• During the forward pass, we redo an update if:
  • the txn did commit
  • datum LSN == olsn
• When we redo, we also set: datum LSN = record LSN

Which updates will be redone?

Undo-Only Logging

• Only store the info. needed to undo txns.
  • update records include only the old value

• Like undo-redo logging, undo-only logging follows WAL.
• In addition, all database pages changed by a transaction must be forced to disk before allowing the transaction to commit. Why? so that no redo operations will be needed

• At transaction commit:

1. force all dirty log records to disk

2. force database pages changed by the txn to disk

3. write the commit log record

4. force the commit log record to disk

• During recovery, the system only performs the backward pass.

Redo-Only Logging

• Only store the info. needed to redo txns.
  • update records include only the new value

• Like the other two schemes, redo-only logging follows WAL.
• In addition, all database pages changed by a txn are held in memory until it commits and its commit record is forced to disk.

• At transaction commit:
  • write the commit log record

• force all dirty log records to disk

• (changed database pages are allowed to go to disk anytime after this)

• If a transaction aborts, none of its changes can be on disk.
• During recovery, perform the backward pass to build the commit list (no undos). Then perform the forward pass as in undo-redo.

Comparing the Three Logging Schemes

• Factors to consider in the comparison:
  • complexity/efficiency of recovery
  • size of the log files
  • what needs to happen when a txn commits
  • other restrictions that a logging scheme imposes on the system
• We’ll list advantages and disadvantages of each scheme.

• Undo-only:
  • + smaller logs than undo-redo
  • + simple and quick recovery procedure (only one pass)
  • – forces log and data to disk at commit; have to wait for the I/Os

Comparing the Three Logging Schemes (cont.)

• Redo-only:
  • + smaller logs than undo-redo
  • +/– recovery: more complex than undo-only, less than undo-redo
  • – must be able to cache all changes until the txn commits
    • limits the size of transactions
    • constrains the replacement policy of the cache
  • + forces only log records to disk at commit

• Undo-redo:
  • – larger logs
  • – more complex recovery
  • + forces only log records to disk at commit
  • + don’t need to retain all data in the cache until commit

Checkpoints

• As a DBMS runs, the log gets longer and longer.
  • thus, recovery could end up taking a very long time!

• To avoid long recoveries, periodically perform a checkpoint.
  • force data and log records to disk to create a consistent on-disk database state

• during recovery, don’t need to consider operations that preceded this consistent state

Static Checkpoints

• Stop activity and wait for a consistent state.

1. prohibit new transactions from starting and wait until all current transactions have aborted or committed.

• Once there is a consistent state:

2. force all dirty log records to disk (dirty = not yet written to disk)

3. force all dirty database pages to disk

4. write a checkpoint record to the log

These steps must be performed in the specified order!

• When performing recovery, go back to the most recent checkpoint record.
• Problem with this approach? stopping all activity can significantly reduce performance!

Dynamic Checkpoints

Don’t stop and wait for a consistent state. Steps:

1. prevent all update operations

2. force all dirty log records to disk

3. force all dirty database pages to disk

4. write a checkpoint record to the log
   • include a list of all active txns

• When performing recovery:

• backward pass: go back until you’ve seen the start records of all uncommitted txns in the most recent checkpoint record

• forward pass: begin from the log record that comes after the most recent checkpoint record. why?

• all earlier changes were forced to disk by the checkpoint

Note: if all txns in the checkpoint record are on the commit list, we stop the backward pass at the checkpoint record

Example of Recovery with Dynamic Checkpoints

Example of Recovery with Dynamic Checkpoints (cont.)

• Could D4 have a datum LSN of less than 110? no. the checkpoint forces T1’s change (LSN 110) to disk.

Reviewing the Log Record Types

• Why is each type needed?
  • assume undo-redo logging

• update records: hold the info. needed to undo/redo changes

• commit records: allow us to determine which changes should be undone and which should be redone

• begin records: allow us to determine the extent of the backward pass in the presence of dynamic checkpoints

• checkpoint records: limit the amount of the log that is processed during recovery