DEV Community: Darshil Somani

Token Bucket vs. Sliding Window: Building Rate Limiters That Actually Hold Under Load

Darshil Somani — Fri, 14 Aug 2026 03:14:12 +0000

Rate limiting sounds like a solved problem until you actually implement one and watch it fail in a way your load test didn't predict: legitimate bursts getting rejected, or a limiter that lets through 2x its stated limit at window boundaries. The failure modes are specific enough that it's worth working through the two dominant algorithms — token bucket and sliding window — with actual code, not just the diagrams.

The problem with fixed windows

The naive approach almost everyone reaches for first is a fixed window counter: pick a window size (say, 60 seconds), count requests in that window, reset the counter when the window rolls over.

import time

class FixedWindowLimiter:
    def __init__(self, limit: int, window_seconds: int):
        self.limit = limit
        self.window_seconds = window_seconds
        self.count = 0
        self.window_start = time.time()

    def allow(self) -> bool:
        now = time.time()
        if now - self.window_start >= self.window_seconds:
            self.window_start = now
            self.count = 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False

This is simple and cheap, and it's also broken in a specific, exploitable way. Say the limit is 100 requests/minute. A client can send 100 requests in the last second of window N, then another 100 in the first second of window N+1. That's 200 requests in roughly two seconds, well within the letter of "100/minute" as the code enforces it, but nowhere near the spirit of it. This is the classic boundary-burst problem, and it's the reason fixed windows get replaced once traffic is adversarial or bursty enough to find the seam.

Sliding window: smoothing the boundary

A sliding window log fixes this by tracking actual timestamps instead of a single counter, and counting how many fall within the trailing window at the moment of the request:

from collections import deque
import time

class SlidingWindowLogLimiter:
    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window_seconds = window_seconds
        self.timestamps = deque()

    def allow(self) -> bool:
        now = time.time()
        cutoff = now - self.window_seconds
        while self.timestamps and self.timestamps[0] < cutoff:
            self.timestamps.popleft()
        if len(self.timestamps) < self.limit:
            self.timestamps.append(now)
            return True
        return False

This is exact — no boundary exploit — but it costs memory proportional to the request rate, since you're storing a timestamp per request within the window. For a single client that's fine. For a service rate-limiting thousands of distinct API keys, storing an unbounded deque per key is a real cost, and it's the reason production systems usually use an approximation instead of the exact log.

Sliding window counter: the practical middle ground

The approximation that shows up in most real infrastructure (this is roughly what Cloudflare and several API gateways describe publicly) is the sliding window counter: keep two fixed-window counters, the current one and the previous one, and weight the previous window's count by how much of it still overlaps the trailing window.

import time

