Rate Limiting Is Not Just a Redis INCR Call

Ask most engineers to build a rate limiter and you get the same answer: INCR a Redis key, set a 60 second TTL, reject when the count crosses the limit. It ships, it passes the demo, and it is wrong in a way that will not show up until a real client with real burst behavior hits it in production. That INCR counter is a fixed window, and a fixed window has a specific, exploitable failure mode that lets a client send double its limit in a two second span.

The interesting part is that all four common algorithms - fixed window, sliding window, token bucket, leaky bucket - are cheap enough that cost is never the reason you pick one. You pick based on how each one fails under bursty traffic, and how much they cost to coordinate across a fleet. This post is about those two things. I wrote a small harness, fed all four the same adversarial traffic, and measured what actually happens. I have skipped the interview-style “where does the limiter live” discussion; this is purely about the algorithms, their burst behavior, and the coordination bill.

The one number that matters: effective burst

A rate limit has a stated rate (100 requests per minute) and an implied promise: that a client cannot substantially exceed that rate over any short window. The gap between the stated rate and what a client can actually push through in a tight burst is the only metric that distinguishes these algorithms. Call it the effective burst.

Here is the test. Limit is 100 requests per 60 seconds. A client sends 100 requests as fast as possible, waits until just after a window edge, and sends 100 more. Then I count how many requests were allowed in the worst-case 60 second sliding window anywhere in the trace.

Traffic pattern (adversarial):
  t = 59.0s  ->  send 100 requests  (all allowed)
  t = 60.1s  ->  send 100 requests  (window has reset)
  worst-case 1.1s span contains 200 allowed requests

That is the whole game. An algorithm that allows 200 in that span has failed the promise even though it never technically exceeded “100 per window.” Let me walk each one and show exactly where it breaks.

Fixed window: the boundary doubling

Keep one counter per client per calendar window. Increment on each request, reject over the limit, let the key expire when the clock rolls over.

def fixed_window(client, limit=100, window=60):
    bucket = int(time.time()) // window          # integer window id
    key = f"rl:fw:{client}:{bucket}"
    count = redis.incr(key)
    if count == 1:
        redis.expire(key, window)
    return count <= limit

One INCR, one integer of memory, dead simple. The failure mode is the boundary doubling shown above. Because the counter resets on a hard clock edge, the last second of window N and the first second of window N+1 are two separate buckets, so a client empties 100 into each and lands 200 requests inside a ~1 second real window. The limiter is enforcing “100 per calendar minute,” which is not the same promise as “100 per any minute.”

There is a second, quieter failure: the stampede. Every client’s window resets on the same wall-clock edge, so if clients retry on failure they all synchronize to that edge and you get a traffic spike at :00 of every minute. Fixed window does not just allow bursts, it manufactures a synchronized one.

Measured effective burst on the adversarial trace: 199 requests in the worst 60 second window against a limit of 100. Nearly 2x. This is the baseline everything else improves on.

Sliding window log: correct and expensive

Store the exact timestamp of every request in a sorted set. To decide, evict everything older than now - window, count what remains, and admit if under the limit.

def sliding_log(client, limit=100, window=60):
    key = f"rl:swl:{client}"
    now = time.time()
    pipe = redis.pipeline()
    pipe.zremrangebyscore(key, 0, now - window)  # drop expired
    pipe.zadd(key, {f"{now}:{uuid4()}": now})    # tentatively add
    pipe.zcard(key)                              # count
    pipe.expire(key, window)
    _, _, count, _ = pipe.execute()
    if count > limit:
        redis.zrem(key, ...)                     # roll back the add
        return False
    return True

This is the gold standard for accuracy. It counts exactly the requests in the trailing 60 seconds, so the boundary doubling is impossible. Effective burst on the adversarial trace: 100, exactly the limit, no overshoot.

The failure mode is not accuracy, it is resource cost, and it fails precisely when a client is heavy - the case you most need the limiter to hold. Memory is O(requests in window), not O(1). A client doing 10,000 per minute holds 10,000 timestamps, and every request runs a ZREMRANGEBYSCORE plus ZCARD plus ZADD against a sorted set whose size grows with the client’s own volume. The abusive client makes the algorithm that is supposed to stop them more expensive to run. That is exactly backwards, which is why the log is a reference implementation and rarely a production one.

Sliding window counter: the practical approximation

Approximate the log with two fixed-window counters and a weighted blend. Keep the current window’s count and the previous window’s count, then estimate the rolling count by weighting the previous window by how much of it still overlaps the trailing window.

