Token Bucket vs Sliding Window Rate Limiting

Most rate-limiting arguments are really arguments about bursts. A token bucket lets an idle client accumulate allowance and spend it at once, which is friendly to well-behaved batch clients and unhelpful when the thing being limited is password guessing. A sliding window enforces a ceiling over the trailing interval regardless of how the requests are spaced, which is exactly right for authentication and slightly annoying for a client that wanted to sync fifty records in one go.

This guide compares the two on the properties that matter, gives an atomic Redis implementation of each, and states which abuse patterns each one actually stops. It is part of the API Rate Limiting & Abuse Prevention guide within Vulnerability Patterns & Web Mitigation Strategies.

Prerequisites

  • Redis 6 or newer reachable from every instance, with scripting enabled
  • A decision about which identity each endpoint counts against
  • Observed request-rate percentiles for the endpoints you intend to limit
  • A load-testing tool that can generate a burst at a chosen instant

Expected Outcomes

  • An informed choice of algorithm per endpoint class rather than one global default
  • An atomic implementation that cannot be raced by concurrent requests
  • No fixed-interval boundary that can be straddled to double the limit
  • Memory cost per key measured at your actual key cardinality

Step 1: Compare the Behaviours That Matter

Property Token bucket Sliding window (log) Sliding window (approximate)
Burst behaviour Allows an accumulated burst up to capacity No burst beyond the ceiling Nearly none
Boundary abuse Not possible Not possible Slight over-admission near a boundary
Memory per key Two numbers One timestamp per request in the window Two counters
Cost to evaluate Constant Proportional to requests in the window Constant
Best for General API traffic, generous ceilings Authentication, metered actions, hard ceilings High-cardinality capacity limits
Worst for Guessing attempts, where burst is the attack Very high request rates per key Cases where exactness is required
The Same Traffic, Three Different Verdicts One request pattern evaluated three ways. The token bucket admits an initial burst because allowance accumulated while the client was idle. The fixed window admits the full quota at the end of one interval and again immediately after the boundary, allowing double the intended rate. The sliding window admits a steady stream up to the ceiling and refuses the rest regardless of position. Token bucket — capacity 10, refill 1 per 6 seconds idle client spends 10 at once, then 1 every 6 seconds burst allowed by design Fixed window — 10 per minute 10 at 00:59, then 10 more at 01:00 — 20 in two seconds double rate at the boundary Sliding window — 10 per trailing minute never more than 10 in any 60-second span, wherever it starts the ceiling means what it says

Step 2: Implement Each One Atomically

A limiter that reads, decides and writes in three round trips can be raced: two concurrent requests both read nine of ten used, both decide there is room, and both proceed. Do the whole operation in one server-side script.

Why the Decision Must Be One Round Trip With three separate round trips, two concurrent requests can both read nine of ten used, both decide there is room, and both proceed — so the ceiling is exceeded exactly when traffic is heaviest. A single server-side script performs the read, the decision and the write atomically, so concurrency cannot produce a state neither request would have permitted alone. Read, decide, write as three commands two parallel requests both observe room and both proceed; the limit is exceeded The failure appears only under concurrency which is precisely the condition attack traffic arrives in One server-side script performing all three the decision is atomic, so parallel requests are serialised by the store itself 
-- token_bucket.lua — KEYS[1] state key; ARGV: capacity, refill/sec, now, cost
local capacity, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + (now - ts) * rate)   -- refill for elapsed time
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) * 2)
return { allowed and 1 or 0, math.floor(tokens) }
-- sliding_log.lua — KEYS[1] sorted set; ARGV: window seconds, max, now, member id
local window, maxn, now, member = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), ARGV[4]

redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)  -- drop what has aged out
local used = redis.call('ZCARD', KEYS[1])
if used >= maxn then
  local oldest = redis.call('ZRANGE', KEYS[1], 0, 0, 'WITHSCORES')
  return { 0, math.ceil(oldest[2] + window - now) }       -- exact retry-after
end

redis.call('ZADD', KEYS[1], now, member)
redis.call('EXPIRE', KEYS[1], window)
return { 1, 0 }

The log variant gives an exact Retry-After for free, because it knows when the oldest request in the window ages out — a small detail that materially improves client behaviour under load.

Step 3: Choose Per Endpoint Class, Not Globally 

