問題とスコープ
単一リージョン内の3つのアベイラビリティゾーンに展開される分散ロックサービスを設計します。100,000個のロック可能リソースを 管理し、通常20,000個のアクティブなロックを保持し、ピーク時には毎秒2,000回の取得を処理します。デフォルトのリース期間は 30秒で、クライアントは10秒ごとに更新し、競合のない取得におけるp99目標は200ミリ秒です。保護対象のストレージまたはサービスは、 フェンシングトークンをアトミックに比較し、古い保持者からのリクエストを拒否できます。
規模、リース期間、レイテンシは面接の前提条件であり、etcd、ZooKeeperなどの特定製品の性能を主張するものではありません。 スコープには排他ロック、待機、更新、解放、フェイルオーバー、オブザーバビリティが含まれます。きめ細かなデータベース行ロック、 完全なトランザクションコーディネータ、コンセンサスアルゴリズムのスクラッチ実装、アクティブ・アクティブのクロスリージョンロックは プライマリ設計の対象外とします。
これはシニアバックエンド、インフラ、システムデザインの代表的な設問です。Amazonの現在のSDE II面接ガイドラインにはシステム デザインが明示的に含まれており、実用性、正確性、効率性、信頼性、最適化、スケーラビリティが評価されます。中心となる障害モードは これらすべてに関わります。すなわち、クライアント障害後にロックを安全に回収し、後から再開した古いクライアントが新しい保持者の データを破壊しないようにしなければなりません。
面接官が評価しているポイント
第1に、候補者が排他制御の安全性と障害時のクリーンアップを明確に区別できるかです。リースは、現在の保持者が消失した後に別の 保持者がいつ引き継げるかを決定します。しかし、長時間停止していたクライアントが再開して書き込みを行うのを防ぐことはできません。 厳密な設計には、フェンシングトークンと保護対象リソース側での検証も必要です。
第2に、整合性境界が明示的であるかです。取得、更新、解放は、1つの強整合性なステートマシンを通過しなければなりません。 少数派パーティションがロックを発行し続けることはできません。3つのアベイラビリティゾーンが独立して決定を下すと、ネットワーク 分断によって同一リソースに2つの保持者が生まれる可能性があります。
第3に、キャパシティプランニングに更新トラフィックが含まれているかです。20,000個のアクティブロックが10秒ごとに更新されると、 更新だけで毎秒約2,000オペレーションが発生します。ピーク時に毎秒2,000件の取得とほぼ同数の解放がある場合、ステートマシンは 取得レートだけでなく、毎秒約6,000件のコミットを処理する必要があります。
第4に、障害セマンティクスがリクエストレベルまで考慮されているかです。回答には、コミットされたが応答が失われた取得、リース期間を 超えて停止したクライアント、新しい保持者のロックを解放してしまう古いクライアント、クォーラムの喪失、リーダー交代時における トークンの単調増加性が含まれる必要があります。
最後に、候補者がこのサービスを使用すべきでないケースを理解しているかです。Google Chubbyは粗粒度の調整を目的としていました。 データベースの一意性制約、条件付き更新、単一コンシューマキュー、またはビジネス冪等性キーですでに解決できる場合、リモートロックは 同期的な障害点を増やすだけになります。
回答前の明確化のための質問
- 排他ロックが必要ですか、それともリーダー・ライターロックですか？ この設計は排他ロックから始めます。リーダー・ライター
ロックは状態、アップグレード、スタベーションのセマンティクスを追加するため、安易に約束すべきではありません。
- 保護対象のリソースはフェンシングトークンを検証できますか？ このプロンプトは、最新トークンのアトミックな比較と保存を
前提としています。これがない場合、リースは競合ウィンドウを狭めるだけで、ゾンビクライアントを厳密に排除することはできません。
- 待機キューの公平性はどの程度必要ですか？ デフォルトは近似FIFOです。絶対的な公平性は、リカバリ時や変動するワークロード下での
柔軟性を低下させます。
- クライアントはどのくらい待機できますか？ 待機状態が無制限に増大しないよう、
waitTimeoutには上限があり、
キャンセル可能です。
- リース期間はワークロードによって変更できますか？ デフォルトは30秒で10秒ごとの更新です。長時間ジョブは制限されたポリシーの
範囲内で期間を要求できますが、リースを無制限に延長することはできません。
- 取得は自動的にリトライ可能ですか？ 同じ安定した
requestIdを持つリトライのみが安全です。そうでない場合、
応答ロストによって結果が不明になります。
- クォーラムがない場合はどうなりますか？ 安全性を優先します。新しい取得と更新を拒否します。各パーティションが勝手にロックを
発行することはできません。
- 保護された操作は依然として冪等である必要がありますか？ はい。フェンシングは古いエポックを拒否しますが、ビジネス上の
リトライや重複送信には依然としてビジネス冪等性キーまたはトランザクションが必要です。
- 低レイテンシのクロスリージョンロックは必要ですか？ プライマリ設計は1つのリージョン内のアベイラビリティゾーン間です。
厳密なクロスリージョンロックはレイテンシが高くなるか、分断時に可用性が失われるため、フォローアップで扱います。
30秒の回答フレームワーク
「ロックの状態を、3つのアベイラビリティゾーンにレプリケーションされた強整合性ステートマシンに保存します。すべての取得、更新、 解放はクォーラムによってコミットされます。取得が成功すると、leaseId、30秒の有効期限、および単調増加する fencingTokenが返されます。クライアントは10秒ごとに更新し、更新が不確実な場合は処理を停止します。保護された すべての操作はトークンを保持し、リソースは受け入れた最大エポックを記録して古いトークンを拒否します。リースによって新しい保持者が 許可され、フェンシングによって再開した古い保持者が拒否されます。重複排除用のrequestIdにより、応答が失われた コミット済み取得を処理します。順序付けられた待機者は先行ノードのみを監視し、サンダリングハードを防ぎます。20,000個のロックは毎秒 約2,000回の更新を生成します。取得と解放を合わせると、永続化とフェイルオーバーの条件下で毎秒約6,000回の状態コミットをテストします。」
ステップごとの詳細解説
コンポーネント図の前に不変条件（インバリアント）から始めます：
- 1つのリソースに対して、整合性ステートマシンは一度に最大1つの有効な
leaseIdのみを記録する。 - 新しく取得されたすべてのロックは、より大きなフェンシングトークンを受け取る。
- 保護対象リソースは、自身が受け入れた最大トークンよりも小さいトークンを拒否する。
- 現在の
leaseIdに一致するリクエストのみが更新または解放できる。 - サービスは、クォーラムに到達することなくロックを作成したり更新成功を返したりしない。
これらの不変条件は、「ロックサービスが誰を保持者と見なしているか」と「リソースが誰の作業をまだ受け入れるか」を分離します。 ステートマシンが前者を決定し、副作用の境界でのフェンシングが後者を決定します。
ステップ1: APIと状態の定義。
Acquire(resource, requestId, leaseTtl, waitTimeout)
-> { leaseId, fencingToken, expiresAt }
Renew(resource, leaseId)
-> { expiresAt }
Release(resource, leaseId)
-> { released }resourceは正規化されたビジネス識別子であり、無制限の未加工ユーザー入力ではありません。leaseIdは この所有権エポックに対する推測不可能な識別子です。fencingTokenはコミットされたコンセンサスログのグローバルに単調増加する リビジョンを使用し、各保護対象リソースは受け入れた最大トークンを保存します。requestIdの重複排除結果は、少なくとも 呼び出し元のリトライウィンドウの間保持されます。解放は冪等ですが、古いleaseIdによる解放が新しい保持者のロックを 削除することはできません。
ロックレコードには、リソース、leaseId、保持者ID、フェンシングトークン、有効期限、およびオプションの待機者参照が 含まれます。アイドル状態のロックレコードは削除できますが、トークンが巻き戻ることはありません。グローバルな単調増加リビジョンにより、 アイドルレコード削除後にリソースのエポックが1にリセットされるのを防ぎます。
ステップ2: 強整合性レプリケーション境界の選択。
ステートマシンには実績のあるコンセンサスストアまたは協調システムを使用し、アプリケーションサービス内にRaftやPaxosを独自実装 しないでください。3つのアベイラビリティゾーンにそれぞれ1つのレプリカを配置します。リーダーは、少なくとも2つのレプリカがコマンドを コミットした後にのみ成功を返します。ロック状態の読み取りは線形化可能（linearizable）であるかリーダーによって処理される必要が あります。遅延しているレプリカがリソースを空き状態と宣言することはできません。
通常の取得パスでは、パラメータと重複排除キーを検証し、ロックが存在しないかステートマシン上でリースが切れていることを確認し、 新しいleaseIdとリビジョンを割り当て、クォーラムにコミットして応答を返します。コミット後、応答が届く前に リーダーが障害を起こした場合、同じrequestIdでのリトライにより、2つ目のリースを作成することなく新しいリーダーから 元の結果を取得します。
3つのレプリカのうち1つしか到達できない場合、サービスは取得と更新を拒否します。これにより可用性は低下しますが、排他制御は維持 されます。少数派側で更新を許可することは一見有用に見えますが、再接続後に両方の分断された保持者を有効として安全に扱う方法は 存在しません。
ステップ3: リースによる障害保持者の回収。
デフォルトのリース期間は30秒で、クライアントは10秒ごとに更新します。これにより、ジッターや一時的な障害のために2回の更新インターバルが 残されます。正式なリース時間はサーバー側の協調ステートマシンによって管理されます。クライアントのローカルクロックはいつ更新を試みるかを 決定できますが、所有権を証明することはできません。更新の連続失敗または不確実な応答の後、クライアントは静止（quiescent）状態に入り、 新しい作業を開始せず、中断可能な実行中の作業を可能な限り速やかに停止します。
リーダー交代時は、残りのリース時間を保守的に処理する必要があります。新しいリーダーのクロックが進んでいるからといって、時期尚早に ロックを他者に渡してはなりません。本番システムでは検証済みのリース実装を再利用し、最大クロックスキュー、選挙時間、ネットワーク リトライをリースバジェットに含めるべきです。リースを数百ミリ秒に短縮するとクリーンアップ速度は向上しますが、通常のジッターが頻繁な ロック喪失につながります。
ステップ4: フェンシングトークンによるゾンビクライアントの阻止。
クライアントAがトークン41を取得した後に長時間のガベージコレクションで一時停止したとします。30秒のリースが期限切れになり、 クライアントBがトークン42を取得して処理を開始します。Aはロックを失ったことに気づかずに再開し、遅延した書き込みを送信します。 ストレージが「Aがかつてロックを取得した」ことしか知らない場合、古い書き込みがBの新しい結果を上書きしてしまう可能性があります。
そのため、保護されたすべてのリクエストは自身のトークンを保持します。ストレージは、各リソースについて確認された最大エポックを アトミックに記憶します。トークン42を受け入れた後は、トークン41を持つすべてのリクエストを拒否します。同一トークンでの複数操作は 正当な場合もあります。それらの順序付け、冪等性、バージョン競合はビジネスプロトコルに属します。比較処理では、同一トークンを一概に 拒否するのではなく、最新エポックより小さいトークンを拒否します。
etcdのドキュメントでも同じ境界が明示されています。リース単体では外部リソースに対する排他制御を保証できません。そのリソースが バージョンを検証する必要があります。ターゲットがトークンを保存または比較できない場合、設計として厳密な安全性を約束することは できません。代替案には、データベースの条件付き更新、一意性制約、ネイティブなトランザクションロック、単一ライターキュー、または トークンを強制できる書き込みプロキシなどがあります。
ステップ5: 待機、公平性、サンダリングハードの処理。
競合の少ないリソースの場合、失敗した呼び出し元はエクスポネンシャルバックオフとジッターを伴ってリトライできます。待機が必要な高競合 リソースの場合は、増加するシーケンス番号を割り当て、各待機者には直前の先行ノードのみを監視（watch）させます。先行ノードが解放 または期限切れになると、全クライアントが一斉に競合するのではなく、次の待機者のみが起床します。ZooKeeperのロックレシピが エフェメラルシーケンシャルノードと先行ノード監視を使用するのはこのためです。
このキューは絶対的な公平性ではなく、近似FIFOを提供します。キャンセル、タイムアウト、セッション期限切れにより待機ノードは削除 されます。ノード作成への応答が失われた場合、requestIdは別のノードを追加するのではなく元のノードを検索します。 リソースごとおよびテナントごとの待機者制限により、単一のホットロックによるメモリ枯渇を防ぎます。
ステップ6: キャパシティとパーティショニングの見積もり。
10秒ごとに更新される20,000個のアクティブロックは、毎秒約2,000件の更新を生成します。ピーク時に毎秒2,000件の取得があり、解放が取得と ほぼ同数であると仮定すると、コンセンサスステートマシンは毎秒約2,000 + 2,000 + 2,000 = 6,000件の書き込みコミットを処理します。 エンキュー、キャンセル、期限切れ、重複排除レコードによって書き込み増幅（write amplification）が発生します。キャパシティテスト では、ピークトラフィック、1つのレプリカの喪失、およびログコンパクションを組み合わせる必要があります。
100,000個のリソースがそれぞれ約500バイトの論理状態を保持する場合、論理的な合計は約50 MBです。レプリカ、ログ、インデックス、 待機者、ストレージエンジンのオーバーヘッドにより、実際のフットプリントは大幅に増加します。静的なレコードサイズよりも、同期永続化、 ホットリソース、更新ボリュームの方がボトルネックになる可能性が高いです。
提示された規模に対しては、1つのコンセンサスグループから開始します。1つのグループが目標を達成できないことが測定によって示された 場合にのみ、リソースのハッシュによってパーティショニングします。シャーディングは総スループットを向上させますが、極端にホットな 単一リソースを分割することはできず、リソース間でのアトミックロックを複雑にします。この設計はマルチリソースのトランザクションロックを 約束しません。呼び出し元が複数のリソースをロックする必要がある場合は、固定順序と全体タイムアウトを使用するか、ドメインを1つの 上位リソースとして再モデル化します。
ステップ7: 障害および運用ループの完結。
- リーダー障害：新しいリーダーがコミット済み状態を回復し、
requestIdにより応答不明リクエストを安全に解決。 - ネットワーク分断：クォーラムのみが処理を提供し、少数派は拒否。フェンシングにより古い保持者の書き込みを最終的に拒否。
- クライアント停止：期限切れ後に新しいロックを発行可能。再開したクライアントはリソース側のトークン検証で失敗。
- ホットロック：待機キュー長、取得レイテンシ、保持時間を計測。キューに上限を設け、キューイングやジョブのパーティショニングを検討。
- 更新ストーム：クライアントのスケジュールにジッターを持たせ、全ロックを一斉に更新するのではなく期限切れに近いリースを優先。
- トークン検証のないリソース：ベストエフォートの排他制御へ明示的にダウングレードするか、金銭や在庫の厳密な書き込みを禁止。
コアメトリクスには、取得・更新・解放のp50/p95/p99、成功・タイムアウト・競合・不明な結果、アクティブロック数、待機者数、期限切れ数、 更新失敗、リーダー選挙時間、コンセンサスコミットレイテンシ、フェンシング拒否数、ホットリソースが含まれます。監査ログには、機密 ペイロードを除いたリソース、leaseId、トークン、呼び出し元、結果が記録されます。
検証は単体テストにとどまりません。ステートマシンモデルテストで単一の所有権と単調増加トークンをチェックします。フォールト インジェクションでは、コミット後の応答ロスト、30秒を超えるクライアント停止、遅延した古い書き込み、1レプリカの隔離、過半数の喪失、 リーダー交代、待機者のキャンセルをカバーします。エンドツーエンドの最も重要なアサーションは、「リソースがBのトークン42を受け入れた 後は、Aのトークン41がそのリソースを二度と変更できないこと」です。
高品質な回答例
「安全性の目標から始めます。1つのリソースは強整合性なロック状態において最大1つの有効なリースしか持たず、保護されたリソースは 古い保持者の書き込みを決して受け入れません。サービスは実績のあるコンセンサスストア上で3つのアベイラビリティゾーンにまたがって 稼働します。取得、更新、解放にはクォーラムが必要です。少数派しか存在しない場合、可用性のために排他制御を犠牲にすることなく 処理を拒否します。
APIはleaseId、有効期限、単調増加するfencingTokenを返します。デフォルトのリース期間は30秒で、 クライアントは10秒ごとに更新します。ローカルクロックは更新スケジューリングのみに使用され、更新が不確実な場合、クライアントは 処理を停止します。リースによって障害後の引き継ぎが可能になりますが、リソース側が実際の安全境界となります。保護されたすべての リクエストはトークンを保持し、リソースは受け入れた最大エポックを記録して古いトークンを拒否します。トークン41のクライアントが トークン42への引き継ぎ後に再開しても、その古い書き込みが適用されることはありません。
すべての取得にはrequestIdが付与されます。サービスがコミットしたものの応答が失われた場合、呼び出し元は同じIDで リトライし、別のリースを作成するのではなく元のリースを受け取ります。更新と解放は現在のleaseIdと一致する必要が あるため、古いクライアントが新しい保持者のロックを解放することはできません。競合するロックに対しては、順序付けられた待機者が 直前の先行ノードのみを監視し、サンダリングハードを起こさずに近似FIFOを提供します。
キャパシティに関しては、10秒ごとに更新される20,000個のロックによってすでに毎秒約2,000回の書き込みが発生します。これに2,000回の 取得と同等の解放レートを加えると、毎秒約6,000回のコンセンサスコミットになります。ベンダーのベンチマークを引用するのではなく、 1つのレプリカがダウンしログコンパクションが実行されている状態で200ミリ秒のp99を検証します。最初は1つのコンセンサスグループから 開始し、負荷テストで必要性が証明された場合にのみリソース単位でシャーディングします。
最後に、モデルテストとフォールトインジェクションにより、コミット後の応答ロスト、クライアント停止、パケット遅延、ネットワーク分断、 選挙、待機者キャンセルをカバーします。取得および更新レイテンシ、競合、期限切れ、キュー長、選挙、フェンシング拒否を監視します。 保護されたシステムがトークンをアトミックに比較できない場合は、厳密な排他制御は利用できないことを明示し、データベースの条件付き 更新、一意性制約、または単一ライターキューを推奨します。」
よくある間違い
- TTL付きのキーのみを保存する → 停止していた古いクライアントが再開して書き込む可能性がある → 取得ごとに単調増加トークンを発行し、リソース側で検証する。
- 各アベイラビリティゾーンが独立してロックを発行できるようにする → 分断により複数の保持者が作成される → すべての状態変更をクォーラムベースの1つのステートマシン経由にする。
- クライアントのクロックをリースの真実として扱う → クロックスキューやプロセス停止によって誤った所有権が発生する → リースをサーバー側で管理し、不確実なクライアントは処理を停止させる。
- 新しいリクエストIDで取得をリトライする → 最初のリクエストがすでにコミットされている可能性がある → 安定した
requestIdを使用して最初の結果を取得する。 - リソース名のみでの解放を許可する → 古いリクエストが新しい保持者のロックを削除する可能性がある → 更新および解放には現在の
leaseIdを要求する。 - 毎秒2,000回の取得のみを想定してサイジングする → 2,000回の更新と同数の解放が見落とされる → ベースラインとして毎秒約6,000回の状態コミットをテストする。
- すべての待機者にロックのルートを監視させる → 解放のたびにキュー全体が起床する → 各待機者には直前の先行ノードのみを監視させる。
- 最初から多数のコンセンサスグループにシャーディングする → 運用やリソース間のセマンティクスが早期に複雑化する → まず1つのグループで測定し、根拠に基づいてシャーディングする。
- すべての行に分散ロックを使用する → 協調処理が高頻度なトランザクションパスとなりボトルネックになる → きめ細かな並行性にはデータベースのアトミック制約を優先する。
- ターゲットがトークンを検証できないのに厳密な安全性を主張する → リースでは遅延した古い書き込みを阻止できない → 保証レベルを引き下げるか、書き込み境界を変更する。
フォローアップの質問と回答
フォローアップ1: ロックにリースがあるのに、なぜフェンシングトークンが必要なのですか？
リースは、30秒後にロックサービスがBにロックを付与することを許可するだけです。Aがすでに外部システムに送信したものの、ネットワークや プロセスキューに残っている操作を取り消すことはできません。また、Aは長時間の停止後にリースが切れたことを知らずに再開する可能性も あります。リソースがトークン42を受け入れた後は、トークン41を拒否することで、副作用が発生するまさにその場所で古いエポックの作業を 阻止できます。再利用可能なルールは次のとおりです。「リースは新しい保持者をいつ選出できるかを決定し、フェンシングは古い保持者の作業が まだ受け入れられるかどうかを決定する。」
フォローアップ2: 保護対象のデータベースがフェンシングトークンを保存できない場合はどうしますか？
まず、UPDATE ... WHERE version = expected、一意性制約、トランザクションロック、データベースのアドバイザリロックなど、同等のアトミックな バージョン条件を探します。また、トークンを検証するプロキシまたは単一コンシューマキューを介して書き込みを行うこともできます。いずれも 不可能な場合、保証はベストエフォートの排他制御にとどまり、プロセスの停止や遅延メッセージによって正確性が損なわれる可能性があります。 金銭や在庫のワークフローでは、曖昧な保証を受け入れるべきではありません。
フォローアップ3: リージョンをまたぐグローバルロックはどのように設計しますか？
直接的な設計としては、各リソースにホームリージョンを割り当て、すべてのリージョンに1つのクロスリージョンクォーラムを使用させます。 これにより長距離の書き込みレイテンシが増加し、少数派リージョンは分断時に取得できなくなります。排他制御の競合は後から取り消すことが できないため、独立したリージョンロックを非同期にマージすることはできません。リージョンの可用性をより重視する場合は、アクティブ・ アクティブのグローバルロックを考案するのではなく、特定のリソースが1つのリージョンでのみ書き込み可能になるようリソースの所有権を パーティショニングします。
フォローアップ4: 30秒のリース期間と10秒の更新インターバルはどのように決めますか？
これらはプロンプトの入力値です。実際の値は、最長の通常プロセス停止時間、ネットワークのp99、選挙時間、クロック誤差バジェット、および 許容される障害復旧時間によって決まります。リースが短すぎると通常のジッターがロック喪失として扱われ、長すぎると障害が発生した保持者 からの復旧が遅れます。10秒の更新間隔は、30秒のリース期間内に2回の追加の機会を提供します。20,000のクライアントが同期して一斉に更新スパイクを 発生させないよう、ランダムなジッターを追加します。
フォローアップ5: 複数のロックを一度に取得する処理はどのようにサポートしますか？
最もシンプルな境界は、このサービスがリソース間のアトミックロックを提供しないことです。呼び出し元は、短い全体タイムアウトを設定した上で 正規化されたリソース名を固定の順序で取得し、失敗時には逆順で解放します。これによりデッドロックは減少しますが、トランザクションの アトミック性はありません。ドメインが真にAll-or-Nothingの取得を必要とする場合は、そのセットを1つの上位リソースとしてモデル化するか、 すべてのキーを1つのコンセンサストランザクション内に保持し、スループットと複雑性のコストを受け入れます。
フォローアップ6: 実装が2つの有効な保持者を決して作成しないことをどのように証明しますか？
ステートマシンモデルを使用して取得、更新、解放、期限切れ、リトライのシーケンスを生成し、各ログ位置に最大1つの有効な leaseIdしか存在しないこと、およびトークンが増加することを確認します。次にフォールトを注入します。コミット後の 応答ロスト、リース期間を超えたAの停止、Bによる取得と書き込み、そして古い書き込みを伴うAの再開をテストし、リソースが古いトークンを 拒否しなければならないことを確認します。さらに、少数派と過半数の隔離、繰り返しのリーダー交代、待機者のキャンセルを実行し、すべての 並行実行履歴を不変条件と照合して検証します。