Transcript Database Recovery

Database Recovery
Chuan Li
Database Recovery
What is Transaction
Database Recovery Overview
Failure Types
Recovery Techniques Implementation
Recovery Strategies
Recovery Techniques with Checkpoints
Database Mirroring
Summary
Transaction
1. Transaction Concept
2. Transaction Definition in SQL
3. Properties of Transactions
Transaction Concept


The minimum unit of collections of operations that
form a single logical step of work is called a
transaction. Since a transaction is indivisible, it
either executes in its entirety or not at all.
Transaction and Program



In a relational database, a transaction can be a SQL
statement, a set of SQL statements, or the entire program
An application typically contains multiple transactions
Transaction is the very basic unit of the recovery
and concurrency.
Transaction Definition in SQL

Explicitly defined
BEGIN TRANSACTION
SQL statement1
SQL statement 2
。。。。。
COMMIT
BEGIN TRANSACTION
SQL statement 1
SQL statement 2
。。。。。
ROLLBACK
Implicitly defined
When a user does not explicitly define transactions,
DBMS provides automatic divisions.

End of the Transaction
COMMIT
Normal end of the transaction
Commit all the transaction operations (read+update)
All transaction to the database update is permanent
ROLLBACK
Abnormal end of the transaction

Transaction failure happened in the process of operation,
and can't continue

Rollback all the update operations

Rollback to the start state
Properties of transactions(ACID)

Atomicity

Consistency

Isolation

Durability
1. Atomicity

Collections of operations that form a single logical
unit of work are called transactions.

Either all operations of the transaction are reflected
properly in the database, or none are.
2. Consistency
A transaction must preserve database consistency—if
a transaction starts from a consistent database, the
database must again be consistent at the end of the
transaction.
consistency
The database contains only the results of successful
transactions, ie, the committed transactions
unconsistency
The database contains the results of failed transactions,
ie, that are not committed, nor are they rolled back
Consistency & Atomicity
Funds-transfer ：account A  account B
 Define a transaction containing two operations
A
B
A=A-1
B=B+1

Correct state: two operations do both or none


Database is in a consistent state if do either all or
nothing.
If only one operation, the database will be in inconsistent
state .
3. Isolation
Concurrency is a normal state.
The execution of one transaction cannot be distracted
by other transactions

Operation and the use of data within one transaction
is isolated from other concurrent transactions

Can not interfere with each other between the
various transactions executing concurrently
T1
T2
① ReadA=16
②
ReadA=16
③ A←A-1
WriteA=15
④
A←A-3
WriteA=13
The modification of T1 was covered by T2.
4. Durability

Durability =Permanence

After a transaction completes successfully, the
changes it has made to the database persist,
even if there are system failures.

The following actions or failures should not have
any influence on the result.
Properties of transactions

How to ensure the ACID properties is the task of the
transaction management module

ACID damaging factors

When running multiple transactions in parallel, the operations of different
transactions may go across each other

A transaction is terminated by force
Database Recovery
What is Transaction
Database Recovery Overview
Failure Types
Recovery Techniques Implementation
Recovery Strategies
Recovery Techniques with Checkpoints
Database Mirroring
Summary
Recovery System Overview

Failure is inevitable





Disk failure
System error
Operator error
Malicious damage
Consequences

Transaction abort unexpectedly

Compromise the database consistency
Recovery System Overview(Cont.)

Countermeasures on Failure




DBMS Recovery sub-system
Ensure that the database can recover from the
erroneous status to some logically consistent
state
Ensure ACID properties
Recovery system is an important indicator which
measures the quality of the DBMS.
Database Recovery
What is Transaction
Database Recovery Overview
Failure Types
Recovery Techniques Implementation
Recovery Strategies
Recovery Techniques with Checkpoints
Database Mirroring
Summary
Transaction failure

Transaction failure


A transaction aborted during operation due to
various reasons and did not run to the normal
termination point
Common cause






bad input
overflow
resource limit exceeded
software error
deadlock
。。。。
Transaction failure recovery

When a transaction failure occurs, it may
have already written some modification
back to disk

Transaction failure recovery :UNDO

ROLLBACK
Clear all modifications of the transaction to
the database

System crash

System crash

Normal operations of the whole system suddenly
are destroyed
All the transaction processing halt

Loss of the transactional data

The content of nonvolatile storage remains intact,
and is not corrupted

Common cause


a bug in the database software or the
operating system
Operating errors

Specific types of hardware error （CPU
failure）

Power failure
Recovering from system crash

Restore all the modification by the incomplete
transaction
 When system reboots, the recovery program will
do UNDO to all incomplete transactions
 And as the result in the buffer was submitted by
completed transaction
 When system reboots, the recovery process
needs to REDO all committed transactions
Failure Classification

Transaction failure

System crash

