Skip to content

Sliding-Window Rate Limiting with Redis and asyncio

A local token bucket keeps one process inside an upstream's quota. Deploy twelve replicas and the upstream sees twelve times the intended rate, because each process only knows about its own requests. Dividing the quota by the replica count works until autoscaling changes the count, or until traffic is uneven and eleven idle replicas hold quota the twelfth needs. A shared limiter in Redis fixes both: every worker asks the same counter, so the limit applies to the fleet. The naive implementation — INCR a key, EXPIRE it, compare — allows up to twice the limit across a window boundary and races between the read and the write. This guide builds a sliding-window limiter as one atomic Lua script, waits the exact time the script says to wait, keys it per tenant and route, decides what happens when Redis itself is unavailable, and adds a local pre-check so the common case does not pay a round trip.

Prerequisites

  • Python 3.11+ and redis (pip install redis), whose redis.asyncio client is used here; the algorithm applies to Valkey and other Redis-compatible servers.
  • Local limiting from Rate Limiting & Throttling and token bucket rate limiter for asyncio clients.
  • A Redis instance reachable from every worker, with latency low enough that one round trip per request is acceptable.
Fixed window versus sliding window 2 columns contrasting fixed window (INCR), sliding window (sorted set). Fixed window versus sliding window fixed window (INCR) resets on the boundary one counter per period cheap up to 2x limit at the edge sliding window (sorted set) always the last N seconds one entry per request exact retry time memory per admitted request The sorted set costs memory and buys an invariant that holds at every instant.

1. Make the decision atomic in one script

The limiter keeps one sorted set per key, holding a member per accepted request scored by its timestamp. A single Lua script trims expired entries, counts what remains, and either admits the request or reports exactly how long to wait — all atomically on the server, with no read-modify-write race between workers.

-- sliding_window.lua: KEYS[1]=bucket, ARGV: now_ms, window_ms, limit, member
local key, now_ms      = KEYS[1], tonumber(ARGV[1])
local window_ms, limit = tonumber(ARGV[2]), tonumber(ARGV[3])
local member           = ARGV[4]

redis.call('ZREMRANGEBYSCORE', key, 0, now_ms - window_ms)   -- drop entries older than the window
local used = redis.call('ZCARD', key)
if used < limit then
  redis.call('ZADD', key, now_ms, member)
  redis.call('PEXPIRE', key, window_ms)                       -- the key cleans itself up
  return {1, limit - used - 1, 0}                             -- allowed, remaining, retry_ms
end
local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
return {0, 0, (tonumber(oldest[2]) + window_ms) - now_ms}     -- denied, 0, retry after

A sliding window counts the requests in the last window_ms at every instant, unlike a fixed window that resets on the hour and allows a double burst around the boundary. The PEXPIRE keeps idle tenants from accumulating keys, and returning retry_ms from the server means clients never guess how long to sleep.

Verify: running the script twice past the limit returns 0 with a retry_ms close to the window minus the age of the oldest entry.

2. Call it from asyncio and wait exactly as long as told

register_script uploads the script once and calls it by hash afterwards, falling back automatically if the server has forgotten it. The client loop sleeps for the returned retry_ms rather than polling.

# pip install redis
import asyncio
import time
import uuid

import redis.asyncio as redis

SLIDING_WINDOW = """
local key, now_ms      = KEYS[1], tonumber(ARGV[1])
local window_ms, limit = tonumber(ARGV[2]), tonumber(ARGV[3])
local member           = ARGV[4]
redis.call('ZREMRANGEBYSCORE', key, 0, now_ms - window_ms)
local used = redis.call('ZCARD', key)
if used < limit then
  redis.call('ZADD', key, now_ms, member)
  redis.call('PEXPIRE', key, window_ms)
  return {1, limit - used - 1, 0}
end
local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
return {0, 0, (tonumber(oldest[2]) + window_ms) - now_ms}
"""


class RedisSlidingWindow:
    def __init__(self, client: "redis.Redis", limit: int, window_seconds: float) -> None:
        self.limit = limit
        self.window_ms = int(window_seconds * 1000)
        self._script = client.register_script(SLIDING_WINDOW)

    async def acquire(self, key: str, max_wait: float = 5.0) -> int:
        loop = asyncio.get_running_loop()
        deadline = loop.time() + max_wait
        while True:
            now_ms = int(time.time() * 1000)
            member = f"{now_ms}-{uuid.uuid4().hex[:8]}"          # unique per attempt
            allowed, remaining, retry_ms = await self._script(
                keys=[f"rl:{key}"], args=[now_ms, self.window_ms, self.limit, member])
            if allowed:
                return int(remaining)
            wait = min(retry_ms / 1000 + 0.001, max(0.0, deadline - loop.time()))
            if wait <= 0:
                raise TimeoutError(f"rate limit for {key} not available within {max_wait}s")
            await asyncio.sleep(wait)

