基本
まずはkumagi-sanのスライドを読む
www.slideshare.net
合意アルゴリズムとアプリケーション
2PC (Two Phase Commit), 3PC (Three Phase Commit)
- アルゴリズムは単純
- 2PCはFail-Recovery発生時にバグる
- 2PCではCoordinatorからのリクエストにCohortが返答しない限りブロックが発生してしまうので、ノンブロッキングな3PCが考えられた
- 3PCでは時間制限を設け、タイムアウトが発生した場合に異なるフェーズに移行する
- 余談: 翻訳: スターバックスは2フェーズコミットを使わない｜Ouobpo
Paxos
ZAB (ZooKeeper Atomic Broadcast)
- Zookeeper (Google Chubbyのクローン?)
- HBaseはZookeeperを使っている
Raft
めちゃくちゃこのページがよく出来ている。アニメーションやら解説スライドなど理解への導入が素晴らしい。 https://raft.github.io/
- Consul by HashiCorp
- MongoDB by Tokutek
- etcd
- etcd/raft at master · coreos/etcd · GitHub
- DockerのCoreOSで使われている軽量KVS
- etcd総選挙を眺めてみる - Qiita
- Kudu
- CockroachDB
その他
FLP impossibility
Fail-Stop(非同期通信)より厳しい故障モデルでは「全ての壊れていないサー バが有限の時間で確実に合意に至るアルゴリズムは存在しえない」という 事を理論的に証明した論文があり、著者の頭文字を取ってその不可能性が命名されたもの
- 解説: A Brief Tour of FLP Impossibility - Paper Trail
- 元論文: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
「合意アルゴリズムは一定の時間内で必ず合意に至れる」っていうのはどこの定義か知らないけれど、Paxosだって2つのプロポーザが競合し合ったら永久に合意に至らないしRaftもリーダー変えまくれば永久にコミット進まないしFLPも「有限時間での合意は絶対保証できないよ」って言ってる。
— KUMAZAKI Hiroki (@kumagi) August 24, 2017
ちなみに上記は以下のブログ記事に対するコメント
Bitcoinは合意アルゴリズムではない – The Third of May
その他、
分散システムにおける合意問題っていうのは「合意結果は覆らない」っていう大前提があって、FLP Impossibilityも「覆らない合意のためには絶対にこういう仕組みになる」っていう前提で証明が立てられているので、bitcoinのPoWは覆る点で合意ではないしFLPも関係ない。
— KUMAZAKI Hiroki (@kumagi) August 23, 2017
CAP定理
Takeru Ohtaさんによる証明論文の抄訳がとても分かりやすい
ConsensusとQuorumの違い
- Achieving consensus means that all the participants in the discussion agree (on a proposal/result/plan etc).
- Achieving quorum means that a majority of the participants in the discussion agree.
- Therefore - if there are N participants, if all N of them agree, a consensus is achieved. If (N/2 + 1) or more participants agree, a quorum is achieved.
What is the difference between a consensus and a quorum? - Quora
