Skip to content

Rate Limiting Strategy

1. Decision

Implement Rate Limiting at the API Gateway or Edge Proxy layer using the Token Bucket algorithm for smooth burst handling, or the Sliding Window Log / Counter algorithm for strict precise rate boundary enforcement, backed by Redis in-memory storage.

2. 30-Second Answer

Rate Limiting protects backend microservices, databases, and third-party APIs from traffic spikes, Denial-of-Service (DoS) attacks, brute-force exploits, and noisy-neighbor resource starvation. It evaluates incoming requests against rate policies (e.g. 100 requests/minute per API Key or IP address). The five primary rate-limiting algorithms are: Fixed Window (simple, but suffers from \(2\times\) burst boundary spikes), Leaky Bucket (constant processing output rate), Token Bucket (supports controlled burst traffic), Sliding Window Log (exact precision, but high memory), and Sliding Window Counter (approximates precision with minimal memory footprint). Rate limiting state is centralized in Redis using atomic Lua scripts to prevent distributed race conditions.

3. Decision Matrix

Option Best For Avoid When Latency Scalability Consistency Operational Complexity
Token Bucket General API Gateway rate limiting, workloads allowing controlled burst traffic (e.g. 10 req/sec with burst of 50) Applications requiring strict uniform execution rates without bursts Low (<1ms Redis Lua execution) High (Stores only 2 values per key: capacity & last_refill) Strong (Atomic Redis Lua script) Low
Leaky Bucket Smoothing out bursty traffic into steady constant output rates (e.g., background job queueing, third-party API proxies) Applications requiring immediate processing of short legitimate bursts Medium (Requests queue in bucket before execution) Medium (Memory bounded by queue capacity) Strong Medium
Sliding Window Counter High-traffic public APIs, microservice protection, memory-efficient precise rate limits Microsecond exact boundary accuracy requirements Ultra-Low (<1ms Redis calculation) Extremely High (Blends current & previous window counters in tiny memory) High (Approximates sliding boundary within ~0.05% error) Low to Medium
Sliding Window Log Security-critical endpoints (login, password reset, payment gateways) requiring exact 100% boundary accuracy High-volume public endpoints (High memory cost storing timestamps) Low (Redis Sorted Set ZREMRANGEBYSCORE execution) Low to Medium (Memory grows with request log volume) Exact 100% Precision Medium

4. Selection Rules

Requirement Best Choice Rationale / Example
Standard API Gateway Protection (AWS/Kong) Token Bucket Refill tokens at fixed rate; allow legitimate initial bursts up to bucket capacity
Smooth Out Bursty Writes to Third-Party APIs Leaky Bucket Converts erratic bursts into a smooth, constant output rate (e.g., 5 msgs/sec)
Memory-Efficient Production API Rate Limiting Sliding Window Counter Blends previous window count with current window count: count = prev * (1 - ratio) + curr
Prevent Brute-Force Password Attempts Sliding Window Log Store exact timestamps in Redis ZSET; block if ZCOUNT > 5 in last 15 minutes
Avoid 2x Burst Boundary Spikes Sliding Window / Token Bucket Fixed Window allows 100 reqs at 12:00:59 and 100 reqs at 12:01:01 (\(2\times\) spike!)

5. Tradeoffs

  1. Burst Allowance vs Smooth Traffic Processing
  2. Gain (Token Bucket): Accommodates natural human interaction bursts (e.g., loading a page).
  3. Lose (Token Bucket): Downstream database must handle temporary short-term burst traffic.
  4. Exact Memory Log Precision vs Memory Footprint Overhead
  5. Gain (Sliding Log): 100% exact boundary enforcement; zero window edge vulnerabilities.
  6. Lose (Sliding Log): Storing every request timestamp in Redis ZSET consumes megabytes per user.
  7. Atomic Lua Script Execution vs Distributed Race Conditions
  8. Gain: Executes check-and-decrement atomically in single-threaded Redis memory.
  9. Lose: Slow or complex Lua scripts block the Redis single-threaded event loop.
  10. Centralized Redis Cluster vs Local Edge Rate Limiting
  11. Gain (Redis): Enforces global rate limits across 100 load-balanced API Gateway containers.
  12. Lose (Redis): Every HTTP request incurs a 1ms network TCP hop to Redis.
  13. Soft Rate Limiting vs Hard Rate Limiting
  14. Gain (Soft): Temporarily allows premium users to exceed limits before returning HTTP 429.
  15. Lose (Soft): Requires managing multi-tier quota queues and tier configurations.

