レート制限の時刻境界を検証する：設計原理

一言でいうと

仮想クロックでスライディングウィンドウとRetry-Afterを検査し、ユーザーごとの上限を分離します。

なぜ必要なのか

トラフィックが増えると、サーバーはすべてのリクエストを同じ一覧に記録し始めました。1人のユーザーの連続したリクエストが、ほかのユーザーの正常なリクエストまで止めました。ウィンドウの最後の時刻で項目を削除する比較演算も間違っていて、制限が1秒長く維持されました。実際に数十秒待つテストは、このような境界を、遅くて不安定にします。

どう動くのか

クロックを関数の引数として受け取れば、待たずに、正確な時点へ移動できます。有効なウィンドウは、now-windowより大きいタイムスタンプだけを含みます。許可したリクエストだけを記録し、拒否したリクエストは、ウィンドウを広げません。いっぱいになったときは、最も古い許可したリクエストが期限切れになるまでの時間を切り上げて、Retry-Afterとして送ります。最後に、同じユーザーの3回目のリクエストと、別のユーザーの最初のリクエストを比べます。

client id → 해당 키의 기록 → 만료 제거 → 여유 있음: 기록+200
                                      └→ 꽉 참: 기록 보존+429

契約を読んで失敗を予測するワークシート

以下は、実装をまるごと暗記するための答案ではなく、ステップごとのコードレビューです。各変更の断片は、意図的に契約を壊しています。変更したあとでも、正常な例は通ることがある点に注意してください。実行する前に、どの入力・例外・状態を観測すれば違いが表に出るかを予想し、実装したあとで、その予想と結果を比べます。

1. 設定を検証する

validate_limit(limit, window)は、boolを除く正のint型のlimitと、正の有限なint/floatのwindowだけを許可して、(limit, float(window))を返します。それ以外は、ValueErrorです。

判断の根拠: boolは、intのサブタイプです。NaNと無限大も、別に拒否する必要があります。

レビューする誤った変更の断片:

not isinstance(limit, int)

この断片が入った関数の公開契約と比べてみてください。成功例1つでは区別できないなら、拒否されるべき入力や、失敗したあとの状態を観測の対象に選びます。

2. ウィンドウの左の境界を除外する

active(history, now, window)は、now-windowより大きい時刻だけを、元の順序の新しいリストとして返します。historyは、ソートされた非減少の時刻です。

判断の根拠: ちょうど期限切れになった時刻を残す>=と、>の違いを確認します。

レビューする誤った変更の断片:

stamp >= now - window

3. 待ち時間を切り上げる

retry_after(history, now, window)は、すでに整理された空でないhistoryの最初の時刻+window-nowをceilした値と0のうち、大きいほうの整数です。空のリストは0です。

判断の根拠: 0.2秒残っているからといってRetry-Afterを0にすると、クライアントがすぐに再リクエストします。

レビューする誤った変更の断片:

int(history[0] + window - now)

4. キーごとに記録を分ける

history_for(state, key)は、ないキーなら空のリスト、あればその記録のコピーを返します。取得するだけで、stateを変更しません。

判断の根拠: 共有されたリストを返すと、1つのリクエストの整理が、別のリクエストの記録を変えてしまうことがあります。

レビューする誤った変更の断片:

state.get(key, [])

5. 許可したリクエストだけを記録する

admit(state, key, now, limit, window)は、設定を検証したあと、該当のキーの期限切れの記録を整理します。余裕があればnowを追加して(True,0)、いっぱいなら追加せずに(False,retry_after)を返します。

判断の根拠: 拒否されたリクエストを追加すると、リトライするたびに、期限切れの時刻が後ろにずれます。

レビューする誤った変更の断片:

len(history) > limit

6. クライアントキーを検証する

client_key(value)は、1–40文字のASCIIの英字・数字・ハイフンの文字列をそのまま返し、それ以外はValueErrorです。

判断の根拠: キーのサイズが無制限だと、状態のメモリを圧迫するので、入力の範囲を制限します。

レビューする誤った変更の断片:

<= 80

7. 拒否のレスポンスを作る

limited_response(wait)は、ステータス429、本文{error:'rate_limited'}、Retry-Afterヘッダーはwaitを文字列にしたJSONResponseです。

判断の根拠: クライアントが再試行の時間を知れるように、ステータスとヘッダーを一緒に送ります。

レビューする誤った変更の断片:

status_code=503

8. 仮想時間でリクエストの流れを完成させる

create_app(clock, limit=2, window=10)は、GET /workでX-Client-IDを検査して、不正なキーは400 {error:'invalid_client'}、許可は200 {ok:True}、超過はlimited_responseです。stateは、アプリごとに分離します。

判断の根拠: 実際にsleepせず、リストに入れた現在時刻を、clock関数で渡します。

レビューする誤った変更の断片:

admit(state, "shared", clock(), limit, window)

現場での姿

プロセスのメモリにある、単一のワーカー用の例です。複数のPodが共有するグローバルな上限や、悪意のあるクライアントの身元は、保証しません。X-Client-IDはテスト用のキーなので、本番では、認証されたプリンシパルからキーを得る必要があります。継続的なクロックの巻き戻りは、単調クロックの使用で避ける必要があり、このラボのclockは非減少です。

次のラボですること

8つのステップが、1つの実行可能な成果物につながります。設定を検証する → ウィンドウの左の境界を除外する → 待ち時間を切り上げる → キーごとに記録を分ける → 許可したリクエストだけを記録する → クライアントキーを検証する → 拒否のレスポンスを作る → 仮想時間でリクエストの流れを完成させる、という流れです。

各ステップは、関数やファイルが存在するという事実ではなく、実際の戻り値・例外・状態の変化を検査します。正解を見たあとには、わざと境界の比較や後始末のコードを変えて、どのテストが失敗するかを確認してください。前のテストが次のステップでも維持される理由を説明し、このラボが保証しない本番の条件を1つ書いてみてください。