const POLICY = {
  'auth.login':      { algo: 'sliding-log', window: 900,  max: 10  },  // ceiling is the security property
  'auth.reset':      { algo: 'sliding-log', window: 3600, max: 5   },
  'message.send':    { algo: 'sliding-log', window: 86400, max: 200 }, // metered: exactness matters
  'api.read':        { algo: 'token-bucket', capacity: 120, refill: 2 },   // bursts are legitimate
  'api.write':       { algo: 'token-bucket', capacity: 30,  refill: 0.5 },
  'catalogue.list':  { algo: 'sliding-approx', window: 60, max: 600 },     // high cardinality, capacity only
} as const;

The rule of thumb is short: if exceeding the number is a security event, use a sliding window; if exceeding it is merely expensive, a bucket is friendlier and cheaper.

Choosing by What the Limit Is For A two-by-two selection guide. When the ceiling is a security property and bursts are illegitimate, use a sliding log. When the ceiling is a security property but modest bursts are fine, still use a sliding window with a slightly higher maximum. When the limit exists for capacity and bursts are legitimate, use a token bucket. When cardinality is very high and approximation is acceptable, use the weighted approximation. Ceiling is a security property Limit exists for capacity Bursts are not legitimate Sliding log login, reset, metered sends Sliding approximation high-cardinality read paths Bursts are normal client behaviour Sliding window, higher max exactness kept, headroom added Token bucket general API traffic, sync clients

Verification 

# 1. Boundary test: the classic fixed-window doubling must not be possible.
#    Send the full quota just before a minute boundary, then again just after.
python3 - <<'PY'
import time, requests
url, headers = "http://localhost:3000/api/search", {"Cookie": SESSION}
time.sleep(60 - time.time() % 60 - 1.0)              # land just before the boundary
first  = sum(requests.get(url, headers=headers).status_code == 200 for _ in range(30))
time.sleep(1.5)                                       # cross the boundary
second = sum(requests.get(url, headers=headers).status_code == 200 for _ in range(30))
print(first, second, "→ sum must not exceed the per-window maximum")
PY

# 2. Concurrency test: 50 parallel requests against a limit of 10 must admit exactly 10.
seq 50 | xargs -P50 -I{} curl -s -o /dev/null -w '%{http_code}\n' \
  -H "Cookie: $SESSION" http://localhost:3000/api/export | sort | uniq -c
# Expected: 10 with 200, 40 with 429 — any other split means the check is not atomic.

The concurrency test is the one that catches a non-atomic implementation, and a non-atomic limiter fails precisely when it matters, because attack traffic is parallel by nature.

Troubleshooting

Symptom Likely cause Fix
More requests admitted than the limit under load Read-modify-write split across round trips Move the whole decision into one server-side script
Clients occasionally get double the quota Fixed window rather than sliding Switch to a sliding variant, or accept the doubling explicitly
Memory growth in the counter store Sliding log at high cardinality, or missing expiry Set an expiry inside the script; move read paths to the approximation
Retry-After values are wrong Computed from the window length rather than the oldest entry Return the exact expiry from the log implementation
Limits behave differently per instance Local in-process fallback active because the store is unreachable Alert on fallback activation; treat it as an incident, not a fallback
Legitimate batch clients constantly throttled Sliding window applied where bursts are normal Move that endpoint class to a bucket with a capacity sized to the batch

Common Implementation Mistakes

Frequently Asked Questions

Which algorithm should I use for a login endpoint?

A sliding window. On authentication the ceiling per interval is the security property, and a burst allowance is a gift to whoever is guessing. Ten attempts per fifteen minutes should mean exactly that, not ten immediately followed by a steady refill that permits another ten a few minutes later. Bucket refill suits ordinary API traffic; it does not suit guessing.

Is a fixed window ever acceptable?

Only where doubling the limit at a boundary is harmless — a coarse capacity guard in front of a cache, for example. The failure mode is easy to state and easy to exploit: send the full quota at the end of one interval and the full quota again at the start of the next, and you have achieved twice the intended rate in a couple of seconds. That is unacceptable on anything security-relevant.

How much accuracy does the approximate sliding window lose?

The weighted-two-window approximation stays within a few percent for smooth traffic and errs slightly permissive for bursts near a boundary — an acceptable trade for capacity limits at high key cardinality. Where the number has to be exact, such as a hard daily ceiling on a metered action, keep the timestamp log for that key. It costs more memory and never over-admits, which is the right priority when each admitted request spends money.