DBMS Notes
Shadow paging is an alternative recovery technique to log-based recovery. Instead of maintaining a transaction log to undo and redo operations, it maintains...
What is Shadow Paging?
Shadow paging is an alternative recovery technique to log-based recovery. Instead of maintaining a transaction log to undo and redo operations, it maintains two page tables simultaneously — a current page table that reflects in-progress changes, and a shadow page table that preserves the last committed state.
The key insight is simple: never modify data in place. When a transaction modifies a page, write the changes to a NEW disk block and update only the current page table. The shadow page table still points to the old (safe) version. On commit, swap the tables. On abort or crash, discard the current table and keep the shadow.
Advantages of Shadow Paging
| Advantage | Explanation |
|---|---|
| No UNDO/REDO logs | Recovery uses the shadow table directly |
| Instant recovery | Just use the shadow — no log scanning |
| Simple implementation | No complex log management or checkpoints needed |
| No WAL overhead | No need to write log records before data |
| Atomic commit | Single pointer write makes commit atomic |
Disadvantages of Shadow Paging
| Disadvantage | Explanation |
|---|---|
| Data fragmentation | Modified pages go to random free blocks (not sequential) |
| Garbage collection | Old blocks must be explicitly freed after commit |
| Difficult for concurrent transactions | Multiple transactions need separate page tables |
| Page table size | For large databases, the page table itself is large |
| Poor locality | Related pages scattered across disk after many updates |
Shadow Paging vs. Log-Based Recovery
| Feature | Shadow Paging | Log-Based Recovery |
|---|---|---|
| Recovery speed | Instant (use shadow) | Requires log scan |
| Runtime overhead | Copy-on-write for each page | Write log records |
| Concurrency support | Difficult for multiple transactions | Well-supported |
| Disk fragmentation | High (random new blocks) | Low (sequential writes) |
| Implementation complexity | Simple for single transaction | Complex but flexible |
| Industry adoption | Rare in practice | Universal standard |
| Scalability | Poor for large databases | Excellent |
Handling Multiple Transactions
Shadow paging was originally designed for single-transaction systems. Supporting multiple concurrent transactions is challenging because:
- Each transaction needs its own "current" page table
- Commit order must be managed carefully
- One transaction's shadow may conflict with another's current pages
Solutions in modern systems that use shadow-paging concepts:
- Copy-on-Write (COW) B-trees: Used in LMDB, SQLite WAL mode
- Multi-Version Concurrency Control (MVCC): PostgreSQL keeps old versions of rows
- Snapshot Isolation: Each transaction sees a consistent snapshot (conceptually similar)
Modern Applications of Shadow Paging Concepts
While pure shadow paging is rarely used in production databases, its ideas influence modern systems:
| ZFS (file system) | Copy-on-write for all file modifications |
| LMDB | Copy-on-write B+ tree, shadow root page |
| SQLite (WAL mode) | New pages written to WAL, original database is "shadow" |
| Btrfs | Copy-on-write file system with snapshots |
| PostgreSQL MVCC | Old row versions kept (conceptual similarity) |
Worked Example
| Initial state | Pages P1(balance=1000), P2(balance=2000) |
| Transaction | Transfer 500 from P1 to P2 |
| Step 1 | Read P1 from Block 10 (balance = 1000) |
| Step 2 | Allocate Block 55, write P1 with balance = 500 to Block 55 |
| Step 3 | Current table: P1 -> Block 55 |
| Step 4 | Read P2 from Block 20 (balance = 2000) |
| Step 5 | Allocate Block 62, write P2 with balance = 2500 to Block 62 |
| Step 6 | Current table: P2 -> Block 62 |
| Step 7 | COMMIT -> flush blocks 55, 62 -> update database pointer |
| Shadow | P1->Block10 (1000), P2->Block20 (2000) -- original state preserved! |
| New table | P1->Block55 (500), P2->Block62 (2500) -- committed state! |
Summary
Shadow paging provides conceptual simplicity — never modify in place, keep the old version as a safety net, and atomically switch to the new version on commit. While pure shadow paging is impractical for modern multi-user databases due to fragmentation and concurrency limitations, its copy-on-write philosophy lives on in file systems, embedded databases, and MVCC implementations.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Shadow Paging.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Database Management Systems (DBMS) topic.
Search Terms
dbms, database management systems (dbms), unit, shadow, paging, shadow paging
Related Database Management Systems (DBMS) Topics