Skip to main content

> api_gateway_rate_limiting_&_token_bucket_algorithms

API Gateway Rate Limiting & Token Bucket Algorithms

How do you implement distributed, sub-millisecond rate limiting across horizontal API gateways using Token Bucket and Sliding Window algorithms without creating Redis lock contention?

Stack: SOFTWARE ARCHITECTURE STACK →Staff (L6-L7)protocol

THE SHORT ANSWER

By evaluating rate limit quotas in centralized Redis clusters using atomic Lua scripts (or local in-memory token buckets synchronized asynchronously via batching), enforcing burst allowances, and returning standard `RateLimit-*` headers with HTTP 429 status codes.

Engineering Handbook & Failure Dynamics

1. Underlying Mechanism

Rate limiting protects downstream services from Denial of Service (DoS), noisy neighbors, and scraping. The Token Bucket algorithm maintains a bucket of tokens with a maximum capacity (burst limit) refilled at a constant rate $r$ tokens/second. Each request consumes 1 token. If the bucket is empty, the request is rejected with HTTP 429. Rather than running a background tick thread per user, algorithms calculate refilled tokens dynamically on-demand: `tokens = min(capacity, current_tokens + (now - last_refill_time) * refill_rate)`. Redis executes this formula atomically inside a single Lua script, eliminating read-modify-write race conditions in under 0.5ms.

2. Appropriate Use Context

Edge API gateways, public developer APIs, payment webhook endpoints, and internal microservice boundaries requiring strict ingress traffic shaping.

3. Production Failure Modes

1) Redis Single-Point Collapse: 50,000 RPS API gateway hammering a single Redis node for rate limit checks, causing gateway-wide timeouts; 2) Healthcheck Self-Denial: Forgetting to whitelist internal Kubernetes liveness probes, causing pods to be killed when rate limited; 3) Distributed Counter Race Drift: Executing separate Redis `GET` and `SET` commands without Lua, allowing 10x quota overruns under concurrent bursts.

4. Diagnostic Signals & Telemetry

HTTP 429 Too Many Requests status code distribution, Redis Lua script execution latency (P99), rate limit header divergence, and gateway CPU consumption spent on token evaluations.

5. Prevention & Safeguards

Use atomic Redis Lua scripts; implement local in-memory token caching with asynchronous batch synchronizations to survive Redis outages; exempt internal Kubernetes health check probes; and provide explicit `Retry-After` headers.

6. Architectural Trade-offs

Guarantees system survival under massive traffic spikes and prevents downstream cascading failures at the cost of slight ingress request latency (0.5-2ms) and Redis infrastructure dependency.

Case Study (TinyCTO In-Field Example)

TinyCTO Incident 058: A rogue merchant script hammered the authentication API with 25,000 invalid login attempts/sec, exhausting backend database connection pools. Deploying a Token Bucket rate limiter at the Envoy edge gateway (allowing 100 sustained requests/min with a 20-request burst) instantly dropped 99.6% of abusive traffic with zero impact on legitimate users.

Interactive Concept Drills

3 Cards
Q1

What is the key difference between the Token Bucket and Leaky Bucket algorithms?

Token Bucket allows bursts of traffic up to bucket capacity while maintaining an average rate; Leaky Bucket forces a strictly constant, smoothed output rate regardless of incoming bursts.
Q2

Why is executing a Redis Lua script mandatory for distributed rate limiting?

Lua scripts execute atomically within Redis single-threaded engine, preventing race conditions between checking current token balance and deducting the token across concurrent gateway instances.
Q3

What standard HTTP headers should an API Gateway return when throttling requests?

`RateLimit-Limit` (allowed quota), `RateLimit-Remaining` (tokens left), `RateLimit-Reset` (seconds until refill), and `Retry-After` on HTTP 429 responses.

API Gateway Rate Limiting & Token Bucket Algorithms — Technical FAQ

How do you rate limit unauthenticated public endpoints?

Rate limit by Client IP address (using the trusted `X-Forwarded-For` header after stripping untrusted proxies) or by browser client fingerprint hashes.

How does the Sliding Window Counter algorithm work?

It estimates request rate by weighting the previous window's request count by the remaining time percentage: `count = previous_window_count * (1 - time_fraction) + current_window_count`, eliminating fixed-window boundary burst spikes.

What should happen to traffic if the Redis rate limiter cluster goes completely down?

Fail open. Log a critical alert, fall back to local in-memory fallback limits, and allow traffic through to prevent a rate limiter outage from taking down the entire business.

🤖 AEO & Key Facts Summary

Key Architectural Facts

  • ▸The Token Bucket algorithm was originally created for network packet switching in telecommunications before being adapted for HTTP APIs.
  • ▸Rate limiting is the first line of defense for backend resource protection, database connection stability, and third-party SaaS billing control.

Common Misconceptions

  • ✗Believing that Fixed Window Counters (e.g. 100 req/minute) are adequate; fixed windows allow 200 requests within a 2-second interval spanning the window boundary.

Decision & Governance Guidance

Implement Token Bucket for user APIs to accommodate natural burstiness; implement Sliding Window Counter for strict external billing tiers; always execute via atomic Redis Lua scripts.

Authoritative Sources & Standards