Rate Limiting: Token Bucket vs. Leaky Bucket

Framing the Problem: What is a Rate Limiter?

A rate limiter is a gatekeeper for your services. It controls the amount of traffic a client can send to an API in a given time frame. For an interview, you must start by clarifying the requirements before jumping to solutions.

Let's watch a segment from a mock system design interview that does an excellent job of breaking down the problem.

As the video demonstrates, a strong interview answer begins with structure. Here’s a summary of the key requirements we'll design for:

• Functional:
  • Identify clients by IP, user ID, or API key.
  • Limit requests based on configurable rules (e.g., 100 requests/min/user).
  • Return an HTTP 429 Too Many Requests error when the limit is exceeded.
• Non-Functional:
  • Low Latency: The check must be fast (e.g., <10ms) to avoid slowing down valid requests.
  • High Availability: The system should favor being online over being perfectly consistent (an AP system in CAP theorem terms). A few extra requests getting through is better than the whole system going down.
  • Scalability: Must handle a high volume of traffic (e.g., 1 million requests per second).
  • Distributed: Must work across multiple instances of our service.

Architectural Placement: Where Does the Rate Limiter Live?

Before diving into algorithms, we must decide where to place our rate limiter. This architectural choice has significant implications for latency, complexity, and effectiveness.

To summarize the trade-offs:

For our design, we'll adopt the standard production pattern: implementing the rate limiter at the API Gateway. This provides centralized protection efficiently without adding latency to every service-to-service call.

Core Algorithms: Token Bucket vs. Leaky Bucket

Now we arrive at the core of the problem: the algorithm that decides whether to allow or reject a request. While several algorithms exist, we'll focus on the two most important ones for an interview setting: Token Bucket and Leaky Bucket.

1. Token Bucket

Imagine each user has a bucket of a fixed size. This bucket is continuously refilled with "tokens" at a steady rate.

• Each incoming request attempts to take one token from the bucket.
• If a token is available, the request is allowed, and the token count decreases.
• If the bucket is empty, the request is rejected.

This algorithm is defined by two parameters:

• Bucket Size: The maximum number of tokens the bucket can hold. This defines the maximum burst of requests allowed.
• Refill Rate: The rate at which tokens are added to the bucket (e.g., 10 tokens per second). This defines the sustained average rate.

The key advantage of the token bucket is its flexibility. It allows for legitimate bursts of traffic (e.g., a web app making several API calls on page load) while still enforcing a long-term average rate.

2. Leaky Bucket

Now, let's look at a different model. Imagine a bucket with a hole in the bottom.

• Incoming requests are like water being poured into the bucket. The bucket represents a queue (First-In, First-Out).
• Requests "leak" out of the bottom at a fixed, constant rate to be processed.
• If requests arrive faster than they are processed, the bucket fills up.
• If the bucket is full when a new request arrives, it "overflows" and the request is discarded.

The primary characteristic of the leaky bucket is that it enforces a constant output rate, regardless of how bursty the input is.

Head-to-Head Comparison

This visual and table summarize the critical differences, which are prime material for an interview trade-off discussion.

For our general-purpose API, the Token Bucket algorithm is the superior choice. It provides the flexibility to handle legitimate client-side bursts while still protecting our backend, which is why it's the de-facto standard for many public-facing APIs.

Implementation in a Distributed System

Choosing the token bucket algorithm is just the first step. For a senior role, you must explain how to implement it in a distributed, scalable, and fault-tolerant way.

This introduces two major challenges:

1. Shared State: Where do we store the token buckets for millions of users so all our gateway instances see the same data?
2. Race Conditions: What happens if two requests for the same user arrive at two different servers at the exact same time?

The solution to both is to use a fast, centralized, in-memory datastore like Redis.

Production-Ready Implementation Summary:

1. Centralized State: Use a Redis cluster to store the token bucket state (token_count, last_refill_timestamp) for each client key (e.g., user_id:123). Redis is chosen for its low latency.

2. Atomicity: To prevent race conditions where two servers read the old token count simultaneously, perform the entire check-and-update logic inside a Redis Lua script. This guarantees the operation is atomic. A server sends a single command to Redis: "For this user, calculate new tokens, check if one is available, decrement if so, and tell me the result."

3. Scalability: A single Redis instance won't scale to millions of RPS. Shard the data across multiple Redis nodes. A common strategy is to use consistent hashing on the client key (user_id or ip_address) to determine which Redis shard holds that client's bucket. Redis Cluster handles this for you automatically.

4. Fault Tolerance: To prevent a single Redis node failure from taking down the system, use replication. Each primary shard has one or more replica shards. If a primary fails, a replica is promoted. This is an Available-Partition Tolerant (AP) system, prioritizing availability. A few requests might be miscounted during a failover, but the system remains online.

Closing the Loop: Responding to the Client

Finally, when a request is rejected, we must inform the client properly. This is not just about returning an error; it's about providing actionable feedback.

When a client is rate-limited:

• Fail Fast: Immediately reject the request. Do not queue it, as this adds complexity and can lead to cascading failures.
• Status Code: Return 429 Too Many Requests.
• Response Headers: Include informative headers to help the client implement intelligent retry logic:
  • X-RateLimit-Limit: The total request limit for the window.
  • X-RateLimit-Remaining: The number of requests remaining in the window.
  • X-RateLimit-Reset: A Unix timestamp indicating when the limit will reset.
  • Retry-After: The number of seconds the client should wait before retrying.

Conclusion

In this lesson, you've designed a complete, distributed, and robust rate-limiting system ready for a senior-level interview discussion.

Key Takeaways:

• Rate limiting is a critical mechanism for ensuring API stability, security, and fairness.
• The Token Bucket algorithm is generally preferred for APIs as it allows for legitimate bursts while enforcing an average rate. Leaky Bucket is better for smoothing traffic into a constant stream.
• A production-ready rate limiter must be distributed. This requires a centralized, low-latency store like Redis.
• Handling race conditions with atomic operations (like Redis Lua scripts) is non-negotiable for correctness.
• Scalability is achieved through sharding, and fault tolerance is achieved through replication, embracing a "fail-open" or "fail-close" strategy depending on business needs.

Preview of the Next Lesson:

Our rate limiter now correctly tells clients to "try again later." But how should a client act on that? Simply retrying immediately could prolong the overload. In our next lesson, we'll look at the client-side of resilience by learning how to implement a retry strategy with exponential backoff and jitter, a pattern that prevents clients from causing a "thundering herd" problem.