問題タブ [consensus]

フェーズ 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 は失敗します。

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

ZooKeeper、Consul、Eurekaなどのコンセンサスタイプのツールを見ていますが、それらはすべて同じソリューションセットを販売しているようです:

• サービス発見
• 動的な集中構成管理
• 同期プリミティブ
• コンセンサスアルゴリズム

しかし、これらのことについて読めば読むほど、サービス ディスカバリが動的な集中構成管理 (KV ペア) システムと実際にどのように異なるのかを理解するのに苦労します。

サービス ディスカバリに関する私の理解(これまでのところ) は、ノードがリモート サービスを動的に検索、検索、および接続できるようにすることです。したがって、アプリケーションがAuthService認証、認可に を使用する場合、サービス検出を使用してAuthServiceノードを検索し、http://auth103.example.org:9103それを使用します。

動的構成システムについての私の理解では、ノードが構成サーバーから更新を動的に受信し、更新を公開するための集中型インフラストラクチャを提供するということです。そのため、アプリ インスタンスが他のすべてのインスタンスの構成を更新する必要があると判断した場合、構成サービスにアクセスして、構成などを更新しますnumPurgerThreads。その後、構成サービスは他のすべてのアプリ インスタンスを更新して、それぞれの構成を適切に更新します。

しかし、これらはまったく同じ問題ではありませんか?

どちらの場合でも、次のことを行います。

1. ある種の検索サービスに接続する
2. データを照会します。また
3. そこにデータを公開し、それを他のノードに波及させます

サービス ディスカバリは動的な構成ですよね!?!

私が実際に推進しているのは、これらのツールの 1 つを使用して 1 つの構成サービスを実装するだけで、偶然にもサービスの検出も解決できないのではないかということです。または、構成/KV 管理用に 1 つの Consul クラスターと、サービス検出用に別の Consul クラスターが必要になる理由はありますか?

コンセンサスとの違いを特定するために、複数のデータセットを調整しようとしています。それぞれにおそらく 30,000 レコードの同じデータが 100 セット存在する可能性があります。各セットには同じ列がありますが、同じ行がない場合があります。つまり、Person1 のレコードは 1 つのセットにのみ存在する場合もあれば、すべてのセットに存在する場合もあります。異なるレコードのみを特定し、その違いを報告したいと考えています。おそらく例を挙げたほうが簡単でしょう。

セット1:

Paxos を使用して、サイズが約 50MB で、個々のノードで常に変更されているファイルのノード間のコンセンサスを維持しようとしています。実用性の問題に直面しています。要件：

1. 数百のノード間で 50MB 以上のファイルを同期
2. このファイルに変更を加えます。これはどのノードからでも行うことができ、互いに直接競合する可能性は低く、せいぜい数秒でネットワーク全体に伝播されます。
3. ネットワークに参加する新しいノードは、Paxos メッセージに従って、数分 (1 時間未満) 以内にファイル全体を構築できます。

私が直面している問題は、目標 2 と 3 の両方を達成する方法がないように見えることです。

これまでに検討したオプションは次のとおりです。

• ラウンドごとにファイル全体を同期する — 完全に非現実的で、Paxos ラウンドには数分かかります
• ファイルへの変更のみを同期 — 目標 1 と 2 には妥当ですが、新しいノードはすべての状態単位が変更された後にのみファイル全体を同期できるため、目標 3 を破ります。
• ラウンドごとに変更とファイルのランダムな部分を同期します — Paxos がこれを許可するかどうかはわかりません。ノードは自分自身に対して変更を検証することができ (新しい変更を許可する)、ファイルのランダムな部分をそれらのバージョンのその部分に対して検証することができますが、これは実用的ですか?

私は 3 番目のオプションが最適だと考えていますが、Paxos がこれを許可するかどうかはわかりません。アイデアは、各ラウンドで交換されるデータをおそらく 1500 バイトに制限し、その 1500 バイトを主にファイルへの変更で埋めることです。ほとんどのラウンドでは、ファイルは変更されず、何かが変更されたラウンドは 100 バイト未満の変更された状態である可能性が高いため、他の 1400 バイトはファイルの一部で満たされる可能性があり、これにより新しいノードを構築できます。時間をかけてファイル全体をアップします。これは実用的ですか？この問題はすでに解決されていますか?

