Log-Based Recovery

A log is placed on stable storage. The log has referred a sequence of log records and maintains a record of update activities on the database. When a transaction Ti starts it registers itself by writing a log record. Before Ti executes the instruction write(X), a log record is written where V1 is the value of X before the write and V2 are the value to be written to X. The log record notes whether Ti has performed a write instruction on a data item Xj Xj which had value V1 before the write and will have value V2 after the write. When Ti finishes its last statement, the log record is written. We assume that the log records are written directly to stable storage which means they are not buffered. Two approaches using logs are deferred database modification and immediate database modification. The deferred database modification scheme records all modifications to the log but it defers all the writes to after the partial commit. The immediate database modification scheme allows database updates of an uncommitted transaction to be made as the writes get issued. It allows database modification to be outputted to the database while the transaction is still active. Since undoing may be needed update logs must have both old value and new value.Updated log record must be written before the database item is written. We assume that the log record is outputted directly to stable storage. It can be extended to postpone the log record output that long as prior to the execution of an output(B) operation for a data block B where all the log records corresponding to items B must be flushed to the stable storage. Problems in recovery procedure as discussed earlier are searching the entire log is time-consuming. We might unnecessarily redo the transactions which have already outputted their updates to the database. Streamline recovery procedure by periodically performing check-pointing is presented as output all log records currently residing in main memory onto stable storage, output all the modified buffer blocks to the disk and write a log record onto stable storage.

Summary

A log is placed on stable storage. The log has referred a sequence of log records and maintains a record of update activities on the database. When a transaction Ti starts it registers itself by writing a log record. Before Ti executes the instruction write(X), a log record is written where V1 is the value of X before the write and V2 are the value to be written to X. The log record notes whether Ti has performed a write instruction on a data item Xj Xj which had value V1 before the write and will have value V2 after the write. When Ti finishes its last statement, the log record is written. We assume that the log records are written directly to stable storage which means they are not buffered. Two approaches using logs are deferred database modification and immediate database modification. The deferred database modification scheme records all modifications to the log but it defers all the writes to after the partial commit. The immediate database modification scheme allows database updates of an uncommitted transaction to be made as the writes get issued. It allows database modification to be outputted to the database while the transaction is still active. Since undoing may be needed update logs must have both old value and new value.Updated log record must be written before the database item is written. We assume that the log record is outputted directly to stable storage. It can be extended to postpone the log record output that long as prior to the execution of an output(B) operation for a data block B where all the log records corresponding to items B must be flushed to the stable storage. Problems in recovery procedure as discussed earlier are searching the entire log is time-consuming. We might unnecessarily redo the transactions which have already outputted their updates to the database. Streamline recovery procedure by periodically performing check-pointing is presented as output all log records currently residing in main memory onto stable storage, output all the modified buffer blocks to the disk and write a log record onto stable storage.

Things to Remember

  • A log is placed on stable storage. The log has referred a sequence of log records and maintains a record of update activities on the database.
  • When a transaction Ti starts it registers itself by writing a log record.
  • Before Ti executes the instruction write(X), a log record <Ti, X, V1, V2> is written where V1 is the value of X before the write and V2 are the value to be written to X.
  • The log record notes whether Ti has performed a write instruction on a data item Xj Xj which had value V1 before the write and will have value V2 after the write.
  • We assume that the log records are written directly to stable storage which means they are not buffered. Two approaches using logs are deferred database modification and immediate database modification. 
  • The deferred database modification scheme records all modifications to the log but it defers all the writes to after the partial commit. 
  • The immediate database modification scheme allows database updates of an uncommitted transaction to be made as the writes get issued.
  • It allows database modification to be outputted to the database while the transaction is still active. Since undoing may be needed update logs must have both old value and new value.Updated log record must be written before the database item is written.
  • We assume that the log record is outputted directly to stable storage. It can be extended to postpone the log record output that long as prior to the execution of an output(B) operation for a data block B where all the log records corresponding to items B must be flushed to the stable storage.
  • Problems in recovery procedure as discussed earlier are searching the entire log is time-consuming. We might unnecessarily redo the transactions which have already outputted their updates to the database.
  • Streamline recovery procedure by periodically performing check-pointing is presented as output all log records currently residing in main memory onto stable storage, output all the modified buffer blocks to the disk and write a log record onto stable storage.

MCQs

No MCQs found.

Subjective Questions

No subjective questions found.

Videos

No videos found.

Log-Based Recovery

Log-Based Recovery

Log-Based Recovery

A log is placed on stable storage. The log has referred a sequence of log records and maintains a record of update activities on the database. When a transaction Ti starts it registers itself by writing a <Ti start> log record. Before Ti executes the instruction write(X), a log record <Ti, X, V1, V2> is written where V1 is the value of X before the write and V2 are the value to be written to X. The log record notes whether Ti has performed a write instruction on a data item Xj Xj which had value V1 before the write and will have value V2 after the write. When Ti finishes its last statement, the log record <Ti commit> is written. We assume that the log records are written directly to stable storage which means they are not buffered.
Two approaches using logs are:

  • Deferred database modification
  • Immediate database modification

