In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, shadow paging is a technique for providing
atomicity and
durability (two of the
ACID
In computer science, ACID ( atomicity, consistency, isolation, durability) is a set of properties of database transactions intended to guarantee data validity despite errors, power failures, and other mishaps. In the context of databases, a sequ ...
properties) in
database system
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...
s. A ''page'' in this context refers to a unit of physical storage (probably on a
hard disk
A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnet ...
), typically of the order of 1 to 64
KiB
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
.
Shadow paging is a
copy-on-write
Copy-on-write (COW), sometimes referred to as implicit sharing or shadowing, is a resource-management technique used in computer programming to efficiently implement a "duplicate" or "copy" operation on modifiable resources. If a resource is dupl ...
technique for avoiding
in-place
In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output ...
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
Write Anywhere File Layout
The Write Anywhere File Layout (WAFL) is a proprietary file system 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 q ...
(WAFL) file system 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
In computer science, write-ahead logging (WAL) is a family of techniques for providing atomicity and durability (two of the ACID properties) in database systems. A write ahead log is an append-only auxiliary disk-resident structure used for crash ...
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 structure
In computer science, a purely functional data structure is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongl ...
s, in that in-place updates are avoided.
References
{{Reflist
Database algorithms
Computer file systems
fa:صفحه_بندی_سایه