Sliding Windows in Production: Rate Limiting
You'll learn to
- -Recall the sliding-window technique and recognize it inside a rate limiter
- -Explain how a token bucket allows short bursts while still enforcing an average rate
- -Contrast token bucket, fixed window, and sliding window log approaches
Back in the two-pointer and sliding-window tier you used a window that slides across an array or string to track a running property - a sum, a count of distinct characters - in less than O(n^2) time. Rate limiting is that same idea pointed at time instead of an array: "how many requests happened in the last N seconds?" is a sliding window over a timeline of request timestamps. Level 23 asks you to build the algorithm almost every API gateway uses to answer that question and act on it: token bucket rate limiting.
Why Not a Simple Fixed Window?
The simplest rate limiter just counts requests per fixed calendar window (reset the counter every 60 seconds) and rejects once the count hits a limit. The flaw shows up at window boundaries: a client can send its full quota in the last second of one window and its full quota again in the first second of the next window, producing double the intended rate in a two-second span even though each window individually looked fine. A true sliding window - counting requests in the last N seconds relative to right now, not relative to a fixed clock boundary - fixes that, but a naive version needs to remember every timestamp, which costs memory proportional to request volume.
Token Bucket: A Sliding Window That Only Needs Two Numbers
Token bucket sidesteps the memory problem by not storing a window of timestamps at all. Picture a bucket that holds up to capacity tokens; tokens refill continuously at rate tokens per second; every request costs one token; a request is allowed only if a token is available, and rejected (or queued) otherwise. Because tokens accumulate while a client is quiet, a client that has been idle can burst up to capacity requests instantly, then gets throttled back down to the steady refill rate. That burst tolerance is the key advantage over a strict fixed window: real clients are bursty - a page load fires ten requests at once, then goes quiet - and token bucket absorbs that without either over-restricting or opening the door to sustained abuse.
- -Fixed window: cheap, but allows bursts up to double the limit across a window boundary.
- -Sliding window log: exact, but costs memory proportional to the number of requests in the window.
- -Token bucket: O(1) memory, and its burst allowance actually matches how real traffic behaves.
Token bucket's cousin, leaky bucket, processes requests at a strictly constant output rate instead of allowing bursts - useful when you need to smooth traffic hitting a downstream system rather than just cap it.
Design a rate limiter for a public API. Why reach for token bucket over a simple per-minute counter?
"A per-minute counter is simple so I'd just use that."
"A fixed per-minute counter lets a client burst its full quota at the boundary of two windows back-to-back, effectively doubling the rate for a moment. Token bucket fixes that: tokens refill continuously, so the enforced rate is a true average over time, while still tolerating short legitimate bursts up to the bucket's capacity - which matches how real client traffic actually arrives."
What problem does a token bucket solve that a naive fixed-window counter does not?
Level 23: Token Bucket Rate Limiter has you implement exactly this: a bucket with a capacity and refill rate, lazily topped up based on elapsed time, that accepts or rejects each request based on token availability - the algorithm behind rate limiting in most production API gateways.