【実務・中級編】リーダー選出 (Leader Election) – Cloud Spanner

【Cloud Spanner深層】リーダー選出のメカニズム：なぜSpannerは「止まらない」のか

こんにちは。テクニカルリードの私だ。
これまで数々の分散データベースの設計・運用を見てきたが、Cloud Spannerほど「CAP定理のジレンマをエンジニアリングの暴力で殴り倒した」プロダクトは他にない。

多くのエンジニアは、Spannerを「リレーショナルデータベースの皮を被った無限スケールの化け物」程度に捉えている。しかし、その心臓部である「Paxosグループ」と「リーダー選出（Leader Election）」の物理的実態を理解していなければ、真のパフォーマンスを引き出すことはできないし、障害時に「なぜその挙動になるのか」をロジカルに説明することもできない。

今回は、Spannerのコアアーキテクチャの中でも最もエキサイティングな「リーダー選出」に焦点を当て、実務の設計に直結する知見を叩き込む。

—

1. そもそもSpannerの「リーダー」とは何を司るのか？

Cloud Spannerは、データをシャード（Split）し、それぞれを複数の地理的レプリカに配置する。このレプリカの集まりがPaxosグループを形成する。

このPaxosグループ内において、リーダー（Leader）は単なる「お飾り」ではない。書き込み（Write）処理の全権を握る絶対的な司令塔だ。

リーダーの主な責務

1. トランザクションのオーケストレーション: 2段階コミット（2PC）のコーディネーターとして振る舞い、タイムスタンプを割り振る。
2. TrueTimeとの同期: リーダーの持つローカルクロックが、Googleの原子時計とGPSに裏打ちされたTrueTime APIと協調し、分散トランザクションの外部一貫性（External Consistency）を担保する。
3. リード（Read）の最適化: 読み取り専用トランザクションであれば、リーダーを通さずにアップ・トゥ・デートなローカルレプリカから直読み（Stale Readなど）することも可能だが、強整合性読み取りの多くもリーダーが起点となる。

つまり、リーダーがダウンするということは、そのPaxosグループが担当するデータレンジへの書き込みが一時的に停止することを意味する。だからこそ、リーダー選出のアルゴリズムが極限まで最適化されている必要があるのだ。

—

2. リーダー選出の裏側：PaxosとLease（リース）の密な関係

一般的なRaftやPaxosの教科書を読むと、「過半数（Quorum）の合意を取ってリーダーを選ぶ」と書いてある。しかし、Google規模のインフラストラクチャにおいて、何かあるたびに投票を行っていたのではレイテンシの面で使い物にならない。

Spanner（正確にはその基盤であるColossusやSpannerのストレージ層）では、Lease（リース）という概念を組み合わせることで、高速かつ安全なリーダー選出を実現している。

[リーダー (Leader)]
│
│ (定期的なハートビート / Lease更新)
▼
[フォロワー 1] [フォロワー 2]
(投票権あり) (投票権あり)

リーダー選出と維持のメカニズム

リースの概念: リーダーは、他のPaxosレプリカ（フォロワー）から「一定期間（例: 数秒間）、私がリーダーである」というLease（時間的特権）を獲得する。
無投票運用（Leaseholderとしての振る舞い）: リース期間内であれば、リーダーはフォロワーとの毎回の合意形成（投票）をスキップして、高速にPaxosログをコミットできる。これがSpannerの高スループットを支える秘密だ。
フェイルオーバー（障害時）:

1. ネットワーク分断やノード障害により、現リーダーがフォロワーへハートビートを送れなくなる。
2. リースの有効期限（Lease Timeout）が切れる。
3. フォロワーのタイマーが発火し、「新しいリーダーを選ぶための選挙（Election）」がトリガーされる。
4. 新しいリーダーが過半数の承認を得て選出され、リースを更新する。

この切り替え時間は、Googleの内部ネットワーク環境において数秒（場合によっては数百ミリ秒オーダー）で完了するようにチューニングされている。

—

3. 実務で知るべき影響：リージョン構成とリーダー選出の罠

設計レビューをしていると、「マルチリージョン構成にすれば可用性が無限に上がる」と誤解しているジュニアエンジニアによく遭遇する。
ここで、リーダー選出の物理的制約がシステムにどう影響するかを解説しよう。

パターンA: リージョン内（Single-Region）構成

