--- title: 'Rate Limiter' source: 'https://academia.sh/en/courses/case-studies/rate-limiter' course: 'Case Studies' language: en updated: '2026-08-23T07:01:25+00:00' license: 'CC BY-SA 4.0' --- # Rate Limiter Designing the component whose job is to reject the request: the overshoot allowed by fixed window, sliding window counter, and token bucket measured across three request patterns, the doubling crossing at the window boundary counted, the overshoot and false-rejection count the distributed counter produces under centralized, split-quota, and delayed-synchronization arrangements, and the synchronization interval determining the threshold. In the previous two cases, the system's job was to satisfy a request; failure was a bad outcome. This case designs the reverse: a component whose job is to **reject** the request. Rate limiting, as an action, was established in the Traffic Layer course and the Caching, Queues and Asynchronous Processing course; there, the location of the decision was addressed, not its algorithm. What is designed here is the rate limiter component itself. The rejection decision is made by looking at a shared counter, and the counter is distributed. Two questions follow from this: in what form the counter's window is defined lets the count climb above the declared limit, and how much drift concurrently reading and writing nodes produce in the counter. ## Constraints and Scope The functional requirements: counting requests per client, rejecting a request that exceeds the limit, reporting the remaining allowance and wait time in the response, and reading the limit from a rule set. What is not designed: authentication, billing for the quota, abuse detection, and the rule-management interface. The non-functional requirements are written with a threshold and its source: the number of requests a client lets through in any 60-second interval does not exceed 1.1 times the declared limit (source: the limit being a promise made to the client), a client that stays under the limit is never rejected (source: the other side of the same promise), and a request is not rejected when the counter store goes down (source: the limiter itself not being a source of outages). ## Assumptions and Scale | Code | Assumption | Value | Rationale | |---|---|---|---| | HS1 | tracked clients | 200,000 | number of distinct keys the limit applies to | | HS2 | peak requests at the edge | 40,000/s | total request rate passing through the limiter | | HS3 | declared limit per client | 600 requests / 60 s | the right written into the contract | | HS4 | limiter node count | 8 | horizontal scale at the edge | | HS5 | counter synchronization interval | 0.2 seconds | how often nodes refresh the shared view | | HS6 | counter record | 48 bytes | key, count, window timestamp | | HS7 | sliding window slice | 12 (5 seconds each) | granularity the 60 seconds is split into | | HS8 | token bucket capacity | 60 tokens | allowance left for a burst | ```js // rate-limit/scale.mjs — the back-of-envelope calculation drawn from the HS assumption table const HS = { clients: 200_000, peakRequests: 40_000, limit: 600, windowS: 60, nodes: 8, syncS: 0.2, recordBytes: 48, slices: 12 }; // HS1..HS8 const perNode = HS.peakRequests / HS.nodes; console.log(`peak requests/s per node ${perNode}`); console.log(`touches/s if using a centralized counter ${HS.peakRequests}`); console.log(`client limit's per-second equivalent ${HS.limit / HS.windowS}`); console.log(`\n${"counter arrangement".padEnd(25)}${"records per client".padStart(21)}${"total MB".padStart(11)}`); for (const [name, n] of [["fixed window", 1], ["token bucket", 1], ["sliding window counter", HS.slices]]) console.log(`${name.padEnd(25)}${String(n).padStart(21)}` + `${((HS.clients * n * HS.recordBytes) / 1e6).toFixed(2).padStart(11)}`); const blindCeiling = (HS.limit / HS.windowS) * HS.syncS * HS.nodes; console.log(`\nsync ceiling: requests a node misses in ${HS.syncS} s = ` + `${perNode * HS.syncS} (all clients)`); console.log(`blind ceiling for a single client = (limit/s) x sync x nodes = ${blindCeiling} requests`); console.log(`threshold: 1.1 times the limit = ${HS.limit * 1.1}; with the blind ceiling ${HS.limit + blindCeiling} -> ` + `${HS.limit + blindCeiling <= HS.limit * 1.1 ? "passes" : "fails"}`); ``` ``` peak requests/s per node 5000 touches/s if using a centralized counter 40000 client limit's per-second equivalent 10 counter arrangement records per client total MB fixed window 1 9.60 token bucket 1 9.60 sliding window counter 12 115.20 sync ceiling: requests a node misses in 0.2 s = 1000 (all clients) blind ceiling for a single client = (limit/s) x sync x nodes = 16 requests threshold: 1.1 times the limit = 660; with the blind ceiling 616 -> passes ``` These numbers belong to the **calculation** class. Three of them shape the design. First, if a centralized counter is used, the peak edge needs 40,000 touches per second; this makes the limiter itself the busiest write source in the system. Second, the sliding window counter demands 115.20 MB, exactly 12 times the fixed window's 9.60 MB; the granularity is written directly to memory. Third, the blind ceiling is 16 requests: within a 0.2-second synchronization interval, eight nodes can let through at most 16 requests for one client without knowing about each other, which comes to 616 and stays below the 660 threshold. The synchronization interval was chosen by this calculation. ## The Window's Shape Determines the Overshoot The measurement is an in-process model: there is no real clock, network, or store; time is the model's clock and the request list is deterministic. Three patterns are tried: a **uniform** flow at twice the limit's rate, a flow **piled up** on either side of the window boundary, and a flow arriving **right at the limit** but spaced out. What is measured is the highest number accepted requests reach in any 60-second sliding interval. ```js // rate-limit/window.mjs — in-process model of the three window algorithms. There is no real // clock, network, or store: time is the model's clock (ms) and the request list is deterministic. const LIMIT = 600, WINDOW = 60_000, SLICE = 5_000, DURATION = 180_000; // HS3, HS7 const BUCKET = 60, REFILL = LIMIT / (WINDOW / 1000); // HS8 const patterns = { "uniform 2x": () => Array.from({ length: (DURATION / 1000) * 20 }, (_, i) => i * 50), "piled at boundary": () => { const times = []; for (const boundary of [WINDOW, 2 * WINDOW]) for (const [start, n] of [[boundary - SLICE, LIMIT], [boundary, LIMIT]]) for (let i = 0; i < n; i += 1) times.push(start + Math.floor((i * SLICE) / n)); return times.sort((a, b) => a - b); }, "spaced at the limit": () => { const times = []; for (let k = 0; k < DURATION / WINDOW; k += 1) for (let i = 0; i < LIMIT; i += 1) times.push(k * WINDOW + Math.floor((i * SLICE) / LIMIT)); return times; }, }; const ALGORITHM = { "fixed window": () => { let p = -1, n = 0; return (t) => { const k = Math.floor(t / WINDOW); if (k !== p) { p = k; n = 0; } return n < LIMIT && (n += 1, true); }; }, "sliding window counter": () => { const counts = new Map(); return (t) => { const slice = Math.floor(t / SLICE), firstValid = slice - WINDOW / SLICE + 1; for (const k of counts.keys()) if (k < firstValid) counts.delete(k); let total = 0; for (const v of counts.values()) total += v; if (total >= LIMIT) return false; counts.set(slice, (counts.get(slice) ?? 0) + 1); return true; }; }, "token bucket": () => { let tokens = BUCKET, last = 0; return (t) => { tokens = Math.min(BUCKET, tokens + ((t - last) / 1000) * REFILL); last = t; return tokens >= 1 && (tokens -= 1, true); }; }, }; const busiestWindow = (accepted) => { let peak = 0; for (let i = 0, j = 0; i < accepted.length; i += 1) { while (accepted[i] - accepted[j] >= WINDOW) j += 1; peak = Math.max(peak, i - j + 1); } return peak; }; console.log(`model: ${DURATION / 1000} s, limit ${LIMIT}/${WINDOW / 1000} s, bucket ${BUCKET} tokens, refill ${REFILL}/s`); for (const [patternName, generate] of Object.entries(patterns)) { const requests = generate(); console.log(`\npattern "${patternName}": ${requests.length} requests`); console.log(`${"algorithm".padEnd(25)}${"accepted".padStart(11)}${"rejected".padStart(11)}` + `${"busiest 60 s".padStart(15)}${"overshoot".padStart(11)}${"overshoot ratio".padStart(18)}`); for (const [algoName, make] of Object.entries(ALGORITHM)) { const allow = make(), accepted = requests.filter((t) => allow(t)); const peak = busiestWindow(accepted); console.log(`${algoName.padEnd(25)}${String(accepted.length).padStart(11)}${String(requests.length - accepted.length).padStart(11)}` + `${String(peak).padStart(15)}${String(peak - LIMIT).padStart(11)}${`x${(peak / LIMIT).toFixed(3)}`.padStart(18)}`); } } ``` ``` model: 180 s, limit 600/60 s, bucket 60 tokens, refill 10/s pattern "uniform 2x": 3600 requests algorithm accepted rejected busiest 60 s overshoot overshoot ratio fixed window 1800 1800 600 0 x1.000 sliding window counter 1800 1800 600 0 x1.000 token bucket 1859 1741 659 59 x1.098 pattern "piled at boundary": 2400 requests algorithm accepted rejected busiest 60 s overshoot overshoot ratio fixed window 1800 600 1200 600 x2.000 sliding window counter 1200 1200 600 0 x1.000 token bucket 318 2082 159 -441 x0.265 pattern "spaced at the limit": 1800 requests algorithm accepted rejected busiest 60 s overshoot overshoot ratio fixed window 1800 0 600 0 x1.000 sliding window counter 1800 0 600 0 x1.000 token bucket 327 1473 109 -491 x0.182 ``` These numbers belong to the **measurement** class and are deterministic; there is no randomness. The first pattern keeps all three algorithms within the limit, with a single exception: the token bucket at 659, that is, 1.098 times. This 59-request excess is the bucket's capacity, and HS8 chooses this number directly. Compared against the 1.1x threshold, a capacity of 60 turns out to be the ceiling; raised to 66, the threshold would be crossed. The second pattern turns the fixed window's known flaw into a number: requests piled on either side of the window boundary fall into two separate counters, and 1200 requests get through in a sliding 60-second interval — exactly double. In a system whose limit is declared as 600, a client can let 1200 requests through. The sliding window counter stays at 600 on the same pattern. The third pattern shows the token bucket's cost. The client sits right at the limit, sending 600 requests per window and never exceeding any limit; the sliding window counter lets all of them through, and the token bucket rejects 1473 of the 1800 requests. The bucket does not bank idle time; a client that runs intermittently cannot use its full allowance. The second non-functional requirement is violated by this row, and so the algorithm chosen is the **sliding window counter**. ## The Distributed Counter's Drift The chosen algorithm works correctly on a single node. When eight nodes count the same client, the question changes. Three arrangements are compared: the **centralized** arrangement, where every request touches a shared counter; **split quota**, where the limit is divided by the node count; and **delayed synchronization**, where nodes count locally and synchronize at an interval. ```js // rate-limit/distributed.mjs — in-process model of the distributed counter. There is no real // node, network, or store: node assignment uses a seeded generator, synchronization uses the model clock. const LIMIT = 600, WINDOW = 60, NODES = 8; // HS3, HS4 function generator(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } export function run({ arrangement, rate, interval = 0.2, seed }) { const rnd = generator(seed); const n = rate * WINDOW; const local = new Array(NODES).fill(0); let global = 0, lastGlobal = 0, lastSync = 0, accepted = 0, rejected = 0, touches = 0; for (let i = 0; i < n; i += 1) { const t = (i / rate), node = Math.floor(rnd() * NODES); if (arrangement === "delayed synchronization" && t - lastSync >= interval) { lastGlobal = global; lastSync = t; for (let j = 0; j < NODES; j += 1) local[j] = 0; } let allow; if (arrangement === "centralized") { touches += 1; allow = global < LIMIT; } else if (arrangement === "split quota") allow = local[node] < LIMIT / NODES; else allow = lastGlobal + local[node] < LIMIT; if (allow) { accepted += 1; global += 1; local[node] += 1; } else rejected += 1; } if (arrangement === "delayed synchronization") touches = NODES * Math.floor(WINDOW / interval); return { requests: n, accepted, rejected, touches, overshoot: Math.max(0, accepted - LIMIT) }; } const ARRANGEMENT = ["centralized", "split quota", "delayed synchronization"]; for (const rate of [10, 90]) { console.log(`\nclient rate ${rate}/s -> ${rate * WINDOW} requests, limit ${LIMIT}, ${NODES} nodes, seed 20260730`); console.log(`${"arrangement".padEnd(26)}${"accepted".padStart(11)}${"rejected".padStart(11)}${"overshoot".padStart(12)}` + `${"false rejects".padStart(16)}${"counter touches".padStart(18)}`); for (const a of ARRANGEMENT) { const r = run({ arrangement: a, rate, seed: 20260730 }); const falseRejects = rate * WINDOW <= LIMIT ? r.rejected : 0; console.log(`${a.padEnd(26)}${String(r.accepted).padStart(11)}${String(r.rejected).padStart(11)}` + `${String(r.overshoot).padStart(12)}${String(falseRejects).padStart(16)}${String(r.touches).padStart(18)}`); } } console.log(`\ndelayed synchronization, client rate 90/s (burst)`); console.log(`${"sync interval".padEnd(18)}${"accepted".padStart(11)}${"overshoot".padStart(12)}` + `${"overshoot ratio".padStart(18)}${"touches/s".padStart(12)}${"threshold 660".padStart(16)}`); for (const a of [0.2, 1, 2, 5]) { const r = run({ arrangement: "delayed synchronization", rate: 90, interval: a, seed: 20260730 }); console.log(`${`${a} s`.padEnd(18)}${String(r.accepted).padStart(11)}${String(r.overshoot).padStart(12)}` + `${`x${(r.accepted / LIMIT).toFixed(3)}`.padStart(18)}${(r.touches / WINDOW).toFixed(1).padStart(12)}` + `${(r.accepted <= LIMIT * 1.1 ? "passes" : "fails").padStart(16)}`); } ``` ``` client rate 10/s -> 600 requests, limit 600, 8 nodes, seed 20260730 arrangement accepted rejected overshoot false rejects counter touches centralized 600 0 0 0 600 split quota 575 25 0 25 0 delayed synchronization 600 0 0 0 2400 client rate 90/s -> 5400 requests, limit 600, 8 nodes, seed 20260730 arrangement accepted rejected overshoot false rejects counter touches centralized 600 4800 0 0 5400 split quota 600 4800 0 0 0 delayed synchronization 609 4791 9 0 2400 delayed synchronization, client rate 90/s (burst) sync interval accepted overshoot overshoot ratio touches/s threshold 660 0.2 s 609 9 x1.015 40.0 passes 1 s 630 30 x1.050 8.0 passes 2 s 720 120 x1.200 4.0 fails 5 s 900 300 x1.500 1.6 fails ``` The first table eliminates split quota. The client sits right at its limit, sending 600 requests and never exceeding it; even so, 25 of its requests are rejected — 4.17%. The reason is distribution imbalance: requests do not split evenly across the eight nodes, and a node that fills its share rejects while unused quota sits idle on other nodes. Splitting the quota does not split the limit — it splits the **right**. The second table prices out the centralized counter. Its overshoot is zero, that much is true; its cost is 40,000 counter touches per second at the peak edge, and even in this single-client model, its 5400 touches are more than double delayed synchronization's 2400. Delayed synchronization accepts 609, with an overshoot of 9. The third table chooses the parameter. As the synchronization interval grows, the overshoot grows: 1.015x at 0.2 seconds, 1.050x at 1 second, 1.200x at 2 seconds. Since the threshold is 1.1x, 1 second passes and 2 seconds does not. Counter touches shrink in the opposite direction: from 40 per second to 4. HS5's choice of 0.2 seconds is the intersection of these two curves, and if the threshold were tightened to 1.05x, the interval would be forced to stay at 0.2 seconds. ## Design, Failure Behavior, and What Is Sacrificed The decision point is the gateway: the portability rule from the Traffic Layer course's Gateway Offloading lesson applies here, because the client ID is a metadata field and the decision does not read the domain's input. The counter is held in the key–value store from the Scaling the Data Layer course's Store Types lesson; the key is the `(client, slice)` pair, the record is 48 bytes, and the time-to-live is 60 seconds. The component itself is the **throttling** from the Resilience and Reliability course's Throttling and Load Shedding lesson: it cuts off above a known rate and does not look at instantaneous capacity. **Deliberately unused pattern.** Queue-based load leveling (Application Layer and Service Interaction) is not used: queuing the excess request and processing it later turns the limit into a delay, whereas the component's contract is to reject. The failure scenario is the counter store going down. Per the third threshold, the limiter stays open: nodes decide using the last known shared view and only their own local counter. This approaches split quota's behavior, and during the outage, overshoot per client can climb as high as eightfold. What is sacrificed is in one sentence: this design does not zero out overshoot — it buys keeping it at 1.015x with 40 counter touches instead of 40,000. ## Summary - Fixed window let 1200 requests through in a sliding 60-second interval on a request pattern piled at the window boundary: exactly double the declared limit. - Token bucket let 659 through on the uniform flow (1.098x, exactly the bucket's capacity), but rejected 1473 of the 1800 requests from a client running intermittently right at the limit. - Sliding window counter stayed at 600 on all three patterns and rejected no valid request; its cost is 12 times the memory, 115.20 MB instead of 9.60 MB. - Split quota rejected 25 requests (4.17%) from a client sitting right at its limit because of distribution imbalance; splitting the quota splits the right. - The centralized counter's overshoot is zero, but it demands 40,000 touches per second at the peak edge; delayed synchronization gives a 1.015x overshoot at a 0.2-second interval with 40 touches per second. - The synchronization interval determines the threshold: 1.050x at 1 second (passes), 1.200x at 2 seconds (fails). ## Next Step In this case, the counter was guarding a threshold, and what was lost when the threshold was crossed was a request; the client resends. The next case asks the same counting problem where what is counted is **not recoverable**. There is a limited number of seats or stock items; a counter that counts two too many does not produce a rejected request — it produces an item sold that does not exist. The number to measure then is the oversell produced under contention, and a second number stands beside it: the valid request the same guard rejects.