Rate Limiter

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

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

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

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