1

多くのスレーブ間でマスターを昇格させるために、レプリケーションアルゴリズムを設計しています。Paxosよりも速くてシンプルにしたいと思っています。基本的な考え方は次のとおりです。

  1. 各ノードに「プロモーション優先度」を割り当てます。たとえば、5つのノードの場合、優先度は50、40、30、20、10、50が最高、10が最低になります。
  2. マスターを選出する必要がある場合、すべてのスレーブは他の4つのノードにマスターになることを要求するメッセージを(同時に)送信しますが、確認メッセージですべてのスレーブによって確認されるそのマスターのみが選出されます。スレーブは、自身の「プロモーション優先度」が要求ノードよりも低い場合、または優先度の高い要求ノードがタイムアウトして自身の要求に対して拒否メッセージを発行した場合に、確認メッセージを送信します。
  3. スレーブが「プロモーション優先度」の高いスレーブから拒否メッセージを受信した場合、その手順は中止されます。
  4. 同じ優先度のノードがあってはなりません。
  5. マスターになるためにスレーブが収集する必要のある確認メッセージの最小数があります。

すべてのスレーブが並行してマスターを選出し、優先順位がプロセスの高速化に役立つため、このアルゴリズムはより高速である必要があります。

あなたはそれについてどう思いますか?優先度の高いマスタープロモーションのための他のアルゴリズムはありますか?

4

1 に答える 1

1

あなたはそれについてどう思いますか?

要件の詳細を知らずに、アルゴリズムの有効性を完全に評価することは困難です。全体的には有効なアプローチのように見えますが、注意が必要な問題がいくつかあります。

あなたの質問は、多くのノードのうちの1つのノードに共有リソースを割り当てる分散アルゴリズムといくつかの類似点があります。その結果、その質問に対する私の答えで提起された議論のいくつかは、この質問にも当てはまります。

マスターを選出する必要がある場合、すべてのスレーブは他の4つのノードにマスターになることを要求するメッセージを(同時に)送信しますが、確認メッセージですべてのスレーブによって確認されるそのマスターのみが選出されます。

このアプローチは、すべてのスレーブがいつでも存在するスレーブの数を知っていることを前提としています。そうでない場合、想定されるマスターは、すべてのスレーブから確認を受け取ったときに結論を出すことはできません。暗黙的に、これは、アルゴリズムを破ることなく、スレーブがシステムを離れたり、システムに参加したりできないことを意味します。

ただし、実際には、クラッシュ、再起動、ネットワークの停止などにより、これらのスレーブ出入りします。この可能性はスレーブの数とともに増加しますが、これが問題になるかどうかは要件によって異なります。システムはどの程度フォールトトレラントである必要がありますか?

ちなみに、スレーブが多いとおっしゃっていますので、リクエストメッセージの送信にはマルチキャストまたはブロードキャストを使用していると思います。そうしないと、多くの意味によっては、すべてのスレーブが存在する場所の管理に関して、セットアップでエラーが発生しやすくなる可能性があります。

スレーブは、自身の「プロモーション優先度」が要求ノードよりも低い場合、または優先度の高い要求ノードがタイムアウトして自身の要求に対して拒否メッセージを発行した場合に、確認メッセージを送信します。

前の発言と同様に、何らかの理由で一部のスレーブが応答に問題がある場合、スレーブは誤った結論を引き出す可能性があります。実際、1つのスレーブがダウンしているか、ネットワークに問題がある場合、他のすべてのスレーブは、応答しないスレーブがマスターであるという同じ(おそらく誤った)結論を導き出します。

すべてのスレーブが並行してマスターを選出するため、このアルゴリズムはより高速になるはずです。

この回答で提起された問題は、マスターの選択を分散して行うことにほぼ固有のものであり、ある種の集中型の意思決定者を導入せずに解決することは困難です。あなたはいくつかを得る、あなたはいくつかを失う...

優先度の高いマスタープロモーションのための他のアルゴリズムはありますか?

もう1つのアプローチは、システム内のすべてのスレーブに、現在のマスターが誰であるかについての管理を常に維持させることです。これは、ある種のハートビートメッセージを介して、すべてのスレーブにその優先順位を定期的にマルチキャスト/ブロードキャストさせることによって(ある程度のネットワーク帯域幅を犠牲にして)行うことができます。その結果、すべてのスレーブは他のすべてのスレーブを認識し、マスターを選択する必要がある瞬間に、すべてのスレーブがそれを即座に実行できます。ハートビートが失われるため、ネットワークの問題またはその他の「システムヘルス」の問題が検出されます。このアルゴリズムは、システムに参加およびシステムから離脱するスレーブに関して柔軟です。ハートビートの頻度が高いほど、システムはトポロジーの変更に対してより応答性が高くなります。ただし、ネットワークが切断されているために、スレーブが独立した結論を導き出すという問題が発生する可能性があります。

于 2012-10-11T01:01:43.943 に答える