class SlidingWindowCounterLimiter:
    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window_seconds = window_seconds
        self.curr_window = 0
        self.curr_count = 0
        self.prev_count = 0

    def _window_id(self, now: float) -> int:
        return int(now // self.window_seconds)

    def allow(self) -> bool:
        now = time.time()
        window = self._window_id(now)

        if window != self.curr_window:
            if window == self.curr_window + 1:
                self.prev_count = self.curr_count
            else:
                self.prev_count = 0
            self.curr_count = 0
            self.curr_window = window

        elapsed_in_curr = now - (window * self.window_seconds)
        weight = max(0.0, (self.window_seconds - elapsed_in_curr) / self.window_seconds)
        estimated = self.curr_count + self.prev_count * weight

        if estimated < self.limit:
            self.curr_count += 1
            return True
        return False

This trades exactness for O(1) memory per client, and the error it introduces is bounded and well understood: it assumes requests are uniformly distributed within the previous window, which is an approximation, not a guarantee. In practice the deviation from the true sliding-window-log count is small enough to be irrelevant for the rate limits most APIs actually enforce.

Token bucket: allowing controlled bursts on purpose

Both algorithms above treat any burst as something to suppress. Token bucket takes a different stance: it explicitly allows bursts up to a configured size, while still enforcing a long-run average rate. This matches how a lot of real traffic actually behaves — a client that's been idle for a while and then needs to catch up shouldn't be penalized as harshly as one hammering the endpoint continuously.

The mechanism: a bucket holds up to capacity tokens. Tokens refill continuously at rate tokens/second. Each request consumes one token; if the bucket is empty, the request is rejected.

import time
import threading

class TokenBucketLimiter:
    def __init__(self, rate: float, capacity: float):
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()

    def allow(self, cost: float = 1.0) -> bool:
        with self.lock:
            now = time.monotonic()
            elapsed = now - self.last_refill
            self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
            self.last_refill = now

            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False

Two details here matter more than they look:

time.monotonic(), not time.time(). Wall-clock time can jump backward (NTP adjustment, manual clock change) and a backward jump would let elapsed go negative, which either refills nothing or, worse, corrupts the token count depending on how you guard it. Monotonic clocks never go backward within a process's lifetime, which is exactly the guarantee a refill calculation needs.
The lock. A rate limiter is almost always shared across concurrent request handlers. Without the lock, two threads can both read self.tokens as sufficient, both decrement, and let through one more request than the bucket should have allowed — a classic check-then-act race. The lock has to wrap the read-modify-write of tokens, not just the final comparison.

The cost parameter is worth calling out too: not all requests are equal. A bulk export endpoint might reasonably cost 10 tokens while a status check costs 1. Token bucket handles variable cost naturally; fixed and sliding window counters do not, without extra bookkeeping.

Distributed rate limiting: why single-process code isn't enough

Everything above lives in one process's memory. The moment you run more than one instance of a service behind a load balancer, a per-process limiter is enforcing the limit per instance, not per client — five instances each independently allowing 100 req/min gives a client 500 req/min in aggregate, not 100.

The standard fix is to move the state into something shared, usually Redis, and to make the check-and-decrement atomic so concurrent requests across instances don't race the same way threads did above. A minimal token bucket in Redis using a Lua script (so the read-refill-check-decrement sequence is atomic on the Redis side):

-- KEYS[1] = bucket key, ARGV[1] = rate, ARGV[2] = capacity, ARGV[3] = now, ARGV[4] = cost
local bucket = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(bucket[1]) or tonumber(ARGV[2])
local ts = tonumber(bucket[2]) or tonumber(ARGV[3])
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * rate)

local allowed = 0
if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
end

