2相コミット(Two-Phase Commit)とは、コンピュータネットワークデータベースにおいて、分散システム内の全ノードがトランザクションコミットに合意するための分散アルゴリズムあるいはプロトコルである。ネットワーク障害やノード故障の場合も考慮され、結果としてトランザクションはコミットが成功するか失敗するかのいずれかの状態となる。しかし、Dale Skeen とマイケル・ストーンブレーカーの研究によれば、2相コミットは同時に複数のサイトが(無作為に)障害に陥った場合に対応できない。このアルゴリズムの2相とは、「調整者; coordinator」が全「参加者; cohorts」の調整を行う「コミット要求相; commit-request phase」と、調整者の決定によって全参加者がトランザクションを完了させる「コミット相; commit phase」である。

前提

編集

2相コミットは次のように動作する。まず、あるノードを調整者(coordinator)とし、ネットワーク上の他のノードを参加者(cohorts)とする。このプロトコルでは各ノードに先行書き込みログを格納する安定した記憶装置が存在し、ノードが永遠にクラッシュ状態であることはなく、先行書き込みログのデータがクラッシュで失われることもなく、任意の2ノード間で通信可能であると仮定する。特に最初の2つの仮定は重要で、1つのノードが完全に故障してしまうとデータが失われてしまう。

プロトコルは、トランザクションが最終段階に達したときに調整者が開始する。参加者は状況に応じて「合意」メッセージか「停止」メッセージで応答する。

基本アルゴリズム

編集

コミット要求相(フェーズ)

編集
  1. 調整者は全参加者に「コミットしてもよいか」というメッセージを送る。
  2. 参加者はトランザクションをコミットを行える状態まで進める。さらに、UndoログとRedoログにエントリを書き込む。
  3. 参加者はトランザクションが成功した場合は「合意」メッセージで応答し、失敗した場合は「停止」メッセージで応答する。
  4. 調整者は全参加者から応答メッセージがあるまで待つ。

コミット相(フェーズ)

編集

成功

編集

調整者が全参加者から「合意」メッセージを受け取った場合:

  1. 調整者は全参加者に「コミットせよ」というメッセージを送る。
  2. 各参加者は操作を完了し、トランザクション中に保持していた全ロックとリソースを解放する。
  3. 各参加者は調整者に「完了応答」メッセージを送る。
  4. 調整者は全参加者から完了応答を受け取った時点でトランザクションが完了したものとする。

失敗

編集

「停止」メッセージで応答した参加者がいた場合:

  1. 調整者は全参加者に「ロールバックせよ」というメッセージを送る。
  2. 各参加者は Undoログを使ってトランザクションをする前の状態に戻し、トランザクション中に保持していた全ロックとリソースを解放する。
  3. 各参加者は調整者に「完了応答」メッセージを送る。
  4. 調整者は全参加者から完了応答を受け取った時点でトランザクションが完了したものとする。

欠点

編集

2相コミットの最大の欠点は、ブロックする可能性があることである。メッセージを待っている状態ではノードはブロックされて何も出来ない。そのため、あるリソースロックを保持した状態でブロックしている場合、他のプロセスがそのリソースを獲得しようとすると、そのプロセスもブロックされる。また、あるノードは他のノードが全て障害状態に陥っても待ち続けることになる。調整者が永久的な障害状態となった場合、各参加者はトランザクションを完了させられなくなる。そうすると関連するリソースもロックされたままとなる。特に参加者が「合意」メッセージを送って、調整者から「コミットせよ」か「ロールバックせよ」のメッセージが来るのを待っている状態で、そのようなブロック状態が発生する。

調整者が「コミットしてもよいか」のメッセージを参加者に送ったとき、全参加者が応答するまで調整者はブロックされる。ある参加者が永久的に障害状態となっている場合、調整者は永久にブロックされたままとなる。このような場合タイムアウトが発生し、調整者はロールバックすることを決定する。このような保守的な動作も2相コミットの不利な点である。

データベースの研究では、2相コミットのコストをなるべく増加させずに改善しようとしてきた。

木構造2相コミットプロトコル

編集

分散システムにおける2相コミットの典型的な改善策として木構造2相コミット(Tree 2 Phase Commit)がある。調整者は通信の木構造のトップ(根)となり、参加者はその木構造上の他のノードとなる。調整者からのメッセージは木構造上を伝播していき、途中のノードに相当する参加者は下位の参加者の応答を集めて上位に渡す。ただし、「停止」メッセージは下位の応答全てを待つのではなく、即座に上位に送られる。

動的2相コミット(Dynamic 2 Phase Commit)は、調整者を予め定めない木構造2相コミットである。最も下位のノード(葉)はトランザクションが完了したときに「合意」メッセージを上位に送り、調整者は早い者勝ちで動的に決定される。動的2相コミットは高速であり、最小時間でコミットを完了できる。

関連項目

編集