プロンプトとコンテキスト
あるテナントが、バースト容量6,000、毎分30,000リクエストのグローバル許容量を購入しています。トラフィックは3つのアクティブなリージョンに流入し、リクエストごとにクロスリージョンで判定を行うとレイテンシの目標を達成できません。グローバル調整レイヤーのみを設計してください。各リージョンにはすでに適切なローカルトークンバケットが存在するものとします。
回答では、リージョン間で需要が移動したとき、リージョンが分断されたとき、またはコーディネーターが障害を起こしたときに何が起きるかを定量化する必要があります。HTTP 429やRetry-Afterはクライアントへ拒否を伝達しますが、内部のレート制限アルゴリズムを決定するものではありません。
面接官が評価するポイント
- 低レイテンシ、分断耐性（可用性）、および厳密なグローバル上限をすべて同時に満たすことはできないと理解しているか。
- クォータが各リージョンに単純複製されるのではなく、リースを通じて総量が保存（保存則）されているか。
- 未使用の容量を二重消費（double spending）なしに回収できるか。
- 障害ポリシーと最大オーバーシュートが測定可能になっているか。
確認すべき明確化のための質問
- グローバルの数値は厳密な不正防止の境界ですか、それとも誤差が許容される商業的な目標値ですか？
- ネットワーク分断時、リージョンはリースが空になった時点で停止すべきですか、それとも緊急許容量の範囲内で継続すべきですか？
- トラフィックはどのくらいの速さで移動し、リージョンごとの需要はどの程度不均衡になり得ますか？
- 1つのリクエストは単位コスト（単一コスト）ですか、それともエンドポイントごとに重み付けされたコストを消費しますか？
- オーバーシュートよりも一時的な過小利用（アンダーアロケーション）のほうが望ましいですか？
厳密な上限の場合、分断されたリージョンは期限内のリースのみを使用できます。ベストエフォートの商業的制限であれば、明示的に制限された緊急許容量を認めることができます。
30秒での回答
「強力な順序保証を持つコーディネーターを使用して、毎秒500リクエストのグローバル補充レートと6,000のグローバルバースト容量という2つのリース可能リソースを管理します。コーディネーターは短期間の補充レート枠とバースト枠を各リージョンにリースし、各リージョンは既存のローカルアトミックトークンバケットを通じて消費します。常に、重複するアクティブなリースの合計は最大で毎秒500リクエストおよび6,000バーストトークンとなり、更新時はローカル残高を補充することなくパラメータのみを更新します。トラフィックの移動時には、古い割り当て枠が返却されるか期限切れになってから再割り当てを行います。厳密制限のリージョンは分断時にリース期限切れで停止し、ベストエフォートのリージョンは個別の緊急許容量を使用でき、その合計がドキュメント化されたオーバーシュートの上限となります。」
ステップバイステップの詳細解説
1. クォータを保存則の不変条件として維持する
毎分30,000リクエストを、バースト容量B = 6000を持つ連続的な補充レートR = 500 req/sに変換します。常にsum(active_lease.refill_rate) <= Rかつsum(active_lease.burst_capacity) <= Bです。リースにはテナント、リージョン、エポック、レート枠、バースト枠、有効化時刻、有効期限、および一意のIDが含まれます。初期のリージョン残高の合計は最大でBであり、更新、拡張、または再構成によって残高が無から作成されることはありません。したがって、任意の区間における総承認数は最大でR × duration + Bとなります。フェイルオーバーは永続化されたリース台帳とより高いエポックを使用し、既存のリースは返却が確認されるか期限切れになるまで両方の制限に対してカウントされます。
2. ローカルで消費し、枯渇前に更新する
リージョンのバケットはリースされたレートで補充され、その残高はリースされたバースト枠を上限とします。各リクエストはアトミックに残高をデクリメントします。中断のない更新では、既存の残高を維持しながらレートと容量を延長または変更し、バケットを再度満たすのではなく、容量が減少した場合には残高を切り詰めます。リースの途切れ（ギャップ）が発生した後は、コーディネーターが確認済みの回収トークンを転送しない限り、次のリースは残高ゼロで開始します。リース期間を短くするとリバランスと障害境界は厳密になりますが、更新負荷が増加します。測定されたピーク、コーディネーターの容量、および許容される切断時間から期間を選択します。
3. 二重消費なしでリバランスする
正常なリージョンは残高と需要を報告します。コーディネーターはコールドリージョンの次期リースにおいてレートとバースト枠を削減し、解放された枠をホットリージョンに付与します。古いリースが返却確認されるか期限切れになるまで、重複する新旧のリースは両方とも2つの制限に対してカウントされます。返却確認によってまず古いバケットが無効化されます。ホットリージョンでの容量増加は残高を生成せず、ゼロから開始するか、確認済みの転送トークンのみを受け取ります。返却は冪等（べきとう）です。状態が不確実な場合は、同じ枠を二重に割り当てるよりも一時的な過小利用を選択します。
4. 障害セマンティクスを明示する
厳密な上限を設ける場合、リージョンはリースが有効な間のみ補充を行います。更新できない場合、期限切れによってローカルバケットは無効化され、確認済みの返却によって転送されなかった残高は破棄されます。その代償は一時的な過小利用です。各リージョンが通常のバースト制限外に緊急許容量Eを持つ場合、最大追加許容量は切断中に有効化され得る予算の合計となり、そのモードでは厳密なオーバーシュートゼロを主張することはできません。コーディネーターの障害によって発行済みリースが無効化されることはありません。代替インスタンスは永続台帳を復元し、より高いエポックで古い発行者をフェンシングし、未期限切れの古いリースを引き続きカウントします。
優れた回答例
「既存のリージョナルトークンバケットは同期パス上に維持します。毎分30,000リクエストを毎秒500リクエストの補充レートとして表現し、6,000リクエストのバースト容量を個別に管理するグローバルコーディネーターを追加します。これはエポックでフェンシングされた期限付きのレート枠とバースト枠を発行し、アクティブなリースの合計が常に最大で毎秒500リクエストおよび6,000バーストトークンとなるようにします。
各リージョンはリースされたレートでローカルバケットを補充し、リースされたバースト枠を上限とします。中断のない更新では残高が保持され、追加容量によって残高が生成されることはありません。ホットリージョンは確認済みの返却トークンのみを受け取るか、コールドリージョンのリース期限切れ後にゼロから補充を開始します。厳密制限の下では、分断されたリージョンはリース期限切れ後にバケットを無効化します。ビジネス要件としてリージョンあたり100の追加緊急トークンを認める場合、ドキュメント化される分断オーバーシュートは、アクティブ化ルールが重複し得る緊急予算の合計が最大となります。フェイルオーバーではリース台帳を復元し、新しいエポックを使用します。トラフィックの急変動、重複返却、重複更新、クロックスキュー、およびネットワーク分断に対して、両方の不変条件を検証します。」
よくある間違い
- すべてのリージョンに完全なレートとバースト容量を付与する → グローバル制限がリージョン数倍に膨らむ → レート枠とバースト枠を個別にリースする。
- 返却が確実になる前に返却されたリースを再利用する → 同じトークンが二重に消費される可能性がある → 返却を冪等にするか、期限切れを待つ。
- 誤差境界を示さずに「結果整合性（Eventual Consistency）」と言う → 発生し得るオーバーシュートが不明になる → リースおよび緊急予算の境界を明記する。
- 更新ごとにローカルバケットを再補充する → 更新のたびに新たなバーストが発生する → 残高を維持し、レート、容量、有効性のみを更新する。
- フェンシングなしでフェイルオーバーする → 2つのコーディネーターが有効なクォータを発行する可能性がある → すべてのリースに単調増加エポックを付与する。
フォローアップ質問と回答
リースのサイズはどのように決定しますか？
期間、補充レート枠、バースト枠を個別に選択します。許容される切断時間から期間を設定し、直近の需要からレートを割り当て、グローバルの6,000容量の範囲内でピークからバーストを割り当てます。期間を短くするとリバランスが高速化し障害境界が厳密になりますが、更新負荷が高まります。
トラフィックが突然別のリージョンに移動した場合はどうなりますか？
コーディネーターはコールドリージョンの次期リースでレートとバースト枠を削減し、返却確認または古いリースの期限切れ後に解放された枠を転送します。待機中、システムは未使用容量があるにもかかわらず一時的に拒否する可能性がありますが、これは重複した過剰割り当てを防ぐための代償です。
Retry-Afterはどのように返しますか？
現在のリース下での次のローカル補充、確認済みの新規リースの有効化、または予想されるコーディネーターの復旧のうち、最も早い時刻を使用し、レスポンスでサポートされる精度に丸めます。復旧が不明な場合は時間を確約せず、代わりに上限付きのリトライポリシーを返します。
この設計でオーバーシュートゼロと分断時の完全な可用性を両立できますか？
各パーティションがすでに十分な事前割り当てクォータを保持しており容量が滞留することを許容できる場合、またはリクエストがリージョン間で同期的に調整を行いレイテンシと分断耐性を犠牲にする場合にのみ可能です。回答では製品としての境界を明示的に選択する必要があります。