Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 79 ยท Recovery

Shadow Paging Recovery

Learn shadow paging: current and shadow page tables, copy-on-write updates, commit by switching one pointer, and why most engines still prefer write-ahead logging.

Write-ahead logging recovers a database by keeping a separate record of changes and replaying or undoing it after a crash. There is a completely different idea, and it is much simpler to state: never overwrite committed data. Write every change to a new place, and make the new version official with a single, tiny, atomic write. If the system crashes before that write, the old version is still there, untouched. If it crashes after, the new version is complete.

This technique is called shadow paging. It needs no undo log and no redo pass. It was used in early systems such as IBM's System R, and the same copy-on-write idea lives on in modern storage engines and file systems. Understanding it also makes the design of write-ahead logging clearer, because each one is the answer to the other's weakness.

The two page tables

The database is stored as fixed-size pages on disk. Instead of locating a page by a fixed address, the system looks it up in a page table that maps each logical page number to its physical location. A single root pointer at a known disk address says which page table is the committed one.

Shadow paging in four steps

Copy the table Current table starts as a copy of the shadow table.
Write elsewhere Each update goes to a brand-new page.
Switch the pointer Commit moves the root to the new table.
Free the old pages Shadow pages become garbage.

One atomic write decides everything.

1 / 2

When a transaction starts, the system makes two page tables that are identical:

  • The shadow page table is the committed one. It is never modified while the transaction runs. The root pointer on disk names it.
  • The current page table is a working copy, held in memory. The transaction updates this one.

When the transaction writes logical page p, the system does not overwrite the physical page. It takes a free physical page, writes the new contents there, and points entry p of the current table at it. The old physical page, still referenced by the shadow table, is the shadow page. Reads by the transaction go through the current table and see its own writes; everyone else still reads through the shadow table.

Commit and recovery

To commit, the system does these things in order:

  1. Make sure all modified pages are on disk.
  2. Write the current page table to disk (to a free location, never over the shadow table).
  3. Write the root pointer so that it names the new table. This is a single, small write to one disk sector, which the hardware performs atomically (or fails to perform at all).
  4. Free the shadow pages that are no longer referenced.

The switch in step 3 is the commit point. After a crash, recovery is almost nothing: read the root pointer and use the table it names. If the crash came before step 3, the pointer still names the old table, and the transaction's new pages are unreachable garbage. If it came after, the pointer names the complete new table. There is no log to scan, no undo and no redo. Abort is equally cheap: throw the current table away.

Python Shadow paging with a simulated crash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the three states. Inside the transaction the new values are visible only through the current table. After the simulated crash, the committed state is exactly what it was: the transfer left no trace to clean up, because its two new pages were never reachable from the root. After the real commit, the root points at a table that includes both new pages. The last line is the cost of the method: seven pages were written to hold a database of three, and four of them are now garbage.

Drawbacks

Shadow paging is elegant, but it has real costs, and they explain why write-ahead logging won in general-purpose engines.

  • Commit overhead. A commit writes every modified data page and a page table. For a big database, the page table itself is large, so systems store it as a tree of page-table pages and copy only the path that changed. Even so, a one-row update writes several pages, where a log-based system writes one small log record sequentially.
  • Fragmentation. Updated pages move to new physical locations, so pages that were neighbours on disk are scattered over time. Sequential scans and clustered layouts suffer, and the system has to reorganize.
  • Garbage collection. Shadow pages and the pages of crashed or aborted transactions must be found and freed. Without a collector, the file only grows.
  • Concurrency. The simple scheme assumes one transaction at a time. With many concurrent transactions, whose changes may even share the same page, there is no single "current" table to switch. Committing one transaction would also publish half-finished changes from others. Practical systems need extra machinery, often including a log.
  • Data-page overhead for hot spots. Copying a whole page to change one row is wasteful. A log record only stores the change.
Python The cost of a commit: flat table versus tree of tables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a flat table, the cost of a commit grows with the size of the database, which is hopeless at ten million pages. With a tree of table pages (the table is itself a B+-tree-like structure, much like the ones in B-Trees and B+ Trees), the cost grows with the depth, which stays small. This tree-shaped copy-on-write design is exactly what some modern embedded key-value stores use, with two alternating root pages instead of one pointer.

Shadow paging versus write-ahead logging

Question Shadow paging Write-ahead logging
What does recovery do? Reads the root pointer Analyses the log, then redoes and undoes (ARIES)
Is there an undo or redo log? No Yes
What does a commit write? Changed pages, page table, root pointer Log records, flushed sequentially
Disk layout over time Fragments Stays in place
Concurrent transactions Hard Natural
Space overhead Extra page copies, garbage The log

Modern engines differ in detail, but the pattern is clear: log-based recovery is the default for busy multi-user servers, and copy-on-write designs appear where one writer at a time is acceptable (embedded stores, snapshot-based file systems) or where cheap consistent snapshots are a feature in their own right.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In shadow paging, which structure is the committed version of the database?

    The root pointer on disk decides. The current table is only a private working copy until the pointer is switched to it.
  2. 2. A crash happens after a transaction has written its new pages and its new page table, but before the root pointer was updated. What happens at recovery?

    The commit point is the single pointer write. Before it, the old state is still fully intact, so no undo is needed.
  3. 3. Why does shadow paging not need an undo log?

    Changes go to new pages, so the committed state is never damaged. Aborting means discarding the current table.
  4. 4. Which is a real drawback of shadow paging?

    Copy-on-write scatters pages and leaves old copies behind. Recovery, by contrast, is very fast.
  5. 5. Why do real systems store the page table as a tree of table pages?

    A flat table would have to be rewritten in full at each commit. A tree needs copying only one page per level.

Summary

  • Shadow paging never overwrites committed pages: updates go to new pages through a current page table, while the shadow page table keeps the old state.
  • Commit writes the new pages and table, then switches one root pointer atomically; that write is the commit point.
  • Recovery just reads the root pointer, and abort discards the current table, so neither needs undo or redo.
  • Costs: commit overhead, fragmentation, garbage collection and difficulty with concurrent transactions.
  • Page tables are stored as trees so that commit copies only a path; most multi-user engines still choose write-ahead logging.

Next: Disks, Pages and the Buffer Pool.