Shadow Paging

Shadow Paging

Shadow paging is considered as an alternate to a log-based recovery. This scheme is useful if transactions execute serially. The idea of shadow paging is to maintain two page tables during the lifetime of a transaction where the two page tables are the current page table and the shadow page table. The shadow paging stores the shadow page table in non-volatile storage in such a way that the state of the database prior to transaction execution may be recovered. Shadow page table is never modified during execution. To start with, both the page tables are identical. Only current page table is used for data item accessed during execution of the transaction. Whenever any page is about to be written for the first time we need to take the following things into account:

• A copy of this page is made onto an unused page.
• The current page table is then made to point to the copy.
• The update is performed on the copy.

To commit a transaction we need to do following things:

• Flush all modified pages in main memory to disk.
• Output current page table to disk.
• Make the current page table the new shadow page table. This can be done by keeping a pointer to the shadow page table at a fixed (known) location on disk. If we have to make the current page table the new shadow page table we simply need to update the pointer to point to current page table on disk.

Once the pointer to the shadow page table has been written transaction is committed. There is no need to recover after a crash as the new transactions can start right away by using the shadow page table. The pages that are not pointed to from current or shadow page table should be freed (garbage collected). Given below are the advantages of shadow-paging over log-based schemes:

• No overhead of writing log records.
• Recovery is trivial.

Disadvantages:

• Commit overhead: It requires multiple blocks to be output. Here the multiple blocks refer to the actual data blocks, the current page table and the disk address of the current page table. (Log based schemes need to output only the log records). It can be reduced by using a page table structured like a B⁺ There is no need to copy the entire tree rather it is needed to copy only the paths in the tree that leads to the updated leaf nodes. Committed overhead is high even with above extension. It is needed to flush every updated page and page table.
• Data Fragmentation: Shadow paging causes database pages to change location when they are updated. Data gets fragmented that is related pages get separated on disk.
• Garbage collection: After the completion of every transaction the database pages containing old versions of modified data needs to be collected as garbage. It is hard to extend algorithm for allowing the transactions to run concurrently. It is easier to extend log based schemes.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.