Deferred Database Modification:

The deferred database modification scheme records all modifications to the log but it defers all the writes to after the partial commit. Assume that the transactions execute serially. Here the transaction usually starts by writing <Ti start> record to a log. A write(X) operation results in a log record that is being written as <Ti, X, V> where V is the new value for X. Note that the old value is not needed for this scheme.The write is not performed on X at this time but it is deferred. When Ti partially commits, <Ti commit> is written to the log. Finally, the log records are read and they are used to actually execute the previously deferred writes. Using log the system handles any failure that results in the information loss. The recovery schemes uses the following recovery procurers:

  • The redo (Ti) operation sets the value of all data items updated by transaction Ti to the new values. The new value can be found in the log.
  • The redo () operation must be impotent which means executing the operation for several times must be equivalent to executing it once. This is required if we are to generate correct behavior even if a failure occurs during a recovery process.

During recovery after a crash, the transaction needs to be redone if and only if both <Ti start> and <Ti commit> are there in the log. If we redo a transaction Ti(redo Ti) it sets the value of all data items updated by the transaction to the new values. Crashes may take place while the transaction is executing the original updates or while recovery action is being taken.
For example: transactions T0 and T1(T0 executes before T1):
T0: read (A)
A:- A - 50
Write (A)
read (B)
B:- B + 50
write (B)

T1: read(C)
C:- C - 100
write (C).

.

If log on stable storage at time of crash is as in case:

  • No redo actions need to be taken.
  • Redo (T0) must be performed since <T0 commit> is present.
  • Redo (T0) must be performed followed by redo(T1) since <T0 commit> and <Ti commit> are present.

Immediate Database Modification:

The immediate database modification scheme allows database updates of an uncommitted transaction to be made as the writes get issued. It allows database modification to be outputted to the database while the transaction is still active. Since undoing may be needed update logs must have both old value and new value.Updated log record must be written before the database item is written:

  • We assume that the log record is outputted directly to stable storage.
  • It can be extended to postpone the log record output that long as prior to the execution of an output(B) operation for a data block B where all the log records corresponding to items B must be flushed to the stable storage.

The display of updated blocks can take place at any time before or after the transaction commit. The order in which the blocks are outputted can be different from the order in which they are written..

  • Note: Bx denotes the block containing X.

Recovery procedure consists of two operations that take place and they are presented below:

  • Undo(Ti) restores the value of all the data items updated by Ti to their old values going backwards from the last log record for Ti.
  • Redo(Ti) sets the value for all the data items that updated by Ti to the new values going forward from the first log record for Ti.

Both of the operations must be idempotent.That is even if the operation is executed multiple times its effect is the same as if it is executed for once. It is needed since the operations may get re-executed during recovery. While recovering after failure:

  • Transaction Ti needs to be undone if the log contains the record <Ti start> and does not contain the record <Ti commit>.
  • Transaction Ti needs to be redone if the log contains both the record <Ti start> and the record <Ti commit>.

First, the undo operations are performed then only the redo operations are performed. Below, we show the log as it appears at three instances of time.

.

Recovery actions in each case above are:

  • Undo (T0): B is restored to 2000 and A to 1000.
  • Undo (T1) and redo (T0): C is restored to 700, and then A and B are set to 950 and 2050 respectively.
  • Redo (T0) and redo (T1): A and B are set to the values 950 and 2050 respectively. Then C is set to 600.

Checkpoint

Problems in recovery procedure as discussed earlier are below:

  • Searching the entire log is time-consuming.
  • We might unnecessarily redo the transactions which have already outputted their updates to the database.

Streamline recovery procedure by periodically performing checkpointing is presented below:

  • Output all log records currently residing in main memory onto stable storage.
  • Output all the modified buffer blocks to the disk.
  • Write a log record <checkpoint> onto stable storage.

During the recovery, we need to consider only the most recent transaction Ti that started before the checkpoint and then the transactions that started after Ti.

  • We should scan backwards from end of log to find the most recent <checkpoint> record
  • Continue to scan backwards till a record <Tistart> is found.
  • We only need to consider the part of log following above start record. The earlier part of a log can be ignored during recovery and can be erased whenever desired.

After identifying the transaction Ti the redo and undo operations to be applied to the Ti and all Tj that started execution after transaction Ti.

  • For all transactions starting from Ti or later with no <Ti commit> execute undo(Ti). This is done only in case of an immediate modification.
  • If we scan forward in the log for all the transactions starting from Ti or later with a <Ti commit> then it executes redo(Ti)..
  • T1 can be ignored since the updates are already outputted to disk due to the checkpoint.
  • T2 and T3 are redone
  • T4 is undone.

References:

  1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
  2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
  3. F.Korth, Henry. Database System Concepts. 6th edition.

Lesson

Crash Recovery

Subject

Computer Engineering

Grade

Engineering

Recent Notes

No recent notes.

Related Notes

No related notes.