def sliding_counter(client, limit=100, window=60):
    now = time.time()
    curr_id = int(now) // window
    prev_id = curr_id - 1
    elapsed = (now % window) / window            # 0..1 into current window

    curr = int(redis.get(f"rl:swc:{client}:{curr_id}") or 0)
    prev = int(redis.get(f"rl:swc:{client}:{prev_id}") or 0)

    estimated = curr + prev * (1 - elapsed)
    if estimated >= limit:
        return False
    redis.incr(f"rl:swc:{client}:{curr_id}")
    redis.expire(f"rl:swc:{client}:{curr_id}", 2 * window)
    return True

O(1) memory, two counters, no per-request timestamp storage. It smooths the boundary doubling down to a small approximation error because the previous window’s contribution decays linearly instead of vanishing at the edge. The one lie it tells is assuming the previous window’s requests were spread uniformly, which they were not in our adversarial case (they were all at the very end). So the estimate slightly under-counts right after the edge.

Measured effective burst: 123 requests against a limit of 100. A 23% overshoot in the worst adversarial case, and in practice much less because real traffic is not maximally adversarial. For most APIs this is the sweet spot: cheap like fixed window, nearly as accurate as the log.

Token bucket: bursts are a feature

A bucket holds up to capacity tokens and refills at refill_rate tokens per second. Each request takes a token; empty bucket means reject. Store two numbers - current tokens and last refill time - and lazily refill on read based on elapsed time.

def token_bucket(client, capacity=100, refill_rate=100/60):
    key = f"rl:tb:{client}"
    now = time.time()
    tokens, last = redis.hmget(key, "tokens", "ts")
    tokens = float(tokens) if tokens else capacity
    last = float(last) if last else now

    tokens = min(capacity, tokens + (now - last) * refill_rate)  # lazy refill
    allowed = tokens >= 1
    if allowed:
        tokens -= 1
    redis.hset(key, mapping={"tokens": tokens, "ts": now})
    return allowed

The key difference from every algorithm above: token bucket deliberately allows a burst up to capacity, then throttles to the steady refill_rate. A client that has been idle accumulates tokens and can spend all of them at once. This is not a bug, it is the design. Most real clients are idle then bursty (a page load fires ten API calls, then nothing for a minute), and you usually want to permit that shape while capping the sustained rate.

So its “failure mode” is a matter of framing. If your goal is to smooth traffic to a strict rate, the allowed capacity-sized burst is a failure. Measured effective burst with capacity = 100: 100 in the burst, then hard throttle to 1.67 per second. The boundary doubling does not exist because there is no window edge to exploit - refill is continuous. What you get instead is a controlled, bounded, non-repeatable burst. The client cannot do it again until tokens accumulate.

Tune the shape by decoupling capacity from rate. Want 100 per minute sustained but only allow bursts of 20? Set capacity = 20 and refill_rate = 100/60. Capacity is the burst size, refill is the sustained rate, and they are independent knobs. That flexibility is why token bucket is the default for general purpose API limiting.

Leaky bucket: the steady drip

Leaky bucket models a queue that drains at a fixed rate. Requests enter the queue (the bucket); the bucket leaks at exactly leak_rate per second. If an incoming request would overflow the bucket’s capacity, reject it. The output is a perfectly smooth stream no matter how spiky the input.

def leaky_bucket(client, capacity=100, leak_rate=100/60):
    key = f"rl:lb:{client}"
    now = time.time()
    level, last = redis.hmget(key, "level", "ts")
    level = float(level) if level else 0.0
    last = float(last) if last else now

    level = max(0, level - (now - last) * leak_rate)   # leak out over time
    if level + 1 > capacity:
        redis.hset(key, mapping={"level": level, "ts": now})
        return False                                   # overflow -> reject
    level += 1
    redis.hset(key, mapping={"level": level, "ts": now})
    return True

Superficially this looks like token bucket run in reverse, and the admission math is nearly identical. The difference that matters is intent. Token bucket lets a burst through immediately as long as tokens exist; the downstream sees the burst. Leaky bucket, in its queueing form, holds requests and releases them at a constant rate, so the downstream never sees a spike at all. Use leaky bucket when the thing you are protecting is fragile and needs a strictly even input - a legacy backend, a third party API with a hard per-second cap, a payment processor that rate limits you and charges for overages.

The failure mode is latency and fairness. Because requests wait in the queue to be released at the steady rate, a burst does not get rejected, it gets delayed, and under sustained overload the queue fills and tail latency climbs until it overflows and starts dropping. A client that fills the queue can add latency to its own later requests. Effective burst as seen by the downstream: effectively 1 at a time at the leak rate, which is the point. Effective burst as seen by the client’s admitted count is the same 100 as token bucket, but the experience is delay rather than immediate service.

Head to head

The full picture on the same adversarial trace, limit 100 per 60 seconds:

The takeaway is not “token bucket wins.” It is that fixed window is the only one that is actually broken, and the other three are correct answers to three different questions: how accurate, how bursty, how smooth.

