Rate Limiting Beyond Algorithms

Background

Amid the enjoyment of the new parenthood journey, reality suddenly hit me and I started interviewing again. The very first interview was scheduled. I cleared the initial rounds, but the system design round was a different story.

It reminded me of something I had started to appreciate through working on production systems: while practicing system design is important, nothing quite prepares you for the challenges that emerge when those systems have to operate reliably at scale.

This conversation went really well; there were some hiccups here and there, but it was filled with learnings and curiosity. I have intentionally split this into parts to help readers digest it properly, and this is part one.

So the conversation started like this:

We need to design a rate limiter. Before we talk about where it lives in the system or how it scales, let’s start simple. What algorithms would you consider for rate limiting, and what are the trade-offs between them? Walk me through the ones you know.

Popular Rate Limiting Algorithms

There are generally four rate limiting algorithms that are popularly used, each having its own advantages and disadvantages. The choice depends on whether we care more about simplicity, burst tolerance, fairness, or strict traffic shaping. The quick comparison will look like:

Algorithm	Implementation complexity	Memory per client	Compute per request	Accuracy	Infra requirement	Cost at scale
Fixed Window	Trivial — one counter + TTL	O(1) — one integer	Very cheap	Poor — boundary burst problem	Any KV store (Redis/local)	Cheapest
Sliding Window (Log)	Moderate–High — sorted set + timestamp pruning	O(N) — N = requests in window	Cheap-ish, but pruning old timestamps adds cost	Perfect — exact	Needs sorted-set support (e.g. Redis ZSET)	Most expensive — memory scales with traffic
Sliding Window (Counter)	Moderate — weighted math across two windows	O(1) — two integers	Very cheap — one weighted calculation	Approximate — generally good enough	Any KV store	Cheap — flat O(1) per client
Token Bucket	Moderate — lazy refill calculation	O(1) — tokens + timestamp	Cheap — simple arithmetic	Exact — with bursty admission by design	Any KV store	Cheap — flat O(1) per client
Leaky Bucket	Moderate–High — requires queue management	O(N) — queued items; O(1) if tracking only level	Cheap for admission; queue processing adds overhead	Exact — for egress smoothing	Queue/worker infrastructure, or careful state tracking	Moderate–High if truly queueing, cheap if tracking a virtual level

Burst Issues

What is the burst problem?

This was very easy to answer and demonstrate with an example.

If the limit is 100 req/min, someone can send 100 requests at 11:59:59 and another 100 at 12:00:00 making it 200 requests in 2 seconds. So technically, they’ve stayed within the limit for each window, but we’ve actually allowed 200 requests within a couple of seconds.

That’s what we mean by the boundary burst problem with fixed-window rate limiting.

Sliding Window Degradation

Then why not just use Sliding Window? Why do we need Token Bucket or Leaky Bucket?

The answer here is not about what is better or what is accurate. But let’s take some time here to explain the nuances of the sliding window algorithms.

The core idea of this algorithm is to answer the question: how many requests have happened during the last window (say 60 seconds) from right now? To make this possible, the sliding window uses two approaches:

• Log based where the most intuitive implementation is to store the timestamp of every request. This also means with every request, the memory consumption will keep growing.

• Counter based where we split the time frame into small buckets and store the count of API calls that we receive. A common optimization is to use the current bucket plus the previous bucket and estimate the partially overlapping previous bucket.

Discussing the above two implementations in detail and going into the scale problems for sliding window can itself take hours and deserves a dedicated blog. A conclusive answer to the above question could look like:

Sliding window solves the boundary problem of fixed windows, but it doesn’t come for free. The log implementation gives very accurate enforcement but its state grows with request volume. The counter implementation scales much better because it aggregates requests into buckets, but introduces approximation. At large scale, the bigger challenges become state cardinality, hot keys, atomicity, cleanup, and distributed consistency.

Bucket Algorithms

The next question came up naturally to evaluate whether we are just mugging up the algorithms or whether we really understand which algorithm is solving what.

What does a bucket based rate limiter give us that Sliding Window doesn’t?

Instead of going forward with the technical algorithm definition, our answer here should reflect an understanding of why the bucket algorithms came into existence. The main thing a bucket-based limiter gives me is explicit control over burst capacity, which isn’t as natural with a sliding window.

With sliding window, we’re primarily asking, “How many requests have we seen in the last N seconds?” It’s good for enforcing a recent-window limit and avoiding the fixed-window boundary problem.

