Why do fixed-window Redis counters fail at window boundaries?

Distributed rate limiting caps how many requests a client can make across every instance of a service, not just the one handling the current request. Teams use API throttling to protect shared dependencies such as databases and downstream APIs, to keep one noisy tenant from starving others, and to enforce plan quotas. Redis is a common place to keep the shared counter because every instance can reach it and its single-key operations are atomic.

The simplest version is a fixed window. Each instance builds a key from the client ID and the current window number, such as rl:client42:<unix_time / 60>. It calls INCR on that key, sets EXPIRE when the returned value is 1, and rejects the request if the count is over the limit. This takes one round trip and one small key per client per window. One known flaw is that if the process dies between INCR and EXPIRE, the key never expires. The Lua scripting section below fixes that with atomic scripts.

The bigger flaw is the window boundary. Suppose the limit is 100 requests per 60 seconds (illustrative numbers). A client sends 100 requests at 00:59.5, and all of them pass. At 01:00.0 a new key starts at zero, so another 100 requests at 01:00.1 also pass. That is 200 requests in about 0.6 seconds, roughly twice the limit, and none of them broke the rule. The counter has no memory of anything before the reset.

This is why the rest of the article compares two alternatives. A token bucket refills capacity continuously instead of resetting it all at once. A sliding window measures the trailing 60 seconds from the current moment, so there is no boundary to exploit.

import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

LIMIT = 100   # requests allowed per window (illustrative)
WINDOW = 60   # window length in seconds

def allow(client_id: str, now: float) -> bool:
    # Every instance computes the same key for the same minute,
    # so they all share one counter in Redis.
    key = f"rl:{client_id}:{int(now // WINDOW)}"
    count = r.incr(key)
    if count == 1:
        # Not atomic with INCR: a crash here leaves a key with no TTL.
        r.expire(key, WINDOW)
    return count <= LIMIT

base = 1_700_000_040          # a timestamp that falls exactly on a window start
late = base + 59.5            # 00:59.5 -> last half-second of window N
early = base + 60.1           # 01:00.1 -> first moments of window N+1

r.delete(f"rl:client42:{int(late // WINDOW)}", f"rl:client42:{int(early // WINDOW)}")

passed_late = sum(allow("client42", late) for _ in range(100))
passed_early = sum(allow("client42", early) for _ in range(100))

print(passed_late, passed_early)

A redis-py fixed-window limiter using INCR and EXPIRE, driven with simulated timestamps to show 100 requests just before and 100 just after a window boundary all being accepted.

Who should use distributed rate limiting in Redis?

Use a Redis-backed limiter when all of the following hold:

  • You run more than one instance of the service. A limit is only meaningful if every instance enforces the same number. With several replicas behind a load balancer, an in-process counter in each replica lets a client multiply its allowance by spreading requests across instances.
  • The limit is per identity, not per process. Per-user fairness, per-API-key plan quotas, and per-tenant caps all need a counter that follows the client regardless of which instance serves it.
  • You need the limit to hold through scaling events. When autoscaling adds or removes instances, a shared counter keeps the aggregate limit stable. Dividing the limit across instances does not.
  • You already operate Redis, or can. The limiter adds a small amount of state and one round trip per guarded request. If Redis is already in your stack with monitoring and failover, the extra operational burden is small.

Typical users are teams running public or partner-facing APIs, multi-tenant SaaS backends that must keep one tenant from starving the rest, and services that front a fragile or metered dependency, such as a database with limited connections or a third-party API with a contractual quota.

It is a poor fit for a single-instance service, where an in-process limiter gives the same result without a network hop, and for latency-critical internal calls where the extra round trip and the dependency on Redis cost more than an exact limit is worth. The section on avoiding central Redis rate limiting covers those cases.

How does distributed rate limiting in Redis work?

Every variant in this article follows the same request path:

  1. Identify the caller. Middleware in each app instance extracts the identity you are limiting on, such as a user ID, API key, client IP, or route, and builds a Redis key from it, for example rl:user:42.
  2. Ask Redis for a decision. The instance sends one command, ideally a Lua script, that reads the key's current state, applies the algorithm (fixed window, token bucket, sliding log, or sliding counter), writes the updated state, and returns whether the request is allowed plus how long to wait if it is not.
  3. Act on the answer. If allowed, the request continues to the handler. If not, the instance returns HTTP 429 with a Retry-After value derived from the limiter's state.
  4. Let state clean itself up. Each write sets a TTL, so keys for clients that stop sending traffic disappear without a cleanup job.

Because the state lives in Redis rather than in any app process, every instance sees the same count for the same key. Because the read-compute-write runs as one atomic script, concurrent instances cannot both act on the same stale count. Because refill and expiry are computed from timestamps at request time, nothing has to run in the background between requests.

