ARIES と fuzzy check pointing

Published at: 2021/06/01

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

https://www.slideshare.net/suzuki_hironobu/recovery-11

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

tags: データベースpostgresqlmysql