API Rate Limiter

What is being asked

Protect an API from abuse and overload by allowing each client only so many requests per window, for example 100 a minute. The limiter sits in front of the services, must add almost no latency, and must give the same answer whichever server a request lands on.

Requirements

Functional

• Limit by a chosen key: API key, user id, or IP address.
• Support different limits for different endpoints and plans.
• Reject excess requests with HTTP 429 and tell the client when to retry.

Non-functional

• A decision in about a millisecond.
• Correct across dozens of gateway instances.
• If the limiter's own store fails, the API must keep working.

Design

1. The gateway works out the key for the request (say user:42:/orders) and looks up the limit that applies.
2. It asks Redis to take one token for that key. The check and the update run as a single atomic step, a short Lua script, so two gateways cannot both spend the last token.
3. If a token was available the request goes through; otherwise the gateway answers 429 with a Retry-After header.
4. Limits are read from a configuration service and cached in each gateway, so changing a plan's limit needs no deployment.

Choice of algorithm

• Token bucket: each key has a bucket that refills at a steady rate. It allows short bursts and stores just two numbers per key. This is the usual choice.
• Fixed window counter: simplest, but a client can send double the limit across a window boundary.
• Sliding window log: exact, but stores a timestamp per request, which is costly for busy keys.
• Sliding window counter: weights the previous window's count; nearly exact for little memory.

Key decisions and trade-offs

• Central store or local counters. Counting in Redis is accurate but costs a network round trip. Counting locally in each gateway is faster but each instance sees only its own share. A common middle path is to count locally and synchronise with Redis every few hundred milliseconds, accepting a small overshoot.
• Fail open or fail closed. If Redis is unreachable, most APIs let requests through (fail open) so that a limiter outage does not become a full outage. A login or payment endpoint may prefer to fail closed.
• Where the key lives. Sharding Redis by key keeps all updates for one client on one node, which the atomic script needs.
• Memory. Keys expire after a window of inactivity, so memory tracks active clients, not all clients ever seen.

Follow-up questions

• How would you limit across several data centres without a round trip between them?
• How do you stop one very busy key from overloading a single Redis shard?
• A customer says they were limited unfairly. What would you log to investigate?
• How would you add a second limit, such as 1,000 a day, on top of 100 a minute?