SYSTEM DESIGN:Lesson 5: Token Bucket vs Sliding Window

The 3am scraper

Picture this: your REST API has been humming along at 200 requests per second all week. Then at 3:07 AM on a Tuesday, a monitoring alert fires. Someone — or something — is hammering your /search endpoint at 8,000 req/s from a single API key.

Your Postgres connection pool is exhausted. Redis is fine, but your app servers are pegged at 100% CPU. Three paying customers in Mumbai cannot check out because their requests time out behind the scraper's traffic.

You do not need a smarter database. You need a rate limiter — a rule that says "this client gets at most 100 requests per minute, and after that, reject or slow them down."

This chapter is about the algorithms behind that rule. Not where to deploy them (that is the next chapter). Just the math and trade-offs you pick when someone asks: "How would you rate-limit an API?"

A bot hammering your API at 3am while you sleep

This is why "we will add rate limiting later" is a sentence that ages poorly.

What you are actually limiting

Before picking an algorithm, nail down the dimension:

• Per user / API key — fair usage for SaaS APIs (Stripe, Razorpay, your own product)
• Per IP — coarse but works when you have no auth (public endpoints, login pages)
• Per endpoint — protect expensive operations (/export, /recommendations) separately from cheap ones (/health)
• Global — protect shared downstream resources (one database, one third-party API quota)

Most interview answers assume per user, 100 requests per minute. That is a reasonable default. Real systems often stack limits: 100/min per user AND 10,000/min globally.

Two response styles matter too:

• Hard reject — return HTTP 429 with Retry-After header
• Soft throttle — queue or delay the request (less common at the API layer, more common in job queues)

Fixed window counter

The simplest approach: divide time into windows (usually 1 minute), count requests in the current window, reject when count exceeds the limit.

Fixed window rate limiting

Implementation sketch with Redis:

key = "ratelimit:user123:202608281430"   // user + minute bucket
count = INCR(key)
if count == 1: EXPIRE(key, 60)
if count > 100: return 429

Pros: dead simple, one key per user per window, minimal memory.

Cons: the boundary burst problem. A client can send 100 requests at 12:00:59 and another 100 at 12:01:00. That is 200 requests in 2 seconds — double your intended rate.

I have seen this bite teams running flash sales. A bot scripts requests to straddle window edges and gets 2× throughput. Fixed window is fine for internal tools and low-stakes APIs. I would not rely on it alone for a payment gateway.

Sliding window counter

Instead of one bucket per minute, track requests in a rolling window. When a request arrives at 12:00:45, count everything since 11:59:45.

Two common implementations:

Sliding window log — store a timestamp for every request in the window. Accurate, but memory-heavy. 100 req/min means up to 100 timestamps per user in Redis.

Sliding window counter (hybrid) — combine the current window count with a weighted fraction of the previous window. Redis popularized this; it is approximate but good enough for most APIs.

// Approximate sliding window at time T within current minute
prev_count = GET("ratelimit:user123:prev_minute")
curr_count = GET("ratelimit:user123:curr_minute")
weight = (60 - seconds_into_current_minute) / 60
estimated = curr_count + prev_count * weight
if estimated > 100: return 429

The hybrid approach fixes the edge burst without storing 100 timestamps. You might be off by 1–2 requests in edge cases. For a public API, that is acceptable.

My take: if you are building on Redis and need smoother limiting than fixed window, use the hybrid sliding window counter. It is what AWS API Gateway and many API gateways approximate under the hood.

Token bucket

Imagine a bucket that holds tokens. It refills at a steady rate — say 10 tokens per second, max capacity 100. Each request costs 1 token. No tokens? Request rejected.

Token bucket rate limiting

# Pseudocode — token bucket per user
capacity = 100          # burst size
refill_rate = 10        # tokens per second

