9.7.5 — Rate Limiter

"Design a rate limiter: allow at most 100 requests per minute per user."

A customer is promised 100 requests a minute. They send 100 requests at 10:04:59, and another 100 at 10:05:01. Your counter resets at the top of the minute, so both batches are allowed, and your service has just taken 200 requests in two seconds from an account you told the sales team was capped at 100 a minute.

That is not a bug in the code. The code did exactly what a per-minute counter does. It is a bug in the choice of algorithm, and the whole first half of this problem is knowing which algorithm fails how, so you can pick one whose failure you can live with.

What the design has to do: for a given key, answer allow or reject right now, in microseconds, using a few bytes of memory, for millions of keys at once, and be able to tell a rejected caller when to come back.

1. Fixed window: the cheap one, and exactly how it breaks

Keep one counter per key per window of time.

class FixedWindow {
  #counts = new Map<string, { windowStart: number; count: number }>();

  constructor(private limit: number, private windowMs: number) {}

  allow(key: string, now: number): boolean {
    const windowStart = now - (now % this.windowMs);          // (1)
    const c = this.#counts.get(key);

    if (!c || c.windowStart !== windowStart) {                // (2)
      this.#counts.set(key, { windowStart, count: 1 });
      return true;
    }
    if (c.count >= this.limit) return false;                  // (3)
    c.count++;
    return true;
  }
}

(1) The window a timestamp belongs to is found by rounding down to a multiple of the window length. At 10:04:59.700 with a 60-second window, that gives 10:04:00. This is why the windows line up for everybody: they are cut from the clock, not from when each user first appeared.

(2) A key seen in a different window starts fresh at one. The old count is simply overwritten, so nothing needs cleaning up on a schedule.

(3) Over the limit, reject, and do not increment. Incrementing on rejection would be defensible if you wanted rejected requests to extend the penalty, and it is not what a limit of 100 per minute means.

It is one number per key and about as fast as anything can be. And here is the failure, precisely.

Figure 1 — The boundary burst. A per-window counter is blind to what happened just before the window started, so a caller who bunches requests against the seam gets double the intended rate for a moment. The effect is worst for exactly the caller you most want to limit, because it takes deliberate timing.

Two spans of a minute can each be inside the limit while a single span of a minute across the seam is at twice the limit. The counter is not measuring the thing you promised. It is measuring the thing that is cheap to measure.

So where is it still the right answer? Anywhere the limit is a rough guard rather than a promise. A cap on how often an internal job may call another internal service does not need to survive an adversary timing the seam, and one integer per key is worth a lot when the alternative costs more memory. What you must not do is ship it as a customer-facing limit without saying this, because a customer with a fast script will find the seam by accident within a week.

2. Sliding window log: exactly right, and you can afford it rarely

Store the timestamp of every request and count the ones inside the last minute.

class SlidingLog {
  #hits = new Map<string, number[]>();