Disk failure
Disk failure


Disk failure makes the data stored in the
peripheral storage part missing or lost
The probability of disk failure is smaller than
the previous two kinds of failures, but much
more destructive
Common cause

Disk failure

Disk damage

Head crash

Some potential errors in operating system

Transient and strong magnetic interference
Recovering from disk failure

Restore database from most recent backup

Consult the log and redo all transactions that
committed after the backup
Theory of recovery

Theory of recovery ：Redundancy


Using redundant data to rebuild the corrupted or
incorrect data
Recovery implementation technique ：
complexity

More than 10% of the code is the recovery system
code in a large database products
Recovery System
Transaction Concept
Database Recovery Overview
Failure Classification
Recovery Technique Implementation
Recovery Strategies
Recovery Technology Using Checkpoints
Database Mirroring
Summary
Recovery techniques
The key issues involved in the recovery
mechanism
1. Redundancy


Backup
Logging
2. How to use these Redundancy to
implement the database recovery
Backup
Backup Concepts
Backup Destinations
Backup Method
Backup concepts

Backup refers to the process that DBA periodically
copies all the database content into a new disk or
tape

These data are called backup data
Backup
failure point
backup
Running
─┼───────┼─────────────
Ta
load backup
Recovery
↓
running transaction
Tb
Tf
redo transaction
─┼───────┴－－－－－－－－－－－－→
Backup method
1． Static backup & Dynamic backup
2． Massive backup & Incremental backup
1．Static backup



No transaction may be active during the backup
procedure, database is in a consistent state
during backuping, and prohibiting any access or
modify events during the backuping
Advantages：Simple
Disadvantages ：reducing the availability of the
database
 Backup can only be performed after user
transaction completed, and
 User transaction can only start after backup
ends
Recovery using a static backup
failure point
static backup
running
running transaction
─┼───────┼─────────────
Ta
Tb
load backup
recovery
↓
─┼───────┥
Tf
Dynamic backup





Backup goes concurrently with user transactions
Backup performed on database even though it is
actively accessible to users and may currently be in a
state of being updated
Update is allowed during the backup period
Advantage
 No need to wait for the end of the running
transaction
 Will not affect the new transactions
Disadvantage

Can not guarantee the accuracy and validity of the backup
Dynamic backup

Recovery

Build the log file about transactions during
the backup period

Only backup copy and log file together can
restore the correct database
Recovery using a dynamic backup
running transaction
dynamic backup
Running
running transaction
↓
─┼───────┼─────────────
Ta
load backup
recovery
failure point
Tb
recovery with logs
━━━━━━╋ ━ ━ ━ ┥
Tf
Recovery using a dynamic backup
Ta
dynamic recovery
running
Tf
Tb
running transaction
failure point
─┼───────┼─────────────
logging
new log file
─────────┼─────────────

backup logs
load backup ，recovery with log backup
Recovery to
━━━━━━┥
Consistent state
Massive backup & Incremental backup



Massive backup: backup the entire database
Incremental backup :only backup the data which
was updated after the last backup
Massive backup & Incremental backup
 Massive backup is more convenient than
incremental backup
 But if database is large and transactions process
frequently, incremental backup is more efficient
3．Summary

Backup methods
Backup state
Backup
method
Dynamic backup
Static backup
Massive
backup
Dynamic massive
backup
Static massive
backup
Incremental
backup
Dynamic
incremental backup
Static
incremental
backup
Backup Strategy

backup is very time and resource consuming, so can
not be done very frequently

DBA should determine the backup period and method
according to the usages of database
For example：
 Dynamic incremental backup every night


Dynamic massive backup every week
Static massive backup every month
Recovery techniques
Backup
Logging
Logging
1. Content
2. Usage
3. Principle
Content
1. Log file concept

The log is a sequence of log records, and
maintains the history of all the update activities on
the database.
2. Log file format
log file based on records
log file based on data blocks
Content （Cont.）
3. The contents of the log file

BEGIN TRANSACTION marks of different transactions

COMMIT or ROLLBACK marks of different transactions

All the updates for different transactions

Internal update operations related to transactions
4. The log file based on record
Contents of each log record

Transaction Indicator

Operation Type （Insertion, deletion or modification）

Operand （Record Id, Block No.）

The old value of the data （for insert operation，it is null）

The new value of the data（for delete operation, it is null）
5. The log file based on data block
Contents of each log record

Transaction indicator

Operand （Record Id, Block No.）

The old value of the data block （for insert
operation，it is null）

The new value of the data block（for delete
operation, it is null）
Usage
1．Usage

Recover from transaction failures

Recover from system failures

Assist backup copies in recovering from disk
failures
Usage（Cont.）
2．Assist backup copies in recovering from disk
failures
 Static backup data is consistent data
 After the completion of the static backup, still