With a Token Bucket, we can separate sustained rate from burst capacity. For example, we could configure it for 100 requests per second with a bucket size of 500. The refill rate controls the long term rate, while the bucket capacity tells us how much of a burst we’re willing to tolerate.

So if the requirement is, “Allow normal traffic at 100/sec, but let a client occasionally burst up to 500,” Token Bucket models that requirement very naturally.

Here’s a quick peek into the details of the bucket algorithms:

	Token Bucket	Leaky Bucket
Allows bursts?	Yes. Unused tokens accumulate, allowing short bursts of requests.	No. Requests leave at a fixed rate, smoothing out bursts.
Controls	Admission rate — whether a request is allowed to proceed.	Processing/egress rate — how quickly requests are processed.
Queue required?	No. A request is typically accepted or rejected immediately based on available tokens.	Yes. Requests are placed in a queue and processed in order.
What happens when overloaded?	Requests are rejected or throttled when no tokens are available.	The queue grows until it reaches capacity; excess requests are rejected.
Best suited for	APIs where short bursts are acceptable but sustained traffic must be limited.	Systems where you need a smooth, predictable output rate.
Mental model	🪙 “You can spend accumulated tokens.”	🚰 “Water leaves the pipe at a fixed rate.”

Token bucket controls how many requests can burst in whereas leaky bucket controls how steadily requests flow out when there’s an incoming burst.

One catch: Leaky bucket’s queue means added latency for burst traffic (requests wait in line), whereas a rejected token-bucket request fails fast. If your system can’t tolerate added latency, token bucket’s fail-fast rejection may matter more than leaky bucket’s smoothing.

The Best Algorithm?

Alert: The upcoming question may look straightforward and in the flow of the conversation, the natural answer will come as - “We can use X rate limiter here”. But, take a pause and always look out for the reason behind the question instead of answering directly.

Given what you now know about all four, if you were rate-limiting a public API gateway protecting your backend from abusive clients, which would you lean toward, and why?

Jumping to give an answer like “We can use the token bucket rate limiter” will not be a good idea. The ideal way is to get clarity on the nature of the traffic. Rate limiter is always for the nature of the traffic not about which algorithm is good, bad or accurate. Ask questions about the nature of the traffic!

• What is the scale we will be dealing with?
• Are bursts allowed or we need to keep the flow steady?
• How much rate-limiter induced latency can be tolerated?
• Is it global limiter or user aware limiter?

On getting clarity, the question will become something like:

You’re protecting a public API gateway seeing on the order of 100K req/sec, from potentially millions of distinct API keys, and you care about keeping infra cost down. Also, we want to allow legitimate clients to burst, so which algorithm will you choose and why?

The two requirements that drive that decision are cost at high scale and controlled burst tolerance. Given those requirements, we can clearly opt for Token Bucket based rate limiting.

Rejecting Log Sliding Window

We’re talking about roughly 100K requests/sec and potentially millions of API keys, so we want the state per key to be small and bounded. We don’t want to maintain individual request timestamps for every key, which makes a Sliding Window Log particularly expensive at this scale.

Rejecting Counter Sliding Window

We also won’t choose Sliding Window Counter. It can be a good choice if the requirement is specifically accurate recent window enforcement, but here the requirement explicitly says we want controlled bursts and low infrastructure cost, which makes Token Bucket a better semantic and operational fit.

Rejecting Leaky Bucket

We would probably not choose Leaky Bucket here because we’re talking about an API gateway. We don’t want to queue arbitrary API requests just to smooth the traffic. This introduces latency and potentially high queue management cost. We would rather make an entry decision and return 429 when the client’s burst capacity is exhausted.

Selecting Token Bucket

With Token Bucket, per key we can essentially maintain the current token count and last refill timestamp. That gives us predictable, relatively small state, and it works well with a TTL based distributed store if we’re using something like REDIS.

The other important requirement is that legitimate clients should be able to burst. That’s where Token Bucket fits naturally. For example, we might configure a tenant for a sustained rate of 100 requests/sec with a bucket capacity of 500. Tokens refill at 100/sec, but if the client has accumulated tokens, it can temporarily consume up to 500 for a burst.

Reflections

Looking back at this conversation, the biggest takeaway for me wasn’t learning another rate-limiting algorithm. It was realizing how easy it is to approach system design as a memory exercise. Rate limiting isn’t about finding the algorithm that is universally better, more accurate, or more scalable. It’s about understanding the nature of the traffic and choosing the trade-offs that make sense for that system.

That’s also where the difference between knowing how something works and having designed or operated it in production starts to become very real.

In the next part, we’ll look at the challenges that arise when rate limiting has to operate at scale.