Sliding Window Rate Limiting with Redis Lua

When many workers across many machines call the same rate-limited resource, the limit has to be enforced in one shared place, atomically. This guide builds a sliding-window limiter in Redis with a Lua script that any worker — Celery, Sidekiq, BullMQ, or a Go consumer — can call before doing limited work, as part of Rate Limiting & Throttling Jobs in Queue Fundamentals & Architecture.

Problem Statement

A data-enrichment platform calls a geocoding API that enforces 600 requests per minute per API key, measured as a rolling 60-second window. The platform has 40 tenants, each with its own key, and workers in Python and Go. A fixed-window limiter (counter reset each minute) let workers send 600 requests at 12:00:59 and another 600 at 12:01:00, which the API's rolling window saw as 1,200 in two seconds, returning a wave of 429s. You want each tenant's calls to stay within 600 in any 60-second window across all workers and languages, a limiter check under a millisecond, a hint for how long to wait when limited, and memory that stays bounded with 40 tenants.

Prerequisites

  • Redis 6+ reachable from all workers, preferably not the same instance as a cache with eviction enabled.
  • Clients that can load and call Lua scripts (EVALSHA) — every mainstream client can.
  • The exact limit and window from the provider's documentation, and whether it is per key, per IP, or global.
  • A job framework that can defer or re-enqueue a job when the limiter says "wait".

Step 1 — Choose Between a Log and a Counter

There are two common sliding-window implementations:

  • Sliding log: store a timestamp for every request in a sorted set; count entries in the last window. Exact, but memory grows with the limit (600 entries per tenant here — fine; 100,000 per second would not be).
  • Sliding window counter: keep counts for the current and previous fixed windows and estimate the rolling count as current + previous × overlap. Approximate, constant memory per key.
Sliding log  : exact; memory O(limit) per key;  ~600 members x 40 tenants = 24k entries
Window counter: ~1-5% error at window edges; memory O(1) per key; 80 small keys

For API limits in the hundreds or low thousands per window, the log is exact and cheap; use the counter for very high limits where storing every timestamp is wasteful.

Why fixed windows fail at the boundary A fixed-window limiter resets at each minute. Workers send 600 requests in the last second of one minute and 600 in the first second of the next, all allowed, but the provider's rolling window sees 1,200 requests within two seconds and throttles. A sliding window counts requests in the 60 seconds before each new request, so the second burst is rejected. 600 per minute, fixed vs sliding 12:01:00 reset 600 at :59 600 at :00 fixed window: both allowed sliding window: second burst refused The provider enforces a rolling window, so the client must too.

Step 2 — Write the Atomic Check-and-Record Script

The check ("are there fewer than 600 entries in the last 60 s?") and the record ("add this request") must happen atomically, or two workers can both see 599 and both proceed. A Lua script runs atomically in Redis.

-- sliding_log.lua
-- KEYS[1] = limiter key, e.g. rl:geocode:tenant-17
-- ARGV[1] = now in ms, ARGV[2] = window ms, ARGV[3] = limit, ARGV[4] = unique request id
local key, now, window, limit, id = KEYS[1], tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), ARGV[4]

redis.call('ZREMRANGEBYSCORE', key, 0, now - window)          -- drop entries outside the window
local count = redis.call('ZCARD', key)
if count < limit then
  redis.call('ZADD', key, now, id)
  redis.call('PEXPIRE', key, window)                           -- idle keys disappear on their own
  return {1, limit - count - 1, 0}                             -- allowed, remaining, wait_ms
end
local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
local wait = tonumber(oldest[2]) + window - now                -- when the oldest entry expires
return {0, 0, wait}                                            -- denied, remaining, wait_ms

The script returns how long to wait until a slot frees — the time until the oldest entry leaves the window — which lets callers defer precisely instead of polling. PEXPIRE keeps memory bounded: a tenant that stops calling leaves no key behind after one window.

Step 3 — Pass Time from the Caller, Consistently

The script takes now as an argument rather than calling TIME, which keeps it deterministic for replication and lets tests control time. In production, use the Redis server clock for consistency across workers whose clocks may drift: fetch it once per call or use TIME inside the script on Redis 5+ with effects replication (the default in Redis 7).

# limiter.py — Python client
import time, uuid, redis

r = redis.Redis.from_url(REDIS_URL)
SCRIPT = r.register_script(open("sliding_log.lua").read())

def acquire(tenant: str, limit: int = 600, window_ms: int = 60_000) -> tuple[bool, int]:
    now_ms = int(time.time() * 1000)          # or read Redis TIME for cross-host consistency
    allowed, remaining, wait_ms = SCRIPT(
        keys=[f"rl:geocode:{tenant}"],
        args=[now_ms, window_ms, limit, f"{now_ms}-{uuid.uuid4().hex[:8]}"])
    return bool(allowed), int(wait_ms)

The request id makes each sorted-set member unique; two requests in the same millisecond would otherwise collapse into one member and undercount.

Step 4 — Use the Limiter from Jobs Without Burning Retries

When the limiter denies a request, the job should defer itself for wait_ms without counting a failed attempt.

# Celery
@app.task(bind=True, acks_late=True, max_retries=None)
def geocode_address(self, tenant: str, address_id: int):
    ok, wait_ms = acquire(tenant)
    if not ok:
        raise self.retry(countdown=max(wait_ms / 1000, 0.05) + random.uniform(0, 0.5),
                         max_retries=None)          # throttle, not failure
    result = geocoder.lookup(load_address(address_id))
    save_geocode(address_id, result)
// Go worker: same script, same key, same limit
allowed, _, waitMs, err := slidingLog(ctx, rdb, "rl:geocode:"+tenant, 600, 60_000)
if err != nil { return err }
if !allowed {
    return river.JobSnooze(time.Duration(waitMs)*time.Millisecond + jitter())
}

