その中心にあるPaxosは非常に簡単です

paxosアルゴリズムは、平易な英語で提示されたとき、非常に簡単です。 –レスリー-ランポート2001

私は方法で単一の法令Paxosを説明しようとするつもりです,うまくいけば,それは理解しやすいです.

今日まで、IMO、John Ousterhoutのpaxosに関する講義はまだそこで最高です。 この記事の資料は、Ousterhout教授の講義から大きく借りています。 John Ousterhoutの同意を得て、私は彼のスライドのいくつかを使ってPaxosを説明しました。

コンセンサス

paxosはプロトコルとして、コンセンサス問題を解決しようとしています。 平易な英語で言えば、1つ以上のサーバーが異なる値を提案できる場合、システムが1つの値のみを選択するという問題を解決しようとしています。

現実世界の例は、選挙のようなものになります。 人々は別の大統領に投票することができます。 しかし、大統領は一人だけ選ぶことができます。

Paxosは、フェイルストップ/クラッシュ(非ビザンチン)とメッセージ遅延/損失に対処するように設計されています。 また、大部分のサーバーが実行されている限り、提案された値が最終的に選択されるという生き生きとした要件があります。 これは、never-accept-any-valueのような興味のない解決策を避けるためです。 あなたが何もしなければ、あなたは間違って何もしません。 同様に、あなたは複数の大統領が選出されることを望んでいないし、人々が投票している限り、最終的に大統領を持ちたいと思っています。

余談ですが、正直言って、私はpaxosを説明するための例として投票を使用しようとすると、元のパートタイム議会の論文では非常に自然だと思います。 しかし、どういうわけか、それは非常にうまく動作しませんでした。 Lamportはまた、それが不幸である完全な失敗だとインタビューでそれ自身を言いました。

Screen-Shot-2018-11-13-at-11.17.43-PM
2F+1サーバーのクラスタでは、提案を受け入れるために常に特定のボックスを作成するとどうなりますか。 そして、そのボックスによって受け入れられているどのような提案が選択されます。

このアプローチの問題は、単一のダウンボックスがサービスを使用できないようにすることです。 しかし、要件には、大部分のサーバーが実行されている限り(この場合はF+1)サービスを起動して実行する必要があると記載されています。

これは事実上単一のマスターレプリケーションモデルであることに注意してください。 マスタースレーブレプリケーションでダウンタイムが避けられないのは、まさにこのためです。

Quorum

だから、単一のアクセプターを持っていても機能しない場合は、複数のサーバーが提案を受け入れてから値が選択されていると主張するまで待つべき

何人?

アクセプタが固定されていて<=Fであれば、再びFクラッシュしたサーバを許容できません。 アクセプターが任意のサーバーであり、それが<=Fである場合、2F+1サーバーのクラスターでは、2つの異なる提案があり、2つの値が選択される原因となる2つの互いに素

なので、アクセプタの数は>=F+1でなければなりません。 アクセプタが少ない方が良いので、F+1と一緒に行きましょう。 また、クラスター内の任意のF+1サーバーにすることもできます。

我々はすでにいくつかの進歩を遂げています! 提案がF+1サーバーによって受け入れられた場合、それが選択されます。

提案を受け入れる

次に、提案を受け入れるかどうかをアクセプターがどのように決定するかを見てみましょう。

最初の提案のみを受け入れますか?
Screen-Shot-2018-11-13-at-11.17.27-PM

上記の場合のように決して価値を選ばないことになるので、うまくいかないでしょう。 これはlivenessの条件に違反する。

第二の提案があるかどうかわからないので、第二の提案を受け入れるかどうかなどを言うのは意味がありません。

だから最初の提案を受け入れなければならないが、最初の提案だけではないかもしれない。

すべての提案を受け入れる?
Screen-Shot-2018-11-13-at-11.31.11-PM
これは、複数の値が選択される可能性があるため、安全要件に違反します。コア

コア

ここで私はPaxosの中で最も興味深い部分だと思うトリックが来ます。

値が選択されると、将来の提案は同じ値を提案する必要があります。

