Rate limiting & throttling

Four reasons to rate limit, and they need different limits

A rate limiter answers "may this request proceed right now?" in a few microseconds, before any expensive work happens. It looks like a small component and it is one of the highest-leverage ones in a design, because it is the only mechanism that lets a system choose what to drop instead of failing at random.

• Abuse and security. Credential stuffing, scraping, enumeration. 5 login attempts per account per 15 minutes turns an online brute force from hours into centuries.
• Fairness / multi-tenancy. One customer's runaway integration script must not consume the capacity everyone else paid for. This is the noisy-neighbour problem, and the limiter is the fix.
• Cost control. When a request costs real money downstream — an LLM call, an SMS, a third-party API billed per call — the limiter is a spend cap that works in real time rather than on the invoice.
• Cascading-failure protection. The subtle one. When a dependency slows down, in-flight requests pile up, threads and connections are exhausted, and a slow dependency becomes a total outage. A limiter bounds concurrency so the system sheds load at the edge instead of dying in the middle. It is the same family as circuit breakers and bulkheads: controlled failure beats uncontrolled.

Fixed window: the simplest one, and the burst it lets through

Keep a counter per key per wall-clock window: INCR user:42:1m with a TTL. Increment, compare to the limit, reject above it. One integer per active key, O(1), trivially correct-looking.

The flaw is at the boundary. With a limit of 100 per minute, a client sends 100 requests at 11:00:59 and 100 more at 11:01:00 — both windows are individually legal, and your service just took 200 requests in one second. Any fixed-window limiter permits a 2x burst across the boundary, and burst is precisely what you were trying to prevent. It also synchronises clients: everyone whose quota resets on the minute retries at the same instant.

Sliding window log: exact, and priced accordingly

Store the timestamp of every request in a sorted set per key. On each request, drop entries older than the window, count what's left, and admit if the count is under the limit. In Redis that is ZREMRANGEBYSCORE + ZCARD + ZADD in one Lua script.

It is perfectly accurate — no boundary artefact, no approximation. It is also the only algorithm here whose memory scales with your limit: 16-24 bytes per retained timestamp. At 5,000 requests per hour per key and 1 million active keys, that's roughly 100 GB of Redis, versus ~16 MB for a counter-based approach. Use it where the limit is small and precision matters — login attempts, OTP sends, password resets — and nowhere else.

Sliding window counter: the practical default

Keep two counters, the current window and the previous one, and weight the previous by how much of it still overlaps the trailing window. It costs two integers per key, has no boundary burst, and its error is bounded and small — it slightly over-counts when traffic is bursty and slightly under-counts when it's idle, on the assumption that the previous window's requests were uniformly distributed.

// state per key: { windowStart, count, prevCount } — two integers plus a boundary
function allow(state, now, limit, windowMs) {
  const windowStart = Math.floor(now / windowMs) * windowMs;

  if (windowStart !== state.windowStart) {
    // rolled into a new window. Only carry the count forward if the
    // previous window is literally the one before this — after a gap, it's stale.
    state.prevCount = windowStart - state.windowStart === windowMs ? state.count : 0;
    state.windowStart = windowStart;
    state.count = 0;
  }

  const elapsed = (now - windowStart) / windowMs;      // 0…1 through the current window
  const estimate = state.prevCount * (1 - elapsed) + state.count;

  if (estimate >= limit) return false;
  state.count += 1;
  return true;
}

Worked example at 100/minute: the client uses its full 100 in window 1. One second into window 2, elapsed = 0.017, so the estimate is 100 × 0.983 = 98.3 — only 2 requests get through, instead of the 100 a fixed window would have allowed. Halfway through window 2 the previous window is weighted at 0.5, so 50 more are admitted. The boundary burst is gone for the cost of one extra integer.

Token bucket: the one to reach for when bursts are legitimate

A bucket holds up to B tokens and refills at r tokens per second. Each request removes tokens (usually one; expensive endpoints can charge more). Empty bucket means reject. That single structure encodes two independent knobs that every other algorithm conflates: the sustained rate is r, and the burst tolerance is B.

class TokenBucket {
  constructor(capacity, refillPerSec) {
    this.capacity = capacity;
    this.refillPerSec = refillPerSec;
    this.tokens = capacity;
    this.updatedAt = Date.now();
  }

  // Lazy refill: no timers. Compute how many tokens accrued since last touch.
  // This is what makes the whole thing O(1) memory and O(1) time per key.
  take(cost = 1, now = Date.now()) {
    const elapsedSec = Math.max(0, now - this.updatedAt) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSec * this.refillPerSec);
    this.updatedAt = now;

    if (this.tokens >= cost) {
      this.tokens -= cost;
      return { allowed: true, remaining: Math.floor(this.tokens), retryAfter: 0 };
    }
    // Tell the client exactly how long until it can succeed — this is what
    // turns a 429 into cooperation instead of a retry storm.
    const deficit = cost - this.tokens;
    return { allowed: false, remaining: 0, retryAfter: Math.ceil(deficit / this.refillPerSec) };
  }
}

