Rate Limiting

A public API is vulnerable to abuse. Whether from malicious DDoS attacks, poorly written client loops, or aggressive scraping bots, unchecked request volumes will saturate server bandwidth, database connections, and CPU cycles. Rate Limiting enforces policies that restrict the number of requests a user, IP address, or API token can execute within a specific time window.

1. Learning Objectives

• Identify security and resource exhaustion risks mitigated by rate limiters.
• Compare rate-limiting algorithms: Token Bucket, Leaky Bucket, Fixed Window, and Sliding Window.
• Explain the mechanics of distributed rate limiting using Redis and Lua scripting.
• Trace how standard HTTP headers communicate rate status to clients.
• Handle rate-limiting edge cases such as token bucket synchronization and concurrency race conditions.
• Implement a thread-safe Token Bucket rate limiter in Java, Python, and C++.

2. Prerequisites

Before starting, ensure you understand:

• HTTP Status Codes: Especially error codes like 429 Too Many Requests.
• Distributed Caching: Basic storage commands in Redis or Memcached.
• Mutex and Concurrency Control: Thread synchronization and atomic variables.

3. Why This Topic Matters

Rate limiters act as the first line of defense for web applications.

Without rate limiting, an attacker could write a script that sends thousands of login requests per second. This brute-forces passwords while simultaneously overloading your database with expensive write queries.

Rate limiting solves three major design problems:

• Prevents Resource Saturation: Keeps backend services from slowing down due to high traffic volumes.
• Ensures Fair Share Usage: Prevents a single aggressive user (noisy neighbor) from hogging all system capacity.
• Cost Optimization: Protects billing budgets by capping calls to paid downstream APIs (e.g. OpenAI, Stripe).

4. Real-world Analogy

Think of a Subway Turnstile:

Passengers queue to pass through the turnstile. If they have a valid ticket, they swipe, the turnstile rotates, and they pass through.

If a crowd of 500 people tries to run through the turnstile at the same time, the turnstile physical barrier prevents them from flooding the platform. It only allows passengers to pass through one at a time, matching the capacity of the arriving trains.

Passengers who arrive too quickly are held back, smoothing out the flow of traffic onto the platform.

5. Core Concepts

• Token Bucket: A bucket holds tokens up to a maximum capacity. Tokens are added to the bucket at a constant rate. Each incoming request consumes one token. If the bucket is empty, the request is rejected. This algorithm handles temporary bursts of traffic easily.
• Leaky Bucket: Requests enter a queue (bucket) and flow out at a constant, steady rate. If the queue fills up, new requests overflow and are discarded. This smooths out traffic spikes but adds latency to queued requests.
• Fixed Window Counter: Divides time into fixed intervals (e.g. 1-minute windows). A counter tracks requests within each window. If the count exceeds the limit, requests are blocked until the next window starts.
  Note: Vulnerable to traffic bursts at the boundary lines (double the limit can pass in a short period).
• Sliding Window Counter: Solves the boundary problem of the fixed window. It calculates the request count by blending the count of the current window with the count of the previous window based on the current timestamp.
• Distributed Rate Limiting: In multi-server setups, local counters in memory will not work. A centralized cache (like Redis) stores the rate-limiting keys so all app servers share the same limits.
• HTTP 429 Status Code: The standard HTTP response returned to a rate-limited client, accompanied by headers indicating when they can retry.

6. Visualizations

Token Bucket Mechanism

Fixed Window Boundary Spikes

7. How It Works Step-by-Step

Token Bucket Algorithm execution

1. Identify Client Key: Extract the client identification key (e.g. IP address, User Session ID, or API Key).
2. Retrieve Bucket State: Lookup the token bucket state associated with that key, including:
   • tokens: The number of tokens remaining.
   • lastRefillTimestamp: The timestamp of the last request check.
3. Calculate Refill: Calculate the time elapsed since lastRefillTimestamp. Add new tokens based on the refill rate: $$\text{New Tokens} = \text{Elapsed Seconds} \times \text{Refill Rate}$$ Cap the total tokens at the maximum bucket capacity.
4. Check Availability:
   • If tokens >= 1, decrement the token count by 1, update the timestamp, and allow the request.
   • If tokens < 1, reject the request and return an HTTP 429 error.

8. Internal Architecture

A distributed rate limiter sits in front of the application servers, integrated into an API Gateway or reverse proxy:

