２フェーズコミット続き

技術的なこと

http://d.hatena.ne.jp/kuangue/20120220/1329664239:２フェーズコミットエントリの続き、２フェーズコミットやredo/undoログの勉強メモ。

入れ子型２フェーズコミット

２フェーズコミットには、多くの最適化された手法が提案されている。２フェーズコミットでは、N個の参加者がいる場合、commitに要するメッセージの数は、4Nになる。ネットワークが貧弱で、このようなやりとりがボトルネックになる場合には、この観点でより最適化された手法があるとうれしい。参加者が線形に順序だてて並んでいる場合には、トータルでメッセージのやりとりを２Nにすることができる。この手法は、入れ子型２フェーズコミットと呼ばれる。

  • 各参加者には、commit命令を処理するときに必要となる、シーケンス番号が割り当てられている。
  • 各参加者は、自分の次に情報をやり取りする参加者の名前を知っている。最後の参加者は自分が最後であることを知っている。

調整者がcommitを送信すると、各参加者はその情報をバケツリレーしていく。phase1が終了してた時点で、N-1個のメッセージが流れて、最後の参加者のところには、全員がphase1を成功したか、誰かが失敗しているかが分かる。成功している場合には、最後の参加者はphase2を実行して、成功したら一つ前の参加者に成功を返す。一つ前の参加者も同様に、phase2を行い、さらに前の参加者へ。続けていくと、全員が成功していると、シーケンス番号１の参加者は成功していることが分かるので、調整者に成功を返却する。よって、再起動時にはredoの必要はなくなる。もし、phase1で参加者のうちいくつかが失敗している場合には、undoを実行する必要がある。

二つの２フェーズコミット手法の比較

入れ子型２フェーズコミットが有効なのは、以下の場合。

  • 送受信のコストが高い、ブロードキャストできない
  • phase1とphase2並列性の必要性がない（これは、そのままレスポンスタイムが悪くても良いと言っている）。
  • 参加者とかcohort（==group）の構造が静的で、グローバルな情報を知っている。

このような理由から、入れ子型がよく使われている。翻って、ノーマルな方が良いのは、以下の場合。

  • ブロードキャストがプロセス間通信として普通に利用出来る場合（送信側を考えれば、）。
  • 並列性を上げて処理したい場合。
リカバリプロトコルのまとめ
  • 一貫性ロックプロトコルは、並列実行時の一貫性を担保する。
  • DO/REDO/UNDOログは、コミットされていないアクションに対応する。
  • WALは、非不揮発ストレージにログを先に書くことで、undo/redoがいつでも可能となる。
  • ２フェーズコミットは、自律的な参加者間のトランザクションコミットについて調整する。

WALと２PCの目的について、考える。

Logレコード有 オブジェクト書換済 redo undo
NO NO 2PCにより不可能 NONE
NO YES WALにより不可能 WALにより不可能
YES NO redo none
YES YES none undo

