ARIESとは、WALでページ更新しつつNo-forceかつStealな特性を持ち、Fuzzyなチェックポイントを獲得するという、Disk-Orientedな伝統的データベースでのベストプラクティスを集めた技法である。IBMのFellowであるDr. C.Mohanらによる"ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging"という論文が原著のようだ。
IBMのDB2やMircosoftのSQL Serverにて採用されている、とWikipediaには書いてあるが現状の製品の中では様々な改造が加えられて原型を留めてないかも知れない。現にSQL Serverのアーキテクチャはhekatonなどのインメモリ技術を取り入れているため、ARIESそのものはそのままでは使えない。
MySQLやPostgreSQLが採用しているアーキテクチャもARIESそのものとは少し違うが大筋で似ている所が多い。最先端ではないが、データベースアーキテクチャとして最も有名な１つであり、一時代を築いたと言っても過言ではない。
部分ロールバックや行レベルロックといった(当時としては)先進的な機能をうまく備えながら頑健なリカバリ機構を設計したという点で、現代のシステム設計においても大いに参考になるアルゴリズムである。

原著の論文を開くと、ちょっと面食らう程度には長いが、このアドベントカレンダー記事の中で繰り返し説明してきた内容がかなり含まれているので、今日の記事にはこれまでのアドベントカレンダーに含まれていなかったARIESの要素に絞って説明する。

ログ

ARIESはUndo情報とRedo情報の両方を保存する。トランザクションがページを書き変える際は必ずその操作に対応するログを先行して書き込む(WAL)プロトコルを採用している。なのでページを書き戻す際はIn-Placeな書き込みを行う、言い換えればページを読んだ場所にそのまま上書きする形で書き戻す。
ログは書き込む際にLog Sequence Number(以後LSN)という他と被らない(=ユニークな)単調増加する数値を割り当てられる。
ログフォーマットはPhysiological(物理論理)ログを採用することでコンパクトさと冪等性を両立する。各ページの中に「最後にこのページを更新したログのLSN(Last LSN)」を保存する領域があり、Redoログを適用する際はLast LSNと適用済みLogのLSNを見比べる事で、そのログを適用すべきか否かを判定できる。それによって冪等性が担保される。
トランザクションをアボートする際は、Undo情報に従って最近のログから順にUndoする操作をRedoする事で新たにログ(正しくは補償ログ)を書き込んでいく。LSNの数字を戻すような事はしない（というか複数のトランザクションがそれぞれ好き勝手にLSNの数字を増やすので、個別にロールバックする操作はこうするしかない）
ログの中に含まれる情報は以下である。

LSN: Log Sequence Number(ユニークな数値)
Type: 通常ログか補償ログか
TxID: トランザクションのID
PrevLSN: 同一トランザクションの前回のLSN
PageID: このログが更新するページのID
UndoNextLSN: Undo時に次にUndoすべきログのLSN、これは補償ログにしか含まれない
Data: UndoおよびRedoの情報。補償ログの場合Undoはなし

チェックポイント

Fuzzyなチェックポイントを行う。具体的にはDirtyなページを明示的に意図的に書きだす事はせず、純粋にリスタート時のリスタートのコストを低減させる事ができる情報を保存する。
ARIESはリスタートを簡潔にするために以下の情報を保存する。

トランザクションテーブル

現在進行途中状態であるトランザクションの一覧を含むテーブル。以下の情報を含む。

TxID: トランザクションのID
LastLSN: そのトランザクションが書いた一番新しいログのLSN
UndoNxtLSN: ロールバック時に次にUndoすべきログのLSN。このトランザクションが最後に書いたログが普通のログならLastLSNと同じ値になる。補償ログならその補償ログのUndoNextLSNを保持する。

ダーティページテーブル

現在メモリに写し取っているディスク上のページの内、ディスク上のデータと一致しない（つまりメモリに入ってから更新された）ページの一覧。

ページID: ページごとの固有ID
RecLSN: 最後に更新された時のLSN

これらの情報を保存する事でリカバリが高速に行える。
保存する際はbegin_checkpointログレコードを書き込み、上記の情報を書き込んだ後にend_checkpointログレコードを書き込む。end_checkpointのないチェックポイントは無効なものとして無視される。

リカバリ

Stealを許すバッファ管理戦略なので、DBプロセスがクラッシュからリスタートした時はDB内のページは一貫性がない。B+ツリーのノードをページに据えている戦略の場合、親ノードはsplitした結果のページを保存している一方でその子ノードが未splitのままである可能性だってあるかも知れない。DBの一貫性を取り戻す為に行う手続きは以下の3ステップで行われる

Analysisフェーズ
Redoフェーズ
Undoフェーズ

それぞれについて見ていくと

Analysisフェーズ

書かれているログを読み出しどの操作を行うべきか整理するフェーズである。

まずbegin_checkpointを探し、それを開始時点とする。
ログを最後まで読んで、トランザクションテーブルとダーティページテーブルを更新する。
ダーティページテーブルの持っているRecLSNの最小値がこれからRedoすべきログの開始時点である。

Redoフェーズ

前回システムがクラッシュした瞬間のDBのメモリ状態を復元するフェーズである。

DBのページに反映されていない情報に絞ってログのリプレイを先頭から順に行う
なお、コミットされていないトランザクションであってもすべて愚直にRedoする（そうしないとページのSplitなどで矛盾が生じるケースがあるので）
ひょっとしたらStealされた時にページが更新されていて特定のRedoが不要である可能性もあるのでLSNとページLSNを比較することで冪等な挙動となるようにする
この時、メモリ内のトランザクションテーブルの値も更新して、コミットが行われたトランザクションをトランザクションテーブルから消去する。

Undoフェーズ

クラッシュした瞬間のDBのメモリ状態での未コミットなトランザクションをすべて巻き戻して消去するフェーズである。

トランザクションテーブルに残っているトランザクションはすべてロールバックする
それらのトランザクションのLastLSNを参照し、そのログのUndo情報でページを更新する。
ページを更新する際に、Undo処理を行っている事自体をRedoとして保存する。これを補償ログという

これで一貫性のあるDBが復旧する。
ポイントは、Undo操作の中でRedoのログを書いているので、リカバリ途中のその瞬間に再びシステムがクラッシュしても次回のRedo対象が少々長くなるだけでUndoすべきデータの総量が減る事である。Undo操作はLastLSNによる過去のログを順番に参照するランダムアクセスであるため時間がかかりがちであるが、それを次回のRedoとして保存するので次回のUndoに掛かる時間が減る事である。
微妙な高速化に見えるかも知れないが、実地ではUndoは酷い時では数時間単位で掛かることすら起こりうるので重要となるケースもあるらしい。

Undoフェーズが始まった段階で、Dirtyなページを巻き戻すトランザクションとして実行されるため、Redoフェーズの段階で既に新しいトランザクションを受け付ける事ができる。Redoが終わった段階で、そのシステムはただの「Abortする先客がいっぱい居るだけ」の普通のトランザクションDBとして観測される。それによってユーザの体感でも素早い立ち上がりを見せかける事ができる。

まだいろいろ書き足りない事はあるが、エッセンスは書ききったと思う。
Exploiting Semanticsがどの部分のSemanticsをExploitしているのかは僕の中ではスッキリしていないが、おそらくUndoを補償ログのRedoとして行うことによってただのアボートと同じセマンティクスに落としこんでシステムの複雑化を避けたあたりではないかなと思う。

いろいろ調べ物をしていたら公開が15分ほど遅れてしまった…。