The algorithms differ only in what they store under the key and how step 2 computes the decision. The next three sections cover those differences.

How does a token bucket rate limiter work in Redis?

A token bucket has two parameters. Capacity is the maximum number of tokens the bucket can hold. Refill rate is how many tokens are added per second. Each request spends one token. If no whole token is available, the request is rejected.

No background process adds tokens. The limiter refills lazily: on each request it reads the stored state, computes the time elapsed since the last update, and credits elapsed × rate tokens, capped at capacity. Keys that receive no traffic therefore cost nothing between requests, and the limiter needs no timers.

Per-key state fits in a small Redis hash, for example ratelimit:{client_id} with two fields:

  • tokens: the current balance, stored as a float so partial refills are kept
  • ts: the timestamp of the last refill, in milliseconds

Set an expiry of roughly capacity / rate seconds. By then an idle bucket would be full again, so deleting the key gives the same result as keeping it.

To fill in Retry-After on a rejected request, compute how long until the balance reaches one token: (1 − tokens) / rate seconds. Round up, because clients that retry early are rejected again.

The trade-off is intentional. A client that has been idle can spend its full capacity immediately. With a capacity of 100 and a rate of 10/s, 100 requests can arrive in the same millisecond (illustrative). The bucket permits this burst by design. Capacity sets the burst tolerance and rate sets the sustained throughput, so you have to size each one separately against what your downstream service can actually handle.

import math
import redis

r = redis.Redis(host="localhost", port=6379)

TOKEN_BUCKET = r.register_script("""
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])              -- tokens per second
local t = redis.call('TIME')                -- server clock avoids app-host skew
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or capacity   -- a missing key means a full bucket
local ts = tonumber(s[2]) or now
-- Lazy refill: credit elapsed time x rate, capped at capacity
tokens = math.min(capacity, tokens + math.max(0, now - ts) / 1000 * rate)
local allowed, retry_ms = 0, 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
else
  retry_ms = math.ceil((1 - tokens) / rate * 1000)  -- time until one whole token
end
redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', now)
-- After capacity/rate seconds an idle bucket is full again, so expiry is lossless
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000))
return {allowed, retry_ms}
""")

def check(client_id: str, capacity: int = 100, rate: float = 10.0):
    allowed, retry_ms = TOKEN_BUCKET(keys=[f"ratelimit:{client_id}"], args=[capacity, rate])
    if allowed:
        return True, None
    # Round up so a client honoring Retry-After never retries too early
    return False, max(1, math.ceil(retry_ms / 1000))

ok, retry_after = check("client-42")
print("allowed" if ok else f"429, Retry-After: {retry_after}")

A Redis Lua token bucket called from Python stores tokens and ts in a per-client hash, refills lazily from elapsed server time, sets an expiry of capacity/rate, and returns the wait in milliseconds that the caller rounds up into a Retry-After value.

How does a sliding window rate limiter work: sliding log vs sliding counter?

Sliding log

The sliding log stores every accepted request as a member of a Redis sorted set, scored by its timestamp. On each request, ZREMRANGEBYSCORE drops entries older than now - window, ZCARD counts what remains, and if the count is under the limit, ZADD records the new request. Members must be unique, for example a timestamp plus a request ID. Otherwise two requests in the same millisecond collapse into one entry and the limiter undercounts.

The result is exact: the window really slides, and no boundary can be exploited. The cost is memory proportional to the limit, because every admitted request stays in the set for the full window.

Illustrative estimate, not measured: assume roughly 100 bytes per sorted-set entry once member, score, and internal structure overhead are included. A key allowing 10,000 requests/minute holds up to 10,000 entries, or about 1 MB. With 1,000 clients at that limit, that is about 1 GB. Each request also performs O(log N) work on a set of that size.

Sliding window counter

The sliding window counter keeps only two fixed-window counters, current and previous, and estimates the rolling count:

estimate = previous × (overlap fraction) + current

For example, with a 60-second window, 15 seconds into the current window, the previous window overlaps by 45/60, so its count is weighted by 0.75.

This uses constant memory but assumes the previous window's requests were spread evenly across it. If they clustered at the end, the estimate is too low and the limiter over-admits. If they clustered at the start, the estimate is too high and it under-admits.

import time, uuid
import redis

r = redis.Redis(host="localhost", port=6379)

SLIDING_LOG = r.register_script("""
local now, window, limit = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', now - window)  -- drop expired entries
if redis.call('ZCARD', KEYS[1]) < limit then
  redis.call('ZADD', KEYS[1], now, ARGV[4])   -- score = timestamp, member = unique id
  redis.call('PEXPIRE', KEYS[1], window)      -- idle keys clean themselves up
  return 1
end
return 0
""")