  allow(key: string, now: number): boolean {
    const cutoff = now - this.windowMs;
    const hits = (this.#hits.get(key) ?? []).filter(t => t > cutoff);   // (1)
    if (hits.length >= this.limit) { this.#hits.set(key, hits); return false; }
    hits.push(now);                                                     // (2)
    this.#hits.set(key, hits);
    return true;
  }
}

(1) Drop everything older than the window, then count what is left. This is genuinely the definition of "100 in the last 60 seconds", evaluated at the exact instant of the request, with no approximation anywhere.

(2) A request that is allowed records its own timestamp, which is what makes the next check correct.

What it costs, with numbers. One timestamp is eight bytes. A key allowed 100 requests a minute holds up to 100 of them, which is 800 bytes plus the overhead of the array, so call it a kilobyte or two per key. A million active keys is a gigabyte or two of memory doing nothing but remembering timestamps. And the filter walks the list on every single request.

So it is the right answer when being exactly right is worth paying for. Metering that a customer is billed against is the usual case: if the invoice says 100,000 calls, the count behind it should not be an estimate. For deciding whether to serve the next HTTP request, it is a lot of memory for a precision nobody can perceive.

3. Sliding window counter: the one most gateways actually run

Keep two numbers instead of a list: this window's count and the previous window's count. Then estimate how many requests fall in the last sixty seconds by taking the whole current window plus a fraction of the previous one.

class SlidingWindowCounter {
  #windows = new Map<string, { start: number; curr: number; prev: number }>();

  allow(key: string, now: number): boolean {
    const start = now - (now % this.windowMs);
    let w = this.#windows.get(key);

    if (!w || w.start !== start) {                                       // (1)
      w = {
        start,
        prev: w && w.start === start - this.windowMs ? w.curr : 0,       // (2)
        curr: 0,
      };
      this.#windows.set(key, w);
    }

    const elapsed = (now - start) / this.windowMs;                       // (3)
    const estimate = w.curr + w.prev * (1 - elapsed);                    // (4)

    if (estimate >= this.limit) return false;
    w.curr++;
    return true;
  }
}

(1) A new window is entered lazily, on the first request that arrives in it. No timer fires at the top of every minute for every key, which matters when there are millions of keys.

(2) The window that just ended becomes prev, but only if it really was the immediately preceding one. A key that was idle for ten minutes has a stale window whose count must not be carried forward as if it were recent, and that condition is the line that handles it.

(3) How far into the current window we are, as a fraction between 0 and 1.

(4) The estimate. Fifteen seconds into a sixty-second window, one quarter has elapsed, so three quarters of the previous window is still inside the last sixty seconds and gets counted at 75%.

Worked. Limit is 100 a minute. The 10:04 window ended with 90 requests. It is now 10:05:15, and 20 requests have arrived in the new window.

estimate = 20 + 90 × 0.75 = 87.5

Under 100, so the request is allowed. Compare that with the fixed window, which would have said 20 and cheerfully accepted 80 more. The seam is smoothed, which is the entire reason this algorithm exists.

And here is what it gets wrong, which you should say without being asked. The estimate assumes the previous window's 90 requests were spread evenly across it. If all 90 actually arrived in its final second, at 10:04:59, then the true count for the last sixty seconds at 10:05:15 is 90 + 20 = 110, which is over the limit, and this algorithm says 87.5 and allows more. The error runs in the permissive direction for callers who bunch requests at the end of a window.

Two numbers per key, no list, seams smoothed, and a small error you can describe exactly. That combination is why this is the usual default in front of an API, and being able to state the error rather than just claiming it is small is what separates having read about it from having chosen it.

4. Token bucket: the one to reach for when a customer is reading the limit

The previous three answer "how many in the last period". Token bucket answers a different and often better question: how fast may you go, and how much may you save up?

A bucket holds up to capacity tokens and refills at rate tokens per second. Each request spends one. Empty means rejected.

interface Decision {                                                    // (1)
  allowed: boolean;
  remaining: number;
  retryAfterMs: number;
}

class TokenBucket {
  #buckets = new Map<string, { tokens: number; lastRefill: number }>();

  constructor(private capacity: number, private ratePerSec: number) {}

  take(key: string, now: number, cost = 1): Decision {                  // (2)
    const b = this.#buckets.get(key) ?? { tokens: this.capacity, lastRefill: now };  // (3)

    const elapsedSec = (now - b.lastRefill) / 1000;
    b.tokens = Math.min(this.capacity, b.tokens + elapsedSec * this.ratePerSec);     // (4)
    b.lastRefill = now;

    if (b.tokens < cost) {                                              // (5)
      this.#buckets.set(key, b);
      return {
        allowed: false,
        remaining: Math.floor(b.tokens),
        retryAfterMs: Math.ceil(((cost - b.tokens) / this.ratePerSec) * 1000),       // (6)
      };
    }

    b.tokens -= cost;
    this.#buckets.set(key, b);
    return { allowed: true, remaining: Math.floor(b.tokens), retryAfterMs: 0 };
  }
}

(1) The answer is not a boolean. A caller who is rejected needs to know when to come back, and a caller who is allowed benefits from knowing how much is left. Returning a boolean throws away information the algorithm already has, and the HTTP layer then has to guess at a Retry-After value.

(2) cost lets one request spend more than one token. An endpoint that runs an expensive report can charge ten, so a limit becomes a budget rather than a request count. This is a small parameter with a large effect: it lets one limit protect a service whose endpoints are wildly different in cost.

(3) A key never seen before starts full. A new customer's first request should not be rejected, and starting empty would do exactly that.

(4) This is the line that makes the whole thing practical. Tokens are not added by a timer. They are computed from elapsed time at the moment of the request. There is no background job refilling ten million buckets every second; there is one subtraction and one multiplication when a key is actually used. A key idle for an hour refills to full in a single multiplication the next time it appears. The Math.min against capacity is what stops an idle key from accumulating an unlimited allowance.

(5) Not enough tokens means rejected, and the bucket is still written back because the refill that just happened is real and should not be recomputed from a stale timestamp next time.

(6) The wait is arithmetic, not a guess. Needing cost - tokens more tokens at ratePerSec per second gives the exact time until the request would succeed. With 0.4 tokens, a cost of 1, and a rate of 10 per second, that is 60 milliseconds. A caller told to wait 60 milliseconds behaves; a caller told nothing retries immediately and makes everything worse.

The two knobs, and why they are the reason to choose this. capacity is how big a burst you tolerate. rate is the throughput you sustain. They are independent, and they map directly onto the two things a customer actually cares about: can I fire off my batch of 20 uploads, and what can I do all day. A limit expressed as "10 per second, bursts up to 50" is one a customer can plan against. A limit expressed as "600 per minute" tells them nothing about whether their batch will go through.

A worked minute. Capacity 20, rate 10 per second. The bucket starts full.

A batch of 20 requests arrives at once. All 20 are allowed, and the bucket is empty. This is the burst the capacity was for. The next request, 50 milliseconds later. Refill adds 0.5 tokens, which is less than 1, so it is rejected with retryAfterMs: 50. Nothing happens for 3 seconds. Refill would add 30 tokens, capped at 20, so the bucket is full again and another batch of 20 goes through.

Sustained, the caller gets 10 a second. In bursts, they get 20 at once. Both promises hold at the same time, from two numbers.

5. Leaky bucket, and why it is a different tool

Leaky bucket is often listed as a fifth algorithm and it is really a different job. Requests go into a queue that drains at a fixed rate, so the output is perfectly smooth no matter how lumpy the input was.

The difference from token bucket is one sentence: token bucket lets a burst through and leaky bucket flattens it. If what you are protecting is a downstream system that cannot take a spike at all, such as a device or a legacy service with a fixed thread count, flattening is what you want, and the cost is that requests wait in a queue rather than being told no. If what you are protecting is your own API from abuse, flattening is wrong, because real users legitimately act in bursts and making them wait is worse for them than letting the burst through.

Nginx's limit_req is a leaky bucket, which is why it is described as smoothing traffic rather than as limiting it. Reaching for it when the requirement says "shape" and for a token bucket when the requirement says "limit" is the whole of the choice.

6. Choosing, and the wrapper around whichever you chose

Algorithm	Memory per key	Failure to name	Use when
Fixed window	one counter	2× at the seam	rough internal caps
Sliding log	one timestamp per request	memory	billing-grade counts
Sliding counter	two counters	under-counts end-of-window bursts	general API gateway
Token bucket	two numbers	none in this list	customer-facing limits
Leaky bucket	queue	requests wait instead of failing	protecting fragile downstreams

The table compares them; the choice comes from one question. Is the requirement "N per period" or "R sustained with bursts of B"? The first three answer the first question, the buckets answer the second, and most customer-facing limits are really the second question asked badly.

Whichever one you picked, the code around it is the same:

interface RateLimiter {                                        // (1)
  take(key: string, now: number, cost?: number): Decision;
}

function rateLimit(limiter: RateLimiter): Middleware {
  return (req, res, next) => {
    const key = keyFor(req);                                   // (2)
    const d = limiter.take(key, Date.now(), costOf(req.route));

    res.setHeader("X-RateLimit-Limit", limiter.limit);         // (3)
    res.setHeader("X-RateLimit-Remaining", d.remaining);

    if (!d.allowed) {
      res.setHeader("Retry-After", Math.ceil(d.retryAfterMs / 1000));   // (4)
      return res.status(429).json({
        code: "RATE_LIMITED",
        scope: d.scope,                                        // (5)
        retryAfterMs: d.retryAfterMs,
      });
    }
    next();
  };
}

(1) One interface, several implementations, chosen per route or per tier. The algorithm is a decision that should be changeable without touching anything that calls it, and swapping a sliding counter for a token bucket on one endpoint should be a configuration change.

(2) Keying is a design decision in its own right and section 8 covers it.

(3) Headers on every response, not just rejections. A well-behaved client slows down before it is rejected if you tell it how much is left, and clients that do this are the ones you want to encourage.

(4) Retry-After is in seconds and is rounded up, because rounding down tells a client to retry slightly too early and get rejected again.

(5) The rejection body says which limit was hit. A customer who is rejected needs to know whether they hit their account's limit, a per-endpoint limit, or a global ceiling, because the fix is different for each. Returning a bare 429 generates a support ticket that could have been a line of JSON.

7. Time is a parameter, and which clock matters

Every method on this page takes now as an argument rather than calling Date.now() inside. That is not only about being able to drive time from outside; it also forces the question of which clock.

The wall clock can jump. A time sync correction, a daylight-saving change on a badly configured host, or a virtual machine resuming from a snapshot can move it forwards or backwards by seconds or more. A backwards jump makes elapsed negative, so a token bucket removes tokens it never granted and starts rejecting a customer who did nothing. A forwards jump refills every bucket to capacity at once and lets everybody burst.

The monotonic clock only ever moves forwards and is meant for measuring durations. In Node that is process.hrtime.bigint(). It has no relationship to calendar time, and it resets when the process restarts, both of which are fine here because a limiter only ever measures how long ago something happened.

So: durations use the monotonic clock, and anything a human will read uses the wall clock. Getting this backwards produces a limiter that is correct in testing and misbehaves once a quarter for reasons nobody can reproduce. The full comparison of the two clocks is in 10.3; the rule here is that a rate limiter is a duration measurement wearing a timestamp costume.

8. Keys, memory, and what happens with millions of them

Keying decides who shares a limit, and getting it wrong makes the limiter either useless or unfair.

By authenticated user or API key is the right default whenever you know who is calling. It is fair, it is what the customer's contract says, and it cannot be dodged by changing networks.

By IP address is the fallback before login, and it has a specific problem worth naming: a corporate office or a mobile carrier puts thousands of people behind one address, so a per-IP limit either punishes an entire building or is set so high that it stops nothing. Keep pre-login limits loose and push everything else onto an identity.

By IP and route together is what protects a login endpoint, because the thing you are stopping there is many attempts against many accounts from one place.

Memory is the part people forget. Each key holds a small object, and the map holds one per key that has been seen. Ten million distinct keys, most of them one-off IP addresses that will never appear again, is a map that grows until the process dies. The limiter needs a bound.

The correct bound is a cache with a size cap that discards whichever key was least recently used, because a key nobody has touched for an hour has a full bucket anyway and losing it costs nothing. That structure is the subject of the next page, and it is worth noticing that this page's design needs it: a rate limiter without eviction is a memory leak with a business justification.

9. What breaks when there are twelve copies of your service

Everything above lives in one process. Run twelve replicas behind a load balancer and each one keeps its own buckets, so a key limited to 100 a minute can do 1,200 a minute by being spread across all twelve. Nothing errors. The limit is simply not the limit any more, and the first person to notice is a customer whose script is running twelve times faster than their contract allows.

Four repairs, and they are not ranked, because which one is right depends on what the limit is for.

Shared state. Put the buckets in Redis and do the check-and-spend as one atomic script. This is correct, and the atomicity is the whole point: reading tokens and then writing them back as two round trips lets two replicas both read 1 token and both spend it, which is the same check-then-act race as everywhere else in this book. The cost is a network round trip on every request and a new hard dependency.

Route each key to one replica. If the load balancer sends everything for a given key to the same replica, the local bucket is the only bucket and it is exact. Free at request time, and it costs routing machinery and gets uncomfortable when one key is far busier than the others.

Split the quota. Give each replica limit ÷ 12. No coordination at all, and it is wrong whenever traffic is uneven: a customer whose requests happen to land on one replica gets a twelfth of what they paid for.

Local buckets plus periodic reconciliation. Cheap, approximately right, and it lets a burst through between syncs.

And one decision that must be made explicitly rather than discovered: what happens when the shared store is down? Failing open means every request is allowed and the limiter has stopped protecting anything, exactly during an incident. Failing closed means every request is rejected and the limiter has become the outage. Neither is universally right. An abuse limit should probably fail closed for unauthenticated traffic and open for known customers; a load-shedding limit should fail open, because its job is to protect a service that is currently fine. What is not acceptable is finding out which one your library chose during the incident.

The layered arrangement that gets used in practice is a cheap local limiter in front of an exact shared one. The local one is set generously, perhaps twice the real limit, and its job is to throw away obvious floods without paying for a network round trip. The shared one is the authority. The full service-scale version of this is 11.3; the reason it belongs here is that both stages run exactly the algorithm from section 4.

10. What the interviewer will push on

"Walk me through the algorithms and tell me which you would use." They are checking whether you have opinions with reasons, not whether you can list five names. Every algorithm should come with its failure: fixed window doubles at the seam, the log costs memory proportional to traffic, the sliding counter under-counts end-of-window bursts, leaky bucket makes requests wait instead of failing. The tell is the closing question — is the requirement "N per period" or "R sustained with bursts of B" — because that is what actually decides it.

"Show me the boundary burst with numbers." They want 100 at 10:04:59 and 100 at 10:05:01, and the observation that both windows counted correctly. The common wrong answer says fixed window is "less accurate", which is vague enough to be worthless. The specific version is that two valid windows can hold a single invalid minute across the seam.

"How do you refill millions of buckets?" You do not. Tokens are computed from elapsed time at the moment of the request, so a key idle for an hour costs one multiplication when it next appears and nothing before that. Candidates who describe a background timer have designed a system that spends all its CPU on keys nobody is using.

"A client gets a 429. What exactly do you send back?" They are checking whether the limiter returns information or a boolean. Status 429, Retry-After computed as (cost − tokens) / rate and rounded up, X-RateLimit-Remaining on every response rather than only on failures, and a body naming which limit was hit. The last one is the tell, because it only occurs to people who have supported an API and answered "why am I being limited" for a customer.

"You have twelve replicas. What is your actual limit?" Twelve times what you promised. Then the four repairs with their trades, and the follow-up that most people miss: what happens when the shared store is unreachable. Fail open and the limiter stops protecting during an incident; fail closed and the limiter causes one. Having decided this deliberately, per limit type, is the senior answer.

"Your limiter has been running for a week and the process is out of memory." One entry per key seen, most of them one-off addresses that will never return. The bound is a size-capped cache evicting the least recently used key, which is safe precisely because an untouched key has a full bucket and losing it costs nothing. This connects the two halves of what used to be one interview, and noticing the connection unprompted is worth a lot.

The thing to volunteer that nobody asks for: which clock. Wall-clock time can jump backwards on a time sync or a resumed virtual machine, which makes elapsed negative and takes away tokens a customer never spent, producing rejections nobody can reproduce. Durations belong on the monotonic clock. Almost nobody raises this, and it is a real production failure rather than a trivia point.

Recall

• Fixed window: one counter per key per window. Doubles the rate at the seam — 100 at 10:04:59 plus 100 at 10:05:01. Fine for rough internal caps only.
• Sliding log: every timestamp kept, exactly correct, memory grows with traffic. Worth it for billing-grade counts.
• Sliding counter: curr + prev × (1 − elapsed fraction). Two numbers, smooth seams, and it under-counts a burst crammed into the end of the previous window.
• Token bucket: capacity is the burst you tolerate, rate is what you sustain, and they are independent. Refill is lazy, computed from elapsed time at request time, so millions of idle keys cost nothing.
• A new key starts full, and Math.min against capacity stops idle keys accumulating forever.
• Retry-After is arithmetic: (cost − tokens) / rate, rounded up so the client does not come back too early.
• cost per request turns a request count into a budget, so an expensive endpoint can charge ten tokens.
• Leaky bucket shapes; token bucket admits. Use shaping to protect a fragile downstream, not to limit an API.
• Return a Decision, not a boolean: allowed, remaining, retry-after, and which limit was hit.
• Send X-RateLimit-* on every response so clients slow down before they are rejected.
• Durations use the monotonic clock. A wall-clock jump backwards makes elapsed time negative and removes tokens nobody spent.
• Key by identity where you have one. IP limits punish whole offices behind one address; keep pre-login limits loose.
• A limiter without eviction is a memory leak. Bound it with a size-capped least-recently-used cache, which is safe because an untouched key has a full bucket.
• Twelve replicas means twelve times the limit. Repairs: shared atomic store, route each key to one replica, split the quota, or reconcile periodically.
• Decide fail-open versus fail-closed before the incident, per limit type.

Self-test: Show the boundary burst with real times. State the sliding counter's error and its direction. Why is refill lazy, and what would a timer cost? Derive Retry-After. What are the two knobs and what does each promise a customer? What is the actual limit across twelve replicas, and what happens when Redis is down?

Quiz Bank

FoundationalCompare the rate-limiting algorithms, each with the failure that decides against it, and say how you would choose.

Fixed window. One counter per key per window, and the window is cut from the clock so everybody's windows line up. Cheapest possible: one integer per key, no cleanup, no scanning.

Its failure is exact rather than vague. A limit of 100 a minute allows 100 requests at 10:04:59 and another 100 at 10:05:01, which is 200 in two seconds. Both windows counted correctly; the windows were the wrong thing to count. It survives where the limit is a rough guard between internal services, and it should not be a customer-facing promise, because a customer with a fast script finds the seam by accident.

Sliding window log. Keep every request's timestamp, drop the ones older than the window, count what is left. This is the literal definition of "100 in the last 60 seconds" with no approximation.

Its failure is memory. One timestamp is eight bytes and a key can hold as many as its limit allows, so a million active keys is a gigabyte or two of nothing but timestamps, plus a list walk on every request. It earns that where being exactly right is worth paying for, which usually means metering a customer is billed against.

Sliding window counter. Two numbers per key: this window's count and the previous window's. Estimate the last sixty seconds as the current count plus a fraction of the previous, scaled by how much of the current window has not yet elapsed.

estimate = curr + prev × (1 − elapsed)

Fifteen seconds into a minute with 90 in the previous window and 20 so far: 20 + 90 × 0.75 = 87.5. The seam is smoothed and the memory is constant.

Its failure is a specific approximation in a specific direction. The formula assumes the previous window's requests were spread evenly. If all 90 arrived in its final second, the true count is 110 and the estimate says 87.5, so bursts crammed against the end of a window are under-counted and allowed. Being able to state that is the difference between having read about this and having chosen it. It is the usual default in front of an API.

Token bucket. Tokens up to a capacity, refilled at a rate, one (or cost) spent per request. Refill is computed from elapsed time at request time rather than by a timer.

It has no failure in the sense the others do; it has a different shape. It answers "how fast, and how much may you save up" instead of "how many in the last period", and those two knobs map onto what a customer actually cares about: can my batch of 20 go through, and what can I do all day. It also produces an exact Retry-After for free. This is the default for a limit a customer reads in documentation.

Leaky bucket. A queue draining at a fixed rate, so the output is perfectly smooth regardless of the input.

Its trade is that requests wait instead of being rejected. That is right when you are protecting something that cannot absorb a spike at all, and wrong for an API, because real users act in bursts and queuing them is worse for them than letting the burst through. Nginx's limit_req is this, which is why it is described as smoothing traffic.

How to choose, in one question. Is the requirement "N per period" or "R sustained with bursts of B"? The windows answer the first, the buckets answer the second, and most customer-facing limits are the second question asked in the language of the first.

AppliedImplement a token bucket and defend every line, including what you return to a rejected caller.

take(key: string, now: number, cost = 1): Decision {
  const b = this.#buckets.get(key) ?? { tokens: this.capacity, lastRefill: now };

  const elapsedSec = (now - b.lastRefill) / 1000;
  b.tokens = Math.min(this.capacity, b.tokens + elapsedSec * this.ratePerSec);
  b.lastRefill = now;

  if (b.tokens < cost) {
    this.#buckets.set(key, b);
    return {
      allowed: false,
      remaining: Math.floor(b.tokens),
      retryAfterMs: Math.ceil(((cost - b.tokens) / this.ratePerSec) * 1000),
    };
  }

  b.tokens -= cost;
  this.#buckets.set(key, b);
  return { allowed: true, remaining: Math.floor(b.tokens), retryAfterMs: 0 };
}

A new key starts full. A customer's very first request must not be rejected, and starting at zero would reject it.

The refill is the line that makes this deployable. Tokens are not added by a background job; they are computed from how much time has passed since this key was last touched. That means a service with ten million keys does zero work for the keys nobody is using. A timer-based refill would wake up every second and iterate ten million entries to add fractional tokens to buckets that are already full, which is a full CPU core spent on nothing. A key idle for an hour is brought fully up to date by one multiplication when it next appears.

Math.min against capacity is what stops an idle key from banking an unlimited allowance. Without it, a customer who goes quiet for a day comes back able to send 864,000 requests at once, which is not a burst allowance, it is an outage.

lastRefill is written even on rejection. The refill that just happened is real. Not writing it back means the next call recomputes elapsed time from a stale timestamp and grants the same tokens twice.

cost turns a request count into a budget. An endpoint that runs an expensive report charges ten tokens; a cheap read charges one. One limit then protects a service whose endpoints differ by orders of magnitude in what they cost you, without needing a separate limit per endpoint.

The return value is a Decision, and that is a deliberate choice over a boolean. The algorithm already knows how many tokens are left and exactly how long until the next one arrives. Throwing that away means the HTTP layer has to invent a Retry-After value, and invented values are either too short (the client comes back and is rejected again, doubling your load) or too long (the client waits pointlessly).

The wait is arithmetic, not a guess:

retryAfterMs = ceil((cost − tokens) / ratePerSec × 1000)

With 0.4 tokens, a cost of 1, and 10 tokens per second, that is 60 milliseconds. It is rounded up, because rounding down sends the client back a fraction too early to be served.

A worked minute, capacity 20, rate 10 per second, bucket starting full.

Twenty requests arrive at once. All allowed, bucket empty. That is what the capacity was for. One more, 50 ms later. Refill adds 0.5 tokens, still under 1, so rejected with a 50 ms retry. Three quiet seconds. Refill would add 30, capped at 20, so the bucket is full and another burst of 20 goes through.

Sustained, the caller gets 10 a second. In a burst, 20 at once. Both promises hold simultaneously from two numbers, and both are things a customer can plan against, which is why this algorithm is the one that appears in public API documentation.

InterviewYour limiter runs in a service with twelve replicas behind a load balancer. What is the real limit, and what are your options?

The real limit is twelve times what you promised. Each replica holds its own map of buckets and knows nothing about the others, so a key allowed 100 a minute can do 1,200 by having its requests spread across all twelve. Nothing errors and no log line appears. The limit is simply not the limit, and the first person to find out is a customer whose script is running twelve times faster than their contract.

It is worse than the arithmetic suggests, because balancing is not perfectly even. A caller whose requests happen to concentrate on three replicas gets a different effective limit from one spread across all twelve, so rejections look random to the client and are impossible for support to explain.

Option one: a shared store. Buckets live in Redis and the check-and-spend runs as one atomic script.

The atomicity is the whole point and it is worth saying why. Doing it as two round trips (read the tokens, then write them back) lets two replicas both read "1 token available" and both spend it, which is the same check-then-act race that puts two cars in one parking bay in 9.7.4. The read and the write have to be one indivisible step, which is what a server-side script gives you.

This is the correct option, and it costs a network round trip on every request plus a new hard dependency in the request path.

Option two: route each key to one replica. With consistent hashing at the load balancer, every request for a key lands on the same replica, so its local bucket is the only bucket and it is exact with no coordination at all. Costs routing machinery, and it goes wrong when one key is far busier than the rest, because that replica now carries a disproportionate load.

Option three: split the quota. Each replica enforces limit ÷ 12. Zero coordination, and it is wrong the moment traffic is uneven: a customer whose requests land mostly on one replica gets a twelfth of what they paid for and is rejected while eleven replicas sit on unused quota.

Option four: local buckets, periodic reconciliation. Each replica limits locally and they exchange counts every few seconds. Cheap, approximately right, and a burst can exceed the limit between syncs.

Which one depends on what the limit is for, and saying that is the answer rather than picking a favourite. A limit that appears in a contract, or one that stops abuse, needs option one's exactness. A limit whose job is shedding load to protect a service needs option four's cheapness, because being approximately right is entirely sufficient for that purpose.

In practice the answer is usually layered. A cheap local limiter, set generously at perhaps twice the real limit, throws away obvious floods without touching the network. Behind it, the shared atomic store is the authority. Most requests never reach the second stage, and the ones that do get an exact answer.

And the question nobody asks until it is too late: what happens when Redis is unreachable?

Fail open allows everything, so the limiter stops protecting anything, and it does so during an incident, which is when the protection mattered. Fail closed rejects everything, so the limiter becomes the outage.

Neither is universally right. An abuse limit should probably fail closed for unauthenticated traffic and open for known customers, on the grounds that the abusive traffic is the anonymous kind. A load-shedding limiter should fail open, because it exists to protect a service that is currently healthy. What is genuinely unacceptable is not knowing which your library chose, and finding out at three in the morning.

StaffDesign the rate-limiting layer for a public API with free, pro and enterprise tiers, per-endpoint overrides, and a requirement that limits change without a deploy.

Start with what a limit is, because the requirement is really about that. A limit is three things: a scope (which tier, which endpoint class, which kind of key), an algorithm, and its parameters. Written that way, "limits change without a deploy" stops being a feature request and becomes a statement that parameters are data.

The algorithm is token bucket everywhere that faces a customer, for one reason: its two knobs are the two things a customer can plan against. Free tier gets 10 per second with bursts to 20; enterprise gets 1,000 per second with bursts to 5,000. A customer reading that knows whether their nightly batch will go through. A limit written as "600 per minute" does not answer that question, which is why customers ask support instead.

Parameters live in a table, hot-reloaded, and every change is recorded with who made it. Tier and endpoint class map to bucket parameters. Changing enterprise from 1,000 to 1,500 is a row update, and the audit record matters because a limit change is a commercial commitment; six months later somebody will need to know who raised it and when.

Resolution order, defined and written down. A request may be covered by an endpoint override, a tier default, and a global ceiling all at once. The rule is that the most specific limit governs the answer, and every layer is still evaluated, so an enterprise customer with a generous tier limit still cannot exceed the global protection ceiling. Saying that all layers are checked, not merely the most specific, is the design; a system that stops at the first match has no ceiling at all.

Two enforcement stages. A local sliding-window counter per gateway process, set generously, sheds obvious floods with no network call. Behind it, an atomic token bucket in a shared store is the authority. The cheap stage removes most of the load from the expensive stage, and the expensive stage is what the customer's contract is measured against.

Keys. Authenticated traffic keys on the API key, which is per-customer and fair. Unauthenticated traffic keys on the address, with the caveat stated rather than discovered: an office or a mobile carrier puts thousands of people behind one address, so a per-address limit either punishes a whole building or is too loose to matter. Keep the pre-login limits loose, and make the interesting limits require an identity.

The HTTP contract, which is API surface and should be designed like it. Every response carries the limit and what is remaining, so a well-behaved client slows down before it is rejected. A rejection is 429 with Retry-After computed from the bucket, plus a body naming which scope tripped. That last field is what stops a support ticket, because "you hit your per-endpoint override on /reports" and "you hit your account limit" have completely different fixes.

Operating it. Three things need to be visible. Rejection rate per scope, alerting on changes rather than on levels, because a scope going from 2% to 100% rejected is nearly always a configuration mistake rather than an attack. A dry-run mode that logs what a new policy would have rejected before it enforces anything, because the first time you learn that a new limit rejects a third of your traffic should not be when it does. And an override for incidents, so a customer can be temporarily raised without a deploy, audited like every other change.

What I would deliberately not build here. Global coordination across regions. Each region enforcing its own limits means a customer using two regions can exceed the global number, and the correct response is to decide whether that matters commercially rather than to build cross-region consensus into the request path. For almost every API it does not matter, and the machinery to fix it costs more than the overage. Where it does matter, 11.3 is the design.

The shape, in one sentence: one algorithm chosen because its knobs mean something to a customer, parameters as audited data rather than code, two stages so the expensive one is rarely reached, and a rejection response a client can actually program against.

Flashcards

FlashThe boundary burst

100 requests at 10:04:59 and 100 at 10:05:01 pass a per-minute counter and are 200 in two seconds. Both windows counted correctly; windows were the wrong thing to count.

FlashSliding counter formula and its error

curr + prev × (1 − elapsed fraction). Two numbers per key, smooth seams. It assumes the previous window was evenly spread, so a burst crammed into its final second is under-counted and allowed.

FlashLazy refill

Tokens are computed from elapsed time when a key is used, not added by a timer. Ten million idle keys cost nothing, and a key idle for an hour catches up in one multiplication. Math.min against capacity stops unlimited banking.

FlashToken bucket's two knobs

Capacity is the burst you tolerate; rate is what you sustain. They are independent, and together they answer the only two questions a customer has: will my batch go through, and what can I do all day.

FlashRetry-After

ceil((cost − tokens) / ratePerSec), rounded up so the client does not return too early. Returning a Decision rather than a boolean is what makes this available instead of guessed.

FlashN replicas

Per-process buckets across twelve replicas allow twelve times the limit. Fix with a shared atomic store, key-to-replica routing, split quotas, or periodic reconciliation — and decide fail-open versus fail-closed before the store goes down.

Next: 9.7.30 — the LRU cache, which is both the classic data-structure interview and the exact thing this page needs to stop its key map growing forever.