挙動: すべてのレプリカが同一リージョン内の異なるゾーンに配置される。
リーダー選出: ゾーン障害が発生した場合、生き残ったゾーンのレプリカ間で瞬時にリーダーが再選出される。
レイテンシ: 極めて低レイテンシ（数ミリ秒）。

パターンB: マルチリージョン（Multi-Region）構成

挙動: レプリカが異なる地理的リージョン（例: `asia-northeast1` と `asia-northeast2`）にまたがって配置される。
リーダー選出の課題:

物理的な距離があるため、光速の壁（伝播遅延）が存在する。例えば、東京と大阪の間でも往復で十数ミリ秒かかる。
もし、リーダーが東京にいて、東京リージョン全体がブラックアウトした場合、大阪のレプリカが「リーダーが死んだ」と判断し、新しいリーダーに昇格するまでに物理的な遅延とタイムアウトの待ち時間が発生する。

> 💡 チーフアーキテクトからの設計アドバイス
>
> マルチリージョン構成を設計する際は、「クォーラム（定足数）の配置」を意識しろ。
> 3リージョン構成（リーダー候補を3つ配置）にする場合、過半数（2リージョン）の合意が必要になる。片方のリージョンがネットワーク隔離されると、残りの2リージョン間でしかリーダー選出が行えないため、配置計画を誤るとフェイルオーバー時に想定以上のダウンタイムを許容することになる。
> 「どこにリーダーを置き、どこをフォロワー（あるいはワットネス/無投票レプリカ）にするか」のトポロジー設計こそが、Spannerアーキテクスの腕の見せ所だ。

—

4. ホットスポットとリーダー選出チャurn（チャーン）の悪夢

コードレビューをしていて最も冷や汗をかくのが、「シーケンシャルなID（オートインクリメントやタイムスタンプ）をプライマリキーの先頭に置いた設計」だ。

— ❌ 最悪のアンチパターン：リーダーチャーンを引き起こす
CREATE TABLE BadTransactions (
TransactionId INT64 NOT NULL, — 常に増加する値
UserId STRING(64),
Amount INT64,
) PRIMARY KEY(TransactionId);

これをやると何が起きるか？
すべての新しい書き込みが、常に「現在の最大値」を持つ単一のシャード（＝単一のPaxosグループ）に集中する。これを「ホットスポット」と呼ぶ。

ホットスポットがリーダー選出に与える影響

1. 特定のPaxosグループのCPUやネットワーク帯域が飽和する。
2. リーダーノードが過負荷により応答遅延（レスポンス遅延）を起こす。
3. フォロワーが「リーダーからのハートビートが途絶えた」と誤認する（あるいはリーダー自身が処理しきれなくなる）。
4. 不要なリーダー選出（リーダーチャーン）が頻発する。
5. リーダー選出のゴタゴタでさらに書き込みが止まり、システム全体がカスケード障害に陥る。

✅ 正しいアプローチ：UUIDv4やハッシュ化プレフィックス

書き込みを分散させるためには、キーの先頭をランダム化し、複数のPaxosグループへ負荷を綺麗にスプレッドさせなければならない。

— ⭕ 推奨される設計：分散されたプライマリキー
CREATE TABLE GoodTransactions (
— ランダムなUUIDや、ハッシュプレフィックスを付与したID
TransactionId STRING(36) NOT NULL,
UserId STRING(64),
Amount INT64,
CreatedAt TIMESTAMP,
) PRIMARY KEY(TransactionId);

これにより、書き込み負荷が複数のPaxosグループに綺麗に分散され、特定のリーダーに負荷が集中するのを防ぐことができる。結果として、意図しないリーダー選出のトリガーを根絶やしにできる。

—

5. まとめ：Spannerを使いこなすということ

Cloud Spannerのリーダー選出は、Googleのインフラストラクチャの深部で完全に自動化されており、普段私たちがその存在を意識する必要はない。

しかし、「ブラックボックスだから知らなくていい」というのはエンジニアの怠慢だ。

レプリカとLeaseの仕組みを理解していれば、マルチリージョンのレイテンシや障害時の挙動が手に取るようにわかる。
ホットスポットとリーダーチャーンの因果関係を知っていれば、アンチパターンなスキーマ設計をコードレビューで一刀両断できる。

分散データベースの本質は「隠蔽された複雑性をいかに理解し、システムをそれに適合させるか」だ。
今日の知見を次の設計レビューに活かしてほしい。健闘を祈る。