分散型選挙アルゴリズム#
内容来自
選挙(election)は分散型システムの実践において一般的な問題であり、ノード間の対等関係を破ることで選ばれたリーダー（またはマスター、コーディネーター）はトランザクションの原子性を実現し、決議の効率を向上させるのに役立ちます。
過半数(quorum)の考え方は、ネットワークが分化した場合に決議の一貫性を達成するのに役立ち、リーダー選挙のシナリオでは唯一のリーダーを選出するのに役立ちます。
リース(lease)の中心思想は、リースの期間中に 1 つのノードだけがリースを取得してリーダーとなり、期限が切れた後はリースを再発行しなければならないことを保証し、常に 1 つのリーダーだけが存在することを確保し、ハートビートメカニズムのみを使用する場合にネットワークの混雑や瞬断によって二重マスターの問題が発生するのを避けます。
Bully アルゴリズム（選挙）#
Bully アルゴリズムは最も一般的な選挙アルゴリズムであり、各ノードに対応する番号が必要で、番号が最も高いノードがリーダーとなります。リーダーがダウンした後、次に高い番号のノードが再選出されてリーダーとなります。
Bully アルゴリズムの選挙プロセスでは、以下の 3 種類のメッセージが必要です：
- Election メッセージ、選挙を開始するために使用されます；
- Alive メッセージ、Election メッセージへの応答；
- Victory メッセージ、選挙に成功したマスターノードが他のノードに送信する権利を宣言するメッセージ。
選挙プロセス#
- クラスター内の各ノードは、自分の ID が現在生存しているノードの中で最大であるかどうかを判断します。もしそうであれば、他のノードに Victory メッセージを直接送信し、自分の権利を宣言します；
- 自分が現在生存しているノードの中で ID が最大でない場合は、自分の ID より大きいすべてのノードに Election メッセージを送信し、他のノードの応答を待ちます；
- 指定された時間内にこのノードが他のノードから Alive メッセージの応答を受け取らなかった場合、自分がマスターノードになったと見なし、他のノードに Victory メッセージを送信し、自分がマスターノードになったことを宣言します；
- 自分より ID が大きいノードから Alive メッセージを受け取った場合、他のノードから Victory メッセージが送信されるのを待ちます。もしこのノードが自分より ID が小さいノードから Election メッセージを受け取った場合、Alive メッセージを返し、他のノードに「私はあなたよりも大きいので、再選挙を行います」と知らせます。
長所と短所、および適用シーン#
長所：
Bully アルゴリズムの選択は特に強引で簡単であり、生存しているノードの中で ID が最大のノードがマスターノードとなり、他のノードは無条件に従わなければなりません。このアルゴリズムの利点は、選挙速度が速く、アルゴリズムの複雑度が低く、実装が簡単であることです。
短所：
- 各ノードが全体のノード情報を持つ必要があるため、追加の情報ストレージが多くなります；
- 次に、現在のマスターノード ID よりも大きい新しいノードやノード障害から復旧したノードがクラスターに参加する場合、再選挙がトリガーされ、新しいマスターノードになる可能性があります。このノードが頻繁にクラスターから退出したり参加したりすると、頻繁にマスターが切り替わることになります。
適用シーン：
MongoDB のレプリカセットのフェイルオーバー機能
MongoDB の分散型選挙では、ノードの最後の操作タイムスタンプを ID として使用し、タイムスタンプが最新のノードが ID が最大であることを示します。つまり、タイムスタンプが最新で生存しているノードがマスターノードです。
Raft アルゴリズム（過半数）#
Raft アルゴリズムは典型的な過半数投票選挙アルゴリズムであり、核心思想は「少数が多数に従う」です。投票数が最も多いノードがマスターとなります。
Raft アルゴリズムを使用した選挙では、クラスターのノードの役割は 3 種類あります：
Leader、すなわちマスターノードで、同時に 1 つの Leader のみが存在し、他のノードを調整および管理します；Candidate、すなわち候補者であり、各ノードは Candidate になることができ、この役割の下で新しい Leader に選ばれることができます；Follower、Leader のフォロワーであり、選挙を開始することはできません。
選挙プロセス#
- 初期化時、すべてのノードは Follower 状態です。
- リーダー選挙を開始すると、すべてのノードの状態が Follower から Candidate に変わり、他のノードに選挙リクエストを送信します。
- 他のノードは受信した選挙リクエストの順序に基づいて、マスターになることに同意するかどうかを応答します。ここで注意が必要なのは、各選挙のラウンドで、1 つのノードは 1 票しか投じることができないということです。
- 選挙リクエストを発起したノードが過半数の票を獲得した場合、そのノードはマスターノードとなり、状態が Leader に変わり、他のノードの状態は Candidate から Follower に降格します。Leader ノードと Follower ノードは定期的にハートビートパケットを送信し、マスターノードが生存しているかどうかを検出します。
- Leader ノードの任期が終了し、他のサーバーが次のリーダー選挙周期を開始した場合、Leader ノードの状態は Leader から Follower に降格し、新しいリーダー選挙に入ります。
長所と短所、および適用シーン#
長所：
- 選挙速度が速く、アルゴリズムの複雑度が低く、実装が容易です。
- Bully アルゴリズムよりも安定性が高いです。これは、新しいノードが参加したりノード障害から復旧した場合にリーダー選挙がトリガーされますが、必ずしも実際にマスターが切り替わるわけではなく、新しいノードまたは障害から復旧したノードが過半数の票を獲得した場合にのみ切り替わるからです。
短所：
- システム内の各ノードが相互に通信できる必要があり、過半数の票を獲得する必要があるため、通信量が多くなります。
適用シーン：
Google がオープンソースの Kubernetes で、etcd コンポーネントを使用して Raft アルゴリズムを実装し、リーダー選挙と一貫性を実現しています。
ZAB アルゴリズム（過半数）#
ZAB 選挙アルゴリズムの核心は「少数が多数に従い、ID が大きいノードが優先的にマスターになる」ことであり、選挙プロセスでは (vote_id, vote_zxID) を使用してどのノードに投票したかを示します。ここで vote_id は投票されたノードの ID、vote_zxID は投票されたノードのサーバー zxID を示します。ZAB アルゴリズムの選挙原則は、server_zxID が最大の者が Leader となり、server_zxID が同じ場合は server_id が最大の者が Leader となります。
ZAB アルゴリズムを使用した選挙では、クラスター内の各ノードは 3 つの役割を持ちます：
Leader、マスターノード；Follower、フォロワーノード；Observer、オブザーバー、投票権なし。
選挙プロセスでは、クラスター内のノードは 4 つの状態を持ちます：
Looking状態、すなわち選挙状態。ノードがこの状態にあるとき、現在のクラスターにリーダーが存在しないと見なし、自分が選挙状態に入ります。Leading状態、すなわちリーダー状態。主が選出され、現在のノードが Leader であることを示します。Following状態、すなわちフォロワー状態。クラスター内で主が選出された後、他の非主ノードの状態が Following に更新され、Leader に従うことを示します。Observing状態、すなわちオブザーバー状態。現在のノードが Observer であり、観望的な態度を持ち、投票権と選挙権がありません。
選挙プロセス#
- システムが起動したとき、3 つのサーバーは現在の投票がすべて第一ラウンドの投票であり、epoch=1 で、zxID はすべて 0 です。この時、各サーバーは自分を推選し、投票情報をブロードキャストします。
- 判断ルールに基づき、3 つのサーバーの epoch と zxID が同じであるため、server_id を比較し、大きい者が推選対象となります。したがって、Server 1 と Server 2 は vote_id を 3 に変更し、自分の投票箱を更新して再度投票をブロードキャストします。
- この時、システム内のすべてのサーバーが Server 3 を推選したため、Server 3 が Leader に選出され、Leading 状態となり、他のサーバーにハートビートパケットを送信して接続を維持します。Server 1 と Server 2 は Following 状態にあります。
長所と短所、および適用シーン#
長所
- アルゴリズムの性能が高く、システムに特別な要求がありません。
- アルゴリズムの選挙安定性が比較的良好であり、新しいノードが参加したりノード障害から復旧した場合にリーダー選挙がトリガーされますが、必ずしも実際にマスターが切り替わるわけではありません。
短所
- ブロードキャスト方式で情報を送信するため、ノードに n 個のノードがある場合、各ノードが同時にブロードキャストすると、クラスター内の情報量は n*(n-1) 個のメッセージとなり、
ブロードキャストストーム（分散型排他制御の分散アルゴリズムにおける「信号ストーム」に類似）を引き起こしやすくなります。 - 投票に加えて、ノード ID とデータ ID の比較も追加されるため、すべてのノードの ID とデータ ID を知っている必要があり、選挙時間が相対的に長くなります。
適用シーン
ZooKeeper の分散型調整機能を実現するために設計されています。
まとめと分析#
3 つのアルゴリズムの比較分析#
マインドマップのまとめ#
思考の拡張#
1. なぜ「過半数」選挙アルゴリズムは通常奇数ノードを採用するのか？#
2 つのノードがそれぞれ半分の票を獲得する可能性があり、偶数ノードを採用するとマスターを選出できず、再投票が必要になります。しかし、再投票を行っても、2 つのノードが同じ票数を持つ確率は非常に高いです。
2. 分散型選挙と一貫性の関係は何か？#
一貫性は、複数のレプリカ間で同時に同じ値を持つことができるかどうかを指します。分散型選挙は通常、一貫性を実現するための基盤であり、マスターノードを選出して他のノードを調整および管理することで、他のノードの秩序ある運用と各ノード間の一貫性を保証します。
3. クラスター内に二重マスターのシナリオは存在するのか？#
二重マスターの状況は、一般的にネットワーク障害、例えばネットワーク分割（特定の時点でクラスターがネットワークの不通により 2 つのネットワーククラスターに分かれる）などによって引き起こされます。二重マスターの期間中、両方のマスターがサービスを提供すると、クラスター内のデータが不一致になる可能性があります。したがって、データの不一致に対するビジネスの許容度に基づいて、二重マスターの状況でサービスを提供することを許可するかどうかを決定する必要があります。
連想記憶：クラスターの脳裂現象、参考：