分散型選挙アルゴリズム#
内容来自
選挙(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状態、すなわち選挙状態。この状態にあるノードは、現在のクラスターに Leader が存在しないと考え、自ら選挙状態に入ります。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 つのネットワーククラスターを形成する）などによって引き起こされます。二重主の期間中、もし二重主がサービスを提供すると、クラスター内のデータが不一致になる可能性があります。したがって、ビジネスがデータの不一致に対する許容度に基づいて、二重主の状況でサービスを提供することを許可するかどうかを決定する必要があります。
連想記憶：クラスターの脳裂現象、参考：