Case: Implement a Rate Limiter
N requests per window, per key. The state is a counter and a window start per key; the representation choice is fixed window against sliding window, and it changes what "N per window" means at the boundary. V2 is "shared across servers", and it changes where the state lives.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
You need to stop one client from sending too many requests. What is a rate limiter as a concept, what does it have to remember, and why does the choice of window change its behaviour rather than just its cost?
The login endpoint is being hammered, or the API needs a fair-use rule. You know the sentence — "no more than N requests per minute" — and you do not know what to store, per whom, or what to do at the edge of the minute.
Add the framework's rate-limit middleware with N = 100 and a window of a minute. It has defaults for everything, it is one line, and requests start getting rejected.
Rejections happen and nobody can say why a particular client was rejected at the 61st second. The middleware picked a window algorithm; the algorithm decides whether 100 requests at 0:59 and 100 at 1:01 are fine or a violation, and that decision is now the product's behaviour by default.
- Rejections happen and nobody can say why a particular client was rejected at the 61st second. The middleware picked a window algorithm; the algorithm decides whether 100 requests at 0:59 and 100 at 1:01 are fine or a violation, and that decision is now the product's behaviour by default.
- The state — what is counted, per what key, in what store — is invisible. When a second server is added, each server counts separately and the limit silently doubles; the middleware's README mentioned this in a paragraph nobody read.
- The concept was never stated, so the questions the product team asks — "is the limit per user or per IP?", "does a rejected request count?", "what does the client see?" — have answers only in the middleware's options page.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Define the concept: for each key, allow at most N requests within any window of length W, and reject the rest. Every word carries a decision — "key" (per whom), "N" and "W" (the policy), "any window" (sliding) against "the current window" (fixed) — and the concept is not finished until each is chosen.
- Discover the state per key: a count and the window it belongs to. That is two numbers per key, and the representation question is whether the window is a fixed bucket (count, windowStart) or a sliding record (timestamps of recent requests, or an approximation). The two are different behaviours with different costs, not different implementations of one behaviour.
- Write the operations — check(key, now) → allowed or rejected, with the state updated — and the rules: never more than N in a window; a rejected request does or does not count (decide); the clock the limiter uses is monotonic. Write the boundary example, because it is where the two representations disagree.
- Implement the fixed window in memory, trace it across the boundary, and write down the reading that moves you to the sliding version and the one that moves the state out of the process: a second server (A Mutex on Server A Does Nothing About Server B in Concurrency).
Meaning and state — every word in "N per window per key" is a decision
The middleware hid five decisions behind two numbers. The question ladder makes them visible: the best form of the request names the key, the window definition and what the client sees, and it can be tested with four timestamps.
The state canvas is per key and depends on the window definition — which is unusual and is the point: here the representation is chosen before the state is final, because the state is the representation. The unknowns board keeps the decisions that are not the limiter's to make.
- ✓Policy shape: N per W per key; rejection is a normal output with a retry-after.
- ✓State per key: a count and a window (fixed), or recent timestamps (sliding).
- ✓Operation: check(key, now); no side effects beyond the key's own state.
- ~One process in V1 — the map is the store. Written down because V2 breaks it.
- ~The clock is monotonic — the limiter never reads the wall clock for windows.
? Per user or per IP?
becomes Which key does the policy protect — an account, a network address, or both with different N?
experiment Ask the owner of the endpoint what the limit is for; a fair-use limit is per account, a brute-force defence is per IP and per target account both.
? Is the boundary leak okay?
becomes Is up to 2N requests in a short span around a window boundary acceptable for what this limit protects?
experiment Run the 0:59 / 1:01 example past the endpoint owner with both answers; their reaction chooses the representation.
? What should the client see?
becomes Which status and which header carry the rejection and the retry-after, and does the client honour it?
experiment Read the APIs rate-limiting contract lesson; adopt its shape rather than inventing headers.
why The best form fixes the key, the window definition and the client contract; the boundary sentence is a test case that decides fixed against sliding before a line is written.
Rules, the boundary example, and the representation as behaviour
The rule is the policy sentence encoded, and it contains the branch the whole limiter turns on: is this request inside the current window? The fixed-window version below resets the count when the window has elapsed; the sliding version would instead drop timestamps older than W.
The compare device shows the two on the boundary example. It is not a worse/better pair in the usual sense — both are correct implementations of different policies — and the "because" says what makes one right for a given protection.
state[alice] = { count: 2, windowStart: 0:00 } (N = 2, W = 60 s)state[alice] = { count: 1, windowStart: 1:00 }; output: allowedrule Within the window the key is currently in, no more than N requests are allowed.
↓ becomes validation If the window has elapsed, start a new one with count 0; then allow only if count < N, and count the request either way.
if now - state.windowStart >= W:
state.windowStart = now; state.count = 0
state.count += 1
allowed = state.count <= NWindow 0:00–1:00 holds two, window 1:00–2:00 holds two: all four allowed. Four requests in two seconds against "two per minute". Two integers per key.
At 1:01 the span 0:01–1:01 already holds the two from 0:59: the last two are rejected. Exact, at up to N timestamps per key.
The fixed window is right when the policy is fair use and the leak is harmless; the sliding window is right when the limit is a defence and the leak is the attack. The representation is the policy — choose it from what the limit protects, not from which is "more accurate".
The trace across the boundary, then where the state lives
The trace runs the fixed-window check on the request that exposes the leak. Its branch is the window test; watch it reset the count and allow the third request in two seconds — correctly, under the fixed policy.
The ladder says how far the limiter goes. V2 is the level the middleware README buried: the moment a second server exists, per-process state means per-server limits. Moving the state to a shared store is a different lesson's mechanism; this lesson's job is to name the trigger and the new rules the move introduces.
- inputstate[alice] = { count: 2, windowStart: 0:00 }; now = 1:01; N = 2, W = 60 s
- lookupstate.get(alice) → found; now − windowStart = 61 s
- branch61 ≥ 60 → the window has elapsed → reset: windowStart = 1:01, count = 0
- mutationcount: 0 → 1
- outputallowed (1 ≤ 2) — the third request in two seconds, and correct under the fixed policy; the sliding policy would have rejected it
- V1 — fixed window in memoryA map from key to { count, windowStart }; check on every request; inactive keys forgotten after W. — The policy is fair use, the leak is acceptable, and there is one process (Hash Map in DSA for the O(1) average lookup).
- V1b — sliding or token bucketRecent timestamps per key, or the approximate two-bucket weighting, or a refilling bucket. — The limit protects something the boundary leak would expose — the policy changed, so the representation must (Rate Limit Algorithms in Backend).
- V2 — shared across serversThe per-key state in a store every server can reach, updated with an atomic increment; a policy for when the store is unreachable. — A second server exists and per-process counting has been observed doubling the limit — the reading, not the fear (Rate Limit Algorithms).
- V3 — the contractStatus, retry-after and limit headers as the API lesson specifies; quotas as a separate concept. — Clients must be able to behave well, and a quota — N per day with a bill — is a different policy with different state (The Rate-Limit Contract, Quotas vs Rate Limits in APIs).
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Rate Limiter = A gate that answers "may this key make one more request now?" so that no key makes more than N requests within one window.
- Does a rate limiter have identity? The limiter does not; its entries do. There is one entry per key — an API key, a user, an IP address — and the entry is identified by the key. Two keys with the same count are two entries and never interact.
- Who owns it? The service that is protecting itself. The client does not own its entry and cannot reset it; that is the point. The key is the client's identity as the service sees it, which is a security decision made elsewhere.
- How long does an entry exist? One window. An entry that has not been touched for a window is worthless and can be forgotten; the limiter is the rare concept whose state is meant to expire. Memory is bounded by the number of active keys, not by history.
- Should it survive reload? Usually no. A restart that forgets every count lets every key start fresh for one window — an acceptable loss for most services, and a reason the store can be a cache rather than a database. A limiter that guards a paid quota is a different concept and does need durability.
- Should it be shared across servers? Yes, as soon as there are two. A limit of N per server is a limit of N × servers per key, which is not the limit anyone wrote down. This is the V2 step, and it is where the counter moves into a central store.
- limit Ninteger > 0keepHow many requests a window permits. Configuration, not per-key state.
- windowdurationkeepHow long a window lasts. Configuration.
- entries[key].countinteger ≥ 0keepHow many requests the key has made in the current window. The one thing allow changes.
- entries[key].windowStarttimestampkeepWhen the current window began, so allow knows whether the count is stale.
- entries[key].timestampslist of timestampsdependsA sliding log needs every request time in the last window.
- entries[key].remainingintegerderiveThe response header says how many are left.
- entries[key].lastSeentimestampderiveTo expire idle entries.
- entries[key].rejectedintegerdropDashboards want to know how often a key hits the limit.
- domain Allow — true if the request may proceed, false if it is over the limit
- read Remaining — how many more requests the key may make in the current window
- delete Reset — nothing
- domain Prune idle entries — how many entries were removed
- • No key makes more than N requests in one window — where "window" is the fixed window [windowStart, windowStart + window).
- • Keys are independent.
- • A rejected request does not count.
- • remaining is never negative.
- • The clock only moves forward.
How to do it
Most important first.
- Write the policy in one sentence with N, W and the key filled in — "at most 10 per minute per user id, unauthenticated by IP" — and get it agreed before writing state. It is a product decision wearing a technical costume.
- Challenge the state: count (keep), windowStart (keep for fixed), timestamps of recent requests (keep for exact sliding — O(N) memory per key), previous-window count (keep for approximate sliding), lastRejectedAt (drop — no operation reads it).
- Write the operation contract: input key and now; reads the key's state; changes count and window; output allowed or rejected plus how long until allowed; side effects none; errors none — a rejection is a normal output, not an error of the limiter.
- Write the boundary example: N = 2, W = 60 s; requests at 0:59, 0:59, 1:01, 1:01. Predict the fixed-window answer (all allowed) and the sliding answer (the last two rejected) before implementing either.
- Implement fixed window first, in memory, with a map from key to state; run the examples; then decide whether the boundary behaviour is acceptable for this policy.
- Write the V2 trigger next to the implementation: "the moment there are two servers, this state must move to a shared store or the limit is per server" (Rate Limiting and Rate Limit Algorithms in Backend for the algorithms).
Worked on a concrete problem
The move has to produce something. This is what it produced.
- Meaning: at most N requests per key within a window of W. Key: the user id when authenticated, the client IP otherwise. Identity: the limiter state has identity per key; the limiter itself has none. Lifetime: a key's state lives while it is active and can be forgotten once a full window has passed without requests.
- State (fixed window): per key { count, windowStart }. State (exact sliding): per key a queue of the timestamps within the last W — O(N) per key. State (approximate sliding): per key { currentCount, previousCount, windowStart } and a weighted estimate. Three representations, three memory costs, three boundary behaviours.
- Operations: check(key, now) → allowed or rejected with retryAfter. Rules: never more than N allowed per window under the chosen definition of window; the clock is monotonic so a wall-clock jump cannot open or close a window; keys are forgotten after inactivity so memory is bounded by active keys, not all keys ever seen.
- Examples, N = 2, W = 60 s: fresh key at 0:00 → allowed (count 1); 0:10 → allowed (count 2); 0:20 → rejected, retryAfter 40 s; 1:00 → allowed (new window, count 1). The boundary: 0:59, 0:59, 1:01, 1:01 → fixed window allows all four — four requests in two seconds against a policy of two per minute; sliding allows two and rejects two.
- Representation: a map from key to state — check is called on every request and must find the key in O(1) average; an array of keys would scan per request. Fixed window chosen for V1 because the state is two integers per key and the boundary leak (up to 2N in a short span) is acceptable for a fair-use limit and not for a brute-force defence on login — which is a policy decision written next to the choice (Authenticate First, or Rate-Limit First? in Backend).
How you know it worked
What now exists that did not before, and what question you can now ask.
- The policy sentence has N, W and the key filled in and agreed, and it names which window definition it means.
- The boundary example is written with both predicted answers, and your implementation matches the one you chose.
- You can say what the state is per key, what it costs in memory, and when a key's state is forgotten.
- The sentence "adding a second server changes the limit" is written next to the code, with the reading that will trigger V2.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?What are N, W and the key — and who agreed them?
- ?Does "N per window" mean the current fixed bucket or any sliding span of W — and what happens at the boundary under each?
- ?What is stored per key, what does it cost, and when is it forgotten?
- ?What does the client see when rejected, and does a rejected request count?
- ?What changes when there is a second server — and what reading tells me it has arrived?
What can go wrong
- The exact sliding window is built for a limit of thousands per minute, and every key holds thousands of timestamps; the memory cost was never annotated.
- The fixed window is used for a brute-force defence, and an attacker gets 2N attempts around every boundary — the leak was acceptable for fair use and was never re-examined when the policy changed.
- The limiter uses the wall clock, and a time sync jumps the clock backwards; every window restarts or never ends, and the bug is not reproducible (Never Measure a Duration With the Wall Clock in Distributed).
- Fixed window is two integers per key and leaks up to twice the limit at the boundary; sliding is exact and costs memory per request or accepts an approximation. Neither is free, and the choice depends on what the limit is protecting.
- Forgetting inactive keys bounds memory and means a key that returns after a full window starts fresh — correct by definition, and worth writing down so it is not read as a bug.
- Deriving the limiter instead of using the middleware means owning the clock, the store and the boundary; the middleware would have owned them badly but for free.
- "A rate limiter is a counter with a timer." It is a policy — N, W, key and window definition — plus per-key state; the counter is the fixed-window representation of one of several policies.
- "Sliding window is just more accurate fixed window." It is a different definition of the policy, with a different memory cost; a product that promised "100 per minute" and used a fixed window has promised something the sliding version would reject.
- "Put the counters in a shared cache and the multi-server problem is solved." Shared state introduces a round trip per request, a race between read and increment that needs an atomic operation, and a dependency whose failure must have a policy — allow or reject when the store is down (Rate Limit Algorithms is the lesson for that, not this).
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- ILLUSTRATIVEN = 2, W = 60 s, requests at 0:59 and 1:01, and the login endpoint are invented to show the boundary; the leak factor of the fixed window is real and bounded by 2N.
- DOMAIN-SPECIFICFor a fair-use API limit the fixed window's boundary leak is acceptable and its cost is unbeatable; for a brute-force defence on login the leak is the attack, and a sliding or token-bucket policy is V1 — the concept is the same, the policy flips.
- SCALE-SPECIFICIn one process the map is the whole store; with a second server the state must be shared or the limit is per server, and the shared version needs an atomic increment and a failure policy — the lesson stops at naming that trigger.
Where the depth lives
This domain asks the question and hands the answer off by name.