Verify the exact boundaries of rate limits: design principles

Summary

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

Why this 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.

How it works

If you take the clock as a function argument, you can jump to an exact point in time without waiting. The effective window includes only timestamps greater than now-window. Only allowed requests are recorded, and a rejected request does not extend the window. When the window is full, the time until the oldest allowed request expires is rounded up and sent as Retry-After. At the end you compare the third request from the same user with the first request from a different user.

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

A worksheet for reading the contract and predicting failures

What follows is not an answer key to memorize an implementation but a step-by-step code review. Each change fragment deliberately breaks the contract. Note that the normal case may still pass after the change. Before running it, predict which input, exception, or state you would observe to expose the difference, and after implementing it, compare that prediction with the result.

1. Validate the settings

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.

Basis for the judgment: bool is a subtype of int. NaN and infinity also have to be rejected separately.

Faulty change fragment to review:

not isinstance(limit, int)

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

2. Exclude the left edge of the window

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.

Basis for the judgment: check the difference between >=, which keeps a timestamp that has exactly expired, and >.

Faulty change fragment to review:

stamp >= now - window

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

3. Round the waiting time up

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.

Basis for the judgment: if you send Retry-After as 0 because 0.2 seconds remain, the client requests again immediately.

Faulty change fragment to review:

int(history[0] + window - now)

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

4. Split the records per key

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.

Basis for the judgment: if you return a shared list, the cleanup in one request can change the record of another request.

Faulty change fragment to review:

state.get(key, [])

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

5. Record only allowed requests

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).

Basis for the judgment: if you append a rejected request, the expiry time is pushed back on every retry.

Faulty change fragment to review:

len(history) > limit

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

6. Validate the client key

client_key(value) returns a string of 1–40 ASCII letters, digits, and hyphens as it is, and everything else is ValueError.

Basis for the judgment: limit the range of the input so that an unbounded key size cannot put pressure on the memory of the state.

Faulty change fragment to review:

<= 80

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

7. Build the rejection response

limited_response(wait) is a JSONResponse with status 429, body {error:'rate_limited'}, and a Retry-After header set to wait as a string.

Basis for the judgment: send the status and the header together so that the client knows when to retry.

Faulty change fragment to review:

status_code=503

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

8. Finish the request flow with virtual time

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.

Basis for the judgment: do not actually sleep; pass the current time, held in a list, through the clock function.

Faulty change fragment to review:

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

Compare it with the public contract of the function this fragment sits in. If a single success case does not tell them apart, choose as your observation target an input that should be rejected or the state after a failure.

What it looks like in the field

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.

What you will do in the next lab

Eight steps lead to one runnable result. Validate the settings → exclude the left edge of the window → round the waiting time up → split the records per key → record only allowed requests → validate the client key → build the rejection response → finish the request flow with virtual time.

Each step checks actual return values, exceptions, and state changes, not the fact that a function or file exists. After you see the answer, deliberately change a boundary comparison or the cleanup code and check which tests fail. Explain why the earlier tests are kept in the next steps, and write down one operating condition that this lab does not guarantee.