Token Bucket vs. Window Algorithms: Trade-offs Explained

Hello! Welcome to the next lesson in our module on Rate Limiting and Traffic Shaping.

In our previous lessons, we dove deep into the implementations of three rate limiting algorithms:

• Fixed-Window Counter: Simple and memory-efficient, but prone to allowing double the request rate at window boundaries.
• Sliding-Window Log: Perfectly accurate by tracking every request timestamp, but at a high memory cost (O(N) per client).
• Sliding-Window Counter: A clever, memory-efficient (O(1)) approximation of the sliding-window log, balancing accuracy and scalability.

Today, we'll introduce the last major algorithm in our toolkit, the Token Bucket, which is exceptionally good at handling bursty traffic. With all the algorithms covered, our primary goal for this lesson is to synthesize this knowledge. The learning outcome is to compare the trade-offs (accuracy, memory, complexity) between token bucket, fixed-window, and sliding-window algorithms. By the end, you'll have a robust mental framework for choosing the right algorithm for any given scenario—a crucial skill for a system design interview at a place like Anthropic.

---

1. An Overview of the Algorithms

Before we dive into the final algorithm, let's get a quick visual overview of all the common approaches.

We've already covered the three on the right. Now let's focus on the bucket-based approaches.

---

2. The Token Bucket Algorithm: Allowing Bursts

The Token Bucket algorithm is one of the most popular choices for public APIs, including many at AWS. Its design elegantly accommodates the bursty nature of real-world clients (e.g., a user rapidly clicking, or a batch job starting).

The concept is straightforward:

• Each client has a bucket with a fixed capacity (e.g., 100 tokens).
• Tokens are added to the bucket at a constant refill rate (e.g., 10 tokens per second).
• Each incoming request attempts to consume one token from the bucket.
• If a token is available, the request is allowed.
• If the bucket is empty, the request is rejected.

The key insight is that an idle client accumulates tokens up to the bucket's capacity. This "saved" capacity can then be used to handle a sudden burst of requests.

The following video provides an excellent conceptual breakdown.

As you can see, this algorithm has two simple but powerful knobs to tune:

1. Bucket Capacity: The maximum number of requests you're willing to absorb in a burst.
2. Refill Rate: The long-term average request rate you want to enforce.

This is highly relevant to your work on systems like Rudi. When managing inference capacity, you're not just dealing with a steady stream of requests. You have to handle sudden bursts from clients while ensuring the overall load on the underlying models remains stable. The token bucket algorithm provides a formal model for this exact behavior.

---

3. The Leaky Bucket Algorithm: Smoothing Output

For completeness, it's essential to contrast the Token Bucket with its close cousin, the Leaky Bucket. While they sound similar, they serve opposite purposes.

• Token Bucket allows bursty input and smooths the long-term average rate.
• Leaky Bucket enforces a constant output rate, smoothing out any bursty input into a steady stream.

Imagine a bucket with a hole in the bottom. Requests "fill" the bucket, and they "leak" out of the hole at a fixed rate to be processed. If requests arrive too quickly and the bucket overflows, they are rejected. This is implemented as a FIFO queue with a fixed processing rate.

This distinction is crucial. You'd use a Leaky Bucket to protect a downstream service that cannot handle bursts, like a third-party payment gateway or an email sending service. The trade-off is that bursty requests from the client will experience added latency as they sit in the queue.

This video gives a clear explanation of the Leaky Bucket.

---

4. The Grand Comparison: A Trade-Off Matrix

Now that we understand all five algorithms, we can put them side-by-side and analyze their trade-offs across the dimensions of accuracy, memory, complexity, and burst handling. This is the kind of analysis you'll be expected to perform in a system design interview.

The following resource provides an excellent and concise comparison table.

Let's synthesize that information into our own comprehensive table, focusing on the key characteristics.

Algorithm	Key Characteristic	Accuracy	Memory per Client	Burst Handling	Complexity
Fixed Window	Simplest; counts in discrete time blocks.	Poor. Can allow up to 2x the limit at window boundaries.	O(1) (1 key)	Poorly. Boundary bursts are a major flaw.	Very Low
Sliding Window Log	Most accurate; logs every request timestamp.	Exact. Perfect enforcement.	O(N) (where N is the limit)	Strict. No bursts are allowed beyond the limit.	Medium
Sliding Window Ctr	Memory-optimized approximation of the log.	Good. Near-exact, but assumes even request distribution.	O(1) (2 keys)	Smooths boundary bursts effectively.	Low
Token Bucket	Allows and controls bursts via a refillable bucket.	Good. Enforces a long-term average rate.	O(1) (2 fields in a hash)	Excellent. Explicitly designed to allow controlled bursts.	High (if using Lua)
Leaky Bucket	Enforces a constant output rate via a queue.	Good. Enforces a steady processing rate.	O(N) (queue size)	None. Smooths all bursts into a steady output stream.	High (if using Lua)

This table is your cheat sheet for rate limiting algorithms. Understanding these trade-offs is far more important than memorizing every line of implementation code.

5. A Practical Decision Framework

So, in an interview, how do you decide which one to use? You can frame your decision-making process by asking a series of questions.

The following article opens with a brilliant decision tree that does exactly this.

Let's walk through that logic:

1. Do my legitimate clients have bursty traffic patterns?

   • Yes: Use Token Bucket. It's designed to forgive legitimate bursts while enforcing a long-term average. This is the default for most public APIs.
   • No: Move to the next question.

2. Do I need to protect a downstream service by ensuring a smooth, constant output rate?

   • Yes: Use Leaky Bucket. It will queue incoming bursts and process them at a steady pace.
   • No: Move to the next question.

3. Do I need exact enforcement (e.g., for a payment or auth endpoint)?

   • Yes: Use Sliding Window Log. You're willing to pay the O(N) memory cost for perfect precision.
   • No: Move to the next question.

4. Do I need a "good enough" approximation that is highly memory-efficient for high-cardinality keys (e.g., millions of API keys)?

   • Yes: Use Sliding Window Counter. It offers the best balance of accuracy and O(1) memory usage. This is the workhorse for large-scale systems like Cloudflare's.
   • No/Unsure: Your remaining option is the simplest.

5. Is this a low-stakes limit where simplicity trumps accuracy?

   • Yes: Use Fixed Window Counter. It's easy to implement and understand, but be prepared to articulate its boundary burst weakness.

Mastering this decision framework will allow you to confidently justify your choice of rate-limiting algorithm in any system design context.

---

Conclusion

In this lesson, we completed our survey of core rate-limiting algorithms and, most importantly, built a framework for comparing them.

Key Takeaways:

• Token Bucket is for Bursts: It excels at handling bursty clients by separating the concepts of burst capacity and average rate. It's the go-to for most public APIs.
• Leaky Bucket is for Smoothing: It protects downstream systems by transforming bursty inputs into a constant, predictable output stream.
• There is a Spectrum of Trade-offs: You can choose between five common algorithms, each offering a different balance of accuracy, memory usage, burst handling, and implementation complexity.
• Ask the Right Questions: The choice of algorithm isn't arbitrary. It follows from the specific requirements of the system, which you can uncover by asking targeted questions about traffic patterns, precision needs, and scale.

Next Lesson Preview

We now have a deep understanding of the algorithms themselves. However, in a system like Bedrock, these algorithms don't run on a single server; they run in a distributed environment. This introduces new challenges.

In our next lesson, we will tackle this head-on. The learning outcome is to design a distributed rate limiting system using an external store like Redis, focusing on atomicity. We will discuss why atomicity is non-negotiable and how to achieve it, ensuring your rate limiter is correct even when scaled across dozens of servers.