Fixed Window Counter

Your gateway from the last lesson now tells clients where they stand. Every response carries the X-RateLimit-* headers, and the login endpoint gets a tighter budget than the rest of the API. By the end you will also have reproduced, on the wire, the one flaw that makes people look for a better algorithm.

One counter, reset on the boundary

Time is cut into aligned windows. For a window of W seconds, the window containing time t starts at floor(t / W) * W and ends W seconds later. A client's state is two numbers: the window it last spoke in and how many requests that window has counted. On each request, if the stored window is older than the current one, the counter is stale and starts from zero.

That is O(1) time and O(1) memory per client, and old windows are simply overwritten. It is the natural fit for calendar quotas: GitHub's REST API gives 5,000 requests per hour, and the reset instant is published to the client.

What the headers say

GitHub's real response to a client with budget left:

HTTP/1.1 200 OK\r\n
x-ratelimit-limit: 5000\r\n
x-ratelimit-remaining: 4999\r\n
x-ratelimit-reset: 1700003600\r\n

A refused request adds Retry-After, the seconds left in the window, rounded up.

A budget belongs to an identity and a route class

The bytes POST /login are worth far less to an attacker than a thousand GET /v1/items, so they deserve a smaller budget. Key the counter by both: the client and the class of route. A client who spends its three login attempts keeps its full API budget, and the reverse. The class is decided from the method and the path alone, and the path ends where the query string begins: /login?next=%2Fhome is still /login.

The flaw: boundary bursts

The counter forgets everything at the boundary. With budget 3 and W = 10:

Six requests were allowed in three seconds under a rule that says "3 per 10 seconds". Worst case a client gets double the budget across any boundary. A second effect: every blocked client's quota returns at the same instant, so clients that poll until unblocked arrive together. The next lesson removes the boundary.

Common mistakes

• Off by one in Remaining. Report the value after counting the current request.
• One counter for every route. Three failed logins must not spend the API budget.
• Matching the target as a whole string. /login?next=... is a login; /login/ and /loginx are not the exact path /login, and a GET /login is not a login attempt.
• Delta where the epoch belongs. Reset is the window end as a timestamp, an integer.

Your exercise

Give the gateway two rules: POST /login gets 3 per window, everything else gets 10, each counted separately per client. Answer with the headers above, in the order the exercise lists.