Because the limiter state lives in Redis under one key per tenant, Python and Go workers share the same budget. The small random jitter prevents every deferred job from waking at the exact same millisecond. For framework-native alternatives, see token bucket rate limiting for Celery tasks and configuring the BullMQ rate limiter.

One budget, many workers, two languages Celery workers in Python and River workers in Go both call the sliding_log script with the key for tenant 17. Redis runs each call atomically against one sorted set. Allowed calls proceed to the geocoding API. Denied calls receive a wait time and defer their job by that amount plus jitter, without consuming a failed attempt. Shared limiter across languages Celery workers Go workers Redis Lua script rl:geocode:tenant-17 allowed: call API denied: snooze wait_ms The script is the contract: same key format, same limit, same window, in every language.

Step 5 — Switch to a Sliding Window Counter at High Limits

For limits in the tens of thousands per window, storing every timestamp costs too much. The sliding window counter keeps two fixed-window counters and weights the previous one by how much of it still overlaps the rolling window.

-- sliding_counter.lua: KEYS[1]=prefix, ARGV: now_ms, window_ms, limit
local prefix, now, window, limit = KEYS[1], tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local cur_start = now - (now % window)
local cur_key, prev_key = prefix .. ':' .. cur_start, prefix .. ':' .. (cur_start - window)
local cur = tonumber(redis.call('GET', cur_key) or '0')
local prev = tonumber(redis.call('GET', prev_key) or '0')
local overlap = (window - (now - cur_start)) / window        -- share of previous window still in range
local estimate = cur + prev * overlap
if estimate < limit then
  redis.call('INCR', cur_key)
  redis.call('PEXPIRE', cur_key, window * 2)
  return {1, 0}
end
return {0, math.ceil((estimate - limit + 1) / math.max(prev, 1) * window)}  -- rough wait hint
Two counters approximate the rolling window At 25 percent of the way through the current minute, the rolling 60-second window covers the last 75 percent of the previous minute and the first 25 percent of the current one. The estimate is the current count, 150, plus 75 percent of the previous count of 480, which is 360, for an estimated 510 requests, below the limit of 600. estimate = current + previous x overlap previous minute: 480 current minute: 150 so far rolling 60 s: 75% of previous + current 150 + 480 x 0.75 = 510 < 600: allowed. Two keys per tenant instead of 600 set members.

The estimate assumes requests in the previous window were evenly spread; its error is usually a few percent, and it never allows the full double burst that a fixed window does. Two small keys per tenant replace a sorted set of up to limit entries. Keys for Redis Cluster must share a hash tag ({rl:geocode:tenant-17}) so both windows live on one slot.

Step 6 — Monitor Denials and Wait Times

A limiter should mostly allow; frequent denials mean the queue is pushing harder than the budget, and wait times tell you how far behind jobs are.

ALLOWED = Counter("ratelimit_allowed_total", "", ["resource", "tenant"])
DENIED = Counter("ratelimit_denied_total", "", ["resource", "tenant"])
WAIT = Histogram("ratelimit_wait_seconds", "", ["resource"], buckets=(0.1, 0.5, 1, 5, 15, 60))
# Share of attempts denied per tenant: sustained high values mean backlog exceeds budget
sum by (tenant) (rate(ratelimit_denied_total[5m]))
  / sum by (tenant) (rate(ratelimit_allowed_total[5m]) + rate(ratelimit_denied_total[5m]))

# 429s from the provider should be ~0 when the limiter matches the provider's window
sum(rate(geocoder_responses_total{status="429"}[5m]))

Denials are expected during bursts; 429s from the provider are not, and indicate a mismatch between the limiter and the provider (window type, limit, or other clients sharing the key). Keep tenant labels only if the tenant count is bounded — 40 is fine; thousands belong in logs, not metric labels.

Verification

def test_never_exceeds_limit_in_any_window(redis_client, frozen_clock):
    allowed_at = []
    for i in range(2000):
        frozen_clock.advance_ms(50)                      # 20 attempts per second
        ok, _ = acquire("t-1", limit=600, window_ms=60_000)
        if ok:
            allowed_at.append(frozen_clock.now_ms())
    for t in allowed_at:
        assert sum(1 for s in allowed_at if t - 60_000 < s <= t) <= 600

Then run two worker processes in different languages against a staging Redis and confirm the combined allowed rate for one tenant stays at or below 600 in every rolling minute.

Gotchas & Edge Cases

Clock skew between workers. If now comes from each worker's clock, a worker whose clock runs fast can see entries as expired early. Use the Redis server clock (TIME) as the single source.

Denied requests are not recorded. The script only adds entries for allowed requests, so a flood of denials does not extend the wait. That is the desired behaviour; do not "count" denials.

Script caching. Clients use EVALSHA; after a Redis restart or failover the script cache is empty and clients must reload. Most client libraries handle NOSCRIPT automatically.

Per-tenant fairness. A per-tenant limiter protects the provider, not other tenants' place in the queue. Combine with fair scheduling if one tenant's backlog delays others.

FAQ

Sliding window or token bucket? A token bucket allows controlled bursts up to the bucket size and refills at a steady rate; a sliding window enforces "no more than N in any T". Match the provider: if it documents a rolling window, use a sliding window.

Can I use Redis modules instead? Modules such as redis-cell implement a generic cell rate algorithm natively. They are convenient where you control the Redis build; managed Redis services often do not allow modules, which is why the Lua approach is common.

How do I test without waiting a minute? Pass now as an argument (as the log script does) and control it from tests, or use a short window in tests with the same code.

Related