redis.call("HMSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("EXPIRE", KEYS[1], math.ceil(capacity / rate) + 1)
return allowed

Running this as a Lua script means Redis executes it atomically — no other client's script can interleave between the read and the write, which is exactly the race the in-process lock was preventing, now solved across processes instead of across threads. The EXPIRE call matters for a different reason: without it, every client that ever made one request leaves a key in Redis forever. Setting the TTL to roughly the time it takes the bucket to fully refill means idle clients' keys disappear on their own.

Picking one

None of these is strictly better; they answer different questions:

Fixed window: only when the boundary-burst issue is genuinely acceptable for your traffic (e.g., you're limiting something coarse like daily export quota, where a burst around midnight doesn't matter).
Sliding window log: when you need exact enforcement and can afford the memory — typically low-cardinality cases like a handful of high-value API keys, not millions of anonymous IPs.
Sliding window counter: the default choice for most API gateways — bounded memory, small and well-understood approximation error, no burst exploit.
Token bucket: when controlled bursts are a feature, not a bug — a client that saved up quota by being idle should be able to spend it faster than the steady-state rate, up to the bucket's capacity.

The thing worth internalizing is that "rate limiting" isn't one algorithm with configuration knobs — the four approaches above encode genuinely different policies about what a burst means, and picking the wrong one shows up as either angry users hitting a limit that shouldn't have triggered, or an abuse vector that technically respects the stated rate while defeating its purpose.

Idempotency Keys: Designing APIs That Survive Retries

Darshil Somani — Mon, 10 Aug 2026 00:05:19 +0000

Every API that sits behind an unreliable network eventually faces the same problem: a client sends a request, the connection drops before the response arrives, and the client has no idea whether the operation happened. Did the payment go through? Did the order get created twice? The client's only safe move is to retry — which means your server needs a story for what happens when the same "create this thing" request arrives more than once.

That story is idempotency keys, and getting the details right is more subtle than it first looks.

The core idea

The client generates a unique token — typically a UUID — once per logical operation, and attaches it to every retry of that operation:

POST /orders
Idempotency-Key: 7c3fd9a2-df01-4b3e-9a55-1e5f9b6b6d55

{"sku": "WIDGET-1", "qty": 2}

The server's job is to guarantee that no matter how many times a request with that key arrives, the side effect (charging a card, creating an order, sending an email) happens at most once, and every retry gets back the same response the original request would have produced.

Note what this is not: it is not deduplicating by request body. Two requests with identical bodies but no key are legitimately two different orders for two widgets. The key is what marks them as "the same attempt," not the payload.

The naive approach, and why it breaks

A common first pass is a table like:

CREATE TABLE idempotency_keys (
  key TEXT PRIMARY KEY,
  response_body JSONB,
  status_code INT
);

On each request: check if the key exists, and if so return the cached response; otherwise do the work and insert the result. This looks right and is wrong in a specific way: it has a race condition. Two retries can arrive concurrently (a client that timed out and fired a second attempt while the first was still in flight), both miss the cache check, and both execute the underlying operation. You've now charged the card twice.

Making the check-and-do atomic

The fix is to claim the key before doing the work, using the database's own concurrency control rather than an application-level check:

CREATE TABLE idempotency_keys (
  key TEXT PRIMARY KEY,
  status TEXT NOT NULL DEFAULT 'in_progress',
  response_body JSONB,
  status_code INT,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

INSERT INTO idempotency_keys (key, status)
VALUES ($1, 'in_progress')
ON CONFLICT (key) DO NOTHING
RETURNING key;

If the INSERT returns a row, you won this key — proceed with the operation, then update the row with the real response and flip status to 'completed'. If it returns nothing, someone else already claimed this key. Now you have three sub-cases to handle explicitly:

status = 'completed' — return the stored response verbatim. This is the retry-after-success path, and it's the one people design for.
status = 'in_progress' — another request with the same key is still executing right now, most likely a genuinely concurrent retry (client-side timeout that fired a duplicate before the first attempt returned). The correct response here is usually 409 Conflict with a "retry shortly" hint, not silently blocking, because blocking ties up a connection for as long as the original request takes and can cascade under load.
status = 'failed' — the original attempt errored out before completing. Whether this is safe to retry depends on whether the failure happened before or after the side effect committed, which is exactly why the next section matters.

Ordering the side effect and the key update

The dangerous window is between "the side effect happened" and "the key record says it happened." If your payment provider charges the card and then your process crashes before writing status = 'completed', the key is stuck at in_progress (or failed, if you have a crash handler) forever, and a legitimate retry will either be rejected or — worse, if you designed the failed-state to allow retry — will charge the card again.

Two practical ways out:

Same transaction, when possible. If the side effect is itself a database write (create an order row), do it in the same transaction as the key update. Either both commit or neither does, and there's no window at all.
External side effect, idempotent downstream. If the side effect is a call to a third party (a payment processor), pass that call an idempotency key too — most payment APIs (Stripe, Braintree, Razorpay) support this natively. Then your recovery path for a crashed in_progress row is: re-issue the downstream call with the same downstream key. If it already happened, the processor returns the original result instead of double-charging. Your own key table becomes a cache in front of an idempotent downstream operation, not the sole source of truth.

Key scope and expiry

Keys should be scoped per-endpoint or per-operation-type, not global — a key valid for POST /orders colliding with an unrelated key namespace for POST /refunds is a bug waiting to happen. Prefix keys by route, or use a composite primary key of (route, key).

Expiry matters too. Clients reuse UUID generation logic, and a key space that never expires grows forever and risks accidental key reuse across unrelated operations months apart. Twenty-four hours is a common TTL: long enough to cover any realistic retry window (including a client that retries after being offline overnight), short enough to bound table growth. Expire with a background job or a partial index plus periodic delete, not by checking created_at on every read — that still requires deciding what "expired" means for a key someone is retrying right at the boundary, so most implementations simply reject requests bearing an expired key and let the client mint a new one, which is equivalent to treating it as a fresh operation.

Handling key reuse with a different payload

What if a client sends the same idempotency key twice, but with a different request body the second time? This usually indicates a client bug — reusing a key across two logically different operations — and the safe response is to reject it (422 with an explanit error) rather than either silently applying the new payload or silently returning the old response. To detect it cheaply, store a hash of the normalized request body alongside the key and compare on the second arrival; a mismatch is the signal.

Testing it

The property you actually want to verify is: N concurrent requests with the same key produce exactly one side effect and N identical successful responses (or, for the couple of concurrent duplicates, one success and N-1 409s that a client is expected to retry). Write this as an actual concurrency test — fire the same key from multiple threads or async tasks at a test server backed by a real database, not a mock, and assert on the row count in the underlying table. The race condition in the naive approach above is invisible in a single-threaded test and only shows up under real concurrency, which is exactly the condition it exists to handle.