システムデザイン面接：安全なリーダー選出サービスをどのように設計するか？

プロンプトとコンテキスト

複数のステートレスなワーカーが存在し、スケジュールされた決済ジョブを同時に実行できるインスタンスは厳密に1つだけでなければなりません。ワーカーはクラッシュ、再起動、一時停止、またはネットワーク分断が発生する可能性があり、システムは2つのワーカーが長時間にわたって書き込みを行える状態にしてはなりません。コーディネーター、リース、更新、フェンシング、フェイルオーバー、および運用の境界を備えたリーダー選出を設計してください。本質は単なるミューテックスではなく、安全な単一ライターの調整です。

面接官がテストしていること

安全性（Safety）と生存性（Liveness）の定義

安全性とは、ある任期（term）に対してリソースによって受け入れられるリーダーが最大1つであることを意味します。生存性とは、古いリースの期限切れが確認された後、健全な候補者が最終的に引き継ぐことを意味します。可用性を維持するためだけに、少数派パーティションが新しいリーダーを宣言することはできません。

合意形成セマンティクスを持つコーディネーターの選定

リーダーレコードには、etcdのような線形化可能性（linearizability）を持つcompare-and-set、リース、およびウォッチセマンティクスが必要です。RedisのTTLやローカルクロックだけでは、古いリーダーが書き込み不能であることを証明できません。

古い書き込み（Stale writes）の防止

リースの期限が切れた後、古いプロセスが回復して処理を継続する可能性があります。ダウンストリームへのすべての書き込みには単調増加するフェンシングトークンを付与する必要があり、リソースはスプリットブレインによる被害を防ぐために古いトークンを拒絶しなければなりません。

最初に確認すべき質問

• ジョブは2回実行されてもよいですか、それともダウンストリームは厳密に1回直列化された実行のみを受け入れる必要がありますか？
• 選出はグローバル、テナントごと、シャードごと、またはジョブごとのいずれですか？
• どの程度のフェイルオーバー時間と一時停止ウィンドウが許容されますか？
• コーディネーターの障害ドメインはいくつあり、どのようなクォーラム/バックアップが利用可能ですか？
• ダウンストリームのリソースはフェンシングトークンを検証し、冪等に回復できますか？
• ウォッチイベント、監査履歴、アラート、および手動切り替えは必要ですか？

30秒での回答

「まず選出スコープと許容障害バジェットを定義し、次に合意形成に裏打ちされた線形化可能なコーディネーターにリース付きのリーダーレコードを保存します。候補者はトランザクショナルな作成・比較（create-or-compare）更新で競合します。勝者はより高いフェンシング任期（term）を取得し、TTL内に更新します。更新に失敗すると、新しい処理と書き込みを停止します。すべてのダウンストリーム書き込みは任期を検証するため、回復した古いリーダーは書き込みができません。ウォッチは新しいCAS試行を加速するだけです。任期、更新レイテンシ、フェイルオーバー時間、フェンシング拒絶数、重複、クォーラムの健全性を監視します。」

ステップバイステップの詳細な回答

任期レコードの定義

election_name、leader_id、lease_id、term、候補者のメタデータ、およびタイムスタンプを保存します。任期またはフェンシングトークンは単調増加しなければならず、クライアントのクロックから生成されるのではなく、コーディネーターによってアトミックに割り当てられる必要があります。

コーディネーターと書き込み条件の選定

候補者はエフェメラルなリース付きレコードを作成します。線形化可能なトランザクションは、キーが存在しない場合にのみ書き込みを行うことができます。リーダーが存在する場合、候補者はキーをウォッチして再試行します。etcdの選出APIを使用すると、参加者は1つの選出名で競合し、一度に1つの成功したリーダーのみが存在するようになります。

更新とフェイルクローズ（Fail Closed）

リーダーは独立したキープアライプループを通じて更新を行います。更新のタイムアウト、接続の喪失、プロセスの一時停止、またはローカルクロックの異常が発生した場合、suspect に移行し、新しい処理の受け入れとダウンストリームへの書き込みを停止します。コーディネーターから切断されている間、安全であると見なして処理を継続してはなりません。

フェイルオーバーの処理

候補者は自身のローカルTTLから古いリーダーが停止したと判断することはできません。コーディネーターによって確認されたリースの期限切れまたは削除を観察した上で、CASで競合する必要があります。フェイルオーバー時間は、TTL、検出、およびスケジューリング遅延の合計であるため、ジッターのマージンを含めた上限を設定します。

フェンシングトークンの追加

新しいリーダーはより高い任期を取得し、データベースの更新、メッセージ、または外部APIリクエストにそれを添付します。リソースは受け入れた最も高いトークンを保存し、それより低いトークンを拒絶します。これにより、古いプロセスが停止していない場合でも危険な書き込みがブロックされます。

ネットワーク分断とスプリットブレインの処理

