Mumbai University > Information Technology > Sem 5 > Advanced Database Management System

Marks: 10M

Year: May 2015

• Recovery algorithms are techniques to ensure transaction atomicity and durability despite failures. The recovery subsystem, using recovery algorithm, ensures atomicity by undoing the actions of transactions that do not commit and durability by making sure that all actions of committed transactions survive even if failures occur.

The recovery procedure involves flushing, its logs stored in data buffers into disk

• Strategies that can be used when flushing occurs.
• In-place updating: - Writes the buffer back to the same original disk location – overwriting the old value on disk.
• Shadowing: - Writes the updated buffer at a different disk location. – Multiple versions of data items can be maintained.

• Two main approaches in recovery process

  a) Log-based recovery using WAL protocol.

  b) Shadow-paging

1. Write-Ahead Logging (WAL)

   • Two types of log entry –log record- information for a write command. The information needed for UNDO.
   • A UNDO-type log entries including the old values (BFIM).
   • Since this is needed to undo the effect of the operations from the log.
   • The information needed for REDO.
   • A REDO-type log entries including the new values (AFIM).
   • Since it is needed to redo the effect of the operations from the log
   • In UNDO/REDO algorithms, both types of log entries are combined.
   • The log includes read commands only when cascading rollback is possible
   • WAL protocol for a recovery algorithm that requires both UNDO and REDO.

   • The before image of an item cannot be overwritten by its after image in the database on disk until all UNDO-type log records for the updating transaction –up to this point in time- have been force-written to disk.

     Ensures atomicity.

   • The commit operation of a transaction cannot be completed until all the REDO-type and UNDO-type log records for that transaction have been force-written to disk. Ensures durability.

2. Steal/no-steal-- Force/no-force Approaches

   • No-steal approach

      1) A cache page updated by a transaction cannot be written to disk before the transaction commits.-deferred update follows this approach-
     
       2)    The pin-unpin bit indicates if a page cannot be written back to disk
     

   • Steal approach

      1) An updated buffer can be written before the transaction commits.
     

     Used when the buffer manager replaces an existing page in the cache, that has been updated by a transaction not yet committed, by another page requested by another transaction.

      2) Advantage: avoid the need for a very large buffer space.
     

   • Force/No-Force approaches

      1) Force approach if all pages updated by a transaction are immediately written to disk when the transaction commits
     
      2) No-force approach otherwise.
     

     Advantage: an updated page of a committed transaction may still be in the buffer when another transaction needs to update it.-save in I/O cost. Typical database systems follow a steal/no-force strategy.

3. Checkpoints

   • In case of failure, the recovery manager requires that the entire log be examined to process recovery→ time consuming
   • A quick way to limit the amount of log to scan on recovery can be achieved using checkpoints.
   • A [checkpoint] record is written into the log periodically at that point when the system writes out to the database on disk all DBMS buffers that have been modified.
   • Hence, all transactions with [commit, T] entry in the log before [checkpoint] entry do not need to have their WRITE operations redone in case of crash.
   • Since all their update have been recorded in the DB on disk during check-pointing.

4. Shadow Paging

   • A recovery scheme
     • In a single-user environment, doesn’t require the use of log.
     • In multi-user environment, the log may be needed for concurrency control method.
   • The DB is made up of n fixed-size disk pages -blocks-

   • A directory with n entries where the ith entry points to the ith DB page on disk.

      All references –reads or writes- to the DB pages on disk go through the directory.
      The directory is kept in main memory if not too large.
     

   • When a transaction begins executing, the current directory is copied into a shadow directory and the shadow directory is saved on disk

      The current directory entries point to the most recent or current DB pages on disk
     

   • During transaction execution, all updates are performed using the current directory and the shadow directory is never modified.
   • When a write_item operation is performed A new copy of the modified DB page is created and the old copy is not overwritten. Two version, of the pages updated by the transaction, are kept. The new page is written elsewhere on some unused disk block. The current directory entry is modified to point to the new disk block. The shadow directory is not modified.

   • To recover from a failure Free the modified database pages and discard the current directory. Reinstate the shadow directory to recover the state of the DB before transaction execution. Return to the state prior to the transaction that was executing when the crash occurred.

   • To commit a transaction Discard the previous shadow directory.

   • NO-UNDO/NO-REDO technique since neither undoing or redoing of data items