Explain the log based recovery scheme with deferred database modification approach?

Answer 1

Modifying the database without ensuring that the transaction will commit may leave the database in an inconsistent state. Consider transaction Ti that transfers $50 from account A to account B; goal is either to perform all database modifications made by Ti or none at all.

Several output operations may be required for Ti (to output A and B). A failure may occur after one of these modifications has been made but before all of them are made. To ensure atomicity despite failures:

First output information describing the modifications to stable storage without modifying the database itself; only then start modifying the database.

We study two approaches:

1. Log -based recovery

2. Shadow paging

We assume (initially) that transactions run serially, that are, one after the other.

A log:

• Sequence of log records

• Maintains a record of update activities on the database

• Kept on stable storage.

• When transaction Ti starts, it writes log record <Ti start>

• Before Ti executes write (X), it writes log record <Ti, X, VI, V2>:

• V1 is the value of X before the write (for undo)

• V2isthevaluetobewrittentoX

• When Ti commits, it writes log record <Ti commit>

• When Ti aborts1 it writes log record <Ti abort >

We assume for now that log records are written directly to stable storage (that is, they are not buffered)

The two approaches using logs are

1. Deferred database modification

2. Immediate database modification

Deferred Database Modification

• Records all modifications to the log

• Defers all the writes to after partial commit

• Transaction starts by writing <T1 start> record to log.

• A write (X) operation results in writing a log record <T1, X, V>

• V is the new value for X

Note: Old value is not needed for this scheme.

The write is not performed on X at this time, but is deferred. When T1 partially commits, <T1 commit> is written to the log. Finally, the log records are read and used to, 'actually execute the previously deferred write s.

During recovery after a crash, a transaction needs to be redone if and only if both < T1 start> and <T commit> are in the log. Redoing a transaction T, (redo Ti) sets the value of all data items updated by the transaction to the new values.

Crashes can occur while the transaction is executing the original updates, or while recovery action is being taken.

Example transactions T0 and T1 (T0 executes before T1):

T0: T1:

read(A) read(C)

A:A50 C:C100

Write(A) write (C)

read(B)

B:B+ 50

write(B)

Let the original value of A be 1000, that of B be 2000 and that of C be 700.

Let us handle the cases when crashes occur at three different instances as shown in (a),(b),(c)

Log at three instances of time (a), (b), (C):

Crash at

(a): No redo actions need to be taken

(b): redo (T0) must be performed since <T0 commit> is present

(c): redo (T0) must be performed followed by redo (T1) since

<T0 commit> and <T1 commit> are present

Immediate Database Modification

• Allows database updates of an uncommitted transaction.

• Undoing may be needed.

• Update logs must have both old value and new value.

• Update log record must be written before database item is written

We assume that the log record is output directly to stable storage output of updated blocks. It can take place at any time before or after transaction commit order in which

blocks are output can be different from the order in which they are written. Immediate Database Modification Example

Recovery procedure has two operations instead of one:

undo (Ti) restores the value of all data items updated by Ti to their old values,

going backwards from the last log record for Ti

redo (Ti) sets the value of all data items updated by Ti to the new values, going

forward from the first log record for Ti

Both operations must be idem potent, that is, even if the operation is executed multiple times the effect is the same as if it is executed once. It is needed since operations may get re executed during recovery.

When recovering after failure, transaction Ti needs to be undone if the log contains the record <Ti start>, but 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>. Undo operations are performed first, then redo operations.

Immediate Database Modification Recovery

Log at three instances of time (a), (b), (c)

Recovery actions in each case above are:

(a) undo (T0): B is restored to 2000 and A to 1000.

(b)undo (T1) and redo (T0): C is restored to 700, and then A and B are set to 950

and 2050 respectively.

(c) redo (T0) and redo (T1): A and B are set to 950 and 2050 respectively. Then C

is set to 600

Checkpoints

Problems in recovery procedure;

• Searching the entire log is time consuming