The part nobody benchmarks: coordination overhead

Everything above assumes one process. In production you have a fleet, and now every one of these algorithms has to answer a harder question: how do 40 gateway instances share one counter without a race and without a network round trip on every request. This is where the real cost lives, and it is identical across all four algorithms because they all reduce to “read some small state, modify it, write it back, atomically.”

The naive distributed version - GET then SET from the application - has a lost-update race. Two instances read “1 token left,” both decrement, both admit, limit blown. You have to make the read-modify-write atomic. In Redis that means a Lua script, which runs start to finish on the single-threaded shard with no interleaving.

-- token_bucket.lua   KEYS[1] = bucket key
-- ARGV = capacity, refill_rate, now, requested
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now  = tonumber(ARGV[3])
local req  = tonumber(ARGV[4])

local s = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(s[1]) or cap
local last   = tonumber(s[2]) or now

tokens = math.min(cap, tokens + (now - last) * rate)  -- lazy refill
local ok = 0
if tokens >= req then tokens = tokens - req; ok = 1 end

redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { ok, tokens }

Now the cost. Every algorithm pays one Redis round trip per request in this atomic design. In-datacenter that RTT is roughly 0.3 to 0.5ms. That number is fine at low volume and ruinous at high volume, and here is why the sliding log is disqualified again: its atomic script does ZREMRANGEBYSCORE plus ZCARD plus ZADD on a set sized by the client’s volume, so its per-op CPU on the shard scales with the heaviest client, while the bucket algorithms do a fixed handful of hash field ops regardless of load.

Rough per-request coordination cost, measured against a single Redis shard with the atomic scripts above:

At a million checks per second a single shard cannot hold the op rate no matter which algorithm you pick, so you shard by client_id (hash(client_id) % shards) and each atomic op touches exactly one shard. That spreads load, but every request still pays a round trip.

Killing the round trip: local buckets plus sync

The move that actually matters at scale is to stop asking Redis per request. Each instance keeps a local token bucket per hot client and reconciles with Redis periodically. Token bucket and leaky bucket make this easy because their state is two commutative-ish numbers; a batched reservation works cleanly.

Batched reservation:
  - instance atomically claims 10 tokens from the global bucket (1 round trip)
  - serves 10 requests locally, zero Redis calls
  - claims another batch when its local reservation runs low

Effect: 10x fewer round trips, at the cost of bounded overshoot
  (an instance holding an unused reservation when the window shifts
   can let the global count run slightly over the limit)

This is a real trade, not a free win. The overshoot is bounded by num_instances * batch_size in the worst case, and you tune batch size to move the dial between Redis load and accuracy. Fixed window and sliding counter can do a coarser version of this (claim a slice of the window’s quota), but the log cannot batch at all - it needs the exact set of timestamps centrally, so it is stuck paying a round trip per request forever. That is the third and final reason the log does not scale.

Per-request coordination, 40 instances, limit 100/min per client:

  Round-trip-per-request:   1,000,000 Redis ops/sec  ->  needs ~7+ shards
  Batched (size 10):          100,000 Redis ops/sec  ->  fits on 1-2 shards
  Trade: up to num_instances * 10 overshoot on the global limit

What actually works

After all four, here is the honest guidance.

• Never ship fixed window as a real limit. The boundary doubling is not theoretical; any client that retries on 429 or batches its calls will hit it. The only place it belongs is a rough internal ceiling where 2x overshoot genuinely does not matter.
• Token bucket is the right default for client-facing API limits. Bursts are how real clients behave, the capacity and refill knobs are independent so you can shape it exactly, its state is O(1) and cheap to coordinate, and it batches for the local-plus-sync design. When someone says “add rate limiting to the API,” this is almost always the answer.
• Sliding window counter when you must forbid bursts and want it cheap. If the promise is “no more than 100 in any 60 seconds, period, no burst allowance,” the counter gives you that at roughly 20% worst-case overshoot and O(1) memory. Reach for it over the log unless you need exactness.
• Leaky bucket when you are protecting something downstream that needs a steady input. Not for shaping client behavior, but for smoothing your own outbound traffic to a fragile dependency or a metered third party. Different job entirely.
• Sliding window log only for low-volume, high-precision limits. A limit of 5 login attempts per hour on a security endpoint is a perfect fit: exact accuracy, and the volume is so low the memory and per-op CPU never matter. At API scale it is a reference implementation, not a production one.

And the meta-point: the algorithm choice is a few percent of the effort. The coordination design - atomic ops, sharding, and the local-bucket-plus-sync trade that trades bounded overshoot for killing the per-request round trip - is where the real engineering is, and it is the same problem no matter which of these four you picked. The INCR was never the hard part.