def allow_sliding_log(client_id, limit=10_000, window_ms=60_000):
    now_ms = int(time.time() * 1000)
    # Timestamp plus random suffix so same-millisecond requests don't collapse.
    member = f"{now_ms}-{uuid.uuid4().hex}"
    key = f"ratelimit:log:{client_id}"
    return SLIDING_LOG(keys=[key], args=[now_ms, window_ms, limit, member]) == 1

def sliding_counter_estimate(prev_count, curr_count, elapsed_s, window_s=60):
    overlap = (window_s - elapsed_s) / window_s   # 15s in -> 45/60 = 0.75
    return prev_count * overlap + curr_count

print(sliding_counter_estimate(8_000, 3_000, 15))

A sliding log implemented as an atomic Lua script over a sorted set (ZREMRANGEBYSCORE, ZCARD, ZADD), next to the sliding window counter's weighted estimate, which keeps no per-request state.

How do you implement atomic rate limiting with Redis Lua scripts?

If two app instances each run GET on a counter, see 99 against a limit of 100, and then each SET it to 100, both requests are admitted. Neither saw the other's write. Under load this race is routine, so separate read and write calls reliably over-admit.

A Lua script avoids this. Redis runs each script to completion before executing any other command, so the read-compute-write sequence executes as one unit:

 app-1 ─┐
 app-2 ─┼─ EVALSHA limiter(key, rate, burst) ─▶ Redis
 app-3 ─┘      read → compute → write
               ◀── allowed / retry-after

Time source. Call TIME inside the script, or pass in one timestamp from a trusted source. If each app host passes its own clock, a host that is a few hundred milliseconds fast will refill a token bucket early.

Key design. Choose the key based on what you are protecting:

  • rl:user:{id} for fairness between users.
  • rl:key:{apikey} for billing tiers.
  • rl:route:{name} to protect an expensive endpoint.
  • A composite key such as rl:{apikey}:search for per-tenant, per-route limits.

Idle keys. Set a TTL on every write, about as long as the window or the full-refill time. Otherwise every client that ever made a request leaves a key in memory.

Redis Cluster. A script can only access keys in a single hash slot. Wrap the shared part of each key in braces, for example {user:42}, so all keys the script touches hash to the same slot.

Script cost. While a script runs, the instance serves nothing else. Keep the work bounded. For example, trim and cap a sliding log rather than scanning an unbounded sorted set.

import redis

TOKEN_BUCKET = """
local rate  = tonumber(ARGV[1])   -- tokens refilled per second
local burst = tonumber(ARGV[2])   -- bucket capacity
-- Use the Redis server clock so skewed app hosts cannot refill early.
local t   = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or burst
local ts     = tonumber(s[2]) or now
tokens = math.min(burst, tokens + math.max(0, now - ts) * rate)
local allowed, retry_ms = 0, 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
else
  retry_ms = math.ceil((1 - tokens) / rate * 1000)
end
redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', tostring(now))
-- Idle keys expire after a full refill; a missing key means a full bucket.
redis.call('PEXPIRE', KEYS[1], math.ceil(burst / rate * 1000))
return {allowed, retry_ms}
"""

r = redis.Redis(host="redis.internal", port=6379)
limiter = r.register_script(TOKEN_BUCKET)

key = "rl:{apikey:ak_test_123}:search"
allowed, retry_ms = limiter(keys=[key], args=[5, 20])  # 5 req/s, burst of 20
if not allowed:
    print(f"429 Too Many Requests, retry after {retry_ms} ms")

A token-bucket Lua script, invoked from Python, that reads, refills, decrements and writes the bucket atomically using Redis server TIME, sets a TTL on idle keys and uses a hash-tagged composite key.

Token bucket vs sliding window: which should you choose?

Token bucket Sliding log Sliding counter
Traffic shape admitted Average rate r, bursts up to capacity b At most N in any trailing window Roughly N per trailing window
Burst behavior Full bucket drains at once, then paced at r Up to N at once, then blocked until entries age out Like the log, but the edge is approximate
Exactness Exact for its own model Exact Approximate, assumes even spread in the previous window
Memory per key Two fields (tokens, timestamp) One sorted-set entry per admitted request, up to N Two counters
Per-request CPU Constant Logarithmic insert plus trimming expired entries Constant
Retry-After Exact: (cost − tokens) / r Exact: oldest relevant entry's timestamp + window − now Estimated by solving the weighted sum for the limit

The table hides a key difference: what each algorithm promises about a trailing interval. A token bucket can admit up to b + r·W requests in any window of length W, so it gives no hard ceiling over short windows. That suits API throttling for legitimate bursty clients, such as a mobile app syncing on launch or a batch job that idles and then fires. You size b for the burst you want to allow and r for the sustained load you can afford.

Use a sliding log when a downstream needs a hard bound, such as a partner API with a contractual "100 per minute" or a database that falls over past a known concurrency. Pay the memory only where the limit N is small.

