ARIES と fuzzy check pointing

Published: 2021/6/1


https://web.stanford.edu/class/cs346/2015/notes/ARIES_One.pdf を読んで fuzzy checkpointing について理解したのでメモ。

ARIES は、古典的な RDB における ACID を効率的に実現するためのベストプラクティスであって、 postgresql や mysql も大体こんな感じらしい。

  • WAL に Undo 情報と Redo 情報を記載する
    • Undo (ロールバック) の処理自体も WAL に記載される。
      • ただし、 Undo の Undo はトランザクションの定義上存在しないので、Redo 情報(とそれにまつわる情報)だけが WAL に入る。
  • page cache は evict のタイミングでディスクに書き戻す
    • checkpointing とかは関係なく書き戻す。 WAL にある undo/redo 情報と後述の checkpointing でリカバリー時になんとかする。
  • checkpoint を行なう際には、 Transaction テーブルと Dirty Pages Table を WAL に出力する
    • Transaction テーブルは、今現在実行中の Tx と、その Tx の Last LSN が記録される
      • rollback のときに、 Last LSN から順に undo する LSN を辿るために、この Last LSN は保持される
    • Dirty Pages Table には recLSN が記録される
      • recLSN == First LSN that made target page dirty.
  • リカバリーの際には、 Analysis, Redo, Undo のフェーズに分けて行なう
    • Analysis フェーズの処理:
      1. 最新の check point を WAL から取得。
      2. それ以降の WAL の内容を読み込んで、それらを適用した後に transaction テーブルと dirty pages tables がどうなるかをエミュレートする
        • Tx の開始や終了, Update による LSN 更新などを transaction テーブルを更新。
        • 新しく page を書き換えていた場合は dirty pages テーブルに追加。
      3. dirty pages テーブルから最小の recLSN を取得し、その LSN から次の Redo フェーズを開始する
    • Redo フェーズの処理
      • (ディスク上の) page LSN と, Redo 中の LSN を比較してもし Redo LSN の方が大きければそれを適用
        • dirty pages テーブルに含まれないことでもって、ディスクから LSN を読み込まなくても、ショートカットできたりもする。
      • 最後まで残ってた transaction テーブルの Tx たちの Abort を開始する(処理をWALに積む)
    • Undo フェーズの処理
      • 通常の Rollback と同じようにひたすらロールバックしていく

このように、今現在の dirty と Tx だけを WAL (など)に書き出しておいて、ひとまず今時点の page cache の内容を書き出してしまう形式の checkpoint の作成方法を、 fuzzy checkpointing と呼ぶ。

メモ

なので、 min(min(recLSN), min(Active Tx start LSN)) が、 Durability のために残しておかなければならない最も古い LSN。

メモ2

PostgreSQL における checkpointing の挙動。 定期的に full write しているのだが、 タイミングの問題でどの時点のページが書き出されるか分からない。 ただ、 fuzzy checkpointing なので問題ない。


Tags: データベースpostgresqlmysql

関連記事

About

エンジニアです。 仕事では Xincere Residence を作っています。 このサイトは個人のブログであり、所属団体の意見等とは関係がありません。

Tags