Rate-Limiting Algorithms

“Limit requests per user/IP/endpoint” sounds simple. The algorithm matters — fixed window has obvious flaws, sliding window costs more but is fairer, token bucket handles bursts cleanly. Senior interview territory.

Fixed window

The simplest. Count requests per N-second window; reset at boundaries.

def allowed_fixed(user, limit=100, window=60):
    bucket = f"rate:{user}:{int(time.time() // window)}"
    count = r.incr(bucket)
    if count == 1:
        r.expire(bucket, window)
    return count <= limit

Pros: trivially cheap, easy to reason about. Cons: boundary burst — a user can do limit in the last second of one window and limit in the first second of the next. Effective rate at the boundary is 2× the configured limit.

Acceptable for forgiving limits (1000/min); broken for tight ones (10/min).

Sliding window log

Store every request timestamp; on each request, count timestamps within the last N seconds.

def allowed_sliding_log(user, limit=100, window=60):
    key = f"rate:{user}"
    now = time.time()
    cutoff = now - window
    p = r.pipeline()
    p.zremrangebyscore(key, 0, cutoff)        # drop old entries
    p.zadd(key, {str(now): now})              # add this request
    p.zcard(key)                              # current count
    p.expire(key, window)
    _, _, count, _ = p.execute()
    return count <= limit

Pros: precisely correct; no boundary burst. Cons: memory grows with active request count per user; storage cost matters at scale.

Sliding window counter

Approximation: count in the current window + a weighted fraction of the previous window’s count.

