j3259の日記： 分散システムにおける協調 (2相コミット)

データが複数のデータベースにまたがってるとか、分散トランザクションなどで複数のプロセスが「同時」になんらかのアクションを取ることが必要な場面がある。「同時」といっても、論理的な同時性があればそれでいい。
困るのが、一つのプロセスではアクションを取ったのに、別のプロセスではアクションを取ってないという状況。なんらかの理由で全員がアクションを取れなかったというのは、仕方が無いということにする。ここでよく例に出てくるのが、銀行の送金とか飛行機の席の予約。送金元では引き下ろしのアクションが取られたのに、送金先では振込みのアクションが取られなかったら困るというのが分かると思う。
内部の様子が分かる例としては、何人かが全く同じ幕の内弁当をもらったとして、全員が同時に同じおかずを食べるという状況。

2 phase commit (2PL; 二相コミット) は調整役（コーディネータ）と参加者が何人いて、全員が調整役が誰か分かってることとする。
コミットが必要になると、調整役が参加者全員に「コミットの準備できましたか？」と聞いて回り、全員が「ok」と答えたら、調整役が再び全員に「コミットして」と連絡する。参加者の一人でも「できません」といったら調整役は全員に「中止して」と連絡する。

弁当に戻ると、調整役が全員に「次、コロッケ。いいか？」と聞いて、全員が「はい」といったら、調整役が「よし食え」と言って、全員が食べる。
困るのが、こっちが「はい」って答えたのに調整役が「よし食え」と言う前に参加者何人か連れて会議に出ちゃった場合。参加者の一人でも「できません」と言ったらコロッケは食べちゃいけない。いなくなった参加者に「よし食え」命令が出てた可能性もある。

Wikepedia 2相コミットにもある通り、欠点はブロックする可能性があること。一人でも返事が遅いと全員が待つ事になるので、参加者が多いとかなり遅いプロトコルになる。

途中でプロセスがクラッシュしたらどうなるかという問題に対して、Skeen と Stonebraker によって提唱されたのが 3 phase commit（3PL; 三相コミット）。availability （可用性）を高めることを意図してるが、正確な故障検知を前提としてるため非現実的。Wikipedia Three phase commit にある通りネットワーク分裂（別名 split brain 現象）に弱い。

3 phase commit も 2PC と同じく調整役と参加者が何人かいる。
- 「初期状態」で調整役にトランザクションのリクエストが入る。(0)
- 調整役は参加者全員に「コミットしてもいいですか？」(1) と聞いて回り「待機状態」に移行する。
- 全員が「ok」と答えたら、調整役は「準備開始」(2) の指令を出し「準備状態」に移行する。
- 参加者全員が「準備完了」と応答したら調整役は「コミットしてください」(3) と指令を出し「コミット状態」に移行する。

- 初期状態中で調整役が故障した場合は、回復後トランザクションを中止
- 待機状態中で誰かが故障、タイムアウトもしくは参加者が「できません」と答えた場合は「中止して」と連絡する
- 準備状態で調整役が故障した場合は参加者は「コミット状態」に移行する