backup log file, when a disk failure occurred, we
can load the backup of the data and use the copy of
log to redo the completed transaction
 We can restore the database to the correct state
before failure at a certain time, but we do not need
to re-run the program that the transaction has been
completed
Usage（Cont.）
failure point
static backup
running
running transaction
↓
─┼──────┼──────────┼──
Ta
Tb
Tf
logging
└───────────┴──
load backup
Recover from
disk failure
recovery with log
keep running
──────┴－－－－－─－－－－－－－┴──────
logging
└──────
Usage（Cont.）
3．Recover from disk failure：LOG FILE + dynamic
backup

Dynamic database backup： backup log file of the
same point

Only backup copy and log file together can
restored the correct database

We can restore the database to the correct state
before failure at a certain time, but we do not need
to re-run the program that the transaction has been
completed
Principle

To ensure that the database is recoverable, we
must follow two principles

The logging order is accordance with the time
order of concurrent transactions

Write the log file firstly, then write the database

Writing log：writing the modification record to the log
file

Writing database：writing the modification to the
database
Principle（Cont.）

Why we write log file first

Writing database and log files are different operations

Failure may occur between the two operations

If database has been modified , but there was no
record in log file , we will never recovery that operation

If write logs, but did not change the database, the log
file recovery is only executed once more unnecessary
UNDO operations, that will not affect the validity of the
database
Recovery System
Transaction Concept
Database Recovery Overview
Failure Classification
Recovery Technique Implementation
Recovery Strategies
Recovery Technology Using Checkpoints
Database Mirroring
Summary
Recovery Strategies
Recover from transaction failure
Recover from system crash
Recover from disk failure
Recover from transaction failure

Transaction failure：The transaction is aborted
before running to the normal termination point

Recovery Method


Recovery subsystem uses log to undo the
modification of database performed by the
transaction
Transaction failure recovery is done automatically by
the system without user intervention
Steps of transaction failure recovery
1. Scan the log backward (that is, scan the log from the end to the
beginning), and find the update action performed by the transaction.
2. Perform
the inverse operation on the update action performed by the
transaction, that is write the “value before updating” in the log into
the database.

Insert operation, the “value before updating” is null, it is equivalent to the
delete operation.

Delete operation, the “value after updating” is null, it is equivalent to the
insert operation.

For modification operation, replace the “value before updating” with the
“value after updating”.
Steps of transaction failure recovery
3. Continue to scan the log backward, find
other update operations performed by the
transaction and do the same
4. This processing continues, until the start tag
ie, BEGIN TRANSACTION, is read, when
transaction failure recovery is complete
Recovering from system crash


Reasons of database state inconsistent
 Some incomplete transaction have already
modified the database
 Some database modification made by committed
transaction still in the buffer did not have time to
write database
Recovery method
 1. Undo all incomplete transactions
 2. Redo updates of all committed transactions
Recovering from system crash automatically
complete when the system restart , without
user intervention.
Steps of system crash recovery
1. Scan the log forwards
 Redo-list: transactions has already committed
before the failure point
T1, T3, T8…..
 Undo-list : in the failure point ,incomplete
transaction
T2, T4, T5, T6, T7, T9 …...
Steps of system crash recovery
2. Perform undo operation on transactions in
undo-list
Scan log backwards, performing undo on log
records of transactions found in undo-list
T2, T4, T5, T6, T7, T9 ……
3. Perform redo operation on transactions in
redo-list
Scan log forwards, performing redo on log
records of transactions found in redo-list
T1, T3, T8…..
Recover from disk failure
1. Reloading the data, bring the database to a
consistent state
2. Redo completed transaction
Recover from disk failure

Recovering steps
1. restore database from most recent backup ,
restore the database to the last consistent state

Loading a static backup into database, the
database will be in a consistent state

Loading a dynamic backup and log file in the
same time, using redo and undo operation to
make database in a consistent sate
Recover the database to a consistent
state with static backup
failure point
running transaction
static backup
Running
↓
─┼───────┼─────────────
Ta
Tf
Tb
Logging
└─────────────
load backup
recovery
━━━━━━┥
Recover the database to a consistent
state with dynamic backup
Ta
dynamic backup
running
Tf
Tb
running transaction
failure point
─┼───────┼─────────────
logging
new log file
─────────┼─────────────

backup logs
load backup ，recovery with log backup
Recovery to
━━━━━━┥
Consistent state
Recover from disk failure（Cont.）
2. Restore database from most recent backup.
Consult the log and redo all transactions that
committed after the backup

First we can scan the log file to find out the
transaction id in the failure point , set the id in the
redo queue.

Scan log forward from the start , perform the
transaction in the redo queue.
Recover from disk failure（Cont.）
Recover from disk failure requires DBA
intervention
Work of DBA

Reloading the last backup copies and log

