Shadow paging
Encyclopedia
In computer science
, shadow paging is a technique for providing atomicity and durability
(two of the ACID
properties) in database system
s.
A page in this context refers to a unit of physical storage (probably on a hard disk
), typically of the order of
to 
byte
s.
Shadow paging is a copy-on-write
technique for avoiding in-place updates of pages. Instead, when a page is to be modified, a shadow page is allocated. Since the shadow page has no references (from other pages on disk), it can be modified liberally, without concern for consistency constraints, etc. When the page is ready to become durable
, all pages that referred to the original are updated to refer to the new replacement page instead. Because the page is "activated" only when it is ready, it is atomic.
If the referring pages must also be updated via shadow paging, this procedure may recurse
many times, becoming quite costly. One solution, employed by the WAFL file system (Write Anywhere File Layout
) is to be lazy about making pages durable (i.e. write-behind caching). This increases performance significantly by avoiding many writes on hotspots high up in the referential hierarchy (e.g.: a file system superblock) at the cost of high commit latency.
Write ahead logging
is a more popular solution that uses in-place updates.
Shadow paging is similar to the old master-new master batch processing technique used in mainframe database systems. In these systems, the output of each batch run (possibly a day's work) was written to two separate disks
or other form of storage medium. One was kept for backup, and the other was used as the starting point for the next day's work.
Shadow paging is also similar to purely functional
data structures, in that in-place updates are avoided.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, shadow paging is a technique for providing atomicity and durability
Durability (computer science)
In database systems, durability is the ACID property which guarantees that transactions that have committed will survive permanently.For example, if a flight booking reports that a seat has successfully been booked, then the seat will remain booked even if the system crashes.Durability can be...
(two of the ACID
ACID
In computer science, ACID is a set of properties that guarantee database transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction...
properties) in database system
Database system
A database system is a term that is typically used to encapsulate the constructs of a data model, database Management system and database....
s.
A page in this context refers to a unit of physical storage (probably on a hard disk
Hard disk
A hard disk drive is a non-volatile, random access digital magnetic data storage device. It features rotating rigid platters on a motor-driven spindle within a protective enclosure. Data is magnetically read from and written to the platter by read/write heads that float on a film of air above the...
), typically of the order of
to byteByte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
s.
Shadow paging is a copy-on-write
Copy-on-write
Copy-on-write is an optimization strategy used in computer programming. The fundamental idea is that if multiple callers ask for resources which are initially indistinguishable, they can all be given pointers to the same resource...
technique for avoiding in-place updates of pages. Instead, when a page is to be modified, a shadow page is allocated. Since the shadow page has no references (from other pages on disk), it can be modified liberally, without concern for consistency constraints, etc. When the page is ready to become durable
Durability (computer science)
In database systems, durability is the ACID property which guarantees that transactions that have committed will survive permanently.For example, if a flight booking reports that a seat has successfully been booked, then the seat will remain booked even if the system crashes.Durability can be...
, all pages that referred to the original are updated to refer to the new replacement page instead. Because the page is "activated" only when it is ready, it is atomic.
If the referring pages must also be updated via shadow paging, this procedure may recurse
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
many times, becoming quite costly. One solution, employed by the WAFL file system (Write Anywhere File Layout
Write Anywhere File Layout
The Write Anywhere File Layout is a file layout that supports large, high-performance RAID arrays, quick restarts without lengthy consistency checks in the event of a crash or power failure , and growing the filesystems size quickly. It was designed by NetApp for use in its storage appliances...
) is to be lazy about making pages durable (i.e. write-behind caching). This increases performance significantly by avoiding many writes on hotspots high up in the referential hierarchy (e.g.: a file system superblock) at the cost of high commit latency.
Write ahead logging
Write ahead logging
In computer science, write-ahead logging is a family of techniques for providing atomicity and durability in database systems....
is a more popular solution that uses in-place updates.
Shadow paging is similar to the old master-new master batch processing technique used in mainframe database systems. In these systems, the output of each batch run (possibly a day's work) was written to two separate disks
Hard disk
A hard disk drive is a non-volatile, random access digital magnetic data storage device. It features rotating rigid platters on a motor-driven spindle within a protective enclosure. Data is magnetically read from and written to the platter by read/write heads that float on a film of air above the...
or other form of storage medium. One was kept for backup, and the other was used as the starting point for the next day's work.
Shadow paging is also similar to purely functional
Purely functional
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
data structures, in that in-place updates are avoided.
External references
- File System Design for an NFS File Server Appliance (The WAFL paper)