問題タブ [paxos]

複数のマシン間で合意に達する手段として、paxos と 2 フェーズ コミットの違いを理解しようとしています。2 フェーズ コミットと 3 フェーズ コミットは非常に理解しやすいものです。また、3PC は 2PC でブロックしてしまう障害の問題も解決しているようです。そのため、Paxos が何を解決しているのかよくわかりません。Paxos が正確に解決する問題について誰か教えてくれませんか?

Raft、Paxos、Zab などの現在のマスター選出アルゴリズムがクラスターでマスターを選出する方法を読みましたが、単純ないじめアルゴリズムではなく洗練されたアルゴリズムを使用する理由を理解できませんでした。

クラスタ ライブラリを開発しており、ハートビート メッセージに UDP マルチキャストを使用しています。各ノードはマルチキャスト アドレスに参加し、定期的にデータグラム パケットをそのアドレスに送信します。ノードが、このマルチキャスト アドレスにパケットを送信する新しいノードがあることを検出した場合、そのノードは単にクラスターに追加されます。同様に、クラスター内のノードがノードからパッケージを取得しない場合、ノードはクラスターから削除されます。マスター ノードを選択する必要がある場合は、クラスター内のノードを反復処理して最も古いノードを選択するだけです。

このアプローチは効果的ではなく、Paxos のようなより洗練されたアルゴリズムを使用して、マスターを選択したり、ハートビート メッセージを介して障害を検出したりする必要があることを示唆する記事をいくつか読みました。Raft を使用せずにノードのクォーラムがいつクラスターから離脱するかを簡単に見つけることができるため、Paxos が従来のいじめアルゴリズムよりもスプリットブレイン シナリオやその他のネットワーク障害に適している理由を理解できませんでした。唯一の利点は、各サーバーが処理しなければならないパケットの数です。マスターのみが Raft でハートビート メッセージを送信しますが、この場合、各ノードはハートビート メッセージを相互に送信する必要があります。ただし、マスター選択アルゴリズムを変更せずに同様のハートビート アルゴリズムを簡単に実装できるため、これは問題ではないと思います。

誰かがそれについて詳しく説明できますか？

私はこれらの 2 つの技術についてかなり混乱しています。

1. これらの 2 つの技術の間に関係はありますか

2. これらの技術を実装した既存の一般的なオープン ソース ソフトウェアはありますか? Zookeeper が Paxos を実装していることは知っていますが、2 フェーズ コミットはどうですか?

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

ウィキやその他の情報源から 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)、承認された最大の提案番号と値を持っているため、同期していますか?

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

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

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

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

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

これらの場合にアルゴリズムが失敗するかどうかを推論して理解しようとしましたが、失敗する例を見つけることができないようです。

そうでない場合、なぜこれらのどれも従わないのですか?

ここのドキュメントには次のように書かれています：

3 サーバー アンサンブルでは、1 台のサーバーに障害が発生しても、サービスは引き続き利用できます。

ただし、定足数を確立するには、ceil(n/2)+1ノードが必要です

3 ノードの場合、次のようになります。
ceil(3/2)+1 = ceil(1.5)+1 = 3

そのため、1 つのノードがダウンした場合、クォーラムは確立されず、zookeeper はダウンするはずです。

この場合、上記のドキュメントは間違っていますか?

Cassandra の軽量トランザクションに実装されている Paxos アルゴリズムに関して、非常に具体的な質問があります。

2 つのノードが同じプロポーザルを同時に発行するとどうなりますか? どちらも ' [applied]: true ' になりますか?

たとえば、次の表を考えてみましょう。

そして、このクエリ：

このクエリを実行すると、次の応答が返されます。

再度実行すると、next_id != 1 であるため受け入れられません。次のようになります。

私の質問は、このクエリを 2 つのノードから並行して実行するとどうなるかということです。どちらも受かる可能性はありますか？

（私のユースケースは、このスタックオーバーフローの質問で説明されています）

フェーズ 2. (a) プロポーザーは、多数のアクセプターから準備要求 (番号 n) に対する応答を受信した場合、それらのアクセプターのそれぞれに、値 v を持つ番号 n の提案の承認要求を送信します。ここで、v は応答の中で最大番号の提案の値、または応答が提案を報告しなかった場合は任意の値です。

論文で述べたように、

提案者は、いくつかのアクセプターのセットに、提案が受け入れられるようにという要求を送信することにより、提案を発行します。(これは、最初のリクエストに応答したアクセプターのセットと同じである必要はありません。)"

しかし、私の理解では、フェーズ 2.(a) を次のように変更すると:

プロポーザーが多数のアクセプターから準備要求 (番号 n) に対する応答を受信した場合、値 v を持つ番号 n のプロポーザルの多数決アクセプターの任意のセットにアクセプト要求を送信します。応答の中で最大番号の提案、または応答が提案を報告しなかった場合は任意の値です。

アルゴリズムは失敗します。以下に例を示します。全部で 3 つのアクセプター ABC があるとします。X(n:v,m) を使用して、アクセプタ X のステータスを示します。プロポーザル n:v は、X によって受け入れられた最大の番号のプロポーザルです。ここで、n はプロポーザル番号、v はプロポーザルの値、m はX がこれまでに応答した最大の番号付きの準備要求の番号。

1. P1 が「prepare 1」を AB に送信
2. 両方の AB は、1 より小さい番号の要求を受け入れないことを約束して P1 に応答します。これで、ステータスは次のようになります: A(-:-,1) B(-:-,1) C(-:-,-)
3. P1 は応答を受信し、スタックして非常に低速で実行されます
4. P2 は「prepare 100」を AB に送信します
5. 両方の AB は、100 より小さい番号の要求を受け入れないことを約束して P2 に応答します。現在のステータスは次のとおりです: A(-:-,100) B(-:-,100) C(-:-,-)
6. P2 は応答を受信し、値 b を選択して、「accept 100:b」を BC に送信します。
7. BC が受け入れ要求を受け取り、受け入れます。ステータスは A(-:-,100) B(100:b,100) C(100:b,-) です。提案 100:b が選択されていることに注意してください。
8. P1 は再開し、値 a を選択し、「accept 1:a」を BC に送信します
9. B はそれを受け入れませんが、C は何も約束したことがないため、C は受け入れます。ステータス: A(-:-,100) B(100:b,100) C(1:a,-)。選択された提案は放棄され、Paxos は失敗します。

ここで何か見逃しましたか？ありがとう。