API rate limiting: patterns, algorithms, and how to do it right

Cross-post. Original: stellarbytecapital.com/blog/api-rate-limiting

Rate limiting may seem straightforward—just tally requests and halt when the count exceeds N—but it swiftly evolves into a distributed-systems challenge once multiple servers are in play, traffic becomes sporadic, or clients truly matter. When executed properly, it safeguards an API against misuse and mitigates spikes without penalizing genuine callers. However, when executed poorly, it suppresses legitimate requests, permits illicit ones, and deceives clients regarding when they can retry.

The primary objectives to safeguard depend on the desired outcome:

- Overload protection—prevents a traffic surge from crashing the service.

- Fair usage—prevents a noisy client from monopolizing resources, starving others.

- Abuse prevention—blocks brute-force attempts, scraping, and credential stuffing.

- Cost control—limits expensive endpoints, such as large language model calls or reports.

The core algorithms for rate limiting comprise:

- Fixed window: Counts requests per calendar interval (e.g., 100 requests per minute) and resets at the minute. Although simple, it fails to account for bursts, allowing a client to send 100 requests at the window's start and another 100 at the window's end, totaling 200 requests per second.

- Sliding window: Implements a rolling window instead of a fixed time frame and subtly smooths the count over time. It's more accurate but requires additional state management.

- Token bucket: Usually the preferred default algorithm. It maintains a bucket of up to N tokens that replenish at a steady rate. Each request consumes one token. This approach accommodates bursty behavior by enabling clients to accumulate tokens during quiet periods and utilize them during spikes. The leaky bucket variant enforces a steady output rate, ideal for downstream systems sensitive to bursts.

The primary challenge arises in distributed rate limiting. A per-instance counter in memory suffices until more than one server is introduced. In such cases, the per-instance limit escalates to N per second, where N is the number of instances. To address this, centralize the counter using Redis with atomic operations or Lua scripts to prevent race conditions that could result in double-counting.

However, trade-offs must be considered. Perfectly synchronized global limits introduce a latency penalty due to network overhead, while approximate local limits may exhibit slight overshoot but offer better performance. Rate limiting must also be scoped appropriately; typically, limits are defined per API key or user for fairness and billing purposes, per IP address to curb anonymous abuse (with caution when dealing with NATs or proxies), and per endpoint to establish tighter budgets for resource-intensive routes.

The client-facing response to rate limiting should adhere to HTTP standards:

- Return 429 (Too Many Requests) instead of generic 400 or 503 status codes.

- Include a Retry-After header to inform clients when to retry their requests.

- Expose rate limit headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset) to enable clients to proactively pace themselves without exceeding limits.

Certain practices should be avoided, such as using fixed windows for critical rate limiting scenarios to prevent burst loopholes, relying on per-instance in-memory counters behind load balancers that can exceed configured limits, employing non-atomic check-then-increment operations susceptible to undercounting under heavy load, or implementing silent drops or incorrect status codes that hinder client back-off mechanisms.

Lastly, avoid applying a single global limit to all API calls without differentiation based on client identity or endpoint importance.