Rate limiting & throttling

Four reasons to rate limit, and they need different limits

A rate limiter answers "may this request proceed right now?" in well under a millisecond, 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 caps an online guess against one account at about 480 a day. Note what that does not stop: credential stuffing is one or two tries on each of millions of accounts, so a per-account limit barely sees it (you need per-IP, per-device and breached-password signals, and MFA), and a hard per-account lockout hands attackers a way to lock real users out. Prefer a soft throttle or a challenge over a lockout.
• 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 as raw data, and a Redis sorted set costs several times that per element once it is large (skiplist plus hash table, on the order of 100 bytes; a planning figure). At 5,000 requests per hour per key and 1 million active keys, that's 5 billion timestamps: about 100 GB even at the raw size and plausibly several hundred GB in a sorted set, versus ~16 MB of raw counters (on the order of 100 MB once Redis's per-key overhead is counted) 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 and removes the boundary burst for ordinary traffic. It is an approximation: it assumes the previous window's requests were spread evenly. If they were bunched near the start of that window it over-counts and rejects a little early; if they were bunched at the end it under-counts and admits a little extra. Against an adversary that times it, the error is not small: 100 requests in the last instant of window 1, then about 99 at the very end of window 2 (when window 1's weight is near zero), puts nearly 200 inside one real trailing minute. On real traffic it is excellent: Cloudflare, which popularised it, measured 0.003% of 400 million requests wrongly allowed or limited, with a 6% average difference from the true rate.

// 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 about 50 have been admitted in total. 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.

Dry run: a token bucket (B = 10, r = 5/sec) under a burst of 12, then one more request

Two things fall out of this trace. First, B and r really are independent knobs: the client spends its entire burst allowance in the same millisecond, then is throttled to exactly one request every 200 ms (1/r) after that. Second, the retryAfter formula rounds up with Math.ceil, so it told the client to wait a full second when only 200 ms of refill was actually needed — conservative by design, since telling a client to retry too early just produces another rejection.

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 in one round trip). For a plain fixed-window counter you do not even need Lua: INCR followed by EXPIRE key 60 NX (the NX option exists since Redis 7.0, and sets the expiry only if none is set) inside one MULTI/EXEC or pipeline is also atomic. The token-bucket script below needs Lua because it reads, computes and writes:

-- KEYS[1] = bucket key, ARGV = refill_per_sec, capacity, cost
-- Returns {allowed, tokens_remaining}. One round trip, atomic, no race.
local st   = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
-- Time comes from Redis, not the caller: client clocks skew, and a client
-- that sends a far-future "now" would refill its own bucket. (TIME inside
-- scripts needs Redis 5+.)
local t    = redis.call('TIME')
local now  = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local rate = tonumber(ARGV[1])
local cap  = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])

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

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

redis.call('HSET', 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.
• Quota headers on every response, not just rejections. The IETF's draft-ietf-httpapi-ratelimit-headers (revision 11, May 2026) is still an Internet-Draft, not an RFC; it defines RateLimit and RateLimit-Policy. The older trio RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset (and the X-RateLimit-* variants) is widely deployed but not a standard, so document whichever you pick. A well-behaved client slows down before it gets rejected, which is strictly better for both sides.
• Hard versus soft limits. A hard limit rejects. A soft limit lets the request through but queues it, degrades it, or marks it low priority. Decide per limiter which one a breach deserves.
• 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.

Retries also compound across layers. If each of three layers makes up to 3 attempts (2 retries), one user action can become 3 × 3 × 3 = 27 calls at the bottom; the Google SRE book's "3 retries" example is 4 × 4 × 4 = 64. Two defences from the SRE book: a per-client retry budget (retry only while retries are under about 10% of your requests, which holds the amplification near 1.1x instead of nearly 3x), and client-side adaptive throttling (once requests exceed K times the accepted count over a two-minute window, K = 2 by default, start rejecting locally with rising probability). Both make the client part of the limiter.

Limit concurrency, not just rate

A rate limit bounds arrivals; it does not bound work in flight. Little's law says in-flight requests = arrival rate × latency. At 200 requests/s and 250 ms each, about 50 are in flight. Let the dependency slow to 5 seconds and the same 200/s means 1,000 in flight, with exhausted threads and connection pools, while the rate limiter happily reports that nobody exceeded their quota. That is why Stripe, in its published write-up, runs four mechanisms rather than one: a request-rate limiter, a concurrent-requests limiter (cap on in-progress requests per user), and two load shedders (one reserving fleet capacity for critical endpoints, one dropping lower-priority traffic when workers are saturated). Cost-based limits (charging tokens by estimated work, as the variable-cost bucket above does) and request criticality (the SRE book tags requests from CRITICAL_PLUS down to SHEDDABLE so overload sheds the least important first) are the same idea at finer grain.

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.