19章-1 2相コミットプロトコル

###### tags: `TransactionalInformationSystems` # 19章-1 2相コミットプロトコル ## 概要分散トランザクションにおいてACID特性を確保することの難しさは、「失敗の局所性」にある。つまり、どちらのバが障害を起こして動作を停止したとき、他のサーバは通常動作中である。さらには、複数のサーバで操作されたデータを一斉にコミットするべきかアボートするべきか決定するためにメッセージを交換しなければならない。例えばそのメッセージが失われたとき、各サーバの意思決定を統一することは難しくなる。メッセージを送ってこないサーバが**単に処理に手間取っているのか、それとも障害を起こして失敗したのかの区別ができない**から。また、クラッシュの正確な時点も他サーバに分からないため、サーバごとにコミットの進行状況が異なる状態でクラッシュするという危険な現象も起こりうる。このような問題を解決するため、各サーバ間でコミットのタイミングを同期するための分散プロトコルである2相コミットプロトコル(2PC)を導入する。このプロトコルは各サーバのログとトランザクション障害回復能力を基に実現され、1組のメッセージやり取りを通じてサーバ間で原子性を確保する契約を確立する。 2PCプロトコルでは、クラッシュしたサーバは、再開時に他のサーバへ敗者トランザクション（in-doubt transaction）の情報を通知する必要がある。この意味で、サーバは完全に独立には回復を行わない。この手順は分散システムのデータ一貫性を維持するために不可避のコストであるが、本章で導入する実装テクニックを用いれば非常に効率的に行えるため問題にならない。分散コミットプロトコルの美点は、ローカルな障害回復アルゴリズムが何でも良いということ。勝者トランザクションと敗者トランザクションの判別ができ、コミットプロトコルのルールに全サーバが従いさえすれば機能する。実際、2PCはソフトウェア産業で一般的に受け入れられているのでこの前提は達成しやすい。 ## 基本の2相コミットアルゴリズムコミットのタイミングを関わるサーバ間で統一するために、**調整者**(coordinator)を導入する。ある意味、調整者は、自分にしかアクセスできない共有ストレージをエミュレートしていて、他サーバは調整者にメッセージを送ることを通じてそのストレージにアクセスするようなものである。共有ストレージの実体は単なる永続ログで、トランザクションのコミット状態を記録する。調整者はどのサーバでもクライアントでもよい。単純に参加サーバの一つの追加スレッドで実行されることも多く、この場合はログファイルも共有される。本章では単純のために調整者が個別のログを持つことにする。 --- ### 第一段階：投票調整者は参加者すべてに、トランザクションをコミットする準備ができているか尋ねる。このメッセージを準備メッセージと呼ぶことにする。参加者は、そのトランザクションをredoするために必要なログが揃っていればYESで返答する。そのため、返答のタイミングでログバッファをforceする。クラッシュからの回復中などの理由でまだコミットの準備ができていないならばNOで返答する。 ### 第二段階：決定調整者が全参加者からYESを受け取ったとき、コミットの準備ができていると判断され、全参加者にコミットメッセージが送られる。一つでもNOがあれば、全参加者にアボートメッセージが送られる。どちらの結果でも、メッセージを受け取った参加者は調整者にackメッセージ（承認メッセージ）を返送する。 --- メッセージはどの時点、どの地点でも失われうるし、複数回発生する場合もあるし、どこかのサーバがクラッシュする場合もある。プロトコルはこのような障害に対応できなければならない。 - メッセージ紛失：ネットワーク障害により、メッセージが目的地に届かない問題。 - メッセージ複製：ネットワークコンポーネントの一時的な障害などにより、同じメッセージが複数個作られる問題。 - プロセス障害：参加者あるいは調整者がソフトクラッシュし、ストレージは大丈夫だが回復ステップが必要になる問題。このうちメッセージに関するものはセッションベースの送受信を確立できるプロトコル(TCP/IPなど)を利用すれば2PC側で対処する必要もなく解決するのだが、それをしたところで結局プロセス障害に起因する2PCの複雑さは全く変わらない。という事情から、メッセージをやり取りするプロトコルに関しては何も仮定を設けないことにする。なので、単にパケットを送りっぱなしで受信されたかの確認は行わないと想定する。 --- 準備メッセージにYESで答えた参加者は、そのトランザクションをコミットもロールバックもできる必要があり、またYESで答えた直後にクラッシュしても再開後にそう答えたことを思い出せる必要がある。よって、YESリプライを送る直前に永続ログにpreparedログエントリを作成する。この際、ログバッファをforceする必要はない。（クラッシュによってこれを含むログバッファが失われた場合、じっさいコミットは不可能なので準備の完了とpreparedログエントリの存在が等価になる） > 参加者は準備ができた時点で調整者のメッセージ待ちの状態になる（調整者にブロックされる）ため、一時的に自律性を失うことになる。分散システムでこのようなサーバ間実行依存性が生まれるのはつらい。が、実のところ、このようなブロックは分散システムで原子性とデータの一貫性を保持するためには避けられない性質であり、2PCはそれをできるだけ効率的に済ますための方法である。調整者側でも、投票フェーズの開始前にbeginログエントリを作成することにする。beginログエントリには参加者のリストを含めておく。これはメッセージの送信開始前にforceする。また、決定フェーズの最後、全てのサーバから承認メッセージを受け取ったタイミングでendログエントリを作成する。endログエントリを作成するタイミングを適切に判定するために、既に承認メッセージを受け取った参加者リストとbeginログエントリの総参加者リストを比較する。調整者のログもガーベジコレクションが必要になる。いちどendログエントリが作成されたトランザクションはもう記録しておく必要がないので削除しても問題ない。調整者及び参加者の状態遷移図を図で示す。 ![](https://i.imgur.com/QpupHx2.png) ただし、これだけでは完全ではない。 - 調整者がCollecting状態で返答を貰いきる前にクラッシュし、回復プロセス中に残りのメッセージが来た場合、それは失われて調整者が永遠にCollecting状態にとどまってしまう。これを防ぐため、調整者は周期的に準備メッセージを送信し、そのたびに参加者から返答を受け取ることでメッセージ紛失への耐性を持たせる。この動作はタイムアウトを利用して実現する。ここまでの考察を踏まえて、基本2PCプロトコルには2種の拡張プロトコルが必要になる。 - 再開プロトコル：クラッシュしたプロトコルの再開手順について記述する。 - 終了プロトコル：メッセージ待機中にタイムアウトした場合の振る舞いについて記述する。クラッシュやタイムアウトが調整者と参加者のどちらで起こったかによってさらに２通りずつのパターンが発生する。 1. 調整者再開プロトコル 2. 調整者終了プロトコル 3. 参加者再開プロトコル 4. 参加者終了プロトコルなお、相手がクラッシュしたのか、それともネットワークのエラーが原因なのかは判別できないものとして取り扱う。じっさい、完全に正確に判別するのは難しい。上述の状態遷移図を拡張し、「F遷移（クラッシュ後の再開時にトリガーされる）」と「T遷移（タイムアウト時にトリガーされる）」を追加して以下の図を得る。 ![](https://i.imgur.com/uVouqyD.png) それぞれのケースでの具体的な動作を分析する。 #### 1.調整者の再開 Initialでクラッシュした場合、まだ準備メッセージを送信してもいないので普通にやり直す。 Collectingでクラッシュした場合、参加者の返答がいくつか失われている可能性があるのでInitialに戻って準備メッセージを送信し直す。 CommitedやAbortedでクラッシュした場合、参加者の承認メッセージがいくつか失われている可能性があるのでコミット/アボートメッセージを送信し直し、承認メッセージを送り直してもらう。 #### 2.調整者の終了調整者側でタイムアウトしたとき、参加者の一部から返答が返ってきていないことを意味するので、メッセージを送信し直す。送信先はまだ返信を貰っていない参加者のみに絞れる。 #### 3.参加者の再開 Initialでクラッシュした場合、まだサーバの自律性を放棄していないので、自発的にトランザクションをアボートすることができる。準備メッセージに対してはNOと返答すればよい。一度Preparedになったら調整者の決定を待つ必要があるので、クラッシュから再開してもPreparedを続ける。 #### 4.参加者の終了参加者のタイムアウト時はクラッシュ時と同様の動作をするが、Initialでの待機時間は多少寛大にしてもよい(分散システムでは通常動作中でも実行時間が大きくぶれやすいため)。 --- ここでは調整者のForgotten状態を無視し、CommittedとAbortedを最終状態とする。 ### 定理19.1 2PCプロトコルは分散トランザクションの不可分性を保証する。すなわち、あるプロセスが最終状態に到達したとき、 - 全てのプロセスがCommitted状態になっている - 全てのプロセスがAborted状態になっているのどちらかである。 #### 証明すべてのプロセスがInitialから開始することを仮定する。参加者を$n$人とし、それに調整者を加えた$n+1$個のプロセスを考える。これら各プロセスの状態（ローカル状態）をすべて合わせたものをグローバル状態とする。示せばよいのは、少なくとも一つのローカル状態がCommittedで少なくとも一つのローカル状態がAbortedであるようなグローバル状態には到達しえないこと。このようなグローバル状態には実際到達しえない。なぜならそんな状態に到達するとしたら、参加者がCommitted/Abortedになるには調整者がCommitted/Aborted状態に入る必要があるため、調整者がCommittedとAbortedの両方を経験しているということになる。だが、調整者のローカル状態におけるCommittedとAbortedはどちらも、一度入ったら出れない最終状態なので、このような状況はありえない。したがって全部Committedか全部Abortedしかありえない。$\square$ --- これで最終的に良い状態にしか到達しないことは示されたが、これでは計算量が考慮されていない。クラッシュ回数が有限回という仮定の下で、状態遷移の数も有限で済むことが示される。 #### 定理19.2 クラッシュの回数が有限回であれば、2PCプロトコルは有限回のグローバル状態遷移で最終状態に到達する。 ##### 証明クラッシュ回数もローカル状態数も有限なので、有限回でローカル最終状態に到達する。よってグローバル状態も有限回で最終状態に到達する。$\square$ --- ### 独立した障害回復ここまでで導入した2PCはブロッキングプロトコルで、参加者はローカル状態遷移にあたって調整者の指示に依存していた。では、他のサーバに依存せずに独立に障害回復し、ローカル最終状態に到達する方法はないのだろうか。実のところ、一般にはそれは不可能だが、障害が一度だけ起こり、かつメッセージの紛失が起こらないという限定的な状況の下で可能になる。この仮定を単一障害仮定と呼ぶことにする。 --- #### 定理19.3 単一障害仮定の下では、独立した障害回復が可能な分散コミットプロトコルが存在する。 --- 独立な障害回復の難しさは、ある参加者はCommitted/Abortedだが、他の参加者はPreparedという状況が可能なので、参加者から見て他の参加者がCommittedなのかAbortedなのか独立に判断できないことにある。 --- #### 補題19.1 一つのコンポーネントが非最終のローカル状態に属し、他に複数の最終ローカル状態に属しえるコンポーネントがあるようなグローバル状態を持つ分散コミットプロトコルは、単一障害仮定の下でも独立な障害回復を保証できない。 --- #### 定理19.4 複数の障害が起こりうる場合、独立な障害回復を保証する分散コミットプロトコルは存在しない。 ##### 証明調整者と参加者が1プロセスずつのシステムを考え、どちらも任意のローカル状態から独立な回復を達成できると仮定する。クラッシュが存在しないとき、グローバル状態は$G_0,...,G_m$と遷移し、$G_m$でどちらのローカル状態もCommittedになる。 - $G_m$でクラッシュが起きて再開されたとき、各プロセスは独立にCommittedに復元される。 - $G_0$でクラッシュが起きて再開されたとき、各プロセスは独立にAbortedに復元される。したがって、ある最小の$k$が存在して、 - プロセス1で$G_k$でクラッシュが起きて再開されたとき、独立にCommittedに復元される。 - プロセス1で$G_{k-1}$でクラッシュが起きて再開されたとき、独立にAbortedに復元される。 - プロセス2で$G_{k-1}$でクラッシュが起きて再開されたとき、独立にAbortedに復元される。を満たす。ここで、プロセス1の復元先が$G_{k-1}\rightarrow G_k$で変化しているので、この状態遷移時にプロセス1のローカル状態がCommittedになっていることが分かる。プロセス間がメッセージでやり取りしておりストレージを共有していないので、グローバル状態遷移は一度に一つのローカル状態しか変更しない。したがって、プロセス2のローカル状態は$G_{k-1}\rightarrow G_k$で変化しておらず、$G_k$でクラッシュが起きて再開されたときもAbortedに復元される。以上の考察から、$G_k$が不正な状態である。（プロセス1はCommitted、プロセス2はAborted）したがって、プロトコルの実行中に複数の障害が起こりうる場合、独立な回復はできない。$\square$ --- 障害が短い時間に複数起こるのはレアケースではあるが、起こらないわけではない。よって、起こりうる現象に本質的に対処手段を持たない非ブロッキングプロトコルは許容されない。