Recovery based on Deferred Immediate Update

Recovery based on Deferred and Immediate Update

AU: May-19, Marks 15

Before discussing the recovery algorithms (deferred and immediate update), let us see the concept of Log and REDO and UNDO operations.

Concept of Log

• Log is the most commonly used structure for recording the modifications that is to be made in the actual database. Hence during the recovery procedure a log file is 50 maintained.

• A log record maintains four types of operations. Depending upon the type of operations there are four types of log records -

1. <start> Log record: It is represented as <T_i, Start>

2. <Update> Log record

3. <Commit> Log record: It is represented as <T_i, Commit>

4. <Abort> Log record: It is represented as <T_i, Abort>

• The log contains various fields as shown in following Fig. 3.19.1. This structure is for <update> operation

• For example: The sample log file is

Here 10 represents the old value before commit operation and 20 is the new value that needs to be updated in the database after commit operation.

• The log must be maintained on the stable storage and the entries in the log file are maintained before actually updating the physical database.

• There are two approaches used for log based recovery technique - Deferred Database Modification and Immediate Database Modification. 

REDO and UNDO Operation

During transaction execution, the updates are recorded only in the log and in the cache buffers. After the transaction reaches its commit point and the log is force written to disk and the updates are recorded in the database.

In order to maintain the atomicity of transaction, the operations can be redone or

undone.

UNDO: This is an operation in which we restore all the old values (BFIM - BeFore Modification Image) onto the disk. This is called roll-back operation.

REDO:This is an operation in which all the modified values(AFIM - After Modification Image) are restored onto the disk. This is called roll-forward operation.

These operations are recorded in the log as they happen.

Difference between UNDO and REDO

Write Ahead Logging Rule

• Before a block of data in main memory is output to the database, all log records pertaining to data in that block must have been output to stable storage. This rule is called the Write-Ahead Logging (WAL)

• This rule is necessary because - In the event of a crash or ROLLBACK, the original content contained in the rollback journal is played back into the database file to revert the database file to its original state.

Deferred Database Modification

• In this technique, the database is not updated immediately.

• Only log file is updated on each transaction.

• When the transaction reaches to its commit point, then only the database is physically updated from the log file.

• In this technique, if a transaction fails before reaching to its commit point, it will not have changed database anyway. Hence there is no need for the UNDO operation. The REDO operation is required to record the operations from log file to physical database. Hence deferred database modification technique is also called as NO UNDO/REDO algorithm.

• For example:

Consider two transactions T₁ and T₂ as follows:

If T₁ and T₂ are executed serially with initial values of A = 100, B = 200 and C = 300, then the state of log and database if crash occurs

a) Just after write (B, b)

b) Just after write (C, c)

c) Just after <T₂, commit>

The result of above 3 scenarios is as follows:

Initially the log and database will be

a) Just after write (B, b)

Just after write operation, no commit record appears in log. Hence no write operation is performed on database. So database retains only old values. Hence A = 100 and B = 200 respectively.

Thus the system comes back to original position and no redo operation take place. The incomplete transaction of T₁ can be deleted from log.

b) Just after write (C, c)

The state of log records is as follows

Note that crash occurs before T₂ commits. At this point T₁ is completed successfully, so new values of A and B are written from log to database. But as T₂ is not committed, there is no redo (T₂) and the incomplete transaction T₂ can be deleted from log.

The redo (T₁) is done as < T₁, commit> gets executed. Therefore A = 90, B = 210 and C=300 are the values for database.

c) Just after < T2, commit>

The log records are as follows:

<T₁, Start>

<T₁, A, 90>

<T₁, B, 210>

<T₁, Commit>

<T₂, Start>

<T2, 6, 280>

<T₂, Commit>

← Crash occurs here

Clearly both T₁ and T₂ reached at commit point and then crash occurs. So both redo (T₁) and redo (T₂) are done and updated values will be A = 90, B = 210, C = 280.

Immediate Database Modification

In this technique, the database is updated during the execution of transaction even before it reaches to its commit point.

If the transaction gets failed before it reaches to its commit point, then the a ROLLBACK Operation needs to be done to bring the database to its earlier consistent state. That means the effect of operations need to be undone on the database. For that purpose both Redo and Undo operations are both required during the recovery. This technique is known as UNDO/REDO technique.

For example: Consider two transaction T₁ and T₂ as follows:

Here T₁ and T₂ are executed serially. Initially A = 100, B = 200 and C = 300

If the crash occurs after

i) Just after Write(B, b) ii) Just after Write(C, c) iii) Just after <T,,Commit>

Then using the immediate Database modification approach the result of above three scenarios can be elaborated as follows:

The contents of log and database is as follows:

The recovery scheme uses two recovery techniques -

i) UNDO (T_i): The transaction T, needs to be undone if the log contains <T_i,Start> but does not contain <T_i,Commit>. In this phase, it restores the values of all data items updated by T, to the old values.

ii) REDO (T_i): The transaction T_i needs to be redone if the log contains both <T_i,Start> and <T_i,Commit>. In this phase, the data item values are set to the new values as per the transaction. After a failure has occurred log record is consulted to determine which transaction need to be redone.

a) Just after Write (B, b): When system comes back from this crash, it sees that there is <T₁, Start> but no <T₁, Commit>. Hence T₁ must be undone. That means old values of A and B are restored. Thus old values of A and B are taken from log and both the transaction T₁ and T₂ are re-executed.

b) Just after Write (C, c): Here both the redo and undo operations will occur.

c) Undo: When system comes back from this crash, it sees that there is <T₂, Start> but no <T₂, Commit>. Hence T₂ must be undone. That means old values of C is restored.

Thus old value of C is taken from log and the transaction T₂ is re-executed.

c) Redo: The transaction T, must be done as log contains both the <T₁,Start> and <T₁,Commit>

            So A = 90, B = 210 and C = 300

d) Just after <T₂, Commit>: When the system comes back from this crash, it sees that there are two transaction T₁ and T₂ with both start and commit points. That means T₁ and T₂ need to be redone. So A = 90, B = 210 and C = 280

Example 3.19.1 Suppose there is a database system that never fails. Is a recovery manager require for this system? Why?

Solution:

1) Yes. Even-though the database system never fails, the recovery manager is required for this system.

2) During the transaction processing some transactions might be aborted. Such transactions must be rolled back and then the schedule is continued further.

3) Thus to perform the rollbacks of aborted transactions recovery manager is required.

Review Question

1. Explain deferred and immediate modification versions of the log based recovery scheme.   AU: May- 19, Marks 15