Chapter Four: Database Recovery Techniques PDF

Chapter Four: Database Recovery Techniques  Outline  Recovery Concepts  Recovery Concepts Based on Deferred Update  Recovery Concepts Based on Immediate Update  Shadow Paging  The ARIES Recovery Algorithm  Recovery in Multidatabase Systems 1...

Chapter Four: Database Recovery Techniques  Outline  Recovery Concepts  Recovery Concepts Based on Deferred Update  Recovery Concepts Based on Immediate Update  Shadow Paging  The ARIES Recovery Algorithm  Recovery in Multidatabase Systems 1 Database Recovery Techniques 12/30/2024  Database Recovery  Database recovery is the process of restoring database to a correct state in the event of a failure.  A database recovery is the process of eliminating the effects of a failure from the database.  Recovery, in database systems terminology, is called restoring the last consistent state of the data items. 2 Database Recovery Techniques 12/30/2024 Cont.  Need for Recovery Control  Two types of storage: volatile (main memory) and nonvolatile.  Volatile storage does not survive system crashes.  Stable storage represents information that has been replicated in several nonvolatile storage media with independent failure modes. 3 Database Recovery Techniques 12/30/2024  Types of failures  A failure is a state where data inconsistency is visible to transactions if they are scheduled for execution. The kind of failure could be:  System crashes, resulting in loss of main memory.  Media failures, resulting in loss of parts of secondary storage.  Application software errors.  Natural physical disasters.  Carelessness or unintentional destruction of data or facilities.  Sabotage.  4 Database Recovery Techniques 12/30/2024 Cont.  In databases usually a failure can generally be categorized as one of the following major groups:  Transaction failure: a transaction cannot continue with its execution, therefore, it is aborted and if desired it may be restarted at some other time. Reasons: Deadlock, timeout, protection violation, or system error.  System failure: the database system is unable to process any transactions. Some of the common reasons of system failure are: wrong data input, register overflow, addressing error, power failure, memory failure, etc.  Media failure: failure of non-volatile storage media (mainly disk). Some of the common reasons are: head crash, dust on the recording surfaces, fire, etc. 5 Database Recovery Techniques 12/30/2024 Cont.  The basic steps in performing a recovery are  Isolating the database from other users.  Occasionally, you may need to drop and re-create the database to continue the recovery.  Restoring the database from the most recent useable dump.  Applying transaction log dumps, in the correct sequence, to the database to make the data as current as possible. 6 Database Recovery Techniques 12/30/2024 Cont.  One can recover databases after three basic types of problems: user error, software failure, and hardware failure.  Each type of failure requires a recovery mechanism.  In a transaction recovery, the effect of failed transaction is removed from the database, if any.  In a system failure, the effects of failed transactions have to be removed from the database and the effects of completed transactions have to be installed in the database.  The database recovery manger is responsible to guarantee the atomicity and durability properties of the ACID property. 7 Database Recovery Techniques 12/30/2024  Transaction and Recovery  Transactions represent basic unit of recovery.  Recovery manager responsible for atomicity and durability.  If failure occurs between commit and database buffers being flushed to secondary storage then, to ensure durability, recovery manager has to redo (roll forward) transaction's updates.  If transaction had not committed at failure time, recovery manager has to undo (rollback) any effects of that transaction for atomicity.  Partial undo - only one transaction has to be undone.  Global undo - all transactions have to be undone. 8 Database Recovery Techniques 12/30/2024  Recovery Facilities  DBMS should provide following facilities to assist with recovery:  Backup mechanism: that makes periodic backup copies of database.  Logging facility: that keeps track of current state of transactions and database changes.  Checkpoint facility: that enables updates to database in progress to be made permanent.  Recovery manger: This allows the DBMS to restore the database to a consistent state following a failure. 9 Database Recovery Techniques 12/30/2024 Cont.  Restoring the database means transforming the state of the database to the immediate good state before the failure. To do this, the change made on the database should be preserved. Such kind of information is stored in a system log or transaction log file.  Log File  Contains information about all updates to database:  Transaction records.  Checkpoint records.  Often used for other purposes (for example, auditing). 10 Database Recovery Techniques 12/30/2024 Cont.  Transaction records contain:  Transaction identifier.  Type of 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.  Log file sometimes split into two separate random-access files.  Potential bottleneck; critical in determining overall performance. 11 Database Recovery Techniques 12/30/2024  Check pointing  Checkpoint: is a point of synchronization between database and log file.  All buffers are force-written to secondary storage.  Checkpoint record is created containing identifiers of all active transactions.  When failure occurs, redo all transactions that committed since the checkpoint and undo all transactions active at time of crash. 12 Database Recovery Techniques 12/30/2024 Recovery techniques  Damage to the database could be either physical and relate which will result in the loss of the data stored or just inconsistency of the database state after the failure.  For each we can have a recover mechanism:  If database has been damaged:  Need to restore last backup copy of database and reapply updates of committed transactions using log file.  Extensive damage/catastrophic failure: physical media failure; is restored by using the backup copy and by re executing the committed transactions from the log up to the time of failure.  13 Database Recovery Techniques 12/30/2024 Cont.  If database is only inconsistent:  No physical damage/only inconsistent: the restoring is done by reversing the changes made on the database by consulting the transaction log.  Need to undo changes that caused inconsistency.  May also need to redo some transactions to ensure updates reach secondary storage.  Do not need backup, but can restore database using before- and after- images in the log file. 14 Database Recovery Techniques 12/30/2024 Cont.  Recovery is required if only the database is updated. The kind of recovery also depends on the kind of update made on the database.  Database update: A transaction’s updates to the database can be applied in two ways:  Three main recovery techniques:  Deferred Update  Immediate Update  Shadow Paging 15 Database Recovery Techniques 12/30/2024  Deferred Update  Updates are not written to the database until after a transaction has reached its commit point.  If transaction fails before commit, it will not have modified database and so no undoing of changes required.  May be necessary to redo updates of committed transactions as their effect may not have reached database.  If a transaction aborts, ignore the log record for it.  And do nothing with transaction having a “transaction start” and “Transaction abort” log records 16 Database Recovery Techniques 12/30/2024 Cont.  A transaction first modifies all its data items and then writes all its updates to the final copy of the database.  No change is going to be recorded on the database before commit.  The changes will be made only on the local transaction workplace.  Update on the actual database is made after commit and after the change is recorded on the log.  Since there is no need to perform undo operation it is also called NO- UNDO/REDO Algorithm  The redo operations are made in the order they were written to log. 17 Database Recovery Techniques 12/30/2024  Immediate Update/ Update-In-Place  Updates are applied to database as they occur.  Need to redo updates of committed transactions following a failure.  May need to undo effects of transactions that had not committed at time of failure.  Essential that log records are written before write to database. Write- ahead log protocol.  If no "transaction commit" record in log, then that transaction was active at failure and must be undone.  Undo operations are performed in reverse order in which they were 18 written to log. Database Recovery Techniques 12/30/2024 Cont.  As soon as a transaction updates a data item, it updates the final copy of the database on the database disk.  During making the update, the change will be recorded on the transaction log to permit rollback operation in case of failure.  UNDO and REDO are required to make the transaction consistent.  Thus it is called UNDO/REDO Algorithm.  This algorithm will undo all updates made in place before commit.  The redo is required because some operations which are completed but not committed should go to the database.  If we don’t have the second scenario, then the other variation of this algorithm is called UNDO/NO-REDO Algorithm. 19 Database Recovery Techniques 12/30/2024  Shadow Paging  Maintain two page tables during life of a transaction: current page and shadow page table.  When transaction starts, two pages are the same.  Shadow page table is never changed there after and is used to restore database in event of failure.  During transaction, current page table records all updates to database.  When transaction completes, current page table becomes shadow page table.  No log record management  However, it has an overhead of managing pages i.e. page replacement issues have to be handled. 20 Database Recovery Techniques 12/30/2024  Algorithms for Recovery and Isolation Exploiting Semantics (ARIES)  ARIES is a recovery algorithm that is designed to work with a steal, no- force approach...  ARIES is one of few algorithm that is documented and explain how to deal with recovery for databases that utilize STEAL and NO-FORCE policies.  If a cache page updated by a transaction cannot be written to disk before the transaction commits, this is called a no-steal approach.  The pin-unpin bit indicates if a page cannot be written back to disk.  Otherwise, if the protocol allows writing an updated buffer before the transaction commits, it is called steal.  21 Database Recovery Techniques 12/30/2024 Cont.  Steal is used when the DBMS cache (buffer) manager needs a buffer frame for another transaction and the buffer manager replaces an existing page that had been updated but whose transaction has not committed.  If all pages updated by a transaction are immediately written to disk when the transaction commits, this is called a force approach. Otherwise, it is called no-force.  When the recovery manager is invoked after a crash, restart proceeds in three phases:  Analysis phase: This phase reads the last checkpoint record in the log to figure out active transactions and dirty pages at point of crash/restart.  A page is considered dirty if it was modified in memory but was not written to disk. 22 Database Recovery Techniques 12/30/2024 Cont.  REDO phase: Repeats all actions, starting from an appropriate point in the log, and restores the database state to what it was at the time of the crash.  UNDO phase: Undoes the actions of transactions that did not commit, so that the database reflects only the actions of committed transactions. 23 Database Recovery Techniques 12/30/2024 Principles of ARIES recovery Algorithm  There are three main principles behind the ARIES recovery algorithm:  Write-ahead logging: Any change to a database object is first recorded in the log;  the record in the log must be written to stable storage before the change to the database object is written to disk.  Repeating history during Redo: Upon restart following a crash, ARIES retraces all actions of the DBMS before the crash and brings the system back to the exact state that it was in at the time of the crash.  Then, it undoes the actions of transactions that were still active at the time of the crash (effectively aborting them).  Logging changes during Undo: Changes made to the database while undoing a transaction are logged in order to ensure that such an action is not repeated in the event of repeated (failures causing) restarts. 24 Database Recovery Techniques 12/30/2024 Cont.  ARIES maintains two data structures and adds one more field to log record:  Transaction table: It contains all the transactions that are active at any point of time (i.e. are started but not committed/aborted).  Dirty page table: Contains an entry for each page that has been modified but not written to disk. 25 Database Recovery Techniques 12/30/2024 Recovery in Multidatabase Systems  So far, we have implicitly assumed that a transaction accesses a single database.  In some cases, a single transaction, called a multidatabase transaction, may require access to multiple databases.  These databases may even be stored on different types of DBMSs;  for example, some DBMSs may be relational, whereas others are object- oriented, hierarchical, or network DBMSs.  In such a case, each DBMS involved in the multidatabase transaction may have its own recovery technique and transaction manager separate from those of the other DBMSs. 26 Database Recovery Techniques 12/30/2024 Cont.  To maintain the atomicity of a multidatabase transaction, it is necessary to have a two-level recovery mechanism.  A global recovery manager, or coordinator, is needed to maintain information needed for recovery, in addition to the local recovery managers and the information they maintain (log,tables).  The coordinator usually follows a protocol called the two-phase commit protocol, whose two phases can be stated as follows: 27 Database Recovery Techniques 12/30/2024 Cont.  Phase 1. When all participating databases signal the coordinator that the part of the multidatabase transaction involving each has concluded, the coordinator sends a message prepare for commit to each participant to get ready for committing the transaction.  Each participating database receiving that message will force-write all log records and needed information for local recovery to disk and then send a ready to commit or OK signal to the coordinator.  If the force-writing to disk fails or the local transaction cannot commit for some reason, the participating database sends a cannot commit or not OK signal to the coordinator. 28 Database Recovery Techniques 12/30/2024 Cont.  If the coordinator does not receive a reply from the database within a certain time out interval, it assumes a not OK response.  Phase 2. If all participating databases reply OK, and the coordinator’s vote is also OK, the transaction is successful, and the coordinator sends a commit signal for the transaction to the participating databases.  Because all the local effects of the transaction and information needed for local recovery have been recorded in the logs of the participating databases, recovery from failure is now possible. 29 Database Recovery Techniques 12/30/2024 Cont.  Each participating database completes transaction commit by writing a [commit] entry for the transaction in the log and permanently updating the database if needed.  On the other hand, if one or more of the participating databases or the coordinator have a not OK response, the transaction has failed, and the coordinator sends a message to roll back or UNDO the local effect of the transaction to each participating database.  This is done by undoing the transaction operations, using the log. 30 Database Recovery Techniques 12/30/2024  Thank You !!! 31 Database Recovery Techniques 12/30/2024