API Rate Limiting and Throttling: Algorithms and Implementation

Every API that survives contact with the real world eventually needs a way to say no. A single misbehaving client — a retry loop with no backoff, a scraper, a compromised API key — can consume enough capacity to degrade service for everyone else sharing that infrastructure. Rate limiting is the mechanism that enforces fairness and protects capacity before that happens, and the algorithm you choose determines whether your limits are precise, gameable, or accidentally hostile to legitimate traffic.

This isn't just about stopping abuse. Rate limiting protects downstream dependencies (databases, third-party APIs you're paying per-call for, internal services with their own capacity limits) from being overwhelmed by traffic that's technically legitimate but poorly paced. It protects your infrastructure bill from runaway automation. And it protects other tenants on a shared multi-tenant API from noisy-neighbor effects. Getting the algorithm and implementation right is a core piece of API reliability engineering, not a bolt-on afterthought.

Fixed window counter: simple, but bursty at the edges

The fixed window counter is the algorithm most engineers reach for first because it's trivial to implement: pick a window size (say, 60 seconds), maintain a counter keyed by client and window, increment it on every request, and reject once the counter exceeds the limit. When the clock rolls into the next window, the counter resets to zero. With Redis this is a single INCR with a EXPIRE set on first write — a few lines of code and O(1) memory per client.

The problem is the boundary. Because the window resets in a hard cliff rather than continuously, a client can send its full quota in the last second of one window and its full quota again in the first second of the next. A limit of 100 requests/minute nominally caps throughput at 100/min, but nothing stops 200 requests landing within a two-second span straddling the boundary — double the intended rate, sustained for as long as the client can time its bursts to the window edges. For a limit meant to protect a fragile downstream resource, that's a real gap, not a theoretical one.

A fixed window doesn't limit your rate — it limits your rate per clock tick, and clients can stand on either side of the tick at once.

Sliding window log and sliding window counter

The sliding window log algorithm fixes the boundary problem by tracking every request's exact timestamp instead of a coarse counter. To evaluate a new request, you drop all timestamps older than now - window_size from the log, then check whether the remaining count is under the limit. Because the window is evaluated relative to the current instant rather than snapping to a fixed boundary, there's no edge to exploit — the rate really is bounded to the limit over any rolling window, not just clock-aligned ones.

The cost is memory and computation: you're storing a timestamp per request per client (typically as a sorted set in Redis, using ZADD and ZREMRANGEBYSCORE to trim expired entries), and at high request rates for high-traffic clients, that log can grow large and expensive to prune on every single request. It's precise but doesn't scale cheaply.

The sliding window counter is the practical middle ground almost every production system actually uses. It keeps two fixed-window counters — the current window and the previous one — and estimates the rolling count by weighting the previous window's count by how much of it still overlaps the sliding window:

estimated_count = current_window_count + previous_window_count * (overlap_fraction)

For example, 30 seconds into a 60-second window, the overlap fraction is 0.5, so half of the previous window's count is added to the current window's count. This assumes requests were evenly distributed within the previous window, which is an approximation — but it's a very good one in practice, closes the boundary-burst gap almost entirely, and costs the same O(1) memory as the fixed window counter. This is the algorithm behind most gateway-level rate limiters you'll encounter, including nginx's limit_req in its default leaky-bucket-adjacent form and Cloudflare's rate limiting rules.

Token bucket and leaky bucket

Where the window-based algorithms are fundamentally about counting requests in a time span, token bucket and leaky bucket model rate limiting as a flow-control problem, and they answer a different question: not just "how many requests," but "how should bursts behave."

In token bucket, each client has a bucket with a fixed capacity, filled with tokens at a steady refill rate (say, 10 tokens/second, capped at a maximum of 100). Every request consumes one token; if the bucket is empty, the request is rejected or queued. Because tokens accumulate during idle periods up to the bucket's capacity, a client that's been quiet can burst up to the full bucket size in a single instant before being throttled back to the steady refill rate. This is usually exactly what you want for APIs: it enforces a long-run average rate while still permitting legitimate bursty behavior — a batch job that fires 50 requests at once after being idle, for instance — without penalizing the client for not having spread that traffic out artificially.

