Rate Limiter: A Sliding Window

A classic interview question: "Build a rate limiter that lets each client make at most 3 requests in any 10 seconds." The answer is a sliding window. Keep the times of each client's requests, and when a new request arrives, look back exactly 10 seconds from now. Times older than that are dropped. If the times that are left already reach the limit, the request is refused. Only requests that get through are saved.

A refused request gets 429 Too Many Requests and a Retry-After header: the seconds until the oldest time leaves the window, rounded up. For example, with a limit of 2 per 60 seconds and saved times 100 and 130, a request at 150 is refused with Retry-After: 10, because 100 leaves the window at 160. In Flask, a third value after the status is a dictionary of headers:

@app.get("/report")
def get_report():
    return jsonify({"error": "Not ready yet"}), 503, {"Retry-After": "30"}

Each request names its client in the X-Client-Id header. The tests also move a hidden clock: now() in the starting code returns the time the test sets, so nobody really waits. These requests, in order, must get these answers:

GET /data   ana, clock 1000     →  200  {"client": "ana", "ok": true}
GET /data   ana, clock 1005     →  200  {"client": "ana", "ok": true}
GET /data   ana, clock 1009     →  200  {"client": "ana", "ok": true}
GET /data   ana, clock 1009     →  429  {"error": "Too many requests"}   Retry-After: 1
GET /data   ben, clock 1009     →  200  {"client": "ben", "ok": true}
GET /data   ana, clock 1010     →  200  {"client": "ana", "ok": true}
GET /data   ana, clock 1012.5   →  429  {"error": "Too many requests"}   Retry-After: 3
GET /data   ana, clock 1015     →  200  {"client": "ana", "ok": true}

Your task: the starting code reads the client, saves the time of every request in request_times and always answers 200. Keep only this client's times from the last WINDOW seconds in recent, and when recent already holds LIMIT times, answer 429 with the error "Too many requests" and a Retry-After header.

Assignment
Follow the Coding Tutorial to keep the recent times and refuse a request when the window is full.

Hint
A time t is still inside the window when t > current - WINDOW. The oldest time, recent[0], leaves at recent[0] + WINDOW; round the seconds until then up with math.ceil.