リーダー選出(Leader Election)と分散システムにおける単一調整者の確保
1. 概要
A. 定義
リーダー選出(Leader Election)とは、対等な権限を持つ複数ノードから成る分散システムにおいて、特定の役割(書き込み調整、ログ複製、タスク割り当てなど)を担うただ一つのリーダーノードをノード自身が合意して選び、そのリーダーが消失したときに再び新しいリーダーを選ぶ分散調整(coordination)メカニズムである。
分散システムは単一サーバの性能・可用性の限界を超えるため、複数ノードに同一の役割を担わせる。 しかし「すべてのノードが対等である」という性質は、拡張性と可用性を与える一方で、同じ資源を同時に変更したり同じ作業を重複して実行したりする衝突を生む。 リーダー選出はこの衝突を構造的に防ぐため、ある瞬間には書き込み・調整権限を一つのノードだけに集中させ、残りを追従者(follower)とする方式である。 リーダーが消失すれば残りのノードが新しいリーダーを選びサービスを継続するので、単一調整者の単純さと複数ノードの可用性を同時に得る。
リーダー選出はそれ自体が一つの合意問題でもある。 「誰がリーダーか」についてノードが互いに異なる答えを持つと、二つのノードが同時にリーダーとして振る舞うスプリットブレイン(split-brain)が発生し、データが破損する。 したがって技術士の観点では、リーダー選出は単なる「代表選び」ではなく、安全性(最大一人のリーダー)と活性(いつかは必ずリーダーが存在)という分散合意の二つの属性を満たさねばならない問題として理解すべきである。
B. 登場背景と必要性
初期の高可用構成はアクティブ・スタンバイ(active-standby)の二重化で、人が障害を検知し手動で予備サーバを昇格させた。 この方式は検知と切り替えに分(minute)単位の時間がかかり、運用者が誤って二つのサーバを同時にアクティブにすると、ただちにデータ衝突につながった。 ノード数が数十・数百に増え、クラウドでノードが頻繁に生成・消滅する環境では、人がリーダーを指定する方式そのものがボトルネックかつ単一障害点となる。
また現代の分散データベース・メッセージブローカー・オーケストレータは「厳密に一度(exactly-once)」あるいは「線形化可能(linearizable)」の水準の一貫性を要求する。 たとえば分散データベースが複製ログを複数ノードに順番に適用するには、ログの順序を決める単一の直列化点が必要である。 スケジューラがcronジョブを厳密に一度だけ実行するには、複数のスケジューラインスタンスのうち一つだけが実際の実行権限を持たねばならない。 このように「複数存在するが決定は一つが」下すべき要求が普遍化するにつれ、障害を自動検知し数秒以内に新しいリーダーへ切り替える自動化されたリーダー選出が必須の基盤技術として定着した。
具体的にApache Kafkaは各パーティションにリーダー複製を一つ置いてすべての読み書きを処理させ、リーダーブローカーが死ぬとISR(In-Sync Replica)の中から新しいリーダーを選出する。 Kafka 3.x以降のKRaftモードは、かつてZooKeeperに依存していたコントローラ選出までRaftベースの内蔵合意で置き換え、外部調整者なしにメタデータリーダーを選出する。 これはリーダー選出が特定製品の付加機能ではなく、分散システムの中核骨格であることを示す事例である。
C. 中核的特性と満たすべき属性
リーダー選出アルゴリズムは次の属性を満たさねばならない。 第一に安全性(safety)で、「いかなる瞬間にも有効なリーダーは最大一人」でなければならない。同時に二人のリーダーが書き込みを行うとデータが分裂する。 第二に活性(liveness)で、「障害や分断が収束すればいつかは必ずリーダーが選出」されねばならない。誰もリーダーになれず永遠に止まれば可用性はゼロになる。
FLP不可能性定理は、完全に非同期なネットワークで一つでも障害ノードがあれば、安全性と活性を同時に常に保証する決定的な合意は不可能であることを証明する。 現実のシステムはタイムアウトとランダム化を導入して活性を「実用的な確率」で確保し、安全性は決して放棄しない設計を採る。 すなわちネットワークがひどく不安定なら一時的にリーダーが不在になることはあっても、二人のリーダーが同時に存在することだけは防ぐ。 第三に、リーダー選出は障害検知(failure detection)と密接である。リーダーが「本当に死んだのか、単に遅いのか」を区別することが選出の出発点であり、この判断が誤ると不要な再選出やスプリットブレインが生じる。
2. 全体構造と動作原理
A. 全体構造
リーダー選出ベースのシステムは一般に、ノード集合、障害検知層、選出アルゴリズム、そしてリーダーの任期を識別するトークン(term・epoch・fencing token)から構成される。 以下の構造図は、追従者がリーダーに追従し、リーダー障害を検知すると選出過程を経て新しいリーダーを立て、外部クライアントは常に現在のリーダーへ要求がルーティングされる流れを示す。
flowchart TB
C["クライアント / 外部要求"] --> R{"現在のリーダーへルーティング"}
R --> L["リーダーノード: 書き込み・調整・ログ順序決定"]
L -->|状態・ログ複製| F1["追従者 1"]
L -->|状態・ログ複製| F2["追従者 2"]
L -->|ハートビート| F3["追従者 3"]
F1 -. ハートビート監視 .-> D["障害検知層"]
F2 -. ハートビート監視 .-> D
F3 -. ハートビート監視 .-> D
D -->|リーダータイムアウト| E["選出手続き開始"]
E -->|新しい任期番号を付与| NL["新規リーダー確定"]
NL -->|フェンシングトークン更新| R
この構造の核心は任期番号(term/epoch)である。 リーダーが替わるたびに単調増加する番号を付与し、追従者と共有資源は「より大きな任期番号を提示するリーダーのみを認める」。 こうすれば、ネットワークで遅れて目覚めた過去のリーダーが古い任期番号で命令を出しても、資源がこれを拒否してスプリットブレインを遮断する。
B. 代表的アルゴリズム別の動作
リーダー選出アルゴリズムは大きく四つの系列に分けられ、それぞれ前提と複雑度が異なる。
(A) ブリーアルゴリズム(Bully Algorithm)。 Garcia-Molinaが1982年に提案した古典的アルゴリズムで、各ノードに固有の優先順位番号を付与し、「生きているノードのうち番号が最も大きいノード」がリーダーになる。 リーダー不在を検知したノードは、自分より番号の大きいすべてのノードに選出メッセージを送り、応答がなければ自らリーダーを宣言し、応答があればより高い番号のノードに選出を譲る。 実装は直観的だが、リーダー交代時にメッセージが$O(N^2)$まで増加し、遅いノードを死んだと誤認すると「仲間外れ交代」が繰り返される弱点がある。
(B) リングアルゴリズム(Ring Algorithm)。 ノードを論理的なリングに配置し、選出メッセージがリングを一周しながら出会ったノードの識別子を収集した後、最も大きな識別子をリーダーとして確定する。 メッセージ複雑度が$O(N)$でブリーより低いが、リング途中のノードが死ぬとリング復旧ロジックが必要で収束が遅い。
(C) 合意ベースの選出(Consensus-based、Raft/Paxos系列)。 今日の実務の標準である。Raftはノードを追従者・候補者・リーダーの三状態に置き、ランダム化された選挙タイムアウト(randomized election timeout)を使う。 追従者が一定時間(通常150~300ms)リーダーのハートビートを受け取れないと、任期番号を1上げて候補者になり、自分自身に投票した後、他のノードに投票を要請する。 過半数(quorum, N/2+1)の票を先に集めた候補者がリーダーになり、各ノードは一つの任期に一票しか与えないので、一つの任期に二人のリーダーは生じない。 ランダム化タイムアウトは、複数の候補が同時に出馬して票が割れるスプリットボート(split vote)を確率的に素早く解消する。
(D) リース型選出(Lease-based、調整サービスの活用)。 ZooKeeper・etcdのような外部調整サービスに選出を委任する方式である。 各ノードが共有ストレージで一時的(ephemeral)なキーやリース(lease)を獲得しようと競い、先に獲得したノードがリーダーになり、セッションが切れるかリース期間が満了するとキーが消えて次のノードがリーダーになる。 アプリケーションは複雑な合意を自ら実装せずとも安定した選出を得る。Kubernetesのコントローラ・スケジューラのHA構成が代表的にこのLeaseオブジェクトベースの選出を使う。
以下の状態図は、Raft系列のノードが追従者から候補者を経てリーダーになり、より高い任期番号を発見すると再び追従者に降りる過程を表す。
stateDiagram-v2
[*] --> Follower
Follower --> Candidate: 選挙タイムアウト経過
Candidate --> Candidate: スプリットボート発生、任期増加後に再投票
Candidate --> Leader: 過半数の得票を獲得
Candidate --> Follower: より高い任期のリーダーを発見
Leader --> Follower: より高い任期番号を受信
Leader --> Leader: 周期的ハートビート送信
C. フェンシングトークンとスプリットブレイン防止手続き
リーダー選出で最も危険な失敗は、「リーダーだと信じる二つのノードが同時に書き込みをする」スプリットブレインである。 ネットワーク分断、GCによる長時間の一時停止、遅いディスクなどで、既存のリーダーが自分が交代された事実を知らぬまま目覚め、過去の権限で書き込みを試みることがある。 これを防ぐ標準技法がフェンシングトークン(fencing token)である。リーダーが替わるたびに単調増加する番号を発行し、保護対象の資源(ストレージ・DB)がこれまで見た最も大きなトークンより小さいトークンの要求を自ら拒否する。
Martin Kleppmannが指摘したように、ロックやリースを「獲得した」という事実だけでは安全ではない。 リースを失ったノードがしばらく止まっていて目覚め、遅れて書き込みを送ることがあるためであり、結局は資源自身がトークンを検査して過去のリーダーの書き込みを遮断してこそ安全性が保証される。 以下のシーケンスは、過去のリーダーの遅延した書き込みが、より大きなトークンを持つ新規リーダーのために拒否される過程を示す。
sequenceDiagram
participant L1 as 過去リーダー トークン 33
participant S as 共有ストレージ
participant L2 as 新規リーダー トークン 34
L2->>S: 書き込み要求 トークン 34
S-->>L2: 受理し最大トークン 34 を記録
L1->>S: 遅延した書き込み要求 トークン 33
S-->>L1: 拒否、トークン 33 は 34 より小さい
3. アルゴリズム比較と適用事例
アルゴリズムの選択はノード数、ネットワーク仮定、要求する一貫性水準によって変わる。 以下の表は代表的な系列を比較したものだが、核心は「実務では安全性のために過半数合意または外部調整に基づく選出が事実上の標準である」という点である。 ブリー・リングは教育的価値が大きいが、遅いノードを死と誤認したときにスプリットブレインを構造的に防げず、強い一貫性が必要な現代システムには単独では使わない。
| 区分 | ブリー | リング | Raft/Paxos | リース型 |
|---|---|---|---|---|
| リーダー決定基準 | 最大識別子 | リング巡回の最大識別子 | 過半数の得票 | 共有キー先取り |
| メッセージ複雑度 | $O(N^2)$ | $O(N)$ | $O(N)$水準 | サービスに委任 |
| スプリットブレイン防御 | 弱い | 弱い | 任期+過半数 | リース+フェンシング |
| ネットワーク仮定 | 同期的 | 同期的 | 部分同期 | セッション/タイムアウト |
| 代表的用途 | 教育・小規模 | 教育 | etcd・Consul・Kafka KRaft | ZooKeeper・K8s Lease |
実務事例を見ると差がより明確になる。 ZooKeeperはZABプロトコルとepoch番号、そして順次一時ノード(sequential ephemeral znode)を用いた「最も小さいシーケンスノードがリーダー」方式の選出レシピを提供し、HBase・Kafka(旧版)・Solrなどがこれを活用した。 etcdはRaftを中核に据えてリーダーを選出し、リース(lease)とリビジョン番号で分散ロック・リーダー選出APIを提供する。Kubernetesのすべての状態がetcdに保存される以上、etcdのリーダー選出の安定性はクラスタ全体の可用性に直結する。 Kubernetesのコントローラマネージャ・スケジューラはLeaseオブジェクトを周期的に更新(renew)する方式でリーダーを維持し、更新が途切れると別のインスタンスがLeaseを獲得して数秒以内に引き継ぐ。これは調整サービスパターンがプラットフォームレベルのHAの事実上の標準であることを示す。
たとえば3ノードのetcdクラスタでリーダーが死ぬと、残りの2ノードが過半数(2/3)を成すので、数百ミリ秒以内に新しいリーダーを選んで書き込みを再開する。 逆に5ノードのクラスタが2+3に分断されると、2ノード側は過半数を成せず自ら書き込みを止める。この「少数派は止まる(fail-stop)」設計こそが、スプリットブレインを防ぐ核心原理である。
4. 深化: 障害検知の感度と実務チューニング
リーダー選出の実務的難題は、アルゴリズムそのものより障害検知の正確度と感度の調整にある。 ハートビートタイムアウトを短くしすぎると、一時的なネットワーク遅延やGC停止をリーダー死亡と誤認し、正常なリーダーを交代させる不要なリーダー交代(leadership churn)が繰り返される。 リーダーが替わるたびにキャッシュのウォーミング、ログの再整列、クライアントの再接続のコストが発生するので、churnはすなわち性能・可用性の低下につながる。 逆にタイムアウトを長くしすぎると、本当の障害で切り替えが遅れ可用性が落ちる。このトレードオフはネットワーク遅延分布(p99)とサービスのRTO目標を併せて考慮して決めねばならない。
実務ではいくつかの補強技法が使われる。 第一にプリボート(pre-vote)で、候補者になる前に「自分が出馬すれば当選可能か」を先に打診し、ネットワークから隔離されて戻ってきたノードが任期番号だけ上げてクラスタを撹乱する現象を防ぐ。 第二にリーダースティッキネス(leader stickiness)と優先順位で、特定ノードを優先リーダーに指定して不要な交代を減らし局所性を確保する。 第三にジッター(jitter)を与えたランダム化タイムアウトでスプリットボートを減らす。 第四に、リーダー選出とは別に実際の書き込み経路にフェンシングトークン検証を置き、選出が一瞬揺らいでもデータ整合性だけは守るよう二重防御を構成する。
また最近では、KafkaのKRaftのように外部調整者(ZooKeeper)依存を除去し自前の内蔵合意で選出を統合する流れが顕著である。 運用構成要素を減らして障害点と運用の複雑度を下げようとするものであり、これは分散システムが「選出を外部に委任」する段階から「選出をコアに内在化」する段階へ成熟していることを示す。 クラウドネイティブ環境ではノードが頻繁に交代するので、リーダー選出はメンバーシップ変更(reconfiguration)中でも安全でなければならず、Raftのジョイント合意(joint consensus)のようにメンバーシップを安全に替える手続きとともに設計せねばならない。
5. 考慮事項および示唆点
技術士の観点では、リーダー選出を設計・導入する際に次を総合的に考慮せねばならない。
- 安全性優先の原則と少数派の停止: 可用性よりデータ整合性が重要なシステムでは、「過半数を得られなければ書き込みを止める」保守的設計が原則である。過半数確保のためノード数は3・5・7のように奇数で構成し、二つのデータセンタ分断時に同点を避けるよう第三の可用性ゾーンに投票ノード(またはwitness/arbiter)を配置するクォーラム設計を併せる。
- フェンシングと冪等性による多重防御: 選出ロジックだけを信じず、書き込み経路にフェンシングトークン検証と要求の冪等性を併せて置き、遅延した過去のリーダーや重複メッセージがデータを破損できないようにする。選出は「誤りうる」という前提で資源側の防御を設計するのが核心である。
- 障害検知のチューニングと可観測性: ハートビート周期・タイムアウト・プリボートをネットワークのp99遅延とRTOに合わせて調整し、リーダー交代回数・任期番号の増加速度・選出所要時間を指標として収集してchurnを早期に検知する。選出関連のログ・メトリクスがなければ、間欠的障害の原因分析は事実上不可能である。
- ビルド対購入(build vs. buy)戦略: 自前のRaft実装は微妙なバグでデータ損失を招きやすいので、特別な理由がなければetcd・ZooKeeper・Consulのような検証済みの調整サービスやライブラリを再利用するのが妥当である。選出をコアに内蔵するKRaftの流れと、外部に委任するLease方式のトレードオフ(運用の単純さ対結合度)を組織の能力に合わせて選ぶ。
- メンバーシップ変更と展望: オートスケーリングでノードが頻繁に替わる環境では、安全な再構成手続き(ジョイント合意、一度に一ノードの追加/削除)も備えねばならない。今後の地理的に分散したマルチリージョンシステムでは、リーダーの位置が遅延・規制(データ主権)に影響するので、リーダー選好・地域固定と選出を連携した設計が重要になる。
参考資料
- Diego Ongaro, John Ousterhout, "In Search of an Understandable Consensus Algorithm (Raft)" — https://raft.github.io/raft.pdf
- Wikipedia, "Raft (algorithm)" — https://en.wikipedia.org/wiki/Raft_(algorithm)
- Martin Kleppmann, "How to do distributed locking (fencing tokens)" — https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
- Apache ZooKeeper, "ZooKeeper Recipes — Leader Election" — https://zookeeper.apache.org/doc/current/recipes.html
- Kubernetes Documentation, "Leases" — https://kubernetes.io/docs/concepts/architecture/leases/
- etcd Documentation — https://etcd.io/docs/latest/
一言まとめ: リーダー選出は対等なノードの中から書き込み・調整権限を持つ単一のリーダーを自動で選び障害時に引き継ぐメカニズムであり、安全性の核心は過半数合意(Raft)やリース型(ZooKeeper・K8s Lease)の選出に任期番号とフェンシングトークンを組み合わせてスプリットブレインを防ぐことである。