Leaky bucket inverts the framing. Requests arrive into a queue (the "bucket") of fixed size and are processed — leaked out — at a constant, fixed rate, regardless of how bursty their arrival was. If the queue is full when a request arrives, it's dropped. The output rate is perfectly smooth by construction; there is no burst allowance at all, because the leak rate is fixed independent of input. This is the right model when the thing you're protecting genuinely cannot tolerate bursts — a downstream service with a hard concurrency ceiling, a metered third-party API billed in a way that punishes spiky call patterns, or a legacy system that falls over under uneven load even if the average rate is fine.

The practical choice: use token bucket when you want to cap an average rate while tolerating legitimate burstiness — this is the default for most public APIs. Use leaky bucket when the downstream consumer needs a constant, predictable output rate and bursts themselves are the problem, not just the volume.

Where rate limiting actually lives in the stack

Algorithm choice matters less than where you enforce it. Rate limiting can live at the API gateway or reverse proxy layer (Kong, nginx, Envoy, or a cloud provider's managed API gateway) or inside application middleware running in your service code. Gateway-level enforcement is almost always preferable for one structural reason: it rejects excess traffic before it consumes application resources. A request rejected at nginx with a 429 costs a socket accept and a header parse. A request rejected inside your application after middleware has already deserialized the body, opened a database connection pool slot, and run authentication logic has already spent the resources you were trying to protect. If the goal is protecting compute and downstream capacity, doing the check as early in the request path as possible — ideally before it even reaches an application process — is the difference between rate limiting working and rate limiting working too late.

Application-level rate limiting still has a place: for limits that depend on business logic the gateway can't see (a per-user quota that varies by subscription tier stored in your database, for instance) or for limits scoped to a specific expensive operation rather than the API as a whole. In practice, most mature systems layer both — coarse, cheap protection at the gateway, finer-grained business-aware limits in the application.

The other key decision is the limiting key. Per-API-key limiting is the standard for authenticated APIs and is the most abuse-resistant, since keys are provisioned deliberately and can be revoked individually. Per-IP limiting is a necessary fallback for unauthenticated endpoints (like login or signup) but is fragile — NAT and shared corporate egress IPs mean it can throttle many legitimate users as one, and it's trivially evaded with IP rotation. Per-user limiting (tied to an authenticated session or account, independent of which key or device they're using) is the right granularity when the abuse vector is account-level rather than key-level, such as preventing one user from spinning up multiple API keys to bypass a per-key limit.

Communicating limits to clients

A rate limiter that rejects requests without explaining itself forces every client to guess — and guessing produces exactly the retry storms you were trying to prevent. The correct HTTP status for a throttled request is 429 Too Many Requests, not a generic 403 or 503; client libraries and monitoring systems key off this specifically to distinguish throttling from actual failure.

Alongside the status code, responses should carry standard headers so well-behaved clients can self-regulate: X-RateLimit-Limit (the ceiling for the current window), X-RateLimit-Remaining (requests left before the client gets throttled), and X-RateLimit-Reset (when the window resets, typically as a Unix timestamp). These aren't formally standardized across all providers — GitHub, Stripe, and Twitter each have slightly different header names and semantics — though the IETF's RateLimit header field draft is pushing toward convergence. Whichever naming you pick, apply it consistently across every endpoint. On a rejected request, always include Retry-After, giving the number of seconds (or an HTTP date) the client should wait before retrying. This single header is what turns a client's retry logic from blind exponential backoff guesswork into an informed wait.

A real-world example

Consider a public API that issues per-customer API keys and needs to support both steady interactive usage and occasional legitimate batch operations — a common shape for billing, CRM, or data-export APIs. A fixed window counter would either be too strict (rejecting a legitimate 200-request batch job that a customer runs once a day) or too loose at the boundary (letting that same customer double their effective rate by timing requests around the window edge).

A token bucket per API key fits this well: each key gets a bucket sized to, say, 100 tokens with a refill rate of 10 tokens/second (a 10 req/s sustained rate). A customer running routine traffic never hits the ceiling. A customer kicking off a nightly batch export can burst up to 100 requests immediately, then gets smoothly throttled back to the sustained rate as the bucket drains — no hard rejection of a legitimate workload, just a graceful cap.

