# リーダー選出 ## 定義 リーダー選出（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）でリーダー選出 ## 横断的知見 - **ランダム化 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]]) ## 未解決の問い - `electionTimeout` の下限（Raft では 10–500 ms の範囲）は安定ストレージの fsync レイテンシに束縛される。NVMe SSD・Optane 等の次世代メディアが使われる場合、タイムアウトはどこまで短縮でき、可用性はどう変化するか？ - 大規模クラスタ（数百〜数千ノード）での Raft 選挙はすべてのノードへの RPC 送信が前提。階層的 Raft やシャーディングによる最適化は何を犠牲にするか？ ## 関連 - [[分散コンセンサス]] — リーダー選出の根底となる合意問題 - [[複製ステートマシン]] — リーダー選出が解決する問題の文脈 ## 出典 - [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]（Raft のリーダー選出詳細・性能実験・ランダム化設計決定の経緯） - [[@2024__SIGMOD__Amazon MemoryDB - A Fast and Durable Memory-First Cloud Database]]（ログベースリーダー選出との対比）