• API Gateway Layer: Nginx, Kong, or AWS API Gateway intercepts requests and queries the rate-limiting store before forwarding them to backend servers.
• Shared Redis Cache: Storing counters in Redis ensures all app servers share request limits. A sorted set (ZSET) coordinates sliding window timestamps.
• Lua Scripting Execution: To prevent race conditions in high-concurrency environments, rate checks and token decrements are packaged in Lua scripts that run atomically inside Redis.

9. Request Lifecycle

Let's trace a client request processed by a rate limiter:

1. Client Request: The client sends an HTTP GET request to /api/v1/data with header X-API-Key: client_987.
2. Gateway Interception: The API Gateway intercepts the request, reads the API Key, and queries Redis using an atomic Lua script.
3. Redis Token Update: Redis calculates the token count for client_987.
   • Token Available: Decrements the count and returns success.
   • No Token Available: Returns failure.
4. Response Generation:
   • Allowed: The gateway forwards the request to the application server and adds headers:
     X-RateLimit-Limit: 100
X-RateLimit-Remaining: 42
   • Rejected: The gateway blocks the request and returns a 429 Too Many Requests status code with headers:
     Retry-After: 30 (wait 30 seconds before retrying)

10. Deep Dive

A. Distributed Concurrency Race Conditions

In a distributed environment, if two request threads query the token count at the same time:

1. Thread 1 reads token count: 1.
2. Thread 2 reads token count: 1.
3. Thread 1 updates token count to 0 and allows the request.
4. Thread 2 updates token count to 0 and allows the request.

This is a classic race condition that lets a client bypass the rate limit.

Mitigation: Use Redis Lua scripts. Redis executes Lua scripts in a single-threaded manner, ensuring token reads and updates run atomically.

B. Standard Rate-Limiting Headers

• X-RateLimit-Limit: The maximum number of requests allowed in the window.
• X-RateLimit-Remaining: The number of tokens remaining in the current window.
• X-RateLimit-Reset: The Unix epoch time when the rate limit window resets.
• Retry-After: The number of seconds the client must wait before making another request.

11. Production Examples

• Stripe API: Uses the Token Bucket algorithm to control request rates. If a client exceeds their limit, Stripe returns a 429 error.
• GitHub API: Enforces rate limits based on API tokens. Authenticated users get 5,000 requests per hour, while unauthenticated users are limited to 60.
• Shopify API: Uses a Leaky Bucket algorithm to smooth out API call frequencies, ensuring fair resource distribution across merchant stores.

12. Advantages

• Protects Infrastructure: Keeps backend services stable during traffic spikes.
• Mitigates DDoS Attacks: Identifies and drops excessive requests before they reach core application logic.
• Reduces Costs: Caps usage on paid third-party APIs, preventing billing surprises.

13. Limitations

• Increased Latency: Querying a centralized rate limit store (like Redis) adds latency to every incoming request.
• Single Point of Failure (SPOF): If the centralized rate limiter cache goes down, the entire system can fail.
• False Positives: Aggressive rate limits can block legitimate users (e.g. users sharing a public IP address behind a NAT gateway).

14. Trade-offs

• Token Bucket vs. Leaky Bucket: The Token Bucket allows short bursts of traffic, which is great for interactive applications, but can cause backend load spikes. The Leaky Bucket smooths traffic to a constant rate, protecting backends, but increases response times for queued requests.
• Centralized Cache vs. Local Memory: Centralized caching (Redis) ensures accurate rate limiting across all nodes but increases latency and complexity. Local memory limiting is fast and simple but allows clients to bypass limits by routing requests across different nodes.

15. Performance Considerations

• Minimize Redis Latency: Use Redis pipelining and Lua scripts to bundle rate-limiting checks into a single network roundtrip.
• Local Cache Buffering: In high-scale systems, nodes can buffer rate metrics locally and sync to Redis in batches (e.g. every 500ms) to reduce load on the cache cluster.

16. Failure Scenarios

• Redis Outage (Fallback to Allow): If the Redis rate limiter cluster crashes:
  Mitigation: Fallback to Fail-Open. Allow requests to pass through to prevent an outage, while falling back to local memory rate limiting on each node as a temporary defense.
• IP Spoofing Bypass: Clients can rotate IP addresses (e.g. using proxy networks) to bypass IP-based rate limits.
  Mitigation: Combine IP rate limiting with API keys, user session tokens, and CAPTCHA challenges on sensitive endpoints.

17. Best Practices

• Return standard rate-limiting headers in all HTTP responses to help clients adjust their request rates.
• Enforce strict limits on heavy operations (e.g. database writes, complex search queries) while leaving light operations (static assets) unthrottled.
• Use Lua scripts for atomic read-and-write operations in Redis.