The implementation detail that matters here is state storage. If the API runs behind multiple gateway instances behind a load balancer — which any API with real traffic does — each instance cannot maintain its own in-process bucket state, because a client's requests will land on different instances between calls, and each instance would think it's seeing a fraction of the client's actual traffic. The standard fix is backing the bucket state in Redis, shared across all gateway instances, using an atomic Lua script (via EVAL) to perform the check-and-decrement as a single operation and avoid race conditions between concurrent requests hitting different instances at the same moment. Libraries like redis-cell or hand-rolled Lua scripts implementing the GCRA (generic cell rate algorithm, a mathematically equivalent formulation of token bucket) are the common production pattern here, because they avoid the read-modify-write race that a naive GET-then-SET implementation would have under concurrent load.

Common mistakes to avoid

Three mistakes account for most rate limiting failures in production:

Rate limiting only at the application layer. If the limiter lives inside your application process, a flood of requests still consumes connection handling, authentication, and routing resources before being rejected. Under a real flood, the application tier can be saturated and rejecting slowly long before the rate limiter's logic even executes. Push enforcement to the gateway or reverse proxy so excess traffic is dropped before it costs you compute.

Omitting Retry-After. Without it, well-behaved clients have no signal for how long to back off and either retry immediately (making the overload worse) or implement their own arbitrary backoff that may be far longer than necessary, hurting their own throughput unnecessarily. This single header is cheap to add and directly determines whether your throttled clients behave cooperatively or adversarially.

Using in-memory counters on a multi-instance deployment. An in-process counter (a simple dictionary or local cache) only sees the traffic that lands on that specific instance. Behind a load balancer distributing across, say, five instances, a limit intended to cap a client at 100 requests/minute actually caps them at up to 500/minute in aggregate, since each instance independently allows 100 before throttling. This is one of the most common production incidents in rate limiting — the limit looks correctly configured in code, passes local testing on a single instance, and then silently under-enforces by a factor equal to the fleet size once deployed. Always back shared state in a centralized store like Redis unless you have a specific, deliberate reason for per-instance limits.

Frequently asked questions

Should rate limiting and throttling be treated as the same thing?
Not quite — they're closely related but distinct in intent. Rate limiting typically means rejecting requests outright once a threshold is exceeded, returning a 429. Throttling more precisely refers to delaying or queuing requests to smooth traffic to an acceptable rate rather than rejecting it — leaky bucket is inherently a throttling mechanism, since excess requests queue rather than fail immediately, whereas a simple fixed window counter is purely a rate limiter. In practice the terms are often used interchangeably, but the distinction matters when you're choosing between rejecting and queuing as your overload response.

Should rate limits apply to authentication failures the same as successful requests?
No — and this is a common oversight. Failed authentication attempts (wrong API key, expired token, invalid credentials) should typically be rate limited more aggressively and separately from normal traffic limits, both to slow credential-stuffing attacks and because a burst of auth failures is a distinct signal from legitimate usage patterns. Many teams implement a tighter, separate limiter specifically on authentication endpoints.

How should rate limits interact with API versioning or tiered pricing plans?
Limits should be looked up dynamically per key rather than hardcoded, typically by attaching a plan or tier identifier to the API key at issuance and having the gateway or middleware fetch the corresponding limit (from a fast cache, not a live database query on every request) before applying it. This lets you offer differentiated limits — free tier at 60 req/min, enterprise at 6000 req/min — without deploying different rate limiter code per tier.

Rate limiting done well is invisible to the overwhelming majority of legitimate traffic and firm against the traffic that isn't. The algorithm you pick — fixed window for simplicity, sliding window counter for a good precision-to-cost ratio, or token/leaky bucket for explicit burst control — should be driven by what you're actually protecting downstream, and the enforcement point should be as close to the edge of your infrastructure as you can push it. Get the headers and status codes right, store shared state centrally, and rate limiting stops being a source of mysterious production incidents and becomes what it's supposed to be: boring, predictable infrastructure.