6. Interview Counter Questions

  1. Why does the Fixed Window Counter algorithm suffer from the 2x Boundary Spike problem?
  2. How does the Token Bucket algorithm calculate token replenishment without running background timer threads?
  3. How do you implement a Sliding Window Counter using a Redis Lua script?
  4. What HTTP headers must an API Gateway return when rate-limiting a client (RFC 6585 / Draft)?
  5. How do you handle distributed race conditions when multiple API Gateway nodes read/write rate limit keys in Redis?
  6. What is the difference between Rate Limiting by IP Address vs API Key vs User ID?
  7. How does a Distributed Rate Limiter handle Redis cluster failure or network partitions (Fail-Open vs Fail-Closed)?
  8. How does a Leaky Bucket algorithm queue traffic differently than Token Bucket?
  9. How do you prevent DDoS attacks using multi-tier rate limiting (CDN Edge vs Gateway vs Application)?
  10. What is a Throttling Penalty / Exponential Backoff header (Retry-After)?

7. Gold Standard Answers

  1. Fixed Window (100 req/min): User sends 100 requests at 12:00:59 and 100 requests at 12:01:01. Both pass because they fall in different minute windows, resulting in 200 requests within 2 seconds (\(2\times\) burst spike!).
  2. Lazy Evaluation: On every request, calculate tokens_to_add = (current_time - last_refill_time) * fill_rate. Update tokens = min(capacity, tokens + tokens_to_add) inline without background timers.
  3. Compute weighted sum: current_weight = (60 - current_second) / 60. estimated_count = (prev_window_count * current_weight) + current_window_count. If estimated_count < limit, execute INCR.
  4. Return HTTP 429 Too Many Requests with headers: X-RateLimit-Limit: 100, X-RateLimit-Remaining: 0, X-RateLimit-Reset: 1770000000, Retry-After: 30.
  5. Atomic Redis Lua Scripts: Package the check-and-decrement logic into a single Lua script. Redis single-threaded event loop executes the script atomically, preventing concurrent race conditions.
  6. IP Address: Protects against unauthenticated bot spam (risk: NAT corporate gateways share 1 IP). API Key / User ID: Protects authenticated user quotas (accurate per tenant).
  7. Fail-Open: Allow traffic through if Redis dies (preserves availability, risks DB overload). Fail-Closed: Block traffic if Redis dies (preserves security, risks full outage). Default: Fail-Open + Local Fallback Rate Limiting.
  8. Leaky Bucket: Requests enter a FIFO queue and exit at a strictly fixed constant rate (smooths traffic). Token Bucket: Tokens accumulate; requests consume tokens and execute immediately up to burst capacity.
  9. CDN Edge (Cloudflare): Filter IP DDoS & SYN floods \(\rightarrow\) API Gateway (Kong): Filter by API Key / OAuth Token \(\rightarrow\) Application: Filter expensive individual endpoints.
  10. Retry-After: 30 instructs the client to wait 30 seconds before retrying. Clients should implement Exponential Backoff with Random Jitter upon receiving HTTP 429.

8. Common Mistakes

  • Using Fixed Window Counter for production APIs, allowing 2x boundary traffic spikes to crash downstream DBs.
  • Implementing check-and-increment in application code via separate Redis GET and SET calls, causing distributed race conditions.
  • Rate-limiting solely by IP address in B2B SaaS platforms, blocking thousands of users behind corporate NAT gateways.
  • Fail-closing the entire production API Gateway when the Redis rate-limiting cache node experiences a minor network glitch.
  • Returning generic HTTP 500 Internal Server Error instead of standard HTTP 429 Too Many Requests with Retry-After headers.

9. Keywords

Rate Limiting, Token Bucket, Leaky Bucket, Fixed Window, Sliding Window Log, Sliding Window Counter, 2x Boundary Spike, HTTP 429, Retry-After, Redis Lua Script, Fail-Open, Fail-Closed, Lazy Evaluation, NAT Gateway, CDN Edge Rate Limiting.

10. Cheat Sheet

  • Token Bucket: Standard API default. Refills tokens lazily; permits controlled traffic bursts up to bucket capacity.
  • Leaky Bucket: Processes output at a strictly constant rate. Smooths out bursty queue jobs.
  • Sliding Window Counter: Production memory-efficient choice. Blends previous & current window counts: prev * (1 - ratio) + curr.
  • 2x Boundary Spike: Fixed Window fails because 100 reqs at 12:00:59 + 100 reqs at 12:01:01 = 200 reqs in 2 seconds!
  • Atomic Execution: Always execute rate-limit checks in Redis using Atomic Lua Scripts to prevent race conditions.
  • HTTP 429 Response: Always return HTTP 429 Too Many Requests + Retry-After: <seconds> header.
  • Resilience: Set Rate Limiter to Fail-Open + Local In-App Fallback if Redis cluster becomes unreachable.

11. Related Decisions