Principles of Transaction-Oriented Database Recovery(1983)
January 29, 2023クラッシュしたRDMSのディスクとバッファの状態をクラッシュ前の状態にもどす手法を体系化する。 体系は、Propagation, Buffer handling, EOT Processing, Checkpointingの4要素に着目して技術を分類する。
Propagationは、ブロックにページ上のデータを書き込むことである。 Propagationで書き込まれたデータは、RDMBSがクラッシュしてもログを使わずに復旧できる。 書き込み方は、もとのページのあったブロックとは別のブロックに更新後のページを書き込むアトミックな方法と、もとのページを上書きするアトミックでない方法がある。 アトミックであれば、propagationの結果は、すべてのデータを書き込めるか、すべて書き込まれないかのどちらかになる。 アトミックでなければ、一部データのみ書き込みが失敗することがある。 たとえば、ページテーブルへの参照を使い、propagationが終わった後に、ページテーブルへの永続的な参照先を、新しいページテーブルのアドレスに更新することで、アトミックな方法を実現できる。 もし、propagationとアドレスの更新の間にRDBMSがクラッシュしたら、ページテーブルはpropagation前の状態に戻る。
Buffer handlingは、ページをブロックに書き込むタイミングの決め方である。 RDBMSがクラッシュするとpropagationされていないバッファ上のデータは失われる。 バッファのデータが部分的に永続化されてRDBMSが異常終了すると、データの整合性がなくなる。 整合性を復元するため操作を取り消さなくてはならない(UNDO)が、UNDOの方法はbuffer hanlingによって変わってくる。 体系は、ディスクへの書き込みとpropagationを任意のタイミングで実行するパターンと、トランザクションの終了(EOT)まで書き込みを延期するパターンを区別する。 propagationがアトミックであれば、前者の場合はUNDOのためにログが必要であり、後者であれば不要である。
ACID特性のDurabilityを保証するならば、トランザクションで起きた更新は、トランザクション終了後にRDMBSがクラッシュしても、永続化されていなければならない。 トランザクションの終了後もpropagationされていないページを残す場合、クラッシュ後にトランザクションの操作を再現(REDO)し、ページを復元しなければならない。 そのためには、そのトランザクションのREDOログが必要になる。 一方、トランザクションの終了時に更新されたページをすべてpropagationするのであれば、不要である。 ただし、ディスクの故障などの物理障害からDurabilityを保証するには、物理的なDB間のレプリケーションをとらなければならず、障害からレプリケーションの内容を守るためのREDOログは依然として必要になる。
Checkpointingは、トランザクションのREDO時にある時点以前の操作のREDOを不要にするための手法である。 Checkpointingは、いつ実行するかによって4種類の区別があり、Transaction-Oriented Checkpoint(TOC), Transaction-Consistent-Checkpoint(TCC), Action-Consisitent Checkpoint(ACC), Fuzzy Checkpointがある。 TOCは、各トランザクションの終了時にトランザクションで更新されたページをpropagationする。 TCCは、前回のチェックポイント以降に発生し、すでに完了したすてのトランザクションをチェックポイントの対象にする。 TCCの開始時点で実行中のトランザクションがすべて完了するまで待機し、完了後にチェックポイントを生成する。 生成が完了するまで、新しいトランザクションの開始を延期する。 ACCは、TCCと同じく、複数のトランザクションを対象にする。TCCとの違いは、ページを更新する処理と処理に実行する点にあり、ACCは実行中のトランザクションもチェックポイントの対象する。 fuzzy checkpointは、バッファの状態をログに記録しておき、復元時には、ログからクラッシュ時点のバッファの状態を復元する。
論文のリンク