問題タブ [paxos]

Paxos made simpleでは、ランポートはアルゴリズムのフェーズ 2 (a) を次のように説明しています。

プロポーザーがその準備要求 (番号 n) に対する応答を多数のアクセプターから受信した場合、値 v を持つ番号 n のプロポーザルを求めるアクセプターのそれぞれに受け入れ要求を送信します。ここで、v は最高値です。回答中の番号付きの提案、または回答が提案を報告しなかった場合は任意の値です。

• これは、提案者は、提案番号に関係なく、受諾者の過半数から応答を集めたらすぐに受諾要求を送信できることを意味しますか? (引用の強調された部分は、そのことを暗示していると思います。なぜなら、同じ番号の提案はすべて同じ値を持つべきだからですよね?)
• それとも、提案者は、多数の承認者から同じ提案番号で応答する必要がありますか? (つまり、番号m ( nより小さい) の応答は、番号nの応答の過半数にはカウントされません)

paxosアルゴリズムでは、wikiに説明があります：

フェーズ 2a: 要求を受け入れる

プロポーザーがアクセプターのクォーラムから十分なプロミスを受け取った場合、そのプロポーザルに値を設定する必要があります。いずれかのアクセプタが以前に提案を受け入れた場合、その値が提案者に送信されます。提案者は、その提案の値を、アクセプタによって報告された最大の提案番号に関連付けられた値に設定する必要があります。この時点までにどの Acceptor も提案を受け入れていない場合、Proposer はその提案に任意の値を選択できます。[17] Proposer は、Accept Request メッセージを、その提案に選択した値とともに、Acceptor の Quorum に送信します。

プロポーザーが Propose(4) を 5 つのアクセプターに送信し、Ack(abc, 2)、Ack(abc, 2)、Ack(xyz, 3) を受信したとします。Accept(xyz, 4) を送信する必要があります。

私の質問は:

1. 提案者が最後に Accept(xyz,4) を送信する必要がある場合、提案者が独自の値を使用して承認要求を送信するとき。受け入れる(qwe,n)?

2. Ack(xyz,3) を送信するアクセプタは、新しいアクセプトを確認したときに何をしますか?またその理由は?

ありがとう

マルチ Paxos を使用してキー バリュー ストアを実装します。複数のノードがあり、そのうちの 1 つがプライマリ ノードです。このプライマリ ノードは更新要求を受け取り、値をスレーブ ノードに複製します。

私の質問は、プライマリ ノード (またはリーダー) がどのように選択されるかです。Paxos アルゴリズムを引き続き使用できますか? もしそうなら、paxos の実装を、レプリケーション ユニットだけでなくリーダー選出ユニットでも使用できる単一のユニットに抽象化する必要があると思いますか?</p>

ID が最小のノードをリーダーとして使用するとどうなりますか? マスター リースを実装するにはどうすればよいですか?

回答ありがとうございます。

以下の質問は、軽薄ではなく真剣であることを意図しています。分散システムの経験はありませんが、基本的な Paxos がどのように機能するか、およびリーダーの選択が役立つ理由は理解しています。残念ながら、私の理解は、以下の質問を理解するのに十分ではありません.

論文Consensus on Transaction Commitの 8 ページ (リンクされた PDF の 11 ページ) には、次のステートメントがあります。

一意のリーダーを選択することは、コンセンサス問題を解決することと同じです。

この声明が真実であり、コンセンサスを達成することが Paxos のまさに目的である場合、なぜ Paxos 自体が一般的にリーダー選挙に使用されないのでしょうか?

さらに、同じ論文は、Stable Leader Election論文で説明されているリーダー選出アルゴリズムを支持しています。

2 つの問題が同等であり、同じ論文が別のリーダー選出アルゴリズムを支持している場合、Paxos の代わりに一般的なコンセンサス問題を解決するために他のアルゴリズムを使用しないのはなぜですか?

Paxos アルゴリズムの使用について混乱しています。Paxos はそのようなシナリオに使用できるようです: 複数のサーバー (クラスター、各サーバーには 3 つの役割、提案者、受け入れ者、リーナーがすべてあると仮定します) は、一貫性とバックアップを実現するために同じコマンド シーケンスを保持する必要があります。このサーバーにコマンドを送信するクライアントがいくつかあると思います（クライアントは並行して送信する場合があります）。コマンドが 1 つの Paxos インスタンスによって複数のサーバーにディスパッチされるたびに。

1. 異なるクライアントは、異なる提案者に異なるコマンドを送信できますよね?

その場合、一部のクライアントからの 1 つのコマンドで Paxos インスタンスが生成されます。そう、

2. 複数の Paxos インスタンスを同時に実行できますか?

