レート制限の時刻境界を検証する

目標

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

なぜ重要なのか

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

ステップ

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

最初に一度だけ準備してください。既存のファイルは上書きしません。

mkdir -p /root/work/fa-rate-window-lab
test -e /root/work/fa-rate-window-lab/service.py || cp /opt/fixtures/ten_labs/fa-rate-window-lab/service.py /root/work/fa-rate-window-lab/service.py
cd /root/work/fa-rate-window-lab

/root/work/fa-rate-window-lab/service.pyで、active(history, now, window)は、now-windowより大きい時刻だけを、元の順序の新しいリストとして返します。historyは、ソートされた非減少の時刻です。
/root/work/fa-rate-window-lab/service.pyで、retry_after(history, now, window)は、すでに整理された空でないhistoryの最初の時刻+window-nowをceilした値と0のうち、大きいほうの整数です。空のリストは0です。
/root/work/fa-rate-window-lab/service.pyで、history_for(state, key)は、ないキーなら空のリスト、あればその記録のコピーを返します。取得するだけで、stateを変更しません。
/root/work/fa-rate-window-lab/service.pyで、admit(state, key, now, limit, window)は、設定を検証したあと、該当のキーの期限切れの記録を整理します。余裕があればnowを追加して(True,0)、いっぱいなら追加せずに(False,retry_after)を返します。
/root/work/fa-rate-window-lab/service.pyで、client_key(value)は、1–40文字のASCIIの英字・数字・ハイフンの文字列をそのまま返し、それ以外はValueErrorです。
/root/work/fa-rate-window-lab/service.pyで、limited_response(wait)は、ステータス429、本文{error:'rate_limited'}、Retry-Afterヘッダーはwaitを文字列にしたJSONResponseです。
/root/work/fa-rate-window-lab/service.pyで、create_app(clock, limit=2, window=10)は、GET /workでX-Client-IDを検査して、不正なキーは400 {error:'invalid_client'}、許可は200 {ok:True}、超過はlimited_responseです。stateは、アプリごとに分離します。

参考

インターネットやパッケージのインストールなしで、既存のlab-dev環境で行います。
各ステップは、45秒の採点バジェットの中で実行されます。実際のsleepやネットワーク呼び出しを追加しないでください。
採点は、提出されたモジュールを新しく読み込んで、独立した入力と一時的なDBで検査します。期待値を定数で返す代わりに、契約を実装してください。
FastAPI公式ドキュメント・pytest公式ドキュメント・Python sqlite3
限界: プロセスのメモリにある、単一のワーカー用の例です。複数のPodが共有するグローバルな上限や、悪意のあるクライアントの身元は、保証しません。X-Client-IDはテスト用のキーなので、本番では、認証されたプリンシパルからキーを得る必要があります。継続的なクロックの巻き戻りは、単調クロックの使用で避ける必要があり、このラボのclockは非減少です。

設定を検証する

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

最初に一度だけ準備してください。既存のファイルは上書きしません。

mkdir -p /root/work/fa-rate-window-lab
test -e /root/work/fa-rate-window-lab/service.py || cp /opt/fixtures/ten_labs/fa-rate-window-lab/service.py /root/work/fa-rate-window-lab/service.py
cd /root/work/fa-rate-window-lab

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/01-contract.shで確認してください。

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

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

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/02-contract.shで確認してください。

待ち時間を切り上げる

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

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/03-contract.shで確認してください。

キーごとに記録を分ける

/root/work/fa-rate-window-lab/service.pyで、history_for(state, key)は、ないキーなら空のリスト、あればその記録のコピーを返します。取得するだけで、stateを変更しません。

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/04-contract.shで確認してください。

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

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

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/05-contract.shで確認してください。

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

/root/work/fa-rate-window-lab/service.pyで、client_key(value)は、1–40文字のASCIIの英字・数字・ハイフンの文字列をそのまま返し、それ以外はValueErrorです。

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/06-contract.shで確認してください。

拒否のレスポンスを作る

/root/work/fa-rate-window-lab/service.pyで、limited_response(wait)は、ステータス429、本文{error:'rate_limited'}、Retry-Afterヘッダーはwaitを文字列にしたJSONResponseです。

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/07-contract.shで確認してください。

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

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

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

保存したら、bash /opt/lab/checks/fa-rate-window-lab/08-contract.shで確認してください。