リーダーがログ エントリを取得すると、それをクラスタ内の他のサーバーに複製します。次に、エントリをコミットし、他のサーバーにもコミットするように指示します。ここには 2 つのケースがあるようです:
1) リーダーがエントリをコミットし、他のサーバーにもコミットするように指示します。
2) リーダーは全員にコミットするように言い、それからリーダーも実行します。

#1 で、他の人にコミットするように指示する前にリーダーがクラッシュした場合、コミットされていなくても、新しいリーダーになる人は誰でもエントリを使用しますか? そうでない場合は、最新のエントリと同期していないログがいくつかあります。(古いリーダーはそれを適用し、他のリーダーは適用しなかったでしょう。) もしそうなら、それをコミットしても問題ないことをどうやって知るのでしょうか?

＃2では、リーダーがコミットする前にクラッシュした場合、コミット後に他のすべてのノードがクラッシュし、選挙で古いリーダーが再び新しいリーダーになり、他のサーバーは新しいリーダーがコミットしていないエントリをコミットしました持っていません。この場合はどうなりますか？

コンセンサスに任意の数のスレッドが到達できることを示すために、peek() メソッドを使用するキューを使用するコンセンサス プロトコルを実装する必要があります。つまり、peek() メソッドを使用するキューには無限のコンセンサス数があります。

これは私のコードです

私の理解では、2 つのスレッドが異なる値を返す場合、peek() は異なるスレッド ID を返す必要があり、スレッド ID をプッシュする前に各スレッドが独自の値をプロポーザルに書き込むため、妥当性が保証されるため、これは機能するはずです。

私がどこで間違っているのかを理解し、コードを修正する方法を教えてくれる人はいますか

特にデータベーストランザクションのコンテキストで、paxos についていくつかの混乱がありました。

「paxos made simple」という論文では、第 2 段階で、提案者は、アクセプターの 1 つが以前に受け入れた最大のシーケンス番号を持つ値の 1 つを選択する必要があると述べています (そのような値が存在しない場合、提案者は自由に選択できます)。提案された元の値を選択します)。

質問:

1. 一方では、コンセンサスを維持するためにそうしていることを理解しています。しかしその一方で、値が実際に何であるかについて混乱がありました。「以前に受け入れられた値をアクセプターに送信する必要がある」という点は何ですか?

2. データベース トランザクションのコンテキストで、新しい値をコミットする必要がある場合はどうなるでしょうか? Paxos の新しいインスタンスを開始する必要がありますか?

3. 上記の質問に対する答えが「はい」の場合、アクセプターはどのように状態をリセットしますか? (私の理解では、状態がリセットされない場合、提案者は、新しい値が何であれ自由にコミットするのではなく、以前に受け入れられた古い値のいずれかを送信することを余儀なくされます。)

下の図は、基本的な Paxos のメッセージ フローです。フェーズ 2a で、リーダーはその提案 1 の値 Vn を選択し、Accept!(1,Vn) をすべてのアクセプターに送信します。私の質問は、これら 3 つのメッセージのうち 2 つが失われた場合はどうなるかということです。Accept!(1,Vn) を受け取るのは Acceptor 1 (多数派ではない) だけです。Acceptor 1 はこの要求を受け入れますか? そして、すべての学習者にブロードキャストしますか? この値は選択されていますか?

いくつかのマシンをエラスティック クラスターに投入し、その中で何らかのコンセンサス アルゴリズムを実行したいとします (Paxos など)。彼らがネットワークの初期サイズ、たとえば 8 台のマシンを知っているとします。

したがって、彼らはコンセンサス アルゴリズムを実行し、定足数は 5 です。

ここで、次のケースを検討してください。

1. CPU が少なすぎることがわかり、クラスター サイズを半分の 4 台のマシンに減らしました。
2. パーティション分割があり、各分割には 4 台のマシンが割り当てられます。

クォーラムを取得するために現在のクラスター サイズを使用すると、パーティションが分割される可能性があります。基礎となるクラスターの場合、状況 (1) と (2) はまったく同じに見えます。ただし、固定数を使用すると、クラスターをスケールダウンできません (スケールアップすると、パーティションによる不整合が発生します)。

スケーリング時にすべてのマシンにクラスターのサイズを通知する 3 つ目の方法がありますが、たとえば、スケールアップの直前にパーティションが発生し、そのパーティションが新しいサイズを受け取らず、十分なクォーラムを持っていない可能性があります。古いサイズを使用したコンセンサス。

Paxos (およびその他の安全なコンセンサス アルゴリズム) は、柔軟な環境では使用できませんか?