Perform system restore command
The recovery of the specific operation is performed
by the DBMS
Recovery System
Transaction Concept
Database Recovery Overview
Failure Classification
Recovery Technique Implementation
Recovery Strategies
Recovery Technique Using Checkpoints
Database Mirroring
Summary
Recovery technique using
checkpoint
1. The issues raised
2. Checkpoint
3. Recovery Strategies using checkpoint
The issues raised

Two issues
 It’s time-consuming when scan the
whole log file
 REDO must re-run a transaction，waste
a lot of time
Solutions

Recovery technology using checkpoint

Add checkpoint in the log file

Add redo-log file

Recovery subsystem dynamically
maintain the log file during log’s
operation
Check Point Technical

Contents recorded by checkpoint



1.The current running transactions list when
creating checkpoint
2.The address of the nearest log of these
transactions
Redo log’s content
The address of every checkpoint in log
Log maintained when create a
checkpoint
1.
Flush all logs in the log buffer area to disk
2.
Write a checkpoint log in the log file
3.
Flush the data in data buffer to database
in the disk。
4.
Write the address of the checkpoint in the
log file to redo log file.
Create checkpoint

Periodically


According to a predetermined time intervals
aperiodicity

According to certain rules , such as when log files have filled half,
then build a checkpoint
Recovery strategy using checkpoints

When a transaction T submitted before a
checkpoint
Changes made by T have already been write to
database

Recovery strategy utilizing checkpoints
There is no need to execute redo when recovery
Recovery strategy using checkpoints
（CONT.）
Tc (check point)
T1
Tf(system crash)
Do not REDO
REDO
T2
UNDO
T3
T4
REDO
T5
UNDO
Recovery procedure utilizing
checkpoint
1.
Find the address of the latest checkpoint’s address
in the log file from the redo file
2.
Using this address find the last checkpoint’s record
in the log file
Recovery strategy utilizing checkpoints
（CONT.）
2. According to the checkpoint log build a
transactions list (ACTIVE-LIST) , ACTIVE-List
contains all the transactions which was running
when create the checkpoint


Build two transactions’ queen

UNDO-LIST

REDO-LIST
Put all transactions in ACTIVE-LIST to UNDOList. ，REDO-List remains empty。
Recovery strategy utilizing checkpoints
（CONT.）
3. Forward scan the log file from the checkpoint
address until the end of the log file.

If there is a new start transaction Ti , add Ti to UNDOLIST
If there is a log indicate Ti has committed, then
remove Ti from UNDO-List, and add Ti to
REDO-LIST
4. For each transaction in UNDO-LIST execute
UNDO，for each transaction in REDO-LIST
execute REDO.

Recovery System
Transaction Concept
Database Recovery Overview
Failure Classification
Recovery Technique Implementation
Recovery Strategies
Recovery Technology Using Checkpoints
Database Mirroring
Summary
Database Mirroring


Media error is the most serious error, affect the
availability of the database
 recover from media error is time-consuming
 In order to avoid media error, DBA must
periodically backup the database to other media
Method to improve the availability of the Database
 Database Mirroring
Database Mirroring（CONT.）

Database Mirroring

DBMS automatically copy the whole database or
some critical data to other disk.

DBMS automatically guarantee the consistency
between master and mirror. (Graph 7.5a)
Application of Database Mirroring

When Media error happens


DBMS automatically use mirror database to recover from
media error，there is no need to shutdown the system or
reload Database copy(graph 7.5b)
Under normal circumstances

Can be used to support concurrent operation(graph7.5a)

When one user add an exclusive lock on the database, other
user can read from the mirror
Database Mirroring（CONT.）
Recovery System
Transaction Concept
Database Recovery Overview
Failure Classification
Recovery Technique Implementation
Recovery Strategies
Recovery Technology Using Checkpoints
Database Mirroring
Summary
Summary


If database only contains the results of success
transactions, then the database is in a consistent
state. Consistency is the basic requirement of a
database.
Transaction is a logical unit of database
 DBMS guarantee all transactions’ atomicity,
consistency, isolation, and continuous property.
Summary(CONT.)

DBMS must guarantee the database recover from
transaction failures, system failures and media
failure.

Most frequently used Recovery technology is ：
database backup and log file

The basic principles of recovery ：Utilize the
Redundant data from backend copy, log files and
database mirroring to rebuild database
Summary(CONT.)

Common Recovery Technology

recover from transaction error


recover from system error


UNDO
UNDO + REDO
recover from media error

Reinstall the backup and restore to a consistent state +
REDO
Summary(CONT.)

Improve the efficiency of recovery technology

Checkpoint

Can improve the efficiency when recover from
system error


Can improve the efficiency when recover from
media error using dynamic backup
Database mirroring
 Database mirror can improve the efficiency
when recover from media error