Members must be unique: two requests in the same millisecond would otherwise collide in the sorted set and one would not be counted. Use the wall clock (time.time()) rather than loop.time() here, because the value is shared with other processes — and keep the servers' clocks synchronised, since the window is measured with the caller's timestamp.

Verify: with limit=5 over a one-second window, the sixth call sleeps until the oldest entry expires and then succeeds.

3. Test the behaviour without a server

The script's logic is simple enough to reproduce locally, which makes the limiter testable in unit tests and lets you assert the shape of the waiting behaviour deterministically.

import asyncio
import collections
import time
import uuid


class FakeRedisWindow:
    """Reimplements the Lua script's semantics in memory, for tests."""

    def __init__(self) -> None:
        self.sets: dict[str, dict[str, int]] = collections.defaultdict(dict)

    async def run(self, key: str, now_ms: int, window_ms: int, limit: int, member: str):
        entries = self.sets[key]
        for m, score in list(entries.items()):
            if score <= now_ms - window_ms:
                del entries[m]
        used = len(entries)
        if used < limit:
            entries[member] = now_ms
            return [1, limit - used - 1, 0]
        oldest = min(entries.values())
        return [0, 0, int(oldest + window_ms - now_ms)]


class TestableLimiter(RedisSlidingWindow):
    def __init__(self, fake: FakeRedisWindow, limit: int, window_seconds: float) -> None:
        self.limit, self.window_ms, self._fake = limit, int(window_seconds * 1000), fake

    async def _call(self, key, now_ms, member):
        return await self._fake.run(f"rl:{key}", now_ms, self.window_ms, self.limit, member)

    async def acquire(self, key: str, max_wait: float = 5.0) -> int:
        loop = asyncio.get_running_loop()
        deadline = loop.time() + max_wait
        while True:
            now_ms = int(time.time() * 1000)
            member = f"{now_ms}-{uuid.uuid4().hex[:8]}"       # unique, like the real limiter
            allowed, remaining, retry_ms = await self._call(key, now_ms, member)
            if allowed:
                return int(remaining)
            wait = min(retry_ms / 1000 + 0.001, max(0.0, deadline - loop.time()))
            if wait <= 0:
                raise TimeoutError("rate limit wait exceeded")
            await asyncio.sleep(wait)


async def main() -> None:
    limiter = TestableLimiter(FakeRedisWindow(), limit=5, window_seconds=0.5)
    started = time.perf_counter()
    admitted: list[float] = []

    async def call() -> None:
        await limiter.acquire("tenant-1")
        admitted.append(time.perf_counter() - started)

    await asyncio.gather(*(call() for _ in range(12)))
    admitted.sort()
    print("first five at:", [round(t, 2) for t in admitted[:5]])
    print("next five at: ", [round(t, 2) for t in admitted[5:10]])
    print("never more than 5 per window:",
          all(sum(1 for t in admitted if x - 0.5 < t <= x) <= 5 for x in admitted))


asyncio.run(main())

Twelve concurrent calls against a limit of five per half-second were admitted in groups: five immediately, five at 0.5 s, the rest at 1.0 s — and no half-second window ever contained more than five. That is the sliding-window property, and it holds across processes when the same script runs in Redis.

Verify: the groups appear one window apart and the invariant check prints True.

Twelve calls, five per half second 2 lanes over time. Twelve calls, five per half second admitted five now five more two window first window full second window full time → Each denied caller sleeps exactly until the oldest entry leaves the window.

4. Decide what happens when Redis is unavailable

A shared limiter adds a dependency to every request. Decide deliberately whether losing it means failing closed (reject) or failing open (allow, with a local fallback limit), and make the choice per route.

import asyncio
import logging

import redis.asyncio as redis

log = logging.getLogger("ratelimit")


class ResilientLimiter:
    def __init__(self, shared: RedisSlidingWindow, local_limit: int, fail_open: bool) -> None:
        self.shared = shared
        self.fail_open = fail_open
        self._local = asyncio.Semaphore(local_limit)         # a conservative per-process cap
        self.degraded = 0

    async def acquire(self, key: str, max_wait: float = 2.0):
        try:
            async with asyncio.timeout(max_wait + 0.5):
                return await self.shared.acquire(key, max_wait=max_wait)
        except (redis.RedisError, TimeoutError, OSError) as exc:
            self.degraded += 1
            if not self.fail_open:
                log.warning("rate limiter unavailable; rejecting: %r", exc)
                raise
            log.warning("rate limiter unavailable; falling back to local limit: %r", exc)
            await self._local.acquire()                      # bounded, per process
            return -1                                        # unknown remaining quota

