Rate Limiting

The problem: one client slows the API for everyone

Say your users send about 1,000 requests a second and your app servers can answer about 1,500. Then one client, a buggy script stuck in a loop or a scraper, starts sending 1,000 a second on its own: 2,000 a second arrive, and every page slows down.

Adding servers only pays for the loop, and blocking the script's address is all or nothing. Rate limiting is the general fix: each client gets a rate, say 10 requests a second, and every request over it is refused at once with 429 Too Many Requests. The script gets 10 a second, the other 990 are refused, and the app sees about 1,010 a second.

Who counts as a client

Count by who the client is whenever the request says: its API key or the signed-in user ID. Fall back to the IP address only for signed-out traffic, with a looser limit, since one address can be a whole office or a phone network. GitHub's REST API is a well-known example: 60 requests an hour without a token, counted by IP address, and 5,000 an hour for each signed-in user.

How it works: three rules on one timeline

To follow every request, use a small limit: 5 requests a minute. One client sends 15 requests in three bursts:

time   requests
0:59   5
1:00   5
1:35   5

Fixed window

The simplest limiter keeps one counter per client for each minute on the clock; a request past 5 gets 429, and when the minute changes a new counter starts at 0. At 0:59 the counter for 0:00–0:59 goes up to 5 and all 5 get through. At 1:00 the counter for 1:00–1:59 starts at 0, so 5 more get through: 10 requests in about one second, 2× the limit. At 1:35 that minute's counter is full, so all 5 get 429.

Sliding window

A sliding window log keeps the time of each request it lets through and counts those in the last 60 seconds, whatever the clock shows. At 1:00 the last 60 seconds still hold the five from 0:59, so all 5 new requests get 429, and at 1:35 those five are still inside: nothing more gets through until 1:59. The log is exact, but it stores a time per request: with a limit of 1,000 a minute, up to 1,000 per client. At about 8 bytes a time, 1 million clients need about 8 GB.

The cheaper sliding window counter keeps two counts and estimates: this minute's count, plus last minute's count times the share of last minute still inside the window. At 1:35, 25 of last minute's 60 seconds are inside, so the estimate starts at 5 × 25/60 ≈ 2.1; two more requests bring it to about 4.1, a third would pass 5, so 2 of the 5 get through. It assumes last minute's requests were spread evenly (all five came at 0:59), but for most APIs it is close enough.

Token bucket

A token bucket gives each client up to 5 tokens, refilled at a steady 1 token every 12 seconds (5 a minute). Each request takes a token; with none left, it gets 429. It stores two numbers per client, the tokens and when it last refilled:

def allow(bucket, now):
    bucket.tokens = min(5, bucket.tokens + (now - bucket.last) / 12)
    bucket.last = now
    if bucket.tokens >= 1:
        bucket.tokens -= 1
        return True
    return False

The bucket is full before 0:59, so all 5 requests at 0:59 get through and it is empty. At 1:00 it holds a twelfth of a token, so all 5 get 429: a new minute changes nothing. The 429s take no tokens, so at 1:35, 36 seconds after it emptied, it holds 3: the first 3 requests get through and the last 2 get 429. A burst of up to 5, then a steady 1 every 12 seconds.

The whole run

time    sent   fixed   log   counter   bucket
0:59    5      5       5     5         5
1:00    5      5       0     0         0
1:35    5      0       0     2         3
total   15     10      5     7         8

Choosing a rule: the trade-offs

• Fixed window: one counter per client, the least work, but up to 2× the limit around each edge.
• Sliding window log: exact; memory grows with the limit.
• Sliding window counter: two counters, close to exact; a common middle ground.
• Token bucket: two numbers per client (about 16 bytes, 16 MB for 1 million clients). Short bursts pass (a page load fires several calls at once) and the average holds; the bucket size sets the burst, the refill sets the rate. A common default: Amazon API Gateway, for one, documents that it throttles with a token bucket.
• Leaky bucket: requests join a queue that drains at a fixed rate; a full queue refuses. Perfectly smooth, but a burst waits instead of passing. nginx describes its request limiting this way.

Where the limiter runs and what the client sees

Put the limiter in front of the app: in the API gateway or a reverse proxy, or in middleware that runs before your code, so a refused request costs a quick check and never reaches an app server. Each key's limit comes from its plan, say 10 requests a second for free keys and 100 for paid ones. The refused client gets a 429 that says when to try again:

HTTP/1.1 429 Too Many Requests
Retry-After: 12
Content-Type: application/json

{"error": "rate_limited", "retry_after": 12}

Retry-After counts the seconds until a token is back: the bucket emptied at 1:35, so the next token comes at 1:47. Many APIs also send headers such as X-RateLimit-Remaining. A good client waits as long as Retry-After says and, if refused again, backs off, waiting longer after each 429.

Across many servers

At busy hours the gateway runs on several servers behind a load balancer. If each server keeps its own counts, a key with a limit of 10 a second gets 10 through each: with 3 servers, 30 a second. A third of the limit per server breaks when one client's requests land unevenly. Counts in the main database put a write on every request, even refused ones, so the flood lands on a database that handles about 5,000 simple lookups a second.

The usual answer is one shared count per key in a fast in-memory store such as Redis (one cache server answers about 100,000 operations a second), updated atomically so two servers never both take the last token. The Rate Limiter design lesson builds this.

Where it shows up in design interviews

Rate limiting comes up as a question of its own and as one line in almost every API design. Say four things: the limit and the key (10 a second per API key, by IP when signed out), the algorithm and why (a token bucket: short bursts pass, the average holds), where it runs (the gateway, counts in a shared in-memory store), and what a refused client gets (429 with Retry-After).

Common interview questions

Token bucket or sliding window: which would you choose?

A token bucket for most APIs: two numbers per client, short bursts, a steady average. A sliding window when the limit must hold in every window, such as sign-in attempts.

What should the API return when a client is over its limit?

429 Too Many Requests, with Retry-After saying how many seconds to wait. A good client waits that long, then backs off if it is refused again.

How do you rate limit across many servers?

Keep each key's count in one shared in-memory store that every server updates atomically. Counting on each server alone lets N servers pass N times the limit.

Summary

• Rate limiting gives each client a rate, by API key or user (IP when signed out), and answers the rest with 429.
• A fixed window is simple but lets 2× the limit through at the edge.
• A sliding window counts the last 60 seconds: exact with a log, close with two counters.
• A token bucket allows bursts up to its size, then the steady rate, with two numbers per client.
• Run it in the gateway, send Retry-After, share counts in memory across servers.