API Rate Limiting: Algorithms and How to Implement It

API Rate Limiting: Algorithms and How to Implement It#

The first time an unauthenticated client hammered one of our endpoints with 4,000 requests a second, the database connection pool drained, healthy tenants started timing out, and a retry storm turned a single misbehaving script into a full outage. Rate limiting is the cheapest insurance you can buy against that. It is a few lines of code that stand between one bad actor and everyone else's bad day.

Why rate limit at all#

Four reasons keep coming up, and most APIs need all of them.

Protect against abuse: scrapers, credential-stuffing bots, and buggy clients in retry loops will send far more traffic than any legitimate user. A limit caps the blast radius.

Ensure fairness: shared capacity is finite. Without a ceiling, one heavy consumer starves everyone else on the same tier.

Control cost: every request burns CPU, database time, and sometimes a paid downstream call. Uncapped usage is uncapped spend.

Prevent cascading overload: when a service saturates, timeouts and retries amplify the load and take dependencies down with it. Shedding excess traffic early keeps a local problem local.

The algorithms and their trade-offs#

You have five common options. They differ mostly in how they handle bursts and how much they cost to run.

Fixed window counts requests in a clock-aligned bucket, say 100 per minute, and resets at the top of each window. It is trivial to implement with a single counter. The flaw is the boundary burst: a client can send 100 requests at 12:00:59 and another 100 at 12:01:00, so 200 land in two seconds while every individual window stays legal.

Sliding window log stores a timestamp for every request and counts how many fall inside the trailing window. It is exact and has no boundary problem, but you pay for it in memory. A client allowed 1,000 requests an hour means storing up to 1,000 timestamps per client.

Sliding window counter approximates the log using two fixed-window counts, the current and the previous, weighted by how far into the current window you are. It smooths the boundary burst without storing per-request data, which makes it a strong default for most APIs.

Token bucket holds a bucket that refills at a steady rate up to a maximum. Each request removes one token; if the bucket is empty, the request is rejected. This allows short bursts up to the bucket size while capping the long-run average. It is the most common choice because it matches how people actually think about limits: a sustained rate plus a bit of headroom.

Leaky bucket queues requests and drains them at a fixed rate, so output is perfectly smooth regardless of how spiky the input is. It is a good fit when a downstream system needs a steady feed, at the cost of added latency and a queue to manage.

Where to enforce it#

Push the limit as close to the edge as you can. An API gateway, load balancer, or CDN rejects excess traffic before it touches your application, which is exactly where you want abuse stopped. Gateway limits are also coarse: they usually key on IP or API key and know nothing about business context.

Enforce inside the application when the limit depends on things only your code knows, such as the user's plan, the specific operation's cost, or a per-resource quota. Most mature setups run both: a blunt gateway limit for raw protection and a finer application limit for fairness and billing tiers.

Distributed rate limiting#

In-memory counters break the moment you run more than one instance. Each process keeps its own count, so a client behind a load balancer effectively gets its limit multiplied by the number of instances, and the number drifts every time you scale. The fix is a shared store, and Redis is the usual pick because its atomic operations and native key expiry map cleanly onto this problem.

The simplest correct version is a fixed window built on INCR plus an expiry:

import redis

r = redis.Redis()

def allow_request(api_key: str, limit: int = 100, window_s: int = 60) -> bool:
    # Bucket key rotates every window; old buckets expire on their own.
    bucket = int(time.time()) // window_s
    key = f"rl:{api_key}:{bucket}"

    count = r.incr(key)
    if count == 1:
        # First hit in this window sets the TTL so the key self-cleans.
        r.expire(key, window_s)
    return count <= limit

For a token bucket you store two fields per key, the current token count and the last refill timestamp, and update them atomically in a Lua script so the read-modify-write can't race between instances. Redis runs the script server-side, which keeps the whole check to a single round trip.

Per-key strategy#

Decide what you are limiting per. The key is usually one of three things. Per API key or per user is the fairest, since it ties usage to an identity and survives IP changes. Per IP is your only option for unauthenticated traffic, but it punishes users behind shared NATs and is trivially evaded with a pool of addresses. A common pattern is a strict per-IP limit on login and signup endpoints and a per-key limit everywhere else.

The response contract#

When you reject a request, say so in a way clients can act on. Return 429 Too Many Requests, add a Retry-After header telling the client how long to wait, and expose the current limit state with RateLimit headers so well-behaved clients can self-throttle before they hit the wall.

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

{"error": "rate_limit_exceeded", "message": "Too many requests. Retry in 30s."}

Send the RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset headers on successful responses too, not just on the rejection. Clients that can see how much budget they have left will pace themselves, which reduces the number of 429s everyone has to handle.

How to choose#

Start from the shape of your traffic. If you serve human-facing clients that occasionally batch work, token bucket gives you a clean average with room for bursts. If a downstream system needs a steady feed, leaky bucket earns its latency. If you want accuracy without per-request storage, sliding window counter is the balanced middle. Fixed window is fine for rough internal quotas where the boundary burst does not matter.

The call we'd make#

For a typical multi-tenant API, run a token bucket per API key backed by Redis, enforced at the gateway for raw protection and again in the application for plan-aware fairness. Return honest 429 responses with Retry-After and RateLimit headers on every request. It is a well-understood setup, it degrades gracefully, and it turns your loudest client into a manageable one instead of an outage.

Rate limiting is one piece of a larger picture. For the surrounding decisions, see our API design best practices, and pair your limits with the controls in API security best practices.