Fixed Window Rate Limiter

Fixed-window rate limiting is the simplest possible rate-limit algorithm: divide time into fixed, non-overlapping windows of width W (e.g., one minute each); maintain a single integer counter per (client, window); on each request, atomically increment the counter and reject if it exceeds the limit N; reset (or simply key on a new window identifier) when the boundary rolls over. The data structure is one integer per client per window — typically Redis INCR + EXPIRE, in-memory with a sweep, or a row in a per-window table — and the algorithm is two lines of code. Fixed-window’s defining flaw is the boundary burst: a client can fire N requests at the last instant of one window and another N at the first instant of the next, achieving 2N requests in an arbitrarily short interval that straddles the boundary, while never violating “N per window” by the algorithm’s own bookkeeping. Despite the burst issue, fixed-window remains the default in many production systems — GitHub’s REST API, the X (Twitter) API’s per-endpoint 15-minute windows, most open-source web frameworks’ rate-limit middleware — because the storage and CPU costs are an order of magnitude lower than sliding-window alternatives, and for many APIs the boundary-burst risk is acceptable or mitigated by other layers (e.g., a token-bucket burst limit on the same path).

1. Intuition — A Per-Hour Coffee Allowance

A coffee shop tells regulars “you can order at most three coffees per hour.” The simplest enforcement: a chalkboard with the customer’s name and a tally. Every order increments the tally. At the top of every hour, a fresh sheet replaces the old one — tallies reset to zero.

This is the fixed-window rate limiter: count requests inside a clock-aligned bucket of width W; reject when the count exceeds N; reset at the boundary. The shop never has to remember exactly when each coffee was ordered, just how many in the current hour.

The flaw in the chalkboard metaphor reveals the algorithm’s flaw. Suppose the limit is 3 per hour. At 9:59 the customer orders 3 coffees (tally hits 3, no more allowed this hour). At 10:00 the sheet flips. At 10:01 the customer orders 3 more. The shop allowed 6 coffees in 2 minutes — but according to the per-hour bookkeeping, neither hour ever exceeded 3. That’s the boundary burst. The algorithm is faithful to the rule “≤3 per chalkboard hour,” but the rule itself doesn’t capture what the shop owner probably meant (no more than 3 per any 60-minute interval).

For a real API, the boundary burst means a misbehaving client can briefly push 2N requests through a window-straddling moment, often coinciding with cron-job scheduling at minute/hour boundaries (a notorious thundering-herd source). Whether that matters depends on the budget you’re protecting:

• Backend CPU/IO: transient 2× spikes are usually absorbable.
• Downstream-service quota: if your downstream itself runs fixed-window rate limiting at the same boundary, you can exhaust their quota in seconds.
• Cost-budgeting (e.g., per-minute API spend): 2× spike still maps to a 2× cost and may exceed budgeted line-item.

The intuition for why we tolerate this in production: the simplicity dividend is huge. One integer per (client, window). One Redis INCR, one EXPIRE. No per-request timestamps. No sliding aggregations. At Stripe-or-Cloudflare scale the difference between “1 byte per client per minute” and “256 bytes per client” is the difference between fitting hot-path state in RAM versus needing a tier of slower storage.

2. Tiny Worked Example — Limit 5 Requests per 60-Second Window

Suppose N = 5 requests per W = 60 seconds. Trace one client’s requests over two windows.

Window 1: [t=0s, t=60s)        Window 2: [t=60s, t=120s)
counter[client, 0]               counter[client, 1]

t=  0s   request → counter=1   ALLOW
t=  5s   request → counter=2   ALLOW
t= 10s   request → counter=3   ALLOW
t= 30s   request → counter=4   ALLOW
t= 55s   request → counter=5   ALLOW
t= 56s   request → counter=6   REJECT (>5)
t= 58s   request → counter=7   REJECT
t= 59s   request → counter=8   REJECT

Window 1 ends at t=60s. Counter for window 0 may stay or be evicted.

t= 60s   request → counter[client, 1]=1   ALLOW
t= 61s   request → counter[client, 1]=2   ALLOW
t= 62s   request → counter[client, 1]=3   ALLOW
t= 63s   request → counter[client, 1]=4   ALLOW
t= 64s   request → counter[client, 1]=5   ALLOW
t= 65s   request → counter[client, 1]=6   REJECT