def allowed_sliding_counter(user, limit=100, window=60):
    now = time.time()
    cur_window = int(now // window)
    prev_window = cur_window - 1
    pos_in_window = (now - cur_window * window) / window     # 0.0 to 1.0

    cur_key = f"rate:{user}:{cur_window}"
    prev_key = f"rate:{user}:{prev_window}"

    cur_count = int(r.get(cur_key) or 0)
    prev_count = int(r.get(prev_key) or 0)

    weighted = cur_count + prev_count * (1 - pos_in_window)
    if weighted >= limit:
        return False

    p = r.pipeline()
    p.incr(cur_key)
    p.expire(cur_key, window * 2)
    p.execute()
    return True

Pros: O(1) memory per user; close to true sliding window. Cons: approximation; slightly over- or under-permissive depending on traffic shape. Good enough for most production needs.

Token bucket

Tokens replenish at a fixed rate; each request consumes one. Allows bursts up to the bucket capacity.

def allowed_token_bucket(user, capacity=10, refill_rate=1):  # 1 token per second; burst up to 10
    key = f"rate:{user}"
    now = time.time()
    lua = """
    local capacity = tonumber(ARGV[1])
    local refill_rate = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])
    local tokens = tonumber(redis.call('hget', KEYS[1], 'tokens') or capacity)
    local last = tonumber(redis.call('hget', KEYS[1], 'last') or now)
    local elapsed = math.max(0, now - last)
    tokens = math.min(capacity, tokens + elapsed * refill_rate)
    if tokens < 1 then
        redis.call('hset', KEYS[1], 'last', now)
        return 0
    end
    tokens = tokens - 1
    redis.call('hset', KEYS[1], 'tokens', tokens)
    redis.call('hset', KEYS[1], 'last', now)
    redis.call('expire', KEYS[1], 3600)
    return 1
    """
    return bool(r.eval(lua, 1, key, capacity, refill_rate, now))

Pros: elegant bursting; intuitive (“you have X tokens, refill at Y/sec”). Used by AWS API rate limits, GitHub, Stripe. Cons: Lua script for atomicity; slightly more state per key.

Leaky bucket (request leak)

A queue with a fixed leak rate. Excess requests overflow.

Conceptually like token bucket inverted: instead of “tokens refill and you consume”, “queue fills and you leak at fixed rate.” Smoothing-focused.

In practice rarely implemented for HTTP rate limiting; nginx’s limit_req is a leaky bucket variant. Token bucket is the more common API rate limiting metaphor.

GCRA (Generic Cell Rate Algorithm)

A precise variant of leaky bucket from telephony. Stores just one timestamp per key: “earliest time the next request would be allowed.” Single comparison + update per request.

def allowed_gcra(user, period=1.0, burst=10):
    # period = average gap between requests; burst = tolerance
    key = f"rate:{user}"
    now = time.time()
    lua = """
    local period = tonumber(ARGV[1])
    local burst = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])
    local tat = tonumber(redis.call('get', KEYS[1]) or 0)
    local new_tat = math.max(tat, now) + period
    local allow_at = new_tat - period * burst
    if now < allow_at then
        return 0
    end
    redis.call('set', KEYS[1], new_tat)
    redis.call('expire', KEYS[1], math.ceil(period * burst) + 1)
    return 1
    """
    return bool(r.eval(lua, 1, key, period, burst, now))

Used by GitHub, Twitter, Stripe internally. Most accurate + most memory-efficient.

Where to enforce

Enforce at the cheapest layer that has the context. Gateway sees IPs; gateway can rate-limit by IP. Per-user-tier (“free tier = 100 RPM, paid = 1000 RPM”) needs application context.

Distributed rate limiting

Most algorithms above work over Redis. The atomic operations (INCR, ZADD, Lua scripts) keep state consistent across multiple API servers.

Common gotchas:

• Redis latency — every request hits Redis. At very high RPS, Redis becomes the bottleneck.
• Hot keys — one popular user’s rate-limit counter takes all the traffic on one Redis shard. Use cluster mode + key hashing.
• Local + distributed combo — local approximate counter (LRU cache) + periodic flush to Redis. Trades accuracy for throughput.

Response shape (HTTP)

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1709125800

Retry-After is the standard. Some APIs include RateLimit-* headers (informational).

For long-running clients, expose the rate-limit state proactively in response headers on EVERY response (not just 429s); they can self-throttle.

What to limit on

Common keys:

• API key — per-customer tier enforcement.
• User ID — per-user prevent abuse.
• IP address — anonymous abuse / DoS protection.
• Endpoint — protect expensive endpoints separately.
• Compound — (user_id, endpoint) for fine-grained.

Often layer multiple: per-IP (DoS), per-API-key (tier), per-endpoint (expense). Each with its own limit.

What to do when rate-limited

• Return 429 immediately — fast feedback.
• Cost shedding — sample the work; return partial results.
• Queue + asynchronous reply — accept, return 202 with a Location for the result, process when capacity allows.
• Tarpitting — slow the response intentionally to make abuse expensive. Last-resort, rarely needed.

Don’t silently drop. 429 with Retry-After is the right behavior.

Interview angle

• “What’s the boundary burst problem in fixed-window rate limiting?” — a user can do limit in the last second of one window and limit in the first second of the next. Effective rate at the boundary is 2× the configured limit. Fixed windows have it; sliding window / token bucket / GCRA don’t.
• “Token bucket vs leaky bucket?” — token bucket: tokens refill, each request consumes one, bursts up to capacity. Leaky bucket: requests queue, leak at fixed rate, excess overflow. Token bucket allows bursts; leaky bucket smooths. Both end up bounded; token bucket is the more common API metaphor.
• “What’s GCRA?” — Generic Cell Rate Algorithm. Precise leaky-bucket variant from telecom. Stores one timestamp per key (TAT — theoretical arrival time). Single check + update per request. Most memory-efficient + accurate.
• “How do you do rate limiting across multiple API servers?” — shared state in Redis via atomic ops (INCR, ZADD, Lua scripts). Each request hits Redis to check/update the counter. Gotchas: Redis latency at the hot path, hot keys for popular users.
• “Where do you enforce rate limits?” — at the cheapest layer with the right context. CDN / WAF for global DoS; gateway for per-API-key / per-IP; application for per-user-tier business logic. Often combined.
• “What HTTP status and headers do you return when rate-limited?” — 429 Too Many Requests, with Retry-After: <seconds>. Optionally X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset for proactive client-side throttling.
• “You need per-user 10/sec with burst tolerance of 50. Which algorithm?” — token bucket: capacity=50, refill_rate=10/sec. Allows a 50-request burst, then sustained 10/sec. Sliding window log with 1-second window would also work but limit semantics get confusing for the burst case.