What Are the Main Rate Limiting Algorithms?

Compare token bucket, leaky bucket, fixed window, and sliding window rate limiting algorithms and when to use each one.

mediumQ162 of 224 in System Design Est. time: 6 minsLast updated: July 2026

Expected Interview Answer

The main rate limiting algorithms are token bucket, leaky bucket, fixed window counter, sliding window log, and sliding window counter, each trading off burst tolerance, accuracy, and memory cost differently.

Token bucket allows a configurable amount of burst by letting unused capacity accumulate as tokens up to a cap, refilling at a steady rate, and is cheap to implement. Leaky bucket instead enforces a strictly constant output rate by queuing requests and draining them steadily, smoothing bursts entirely rather than allowing them. Fixed window counters simply count requests in discrete time buckets (e.g., per minute) and are the simplest and cheapest, but they allow up to double the limit in a burst spanning a window boundary. Sliding window log tracks the exact timestamp of every request for perfect accuracy but costs memory proportional to request volume, while sliding window counter approximates a sliding window cheaply by weighting the current and previous fixed windows, giving most of the accuracy of the log approach at a fraction of the storage cost — which is why it is the common production default at scale.

Token bucket allows controlled bursts while still enforcing a long-run average rate
Leaky bucket guarantees a smooth, constant output rate protecting downstream systems
Fixed window is cheap and simple for coarse-grained limits
Sliding window counter gives near-exact accuracy at low memory cost, ideal for distributed rate limiters

AI Mentor Explanation

Token bucket rate limiting is like a batter who banks unused review appeals across overs up to a cap, so they can burn several reviews quickly during a controversial passage of play, while leaky bucket is like a bowler restricted to exactly one delivery every fixed number of seconds no matter what, smoothing pace to a constant rhythm. Fixed window counting is like simply capping deliveries per over by the clock, which can let two full quotas land back-to-back right at the over break. Sliding window tracking instead looks at any rolling six-ball stretch continuously, catching that boundary-clustering trick that fixed windows miss. Each algorithm makes a different trade between allowing bursts and enforcing a strictly even pace.

Step-by-Step Explanation

Step 1
Pick the accuracy/cost trade-off
Decide whether coarse fixed windows, exact logs, or an approximate sliding counter fits the traffic and memory budget.
Step 2
Decide on burst tolerance
Token bucket allows bursts up to bucket capacity; leaky bucket enforces a hard constant rate with no bursts.
Step 3
Implement per-key state
Track tokens/timestamps/counts per client key (user, IP, API key), typically in a fast shared store like Redis for distributed systems.
Step 4
Enforce and respond
Reject or delay requests exceeding the limit, returning HTTP 429 with rate-limit headers indicating remaining quota and reset time.

What Interviewer Expects

Can name and describe at least three algorithms: token bucket, leaky bucket, fixed/sliding window
Explains the fixed-window boundary burst problem concretely
Understands the accuracy vs. memory trade-off of sliding window log vs. sliding window counter
Knows which algorithm suits which scenario (e.g., token bucket for API bursts, leaky bucket for smoothing downstream load)

Common Mistakes

Only knowing one algorithm and treating it as “the” rate limiting solution
Not explaining the fixed window double-burst edge case
Confusing token bucket (allows bursts) with leaky bucket (forces constant rate)
Ignoring the storage cost trade-off of sliding window log at high request volume

Best Answer (HR Friendly)

“There are a few standard ways to limit how many requests someone can make. Token bucket lets some bursts through as long as the average stays under the limit. Leaky bucket forces a perfectly steady rate with no bursts at all. Fixed and sliding window approaches just count requests in a time period, with sliding window being more accurate about edge cases where bursts sneak in right at the boundary between two time periods.”

Code Example

Sliding window counter approximation (Python, Redis-style pseudo-store)

def is_allowed(key, limit, window_seconds, now, store):
    current_window = int(now // window_seconds)
    previous_window = current_window - 1

    current_count = store.get_count(key, current_window)
    previous_count = store.get_count(key, previous_window)

    elapsed_in_current = now - (current_window * window_seconds)
    weight_previous = max(0.0, (window_seconds - elapsed_in_current) / window_seconds)

    estimated_count = current_count + previous_count * weight_previous

    if estimated_count >= limit:
        return False  # reject, HTTP 429

    store.increment(key, current_window)
    return True  # allow

Follow-up Questions

When would you choose token bucket over leaky bucket for an API gateway?
Why does sliding window log guarantee exact accuracy, and what does that cost in memory?
How would you make a rate limiting algorithm consistent across multiple distributed servers?
What rate limit headers should an API return, and how do clients use them?

MCQ Practice

1. Which algorithm allows requests to burst up to a stored capacity but enforces a long-run average rate?

2. What is the main drawback of a naive fixed window counter?

3. What is the main advantage of a sliding window counter over a sliding window log?

Flash Cards

1 / 4

What Are the Main Rate Limiting Algorithms?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Pick the accuracy/cost trade-off

Decide on burst tolerance

Implement per-key state

Enforce and respond