Use a sliding counter for high-cardinality keys, such as per-IP or per-tenant limits across many keys. There, a small overshoot is acceptable and per-key memory dominates the cost.

When should you avoid central Redis rate limiting, and what are the alternatives?

A central Redis limiter adds a network round trip to every request it guards. It also makes Redis a hard dependency: if Redis is slow, your API is slow, and if Redis is down, you must choose between failing open and failing closed. For internal service-to-service calls with tight latency budgets, that cost can outweigh the benefit of an exact limit.

Hot keys are the next problem. A global limit or a very large tenant sends every check to a single key, and that key lives on one shard. Redis executes commands on a single thread per instance, so one busy key can saturate a node while the rest of the cluster sits idle. You can split the limit across k sub-keys, each allowing N/k, but traffic rarely spreads evenly. One sub-key rejects requests while others still have capacity, so the effective limit is no longer exact.

Failover can also erase state. Redis replication is asynchronous, so a promoted replica may be missing the most recent counter writes. Clients can briefly get a fresh allowance right after a failover.

Approach Hot-path cost Accuracy Main weakness
Central Redis One round trip per check Close to exact Dependency, hot keys
Local in-process None Approximate Drifts as instance count changes
Hybrid Round trip only for traffic that passes the local check Close to exact More moving parts

A local limiter gives each instance N divided by the instance count. Autoscaling changes that divisor, and uneven load balancing skews it further, so the real aggregate limit drifts. A hybrid design puts a coarse local limit in front of Redis. The local limit cheaply sheds abusive bursts, and Redis keeps the precise shared count for the traffic that gets through.

How should clients be told about limits, and what happens when Redis fails?

Reject with HTTP 429 Too Many Requests and compute Retry-After from the limiter's own state rather than a fixed constant:

  • Token bucket: the deficit divided by the refill rate, (1 − tokens) / rate. This is the time until one token exists.
  • Sliding log: the oldest entry's timestamp plus the window, minus now.
  • Sliding counter: the time until the weighted count drops below the limit.

Round up to whole seconds. Rounding down invites a retry that is guaranteed to fail.

Return the same remaining-quota headers on every response, not only on 429s, so clients can pace themselves before they hit the wall. Many APIs use X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset. Some follow the IETF's RateLimit header work instead. Pick one convention, document its units (seconds vs. epoch), and use it across all services.

Failure policy

Decide what happens when Redis is slow or down before it happens:

  • Fail open when an outage of the limiter should not become an outage of the API. This suits most read traffic.
  • Fail closed where abuse is costlier than downtime, such as login, OTP sending and expensive paid calls.
  • Fall back to a local limiter sized at the global limit divided by the instance count. Enforcement becomes approximate but stays bounded.

Whichever you choose, give the Redis call a timeout that is a small fraction of the request's latency budget, and add a circuit breaker. Without them, a struggling Redis adds its latency to every request instead of triggering the fallback.

How can a shared Redis rate limiter save engineering time?

Most of the time saved comes from solving the hard parts once instead of in every service:

  • One implementation instead of many. Without a shared limiter, each team tends to write its own counter, often a fixed window with a non-atomic INCR/EXPIRE, and each one rediscovers the boundary burst and the missing-TTL bug. A single reviewed Lua script, wrapped in a small library or middleware, lets services import the limiter instead of re-deriving it.
  • No race conditions to debug. Because the script runs atomically in Redis, there is no class of intermittent over-admission bugs that only appear under concurrent load. Those bugs are expensive to reproduce, so ruling them out by design avoids slow investigations.
  • No background infrastructure. Lazy refill and per-key TTLs mean there are no refill workers, cron jobs or cleanup tasks to build, deploy and monitor. The only moving parts are the script and Redis itself.
  • Limits become configuration. Rate, capacity and window are script arguments. Changing a tenant's plan limit or tightening an endpoint during an incident is a config change, not a code change and redeploy of the limiting logic.
  • Deterministic tests. When the algorithm takes time as an input, as in the fixed-window example's simulated timestamps, edge cases such as boundary bursts and refill timing can be tested without sleeping, which keeps test suites fast and reliable.
  • Fewer client-side support problems. Accurate Retry-After values and consistent quota headers let client developers back off correctly on their own, which cuts down on retry storms and on questions about why requests are being rejected.
  • Shared incident vocabulary. A shared header contract means that during incidents, every 429 means the same thing across services, so on-call engineers do not have to work out which service's limiter behaves which way before they can act.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to distributed rate limiting redis, this is where it helps:

Saves time

  • Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
  • One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
  • Changing a shared variable is one edit and one review instead of editing every service's .env by hand.

Saves cost

  • Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
  • Less duplicated configuration to maintain: one shared definition inherited by many services.
  • A wrong or stale value is caught at review time by the services it affects, not by a failed deploy.
  • OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.