Transcript transaction - Dalhousie University

CSCI 3140
Module 8 – Database Recovery
Theodore Chiasson
Dalhousie University
Recovery
• Database Recovery
– The process of restoring the database to a correct state in the event of a
failure
• Types of storage
– Main memory
• Primary storage
• Extremely fast
• Volatile
– Disk
•
•
•
•
Secondary storage
Online, random access
Fast
Non-volatile
– Tape
• Off-line, sequential
• Stable
– Optical drive
• Stable
• Random access
Recovery
• Transactions and Recovery
– Transactions represent the basic unit of work in a database
– Recovery manager ensures two of the four ACID properties
• Atomicity
• Durability
– To implement a read operation, the DBMS must
• Find the address of the disk block that contains the record with
primary key x
• Transfer the disk block into a database buffer in main memory
• Copy the value stored in the database buffer into a local variable
– To implement a write operation, the DBMS must
• Find the address of the disk block that contains the record with
primary key x
• Transfer the disk block into a database buffer in main memory
• Copy the value stored in a local variable into the database buffer
• Write the database buffer back to disk
Recovery
• Transactions and Recovery
– Buffers in main memory are volatile
– Buffers must be flushed to disk before changes become permanent
– Buffers can be flushed because the buffers are full, or a force-write can be
issue to ensure that a buffer is flushed immediately
• If a failure occurs after writing to the buffer but before the buffer has
been flushed, the recovery manager must check the status of the
transaction
– If the transaction was committed, the recovery manager uses REDO to
rollforward
– If the transaction was not committed, the recovery manager uses UNDO
to rollback.
Recovery
•
Buffer management
–
Replacement strategy
•
•
–
First-in-first-out (FIFO)
Least-recently-used (LRU)
Two variables assigned to each database buffer
•
pinCount
–
•
How many transactions are using this buffer
dirty
–
–
Set if a transaction has changed a value
Indicates that the buffer will have to be written back to disk
Recovery
•
When a page is requested, buffer manager checks if it is already in
a database buffer. If not, it will
(1)
(2)
(3)
Use a replacement strategy to choose a replacement buffer (cannot be
pinned). Set the replacement buffer’s pinCount to 1.
If dirty is set to 1 in replacement buffer, it must be flushed to disk before
loading the requested page
Load the requested page into the replacement buffer, set dirty to 0.
-
If a page is requested that is already pinned in memory, the
pinCount for the buffer is incremented.
-
When a transaction is finished with a buffer, it decrements the
pinCount
-
If the pinCount reaches zero, the buffer is unpinned (available for
replacement)
Recovery
•
Steal policy
–
•
Allows the buffer manager to write a buffer to disk before the transaction
has committed
No-steal policy
–
•
Must wait until the buffer is unpinned before choosing it for replacement
Force policy
–
•
Pages are flushed to disk before the transaction commits
No-force policy
–
•
The commit can occur even though the buffers have not been flushed to
disk
Simplest implementation is for force, no-steal
–
•
Requires large pool of buffers
Most DBMS implementations use steal, no-force
–
Requires the recovery manager to us REDO/UNDO to restore
consistent state after a failure
Recovery
A DBMS should provide the following facilities to assist with recovery:
–
A backup mechanism
•
•
–
Need to allow backup copies of the database and the log files without
necessarily having to stop the system first
Backup is typically offline storage, such as magnetic tape
Logging facilities
•
•
–
Log file is used to keep track of database transactions
Also called a journal
A checkpoint facility
•
–
Provides a stable, consistent starting point for the recovery manager
A recovery manager
•
Responsible for restoring the database to a consistent state in the event of a
failure
Recovery
•
Log file has
–
Transaction records:
•
•
•
Log file is used to keep track of database transactions
Also called a journal
Transaction records:
–
–
–
–
–
–
–
Transaction ID
Type of log record (start, insert, update, delete, abort, commit)
Id of data item affected by action (insert, delete, update operations)
Before-image of the data item (for update and delete operations)
After-image of the data item (insert and update only)
Log management information (e.g., pointers to previous and next log entries for
this transaction)
Checkpoint records:
•
•
•
Represent a synchronization point between the database and the log file
Contains a list of all the transactions that were active when the checkpoint
occurred
On recovery, recover from the most recent checkpoint
–
–
Checkpointing involves force-writing all logs and dirty buffers to disk
Can undo transaction that were active at the time of checkpointing, and redo all
transactions that committed since the checkpoint occurred
Recovery
•
If the database is severely damaged (disk crash), must recover from
backup
–
•
Log file should be on a different disk if possible
If database is corrupted due to a failure while transactions are
active, recover from log file
–
•
Use before-images to UNDO transactions that did not commit, use
after-images to REDO transactions that did commit since the last
checkpoint
Deferred update
–
Perform updates after commit
•
•
No action on aborts, use REDO on recovery
Immediate update
–
Change database buffers immediately
•
•
Requires use of UNDO for aborts and both REDO and UNDO for recovery
Shadow paging
–
Alternative to log files
Recovery
•
Deferred update
–
–
Updates are not written to the database until the commit point
Possible that updates didn’t make it to the database even though
transaction was committed
Log file is used to ensure recovery is possible
–
•
•
Write a transaction start record when the transaction starts
For every write operation, add a log entry with the after-image
–
•
•
–
Do not change the database buffers or the database itself yet
When a transaction is about to commit, write a transaction commit log entry,
write all of the transaction’s log entries to disk, then commit by using the log
entries to update the database
If a transaction aborts, ignore the log entries for the transaction and do not
perform writes
In event of a failure, go back to most recent checkpoint and:
•
•
•
Any transaction with a start transaction and a transaction commit entry in the
log must be redone
REDO writes the after-images in the transaction log to the database in the
order in which they appear in the log
Any transaction with a start transaction and an abort transaction entry in the
log can be safely ignored, since no writes were performed by these
transactions
Recovery
•
Immediate update
–
–
Updates are written to the database as they occur
Possible that updates didn’t make it to the database even though transaction
was committed
Also possible that updates made it to the database even though the transaction
did not complete
Log file is used to ensure recovery is possible
–
–
•
•
•
•
•
•
–
Write a transaction start record when the transaction starts
When a write operation occurs, store the before-image and after-image in the log file
Once the log file is written, write the changes to the database buffers
Updates to the database are written when the database buffers are flushed to the disk
When a transaction commits, write a transaction commit record to the log
If a transaction aborts, the log file is used to UNDO the writes it performed in reverse
order
Write-ahead log protocol
•
–
Log record is written BEFORE the buffers are updated
In event of a failure, go back to most recent checkpoint and:
•
•
•
Any transaction with a start transaction and a transaction commit entry in the log must
be redone
REDO writes the after-images in the transaction log to the database in the order in
which they appear in the log
Any transaction with a start transaction and no commit transaction entry in the log must
be undone by writing the before images of to the database in the reverse order in which
they were performed
Recovery
•
Shadow paging
–
–
–
–
–
–
Two pages are kept in memory for each database buffer
Changes are made to one of the pages – the other page (shadow page)
is not altered
The shadow page contains the before-image of the data values
When a transaction commits, the changed page becomes the shadow
page
Eliminates the need for the log file
Additional overhead in terms of memory fragmentation, garbage
collection