4

ここのタイトルは誤解を招く可能性があります。例を通して私の疑問を説明するために最善を尽くします。

ウィキやその他の情報源から paxos アルゴリズムについて読んでいます。

1) 値を更新するクライアントの要求 (X以下の例) が処理される状況を想像してください。Paxos の 1 ラウンド後、値Vbが選択されます。これは、Acceptor が Proposer に返信するときに、以前に受け入れられた Proposal 番号と対応する値が含まれているためです。以下の例では、3 つのアクセプターが、(8,Va),(9,Vb),(7,Vc)現在 を持っているプロポーザーに送信します(10,X)。受信(9,Vb)した最大の提案番号であるため、値を取得(10,Vb)し、すべてのアクセプターに値をブロードキャストして承認します。Xそのため、この Paxos のラウンド全体が処理された初期値は更新されませんでした。この場合、X への更新のクライアント トランザクションは失敗しましたか?

この後のアクセプターの最終的な状態は何ですか? それらはすべて(10,Vb)、承認された最大の提案番号と値を持っているため、同期していますか?

クライアント 提案者 受容者 学習者
   | | | | | | | | | | | | | | --- 最初のリクエスト ---
   X-------->| | | | | | | | | | | リクエスト
   | | X--------->|->|->| | | | | 準備する(10)
   | | |<---------X--X--X | | | Promise(10,{(8,Va),(9,Vb),(7​​,Vc)}
   | | X--------->|->|->| | | | | 受け入れる!(10,9,Vb)
   | | |<---------X--X--X------>|->| 可(10,9,Vb)
   |<---------------------------------X--X 応答
   | | | | | | | | | | | | | |

2) より複雑なケースで、2 つの提案が行われますが、コンセンサスに到達しようとする時点が異なります。Xこれは、リージョン A のクライアント C1 が一部のデータを変更していて、まだコンセンサスに達していない一方で、リージョン B のクライアント C2 が同じデータを変更している状況を想像してくださいX。クライアントの要求の 1 つが拒否されましたか? C2 は C1 よりも遅く発生することに注意してください。ただし、コンセンサスにはまだ達していません。順序付けに従う場合、C1 リクエストを終了し、コンセンサスを受け入れてから、C2 リクエストを処理する必要があります。このブログの私の理解から、この場合、C1 リクエスト値が選択されます。

では、C2 リクエストは放棄されたのでしょうか。それは良い選択肢ではないかもしれません。

例 (このブログからの著作権):

ここに画像の説明を入力

この場合、v=8が最終的に選択されますが、 request forV=5はクライアントによって要求された最新の更新です。なぜそうなのですか？これは深刻な影響を与える可能性があります

助けてくれてありがとう、明けましておめでとう！

4

1 に答える 1

4

これを説明するために、いくつかのコンテキスト、つまり OSI プロトコル スタックの解釈を示します。

+------------------------+
|100. Your Application   |
#========================#
|8. Some state machine   |
|   or key/value store   |
+------------------------+
|7. Transaction log      |
+------------------------+
|6. Paxos                |
+------------------------+
|5. Some framing protocol|
+------------------------+
|4. TCP                  |
+------------------------+
|...                     |
+------------------------+

私が見た paxos のすべての本格的な実装は、同様のモデルを使用しています (そして、多くの本格的な実装を見てきました)。つまり、Paxos はステート マシンのトランザクション ログ内の次のエントリを選択するために使用されます(トランザクション ログがなければ、データベースは高価で遅く、バグのあるキャッシュに過ぎないためです)。トランザクション ログのエントリごとに異なる Paxos インスタンスがあります。それらは完全に独立しています。システムの設計者が非常に頭が良ければ、Paxos インスタンスを並行して実行することもできます。

それでは、あなたの質問に進みましょう。

はい、最初の例の X は失敗しました。選ばれませんでした。上位層に失敗を返す必要があります。これは必ずしもクライアント (上記のモデルでは「あなたのアプリケーション」) にとっての失敗を意味するわけではありません。上位層は、トランザクション ログの後のエントリで値を再試行することを決定する場合があります。または、クライアントに失敗を返すだけかもしれません。

2 番目の例では、これらの要求の 1 つを最後に拒否する必要があります。Paxos は最大で 1 つの値を選択します。そして、その値が選択されると、選択されたままになります。チャック・ノリスが選んだかのように。

しかし、その 2 番目の例には少し誤解があるようです。どちらの要求が最初に開始されたかは問題ではありません。ネットワークのレイテンシーと惑星の配置により、2 番目のリクエストが最初のリクエストを追い越してしまう可能性があります。

それを試してみてください！X、Y を値として使用します。提案者としての P1、P2。アクセプターとしてのA1、A2、A3：

  1. P1 には X があり、Prepare(1) を送信します
  2. A1 は 1 を約束し、Accepted(0,_) を返します。
  3. A2 は 1 を約束し、Accepted(0,_) を返します
  4. A3 は 1 を約束し、Accepted(0,_) を返します
  5. P1 にはまだ X があり、Accept(X,1) を送信します。
  6. A1は(X,1)を受け入れます
  7. P2 には Y があり、Prepare(2) を送信します。
  8. A2 は 2 を約束し、Accepted(1,_) を返します
    • ご覧のとおり、A2 は 2 未満のラウンドを受け入れないように切り替えました。
  9. A2 は Accept(X,1) を拒否します
  10. A3 は 2 を約束し、Accepted(1,_) を返します
  11. P2 にはまだ Y があり、Accept(Y,2) を送信します。
  12. A2 受け入れます(Y,2)
  13. A3 受け入れます(Y,2)
    • そして単純多数決でYが選ばれました。提案者がこれから何をしようとも、Y の値は常に選択されます。

これは実際には、2 番目の例の図のように始まりますが、この例では、ネットワークは 2 番目の提案者を支持しました。

于 2015-01-03T18:37:00.060 に答える