Verify the exact boundaries of rate limits

Goal

Check the sliding window and Retry-After with a virtual clock, and keep per-user limits separate.

Why it matters

As traffic grew, the server began recording every request in the same list. One user's burst of requests blocked even another user's normal requests. The comparison that removes entries at the last instant of the window was also wrong, so the limit lasted one second longer. A test that really waits dozens of seconds makes such boundaries slow and unstable.

Steps

1. In /root/work/fa-rate-window-lab/service.py, validate_limit(limit, window) allows only a positive int limit (excluding bool) and a positive finite int/float window, and returns (limit, float(window)). Everything else is ValueError.

Prepare this once at the start. Existing files are not overwritten.

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

1. In /root/work/fa-rate-window-lab/service.py, active(history, now, window) returns, as a new list in the original order, only the timestamps greater than now-window. history is a sorted, non-decreasing list of timestamps.

2. In /root/work/fa-rate-window-lab/service.py, retry_after(history, now, window) is the larger integer of 0 and the ceil of (the first timestamp + window - now) of a non-empty history that has already been cleaned up. An empty list gives 0.

3. In /root/work/fa-rate-window-lab/service.py, history_for(state, key) returns an empty list for a key that does not exist, and a copy of that record if it does. A lookup alone does not modify state.

4. In /root/work/fa-rate-window-lab/service.py, admit(state, key, now, limit, window) validates the settings and then cleans up the expired records of that key. If there is room, it appends now and returns (True,0); if full, it does not append and returns (False,retry_after).

5. In /root/work/fa-rate-window-lab/service.py, client_key(value) returns a string of 1–40 ASCII letters, digits, and hyphens as it is, and everything else is ValueError.

6. In /root/work/fa-rate-window-lab/service.py, limited_response(wait) is a JSONResponse with status 429, body {error:'rate_limited'}, and a Retry-After header set to wait as a string.

7. In /root/work/fa-rate-window-lab/service.py, create_app(clock, limit=2, window=10) checks X-Client-ID at GET /work: an invalid key gives 400 {error:'invalid_client'}, an allowed request gives 200 {ok:True}, and an excess request gives limited_response. The state is kept separate for each app.

Notes

• You work in the existing lab-dev environment with no internet and no package installation.
• Each step runs within a 45-second grading budget. Do not add real sleeps or network calls.
• The grader loads the submitted module fresh and checks it with independent inputs and a temporary DB. Implement the contract instead of returning the expected values as constants.
• FastAPI official documentation · pytest official documentation · Python sqlite3
• Limitation: this is an example for a single worker held in process memory. It does not guarantee a global limit shared by several Pods or the identity of a malicious client. X-Client-ID is a key for testing, so in production the key should come from an authenticated principal. A persistent clock going backward should be avoided by using a monotonic clock, and the clock in this lab is non-decreasing.

Validate the settings

In /root/work/fa-rate-window-lab/service.py, validate_limit(limit, window) allows only a positive int limit (excluding bool) and a positive finite int/float window, and returns (limit, float(window)). Everything else is ValueError.

Prepare this once at the start. Existing files are not overwritten.

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 is a subtype of int. NaN and infinity also have to be rejected separately.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/01-contract.sh.

Exclude the left edge of the window

In /root/work/fa-rate-window-lab/service.py, active(history, now, window) returns, as a new list in the original order, only the timestamps greater than now-window. history is a sorted, non-decreasing list of timestamps.

Check the difference between >=, which keeps a timestamp that has exactly expired, and >.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/02-contract.sh.

Round the waiting time up

In /root/work/fa-rate-window-lab/service.py, retry_after(history, now, window) is the larger integer of 0 and the ceil of (the first timestamp + window - now) of a non-empty history that has already been cleaned up. An empty list gives 0.

If you send Retry-After as 0 because 0.2 seconds remain, the client requests again immediately.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/03-contract.sh.

Split the records per key

In /root/work/fa-rate-window-lab/service.py, history_for(state, key) returns an empty list for a key that does not exist, and a copy of that record if it does. A lookup alone does not modify state.

If you return a shared list, the cleanup in one request can change the record of another request.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/04-contract.sh.

Record only allowed requests

In /root/work/fa-rate-window-lab/service.py, admit(state, key, now, limit, window) validates the settings and then cleans up the expired records of that key. If there is room, it appends now and returns (True,0); if full, it does not append and returns (False,retry_after).

If you append a rejected request, the expiry time is pushed back on every retry.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/05-contract.sh.

Validate the client key

In /root/work/fa-rate-window-lab/service.py, client_key(value) returns a string of 1–40 ASCII letters, digits, and hyphens as it is, and everything else is ValueError.

Limit the range of the input so that an unbounded key size cannot put pressure on the memory of the state.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/06-contract.sh.

Build the rejection response

In /root/work/fa-rate-window-lab/service.py, limited_response(wait) is a JSONResponse with status 429, body {error:'rate_limited'}, and a Retry-After header set to wait as a string.

Send the status and the header together so that the client knows when to retry.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/07-contract.sh.

Finish the request flow with virtual time

In /root/work/fa-rate-window-lab/service.py, create_app(clock, limit=2, window=10) checks X-Client-ID at GET /work: an invalid key gives 400 {error:'invalid_client'}, an allowed request gives 200 {ok:True}, and an excess request gives limited_response. The state is kept separate for each app.

Do not actually sleep; pass the current time, held in a list, through the clock function.

After saving, check with bash /opt/lab/checks/fa-rate-window-lab/08-contract.sh.