3相コミット
コンピュータネットワークやデータベースにおいて、3相コミットプロトコル(3PC)[1]は分散アルゴリズムであり、分散システムの全ノードがデータベーストランザクションのコミットに合意することを可能にするものである。しかし、2相コミット(2PC)とは違い、3PCはノンブロッキングである。より詳細には、3PCはトランザクションがコミットするか、中止するかのいずれかにかかる時間に上限を設ける。この性質により、もしあるトランザクションが3PCによりコミットしようとして、あるロックを行っている場合、タイムアウトによりそのロックが解除されることが保証される。
プロトコル説明 編集
このプロトコルを説明するにあたり、2相コミットと類似の用語を使用する。したがって、一つの調整者(coordinator)サイトがトランザクションを指揮し、一つあるいは複数の参加者(cohorts)が調整者からの指示を受けるものとする。
調整者 編集
- 調整者はトランザクションリクエストを受信する。もしこの時点で障害があれば、調整者はトランザクションを中止する。(つまり、回復したときにトランザクションが中止されたものとみなす)そうでない場合、調整者はcanCommit?メッセージを参加者に送り、待機状態に遷移する。
- もし、待機状態において調整者が、障害やタイムアウトが発生したり、あるいはNoメッセージを受信した場合、調整者はトランザクションを中止し、全ての参加者へ中止メッセージを送信する。そうでなければ、調整者は制限時間内に全ての参加者からYesメッセージを受信するので、preCommitメッセージを全ての参加者に送り、準備状態に移る。
- もし調整者が準備状態で成功したなら、コミット状態へ遷移する。しかし、調整者が参加者からの了解メッセージを待つ間にタイムアウトを起こした場合、トランザクションを中止する。全ての了解メッセージが受信された場合も、調整者はコミット状態へ移る。
参加者 編集
- 参加者はcanCommit?メッセージを調整者から受信する。もし参加者がそれに合意すれば、Yesメッセージを調整者に送信し、準備状態に移る。
- 準備状態において、参加者が調整者から中止メッセージを受信した場合、あるいは障害が発生するか、コミットを待っている状態でタイムアウトが生じた場合、中止を行う。参加者がpreCommitメッセージを受信した場合、ACKメッセージを送信し、コミットを行う。
問題点 編集
このアルゴリズムの主な問題として、ネットワークがセグメント化されていると復旧が出来ないということがある。最初の3PCアルゴリズムはフェイルストップモデルを前提としており、その場合、プロセスがクラッシュにより障害を起こし、クラッシュは正確に認識が可能であり、これはネットワークパーティションや非同期通信においては適用できない。
脚注 編集
- ^ Skeen, Dale (May 1983). “A Formal Model of Crash Recovery in a Distributed System”. IEEE Transactions on Software Engineering 9 (3): 219--228. doi:10.1109/TSE.1983.236608.
関連項目 編集
- 2相コミット
- Gaddam, Srinivas R. (1995年4月29日). “Three-Phase Commit Protocol”. 2008年3月11日閲覧。
- Paxos commit nプロセス間での合意のためのPaxosアルゴリズムに基づくフォールトトレラントなコミットアルゴリズム