In our last lesson, we configured an API Gateway, establishing it as the front door to our microservices. One of its crucial roles is rate limiting—protecting our backend services from being overwhelmed. We added a basic rate-limiting plugin, but in a real-world, high-scale system, the choice of how you rate limit is a critical design decision with significant trade-offs.
This lesson dives deep into that "how." Your goal is to compare the most common rate limiting algorithms: Token Bucket, Leaky Bucket, and the Sliding Window family. We will dissect their mechanics, analyze their performance characteristics, and discuss their ideal use cases. Understanding these trade-offs is not just an academic exercise; it's a frequent and fundamental topic in system design interviews for senior engineering roles.
A Baseline: The Fixed Window Counter
To appreciate the more sophisticated algorithms, let's start with the simplest approach: the Fixed Window Counter.
The concept is straightforward:
- Divide time into fixed, non-overlapping intervals (e.g., 60-second windows).
- For each client, maintain a counter for the current window.
- Increment the counter on each request.
- If the counter exceeds a predefined limit, reject the request.
- When a new time window begins, reset the counter to zero.
The video "Five Rate Limiting Algorithms" from the Hello Byte channel provides a clear walkthrough of this mechanism.
Five Rate Limiting Algorithms ~ Key Concepts in System Design
This video explains the Fixed Window Counter algorithm with a simple, step-by-step example.
Watch the segment from the third algorithm. Pay close attention to how the counter increments within a window and resets when a new window starts. Crucially, notice the example given of the "boundary problem," which is the algorithm's primary weakness.
The main issue, as highlighted in the video, is the boundary burst problem. A client could make their full quota of requests at the very end of one window and immediately make another full quota at the start of the next. For a limit of 100 requests/minute, this could allow 200 requests in just a couple of seconds, potentially overwhelming your service.
Despite this flaw, the algorithm's simplicity and low memory footprint (just one counter per client per window) make it suitable for low-stakes scenarios, like internal admin tools.
Achieving Precision: The Sliding Window Algorithms
To solve the boundary burst problem, we can use a "sliding" window that isn't tied to fixed intervals. There are two main flavors of this approach.
1. Sliding Window Log
This is the most accurate, but also the most resource-intensive, sliding window variant. It works by logging the exact timestamp of every request.
How it works:
- For each client, store a log of request timestamps (typically in a sorted set).
- When a new request arrives, discard all timestamps from the log that are older than the window duration (e.g., older than 60 seconds).
- Count the remaining timestamps in the log.
- If the count is less than the limit, accept the request and add its timestamp to the log. Otherwise, reject it.
Five Rate Limiting Algorithms ~ Key Concepts in System Design
The Hello Byte video also offers an excellent conceptual explanation of the Sliding Window Log.
Watch the segment on the fourth algorithm. This visualization will help you understand how the window "slides" by removing old timestamps.
- Pros: Perfect accuracy. It completely eliminates the boundary burst problem because it always considers the true request rate over the preceding interval.
- Cons: High memory cost. Storing a timestamp for every single request can become very expensive, especially for high-traffic clients or long window durations. This makes it impractical for many large-scale applications.
2. Sliding Window Counter
This algorithm provides a clever compromise, offering much better accuracy than the Fixed Window without the high memory cost of the Sliding Window Log. It approximates the true sliding window by considering a weighted value of the current and previous windows.
The formula is:rate ≈ (previous_window_count * (1 - percentage_into_current_window)) + current_window_count
For example, if a client made 80 requests in the previous minute, and is 75% of the way through the current minute with 30 requests so far, the estimated rate is (80 * (1 - 0.75)) + 30 = 20 + 30 = 50.
This approach is extremely popular in practice. The following article from Redis, a tool you'd almost certainly use to implement a distributed rate limiter, provides an excellent walkthrough. Since you're proficient in JavaScript, the code will be very familiar.
Building a Rate Limiter with Redis
This section of the Redis tutorial details the Sliding Window Counter algorithm, including its weighted formula and a practical implementation using Redis.
Read the section on the Sliding Window Counter. Pay special attention to the "Code walkthrough" and the "Key details," which explain how two simple counters and a TTL of twice the window size are used to achieve this smooth approximation.
- Pros: Balances accuracy and performance. It smooths out boundary bursts effectively with a very low memory footprint (only two counters per client).
- Cons: It's an approximation. While very good, it's not perfectly accurate and assumes a relatively even distribution of requests. For most public APIs, this is an excellent trade-off.
Controlling Flow: Token Bucket vs. Leaky Bucket
The final two algorithms, Token Bucket and Leaky Bucket, are classics of traffic shaping. They are less about counting requests and more about managing flow and burstiness.
1. Token Bucket
This is one of the most widely used and flexible algorithms. It is favored by major providers like AWS and Stripe and is a go-to choice in many system design interviews.
How it works:
- Each client has a "bucket" with a certain capacity of "tokens."
- Tokens are added to the bucket at a constant "refill rate" (e.g., 10 tokens per second).
- When a request arrives, it must consume one token from the bucket.
- If the bucket has a token, the request is allowed, and the token count is decremented.
- If the bucket is empty, the request is rejected.
- The bucket cannot hold more tokens than its capacity.
The key advantage is its ability to handle bursts. A client that has been idle can accumulate tokens up to the bucket's capacity, allowing them to send a sudden burst of requests. The long-term average rate, however, is capped by the refill rate.
Implementing this correctly in a distributed system requires ensuring atomicity. The sequence of reading the token count, calculating the refill, checking the limit, and updating the count must happen as a single, indivisible operation to avoid race conditions. This is a perfect use case for Lua scripting in Redis.
Design a Distributed Rate Limiter w/ a Ex-Meta Staff Engineer: System Design Breakdown
In this video, an ex-Meta Staff Engineer designs a distributed rate limiter and explains why Token Bucket is often the preferred choice. He also details the implementation with Redis and the critical role of Lua scripting.
First, watch the comparison of the algorithms from the heart of rate limiting. He provides a clear explanation of why Token Bucket is so powerful. Then, watch the implementation details from how do we actually implement this?, which covers the use of Redis for shared state and, most importantly, the race condition and how Lua scripting solves it.
2. Leaky Bucket
The Leaky Bucket algorithm works in the opposite way. Instead of accommodating bursts, it smooths them out entirely.
How it works:
- Imagine a bucket with a hole in the bottom that leaks at a constant rate.
- Incoming requests are like water being poured into the bucket.
- Requests are processed (i.e., "leak" out of the bucket) at a fixed, steady rate.
- If requests arrive faster than they can be processed, they queue up in the bucket.
- If the bucket (queue) becomes full, new incoming requests are discarded.
This algorithm enforces a strict, constant output rate, regardless of how bursty the input traffic is. This makes it ideal for protecting downstream services that have a fixed throughput and cannot handle traffic spikes.
Building a Rate Limiter with Redis
The Redis tutorial provides an excellent explanation of the Leaky Bucket algorithm and its implementation, contrasting it with the Token Bucket.
Read the section on the Leaky Bucket. Note how it's described as the "inverse of the token bucket." The core use case is traffic shaping for a predictable output rate, which is a different goal than allowing bursts.
Summary and Comparison
Choosing the right algorithm depends entirely on your specific requirements for accuracy, memory, complexity, and burst handling.
The Redis article provides a fantastic summary table.
Building a Rate Limiter with Redis
This final section provides a side-by-side comparison and a clear guide for choosing an algorithm.
First, review the comparison table carefully. It summarizes the key trade-offs at a glance. Then, read the section Choosing the right rate-limiting algorithm for a concise decision-making framework.
This framework is precisely what an interviewer looks for: a clear articulation of the trade-offs and a justified choice based on system constraints.
Conclusion
In this lesson, we dissected the core algorithms that power rate limiting. You now have the knowledge to compare them based on their distinct behaviors and resource requirements, a skill essential for designing robust, scalable systems.
Key Takeaways:
- Fixed Window: Simple, low-memory, but suffers from boundary bursts.
- Sliding Window Log: Perfectly accurate but memory-intensive.
- Sliding Window Counter: A pragmatic, memory-efficient approximation that smooths boundary bursts.
- Token Bucket: Highly flexible, allows for controlled bursts while enforcing a steady average rate. It's a popular choice for public APIs.
- Leaky Bucket: Enforces a strict, constant output rate, ideal for protecting sensitive downstream services from any traffic variation.
- Atomicity is Key: For distributed bucket-based or counter-based algorithms, using atomic operations (like Lua scripts in Redis) is non-negotiable to prevent race conditions.
In our next lesson, we will explore another critical resilience pattern: the Circuit Breaker. While rate limiting protects a service from being overwhelmed by its clients, the Circuit Breaker pattern protects a system from a service that is failing, preventing catastrophic cascading failures across your entire architecture.