Step 2 of 14 · 1 min

What rate limits are for

Rate limits do several different jobs, and it helps to know which one you're doing, because they lead to different limits:

• Protecting capacity. No single caller, buggy or malicious, should be able to use up resources everyone needs. The partner's loop was this.
• Fairness. Paying customers, free users and internal tools each get a fair share, rather than whoever sends fastest getting most.
• Stopping abuse. Sign-up spam, password guessing, scraping (lesson 4.3), mass messaging. Here, limits are about what a legitimate user could plausibly do: nobody honestly creates fifty accounts an hour, or tries two hundred passwords a minute.
• Controlling cost. Some requests cost real money: sending an SMS code, calling a paid third-party API, running an expensive search.

Rate limiting is related to load shedding (lesson 6.1), but they're different. Load shedding happens when a service is already overloaded, and rejects whatever it must to survive. Rate limiting happens before that, and rejects a specific caller who has used up their allowance, even if the service has plenty of room.

Step 3 of 14 · 2 min

The algorithms

All rate limiters answer the same question, "may this request go ahead?", by keeping a small amount of state per caller. They differ in how they treat bursts and how accurate they are.

Fixed window

Count requests in fixed blocks of time: "100 requests per minute," counting from 10:00:00 to 10:00:59, then resetting at 10:01:00.

INCR rl:user:4821:10:00      → 37
EXPIRE rl:user:4821:10:00 60

It's the simplest possible limiter: one counter per caller per window, which is cheap to store and easy to understand. Its weakness is the boundary between windows. A caller can send 100 requests at 10:00:59 and another 100 at 10:01:00, which is 200 requests in two seconds, twice the intended rate, without breaking the rule.

Sliding window

Fix the boundary problem by always looking at the last 60 seconds, whenever "now" is.

The exact version keeps a timestamp for every request in the last minute (a sliding log) and counts them. It's precise, but it stores one entry per request, which gets expensive for high limits.

The common practical version, the sliding window counter, keeps just two numbers: the count for the current fixed window and the previous one, and estimates the last 60 seconds by weighting them. If we're 15 seconds into the current minute, the estimate is:

current window count + previous window count × (45 / 60)

It assumes requests in the previous window were spread evenly, which isn't exact, but it's close, needs only two counters, and removes the double burst at the boundary.

Token bucket

The most widely used algorithm, and the most flexible. Picture a bucket that holds tokens:

• The bucket holds at most B tokens (the burst size).
• Tokens are added at a steady rate, R per second, until the bucket is full.
• Each request takes one token. If there's no token, the request is rejected.

So a caller can burst up to B requests at once, after being quiet for a while, but over time can't average more than R a second. That matches real behaviour well: an app opening up fires off a burst of requests, then goes quiet.

You don't need a timer adding tokens. Store just two numbers per caller (the token count and the time it was last updated) and, on each request, add however many tokens would have accumulated since then:

tokens = min(B, tokens + (now − last_update) × R)
if tokens ≥ 1: tokens -= 1, allow
else: reject

A close cousin, the leaky bucket, smooths requests out to a steady rate instead of allowing bursts, which suits things like sending to an outside API that can't cope with spikes. (Another formulation you might see, GCRA, gives the same behaviour as a token bucket with just one stored number.)

Chirp used token buckets almost everywhere, and a sliding window counter for limits measured over long periods ("at most 5 accounts per device per day").

Step 4 of 14 · 2 min

Who to limit

The algorithm is the easy part. The hard part is choosing what you're counting: the key the limit applies to.

Not just by IP address

The obvious key is the client's IP address. It's what Chirp reached for first, and it went badly, for two reasons:

• Many people can share one IP. Mobile networks in India, and in many other countries, use carrier-grade NAT: thousands of phones share a small pool of public IPv4 addresses. A limit of 100 requests a minute per IP becomes 100 a minute shared between everyone behind that address. Offices, universities and public Wi-Fi do the same on a smaller scale.
• One person can have many IPs. The spammer ran their script from hundreds of cloud servers, each with its own address, staying under the limit on every one. With IPv6, a single home connection can have billions of addresses, so IPv6 limits are usually applied to a whole block (such as a /64) rather than a single address.

IP-based limits are still useful as a rough first line of defence (for unauthenticated requests, like login and sign-up), but with generous limits, and combined with other keys.

Better keys

