Paxos Made Simple 読んだ
Paxos Made Simpleを読んだ時のメモ。
どんなもの?
- Paxos
- 分散合意アルゴリズム
- 複数のプロセスが値を提案した時に、どのように1つの値を選ぶかについて
- 分散合意アルゴリズム
技術や手法の肝は?
The Problem
safety requirements
- 提案された値のみが選ばれる
- 1つの値のみが選ばれる
- 値が選ばれた後でしたか、その値は使えない
roles
- proposer
- acceptor
- learner
1つのprocessが複数のroleを担っても良い
- 分散システムの問題点
- Agentは任意の速度で処理を行う
- 処理が止まって、失敗するかもしれないし再起動するかもしれない
- メッセージは到達するまで任意の時間がかかる
- メッセージは重複するかもしれないし、失われるかもしれない
- メッセージは壊れた状態では届かない
Chosing a Value
- 1つの値を選ぶのに一番簡単な方法はacceptorを1つにすること
- SPOFになるのでダメ
- acceptorを複数にし、proposerが複数のacceptorに提案を送る
- 過半数のacceptorがacceptした値が選ばれるとする
- P1. acceptorは最初に受け取った提案をacceptしなければならない
- P2. 値vの提案が選ばれたら、それより大きいIDのproposalの値はvでなければならない
- 提案が選択されたあとの上書きを防げる
- 提案は少なくとも1つのacceptorにacceptされる必要がある
- P2a. 値vの提案が選ばられたら、全てのacceptorによってacceptされたものより大きなIDの提案は値vを持たねばならない
- これだと、P1が満たせない(acceptorは最初に受け取った提案をacceptせねばならない)
- 新しいacceptorが異なる値の提案をしたときに、P1を満たすためにはその提案をacceptせねばならない(P2aに違反)
- P2b. 値vの提案が選ばれたら、それより大きなIDを持つ提案は全て値vを持つ
- P2c. ID:n, 値:vの提案が発行されたら、下記のようなacceptor群Sが存在しなければならない
- a) ID:nより小さな提案をacceptしているacceptorはSにはいない
- b) ID:nより小さい全ての提案の中で最も大きいnumberの提案の値がv
- ID:n より小さい提案を全部無視して欲しい
- prepare request
- ID:n より小さい提案をacceptしないことを約束する
- accept request
- 提案を受け入れた
- P1a. AcceptorはID:nより大きなIDのprepare requestにresponseしていない場合、ID:nの提案をacceptできる
- 1つの値を選ぶのに一番簡単な方法はacceptorを1つにすること
- Paxos
- Phase 1
- ProposerがID:nの提案を選び、prepare reqをacceptorの過半数に送る
- もしID:nがPromise済みのIDよりも大きければacceptし、違ったら現在acceptしている提案を返す
- Phase 2
- ProposerがAcceptorの大半からprepare reqを受け取ったら、それぞれのacceptorに accept reqを送る(ID:n, value:v)
- acceptorがID:nのaccept reqを受け取る
- nがPromiseした提案のID以上ならaccept
- Phase 1
- Learning a Chosen Value
- 提案が選ばれたことを確認するにはLearnerを使う
- 過半数のacceptorに提案がacceptされたことをlearnerに確認させる
- Distinguished learnerにacceptorが提案がacceptされたことを報告する
- Distinguished learnerが他のlearnerに通知する