Rate Limiting Algorithms: Token Bucket & Leaky Bucket
Exposing public REST or GraphQL API endpoints without strict rate limiting guarantees system instability during unexpected traffic bursts or malicious DDoS attacks. A sudden spike of 50,000 API requests per second will overwhelm downstream microservices, exhaust database connection pools, and crash application pods.
API Rate Limiting Algorithms govern incoming request rates by enforcing quota boundaries per IP address, user ID, or API key. Choosing between Token Bucket, Leaky Bucket, and Sliding Window Counter requires evaluating burst capacity vs constant request smoothing. This guide details rate limiting algorithm math, atomic distributed evaluation via Redis Lua scripts, HTTP 429 response formatting, and exponential backoff retry strategies.
Mental Model: Protecting Distributed APIs from Cascading Overload & DDoS Traps
Rate limiting acts as an API Gateway guardrail, rejecting excessive traffic at the edge before backend microservices process compute-heavy requests.
Rate Limiting Execution Pipeline:
1. Identify Client: Extracts client identifier (IP address, OAuth JWT client_id, or X-API-Key). 2. Evaluate Quota: Checks the rate limiter cache (e.g. Redis) for current token count or window timestamp. 3. Enforce Policy: If within quota, increments counter and passes request downstream. If quota is exceeded, returns HTTP 429 Too Many Requests immediately. For gateway security and caching, review securing api gateways oauth2 m2m client credentials and prevent cache stampede redis.
Quick reference
- Protects backend infrastructure from denial-of-service attacks and runaway client scripts.
- Prevents database pool exhaustion by shedding excess API traffic at the edge gateway.
- Enforces API monetization tier limits (e.g. Free Tier 100 req/min vs Enterprise 10,000 req/min).
- Evaluates rate limits in sub-millisecond execution windows using in-memory datastores.
- Powers API gateways at Stripe, GitHub, Cloudflare, Twilio, and CoreConcept.
Remember this
Implement edge API rate limiting to protect backend microservices from traffic spikes.
Token Bucket vs Leaky Bucket vs Sliding Window Counter Algorithms
Selecting the optimal rate limiting algorithm depends on whether your application requires burst capacity or constant smoothing:
- Token Bucket: A bucket holds up to $N$ tokens, replenished at rate $R$ tokens/sec. Incoming requests consume 1 token. Allows burst traffic up to capacity $N$, then throttles. Ideal for REST APIs. - Leaky Bucket: Requests enter a FIFO queue and leak out at a constant, fixed rate $R$. Smooths out traffic bursts into a steady processing stream. Ideal for background worker queues. - Sliding Window Counter: Combines fixed-window speed with previous-window weighting to prevent edge-of-window traffic doubling attacks.
Quick reference
- Token Bucket permits controlled traffic bursts while capping long-term consumption rates.
- Leaky Bucket enforces a smooth, constant egress rate to protect sensitive downstream dependencies.
- Sliding Window Counter eliminates edge-of-window spike vulnerabilities with weighted memory math.
- Fixed Window Counter has low memory footprint but suffers from double-burst window edge attacks.
- Provides predictable infrastructure throughput under high concurrency.
Remember this
Use Token Bucket for bursty REST APIs and Leaky Bucket for smoothing background worker pipelines.
Distributed Redis Lua Scripts for Atomic Millisecond Evaluation
In multi-pod Kubernetes API Gateway clusters, local in-memory rate limiters permit race conditions across instances. Redis Lua Scripts evaluate and update rate limits atomically inside the Redis engine:
1-- Atomic Token Bucket Lua Script in Redis2local key = KEYS[1]3local limit = tonumber(ARGV[1])4local current = tonumber(redis.call('get', key) or "0")5 6if current + 1 > limit then7 return 0 -- Quota Exceeded (Reject)8else9 redis.call('INCRBY', key, 1)10 if current == 0 then11 redis.call('EXPIRE', key, 60) -- 60s TTL12 end13 return 1 -- Allowed14endQuick reference
- Redis Lua execution is single-threaded and atomic, eliminating concurrency race conditions across gateway pods.
- Reduces network round-trips by executing fetch, compare, and update logic in a single Redis call.
- TTL expiration (EXPIRE) cleans up stale client key entries automatically after window elapsed.
- Redis Cluster sharding scales rate limit evaluation across millions of active client keys.
- Delivers sub-millisecond evaluation latency for high-QPS API gateways.
Remember this
Execute rate limit checks via Redis Lua scripts to guarantee atomic, race-condition-free evaluation.
Handling HTTP 429 Retry-After Headers & Client-Side Backoff Strategies
When an API client exceeds its rate limit, the API Gateway MUST respond with HTTP status code 429 Too Many Requests accompanied by standardized rate limit HTTP headers:
1HTTP/1.1 429 Too Many Requests2Content-Type: application/json3X-RateLimit-Limit: 1004X-RateLimit-Remaining: 05X-RateLimit-Reset: 17227300006Retry-After: 457 8{9 "error": "rate_limit_exceeded",10 "message": "Quota exceeded. Retry in 45 seconds."11}Quick reference
- Return X-RateLimit-Limit, Remaining, and Reset headers to inform clients of quota status.
- Include Retry-After header indicating exact seconds until the client can retry requests.
- Clients should implement Exponential Backoff with Full Jitter to prevent retry thundering herds.
- Circuit breakers handle sustained 429 responses gracefully in microservice call trees.
- Improves API client integration developer experience and infrastructure stability.
Remember this
Return HTTP 429 status with Retry-After headers to guide client-side exponential backoff retries.
Key takeaway
To test Token Bucket rate limiting locally, run docker run -d -p 6379:6379 redis:alpine and evaluate the Lua script using redis-cli --eval rate_limit.lua client_123 , 100.
Related Articles
Explore this topic