Design a Rate Limiter

In a world where APIs are the backbone of modern software, protecting them from accidental overloads and malicious attacks is a non-negotiable requirement for reliability and security. A rate limiter is a traffic cop for your service, controlling how many requests a client can make in a given timeframe. Designing an effective system involves choosing the right algorithm, managing state across a distributed architecture, and communicating limits gracefully to users—skills that are fundamental for building robust systems and a common topic in technical interviews.

Core Concept 1: Foundational Rate Limiting Algorithms

The choice of algorithm dictates the behavior, efficiency, and fairness of your rate limiter. Three primary algorithms form the foundation: fixed window, sliding window, and token bucket.

The fixed window counter is the simplest algorithm. It divides time into discrete, non-overlapping windows (e.g., 1-minute blocks) and counts requests within each window. For example, with a limit of 100 requests per minute, a new counter starts at zero for each new minute. While easy to implement and understand, it suffers from a critical flaw: requests can burst at the edges of windows. A user could make 100 requests at 0:59 and another 100 at 1:01, effectively making 200 requests in two seconds, violating the spirit of the 100-per-minute limit.

To combat this edge-case bursting, the sliding window log algorithm tracks a timestamp for each request. When a new request arrives, you purge timestamps older than the window (e.g., one minute) and count the remaining timestamps. If the count is below the limit, the request is allowed, and its timestamp is logged. This provides perfect accuracy and fairness but can be memory-intensive, as it requires storing a potentially large list of timestamps for every user or key. A more memory-efficient variant, the sliding window counter, hybridizes the fixed and sliding approaches. It approximates the current window's request rate by using the count from the previous window, prorated based on how much of the current window has elapsed, and adding it to the current window's count. This balances accuracy with lower storage overhead.

The token bucket algorithm offers a different model focused on smoothing bursts. Imagine a bucket that holds a maximum number of tokens. Tokens are added to the bucket at a steady refill rate (e.g., 10 tokens per second). When a request arrives, it tries to take a token from the bucket. If tokens are available, the request is processed and the token is consumed. If the bucket is empty, the request is denied. This allows for controlled bursts up to the bucket's capacity while ensuring the long-term average rate does not exceed the refill rate. It’s particularly useful for network traffic shaping and scenarios where short, controlled bursts are acceptable.

Core Concept 2: Distributed Rate Limiting with Shared State

In a microservices or load-balanced environment, your application runs on multiple servers. A naive rate limiter that only tracks counters in local memory would be ineffective, as a user could send requests to different servers and each would have an incomplete view. Distributed rate limiting solves this by using a fast, centralized data store accessible by all application instances.

Redis is the quintessential tool for this purpose due to its speed, support for atomic operations, and built-in key expiration. Instead of storing a counter in local memory, each server interacts with Redis to check and update the user's count. The key challenge is ensuring atomicity—the operations "check current count" and "increment count" must happen as a single, uninterruptible unit to prevent race conditions where two simultaneous requests both see a count of 99 and allow the 100th request.

Redis provides atomic commands like INCR and EXPIRE to handle this. A common pattern is to use the INCR command on a key (e.g., user:123:minute). If the key doesn't exist, Redis creates it and sets its value to 1. You then pair this with the EXPIRE command to set a time-to-live (TTL) equal to your rate limit window (e.g., 60 seconds). To make the check-and-increment atomic, you can use a Redis transaction or, more efficiently, a Lua script that executes on the Redis server itself. The script would check the current count, increment it if under the limit, and handle setting the initial expiration, all in one step.

Core Concept 3: System Design Decisions and Integration

Choosing an algorithm is only part of the design. You must also define the granularity of your limits. Will you limit by user ID (for authenticated APIs), by IP address (for public endpoints), by API key, or by a combination? Each has trade-offs: user IDs are fair but require authentication; IPs can affect multiple users behind a shared network (NAT). You often need multiple layers, such as a strict IP-level limit to prevent DDoS and a more generous user-level limit for authenticated traffic.

Communication is vital. When a request is rate-limited, your API should respond with the standard HTTP status code 429 Too Many Requests. Crucially, you should include helpful headers like Retry-After (suggesting how many seconds to wait) or X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset to inform the client of their current quota. This transparency allows well-behaved clients to self-regulate.

Finally, consider graceful degradation. A rate limiter should fail open, not closed. If your Redis cluster goes down, your service should typically continue to process requests, perhaps with a fallback to a less accurate local limit or no limit at all, rather than rejecting all traffic. The risk of temporary overload is often preferable to a complete outage. Monitoring and alerting on the health of the rate-limiting infrastructure are essential.

Common Pitfalls

1. Choosing the Wrong Algorithm for the Use Case: Using a fixed window counter for an API where burst protection is critical will lead to the "window edge" problem described earlier. Conversely, implementing a full sliding window log for a high-traffic, low-limit scenario is an unnecessary waste of memory. Always map the algorithm's behavior to your specific requirements for fairness and burst tolerance.

1. Race Conditions in Distributed Counters: Simply reading a value from Redis and then incrementing it in two separate commands is a classic bug. Between the read and the write, another server could have changed the counter, leading to an incorrect allowance. Correction: Always use atomic operations provided by your data store, such as Redis's INCR within a Lua script or atomic compare-and-set operations.

1. Neglecting to Communicate Limits: Denying a request with a bare 429 error leaves clients guessing. They may retry immediately, creating more load, or give up unnecessarily. Correction: Implement the standard 429 status with Retry-After and X-RateLimit-* headers. This turns the rate limiter from a black box into a cooperative component of your API contract.

1. Creating a Single Point of Failure: Placing your entire rate-limiting state in one Redis instance creates a critical vulnerability. If it fails, your rate limiter fails, which could bring down your API if you fail closed. Correction: Design for high availability using Redis Sentinel or Redis Cluster. More importantly, implement the fail-open pattern so your service remains partially available even if the rate-limiting backend is down.

Summary

• The three core algorithms each have distinct trade-offs: Fixed window is simple but allows bursts at window edges; sliding window is accurate but can be costly; token bucket smoothly controls burst size and average rate.
• For systems with multiple servers, distributed rate limiting is essential. Use a fast, centralized store like Redis with atomic operations (e.g., INCR with EXPIRE or Lua scripts) to maintain accurate, shared counters.
• Key design decisions include setting the granularity of limits (user, IP, API key) and implementing clear client communication via HTTP 429 status codes and X-RateLimit-* headers.
• Always design your rate limiter to fail open to prevent it from becoming a single point of failure that causes a full system outage during backend issues.