Cruxly › System design › Scaling Building Blocks

Rate Limiting

protect the system, and the limit must be shared

A limit keeps one caller from consuming everyone's capacity. The algorithm choice is quick; the interesting parts are where the counter lives, what happens when the limiter itself is unavailable, and what you do with rejected traffic.

Decide what you are protecting first

Say which goal you're solving first.

Goal	Limit
Abuse, scraping	Per account and per IP, aggressive, long window
Fair sharing among tenants	Per-tenant quotas by plan: isolation, not a global cap
Protecting a dependency	A global limit sized to its capacity, plus a circuit breaker. Per-user limits don't stop a thousand well-behaved users
Cost control	Per-account quotas over hours or days

Limits stack: per-IP at the edge, per-account in the gateway, a concurrency cap before each expensive dependency. Name the layers.

The four algorithms

Two of the four win in practice.

Algorithm	State per user	What it gets wrong
Fixed window	1 counter	2× burst across the boundary: 100 at 10:00:59, 100 at 10:01:00
Sliding window log	1 timestamp per request	Exact, but 10,000 req/min = 10,000 timestamps per user
Sliding window counter	2 counters	A few percent error; almost always fine
Token bucket, the default	2 numbers: refill rate, bucket size	Nothing, for user-facing traffic

Only token bucket says "sustained 10/s, but a burst of 50 is fine" directly; a fixed window can't express it. Leaky bucket smooths the output to a constant rate, for a downstream that wants perfectly even flow.

Where the counter lives

The real design question; the algorithm is the warm-up.

Counter location	Verdict
Instance memory	Wrong. Twenty instances turn a limit of 100 into 2,000, and the multiplier changes with every autoscale. Only "works" if the load balancer pins each user to one instance; don't rely on that
Shared store (Redis), atomic increment	The answer. Check-and-increment in one atomic round trip: read-then-write races under exactly the concurrency a limiter exists for. Costs a sub-millisecond hop on every request; say so
Local counters, reconciled every ~1 s	Escape hatch at very high volume: bursts briefly overshoot, zero per-request cost. A trade you chose, not the default

:::key Store unreachable? You will be asked Fail open: an outage means unlimited traffic to everything behind it. Use for user-facing limits (availability wins). Fail closed: a blip takes the whole API down. Use when guarding an expensive downstream (cost and cascading failure win). Decide deliberately and say so. :::

What the client sees

Return 429 Too Many Requests with headers clients can act on:

HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 30
Retry-After: 30

Problem	What happens	Fix
No `Retry-After`	Clients retry in a tight loop: a self-inflicted DoS	Always send it
Thundering retry (most candidates miss it)	1,000 clients told `Retry-After: 30` return at the same instant, rebuilding the spike	Retry-After + exponential backoff + jitter, built into your SDK: you can't trust arbitrary clients
Shaping (queueing) instead of rejecting	Ties up connections; under sustained overload it only moves the failure	Reject with a clear retry signal

Throttling: slowing callers instead of rejecting them

Everything so far rejects: over the limit, you get a 429. There is a second answer, delay: hold the request and release it at a pace the system can take. The two are different tools, and the choice is about who is waiting and for how long.

	Reject (429)	Delay (queue, then serve)
Caller sees	An immediate answer, then decides	A slow success, or a timeout
Server holds	Nothing	A connection, memory and a queue slot per waiter
Fits	Interactive and user-facing traffic; anything with a short timeout	Batch jobs, webhooks, background syncs: callers who care about completion, not latency
Fails by	Clients that retry blindly	A queue longer than the caller's patience

Leaky-bucket shaping is the delay form: requests enter a bounded queue and drain at a constant rate, so a bursty caller becomes a steady one. The queue bound is the whole design. Worked arithmetic: drain at 100 requests per second with a 200-slot queue, and the last request waits two seconds. If callers time out at one second, every request past slot 100 is processed for nobody. Size the queue to rate x client timeout (here 100) and shed the rest at once. The AWS Builders' Library makes the same point: bound the queue by size and by age, and drop requests that are too old so the server can work on fresher ones. Stripe's rate-limiter post lets a caller burst above the steady rate for the same reason, because spikes such as flash sales are normal.