redoは、ログに記述されていない場合は、必要ない。１行目は、何も出来ないし、する必要もない。２行目は、ありえない。３行目は、redoするようだが、個人的には、undoという選択肢があるように思う。つまり、コミットが完了したかどうかで扱いが変わるのではないだろうか。コミットしたことがログとして残っているのなら、redo。逆に、(YES、YES）でもコミットしたことがログに記述されていないならundoというところかと思う。この部分は、自分で一度設計してみないと身にしみないかもしれないなあ。

リカバリマネージャの構造

二つの構成要素からなる。

リカバリシステムの目的は、二つある。マイナーなエラーに対して、実行中のトランザクションをundoneし、その作業は他のトランザクションに影響を与えない。マイナーなエラーとは、オペレーションのキャンセル、タイムアウト、デッドロック、一貫性制約、リソース制約などがある。

二つ目は、メジャーなエラーに対応する。障害などに対して、それまで行なってきた処理をできるだけ失うことなく、最新の状態に普及させる。データベースのキーとなる状態は、一定期間ごとに不揮発ストレージ（いままで、なんとなく非と書いてきたが、不だね）に書きこむ。そこに対する変更は、適宜ログに書き込む。障害が発生すると、まずは、不揮発ストレージから一貫性を満たした状態のデータベースを復元し、ログを使って最新の状態にする。

  • undoは、クラッシュの時にコミットされてないトランザクションに対して、実行する。
  • redoは、チェックポイントとクラッシュまでの間で、コミットが完了したトランザクションに対して、実行する。

もし、オンラインタイプの不揮発ストレージが破壊された場合は、テープに書き込んだアーカイブから復旧させることになる。このことを実現するための条件は、

  • システムに含まれるオブジェクトの完全なコピーを書きこんでおく。
  • dumpしておいたディスクイメージと現状の差分を記録しておく。この差分は、アドレスの上から順にとっておけば、復旧時にはシーケンシャルアクセスをすれば良い(change accumulationってのは、差分集合のことだと思うのだが、どうだろうか)。
トランザクションのセーブ

トランザクションのありのままをセーブする。だから、処理中のトランザクションをcommitしたり、ロックを開放したりはしない。

トランザクションのコミット

フェーズは二つに分かれる。最初のフェーズでは、redo/undoログを書き込む。次のフェーズで、コミット要求を各コンポーネントに通知しつつ、オブジェクトを更新し、ロックを解放する。フェーズ１では、各コンポーネントはAbort可能。もし、フェーズ１でOKを返却した場合、フェーズ２では、COMMITもABORTも受け入れる必要がある。

さっきの表が少し分かった気がする。チェックポイントは、トランザクションのSAVEを発生するが、コミットしたからといって、SAVEしているとは限らない。よって、REDOが必要な場合がある。逆に、トランザクションの途中状態がSAVEされる可能性があり、それはコミットしていないのにオブジェクトへの更新が行われている場合がある。と。実感としてわくためには、DBMSの実装を読んだほうが良さそうな気がしなくもない。

トランザクションのバックアップ

ログは、スタックのようなものだと捉えることができる。実際に、データを追加・更新するときには、pushと考え、ログからundoを行う場合には、popしていると考えることができる。チェックポイントまで、このpopを繰り返せば、状態を戻すことができる。大抵の場合、ひとつのトランザクションにひとつのログとはならないで、全トランザクションでログはひとつだけとなるので、あるトランザクションをundoしようとすると、不必要なところをスキップして、ランダムアクセスできるようにする必要がある。ので、tape driveは使えない。

チェックポイント

チェックポイントは、定期的、定量的、人力で発生する。目的は同じで、障害が発生したときにログから読み込む量を減らしたいということ。５分ごとにチェックポイントを発行するのが一般的。チェックポイントアルゴリズムが、システムを停止するようなものではないほうが良い。なぜなら、再起動はしたくないので、チェックポイントを頻繁には発行できなくなるから。チェックポイントアルゴリズムは、BEGIN_CHECKPOINTをログに書き込み、各コンポーネントの機能を呼び出して、END_CHECKPOINTを書きこむ。このレコードは、コンポーネントのレコードをひとまとめにする。コンポーネントは、ひとつ以上のレコードを書きこむかもしれない。結果として、チェックポイントから起動することができる。例えば、バッファマネージャは、バッファプールにあるバッファの名前を記録し、ファイルマネージャは、ファイルの状態を記録し、ネットワークマネージャは、ネットワークの状態を記録したり、トランザクションマネージャは、全てのトランザクションの名前を記録しておく。チェックポイントの書き込みが完了したときに、リカバリマネージャーは、起動時に見るファイルにこのチェックポイントのアドレスを記録しておく。このスタートファイルは重要なので、二つの実体があり、チェックポイントの度に、交互に書き込みが行われる。つまり、ひとつは、直前のチェックポイントのアドレス。もうひとつは、さらに一つ前のチェックポイントを書き込んでいる。システムが再起動すると、プログラムがロードされ、トランザクションマネージャは各コンポーネントを最初期化する。ネットワークを開始し、ファイルを開いてデータベースを再構築する。リカバリマネージャは、この段階で制御を渡される。リカバリマネージャは、最近おこなれたチェックポイントファイルのログ上の書き込みアドレスを、起動時に見るファイルから取得する。もし、チェックポイントの書き込み以後にログファイルに書き込みがなければ、正常終了したことになり、特にredo/undoは必要としない。リカバリマネージャーは、ログにリスタートレコードを書き込み、スケジューラに制御を渡し、システムは正常に起動される。

他方、チェックポイント時に処理途中のタスクがあったり、チェックポイント後に書きこまれたレコードがある場合、クラッシュからのリカバリとなる。トランザクションとチェックポイント、クラッシュポイントには、５つのタイプがある。ちょっと図を書くのが面倒なので、自分なりにまとめることにする。ここでは、Ti.begin、Ti.commitをそれぞれ、トランザクションTiの開始、コミットした時間を示すとする。CheckP、CrushPは、それぞれ、チェックポイント時刻、クラッシュポイント時刻とする。Ti.begn < Ti.commitは明らか。CheckP < CrushPを仮定しても一般性は失われない

  • T1: T1.commit < CheckP
  • T2: T2.begin < CheckP < T2.commit
  • T3: CheckP < T3.begin < T3.commit < Crush
  • T4: T4.begin < CheckP < CrushP < T4.commit(これは、コミットしてないの意味とする)
  • T5: CheckP < T5.begin < CrsuhP < T5.commit(これは、コミットしてないの意味とする)

この状況で、再起動時に何をするか話すのが、分かりやすい。T1、T2、T3は、コミット済みなのでredoされなければならない。T4、T5はコミットされていないので、undoされなければならない。ここまで来て思ったんだけど、トランザクションの内部処理がわかってないと、undo/redoがいまいちわからない気がしてきた。内部状態はisolationがserializableであれば、commitしない限り見えないけど、実は内部的には色々変更を加えているんだよね。多分、最後の最後にcompre-and-swap的な処理を用いて、atomicに変更したりしているんだろうけど、途中状態で終了すると、不必要な情報が残ってしまっているということなんだろう（テンポラリのバッファとか）。T1,T2,T3をwinner、T4,T5をloserと呼ぶ。

undo()の前に、redo()をしなければならない（えっと、この理由は、コミットしたらオブジェクトのログ上のシーケンスIDが新しくなる（閾値）、で、undoは自分のシーケンスIDが閾値未満であればそもそもスルーするというロジックであり、idempotent性を保証するための仕組みなので、かな？）。このことは、ログ全てを見てredoしなければいけないことを示している。全てのトランザクションに対してredoしなければならないので（うーん、前回のチェックポイントまででいいはずだけど）。再起動は早ければ早いほどよく、ここでは工夫の一つを紹介。再起動する際に、T未満の時刻のログについては再起動とは関係がないような時刻Tを探し出します。

この時間を探すため、あるデータベースオブジェクトにフォーカスして考える、ページPとする。クラッシュ後の再起動なので、 最新のページPは不揮発ストレージに反映されているかもしれないし、ないかもしれない。ページPは、閾値とともに書きこまれていて、その値をLSN(P)とする。もしも、winnerに属するトランザクションがLSN(P)以上の値でページPを更新しているとすると、ページPに対する更新はredoされなければならない。逆に、loserに属するトランザクションの場合であれば、undoされなければならない。メッセージの送信に関しても同様。もし、loserによって作成されたメッセージであれば、送信をキャンセル。もし、winnerによって作成されていて、未送信であれば、再送が必要。次に、5つのトランザクションについて、この観点で検討してみる。LSN(P)によって書き込みが行われた時刻をWPとする。

  • T1: T1.commit < WP
  • T2: T2.begin < WP < T2.commit
  • T3: WP < T3.begin < T3.commit < CrushP
  • T4: T4.begin < WP < CrushP < T4.commit
  • T5: WP < T5.begin < CrsuhP < T5.commit

注意するべきは、以下。T5の更新は、特にまだ何もされていないので、すでにundone。T1の更新は全て更新済みなので、redo済み。残りは、T2,T3,T4となる。T2,T3は、LSN(P)以降をredoしなければならない。T2の前半分は、ページPにすでに反映済み。他方、T4はLSN(P)に向けてundoされる必要がある。次のように正常でない場合には、スキップする。T2は、LSN(P)より前の状態に戻るかもしれない、そうすると、T2に対するundoが実行されるが、大した問題ではない。したがって、ページPに関わるredoログは、PSN(P)の時点か、それ以降に限られる（むーん、よくわからないぞー。redoログは、2PC+WALよりコミットの前に書かれるよね、redoログそのものは、PSN(P)以前も関係する気がする。と思ったけど、ここで言っているのは、それらに対しては、すでに反映済みだから、redoの必要はないということか。）。システムのチェックポイントにおいては、データマネージャは、MINLSNを記録しておく。それは、まだ書き込みが反映されていないページの中で最も古いLSNを示している。ので、Tは、最近のチェックポイントのMINLSNと定義すれば良い。ということで、再起動時にはチェックポイントレコードを読み込んで、チェックポイント時にアクティブなトランザクションをloserグループに入れれば良い。ログを前から後ろに読んでいく。COMMITのログレコードを見つけたら、そのトランザクションは、winner。BEGIN_TRANSACTIONを見つけたら、loserに入れる。ログを読みきれば、winner/loserの集合が得られる。次に、winnerに属するトランザクションをredoするため、ログをMINLSNから読み込む。次に、ログを後ろから前へ読み込み、loserのトランザクションに対して、undoを行う。２回読み込まないといけないのはどうかと思う。まあ工夫次第だね。

元々は２PCを学びたかったんだけど、予想外にリカバリマネージャの概要を知ることができてよかった。bigtableでは、redoログしか無いんだなと分かった。bigtableでは、データベースの状態そのものをチェックポイント化するわけではないので(MinorCompactionはあくまでメモリを吐き出すだけ)、障害が起きたときのメモリ上への再現が比較的簡単なんですね。自然とMINLSNのような仕組みを行うことになる。

データベースの実装って、奥深くて、面白いなぁ。