シャドウページング

計算機科学におけるシャドウページングとは、データベースシステムにおいて原子性と永続性（ACID特性のうちの2つ）を実現するテクニックのひとつである。

ここでのページは物理的なストレージ（通常はハードディスク）上の一単位を意味している。
1ページのサイズは通常1キロバイトから32キロバイト程度である。

シャドウページングはin-placeなページの更新が行えない場合に使用される。
あるページに変更を加える際には、まずシャドウページがアロケートされる。
アロケートされた直後の状態では、シャドウページはディスク上の他のページから参照されていないため、一貫性制約等の制限を考慮せずに自由に変更が行える。
ページの変更が完了し永続化可能な状態になったら、変更前のページを参照している箇所全てを新しいページを参照するように変更する。
このような手順で処理を行えば、新しいページは永続化可能な状態にならない限り他から参照されないため、アトミックな変更が可能となる。

更新対象のページを参照している箇所をさらにシャドウページングによって更新する場合、上記の処理が再帰的に実行されることになり、処理に膨大な時間がかかる。
これを解決する方法として、WAFL(Write Anywhere File Layout)ファイルシステムではページの永続化処理を遅延させる（write-behind cachingを行う）方法が採用されている。
これにより、コミットのレイテンシは悪化するが、ファイルシステムのスーパーブロックなど、参照の階層の上位に位置し書き込みが集中するポイントへの書き込みを回避することができるため、パフォーマンスは劇的に向上する。

なお、in-placeな更新を行える環境では、ログ先行書き込みが使用されることの方が多い。

シャドウページングに類似のテクニックとして、メインフレームのデータベース上でバッチ処理を行う際に使用されるold master-new master方式が挙げられる。
この処理方式では、各バッチ（一日に一度実行されるものとする）の出力結果を2つのハードディスク（またはその他のストレージ）に出力する。
そのうちの一つはバックアップ用にとっておき、もう一つは次の日の処理のスタート地点として使用される。

シャドウページングは、in-placeな更新を行わないという点で純粋関数型データ構造とも類似点が見られる。

外部リンク
 File System Design for an NFS File Server Appliance (WAFLに関するテクニカルレポート)

Category:データベースアルゴリズム
Category:OSのファイルシステム