• The account, for anything a logged-in user does: posting, liking, following. This is the fairest key for normal usage.
• The API key or partner, for integrations. The scores website's loop would have been stopped by a per-partner limit within a second.
• The device, for sign-ups and logins from the app, using a device identifier the app sends (imperfect, since it can be faked, but it raises the effort).
• The target, for attacks aimed at one thing: limit login attempts per account being logged into, regardless of who's trying, so a password-guessing attack spread across many IPs still hits a wall.
• Combinations, like "per account per endpoint" or "per IP block per hour for sign-ups."

Different limits for different things

One number for everything doesn't make sense. Chirp ended up with limits by endpoint and by cost:

Some systems go a step further and make limits cost-based: each request uses up tokens in proportion to how expensive it is, so a complex search costs 10 tokens and a profile lookup costs 1.

Step 5 of 14 · 1 min

Telling callers what happened

When a request is limited, say so clearly, so well-behaved clients can slow down:

• Return 429 Too Many Requests.
• Include Retry-After, saying how many seconds until a retry will work.
• Optionally, tell clients their limits and remaining allowance in headers on every response. There's an IETF draft standardizing headers for this (RateLimit and RateLimit-Policy), and many APIs use similar ones already.

On the client side, Chirp's own apps treat a 429 like lesson 1.5's retryable errors: wait as long as Retry-After says (with jitter), and never retry immediately in a loop. That's important, because a client that hammers on a 429 is just generating more requests to reject.

For abuse limits, sometimes the right response isn't a clear 429. Telling a spammer exactly where the limit is helps them stay just under it. Chirp's sign-up limits respond with a challenge (a CAPTCHA) or silently put new accounts into a "needs review" state instead.

Step 6 of 14 · 2 min

Limiting across many servers

A limit of "30 posts an hour per account" has to hold across every API server in every region. If each server counted on its own, an account would get 30 per server, which was lesson 2.1's per-server-counter bug.

A shared store

The usual approach keeps limiter state in Redis (lesson 2.4). The fixed-window counter is just INCR plus EXPIRE. A token bucket needs a read, a calculation and a write, which must happen together so two servers don't both take the last token. A small Lua script run inside Redis does all three atomically, because Redis runs each script without interruption.

That adds a Redis round trip to every limited request. Within a region, it's well under a millisecond. Fine.

At very high volume

For limits with huge traffic (a partner allowed 200 requests a second, spread across 50 servers), checking a shared counter on every request becomes its own hot key (lesson 4.5). Common approximations:

• Split the allowance: each of 50 servers allows 4 a second locally, with no shared state. It's imprecise if traffic is uneven between servers, but costs nothing.
• Check locally, sync periodically: each server keeps a local token bucket and synchronizes with the shared count every few hundred milliseconds. Briefly exceeding the limit by a little is the price of not making every request wait for Redis.

Most limits don't need to be exact. A limit of 30 posts an hour that occasionally allows 31 does its job perfectly well.

When the limiter fails

Every limiter needs an answer to: what happens if Redis is down?

• Fail open: allow requests when the limiter can't decide. Chirp is briefly unprotected, but users aren't affected. Right for most limits, which protect against rare problems.
• Fail closed: reject requests when the limiter can't decide. Safe, but now a limiter outage is a full outage. Right only where an unlimited burst would be worse than an error: sending SMS codes (cost) and login attempts (security).

Either way, put a short timeout on the limiter call (lesson 6.1), so a slow Redis doesn't slow down everything.

Step 7 of 14 · 1 min

Where limits live

Limits can be checked at several layers, and large systems use more than one:

• At the edge: the CDN or a web application firewall (lesson 2.3) can apply crude limits, per IP block, before traffic reaches your servers at all. Good for absorbing floods cheaply.
• At the API gateway: per account, per partner, per endpoint, with the identity information the edge doesn't have.
• Inside services: limits on expensive internal operations, and fairness between internal callers.

Chirp applied coarse IP-block limits at the CDN, account and partner limits at its API gateway, and specific business limits (like follows per day) inside the services that understood them.

Step 8 of 14 · 1 min

From the real world: 1.35 terabits per second

Rate limiting in your application protects against clients who send too much. It can't protect against traffic big enough to fill your network links before it reaches any code. GitHub's experience on 28 February 2018 shows where that line is.

At 17:21 UTC, GitHub was hit by what was, at the time, the largest DDoS attack publicly recorded: 1.35 terabits per second, at 126.9 million packets per second. It used memcached amplification. Tens of thousands of memcached servers had been left reachable on the internet with UDP enabled. The attacker sent them small requests with GitHub's address forged as the sender. Memcached answered each tiny request with a far larger response (amplification factors up to around 50,000× were reported), and all those responses went to GitHub.

