2相コミット

2相コミット（Two-Phase Commit）とは

2相コミットは、分散システムにおいて、複数のノードが連携してトランザクション処理を行う際に、すべてのノードがトランザクションのコミットに合意するための分散アルゴリズム、またはプロトコルです。このプロトコルは、ネットワーク障害やノードの故障が発生した場合でも、トランザクションが完全に成功するか、完全に失敗するかのいずれかの状態になることを保証します。しかし、複数のノードが同時に故障した場合に対応できないという課題も存在します。

2相コミットの基本的な流れ

2相コミットは、以下の2つのフェーズで構成されます。

1. コミット要求相 (Commit-Request Phase)
調整者 (Coordinator) が、トランザクションに関与するすべての参加者 (Cohorts) に対して「コミットしてもよいか」というメッセージを送信します。
各参加者は、トランザクションをコミット可能な状態まで進め、UndoログとRedoログにエントリを書き込みます。
参加者は、トランザクションの準備が完了した場合「合意」メッセージを、失敗した場合は「停止」メッセージを調整者に返信します。
調整者は、すべての参加者からの応答を待ちます。
2. コミット相 (Commit Phase)
成功時
調整者は、すべての参加者から「合意」メッセージを受け取った場合、すべての参加者に「コミットせよ」というメッセージを送信します。
各参加者は、トランザクションを完了させ、トランザクション中に保持していたすべてのロックとリソースを解放します。
各参加者は、トランザクションの完了を通知するために「完了応答」メッセージを調整者に送信します。
調整者は、すべての参加者から「完了応答」メッセージを受信したら、トランザクションが完了したとみなします。
失敗時
調整者は、1つ以上の参加者から「停止」メッセージを受け取った場合、すべての参加者に「ロールバックせよ」というメッセージを送信します。
各参加者は、Undoログを用いてトランザクション開始前の状態に戻し、トランザクション中に保持していたすべてのロックとリソースを解放します。
各参加者は、ロールバックの完了を通知するために「完了応答」メッセージを調整者に送信します。
調整者は、すべての参加者から「完了応答」メッセージを受信したら、トランザクションが完了したとみなします。

前提条件

2相コミットは、以下の前提条件に基づいています。

各ノードには、先行書き込みログを格納する安定したストレージが存在します。
ノードが完全にクラッシュすることはありません。
先行書き込みログのデータがクラッシュによって失われることはありません。
任意の2つのノード間で通信が可能です。

これらの前提条件のうち、特に最初の2つが重要です。1つのノードが完全に故障してしまうと、データが失われる可能性があります。

2相コミットの欠点

2相コミットには、以下の欠点があります。

ブロックの可能性: メッセージを待機している間、ノードはブロックされて何もできなくなります。特に、あるリソースロックを保持したままブロックしている場合、他のプロセスもそのリソースを獲得しようとするとブロックされます。また、調整者が故障した場合、参加者はトランザクションを完了できず、関連するリソースもロックされたままになります。
調整者の障害: 調整者が永久的な障害状態になると、参加者はトランザクションを完了することができなくなります。特に、参加者が「合意」メッセージを送信した後、調整者からの「コミットせよ」または「ロールバックせよ」メッセージを待っている状態でブロックが発生します。
タイムアウトによるロールバック: 調整者が「コミットしてもよいか」メッセージを送信した際、全ての参加者が応答するまで調整者はブロックされます。ある参加者が永久的に障害状態の場合、調整者は永久にブロックされます。このような状況を避けるためタイムアウトを設定し、タイムアウトが発生した場合、調整者はトランザクションをロールバックさせるという保守的な動作を行います。

これらの欠点から、2相コミットのコストを削減し、より効率的な分散トランザクション処理を実現するための研究が行われています。

木構造2相コミット

木構造2相コミットは、分散システムにおける2相コミットの一般的な改善策の一つです。この方式では、調整者は通信の木構造の頂点（ルート）となり、参加者は木構造上の他のノードとなります。調整者からのメッセージは木構造を伝播し、途中のノードに相当する参加者は、下位の参加者の応答を集めて上位に送信します。ただし、「停止」メッセージは、下位の全ての応答を待つのではなく、即座に上位に送信されます。

動的2相コミット

動的2相コミットは、調整者を事前に定めない木構造2相コミットの一種です。トランザクションが完了した際、最も下位のノード（葉）は「合意」メッセージを上位ノードに送信し、最も早く応答したノードが動的に調整者となります。動的2相コミットは高速であり、最小限の時間でトランザクションを完了できます。

2相コミット