Too Many Req: A Bucket List Guide to Building a Rate Limiter

Hello, I'm Maneshwar. I'm developing git-lrc, a Micro AI code reviewer that operates on every commit. It's free and open-source on Github. Please star git-lrc to support the project and share your feedback. Every robust API will eventually inform you to sit and remain silent. Exert excessive pressure on services like GitHub, Stripe, or AWS, and your requests will begin returning a polite yet firm 429.

I've always found that intriguing, so let's construct the very thing that says no. By the conclusion of this post, we will have designed a rate limiter that effectively functions when subjected to genuine traffic, and I promise to limit my rate of token bucket puns. A rate limiter performs a single task: determining the maximum number of requests a client can make within a specified time frame.

It safeguards your system from becoming overwhelmed and prevents a single greedy user from consuming everyone else's resources. A straightforward concept. A surprisingly robust implementation. Let's construct it step by step, as you would in an interview or a design document. First, what are we actually building? Before writing a single line of code, let's agree on what constitutes a good solution. Here's my wish list:

Configurable limits. Something like 100 requests per minute per user.

The rules should not be hardcoded, as free users and premium users should have different levels of restrictions.

Honest rejections. When someone exceeds the limit, we return HTTP 429 Too Many Requests and provide helpful headers indicating how many requests they have left and when the window resets. No ambiguity.

Minimal latency. This check occurs on every single request, so it must be fast. Let's aim for under 3ms at the 95th percentile. If your rate limiter is slow, you've inadvertently introduced another bottleneck. High availability and sharing. Multiple servers need to agree on the same counts. This aspect is crucial and will become apparent later.

Alright, let's begin with a naive approach and see how reality challenges us. Attempt 1: the fixed window counter The simplest thing that could possibly work is fixed window counting. Divide time into neat one-minute intervals. Assign each user a counter. With each request, increment the counter by one. Exceed the limit, reject the request (return 429), and reset the counter when the next window begins.

It's clean, readable, and easy to explain even to a rubber duck. The counter needs a storage location. Where should we keep the counter? (This often confuses people) Your initial thought might be to use a database. Please don't. Adding a write to the database on every request means the thing we built to protect our system could inadvertently become a bottleneck itself.

That's a classic case of making peace with a full table scan. Okay, so the database is out. What about storing counters in memory on the server? Fast and efficient. Love it. However, it only works if you have a single server, and nobody runs a single server. As soon as you scale out, each box maintains its own private counter. A crafty user sends 100 requests to Server A and 100 to Server B, and they end up with 200 requests per minute, while your limit specifies 100.

Oops. What we truly want is something that is fast to access and shared across all servers. Redis fits the bill perfectly. It's an in-memory data store with atomic counter primitives like INCR, and it can automatically expire keys, ensuring windows reset on their own. Redis is the go-to choice in virtually every rate limiter design you'll encounter.

Now, let me introduce a flaw that nobody warns you about in fixed window counters. Picture a limit of 100 requests per minute. A user sends 100 requests in the last 10 seconds of one minute and another 100 in the first 10 seconds of the next minute. Each window individually is within the limit (100 or under), but together they constitute 200 requests in a 20-second span, which is far from the intended behavior of 100 per minute.

This issue occurs at every window boundary, and once someone notices the pattern, they will undoubtedly exploit it. The counter lacks memory across the boundary, so it cannot perceive the burst spanning two windows. We need an algorithm that considers a smooth rate rather than hard resets. Attempt 2: the token bucket (our hero) Introducing the token bucket, the algorithm quietly powering limits at places like AWS and Stripe.

Here's the mental model - it's literally a bucket. Imagine a bucket filled with tokens. Tokens flow in at a steady rate. Each request must acquire one token to proceed. No tokens available? Reject the request. That's it.

To implement this, we track the elapsed time since the last refill and update the token count accordingly. If there's at least one token, we decrement it and allow the request. Otherwise, we reject it and inform the user of the remaining requests and when the window resets. The diagram illustrates this decision process clearly. This solution elegantly resolves our boundary issue.

Two parameters control the entire process: Capacity determines the size of the burst you can tolerate. Refill rate sets your sustained throughput. With a capacity of 100 and a refill rate of 100 requests per minute, users can send up to 100 requests instantly if idle, but over time, they're constrained to 100 requests per minute.

When conditions are calm, the system allows bursts; when critical, it enforces strict limits. Aren't there other algorithms? Certainly. Sliding window logs, sliding window counters, leaky buckets, each addresses the boundary problem differently. However, the token bucket strikes the ideal balance.