def allow_request(user_id):
    bucket = get_bucket(user_id)  # { tokens, last_refill_time }
    now = time.time()
    elapsed = now - bucket.last_refill_time
    bucket.tokens = min(capacity, bucket.tokens + elapsed * refill_rate)
    bucket.last_refill_time = now
    if bucket.tokens >= 1:
        bucket.tokens -= 1
        return True
    return False

Why teams love it: you get controlled bursts. A user idle for 10 seconds accumulates tokens and can burst 100 requests, then settles to 10/sec steady state. That matches real traffic — someone opens Swiggy, loads 15 API calls in 2 seconds, then goes quiet.

Downside: slightly more state per user (tokens + timestamp). Distributed token buckets need atomic updates — covered in the architecture chapter.

Token bucket is my default recommendation in interviews when the interviewer asks about burst tolerance. It is what Stripe documents for their API rate limits.

Leaky bucket

Requests enter a queue (the bucket). They "leak" out at a fixed rate — like water dripping from a hole. If the queue is full, new requests are dropped.

Think of it as smoothing output, not smoothing input. A burst of 500 requests gets queued and processed at exactly 10/sec. Clients see steady, predictable throughput.

Where you actually see leaky bucket behavior:

• Network traffic shaping — routers limit egress bandwidth
• Log ingestion pipelines — absorb spikes, write to disk at constant rate
• Old-school API gateways — queue requests before hitting backend

For a synchronous HTTP API, leaky bucket is awkward. Users do not want their request sitting in a queue for 30 seconds. You usually reject immediately (429) rather than queue. That is why token bucket wins for REST APIs and leaky bucket wins for streaming/queue systems.

Interview tip: mention leaky bucket to show you know the family, then explain why token bucket fits HTTP better. Interviewers notice when you connect algorithm to protocol semantics.

Side-by-side comparison

What I would say in a 45-minute interview

If I have 3 minutes on algorithms, I pick token bucket and explain why: burst tolerance for mobile/web clients, well-understood parameters (capacity + refill rate), maps cleanly to "100 req/min with bursts up to 20."

If the interviewer pushes on simplicity, I mention fixed window with a note about edge bursts, then offer sliding window counter as the fix.

If they ask about strict fairness ("no bursts at all"), I go sliding window log and acknowledge the memory cost — maybe only for premium tier users where you store per-request timestamps.

What I would not do: recite all five algorithms for 10 minutes without connecting to requirements. Start with "What kind of traffic? Bursty mobile app or steady server-to-server?" That question alone eliminates two options.

Concrete numbers to drop:

• Twitter API v2: 300 requests per 15-minute window (fixed window feel)
• GitHub REST: 5,000 requests/hour per token
• Typical SaaS default: 100 req/min per API key with 429 + Retry-After

These numbers change. The pattern — pick algorithm based on burst tolerance, memory budget, and accuracy — does not.

Common follow-up questions (algorithm level)

"What HTTP status do you return?" — 429 Too Many Requests. Include Retry-After: 12 (seconds) so well-behaved clients back off.

"How do you rate-limit unauthenticated traffic?" — IP-based fixed or sliding window. Coarse, but better than nothing. Watch for NAT — one IP might be 500 users behind a corporate proxy.

"Different limits for free vs paid tiers?" — Same algorithm, different parameters. Free: 60/min. Pro: 1,000/min. Store tier in user metadata, look up limit at check time.

"What about GraphQL where one request can fan out to 50 DB queries?" — Rate limit by cost, not raw request count. Assign query complexity scores. A mutation costing 50 points counts differently than a simple read.

Algorithm picked. Now what?

You know token bucket (or sliding window) is the right shape. But your API runs on 40 Kubernetes pods behind a load balancer. Each pod has its own in-memory counter. A user hitting pod A and pod B gets double the limit.

Single-machine rate limiting is a coding exercise. Production rate limiting is a distributed systems problem — shared state, atomic operations, failure modes when Redis hiccups.

Continue here: Building a Distributed Rate Limiter.

Want hands-on practice? Try the rate limiter scenario in System Design Challenges.