分散システムについての学習

基本

まずはkumagi-sanのスライドを読む

www.slideshare.net

合意アルゴリズムとアプリケーション

2PC (Two Phase Commit), 3PC (Three Phase Commit)

Paxos

ZAB (ZooKeeper Atomic Broadcast)

  • Zookeeper (Google Chubbyのクローン?)
  • HBaseはZookeeperを使っている

Raft

めちゃくちゃこのページがよく出来ている。アニメーションやら解説スライドなど理解への導入が素晴らしい。 https://raft.github.io/

その他

FLP impossibility

Fail-Stop(非同期通信)より厳しい故障モデルでは「全ての壊れていないサー バが有限の時間で確実に合意に至るアルゴリズムは存在しえない」という 事を理論的に証明した論文があり、著者の頭文字を取ってその不可能性が命名されたもの

ちなみに上記は以下のブログ記事に対するコメント

Bitcoinは合意アルゴリズムではない – The Third of May

その他、

CAP定理

Takeru Ohtaさんによる証明論文の抄訳がとても分かりやすい

『Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services』の要約 · GitHub

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