Two details that read as experience. Lazy refill — deriving tokens from elapsed time on access rather than running a timer — means a million idle keys cost nothing but their last-touched timestamp. And variable cost means one limiter can express "a search costs 1, a bulk export costs 50", which is how you protect a database from an endpoint that is 50x more expensive without inventing a second limiter.

Picking one

Where the limiter lives

The distributed problem: one limit, many nodes

A limiter is trivial on one box and interesting on fifty, because the counter is shared mutable state on the hot path of every request. Three approaches, and the tradeoff between them is the actual interview question.

If you do go to Redis, the operation must be atomic. This is wrong:

const n = await redis.incr(key);
if (n === 1) await redis.expire(key, 60); // crash between these two and the key never expires

A key that never expires is a key whose counter never resets — the user is banned forever. Do the whole read-modify-write in one round trip with a Lua script (Redis executes it atomically), which also collapses two RTTs into one:

-- KEYS[1] = bucket key, ARGV = now_ms, refill_per_sec, capacity, cost
-- Returns {allowed, tokens_remaining}. One round trip, atomic, no race.
local st   = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local now  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cap  = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local tokens = tonumber(st[1]) or cap
local ts     = tonumber(st[2]) or now
tokens = math.min(cap, tokens + ((now - ts) / 1000) * rate)

local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil((cap / rate) * 1000) + 1000)
return { allowed, tokens }

Choosing the key

Layer them rather than agonising over one. Per-IP at the edge catches the botnet; per-user at the gateway catches the runaway script; per-tenant catches the enterprise customer whose backfill job just woke up.

What you return, and how a good client behaves

A rejection is an API response, and its quality determines whether clients back off or hammer you harder.

• 429 Too Many Requests for a client exceeding its quota. Use 503 with Retry-After for server-side overload shedding — the distinction tells the client whether the problem is theirs or yours.
• Retry-After: 12 (seconds, or an HTTP date). The single most valuable header: it converts guesswork into a schedule. Compute it from the limiter itself, as the token-bucket code above does.
• Standard quota headers on every response, not just rejections — RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset. A well-behaved client slows down before it gets rejected, which is strictly better for both sides.
• Never 200 with an error body. Clients and their HTTP libraries key retry behaviour off the status code.

On the client side, plain exponential backoff is not enough: every client throttled at the same moment retries at the same moment, and the recovering service is knocked over by the herd it just created. You need jitter.

// "Full jitter": pick uniformly in [0, ceiling) rather than backing off to a fixed point.
// Ceilings here: 200, 400, 800, 1600, 3200, 6400, 12800, 20000 ms (capped).
function backoffDelay(attempt, baseMs = 200, capMs = 20000) {
  const ceiling = Math.min(capMs, baseMs * 2 ** attempt);
  return Math.floor(Math.random() * ceiling);
}

async function callWithRetry(fn, maxAttempts = 6) {
  for (let attempt = 0; ; attempt++) {
    const res = await fn();
    if (res.status !== 429 && res.status < 500) return res;
    if (attempt >= maxAttempts - 1) return res;

    // Trust the server's own estimate when it gives one — it knows the refill rate.
    const hinted = Number(res.headers.get("retry-after")) * 1000;
    const delay = Number.isFinite(hinted) && hinted > 0 ? hinted : backoffDelay(attempt);
    await new Promise((r) => setTimeout(r, delay));
  }
}

Two things this snippet gets right that most don't: it prefers the server's Retry-After over its own guess, and it caps the attempt count. Unbounded retries against a struggling service are an outage amplifier — the client's retry budget is part of the server's capacity planning, which is why mature systems also implement a circuit breaker that stops calling entirely after a failure threshold. Even with a server hint, add a small random offset if thousands of clients share the same reset instant.

Recognizing it in an unseen problem

• Signals: "public API", "prevent abuse", "free tier vs paid tier", "one customer is affecting others", "we got scraped", or any endpoint whose cost per call is measured in dollars. Also any design with a fan-out to a fragile third party.
• The naive design puts a counter in each app server's memory and calls it done — which silently means N times the intended limit, and resets on every deploy.
• Pick the algorithm from the traffic shape. Clients that legitimately batch → token bucket, so burst and rate are separate knobs. Smooth user-facing quotas → sliding window counter. Security-critical small limits → sliding window log, because exactness is the point and the memory cost is trivial at 5 events.
• Distinguishing it from load shedding and circuit breaking: rate limiting is about who gets to use capacity (fairness, per-key, mostly static); load shedding is about whether there is any capacity right now (health-based, global, dynamic); a circuit breaker is a client-side decision to stop calling a failing dependency. Real systems have all three and an interviewer will be pleased if you separate them.
• Always state the distributed answer. "Counters in Redis with a Lua script for atomicity, roughly half a millisecond added per request, fail open to a local bucket if Redis is unreachable" is the whole answer in one sentence.
• The pitfall to avoid: returning a bare 429 with no Retry-After. You have told a thousand clients to retry immediately and simultaneously, which is how a rate limiter causes the outage it exists to prevent.