もしそうなら、クライアント A は提案者 A に「A += 1」コマンドを送信し、クライアント B は提案者 B に「B += 2」コマンドをほぼ同時に送信します。各サーバーが 2 を受信したことがわかります。コマンド、「A += 1」および「B += 2」。

でも、

3. 5 つのサーバー、たとえば S1 ～ S5、S1 はコマンド "A += 1" を送信し、S5 はコマンド "B += 1" を送信すると、S2 は S1 を約束しますが、S3、S4 は S5 を約束するため、最終的に S3、S4、S5 は "B + = 1」ですが、プロミスの数が過半数ではないため、S1,S2 は何も得られませんでした。Paxos はまったく役に立たないようです。5 台のサーバーすべてで、期待される「A += 1」と「B += 2」が得られませんか?

4. では、Paxos の実際のアプリケーションでは、並列 Paxos インスタンスは許可されないのでしょうか? もしそうなら、並列 Paxos インスタンスを回避する方法は、複数のクライアントと複数のプロポーザーを許可した場合、Paxos が実行されているかどうかにフラグを付けるための中央サーバーが必要なようです。

5. また、提案者番号について質問があります。私はインターネットを検索し、以下が解決策であると主張する人もいます
   : 5 つのサーバー、対応するインデックス k(0-4) を指定すると、各サーバーはこのサーバーの "i" 番目の提案に番号 5*i + k を使用します。

server-1 の最初の提案番号は常に 1 で、server-4 の最初の提案番号は常に 4 であるため、これは要件をまったく満たしていないように見えますが、server-4 は server-1 よりも早く提案を提起する可能性がありますが、それは提案です数の方が大きいです。

multi-paxos を実行している場合、ノードは次のように表示されます。

これは、次のいずれかが原因である可能性があります。

• 安定したリーダーがありましたが、このノードにローカルなネットワークがドロップされた場合、+2 と +3 の遅延が発生しました。
• +2 と +3 が失敗したラウンドの提案であるなど、提案する試みが 2 回あったような停止がありました。

一般に、分散有限状態マシンでの操作は、ノードがすべての操作を順番に適用する必要があるように変更されません。これは、ノードが 2 つのケースを区別できる必要があることを意味します。提案のラウンドが失敗した場合、ノードに問題はありません。メッセージが失われた場合は、ノードが起動するまで待機する必要があることを示唆しています。

これを処理するためのオプションまたは戦略は何ですか?また、それらによってどのようなオーバーヘッドが発生しますか?

この質問は、In Paxos に触発されています。アクセプターは、既に値を受け入れた後に別の値を受け入れることができますか?

分散クラスターからコンテンツを読み取る方法を紹介してくれる人はいますか?

つまり、Paxos アルゴリズムによって一貫性が保証されている分散クラスターがあるということです。

実際のアプリケーションでは、クライアントはクラスターに書き込んだ内容をどのように読み取るのでしょうか?

たとえば、5 台のサーバーのクラスターでは、そのうちの 3 台だけが最新のデータを取得し、残りの 2 台はネットワークの遅延などのために古いデータを取得している可能性があります。

これは、クライアントがすべてのノードの少なくとも大部分を読み取る必要があることを意味しますか? 5 台のサーバーでは、少なくとも 3 台のサーバーからデータを読み取り、バージョン番号が最新のものを確認することを意味します。

もしそうなら、あなたは3部読む必要があるので、それはかなり遅いようですか？現実の世界ではこれをどのように実装していますか?

multi-paxos がmulti-paxosと呼ばれるのはなぜですか? どうやって「マルチ」なのかわからない。

Operational Transform と CRDT の主な違いを簡単に説明してもらえますか?

私が理解している限り、どちらも分散システムの異なるノードで競合することなくデータを収束させるアルゴリズムです。

どのユースケースでどのアルゴリズムを使用しますか? 私の知る限り、OTは主にテキストに使用され、CRDTはより一般的で、より高度な構造を正しく処理できますか?

CRDT は OT よりも強力ですか?

私がこの質問をするのは、HTML 文書用の共同エディターを実装する方法を調べようとしていて、最初にどの方向を見ればよいかわからないからです。私は、ShareJS プロジェクトと、ブラウザ上でcontenteditables要素のリッチ テキスト コラボレーションをサポートしようとする試みを見ました。ShareJSのどこにも、そのためにCRDTを使用しようとする試みは見られません。

また、Google Docs が OT を使用していることもわかっており、リッチ ドキュメントのリアルタイム編集に非常にうまく機能しています。Google が OT を選択したのは、当時 CRDT があまり知られていなかったからですか? それとも今日も良い選択でしょうか？

データベースでこれらのアルゴリズムを使用するなど、他のユースケースについても知りたいです。Riak は CRDT を使用しているようです。OT を使用してデータベースのノードを同期し、Paxos/Zab/Raft の代わりにすることはできますか?