ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging(1992)
February 26, 2023ARIES(Algorithm for Recovery and Isolation Exploiting Semantics)は、ログ先行書き込み(write-ahead-logging, WAL)によるSAVEPOINTまでの部分的なトランザクションのロールバック、レコード単位のロック、回復のためのアルゴリズムである。 ログの対象と粒度はページの更新であり、レコードには単調増加するLSN(Log Sequence number)をわりあてる。 レコードは直前の更新のレコードへのポインタであるPrevLSNも含み、あるレコードから以前の更新のレコードへ遡行できる。
ロールバックやリスタート時の更新は、通常時の更新とは別に、保証ログレコード(compensation log record, CLR)に記録される。 ARIESのCLSに記録された更新はUNDOされない。 一方、IMS, AS/400, DB2のCLSは、あるトランザクションが何度もロールバックされると、対応するCLSの更新をUNDOすることがある。
WALに記録された更新をUNDOすると、UNDO対象のWALレコードより1つ前のレコードへのポインタ(UndoNxtLSN)も、UNDO時の更新と一緒に、CLRに追加される。
以下の図は、ポインタによって繋がれたレコードを示す。
1, 2, 3は通常のトランザクションで生じたレコードで、2', 3’は2, 3のためのCLRのレコードである。
すべてレコードにはPrevLSNがあるため、先行するレコードに簡単にたどりつける。
UndoNxtLSNによって、トランザクションをどこまでUNDOできたか正確に記録する。
ARIESは定期的にチェックポイントを生成する。 チェックポイント時には、再起動時にREDOを開始する位置を特定するために、実行中のトランザクションとその状態、最後にログに書きこまれたLSN、永続化されていないバッファ上のデータをログに記録する。 再起動し、最後のチェックポイントから停止直前の状態に戻すときは、ディスクに書き込まれていないデータを永続化するためにREDOし、そのあとで、トランザクションをロールバックするためにUNDOを実行する。
REDO時には、はじめに、障害時にコミット済みでないまたは未確定(in-doubt)状態だったトランザクションもふくめたすべてのトランザクションを対象に、永続化されていないページのLSN(RedoLSN)を探す。 そのあと、RedoLSN以降のログに記録されているが永続化されていないページ上の更新を再実行する。 ARIESは、ページが更新されると、更新とLSNをログに書き出したあとに、ページにもLSNを書き込む。 チェックポイントから復旧したページ上のLSNがログ上のLSNよりも小さいページの更新をREDOする。 REDO時の更新は、UNDOする必要がないので、ログに記録されなない。
未コミットや未確定状態のトランザクションを障害時の直前状態まで戻したら、競合と劣後されたトランザクションをUNDOする。 ロールバックする各トランザクションの最大のLSNを見つけ、時系列とは逆順にUNDOする。 このとき、REDO時のように、ページ上のLSNとログ上のLSNを比べることはない。
論文のリンク 論文から図を引用しました。