cluster-computing - いじめっ子アルゴリズムに対する高度なマスター選挙アルゴリズムの利点は何ですか?

Question

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

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

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

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

Answer 1

理論的な観点からは、Raft、Paxos、Zab はリーダー選出アルゴリズムではありません。彼らはコンセンサスと呼ばれる別の問題を解決します。

具体的なシナリオでは、違いは次のとおりです。リーダー選出アルゴリズムでは、最終的に 1 つのノードがリーダーになることのみを保証できます。つまり、一定期間、複数のノードが自分をリーダーと見なし、その結果、1 つのノードのように振る舞う可能性があります。対照的に、上記のコンセンサス アルゴリズムを使用すると、論理的な瞬間に最大で 1 つのリーダーが存在することを保証できます。

その結果がこれです。システムの安全性が 1 人のリーダーの存在に依存している場合、リーダーの選挙だけに頼ると問題が発生する可能性があります。例を考えてみましょう。ノードは UDP マルチキャストからメッセージを受信し、送信者がリーダーの場合は A を実行しますが、送信者がリーダーでない場合は B を実行します。2 つのノードがクラスター内の最も古いノードを確認する時点がわずかに異なる場合、異なるリーダーが表示される可能性があります。これらの 2 つのノードはマルチキャスト メッセージを受信し、異なる方法で処理する可能性があり、保持したいシステムの安全性に違反する可能性があります (たとえば、すべてのノードが A または B のいずれかを実行し、一方が A を実行し、もう一方が実行することはありません)。 B）。

Raft、Paxos、および Zab を使用すると、これらのアルゴリズムがある種の論理的エポックを作成し、それぞれに最大で 1 つのリーダーを持つため、この問題を克服できます。

ここで2つのメモ。まず、いじめアルゴリズムが同期システム用に定義されます。Garcia-Molina の論文で説明されているように実際に実装すると、部分的な同期システムで問題が発生する可能性があると思います。第 2 に、Zab アルゴリズムは、非同期システム用のいじめっ子アルゴリズムに依存しています。リーダーは、履歴の長さを比較することによって選出されます (システムの回復時間を最小限に抑えます)。リーダーが選出されると、リーダーのエポックをロックする Zab プロトコルを開始しようとします。