18. Common Mistakes

• Failing to handle race conditions in distributed environments, allowing clients to bypass limits.
• Applying rate limits globally instead of scoping them per API key or user session.
• Setting rate limits too low, causing false positives that degrade the user experience.

19. Implementation (Thread-Safe Token Bucket)

Below is a complete implementation of a thread-safe Token Bucket rate limiter in Java, Python, and C++. The implementation dynamically calculates token refills based on elapsed time, handles concurrent requests, and enforces capacity limits.

20. Interview Questions & Answers

Q1. Compare the Token Bucket and Leaky Bucket algorithms. Under what scenario would you choose one over the other?

Answer:

• The Token Bucket allows short bursts of traffic because it retains tokens up to its capacity limit. It is ideal for most web APIs where user interactions can be bursty (e.g. loading a page with multiple assets).
• The Leaky Bucket smooths out traffic to a constant rate, queueing requests and releasing them at a fixed interval. It is ideal for systems that require strict, steady flow limits to protect sensitive legacy downstream databases.

Q2. How do you prevent concurrency race conditions in a distributed rate limiting cluster?

Answer: Concurrency race conditions occur when two separate application servers check a client's token count in Redis, read the same value, allow the requests, and update the count incorrectly.

To prevent this, use Redis Lua scripts. Because Redis runs Lua scripts atomically in a single thread, the read-evaluate-update sequence is guaranteed to run without interruption, eliminating race conditions.

Q3. What is the boundary problem of the Fixed Window algorithm, and how does the Sliding Window Counter solve it?

Answer: The Fixed Window algorithm counts requests within set time intervals (e.g. 1 minute). An attacker can bypass limits by sending a burst of requests right at the window boundary: sending 10 requests at 0:59 and another 10 at 1:01. Although both windows technically stay under the limit of 10, the server is overloaded with 20 requests in 2 seconds.

The Sliding Window Counter solves this by calculating request rates dynamically. It blends the count of the current window with the count of the previous window based on the current timestamp, ensuring the rate is calculated across a rolling 1-minute window.

21. Practice Exercises

• Exercise 1 (Easy): Trace the rate limit headers returned to a client when they make their 3rd request in a window with a limit of 10 requests.
• Exercise 2 (Medium): Modify the Python TokenBucketRateLimiter code to support dynamic cost values. For example, heavy write queries can consume 3 tokens while light read queries consume 1 token.
• Exercise 3 (Hard): Write a Python prototype of a Sliding Window Log rate limiter using an in-memory deque to store and prune request timestamps.

22. Challenge Problem

The Multi-Tier Distributed Rate Limiting Challenge: You are designing a global rate limiter for an e-commerce platform processing 1,000,000 requests per minute across 10 regions.

If you query a central Redis cluster for every request, the network roundtrips between regions will add significant latency, degrading the user experience.

• Propose a multi-tier rate limiting architecture that balances accuracy with low latency.
• Draw a diagram showing how you would use local memory caches on application nodes to buffer rates, and how they sync with Redis asynchronously.
• Explain how you would handle synchronization lag between region caches to prevent users from bypassing limits.

23. Summary

Rate limiting is an essential security and reliability pattern for web services. Choosing the right algorithm—Token Bucket for bursty traffic, Leaky Bucket for steady throughput, or Sliding Window for high accuracy—is key to matching your application's requirements. Implementing atomic scripts in distributed caches like Redis ensures limits are enforced accurately across clusters.

24. Cheat Sheet

Algorithm	Allows Bursts?	Memory Complexity	Best Use Case
Token Bucket	Yes	$O(1)$	Standard API rate limiting (e.g. Stripe)
Leaky Bucket	No (Smooths out traffic)	$O(Q)$ (queue size)	Protecting legacy backend databases
Fixed Window	Yes (At boundaries)	$O(1)$	Simple, low-precision quotas
Sliding Window	No (Accurate boundaries)	$O(1)$ (counter based)	High-precision user rate limits

25. Quiz

26. Further Reading

• Stripe Blog: How we build rate limiters for APIs.
• Redis Eval command documentation (Lua Scripting).
• System Design Interview — Alex Xu (contains a detailed chapter on rate limiter design).

27. Next Lesson Preview

Once we protect services using rate limiting, we must coordinate how microservices locate each other. In the next lesson, we will look at Service Discovery—the dynamic routing catalog that registers microservice network addresses.