Shadow Paging

Shadow Paging

• This technique does not require LOG in single user environment

• In multi-user may need LOG for concurrency control method

• Shadow paging considers

• The database is partitioned into fixed-length blocks referred to as PAGES.

• Page table has n entries – one for each database page.

• Each contain pointer to a page on disk (1 to 1st page on database and so on…).

The idea is to maintain 2 pages tables during the life of transaction.

• The current page table
• The shadow page table

When transaction starts, both page tables are identical

• The shadow page table is never changed over the duration of the transaction.
• The current page table may be changed when a transaction performs a write operation.
• All input and output operations use the current page table to locate database pages on disk.

Advantages

• No Overhead for writing log records.
• No Undo /  No Redo algorithm.
• Recovery is faster.
  

Disadvantages

• Data gets fragmented  or scattered.
• After every transaction completion database pages containing old version of modified data need to be garbage collected.
• Hard to extend algorithm to allow transaction to run concurrently.
  

Checkpoints

Checkpoints

When System failure occurs

o We must consult log to determine those transaction that need to be redone and those transaction that need to be undone.

o We need to search entire log to determine this information.

There are two major difficulties with this

o Search process is time consuming

o Most of transaction that need to be redone have already written their update into the database. Although redoing them will cause no harm.

• To reduce this type of overhead, we introduced checkpoints.

• During execution system maintains the log, using one of the two techniques Deferred update or Immediate update.

• In addition, System periodically performs checkpoints, which requires following sequence of action to take place

• Output onto stable storage all log records currently residing in main memory.

• Output to the disk all modified buffer blocks

• Output onto stable storage a log record.

• Transactions are not allowed to perform any update actions such as

• Writing to a buffer block or

• Writing to log record

While a checkpoint is in progress.

• Checkpoint can be occur automatically and manually.

• Checkpoints continue to occur whenever the database is shut down (normal or immediate) or when a redo log switch occurs.

• To force a checkpoint, issue the following SQL command:

o alter system switch logfile;

o Alter system checkpoint;

Example :

• T1 can be ignored (updates already output to disk due to checkpoint)

• T2 and T3 redone.

• T4 undone

Immediate Update Method

Immediate update technique

• Database may be updated by some operations of a transaction before the transaction reaches its commit point.
• These operations are typically recorded in the log on disk by force writing before applied

  Transaction fail

  If a transaction fail after recording some change to the database, but before commit point, the effect of its operations on the database must be undone (transaction must be rollback)

  Need both undo and redo in recovery

  Immediate update is known as “UNDO/REDO Algorithm”to the database.
  

If fail occurs,

The executing (active) transaction at the time of failure may have recorded some Changes in the database.

The effect must be undone

Example

Example


Example :

Log Based Recovery

Log Based Recovery

• The most widely used structure for recording database modification is the log.
• The log is a sequence of log records, recording all the update activities in the database.
• In short Transaction log is a journal, which contains history of all transaction performed.
• Log contains Start of transaction, trans-id, record-id, type of operation (insert, update, delete), old value, new value, End of transaction that is commit or aborted.

Techniques for recovery

Log Based Crash Recovery

o Deferred update

Complete -> update

o Immediate update

Change -> update

o Checkpoints

Shadow Paging

Defferred Update method

Deferred update

• Do not physically update the database on disk until after a transaction reaches its commit point;
• Then updates are recorded persistently in the log and the written to the database.
• Before reaching commit point, the transaction updates are recorded in the local transaction workspace (buffers)
• During commit, the updates are first recorded persistently in log and then write to the database.

Transaction fail

o If transaction fails before reaching commit point, it will not have changed the database. (no need undo)

o It may necessary to REDO the effect of the operations of a committed transaction from the log, because their effect may not yet have been recorded.

• Deferred update is known as “NO-UNDO/REDO Algorithm”
  

Recovery based on deferred update

This technique postpone any actual update to the database until the transaction complete and reached check point.

During transaction execute

o Updates are recorded in log file and in cache buffer.

o After transaction reaches it commit point and the log file is forced to write to disk, the update are record to database.

Fail before commit,

no need undo.

Simplify recovery,

• Can not use in practice because unless transaction are short and each transaction change few times.
• May running out of buffer space because transaction change must be held in buffer until commit.

State

• A transaction can not change the database on disk until it reaches it commit point.
• A transaction does not reach its commit point until all its update operations are recorded in the log and the log is force written to disk.

Example of Deferred Update


Example


Example :