# API Rate Limiting: Algorithms and How to Implement It

URL: https://www.devopsness.com/blog/api-rate-limiting
Author: Kiril Urbonas
Published: 2026-08-11
Updated: 2026-10-31
Categories: DevOps
Tags: API Design, Rate Limiting, Scalability, Backend, Redis

Summary: A practitioner's guide to rate limiting algorithms, where to enforce them, and how to make them work across many instances with Redis.

---
# API Rate Limiting: Algorithms and How to Implement It

Rate limit a public API with a token bucket per API key, kept in Redis so every instance sees the same count. Enforce a coarse limit at the gateway and a plan-aware one in the app. Reject excess traffic with `429 Too Many Requests` plus `Retry-After`. Use a sliding window counter when you don't want bursts.

> [!VERIFIED]
> RFC 6585 (429 status), RFC 9110 (Retry-After), IETF draft-ietf-httpapi-ratelimit-headers-11 (May 2026), against the Redis INCR command docs. Checked October 2026.

The failure this prevents is familiar: one unauthenticated client hammers an endpoint, the database connection pool drains, healthy tenants start timing out, and a retry storm turns a single misbehaving script into a full outage. Rate limiting is a few lines of code that stand between one bad actor and everyone else's bad day.

Four reasons keep coming up: abuse (scrapers, credential stuffing, buggy retry loops), fairness (one heavy consumer starving a shared tier), cost (every request burns CPU, database time, and sometimes a paid downstream call), and cascading overload (timeouts and retries amplifying load into dependencies). Most APIs need protection from all four.

## 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 matches how people think about limits: a sustained rate plus some 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.

| Algorithm | Allows bursts | Accuracy | State per key | Best fit |
|---|---|---|---|---|
| Fixed window | Yes, up to 2x at boundaries | Rough | One counter | Internal quotas |
| Sliding window log | No | Exact | One timestamp per request | Low-volume, strict limits |
| Sliding window counter | Smoothed | Close approximation | Two counters | General-purpose default |
| Token bucket | Yes, up to bucket size | Exact average | Tokens plus timestamp | Public multi-tenant APIs |
| Leaky bucket | No, queued | Exact output rate | Queue | Feeding a fragile downstream |

## 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. If you are still choosing a cache, our [Redis vs Memcached comparison](/blog/redis-vs-memcached) covers the trade-offs; Memcached has no server-side scripting, which matters for the token bucket below.

The simplest correct version is a fixed window built on `INCR` plus an expiry, sent in one `MULTI`/`EXEC` transaction. The Redis docs call out the race in the naive version: if the process dies between `INCR` and `EXPIRE`, the key never expires.

```python
# ratelimit.py
import time
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}"

    # transaction=True wraps both commands in MULTI/EXEC, so the TTL is always set.
    pipe = r.pipeline(transaction=True)
    pipe.incr(key)
    pipe.expire(key, window_s)
    count, _ = pipe.execute()
    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. At the edge, the same single-source-of-truth problem has a different answer: [Cloudflare Durable Objects](/blog/cloudflare-durable-objects-stateful-edge) give each key one instance that does the counting.

## 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. Platforms do exactly this; see [GitLab's new unauthenticated API limits](/blog/gitlab-rate-limits-october-19-what-to-fix-now) for what it looks like from the client side.

## The response contract

When you reject a request, say so in a way clients can act on. RFC 6585 defines `429 Too Many Requests` and says the response may include `Retry-After` telling the client how long to wait; it also says 429 responses must not be stored by caches. For exposing remaining budget, the IETF draft `draft-ietf-httpapi-ratelimit-headers` (revision 11, May 2026, still an Internet-Draft as of October 2026) defines two fields: `RateLimit-Policy` for the quota and `RateLimit` for what is left.

```http
HTTP/1.1 429 Too Many Requests
Retry-After: 30
RateLimit-Policy: "default";q=100;w=60
RateLimit: "default";r=0;t=30
Content-Type: application/json

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

Earlier drafts used separate `RateLimit-Limit`, `RateLimit-Remaining`, and `RateLimit-Reset` headers, and many APIs still send the `X-RateLimit-*` variants. Pick one convention, document it, and send it on successful responses too, so clients can pace themselves before they hit a 429.

## Questions people ask

### What is the best rate limiting algorithm for an API?

For most public, multi-tenant APIs, token bucket is the best default. It caps the long-run average rate while letting a client burst up to the bucket size, which matches how real clients batch work. Choose a sliding window counter if you want to suppress bursts without storing per-request timestamps, and a leaky bucket only when a downstream system needs a perfectly steady feed.

### Why use Redis for rate limiting?

Because in-memory counters multiply your limit by the number of instances behind the load balancer. Redis gives every instance one shared count, `INCR` is atomic, and keys expire on their own, so old windows clean themselves up. Wrap `INCR` and `EXPIRE` in `MULTI`/`EXEC` or a Lua script, as the Redis docs recommend, so a crash between the two commands cannot leave a key that never expires.

### What should a 429 response include?

Return status `429 Too Many Requests` with a `Retry-After` header giving the wait in seconds, and a short body explaining the limit. RFC 6585 allows both and forbids caching the 429. Add budget headers so clients can self-throttle: either the IETF draft's `RateLimit-Policy` and `RateLimit` fields or the common `X-RateLimit-*` set, sent on every response.

## 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 budget headers on every request. It degrades gracefully and turns your loudest client into a manageable one instead of an outage. The caveat: your Redis is now in the request path, so decide up front whether a Redis outage fails open (serve traffic unlimited) or closed (reject), and test it.

Rate limiting is one piece of a larger picture. For the surrounding decisions, see our [API design best practices](/blog/api-design-best-practices), and pair your limits with the controls in [API security best practices](/blog/api-security-best-practices).

## Sources

- [RFC 6585: Additional HTTP Status Codes (429 Too Many Requests)](https://www.rfc-editor.org/rfc/rfc6585.html)
- [RFC 9110: HTTP Semantics (Retry-After)](https://www.rfc-editor.org/rfc/rfc9110.html)
- [IETF draft-ietf-httpapi-ratelimit-headers: RateLimit header fields for HTTP](https://datatracker.ietf.org/doc/draft-ietf-httpapi-ratelimit-headers/)
- [Redis docs: INCR command and the rate limiter pattern](https://redis.io/docs/latest/commands/incr/)