The bookkeeping is honest by its own rule: window 1 saw 5 ALLOWs (and some REJECTs), window 2 saw 5 ALLOWs. But the client achieved 10 ALLOWed requests in a 10-second span (t=55s to t=64s). That is 2× the nominal rate of 5 requests per minute, sustained for one boundary-straddling moment.

This is the canonical demonstration. If a malicious client knows the boundary, they can plan their bursts. Even a non-malicious client may exhibit this behavior if they have a cron job running at :00 of every minute — many naive cron schedules cluster requests at second-boundary moments, producing the same effect by accident.

3. Algorithm and Pseudocode

The straightforward implementation:

def allow(client_id, now, limit_N, window_W):
    window_id = floor(now / window_W)
    key = (client_id, window_id)
    counter[key] = counter.get(key, 0) + 1     # atomic
    if counter[key] > limit_N:
        return False, retry_after = (window_id + 1) * window_W - now
    return True, retry_after = 0

The two non-obvious requirements:

1. The increment + check must be atomic. Two requests arriving simultaneously must see consistent counter values; otherwise both can pass an INCR that takes the counter from 5 to 7, both seeing “≤5” because they read the pre-increment value. In Redis this is achieved by INCR (atomic increment, returns the post-increment value).
2. Counter values must expire. A client who makes one request and disappears must not leave a row in the table forever. In Redis: INCR followed by EXPIRE (set TTL = W). In an in-memory hash table, a periodic sweep evicts windows with window_id < floor(now/W) − k for some small k.

The Redis idiom (Stripe’s approach):

MULTI
    INCR rate:{client_id}:{window_id}
    EXPIRE rate:{client_id}:{window_id} 60
EXEC

A MULTI/EXEC transaction does run its queued commands atomically — Redis is single-threaded and executes the whole transaction with no other client’s commands interleaved, so the INCR and the EXPIRE always apply to the same key state. The reason production code reaches for a Lua script instead is not atomicity of two unconditional commands but conditional logic: you only want to call EXPIRE on the first request to a fresh key (when INCR returns 1), so that an in-flight window’s TTL is not repeatedly reset to a full W on every request — which would let an active client’s window never expire. A plain MULTI/EXEC cannot branch on the value INCR returned (the reply is not available until EXEC), whereas a Lua script can read INCR’s return value and decide whether to EXPIRE. Lua also collapses the two round-trips into one and runs server-side without interruption.

Cloudflare’s rate-limiting write-up describes keeping each counter to two integers and incrementing with a single INCR against their memcached-backed counter store (per the Cloudflare blog).

4. Python Implementation

A single-process implementation suitable for testing or single-instance services:

from __future__ import annotations
import time
import threading
from collections import defaultdict
from typing import Tuple
 
 
class FixedWindowRateLimiter:
    """Single-process, thread-safe fixed-window rate limiter.
 
    For multi-process / distributed: replace the `_counters` dict with Redis INCR + EXPIRE.
    """
 
    def __init__(self, limit: int, window_seconds: float):
        if limit <= 0:
            raise ValueError("limit must be > 0")
        if window_seconds <= 0:
            raise ValueError("window_seconds must be > 0")
        self.limit = limit
        self.window = window_seconds
        # _counters[client_id][window_id] = count
        self._counters: dict[str, dict[int, int]] = defaultdict(dict)
        self._lock = threading.Lock()
 
    def _window_id(self, now: float) -> int:
        return int(now // self.window)
 
    def allow(self, client_id: str, now: float | None = None) -> Tuple[bool, float]:
        """Returns (allowed, retry_after_seconds).
 
        retry_after_seconds is 0 when allowed, else the time remaining in
        the current window.
        """
        if now is None:
            now = time.time()
        wid = self._window_id(now)
        with self._lock:
            client = self._counters[client_id]
            # Garbage-collect old windows for this client
            stale = [w for w in client if w < wid]
            for w in stale:
                del client[w]
            count = client.get(wid, 0) + 1
            client[wid] = count
            if count > self.limit:
                retry_after = (wid + 1) * self.window - now
                return False, retry_after
            return True, 0.0
 
 
# Example
if __name__ == "__main__":
    rl = FixedWindowRateLimiter(limit=5, window_seconds=60)
    base = 0.0
    for t_offset in [0, 5, 10, 30, 55, 56, 58, 59,   # window 0
                     60, 61, 62, 63, 64, 65]:        # window 1
        ok, retry = rl.allow("client-A", now=base + t_offset)
        print(f"t={t_offset:3.0f}s  allowed={ok}  retry_after={retry:.2f}s")

The output reproduces the boundary-burst trace from §2 — 10 ALLOWs straddling t=55s..t=64s, even though no individual window exceeds 5.

A Redis-backed version (using redis-py):

import redis
 
redis_client = redis.Redis()
 
LUA_FIXED_WINDOW = """
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local count = redis.call('INCR', key)
if count == 1 then
    redis.call('EXPIRE', key, window)
end
if count > limit then
    return {0, redis.call('PTTL', key)}
end
return {1, 0}
"""
 
_script = redis_client.register_script(LUA_FIXED_WINDOW)
 
 
def allow_redis(client_id: str, limit: int = 5, window: int = 60):
    import time
    wid = int(time.time() // window)
    key = f"rate:{client_id}:{wid}"
    allowed, ttl_ms = _script(keys=[key], args=[limit, window])
    return bool(allowed), (ttl_ms / 1000.0 if not allowed else 0.0)

The Lua script ensures INCR and EXPIRE are atomic — important on the first request to a fresh key, where without atomicity a crash between INCR and EXPIRE would leave a key with no TTL (memory leak).

5. Complexity

Quantity	Cost
Per-request CPU	O(1) — one increment, one comparison
Per-request storage	O(1) — one integer per (client, window)
Active state size	O(active clients × max-windows-retained)
Network round-trips (Redis)	1 per request
Counter precision	Limit is enforced exactly per-window; not over arbitrary intervals

The state size argument is what makes fixed-window attractive at scale. With 1 minute windows and TTL-eviction, you store one integer per client that requested in the last minute. At 10⁹ unique clients per day but only ~10⁷ active per minute, fixed-window state is ~80 MB; sliding-window with per-request timestamps would be 80–800× more.

What “rate” does fixed-window actually enforce?

The strict mathematical guarantee is count ≤ N within any clock-aligned window of width W. That is a strictly weaker statement than ”≤ N within any width-W interval,” and the gap is exactly the boundary burst. Consider an arbitrary (not clock-aligned) interval that straddles a boundary: place N requests in window k arbitrarily close to its right edge (at time (k+1)·W − ε), and another N requests in window k+1 arbitrarily close to its left edge (at time (k+1)·W). An interval of width 2ε — which can be made far smaller than W — then contains all 2N requests, yet neither clock-aligned window ever exceeded N. So the worst-case burst across the boundary is exactly 2N, achievable within an interval of width arbitrarily less than W (the often-quoted “2N − 1” undercounts by one — there is nothing preventing the full N-th request of each window from landing on either side of the boundary). The naive marketing claim “rate ≤ N/W per second” is therefore wrong — the algorithm only bounds clock-aligned-window counts, and the instantaneous rate across a boundary can momentarily double. This 2× ceiling is corroborated across the standard references: a “10 per 10 s” fixed window can pass 20 requests in a ~2 s span straddling the reset (per node-rate-limiter-flexible’s write-up).

A loose upper bound in the other direction: the long-term average rate is at most N/W (over many windows the boundary effect washes out, since each clock-aligned window still admits at most N), but any single short interval straddling a boundary can see up to 2N requests.

6. Variants and Production Examples

6.1 Multi-Tier Fixed Windows

Real APIs combine fixed-window limits at multiple time scales — e.g., 100/min AND 1000/hour AND 10000/day — to bound bursts at all relevant scales. Each tier is a separate counter; a request must pass all tiers to be allowed. GitHub’s REST API is a layered variant of this: a primary rate limit of 5,000 requests/hour for an authenticated user (15,000/hour for GitHub Apps and OAuth apps owned by an Enterprise Cloud org), exposed via the x-ratelimit-limit / x-ratelimit-remaining / x-ratelimit-reset headers, plus separate secondary rate limits that bound short-burst and concurrency behavior (per the GitHub REST API rate-limit docs). HTTP/2 mandates lowercase header field names, which is why GitHub’s headers appear as x-ratelimit-*; header names are case-insensitive, so X-RateLimit-Remaining and x-ratelimit-remaining refer to the same field.

6.2 Hybrid: Fixed Window + Token Bucket

To mitigate boundary bursts cheaply, deploy fixed-window for the quota (e.g., 10000 per day) and token-bucket for the burst (e.g., 50 per second with burst 100). The fixed-window catches abuse over long intervals; the token bucket smooths short-interval bursts. This layering shows up in production: AWS API Gateway pairs a token-bucket throttle (steady-state rate + burst) with separate per-day/week/month usage-plan quotas (per the AWS throttling docs).

Uncertain

Verify: the specific claim that Stripe and Cloudflare deploy a fixed-window-quota + token-bucket-burst combination. Reason: Stripe’s blog (stripe.com/blog/rate-limiters) documents a request-rate token bucket plus a separate concurrency limiter — not a fixed-window quota tier; Cloudflare’s blog (blog.cloudflare.com/counting-things-a-lot-of-different-things) documents a sliding-window counter, not a token-bucket burst overlay. The general fixed-window-plus-token-bucket pattern is sound and used in the wild (AWS above), but attributing it specifically to Stripe and Cloudflare is not supported by their primary write-ups. To resolve: cite a primary source that shows either company combining a fixed-window quota with a token-bucket burst limiter, or drop the attribution. uncertain

6.3 Sliding-Window Counter (Approximate Fix)

A halfway house between fixed and true sliding windows: store counters for the current and previous windows, and compute a weighted estimate — e.g., if 30 seconds into the new window, the effective count is 0.5 · prev_count + curr_count. Cloudflare’s blog post describes this as their preferred algorithm: it eliminates the worst boundary burst (estimated count rises smoothly across the boundary) at the cost of two counters per client instead of one. See Sliding Window Rate Limiter for the full version.

6.4 Production Examples

• GitHub REST API uses a fixed window of 5,000 requests/hour per authenticated user. The x-ratelimit-reset header gives the window-reset timestamp (UTC epoch seconds) — i.e. the boundary at which the count returns to the full allowance — and the docs explicitly advise waiting until that time before retrying, which is the fixed-window reset contract (per GitHub’s docs). This is the canonical fixed-window example in public web APIs.
• AWS API Gateway does not use fixed-window — it throttles “using the token bucket algorithm, where a token counts for a request,” with a configurable steady-state rate (the rate at which tokens are added to the bucket) and burst (the bucket capacity, i.e. the target maximum number of concurrent submissions before 429 Too Many Requests is returned) (per the AWS API Gateway throttling docs). It is listed here as a deliberate contrast: a widely-cited “API throttler” people sometimes assume is fixed-window but is actually a token bucket. Throttles and quotas are applied “on a best-effort basis and should be thought of as targets rather than guaranteed request ceilings.” (AWS Usage Plans add a separate per-client request quota over a day/week/month period — that quota is a fixed-window counter, distinct from the token-bucket throttle.)
• X (formerly Twitter) API v2 uses fixed windows: “Limits are shown per 15 minutes unless otherwise noted (e.g., ‘/24hrs’ or ‘/sec’),” and the x-rate-limit-reset response header carries the “Unix timestamp when window resets” — a defined window endpoint after which the allowance resets to maximum, which is the fixed-window signature (per the X API rate-limits docs). Limits are per-endpoint (e.g. 450 requests / 15 min on recent-search), and the rejection contract is 429 followed by waiting until x-rate-limit-reset. The per-window-reset semantics have been stable through the v1.1 → v2 transition even as the numeric limits and access tiers churned.
• Redis basic patterns (the INCR + EXPIRE recipe) are documented in Redis’s rate limiting tutorials. This is the standard reference implementation taught in system-design interview prep.
• Kong, Tyk, Envoy rate-limit filters all support fixed-window as a built-in algorithm.
• NGINX limit_req_zone uses leaky-bucket, not fixed-window — a useful contrast.

6.5 Distributed Fixed-Window

In a multi-instance deployment, the counter must be shared. Three patterns:

1. Centralized counter (Redis). Every request hits Redis. Simple but Redis becomes the bottleneck.
2. Local counters with periodic sync. Each instance counts locally, syncs to a central store every k requests or every Δt. Drifts and over-counts during sync windows.
3. Sharded counters. Hash client → instance; each client’s counter lives on one instance. Avoids cross-traffic but needs sticky routing or migration on rebalance. See Consistent Hashing.

Stripe’s blog post confirms pattern 1: “We implement our rate limiters using Redis” — a centralized counter store (per stripe.com/blog/rate-limiters). Cloudflare’s rate-limiting write-up describes per-counter state stored in memcached with the basic GET/SET/INCR operations, kept deliberately tiny (two numbers per counter) so it scales across their edge (per the Cloudflare blog).

Uncertain

Verify: that Cloudflare specifically uses sharded counters (pattern 3) for rate limiting. Reason: the primary Cloudflare blog read here documents memcached-backed counters with tiny per-counter state, but does not explicitly describe a client→shard hashing scheme. To resolve: find a Cloudflare engineering post that details their counter sharding/placement, or soften the claim to “distributed counter store.” uncertain

7. Comparison Table

Algorithm	Burst behavior	State per client	Complexity
Fixed window	Up to 2N at boundary	O(1) integer per window	Simplest
Sliding window log	Exactly N in any interval	O(N) timestamps	Highest
Sliding window counter	~1.1N in pathological case	O(2) integers	Moderate
Token Bucket	Configurable burst ≤ B	O(2) — tokens + last_refill	Smooth
Leaky Bucket	Smooth output rate	O(2) — queue depth + rate	Buffers requests

The reasons to choose fixed window despite the burst issue are concrete: minimum state, minimum CPU, no per-request timestamp comparison, trivial debugging (you can GET the counter and read off the count). For high-cardinality clients (per-IP rate limiting on a CDN edge with 10⁸ IPs/day), fixed-window’s state efficiency is decisive. For low-cardinality, latency-sensitive flows (a few hundred enterprise customers), sliding-window or token-bucket pay off.

8. Pitfalls

8.1 The Boundary Burst (Canonical)

Already discussed — 2N in 2 seconds at the boundary. Mitigations: pair with a token-bucket burst limit, use a sliding-window counter, or accept the risk for non-critical paths.

8.2 Non-Atomic INCR + EXPIRE

On the first request to a key, you do INCR (creates key), then EXPIRE (sets TTL). If the process crashes between, the key has no TTL — and accumulates forever. Fix: use a Lua script (atomic) or SET ... EX ... NX followed by INCRBY, or SET key 1 EX W NX then INCR (the NX version sets if not exists).

8.3 Window Alignment Across Servers

If two servers have unsynchronized clocks (drift > seconds), they map the same now to different window_ids. Mitigation: NTP-synchronize servers; use the Redis clock as authoritative when available.

8.4 Per-Window Counter Ratchet on Time Skew

If client clock skews backward, the same window_id could appear after the next has already started. Always derive window_id from server time, never client-supplied time.

8.5 Over-Counting Failed Requests

Should a request that fails mid-processing count? Some implementations decrement on failure, but this races with concurrent requests and undercounts when crashes happen. Most production code counts attempts, not successes — failure to debit on rejection means an attacker can effectively probe past the limit.

8.6 Forgetting Retry-After Header

HTTP 429 responses (Too Many Requests, RFC 6585) should include a Retry-After header. With fixed windows, the natural value is “seconds until next window boundary.” Forgetting this leads to clients hammering immediately and contributing to backend load.

8.7 Privacy: Per-IP Limiting and CGNAT

Many residential ISPs use Carrier-Grade NAT, multiplexing thousands of users behind one IP. Per-IP fixed-window rate limits with N=100/min may falsely throttle entire neighborhoods. Mitigation: combine IP with user-agent / cookie / authenticated user-id when available.

8.8 First-Request Counter Race

On the first request of a window, all parallel requests see count=0 before incrementing. Without atomic INCR, a burst of parallel requests can all pass the “⇐N” check before any of them increments. Always use atomic primitives.

8.9 Memory Leak from Per-Window Keys

Each window creates a new key. If you do not set TTL, keys accumulate forever. The fix is EXPIRE. With Redis, ensure the eviction policy handles it as well (e.g., volatile-lru).

8.10 Rate Limit on the Wrong Identity

Rate-limiting by API key is the right identity for authenticated APIs; rate-limiting by IP is the right identity for unauthenticated endpoints; rate-limiting by User-Agent is almost always wrong (trivially spoofed). Match identity to threat model.

9. Mermaid Diagram — The Boundary Burst Visualized

gantt
    title Fixed Window: limit=5 per 60s — boundary burst at t=60s
    dateFormat  s
    axisFormat  %S
    section Window 0 [0..60s]
    Allowed (5 reqs)         :done, w0a, 0, 56
    Rejected reqs            :crit, w0r, 56, 60
    section Window 1 [60..120s]
    Allowed (5 reqs)         :done, w1a, 60, 66
    Rejected reqs            :crit, w1r, 66, 120
    section Burst window
    10 reqs in 10s straddle  :active, burst, 55, 65

What this diagram shows. Two adjacent fixed windows, each allowing 5 requests, separated by the boundary at t=60s. Window 0 allows 5 requests by t=56s, then rejects until the boundary. Window 1 immediately allows 5 more starting at t=60s. The bottom row marks the 10-second interval [55s, 65s] in which 10 ALLOWed requests fit — twice the nominal 5/minute rate, sustained for one tenth of a window. No individual window exceeded its quota, yet the effective short-term rate doubled. The diagram emphasizes that the algorithm’s correctness guarantee (”≤ N per clock-aligned window”) and the operator’s intent (”≤ N per any 60s interval”) are different statements; fixed-window honors the former while violating the latter at boundary moments.

10. Common Interview Problems / System-Design Round Questions

Question	What to hit
”Implement a rate limiter with limit N per minute”	Fixed-window: INCR rate:{client}:{floor(now/60)}, compare to N
”What’s the boundary-burst problem?“	2N requests possible across the boundary in arbitrarily short time
”How do you mitigate the boundary burst cheaply?”	Combine fixed-window with token-bucket; or use sliding-window counter
”Why use fixed-window at all?”	One integer per client per window; cheapest distributed primitive
”Make INCR + EXPIRE atomic in Redis”	Lua script, or SET NX with TTL then INCRBY
”How would you scale to 100M clients?”	Sharded counters, eviction by TTL, accept that not every counter fits in RAM
”What HTTP status and headers go with rejection?“	429 Too Many Requests with Retry-After
”Compare fixed-window with token-bucket”	Fixed: simpler, bursty at boundary; token: smooth, configurable burst, more state
”What about clock skew between servers?”	Use a single authoritative clock (e.g., Redis time), NTP-sync, or accept ε
”How do you handle a client behind a NAT?”	Per-IP limits over-throttle; layer with auth identity when possible
”Why doesn’t the long-term rate exceed N/W?”	Boundary effects are transient; over many windows average converges to N/W
”Walk through the trace of 10 requests at 55s..65s with N=5, W=60”	5 allowed in window 0 (t<60), 5 in window 1 (t≥60), 0 rejections in this trace

11. Open Questions

• In a system with extremely tight downstream-quota constraints, is there a fixed-window-like algorithm with bounded boundary error and O(1) state per client? (Sliding-window counter approximates this — does anything do better at the same state cost?)
• How should distributed fixed-window handle clock skew formally — is there a known impossibility result analogous to FLP for rate limiting?
• What’s the right policy when the rate-limit store (Redis) itself is overloaded — fail open, fail closed, or local fallback? Production systems disagree.
• Can machine learning predict which clients are about to abuse fixed-window’s boundary burst and pre-throttle them? (Anomaly-detection-on-rate-limit research.)

12. See Also

• Token Bucket — sibling rate-limiter algorithm; smoother bursts, configurable
• Leaky Bucket — sibling; produces output at constant rate
• Sliding Window Rate Limiter — the more accurate (and more expensive) successor
• Consistent Hashing — sharding rate-limit counters across nodes
• Bloom Filter — used to pre-filter known-bad clients before rate-check
• Hash Function Design — used in client-id → shard mapping
• Big-O Notation
• SWE Interview Preparation MOC