GitHub's monitoring detected the anomaly, and within minutes GitHub moved its traffic to Akamai Prolexic, a scrubbing service whose network is large enough to absorb that volume and filter out the attack. GitHub was intermittently unavailable for about ten minutes, between 17:21 and 17:30 UTC.

The layers are the lesson:

• Volumetric attacks are stopped upstream, by networks bigger than the attack: scrubbing services, CDNs, cloud providers' DDoS protection. Your own servers never see most of it.
• Rate limits in your app handle what gets through: credential stuffing, scraping, abusive clients, bugs that loop. Those are well below link capacity and need per-user, per-key or per-IP decisions only your app can make.
• Don't be the amplifier. Memcached, DNS resolvers and NTP servers exposed to the internet over UDP are the raw material for these attacks. Chirp's internal Redis and memcached should never be reachable from outside.

Step 9 of 14 · 1 min

Going deeper: GCRA, a rate limit stored as one timestamp

The token bucket is the usual algorithm, but storing it means keeping two values per key (tokens left, last refill time) and doing a little arithmetic on both. The generic cell rate algorithm (GCRA), from ATM networks in the 1990s, gives exactly the same behaviour while storing one number per key. Stripe-style limiters and libraries like redis-cell use it.

GCRA thinks in terms of a schedule. With a limit of 10 requests a second, requests are "due" every 100 ms; that's the emission interval, T. For each key, store a single timestamp: the theoretical arrival time (TAT), when the next request would be exactly on schedule. A burst allowance lets requests run ahead of schedule by up to some limit, τ (for a burst of 5, τ = 5 × T = 500 ms).

For each request arriving at time now:

new_tat = max(now, tat) + T
if new_tat - now > τ:      reject, retry after (new_tat - now - τ)
else:                       tat = new_tat; allow

That's it. A client that sends steadily at the limit keeps TAT just ahead of now. A burst pushes TAT forward, and once it's more than τ ahead, requests are rejected until time catches up. There are no windows to reset, no background refill and nothing to expire except the key itself (which can expire at TAT). In Redis it's one small Lua script or one call to CL.THROTTLE, and a single atomic operation per request is what makes it safe across many servers.

Step 10 of 14 · 1 min

What Chirp changed

• Token buckets per account for reads and writes, and sliding window counters for daily limits, stored in Redis with Lua scripts.
• Per-partner limits, set in each partner's contract.
• Sign-up and login limits keyed by device, account and IP block, never by single IPv4 address alone.
• Limits were tuned using real usage data: each one set well above what genuine heavy users do.
• 429 with Retry-After, and limit headers on partner APIs. Chirp's apps back off properly.
• Fail open for most limits, fail closed for SMS and login attempts, with a 5 ms timeout on limiter calls.
• Coarse limits at the CDN edge, detailed ones at the gateway and in services.

The next spam wave created 61 accounts before hitting device and IP-block limits, and those 61 were caught by review. The partner's next bug was stopped within a second, and their on-call engineer got a clear 429 with a header explaining why.

Step 11 of 14 · 1 min

In the simulation

Stage 5 sends three kinds of trouble at Chirp: a scripted sign-up wave, a partner integration in a loop, and a crowd of real users behind shared mobile IPs. The simulation tracks blocked attackers, blocked innocent users, and the load each lets through. A single per-IP limit does badly on two of the three.

Open the simulation →

Step 12 of 14 · 1 min

If you're here for an interview

"Design a rate limiter" is one of the most common system design questions. A strong answer:

• Starts with requirements: what's being protected, which keys, how strict, what happens on the limit.
• Compares algorithms: fixed window (simple, boundary bursts), sliding window (smooth), token bucket (bursts plus a sustained rate), and picks one with a reason.
• Makes it distributed: shared state in Redis with atomic updates (a Lua script), or local limits with periodic syncing at very high volume.
• Handles failure: fail open or closed, and a timeout on the limiter.
• Communicates: 429, Retry-After, and clients that back off.

Mentioning that IP-based limits hurt users behind shared IPs (common on mobile networks) is a detail that stands out.

Step 13 of 14 · 2 min

Try these yourself

Step 14 of 14 · 1 min

Further reading

• Stripe Engineering, "Scaling your API with rate limiters," a clear practical account of several limiter types used together.
• The IETF draft "RateLimit header fields for HTTP."
• Redis documentation on scripting with Lua, and on atomicity.
• Cloudflare's blog posts on rate limiting at the edge, and on the sliding window counter approximation.
• Sam Kottler, "February 28th DDoS Incident Report," GitHub blog, March 2018.
• Brandur Leach, "Rate Limiting, Cells, and GCRA," 2015, and the redis-cell module's README.