Rate Limiting Algorithms: Selection & Comparison

Hello! Welcome back to our course on designing security products.

In our last lesson, we architected a comprehensive, multi-layer DDoS scrubbing pipeline. We established that a crucial component of this pipeline is the "Behavioral Layer," which uses stateful analysis to distinguish legitimate users from attackers. A core function of this layer is rate limiting—enforcing policies on the rate of incoming traffic.

Today, we will dive deep into the engine room of rate limiting. Our learning outcome is to compare rate limiting algorithms (e.g., token bucket, leaky bucket) and select appropriate ones for different attack profiles.

We will explore the fundamental algorithms that power rate limiting systems, analyzing their trade-offs in terms of performance, memory usage, and precision. By the end of this lesson, you will understand not just how these algorithms work, but why you would choose one over another when architecting a defense against a specific type of DDoS attack.

1. An Overview of Rate Limiting Algorithms

At its core, a rate limiting algorithm is a set of rules for deciding whether to accept or reject a request based on its arrival rate. While the goal is simple, the implementation details have significant implications for how your system handles both legitimate bursts of traffic and malicious floods.

To start, let's get a high-level overview of the five most common rate limiting algorithms. The following video provides a clear and concise introduction to each one.

Now that you have a mental model for each algorithm, let's dissect them from a system design perspective, focusing on the trade-offs that matter when building a DDoS mitigation service.

2. A Deeper Dive into the Algorithms

For a builder, a conceptual understanding is not enough. We need to understand the implementation trade-offs, memory complexity, and precision of each approach. The following article provides an excellent, in-depth analysis.

Let's consolidate our understanding of these algorithms.

Token Bucket

• Mechanism: A bucket is filled with tokens at a constant rate. Each incoming request consumes one token. If the bucket is empty, the request is rejected.
• Key Behavior: It allows for bursts. If a client has been idle, the bucket fills up, allowing the client to send a burst of requests up to the bucket's capacity. After the burst, the client is limited to the token refill rate.
• Pros:
  • Accommodates bursty but legitimate traffic patterns.
  • Memory efficient: requires only a few variables per key (token count, last refill time). O(1) space.
• Cons:
  • Tuning two parameters (bucket size and refill rate) can be complex.
• DDoS Use Case: Ideal for Layer 7 rate limiting where you want to allow legitimate users to load page assets quickly (a burst) but throttle a bot that is sending a sustained, high-rate flood of requests.

Leaky Bucket

• Mechanism: Requests are added to a fixed-size queue (the bucket). The queue is processed at a constant, fixed rate (it "leaks"). If the queue is full, new requests are rejected.
• Key Behavior: It smooths out traffic. Bursts are not processed immediately; they are queued and handled at the same steady rate as all other traffic. This introduces latency.
• Pros:
  • Provides excellent protection for downstream services that cannot handle bursts.
• Cons:
  • Introduces latency for all burst traffic.
  • Memory usage is O(n) where n is the queue size.
• DDoS Use Case: Perfect for protecting a sensitive or resource-intensive backend API endpoint (e.g., a search function that hits a database heavily). By forcing all traffic into a steady stream, you prevent the backend from being overwhelmed by a sudden spike.

Fixed Window Counter

• Mechanism: A simple counter for a specific time window (e.g., requests per minute). The counter resets at the start of a new window.
• Key Behavior: Very simple, but vulnerable to a "boundary attack." An attacker can send limit requests at the end of window N and another limit requests at the start of window N+1, effectively achieving twice the intended rate.
• Pros:
  • Extremely simple to implement and understand.
  • Very memory efficient (O(1) space).
• Cons:
  • Imprecise due to the boundary issue.
• DDoS Use Case: Best used as a coarse, inexpensive first-pass filter. For example, a very high, non-critical limit (e.g., 10,000 requests/min/IP) can be implemented with this method to catch grossly abusive sources without much overhead.

Sliding Window Log

• Mechanism: Stores a timestamp for each request in a log (e.g., a Redis sorted set). To check a new request, all timestamps outside the sliding window are removed, and the size of the remaining log is checked against the limit.
• Key Behavior: Extremely precise. It perfectly enforces the rate limit over a moving time window, completely solving the boundary issue of the fixed window.
• Pros:
  • Perfectly accurate enforcement.
• Cons:
  • High memory usage: O(n) space, where n is the number of allowed requests in the window. This can be prohibitive for millions of keys.
• DDoS Use Case: Ideal for situations requiring high precision, such as limiting login attempts to prevent brute-forcing (e.g., "max 5 attempts per user in the last 10 minutes"). The number of keys (users actively logging in) is relatively low, so the memory cost is acceptable.

Sliding Window Counter

• Mechanism: An approximation of the Sliding Window Log that provides a balance between accuracy and memory efficiency. It uses a weighted sum of the counter from the previous window and the counter from the current window. The formula is: $$\text{estimated\_rate}=(\text{rate\_in\_previous\_window}\times (1-\text{progress\_in\_current\_window}))+\text{rate\_in\_current\_window}$$
• Key Behavior: Smooths out the boundary issue of the fixed window without the high memory cost of the log-based approach.
• Pros:
  • Good accuracy with O(1) memory usage, making it highly scalable.
• Cons:
  • It is still an approximation and can, in worst-case scenarios, allow slightly more traffic than the configured limit.
• DDoS Use Case: This is often the workhorse for large-scale DDoS mitigation and API gateways (used by providers like Cloudflare). It provides a very good balance for general-purpose rate limiting across millions of IPs or API keys.

3. Selecting the Right Algorithm for the Job

The choice of algorithm is not academic; it's a critical design decision based on the specific threat you are mitigating and the characteristics of the service you are protecting.

To help structure this decision-making process, let's look at a clear decision tree.

Let's apply this thinking to specific DDoS attack profiles:

This table from the same article offers a final, compact summary of the trade-offs.

Conclusion

In this lesson, we dissected the core algorithms that power rate limiting systems, moving from high-level concepts to the specific architectural trade-offs involved in their implementation.

Key Takeaways:

• No Single Best Algorithm: The choice is a trade-off between allowing legitimate bursts, protecting sensitive backends, memory efficiency, and enforcement precision.
• Token Bucket for Bursty APIs: It accommodates legitimate user bursts while enforcing a sustained average rate, making it a default choice for many public-facing APIs.
• Leaky Bucket for Smoothing: It protects backends that cannot handle traffic spikes by queuing requests and processing them at a constant rate, trading latency for stability.
• Window-Based Algorithms for Precision vs. Scale:
  • Fixed Window is simple but imprecise.
  • Sliding Window Log is perfectly precise but memory-intensive.
  • Sliding Window Counter offers a scalable, O(1) memory compromise, making it a workhorse for large-scale systems.
• Match the Algorithm to the Threat: Your choice should be dictated by the attack profile you're defending against and the nature of the resource you're protecting.

Preview of the Next Lesson:

Now that we have scrubbed malicious traffic using techniques like rate limiting, we face a new architectural challenge: how do we get the cleaned, legitimate traffic back to the origin servers? In our next lesson, we will design mechanisms for returning cleaned traffic to origin servers, considering latency, security, and protocol transparency. We'll explore techniques like GRE tunneling, proxying, and Direct Server Return.