N相コミットと合意アルゴリズム

作成日時：2024-08-27
更新日時：2024-08-27

N相コミットの流れ

1相コミット
- 3. コホートにコミット指示を出す
2相コミット
- 3. コホートにコミットしていいか聞く(準備フェーズ)
- 4a. 全コホートからOKメッセージが来たら、コホートにコミット指示を出す(コミットフェーズ)
- 4b. タイムアウトもしくはNGが来たらロールバック指示を出す
3相コミット
- 3. コホートにコミット可能(canCommit)か聞く(投票要請フェーズ)
- 4a. コホートからNoメッセージやタイムアウトが発生したら、ロールバック
- 4b. 制限時間内に全員のYesメッセージが来たら、preCommitメッセージをコホートに送る(準備フェーズ)
- 5a. 全コホートからAckが来ればコミット指示を出す(コミットフェーズ)
- 5b. 来なかったらロールバック

各相はどういうフェーズかと言うと、下記のようになる。

コーディネーターの動きとしてはこんな感じ。

3PCの特徴的な点は以下。

最初の「コミットできる？」フェーズで、実際のリソースをロックせずに各ノードの状態を確認する。
- これにより、早い段階で不可能なトランザクションを中止でき、リソースの長時間ロックを回避できる。
「コミットするね」フェーズ（準備フェーズ）の後、コーディネーターに障害が発生しても、各ノードはお互いの状態を知っているため、自律的に判断できる可能性が高まる。
タイムアウトの扱いが洗練されており、フェーズによって適切な判断（コミットまたはアボート）ができる。

これらとは別に、Paxos、Raftという合意アルゴリズムがある。
NewSQLにおける、分散しているデータの同期に使われているらしい。
TiDBやCockroachDBなど。

故障モデルには下記の段階がある。
対応する複製アルゴリズムも併記する。
https://www.slideshare.net/slideshow/ss-78765920/78765920#2

1：故障なし
- 2PC
2：Fail-Stop(同期通信)
- 3PC
3：Fail-Stop(非同期通信)
- 3PC
- 壊れたサーバーは他サーバーから故障と観測される。
- 壊れたサーバーを壊れていないと認知、またその逆は発生しない。
- 壊れたサーバーは復帰しない。
4：Crash-Recovery
- 壊れたサーバーは復帰する可能性がある
- Paxos
- Raft
5:Byzantine
- PBFT
- ビザンチン将軍問題
- フォールトトレラント

故障モデルは下に行くほど面倒くさい。
Redis SentinelはJepsen Testしたら50%近くデータが消えたとか。