お題・ディスカッション一覧

スライディングウィンドウとバースト許容を備えたレートリミッタ

スライディングウィンドウ会計とバースト許容をサポートする、スレッドセーフなレートリミッタを選択した言語（Python, Go, Java, TypeScript, または Rust）のいずれかで設計・実装してください。要件は次のとおりです。 1. **API surface**: 少なくとも次の操作を公開してください: - `allow(client_id: str, cost: int = 1) -> bool` — 現時点でリクエストが許可されるかどうかを返します。 - `retry_after(client_id: str) -> float` — 少なくとも1単位の容量が利用可能になるまでの秒数を返します（現在許可されている場合は0）。 - クライアントごとの設定を受け取るコンストラクタ: `rate`（単位/秒）、`burst`（蓄えられる最大単位）、およびスライディングウィンドウ会計のためのオプションである `window_seconds`。 2. **Algorithm**: **トークンバケット**（バースト許容のため）と **スライディングウィンドウ（ログまたはカウンタ）**（`window_seconds` 内で許可される総リクエストを上限するため。純粋なトークンバケットではリフィル後に持続的な乱用を許してしまう）を組み合わせたハイブリッドを実装してください。リクエストは両方のチェックが通った場合にのみ許可されます。スライディングウィンドウのデータ構造選択（正確なログ vs. 重み付き二窓近似）について正当化し、メモリ/精度のトレードオフを短いコメントブロックまたは付随するノートで議論してください。 3. **Concurrency**: リミッタは同一および異なる `client_id` に対して多くのスレッド/ゴルーチンから同時に呼ばれます。単一のグローバルロックがボトルネックにならないようにしてください（例：クライアント毎のロック、ロックストライピングなど）。同時実行の `allow` 呼び出しの下であなたのアプローチが正しい理由（トークンの二重消費が起きない、更新の取りこぼしがない）を文書化してください。 4. **Time source**: テストが決定論的になるようにクロックを注入可能にしてください。デフォルトではモノトニッククロックを使用してください。 5. **Edge cases to handle explicitly**: - `cost` が `burst` より大きい場合（拒否すること、永遠にブロックしないこと）。 - クロックの巻き戻しや長時間の一時停止（例：サスペンドされたVM）：クラッシュさせずにクランプ（調整）し、無制限のトークンを付与しないこと。 - 新規クライアントの最初のリクエスト（遅延初期化）。 - ステールなクライアントのクリーンアップ（クライアントが停止してもメモリが無制限に成長しないこと）。 - 小数トークン／サブミリ秒の時間処理。 6. **Tests**: 注入可能なクロックを使用して、少なくとも6つの単体テストを提供してください。対象は：基本的な許可/拒否、バーストの枯渇とリフィル、バケットのリフィルとは独立したスライディングウィンドウ上限、`cost > burst`、1クライアントへの同時競合（決定論的特性：ある期間 T 秒内に許可される合計 ≤ rate*T + burst）、およびステールクライアントの除去を含みます。 7. **Complexity**: `allow` の償却時間計算量とクライアントあたりのメモリ計算量を明示してください。 Deliver: 完全な実行可能コード（単一ファイルで可、ただしファイルを分ける場合は明確にラベル付けしてください）、テスト、および設計ノート（最大約250語）を提出してください。