• We might unnecessarily redo transactions that have already output their updates to the database.

• Streamline recovery procedure by periodically performing

• Check pointing procedure

• Output all log records currently residing in main memory onto stable storage.

• Output all modified buffer blocks to the disk

• Write a log record <checkpoint > onto stable storage.

Checkpoint system failure

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

Log based recovery

The log, sometimes called the trail or journal, is a history of actions executed by the DBMS. Physically, the log is a file of records stored in stable storage, which is assumed to survive crashes; this durability can be achieved by maintaining two or more copies of the log on deferent disks (perhaps in different locations), so that the chance of all copies of the log being simultaneously lost is negligibly small.

The most recent portion of the log, called the log tail, is kept in main memory and is periodically forced to stable storage. This way, log records and data records are written to disk at the same granularity (pages or sets of pages).

Every log record is given a unique id called the log sequence number (LSN). As with any record id, we can fetch a log record with one disk access given the LSN. Further, LSNs should be assigned in monotonically increasing order; this property is required for the ARIES recovery algorithm. If the log is a sequential file, in principle growing indefinitely, the LSN can simply be the address of the first byte of the log record. For recovery purposes, every page in the database contains the LSN of the most recent log record that describes a change to this page. This LSN is called the page LSN.

A log record is written for each of the following actions:

1. Updating a page: After modifying the page, an update type record (described later in this section) is appended to the log tail. The page LSN of the page is then set to the LSN of the update log record. (The page must be pinned in the buffer pool while these actions are carried out.)

2. Commit: When a transaction decides to commit, it force-writes a commit type log record containing the transaction id. That is, the log record is appended to the log, and the log tail is written to stable storage, up to and including the commit record.2 The transaction is considered to have committed at the instant that its commit log record is written to stable storage. (Some additional steps must be taken, e.g., removing the transaction's entry in the transaction table; these follow the writing of the commit log record.)

3. Abort : When a transaction is aborted, an abort type log record containing the transaction id is appended to the log, and Undo is initiated for this transaction

4. End As noted above, when a transaction is aborted or committed, some additional actions must be taken beyond writing the abort or commit log record. After all these additional steps are completed, an end type log record containing the transaction id is appended to the log.

5. Undoing an update : When a transaction is rolled back (because the transaction is aborted, or during recovery from a crash), its updates are undone. When the action described by an update log record is undone, a compensation log record, or CLR, is written.

Every log record has certain fields: prevLSN, translD, and type. The set of all log records for a given transaction is maintained as a linked list going back in time, using the prevLSN field; this list must be updated whenever a log record is added. The trasID field is the id of the transaction generating the log record, and the type field oIviously indicates the type of the log record.

Additional fields depend on the type of the log record. We have already mentioned the, additional contents of the various log record types, with the exception of the update and compensation log record types, which we describe next. Update Log Records.

The pagelD field is the page id of the modified page; the length in bytes and the offset of the change are also included. The before-image is the value of the changed bytes before the change; the after-image is the value after the change. An update log record that contains both before- and after-images can be used to redo the change and to undo it. In certain contexts, which we will not discuss further, we can recognize that the change will never be undone (or, perhaps, redone). A redo-only update log record will contain just the after-image; similarly an undo-only update record will contain just the before-image.

Log File

Contains information about all updates to database:

• Transaction records.

• Checkpoint records.

Transaction records contain:

• Transaction identifier

• Type pf log record, (transaction start, insert, update, delete, abort, commit).

• Identifier of data item affected by database action (insert, delete, and update operations).

• Before-image of data item.

• After-image of data item.

• Log management information.

A technique often used to perform recovery is the transaction log or journal

1. Records information about the progress of transactions in a log since the last

consistent state.

2. The database therefore knows the state of the database before and after each transaction.

3. Every so often database is returned to a consistent state and the log may be truncated to remove committed transactions.

4. When the database is returned to a consistent state the process is often referred to as checkpointing.