Throttling versus load shedding. Throttling is about whose traffic: this caller is over its share. Load shedding is about the server: whoever is calling, we are near overload, so some work must go. The AWS article frames the goal as keeping goodput, the work finished in time to be useful, flat as offered load rises, rather than collapsing. Stripe runs both layers: per-user request-rate and concurrency limiters, then a fleet-wide shedder that reserves capacity for critical methods (creating a charge) and rejects non-critical ones (listing charges) with a 503 first, and a last-resort worker-utilization shedder. Stripe's post ties 503 to its fleet-usage shedder; use 429 for "you are over your own limit" and 503 for "the service is overloaded", because keeping the two apart tells the client whether lowering its own rate will help.

Priorities and fairness. When something must go, pick it on purpose. The AWS article ranks the load balancer's health-check pings first, because a server that misses them is pulled from rotation and the fleet shrinks mid-overload, and it favours requests that finish an in-flight operation over ones that start new work. Then favour paid or critical traffic over batch. Google's overload chapter tags each request with a criticality (CRITICAL_PLUS down to SHEDDABLE) so the same rule applies across every service in a call chain. Fairness is the other axis: per-customer quotas can sum to more than capacity because customers rarely peak together, so shedding needs a rule for the moment they do.

What goes wrong: the retry storm. Rejection creates retries, and retries are more load at the worst moment. The SRE book (chapter 22) works the arithmetic: three retries, so four attempts, at each of three layers is 4 x 4 x 4 = 64 attempts on the database for one user action. The defences stack:

Randomized exponential backoff, so rejected clients do not return in lockstep.
A retry budget: Google's example allows each request at most three attempts, and retries only while they are under 10% of that client's traffic.
A distinct "overloaded, do not retry" answer for when many tasks are overloaded at once, so layers above stop multiplying.
Client-side throttling: a client that sees its requests running at twice what the backend accepted rejects some locally, without spending a round trip.

:::key Verified November 2026

IETF headers: the RateLimit header work (draft-ietf-httpapi-ratelimit-headers, revision 11, dated 23 May 2026) is still an Internet-Draft, not an RFC, and it expires 24 November 2026. It defines RateLimit-Policy (quota q, window w, quota unit qu, partition key pk) and RateLimit (remaining quota r, effective window t in seconds), both as structured fields. The RateLimit-Limit / RateLimit-Remaining / RateLimit-Reset names in the example above come from earlier drafts and are widely deployed but not standardized.
When Retry-After and RateLimit appear together, the draft says Retry-After takes precedence.
Treat the header names as a convention and document the ones your API uses.

:::

Further reading: Site Reliability Engineering, chapters 21 (Handling Overload) and 22 (Addressing Cascading Failures), and the AWS Builders' Library article "Using load shedding to avoid overload".

The traps

:::key Limiting the wrong identity: raise it unprompted Login has no authenticated account yet, so per-account limits can't apply. It needs two:

Per-IP stops one machine guessing many passwords. Alone, it blocks everyone behind a corporate NAT and misses credential stuffing from thousands of IPs.
Per-username stops a distributed attack on one account. A hard lock lets an attacker lock the victim out, so escalate instead: increasing delays, then a CAPTCHA or step-up challenge, with the user's known devices or IPs exempt.

:::

Trap	What it looks like	Fix
Uniform cost	One search costs 1,000× a profile fetch; both deduct one token	Weight by cost, or limit per endpoint class
No burst allowance	A strict per-second cap breaks five parallel requests on page load	Token bucket
Silent limiting	No 429, so clients can't tell a limit from a failure and retry forever	Always send an explicit 429
Internal callers	Your own batch job trips abuse protection at 3am	Their own, much higher limit

How to say it in the interview

"The counter can't live in instance memory — with twenty instances, a limit of 100 becomes a limit of 2000. It goes in a shared store with atomic increment, and I need an answer for what happens when that store is unreachable."

Checklist

Said what the limit protects: abuse, fairness, a dependency, or cost
Chose an algorithm and named its weakness
Put the counter in a shared store with an atomic operation
Decided fail-open vs fail-closed when the limiter store is down
Returned 429 with Retry-After and remaining-quota headers
Required jittered exponential backoff on the client
Chose the right identity, including the login-endpoint subtlety
Weighted the limit by request cost, or split limits per endpoint class
Chose between rejecting, delaying and shedding, and bounded any queue by the caller's timeout

Practice this interactively