# リーダー選出 ## 定義 リーダー選出（Leader Election）とは、分散システムにおいて複数のサーバーの中から一つを「リーダー（調整者）」として選び出すプロセスおよびそのアルゴリズムである。リーダーはログ複製・クライアントリクエスト受付・コーディネーション等の責任を担い、障害時には新リーダーを選出し直す。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) **Raft のリーダー選出**（§5.2）: 1. フォロワーが `electionTimeout`（150–300 ms）の間リーダーから通信を受け取れない場合、候補者に遷移して選挙を開始する 2. 候補者は term をインクリメント、自身に投票し、全サーバーへ `RequestVote RPC` を並列送信する 3. クラスタ過半数から同一 term 内で票を得た候補者がリーダーになる 4. **投票制限**: 候補者のログが有権者のログより up-to-date（最終エントリ term が新しい、または term 同一ならログが長い）でなければ票を与えない → Leader Completeness Property 保証 5. **スプリットボート解消**: タイムアウトをランダム化（固定区間内から選択）することで通常は単一サーバーのみが先にタイムアウトして選挙を勝ち取る **タイミング性能**（5 サーバー、ブロードキャスト時間 〜15 ms での実験）: - ランダム性ゼロ（150–150 ms）: 多数の試行でスプリットボートが連続し 10 秒超の停止が発生 - 5 ms のランダム幅（150–155 ms）: 中央値 287 ms でリーダー選出 - 12–24 ms タイムアウト: 中央値 35 ms（最長 152 ms）でリーダー選出 ## 合意アルゴリズムに内蔵されない古典的な選出アルゴリズム Raft のような合意アルゴリズムはリーダー選出をコアメカニズムとして内蔵するが、これとは別に、単独のリーダー選出アルゴリズムとして古くから研究されてきた系統がある。『詳説 データベース』10章はこの系統を以下のように整理する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]) - **ブリーアルゴリズム(bully algorithm)**: プロセスのランクを比較し、もっとも高いランクのプロセスがリーダーになる3段階の選出手順。単純さで知られるが、ネットワーク分断時に安全性(同時に存在できるリーダーは最大1つ)を破りスプリットブレインを起こしうる。また、ランクの高いノードが不安定だと、選出→即障害→再選出を繰り返す問題も持つ。 - **次候補へのフェイルオーバー**: リーダーがあらかじめフェイルオーバー先ノードのリストを提供し、障害検出時に完全な選出ラウンドを経ずに代替ノードへ直接移行できるようにしたブリーアルゴリズムの改良版。 - **候補者/一般人の最適化**: ノードを候補者(candidate)と一般人(ordinary)に分割し、候補者ノードのみがリーダーになれるようにしてメッセージ数を削減する。タイブレーカー変数 δ で同時選出の衝突を緩和する。 - **招待アルゴリズム(invitation algorithm)**: ランクを競う代わりに他プロセスをグループへ招待し、グループ同士をマージしていく方式。グループ単位でリーダーが存在するため、定義上複数リーダーが許容される。 - **リングアルゴリズム(ring algorithm)**: 全ノードがリングトポロジを認識し、選出メッセージをリング上で転送しながら最高ランクのノードを収集する。リングが分断されると独自のリーダーが並立しうるため安全性を持たない。 いずれのアルゴリズムも、安全性(スプリットブレイン回避)より活性(選出が必ず完了すること)を優先する設計であり、Raft・Paxos・ZAB のような合意アルゴリズム内蔵型のリーダー選出とは異なり、安全性を保証しない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]) ## 横断的知見 - **リーダー選出は合意(コンセンサス)と等価な問題である、という宣言的な整理は、DDIA が示す「エポック番号による2段階クォーラム投票」という実装レベルの説明を裏づける**: 『詳説 データベース』10章は「リーダーを選出するには、その存在に関して合意に達する必要がある。リーダーの存在に関して合意に達することができるなら、同じ手段を使用して、他のどのような事柄についても合意に達することが可能である」と述べ、リーダー選出と合意問題の等価性を宣言する。これは、本ページが DDIA 2E 第10章から記録している「エポックごとに一意なリーダーが存在する」という弱い前提や、[[分散コンセンサス]] ページが記録する「重複クォーラム投票による安全性」という実装レベルの仕組みが、なぜ機能するのかを説明する上位の理論的根拠になる: リーダーの存在それ自体が1つの合意対象である以上、リーダー選出アルゴリズムはコンセンサスアルゴリズムの特殊形にほかならない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]] §10.6 まとめ, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "From single-leader replication to consensus") - **リーダー選出は障害検出器の上に乗る層であり、検出器の判定がそのまま選出の安定性を左右する**: 『詳説 データベース』は障害検出(9章)とリーダー選出(10章)を別章として切り分けているが、10章自身はリーダーのクラッシュ検出を9章の障害検出アルゴリズムに委ねると明記し、さらに「安定したリーダー選出のアルゴリズムは、単一の安定したリーダーの選出ラウンドとタイムアウトに基づく障害検出を使用して、リーダーがクラッシュしたりアクセス不可能になったりしない限りその地位を維持できることを保証する」と述べる。つまり、選出アルゴリズム自体は「誰をリーダーにするか」のロジックしか持たず、「いつ再選出すべきか」の判断は丸ごと障害検出器の精度に依存する。本ページが記録してきた Raft の `electionTimeout` によるタイムアウトベース障害検出も、この一般原則の一実装である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]) - **ランダム化 vs 決定論的優先順位付け**: Raft はランキングシステム（固定優先順位）を検討したが、新たなコーナーケースを生み続けたためランダム化タイムアウトを採用した。ランダム化は「どの選択でも同様に扱う」ことで状態空間を実質的に削減する。Paxos では「弱いリーダーシップ」が性能最適化として後付けされたのに対し、Raft は選挙をコアアルゴリズムの第一フェーズとして統合した。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) - **ログベースリーダー選出の変形**: Amazon MemoryDB はマルチ AZ トランザクションログの最新書き込みを持つノードを選択するログベースリーダー選出を採用する。これは Raft の「より up-to-date なログを持つ候補者が優先」という原則と類似しており、データの完全性を保ったリーダー遷移を保証する。(Source: [[@2024__SIGMOD__Amazon MemoryDB - A Fast and Durable Memory-First Cloud Database]]) - **Raft の term number は、Paxos の ballot number・VR の view number・Zab と同じ「エポック番号」という一般概念の一実装であり、実運用ではコーディネーションサービスのフェンシングトークンとして露出する**: DDIA 2E 第10章は、リーダー選出を「単一のリーダーが常に存在する」という強い前提ではなく、「エポックごとに一意なリーダーが存在する」という弱い前提に基づく設計として位置づけ直す。あるエポックのリーダーが実は生きていた場合でも、より高いエポック番号を持つ新リーダーが優先されるため、split brain は起こらない。この一般化は Raft の term number にとどまらず、ZooKeeper の `zxid`・etcd の revision number のような、コーディネーションサービスがクライアントに提供するフェンシングトークンとも直接対応する。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "From single-leader replication to consensus") - **『詳説 データベース』14章は、10章が持ち越していた「合意アルゴリズム内蔵型リーダー選出はなぜ安全性を持つのか」という問いに、クォーラムの共通部分という具体的な答えを与える**: 本ページの未解決の問いは、ブリー系・招待・リングのような単独のリーダー選出アルゴリズムが安全性(スプリットブレイン回避)を欠く一方、Raft・Paxos・ZAB のような合意アルゴリズム内蔵型リーダー選出がなぜ安全性を獲得できるのかを10章単体では説明できないと記していた。[[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.2 は「十分な数の参加ノードが提案を受け入れさえすれば、どのような2つの過半数にも少なくとも1つの参加ノードが共通して含まれているので、プロトコルはその値が受け入れられることを保証する」と述べ、これが Paxos の安全性の直接の根拠であることを明示する。ブリー系・招待・リングのアルゴリズムはランクの比較や招待関係のみでリーダーを決定し、この「過半数クォーラムの共通部分」という仕組みを持たないためスプリットブレインを防げない。過半数クォーラムこそが、単独のリーダー選出アルゴリズムと合意アルゴリズム内蔵型リーダー選出を分ける決定的な設計要素である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.2, [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]) ## 未解決の問い - `electionTimeout` の下限（Raft では 10–500 ms の範囲）は安定ストレージの fsync レイテンシに束縛される。NVMe SSD・Optane 等の次世代メディアが使われる場合、タイムアウトはどこまで短縮でき、可用性はどう変化するか？ - 大規模クラスタ（数百〜数千ノード）での Raft 選挙はすべてのノードへの RPC 送信が前提。階層的 Raft やシャーディングによる最適化は何を犠牲にするか？ - リーダー選出を障害検出器と組み合わせて安定性を得るという原則は10章で宣言され、14章はZABとRaftの具体的なハートビート機構(§14.2.2, §14.4.2)でこれを裏づけたが、障害検出器側の精度(誤検知率・検出遅延)が選出の安定性(再選出頻度)にどの程度の感度で影響するかは定量化されていない。9章の障害検出アルゴリズム(タイムアウトフリー障害検出等)とRaftの`electionTimeout`実験を突き合わせた定量分析は可能か。 - Flexible Paxos(14章§14.3.7)はクォーラムを「過半数」から「$Q_1+Q_2>N$を満たす任意の集合」へ一般化する。この一般化はリーダー選出フェーズのクォーラム$Q_1$とログ複製フェーズのクォーラム$Q_2$を非対称にできることを意味するが、リーダー選出の安定性(再選出頻度)と$Q_1$のサイズの関係は本ページではまだ定量的に整理できていない。 ## 関連 - [[分散コンセンサス]] — リーダー選出の根底となる合意問題 - [[複製ステートマシン]] — リーダー選出が解決する問題の文脈 - [[コーディネーションサービス]] — エポック番号がフェンシングトークンとして露出する実装例 - [[障害検出器]] — リーダー選出の安定性の前提となる障害検出レイヤー - [[単一リーダーレプリケーション]] — リーダー選出が新リーダー決定を担うフェイルオーバーの一段階 ## 出典 - [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]（Raft のリーダー選出詳細・性能実験・ランダム化設計決定の経緯） - [[@2024__SIGMOD__Amazon MemoryDB - A Fast and Durable Memory-First Cloud Database]]（ログベースリーダー選出との対比） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]]（term/ballot/view number をエポック番号として一般化する視点） - [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]]（ブリー系・招待・リングアルゴリズムの分類、リーダー選出と合意の等価性、障害検出との組み合わせによる安定性） - [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.2(過半数クォーラムの共通部分による安全性の根拠), §14.3.7(Flexible Paxosによるクォーラムの一般化)