これは、二相プロトコルが必要になることを意味します。 第一段階では、提案者は、任意の値が既に選択されているかどうかを把握する必要があります。 そして、第二段階で提案します。

あなたが分散システムのベテランであれば、前の声明の一つのキーワードにすでに気づいている必要があります。 そして、それは”未来”です。 私は前に時間と注文を見直しました。 分散システムは、すべての順序についてです。 ここでの”未来”は、順序付け(発生前の関係)を意味します。 だから我々はすべての提案を注文する必要があります。 以下の例では、blueが選択され、redが古い提案であることがわかっているため、redを拒否できます。

Screen-Shot-2018-11-13-at-11.39.37-PM

投票番号

提案を注文する簡単な方法は、各提案に対して一意の投票番号を<seq_id, server_id>の形式で持つことです。 順序を保証するためには、seq_idはcross crash/restartを永続化する必要があります。 だから、それは永続的にローカルに保存する必要があります。

Paxos

今、私たちはすべて、実際の二相Paxosプロトコルを記述するように設定されています。 第一相をprepare相、第二相をaccept相と呼びます。 prepareフェーズは、一つの往復で二つの目的を果たしています。

  1. すでに選択されている値について学ぶ
  2. 古い提案を受け入れるアクセプタを防ぎます(二段階コミットのリザーブステップと非常によく似ています)

Screen-Shot-2018-11-13-at-11.53.52-PM
を使っていますが、これは

  • minProposal
  • acceptedProposal
  • acceptedValue
    「すべてのサーバーにブロードキャスト」の代わりに、「少なくともF+1サーバーにブロードキャスト」する必要があることに注意してください。 提案者は、準備段階と同じF+1サーバーのセットにacceptメッセージを送信する必要があります。

各ステップをよく見てみましょう。

準備フェーズ

このフェーズでは、提案者は受諾者から自分より古い提案を受け入れないという約束を得ようとします。 同時に、アクセプターは、これまでにどのような価値がすでに受け入れられているかを提案者に通知します。

ステップ3および4では、提案者は、それが話したアクセプターから最新の受け入れられた提案に提案を変更します。 あなたが選ばれていない受け入れられた提案を得るかもしれないし、提案者が彼の提案をあきらめてしまうので、それは非常に保守的なようです。 しかし、我々はコンセンサスを気にするだけなので、それは大丈夫です。 最初の段階では、提案者が値が選択されているかどうかを知ることは困難です。 受け入れられた値は選択されない可能性があります。 しかし、選択された値は、サーバーの大多数によって受け入れられなければなりません! る(ステップ<3 3 3 0>)。 2つの不変量を使用すると、フェーズ1で提案に返された最新の受け入れられた提案がすでに選択されているか、現時点では値が選択されていないこ いずれにしても、その価値を提案するのは安全です。

なぜminProposalを追跡するのですか?
準備段階では、まだ何も受け入れられていない間に二つのレース提案がある可能性があります。 これは、彼らが両方の段階を受け入れるように移動することを意味します。 すべての提案とF+1要件の合計注文のおかげで、少なくとも一つのアクセプターは新しい提案を見て、失われた/古い提案からのacceptメッセージを拒否します。 ここでの不変量はminProposal >= acceptedProposalです。

Screen-Shot-2018-11-14-at-12.28.11-AM

これはおそらく最も興味深いケースであり、第二の提案者は以前に受け入れられた値を見ておらず、準備段階で値が選択されていなかったためです。 この場合、先に進み、accept(Y)を他のサーバーに送信します。 S34.5より後の提案のみを受け入れることを約束しているため、Xを拒否します。 我々がminProposalを追跡しなければ、XS3によって受け入れられます。 その場合、XYの両方が3つのサーバーに受け入れられ、選択されたと見なされ、安全要件に違反します。

そこにそれがあります。 これは、単一の法令Paxosです。 それは言われている、Paxosを実装することは非常に非常に難しいことが証明されています。

  1. Paxosはシンプルにしましたhttps://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. パートタイマーの会https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. パクソスがライブで作ったhttps://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

コメントを残す

メールアドレスが公開されることはありません。