Rate Limiting Algorithms: Token Bucket, Leaky Bucket and Sliding Windows

Rate limiting controls how many requests a client can make in a period of time. It protects your services from overload and abuse, keeps usage fair across customers, controls costs (especially for expensive operations like LLM calls), and enforces pricing tiers. Every public API needs it, and most internal services benefit too.

#Key takeaways

• Rate limiting protects availability, ensures fairness, defends against abuse and controls cost.
• The main algorithms: fixed window, sliding log, sliding window counter, token bucket and leaky bucket.
• Token bucket is the most popular for APIs: it allows short bursts while enforcing an average rate.
• In distributed systems, keep counters in a shared store such as Redis, and update them atomically.
• Return 429 Too Many Requests with Retry-After and rate-limit headers so clients can behave.

#Where to rate limit

• Edge / API gateway: coarse protection per IP or API key before traffic reaches your services.
• Application layer: fine-grained limits per user, tenant, endpoint or operation cost.
• Outbound: limit your own calls to third-party APIs to stay within their quotas.

Choose the key carefully: per API key or user is fairer than per IP (many users can share one IP behind a NAT, and one attacker can rotate IPs).

#1. Fixed window counter

Count requests in fixed time buckets, such as per minute:

textWindow 12:00:00–12:00:59 → count ≤ 100
Window 12:01:00–12:01:59 → count resets

• ✅ Simple and memory-cheap (one counter per key per window).
• ❌ Boundary bursts: a client can send 100 requests at 12:00:59 and another 100 at 12:01:00, so 200 in two seconds.

#2. Sliding window log

Store a timestamp for every request; count those within the last N seconds.

• ✅ Precise, with no boundary bursts.
• ❌ Memory-heavy at high volumes (one entry per request).

#3. Sliding window counter

Approximate a sliding window by weighting the previous fixed window's count:

textestimated = current_window_count + previous_window_count × (1 − elapsed_fraction_of_current_window)

At 25% into the current minute, with 40 requests so far and 80 in the previous minute: 40 + 80 × 0.75 = 100.

• ✅ Smooths boundary bursts, and cheap (two counters).
• ⚠️ Approximate, which is fine for most use cases.

#4. Token bucket

A bucket holds up to capacity tokens and refills at a steady rate. Each request consumes a token; if the bucket is empty, the request is rejected (or delayed).

textcapacity = 20 tokens, refill = 5 tokens/second
→ a client can burst 20 requests instantly, then sustain 5/second

pythonimport time

class TokenBucket:
    def __init__(self, capacity: float, refill_per_sec: float):
        self.capacity = capacity
        self.tokens = capacity
        self.rate = refill_per_sec
        self.updated = time.monotonic()

    def allow(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

• ✅ Allows natural bursts (page loads that fire several API calls) while enforcing an average rate.
• ✅ Cost-based limiting: expensive operations consume more tokens.
• ✅ Only two values per key (tokens, last update time).

This is why token bucket is the default in many API gateways and cloud services.

#5. Leaky bucket

Requests enter a queue (the bucket) that drains at a constant rate. If the queue is full, new requests are dropped.

• ✅ Produces a smooth, constant output rate. Useful for protecting a downstream system that can't handle bursts.
• ❌ Adds latency (queuing), and bursts are smoothed rather than served quickly.

#Comparison

#Distributed rate limiting with Redis

With many app instances, in-memory counters don't work, because each instance sees only part of the traffic. Use a shared store and atomic operations. A fixed-window example:

pythondef allow(redis, key: str, limit: int, window_s: int) -> bool:
    bucket = f"rl:{key}:{int(time.time() // window_s)}"
    pipe = redis.pipeline()
    pipe.incr(bucket)
    pipe.expire(bucket, window_s + 1)
    count, _ = pipe.execute()
    return count <= limit

For token buckets or sliding windows, implement the logic in a Lua script so the read-modify-write happens atomically on the Redis server.

Considerations:

• Latency: a Redis round trip per request. Keep Redis close, and consider local pre-checks for very high throughput.
• Failure mode: if Redis is down, do you fail open (allow traffic, which risks overload) or fail closed (reject traffic, which risks an outage)? Usually fail open with a conservative local limiter as backup.
• Hot keys: a single very active key can concentrate load on one Redis shard.

#Communicating limits to clients

httpHTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 12
Content-Type: application/json

{"error": {"code": "rate_limited", "message": "Too many requests. Retry in 12 seconds."}}

• Include limits in successful responses too, so clients can pace themselves.
• Document limits per plan and endpoint (API design best practices).
• Well-behaved clients should back off exponentially with jitter. That applies to your own scrapers and integrations, too (responsible web scraping).

#Designing good limits

• Layer limits: per second (burst protection) plus per day (quota).
• Different limits per endpoint: logins and password resets need strict limits to prevent credential stuffing; read endpoints can be generous.
• Weight by cost: an export or an LLM-backed endpoint should consume more quota than a simple read (LLM cost optimization).
• Tenant fairness: prevent one customer from starving others in multi-tenant systems.
• Load shedding: beyond per-client limits, shed low-priority traffic when the system is overloaded (how to scale a web application).

#FAQ

#What is the best rate limiting algorithm?

For most APIs, token bucket: it allows reasonable bursts while enforcing an average rate, supports cost-based limits, and is cheap to implement. Sliding window counters are a good alternative when you want smoother enforcement of a strict per-window limit.

#Should rate limiting be done at the API gateway or in the app?

Both. Gateways provide coarse, early protection (per IP or key). The application enforces fine-grained, business-aware limits (per user, tenant, operation cost).

#What's the difference between rate limiting and throttling?

The terms overlap. Rate limiting typically rejects requests over the limit (429). Throttling often implies slowing requests down, by queuing or delaying them, rather than rejecting them.

#How do I rate limit by IP safely behind a load balancer?

Use the client IP from trusted forwarding headers set by your own load balancer or CDN, and don't trust headers supplied directly by clients. Prefer API-key or user-based limits for authenticated traffic.