少数派パーティションは新しい任期を発行できません。コーディネーターのクォーラムに到達できない候補者は、停止するか読み取り専用のままでいる必要があります。再接続後、古いリーダーはキャッシュされた状態を信頼するのではなく、現在の任期を再読み込みして再度競合しなければなりません。

疑似コード

~~~text campaign(): lease = coordinator.grant(ttl) result = coordinator.txn(key absent -> put(candidate, lease, next_term)) if result.succeeded: token = result.term keepalive(lease) runwithfencing(token) else: watch(key)

onkeepalivefailureorexpiry: stopnewwork() stopdownstreamwrites() ~~~

複雑性、復旧、および可観測性

各選出および更新にはコーディネーターとのラウンドトリップが伴います。候補者が増えるとウォッチと再試行の負荷が増加するため、ジッター付きの指数バックオフを使用します。任期の遷移を再構築するために、現在のリーダー、任期、更新RTT、リースの期限切れ、選出時間、フェンシング拒絶数、重複ジョブ、およびクォーラムの健全性を記録します。

模範回答

「私は、線形化可能なトランザクションを備えた合意形成ベースのコーディネーターに、リース付きのリーダーレコードを保存します。候補者は、レコードが存在しない場合にのみ作成することで競合します。勝者は単調増加する任期を受け取り、TTL内にそれを更新します。更新に失敗した場合、直ちに新しいジョブとダウンストリームへの書き込みを停止します。すべてのデータベース書き込み、メッセージ、または外部呼び出しにはフェンシングトークンが付与され、リソースは受け入れ済みの最高値未満のトークンを拒絶するため、一時停止または分断された古いリーダーが書き込みを継続することはできません。少数派は新しい任期を発行できず、ウォッチは選出の遅延を減らすためだけに機能します。手動のキルスイッチを備えつつ、更新RTT、任期、フェイルオーバー時間、フェンシング拒絶数、重複ジョブ、およびクォーラムを監視します。」

よくある間違い

RedisのTTLのみを使用すること

リースの期限切れと、クライアントによる期限切れの認識は同一ではありません。ネットワーク遅延や一時停止により、2つのクライアントが自身に実行権限があると誤認する可能性があります。線形化可能な調整とダウンストリームのフェンシングを併用してください。

リースを書き込み保護として扱うこと

リースは障害の検出に役立ちますが、古いプロセスを即座に停止することはできません。トークンの検証がなければ、古いリーダーが新しいリーダーの結果を上書きしてしまう可能性があります。

ローカル時刻から任期を生成すること

クロックはドリフト、ジャンプ、または一時停止する可能性があります。コーディネーターがアトミックに任期を割り当て、永続化しなければなりません。

分断中に強制的に乗っ取りを行うこと

少数派は古いリーダーの状態を確認できません。強制的な乗っ取りはスプリットブレインを引き起こします。安全な設計では、短時間の可用性低下を受け入れます。

ウォッチイベントで安全性を判断すること

ウォッチは遅延、喪失、または再接続される可能性があります。ウォッチは再読み込みとCASのトリガーとして機能すべきであり、線形化可能な読み取りと書き込みの代替にしてはなりません。

ジョブの冪等性を省略すること

正しい選出を行っても、クラッシュやメッセージの再配信後の重複は防げません。ジョブには冪等性キー、進捗レコード、または再実行可能なトランザクションが必要です。

フォローアップの質問と回答

リーダー選出は分散ロックとどのように異なりますか？

ロックはクリティカルセクションを保護します。選出は任期、更新、ウォッチ、フェンシング、フェイルオーバーを伴う長期的なコーディネーターの役割を維持します。これらはコーディネーターを共有できますが、選出の方が安全性の対象範囲が広くなります。

TTLはどのように選定すべきですか？

通常の更新RTT、GCまたはスケジューラーの一時停止、ネットワークジッター、およびフェイルオーバーSLOをカバーするように設定します。TTLが短いとチャーン（頻繁な交代）が発生し、長いと引き継ぎが遅れます。フォールトインジェクションを用いて調整します。

なぜリソース側でフェンシングトークンをチェックする必要があるのですか？

コーディネーターはすべての古いプロセスを即座に停止できるわけではないためです。リソース側での拒絶により、そのプロセスがまだ生存している間でも危険な書き込みをブロックできます。

etcdクラスターがクォーラムを失うとどうなりますか？

新しい任期やリースの状態をコミットできなくなります。現在のリーダーは更新できなくなった後、書き込みを停止しなければなりません。クォーラムが回復した後、候補者は再度競合します。

リーダーの長時間のプロセス一時停止はどのように処理しますか？

一時停止中に更新が失敗し、新しい候補者が引き継ぐことができます。古いプロセスが再開した際、その古いトークンは拒絶されるため、選出に再参加する必要があります。

スプリットブレインのテストはどのように行いますか？

プロセスの一時停止、ネットワーク分断、クロックジャンプ、コーディネーターの障害を注入します。書き込みに対して任期ごとに1つのトークンのみが受け入れられることを検証し、フェイルオーバー時間と拒絶レコードを検査します。