Fail open for internal, low-risk traffic where availability matters more than precision; fail closed when exceeding the quota has real consequences — a paid API with overage charges, or an upstream that bans clients. The local fallback must be strict: quota divided by the maximum replica count, not the full quota, so a Redis outage cannot multiply the rate by the fleet size.

Verify: simulating a Redis failure increments degraded and either rejects or admits at the local limit, according to the configured policy.

5. Skip the round trip when the answer is obvious

One Redis call per request costs a round trip on the hot path. A local token bucket sized to this process's share of the quota admits the common case without asking, and the shared limiter is consulted only when the local bucket is empty — the arrangement used by most production limiters.

import asyncio
import time


class TwoTierLimiter:
    """Local bucket first, shared window only when the local share is exhausted."""

    def __init__(self, shared, local_rate: float, local_burst: int) -> None:
        self.shared = shared
        self.rate = local_rate
        self.capacity = local_burst
        self.tokens = float(local_burst)
        self.updated = time.monotonic()
        self.local_hits = 0
        self.shared_calls = 0

    def _refill(self) -> None:
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
        self.updated = now

    async def acquire(self, key: str) -> str:
        self._refill()
        if self.tokens >= 1:
            self.tokens -= 1
            self.local_hits += 1
            return "local"
        self.shared_calls += 1
        await self.shared.acquire(key)                       # a round trip only when needed
        return "shared"


async def main() -> None:
    limiter = TwoTierLimiter(TestableLimiter(FakeRedisWindow(), limit=100, window_seconds=1.0),
                             local_rate=50, local_burst=20)
    decisions = [await limiter.acquire("tenant-1") for _ in range(40)]
    print(f"local: {decisions.count('local')}, shared round trips: {decisions.count('shared')}")


asyncio.run(main())

Twenty requests were admitted from the local burst without touching Redis, and the rest consulted the shared window. Size the local share below the fleet's fair share so the tiers cannot jointly exceed the quota, and treat the local tier as an optimisation, not as the limit of record. For handling the upstream's own rejections, see handling 429 and Retry-After responses in async clients.

Verify: the local count equals the configured burst plus refills during the run, and the shared count is the remainder.

Two tiers, one quota 3 stacked layers from Local bucket to Degraded mode. Two tiers, one quota Local bucket this process's share no round trip absorbs bursts Shared window fleet-wide quota one round trip atomic decision Degraded mode Redis unavailable fail open or closed strict local cap The local tier is an optimisation; the shared window is the limit of record.

Verification

The shared limiter is correct when:

  • The decision is atomic: admission and counting happen in one server-side script, with no read-then-write race between workers.
  • The window truly slides: no interval of window length ever contains more than limit admissions, including across boundaries.
  • Waits come from the server: clients sleep the returned retry_ms instead of polling, and bound the total wait.
  • Degradation is deliberate: a Redis outage produces the configured fail-open or fail-closed behaviour, with a strict local fallback and a counter.
  • The hot path is cheap: a local tier absorbs most requests, and shared calls per second are a measured number.

Pitfalls & edge cases

  • Fixed windows pretending to be sliding. INCR plus EXPIRE allows up to twice the limit around a boundary; the sorted-set approach does not.
  • Non-unique members. Two requests with the same member in one millisecond collapse into one entry, silently raising the effective limit.
  • Clock skew between workers. Timestamps come from the callers; skew widens or narrows the window. Keep NTP healthy, or pass redis.call('TIME') from the server into the script.
  • Unbounded memory per key. Each admitted request costs a sorted-set entry until it expires; a limit of 100,000 per minute means 100,000 entries per key. Use approximate counters for very large limits.
  • Counting after the call. Admitting first and recording later leaks quota when the request fails; record admission atomically, as the script does.

Frequently Asked Questions

How do I rate limit across multiple asyncio workers or processes?

Keep the counter in a shared store such as Redis and make the admission decision there. A Lua script that trims old entries, counts the remainder and adds the new one runs atomically, so workers cannot race. Local per-process limiters cannot enforce a fleet-wide quota because each one sees only its own traffic.

Why use a sorted set instead of INCR for rate limiting?

INCR with an expiring key implements a fixed window, which allows up to twice the limit around the boundary — a full window's worth just before it resets and another just after. A sorted set scored by timestamp implements a true sliding window: the count always covers the last window's worth of time.

What should an async client do when the rate limiter is at its limit?

Sleep for the wait time the limiter returns, rather than polling, and bound the total wait so a caller with a deadline fails fast instead of queueing forever. Returning the remaining quota and the retry delay from the script lets clients back off precisely.

What happens if Redis goes down while it is the rate limiter?

Decide per route. Failing closed rejects requests, which protects a quota whose breach is costly. Failing open admits them under a strict local limit, sized as the fleet's per-process share, which protects availability. Either way, count degraded decisions and alert on them.