2フェーズコミットの勉強
なんだかんだで、２フェーズコミットを実装したことがなくて、なんとなく分かっている状態なので、 J. Gray, Operating Systems, an Advanced Course, Bayer et. al. eds., Lecture notes in Computer Science 60, Springer-Verlag, 1978, pp. 393-481. の 5.8. RECOVERY MANAGEMENT を参考にしながら勉強することにする。このエントリは、そのメモ。が、なんで変わらないけど、読みづらいなあ。
エラーモデル
リカバリを考える上で重要なのは対処するべきエラーを知ることである。
ストレージのエラーモデル
まず、ストレージには、大きく分けて以下がある。
- 揮発性ストレージ：メモリ
- オンライン不揮発性ストレージ：ディスク。メモリより信頼度高い。
- オフライン不揮発性ストレージ：テープ。ディスクより信頼度高い。
ストレージは、固定長のページと呼ばれる単位で、配置・転送される。転送に対して、3つの結果がある、成功、部分的に失敗、失敗。どんなページでもエラーは生じるし、生じたらオリジナルのデータはなくなる。こういったエラーは、あとになって読み込む段になってわかる。N個の独立したページが、一度に破壊されるような状況は確率的に大分低いので無視して良い。N＝２でも、かなり確率は小さい（コモディティ製品だと、そうとも言えない気がするなぁ）。
コミュニケーションエラー
コミュニケーションは、セッション上のメッセージの集合として考える。メッセージの転送に際しては、正しく受信、正しくないが受信、受信してないの三つの結果がある。メッセージの転送では、各メッセージで成功しない場合がある。リカバリマネージャの役割は、これらのエラーに対して対処を行うこと。
リカバリマネージャの概要
トランザクションは、明示的にあるプロセスが割り当てられたり、すでに存在するプロセスがBEGIN_TRANSACTIONを発行した時に、開始される。トランザクションが初期化されたときに、リカバリマネージャはそのトランザクションをリカバリするのに必要なリカバリ 構造（内部変数位の意味だと思う）を割り当てるために呼び出される。このプロセスは、トランザクションの機能リストにリカバリマネージャが持つ、COMMIT、SAVE、BACKUPといった機能をバインドする。その後、トランザクションが行うすべてのアクションをリカバリログに記録する（ログマネージャ経由で）。更新に関わるアクションは、undo-logレコードとredo-logレコードをトランザクションログに書くべきだ。undo logレコードは、古いレコード値、redo logレコードは、新しいレコード値をそれぞれ書きこむ。トランザクションの保存時に、リカバリマネージャは保存ポイントIDと、必要な情報を記録する（あとで、この保存ポイントにもどることができるように）。
minor error(??どのよな種類かは明確ではなさそう??)が生じた場合に、トランザクションは保存ポイントまで戻す。この場合、アプリケーションには、保存ポイントからアプリケーションが行って来たアクションを全て忘れたことをアプリケーションに伝える。トランザクションが巻き戻ったり、アボートしたりした場合、トランザクションの状態によって、トランザクションをやり直したり、しなかったりする。
トランザクションが完全に成功した場合（Commitした場合）、クラッシュしたあとの復旧時に、このトランザクションは実行されることになる。コミットしていない状態で、システムがクラッシュしている時点で実行していたトランザクションは論理的にundone(abort)する。リカバリマネージャは以下のようなエラーに対処する必要がある。
- アクション失敗:ある種の呼び出しは、予測済みの条件に引っかかり失敗する。巻き戻されて、状態がクリアされて、呼び出し元に戻る。例として、引数エラー、リソース制限、データが無い。
- トランザクション失敗:トランザクションは、続けることができなくなって、アボートする。デッドロック、タイムアウト、保護エラー、ローカルシステムエラーなどがある。
- システムエラー:OSやハードウェアのエラーから、生じる。不揮発性のストレージがシステムエラー後の復旧のために利用出来る。
- メディアエラー：リカバリできないエラーが、ストレージで発生する。生じた場合には、ログからデータを、別のストレージに復旧する。パリティエラー、ヘッドクラッシュ、磁気メディアへのほこり、テープ自体を紛失(??)。自然災害などでメディアが壊れたことにより、ソフトからデータが読めなくなるのもこのエラーの範疇。
システムは、リカバリ可能なデータのコピーを安全な場所に保存しておく。あるオブジェクトが、メディアエラーにより壊れると、そのオブジェクトに対してアクセスするようなトランザクションは、全てアボートする。特殊なトランザクションが、オブジェクトを排他的に利用する。このトランザクションは、オブジェクトのコピーが出来てから発生した全てのアクション（変更の束と読んでみる）と最近作成したチェックポイントをマージする。変更の束は、２つの形をとる。システムログのREDOログか、システムログが圧縮されるときにREDOログから作成する「変更の束」かもしれない。メディアリカバリが終了したら、ロックを外して、通常の運用に戻る。
アーカイブコピーの作り方は、色いろある。リカバリマネージャは、チェックポイント設けて、システムにとって重要な情報を不揮発性のストレージに保存する。ここで作成するファイルを、warm start fileと読んだりする。システム再起動時には、以下の３つのモードがある。
リカバリプロトコル
リカバリ可能なオブジェクトに対して、トランザクションに含まれる全てのモジュールは、次のようなプロトコルに従う。
簡単なリカバリは、old-master/new-masterを用意して、new-masterが失敗したら、old-masterに変えれば良い。ただ、複数のトランザクションが並列で実行さ得れている場合、ひとつのトランザクション失敗でnew->oldにした場合、他の全てのトランザクションも含めてもとに戻すことになる。各トランザクションごとに、commit/abortを制御できたほうが良い。一貫性を保持している状態とその状態に対する実行中のトランザクションの集合が与えられたときに、トランザクションの部分集合を他のトランザクションに影響を与えずにundoすることができるとする。このような性質を実行中トランザクションバックアップと呼ぶ。…データベースそのものを更新しつつ、必要な情報はログで残す。リカバリ可能オブジェクトの更新時には、更新前と更新後の値を両方ログに書く。リードの時は必要ない。ということで、後で必要になれば、undo/redoを行うことが可能になる。更新に関するログエントリは、トランザクションごとにまとめられ、非揮発性のストレージある共通のシステムログに集められる。システムログは、二重化される。データベース本体とは別のストレージに作ることで、一度に故障する可能性は低くなる。
システムログの故障は考えないことにする。必要があれば、二重化、三重化する。リカバリ可能な命令は、以下のようなエントリを持つ必要がある。
- DOエントリは、アクションを実行し、undo/redoするのに十分なログレコードを記録する。
- UNDOエントリは、DOアクションによって記述されたログレーコに基づいてundoしたことを記録する。
- REDOエントリは、redoしたことを記録する
- DISPLAYエントリは、ログエントリを人間が読めるように変換する。
updateを例にして、考えてみる。ログに記述するべきことは、
- レコード名
- 古いレコード値
- 新しいレコード値
他に、ログを管理するモジュールに渡すべき情報として、
undoオペレーションは、古いレコード値で更新することで、インデックスやデータベースをリストアする。redoでは、新しい値で更新し、リストアする。ログレコードは、一度書かれたら二度と更新しない。読み込み時にはカーソルが用意され、どちら向きにでも移動することができる（カーソルの移動方向のこと）。UNDOでは、再起動時にちょっと問題がある。再起動されるたびにUNDOは繰り返さるが、再起動処理中に、また落ちて再起動すると、なんどもUNDOされる。REDOにも同じような問題がある。実はすでに、データベースに反映されているレコードを再実行してしまうかもしれない。WALはこのような問題を解決する。
WALプロトコル
メモリには、揮発性と不揮発性がある。ログに書きこむ前にデータベースを更新し、ログに書きこむ前の段階で障害等が起きたら、UNDO出来なくなる。コミット後にREDOログを書いたとしても同様。つまり、ログ書き込みは先に書き込まれないといけない。リカバリ可能なオブジェクトを変更するときには、必ずログを書く。ログは障害の仕方が独立となっているようなメディアに二重で書くことにより、信頼性が格段に増加する。
WALとは、
- まだコミットされていない更新に対して、リカバリ可能なオブジェクトを不揮発性ストレージに更新する前に、トランザクションは、不揮発性のログに対して、UNDOエントリを追記しなければならない。
- リカバリ可能なオブジェクトに対するコミットを行う前に、コーディネータモジュールは、undo/redoログを不揮発性ストレージに書き込む必要がある。そうすることで、コミットされたトランザクションがundo/redoどちらも可能。このプロトコルは、広くはメッセージついても同じように解釈される必要がある。リカバリ可能なメッセージをログに追記する前に送信してはならない。ログに書くことで、キャンセルや再送信が可能となるので。
WALの実装について。各ログエントリは、連続的なIDを持っている。各リカバリ可能なオブジェクトは、それまでに割り当てられた連続的なIDを持っている。オブジェクトが更新されるときには、新しいログレコードのIDを設定する。設定されているログIDを通り越して、ログに書き込まれる前にオブジェクトが非揮発型ストレージに書き込まれることはない。ログマネージャは、特定のIDまで一気に書きだす同期呼び出しをもつ。
システム再起動に、トランザクションはundoneやredoneするかもしれない。再起動は、エラーが発生した場合なんども繰り返すかもしれない。となると、undo/redoは何回も行うことになる。ログは、非揮発型ストレージよりも先に（オブジェクトの更新という意味かな）書き込まれるので、最初のundoはすでにもう実行済みと同じ状態かもしれない。redoに関しても同じで、すでにredo済みかもしれない。よって、undo/redoの処理を何回やったとしても結果は同じというような等羃性を持たせることが必要。undo/redoは、再起動が繰り返されたり、２フェーズコミットが失敗したときに生じる。
先ほど出てきた、連続的なIDを用いるとundo/redoに等羃性を持たせることができる。オブジェクトが永続化されるときにこのIDも一緒に入れておき、かつ、この書き込みがatomicであれば、undo/redoが必要かどうかは、このIDを見てあげれば良い（undo/redoのIDが低いか同じであれば、実行の必要がないということかな)。メッセージの場合は、最大のID以下のIDが飛んできたら捨てれば良い。
歴史的経緯の話。元々、ログバッファは、非揮発性のストレージに書きこまれていて、いろんな障害からデータロストを防いでいた。でも、揮発ストレージであるメモリを使うことが増えたため、WALプロトコルが必要となる。
なるほどー、勉強になった。いまいち、undo/redoの考え方がよく分かってなかったので。
２フェーズコミット
やっと、２フェーズコミットまできた。
将校のパラドックス
２フェーズコミットを理解するには、将軍のパラドックスを知っていると良いかも。ある作戦において将校が二人いる。目的は同じで、ある丘を占領したい。協力して行軍すれば、成功することが保証される。１軍だけが行軍したら、負ける。２軍は、比較的近いところで野営しているのだが、技術的な課題によって、伝令を走らせるしか情報伝達の手段がないとする。伝令は、不完全であり、毎回野営を出発するが、何を伝えるか忘れる場合がある。問題は、このように情報伝達が途中で喪失する場合があったとしても、同時に行軍できるようなプロトコルが存在するかということである。
簡単な証明で、固定長のプロトコルはないことが分かる。（この証明は、背理法なので）Pを同時に行軍できるプロトコルであり、最も短いプロトコルであるとする。Pに含まれる最後のメッセージが紛失するとする。この時、伝令は役に立たず、ひとりの将校に必要な情報が渡らない。Pが最小のプロトコルであることを考えると（必要最小限しか送らないことから）、最後の情報は極めて重要であり、情報が渡らない将校は行軍を開始しない。よって、矛盾。プロトコルは存在しない。
将校のパラドックスは、コミット処理を行うときのリカバリマネージメントで生じる問題と極めて近い。メインフレームが東京、ATMがドイツにあることを考えれば良い。ゴールは以下。
- 現金の引き出しをドイツで行う。
- 引き出した金額を東京の非揮発ストレージに記入する。
もし、片側だけしか生じなかったら、一貫性が担保できない。
２フェーズコミットプロトコル
将軍のパラドクスに解はないが、条件を緩めたらどうだろう。つまり、プロトコルが有限な最大長をもつと緩めることで、解が存在することになる。これから説明するプロトコルは、任意の数のメッセージのやりとりをして良いとする。通常、２，３のメッセージのやりとりで済むが、場合によっては永遠にメッセージのやりとりを行うことになる。コミット調整者というものを導入する。コミット調整者は、全ての参加者と通信で繋がっている。参加者は、ノード上のプロセスであったり、自律的なモジュールだったりする。コミット調整者は、全ての参加者に、redo/undoどちらにでも行ける状態にしてくれと頼む（つまり、信頼性の高いストレージにログを書きだす）。コミット調停者は、参加者から投票を受ける。
- 参加者のうち、ひとりでもabortした場合、コミット調停者はabortを全参加者に送り、ログにabortしたことを書き込む。他の参加者者全員abortする。
- 全参加者がOKとしたらな、コミット調停者は、ログにコミットレコードを書き込む。全参加者にコミット要求を行い、全員からackが返却されたら調整者は終了する。
このアプローチが成功する理由は、コミット判断のための情報ををひとつの場所に集めたこと、また、時間的な制約を付けてないこと（失敗したら、諦めるという部分）。成功する場合、参加者がabortする場合、調整者がabortする場合の三つのシナリオがある。
ここまで来て、なぜ２フェーズコミットがいまいち分かってなかったかが分かった気がする。２フェーズコミットプロトコルそのものが、わからないというよりも、redo/undoがidempotentに作成されていることが分かってなかった。
以下は、擬似コード。
coordinator_proc(){
int vote = COMMIT;
for(int i = 0; i < allparticipants; i++){
int reply=send_msg(i, REQUEST_COMMIT);
if(reply != AGREE) vote=ABORT;
}
if(vote==COMMIT){
write_log_sync(SEND_COMMIT);
for(i = 0; i<allparticipants; i++){
flg_wait_ack=true;
while(flg_wait_ack){
send(i, COMMIT);
reply = wait_ack_timeout();
if(reply == ACK){
break;
}else{
continue;
}
}
}
}else{
write_log_sync(ABORT);
for(i = 0; i<allparticipants; i++){
flg_wait_ack=true;
while(flg_wait_ack){
send(i, ABORT);
reply = wait_ack_timeout();
if(reply == ACK){
break;
}else{
continue;
}
}
}
}
write_log_sync(COMPLETE);
}
participant_proc(){
wait_msg(COMMIT);
reply = write_log_sync(UNDO_REDO_LOG); /* phase 1 */
if(reply){ /*writes AGREE in log */
send(coordinator, AGREE);
}else{
send(coordinator, ABORT);
}
verdict = wait_verdict(); /* phase 2 */
if(verdict == COMMIT){
release(resources-locks);
send(coordinator, ACK);
}else{
undo();
send(coordinator, ACK);
}
}
何かが生じて再起動した場合には、基本的にはログの情報しか残っていない。SEND_COMMITを書きこむ前に、調整者がクラッシュした場合には、abortを行う。思うに、REQUEST_COMMITは覚えておかなくても良いのだろうか。それがないと、トランザクション自体の処理が始まったことが分からないように思う。
SEND_COMMITがあって、COMPLETEがない場合、再起動時にはCOMMITを再送信する。COMPLETEがある場合には、特にトランザクションとしてリカバリを必要としてない。今度は、参加者の方。AGREEエントリがログになければ、abortする。もし、AGREEがあった場合、調整者に対して、トランザクションがcommitなのか、abortなのか、を聞く（redo/undo）。
- SEND_COMMITとAGREEをログに書き込む前
- SEND_COMMITとAGREEをログに書き込んだ後
という二つのフェーズを持っているので、２フェーズコミットと呼ぶ。参加者のひとりが間違えて、行軍しないことを保証している。うーん、でもどうなんだろう。COMMITメッセージを複数に送る場合には、中途半端に届く可能性があるよね。まあ、その場合は、成功するまで再送信するからいいのか。まあ、考えてみるとshared nothingで時刻同期が不完全な場合、故障を考えなかったとしてもある時から、一気に状態変更はできないね。だから、参加者は、コミットが来るまでは不完全な状態であることを把握して、中途半端なトランザクションに対する検索には、エラーを返却すればよいのかもしれない。phase1でクラッシュしても、全体はabortされる。phase2でクラッシュした場合、調整者にundo/redoを聞く。phase1で必要な情報を書いておくことで、どちらにも対応できる。このためには、redo/undoがidempotentである必要がある。SEND_COMMITがログになければ、abortを送る。SEND_COMMITがあるのなら、COMMITを送る（redoに対応）。
今日は、ここまで、続きは気が向いたら（P469から）。
