Database Recovery System: Recovery Concept

Recovery from failure state refers to the method by which system restore its most recent consistent state just before the time of failure. There are several methods by which you can recover database from  failure state.  These are defined  as follows:

1. Log Based Recovery

In log based recovery system, a log is maintained, in which all the modifications of the database are kept. A log consists of log records. For each activity of database, separate log record is made. Log records are maintained in a serial manner in which different activities are happened. There are various log records. A typical update log record must contain following fields:

• Transaction identifler : A unique number given to each transaction.
• Data-item identifler : A unique number given to data item written.
• Date and time of updation.
• Old value : Value of data item before write.
• New value : Value of data item after write.

Logs must be written on the non-volatile (stable) storage. In log-based recovery, the following two  operations for  recovery  are required:

• Redo : It means, the work of the transactions that completed successfully before crash is to be performed again.
• Undo : It means, all the work done by the transactions that did not complete due to crash is to be undone.

The redo and undo operations must be idempotent. An idempotent operation is that which gives  same  result,  when executed  one  or  more  times.

For any transaction Ti, various log records are:

[Ti start] : It records to  log when Ti starts execution.

[Ti, Aj] : It records to log when Ti reads data item Aj.

[Ti, Aj, V1, V2] : It records to log when Ti     updates data item Aj, where V1 refers to old value and V2 refers to new value of Aj.

[Ti Commit] : It records to log when Ti    successfully commits.

[Ti aborts]  : It records  to  log if  Ti  aborts.

There are two types of Log Based Recovery  techniques and are discussed below :

1.1. Recovery Based on Deferred Database Modification

In deferred database modification technique, deferred (stops) all the write operations of any Transaction Ti until it partially commits. It means modify real database after Ti partially commits. All the activities are recorded in log. Log records are used to modify actual database. Suppose a transaction Ti wants to write on data item Aj, then a log record [Ti, Aj, V₁, V₂] is saved in log and it is used to modify database. After actual modification Ti enters in committed state.  In  this  technique,  the  old value  field  is  not  needed.

Consider the example of Banking system. Suppose you want to transfer 200 from Account A to B in Transaction T₁ and deposit 200 to Account C in T₂. The transactions T₁ and T₂ are  shown  in  Figure  10.1.

Suppose, the initial values of A, B and C Accounts are 500, 1,000 and 600 respectively, Various log  records for  T₁ and T₂ are as  shown  in Figure  10.2.

For a redo operation,  log must contain [Ti start]  and [Ti commit]  log records.

Crash will happen at any time of execution of transactions. Suppose crash happened

• After write (A) of  T₁: At  that  time log  records in  log are  shown  in Figure  3(a).

There is no need to redo operation because no commit record appears in the log. Log records of T₁ can be deleted.

• After write (C) of T₂ : At that time log records in log are shown in Figure 3(b). In this situation, you have to redo T₁ because both [T₁ start] and [T₁ commit] appears in log. After redo operation, value of A and B are 300 and 1200 respectively. Values remain same because  redo  is  idempotent.
• During recovery : If system is crashed at the time of recovery, simply starts the recovery again.

1.2. Recovery Based on Immediate Database Modification

In immediate database modification technique, database is modified by any transaction Ti during its active state. It means, real database is modified just after the write operation but after log record is written to stable storage. This is because log records are used during recovery. Use both Undo and Redo operations in this method. Old value field is also needed (for undo operation). Consider again the banking transaction of Figure 10.1. Corresponding log records after successful completion of T₁ and T₂ are shown in Figure 10.4.

• For a transaction Ti to be redone, log must contain both [Ti start] and [Ti commit] records.
• For a transaction Ti to be undone, log must contain only [Ti  start]

Crash will happen at any time of execution of transaction. Suppose crash happened.

• After write (A) of T₁ : At that time log records in log are shown in Figure 5(a). Here only [T₁ start] exists so undo transaction T₁. As a result, Account A restores its old value 500.
• After write (C) of T₂ : At that time log records in log are shown in Figure 5(b). During back-up record [T₂ start] appears but there is no [T₂ commit], so undo transaction T₂. As a result, Account C restores its old value 600. When you found both [T₁ start] and [T₁ commit] records in log, redo transaction T₁ and account A and B both keep their new value.
• During recovery : If system is crashed at the time of recovery simply starts recovery again.

1.3. Checkpoints

Both the techniques discussed earlier ensures recovery from failure state, but they have some disadvantages such as :

• They are time consuming because successfully completed transactions have to be redone.
• Searching procedure is also time consuming because the whole log has to be searched.

So, use checkpoints to reduce overhead. Any of previous recovery techniques can be used with checkpoints. All the transactions completed successfully or having [Ti commit] record before [checkpoint]  record need  not  to be  redone.

During the time of failure, search the most recent checkpoint. All the transactions completed successfully after checkpoint need to be redone. After searching checkpoint, search the most recent transaction Ti that started execution before that checkpoint but not completed. After searching that transaction, redo/undo transaction as required in applied method.

Advantages :  The major  advantages of  check points  are

1. No need to redo successfully completed transactions before most recent checkpoints.
2. Less searching required.
3. Old records can be deleted.

Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)