Rate limiting

Rate limiting caps how many requests someone can make in a certain amount of time. It protects your services from getting overloaded or abused, and stops one heavy user from ruining things for everybody else.

Token buckets are a popular way to do it. Picture a bucket that holds up to 10 tokens and gets one more every second. Each request takes a token, and if the bucket's empty, the request gets rejected. Someone can send 10 requests all at once, but over time they can only average one a second.

With lots of servers, they all need to share the counts. A central store is accurate, but adds a network call to every request. Counting locally is fast, but people can go a bit over the limit. And checking and updating the count has to happen as one step, or requests arriving together can sneak through.

• Ask what you're limiting by: user, API key or IP address.
• Return a 429 with a Retry-After header.
• Talk about requests arriving together, and what happens when the store is down.

100 requests a minute per API key

A public API allows each API key 100 requests a minute, with short bursts allowed. It runs on 20 servers behind a load balancer.

1. Use a token bucket per key: capacity 100, refilling at 100 a minute, which is one token every 0.6 seconds.
2. Store each bucket in Redis as two values: tokens left and the last refill time. Any of the 20 servers can check any key.
3. On each request, compute how many tokens have refilled since last time, add them up to the cap, and take one if there's one available. Do it in a single Lua script so two servers can't both take the last token.
4. A key that's been quiet for an hour has a full bucket, so it can send 100 requests at once, then gets about one every 0.6 seconds.
5. When the bucket's empty, return 429 with Retry-After set to when the next token will arrive.
6. That's one Redis call per request. At 50,000 requests a second, shard the keys across a few Redis nodes.
7. If Redis is unreachable, the servers fall back to a local limit of 100 divided by 20 servers per key. It's rough, but it keeps some protection without causing an outage.

Things interviewers tend to ask once you've brought this up.

How would you limit by multiple things at once?

Check several buckets per request, like per key, per IP and per endpoint, and reject if any is empty. Order them so the cheapest check runs first.

How do you avoid a Redis call on every request?

Each server takes a small batch of tokens at a time and spends them locally. You'll occasionally go a little over, in exchange for far fewer calls.

What's wrong with a fixed window?

Someone can send 100 requests at 12:00:59 and 100 more at 12:01:00, which is 200 in two seconds. Sliding windows and token buckets smooth that out.

Where should the limiter live?

Usually at the API gateway or a shared middleware, so every service gets it for free. Expensive endpoints might add their own tighter limits.

• Keeping counts in each server's memory and calling it a global limit.
• Reading the count and then writing it in two steps, so concurrent requests slip through.
• Not saying what clients get back when they're limited.
• Not deciding what happens when the counter store goes down.
• Only limiting by IP when lots of real users can share one IP.

• Caching strategiesMake reads faster, and figure out what to do when data changes.
• WebhooksHow one system tells another that something happened.
• Consistency and the CAP theoremWhat happens when copies of your data can't agree.