プロンプトとスコープ
ユーザーごとのトークンバケットレートリミッターを実装します。各バケットは最大 capacity、1秒あたり refillRate の補充レート、および現在のトークン残高を持ちます。リクエストにはユーザーID、タイムスタンプ、およびコストが含まれます。補充後の残高がコストをカバーしている場合はそれを消費してリクエストを許可し、そうでない場合は拒否します。API、計算量、時間精度、並行処理、およびテストについて説明してください。
これはバックエンド、プラットフォーム、インフラストラクチャのコーディング面接に適しています。AWS では、トークンバケットを「設定されたレートで補充され、リクエストごとに1トークンが消費される、リクエストを表すトークン」と説明しており、制限を引き上げる前にテストすることを推奨しています。
面接官が評価するポイント
- バケットごとにタイマーを起動するのではなく、遅延補充（lazy refill）を導出できるか。
- クロックの後退によってトークンが不正生成されないよう、単調増加時間（monotonic time）を使用しているか。
- トークンに上限が設定され、拒否されたリクエストが残高を変更しないようになっているか。
- 単一プロセスのメモリと分散共有状態を区別しているか。
- 並行処理、数値精度、長いアイドル期間、および無効なパラメータを網羅しているか。
最初に確認すべき明確化の質問
以下を確認します：
costは常に正の整数ですか、それとも小数もあり得ますか？- 時間は決定論的テストのために注入（DI）されますか、それともリミッター自体が読み取りますか？
- 単一プロセスの実装で十分ですか、それとも複数インスタンス間でクォータを共有する必要がありますか？
- 拒否時に残りのトークン数や推定再試行時間を含める必要がありますか？
指定がない場合は、単一プロセス、非負の整数コスト、ナノ秒精度の単調増加クロック、およびバケットキャパシティまでのバースト許容を前提とします。
30秒の回答フレームワーク
ユーザーごとに tokens と lastRefillAt を保持します。各リクエスト時に、単調増加の経過時間を用いて min(capacity, tokens + elapsed * refillRate) で遅延補充を行います。補充後の残高が cost を満たす場合にのみ許可し、そうでない場合は状態を維持して拒否します。単一プロセスでは、ユーザーごとのロックまたはアトミックなクリティカルセクションにより、読み取り、補充、判定、書き込みを不可分（indivisible）にします。分散環境では、アトミックな共有ストアスクリプトまたはトランザクション内で同じ遷移を実行します。制御可能なクロックモデルテストにより、パラメータ、クロックの動作、境界値、および並行呼び出しを検証します。
ステップバイステップの詳細解説
1. 状態と不変条件
ユーザーごとに tokens、lastRefillAt、およびオプションでバージョンを保持します。不変条件は 0 <= tokens <= capacity であり、lastRefillAt は決して後退しません。作成時に正のキャパシティと補充レートを検証します。コストは正であり、キャパシティ以下である必要があります。そうでない場合は状態を変更せずにパラメータエラーを返します。
2. 遅延補充（Lazy refill）
現在時刻を now、elapsed = now - lastRefillAt とします。elapsed * refillRate を加算し、min(capacity, tokens + refill) で残高をクランプ（上限制限）します。バケットが満杯の場合でも、その期間が重複してカウントされないよう lastRefillAt を now に進めます。有理数演算を伴う整数のナノ秒を使用することで浮動小数点数のドリフトを軽減します。浮動小数点数を使用する場合は、丸めを定義し、長時間の実行をテストします。
3. 許可と拒否
補充後の残高が少なくとも cost ある場合は、コストを減算して許可します。そうでない場合は何も減算せず、拒否を返し、オプションで retryAfter を返します。遅延時間を (cost - tokens) / refillRate の切り上げとして推定し、補充レートがゼロの場合やコストがキャパシティを超えている場合を処理します。拒否が成功のように見えたり、カーソルが後退したりしてはなりません。
4. 並行処理とストレージ
単一プロセスのコードでは、読み取り、補充、判定、書き込みを1つのクリティカルセクション内に維持する必要があります。ユーザーごとにシャーディングされたロックを使用することで、単一のグローバルロックを回避できます。複数インスタンスでクォータを共有する場合、アプリケーションロックでは不十分です。状態遷移全体に Redis Lua、データベースの行ロック、または別のアトミックトランザクションを使用します。ネットワークの再試行時にリクエストIDを引き継ぐことで、レスポンスの消失によってビジネス上のトークンが誤って二重消費されるのを防ぎます。
5. 有効期限とカーディナリティ
lastRefillAt とリース（lease）ポリシーを使用して非アクティブなユーザー状態を期限切れにしつつ、新しいリクエストが正しく初期化されるようにします。状態の上限、シャーディング、およびエビクションポリシーによって高カーディナリティのユーザーから保護します。エビクションされたバケットを満杯のキャパシティで再作成するとバーストが発生する可能性があるため、本番環境のポリシーでそれが許容されるかどうかを明記する必要があります。攻撃者が制御可能なユーザーIDによって無制限にマップが増大しないようにしてください。
6. テストとオブザーバビリティ
初期状態で満杯のバケット、繰り返しの拒否、正確な補充、キャパシティと等しいコスト、時間の経過なし、クロックの後退、長いアイドル期間、競合、および重複呼び出しをテストします。注入されたクロックを使用して、残高が境界内に収まること、および成功したコストが初期キャパシティ＋理論上の補充量を超えないことをアサートします。許可・拒否レート、トークン分布、状態数、ロック待機時間、アトミックスクリプトのエラー、およびメモリ使用量を監視します。
高品質な模範解答
私なら allow(userId, now, cost) を公開します。ユーザー状態には tokens と lastRefillAt のみを含めます。単一のクリティカルセクション内で、経過時間を計算し、補充し、キャパシティにクランプして判定します。成功した場合はコストを減算してカーソルを now に進めます。拒否された場合は補充後の残高を維持しつつ何も消費しません。すべての時間計算に単調増加クロックを使用するため、状態が後退することはありません。
単一プロセスの場合は、ユーザーごとにシャーディングされたロックを使用します。複数インスタンスの場合は、個別のネットワーク読み書きを行うのではなく、同じ遷移を Redis Lua やアトミックなデータベーストランザクションに配置します。リクエストIDは再試行の冪等性を担保しますが、ビジネスオペレーション自体を厳密に1回（exactly-once）にするわけではありません。有効期限と高カーディナリティ制御により、メモリの乱用を防ぎます。
テストでは、制御可能なクロックを使用して、経過時間ゼロ、正確な補充、フルコストのリクエスト、長いアイドル期間、クロックの後退、および並行性を検証します。プロパティテストにより、すべての残高がゼロからキャパシティの間に収まること、および累積の許可コストが初期キャパシティ＋補充量を決して超えないことをアサートします。本番環境では、拒否率、トークン分布、状態の増加、ロック待機、およびストレージスクリプトのエラーを監視します。AWS のガイダンスでも、制限を引き上げる前に提案された制限をテストすることが求められています。
よくある間違い
- バケットごとにタイマーを起動し、ユーザー数に応じてスケジューリングコストが増大してしまう。
- クロック時間（ウォールクロック）を使用してしまい、NTP による時刻後退で余分なトークンが生成される。
- キャパシティのクランプを忘れ、無制限の蓄積を許してしまう。
- 拒否されたリクエストに対してコストを請求し、ユーザーのクォータを密かに消費してしまう。
- プロセス内ロックをインスタンス間のアトミック性として扱ってしまう。
cost > capacityを受け入れてしまい、無限に待機したり、不正な再試行時間を生成したりする。- 丸め規則や長期的なドリフトを定義せずに浮動小数点数を使用する。
- 順次呼び出しのみをテストし、並行した Read-Modify-Write の競合を見逃す。
フォローアップの質問と回答
なぜ固定ウィンドウカウンターではないのですか？
固定ウィンドウはシンプルですが、境界部分で短いダブルバーストを許してしまう可能性があります。トークンバケットは、キャパシティによって許容バーストを、補充によって持続レートを表現します。バーストが一切許容されない場合は、スライディングウィンドウやリーキーバケットと比較検討します。
Retry-After はどのように返しますか？
不足している残高を補充レートで除算し、切り上げます。補充レートがゼロの場合やコストがキャパシティを超えている場合は、無限大のタイムスタンプではなく、設定エラーまたは再試行不可の結果を返します。
Redis が利用できない場合はどうしますか？
エンドポイントのリスクに応じて、フェイルクローズ、制限付きローカルバジェット、または明示的な縮退動作を選択し、その理由を記録します。バジェットなしで全インスタンスがフェイルオープンになったり、障害を通常の拒否として隠蔽したりしないようにします。
キャパシティと補充レートはどのように変更しますか？
変更時刻までの旧パラメータで補充を行い、その後明示的なポリシーに基づいて残高をクランプまたは変換し、設定バージョンを記録します。キャパシティを引き下げる際は、新しい制限を超えている既存の残高をアトミックに処理する必要があります。
オーパーセリング（過剰許可）がないことをどのように証明しますか？
ランダム化された時間に対して状態マシンのプロパティテストを実行し、すべてのインターバルで許可されたコストが初期トークン＋理論上の補充量によって制限されていることをアサートします。アトミックなクリティカルセクションを検証するために、並行ストレステストを追加します。