Shadow Paging Recovery Technique
Shadow Paging Recovery Technique
Shadow Paging is a database recovery technique that does not require a log in a single-user environment. Instead of recording changes in logs, it maintains two page directories to protect the database from failures.
This technique ensures that if a system crash occurs, the database can be restored simply by switching to the shadow directory, without performing UNDO or REDO operations.
1. Basic Idea of Shadow Paging
Shadow paging treats the database as a collection of fixed-size disk pages (blocks).
Example:
To manage these pages, the system maintains a page directory.
The directory contains n entries, where:
Every read or write operation accesses pages through this directory.
2. Directories Used in Shadow Paging
When a transaction begins, two directories exist.
| Directory | Description |
|---|---|
| Current Directory | Used by the running transaction |
| Shadow Directory | Backup copy of the database state |
Step when transaction starts
-
Current directory exists (points to latest pages).
-
It is copied to create a shadow directory.
-
The shadow directory is stored safely on disk.
-
The current directory is used by the transaction.
Important rule:
The shadow directory is never modified during transaction execution.
3. How Updates Work
When a transaction updates a page, shadow paging does not overwrite the original page.
Instead it follows this process.
Step-by-step update
-
Transaction wants to update page Pi
-
A new page copy is created.
-
The update is written to the new page.
-
The current directory entry is changed to point to the new page.
-
The shadow directory continues to point to the old page.
Thus two versions of the page exist:
| Version | Used by |
|---|---|
| Old Page | Shadow Directory |
| New Page | Current Directory |
4. Example of Shadow Paging
Suppose a database has 6 pages:
Initial directories:
Transaction updates Page 2 and Page 5.
New pages are created:
Directories now look like this:
| Page | Shadow Directory | Current Directory |
|---|---|---|
| 1 | P1 | P1 |
| 2 | P2 | P2' |
| 3 | P3 | P3 |
| 4 | P4 | P4 |
| 5 | P5 | P5' |
| 6 | P6 | P6 |
So:
-
Old pages remain unchanged
-
New pages contain updates
5. Recovery After System Crash
If the system crashes during transaction execution, recovery is very simple.
Recovery Steps
-
Discard the current directory
-
Discard newly modified pages
-
Restore the shadow directory
Since the shadow directory points to the original pages, the database returns to the state before the transaction began.
No:
-
UNDO
-
REDO
-
Log scanning
is required.
6. Commit Operation in Shadow Paging
When a transaction commits successfully, the system:
-
Replaces the shadow directory with the current directory
-
Deletes the old shadow directory
This means the updated pages become the official database pages.
Important requirement:
Switching directories must be done as an atomic operation (cannot be interrupted).
7. Why It Is Called NO-UNDO / NO-REDO
Shadow paging is classified as:
Because:
| Operation | Needed? |
|---|---|
| Undo | No |
| Redo | No |
Reasons:
-
Old data is preserved in the shadow directory
-
New updates are stored separately
So recovery only requires directory switching.
8. Shadow Paging in Multiuser Systems
In multiuser environments, shadow paging alone is not enough.
Additional mechanisms are needed:
-
Concurrency control
-
Logging
-
Checkpoints
These are required because multiple transactions may update pages simultaneously.
9. Advantages of Shadow Paging
1. No logging required
No need to maintain complex log records.
2. Fast recovery
Recovery only requires switching directories.
3. No UNDO or REDO
This simplifies recovery operations.
4. Simple crash handling
Restoring the shadow directory restores the database.
10. Disadvantages of Shadow Paging
1. Page fragmentation
Updated pages are written to new disk locations, causing scattered pages.
This reduces disk performance.
2. Directory overhead
Large databases require large page directories, which must be copied and stored.
3. Garbage collection problem
Old pages that are no longer used must be identified and freed.
This process is called garbage collection.
4. Difficult storage management
Maintaining related pages close together on disk becomes difficult.
5. Atomic directory switching required
If the system crashes while switching directories, database consistency may be affected.
11. Comparison with Log-Based Recovery
| Feature | Shadow Paging | Log-Based Recovery |
|---|---|---|
| Uses Log | No | Yes |
| Undo Needed | No | Yes |
| Redo Needed | No | Yes |
| Recovery Speed | Very Fast | Moderate |
| Disk Fragmentation | High | Low |
| Used in Modern DBMS | Rare | Very Common |
12. Summary
Shadow paging is a recovery technique that maintains two page directories:
-
Shadow Directory → old stable database
-
Current Directory → modified database
If a crash occurs:
-
The system restores the shadow directory.
If a transaction commits:
-
The current directory becomes the new shadow directory.
Thus shadow paging provides simple and fast recovery without using logs.
Shadow paging is a recovery technique that maintains two page directories—shadow and current. Updates are written to new pages without overwriting old pages. If a crash occurs, the shadow directory is used to restore the database, making it a NO-UNDO/NO-REDO recovery method.
Comments
Post a Comment