Redis Sliding-Window Rate Limits for Spatial Endpoints

← Back to Rate Limiting Geofence & Tile Endpoints

Enforce an exact, burst-smooth per-API-key request limit on FastAPI tile and geofence routes using a Redis sorted set trimmed and counted inside one atomic Lua script.

# Context & when to use

A fixed-window counter — increment a key, reset it every second — is trivial but wrong at the boundary: a client can fire the full limit in the last 10 ms of one window and again in the first 10 ms of the next, sending 2× the intended rate in a 20 ms burst. For a cheap route nobody notices. For a geofence route where each request can hold a pooled connection for seconds, that doubled burst is exactly the overload the limit was meant to prevent.

A sliding-window log fixes this by remembering the timestamp of every request in a rolling window rather than a single bucket count. At each request it discards timestamps older than the window and counts what remains; the limit is enforced against a window that slides continuously with the clock, so there is no boundary to exploit. Reach for this when you need exact, fair per-client limits on expensive spatial routes and your per-window limit is modest (up to a few thousand). When requests differ enormously in cost, layer cost-based throttling on top so a large-radius ST_DWithin counts for more than a point lookup. The algorithm trade-offs against fixed-window and token-bucket are laid out in the parent rate limiting geofence and tile endpoints guide.

The single hard requirement is atomicity. Trim, count, and conditionally add must happen with no other client interleaving, or two concurrent requests both read “9 used” and both get admitted. Redis runs a Lua script to completion without interleaving other commands, which is what makes the check-decide-write a single indivisible step.

# How the window slides

# Runnable implementation

The Lua script is the whole limiter; the Python around it just loads it once and calls it by SHA. Every operation runs server-side inside Redis, so the trim-count-add sequence is atomic with respect to every other client.

# app/sliding_window.py
import time
from dataclasses import dataclass
from redis.asyncio import Redis

# Atomic sliding-window log.
#   KEYS[1] = the per-client sorted set
#   ARGV[1] = now in milliseconds
#   ARGV[2] = window width in milliseconds
#   ARGV[3] = max requests allowed in the window
#   ARGV[4] = a unique member id (so two requests at the same ms don't collide)
# Returns {allowed(1|0), remaining_or_retry_ms}
SLIDING_WINDOW_LUA = """
local key    = KEYS[1]
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])
local member = ARGV[4]

-- 1. Drop every timestamp that has slid out of the window.
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

-- 2. How many requests remain inside the window?
local used = redis.call('ZCARD', key)

if used < limit then
    -- 3a. Admit: record this request and refresh the key's TTL.
    redis.call('ZADD', key, now, member)
    redis.call('PEXPIRE', key, window)
    return {1, limit - used - 1}
end

-- 3b. Reject: Retry-After is when the oldest in-window entry falls out.
local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
local retry_ms = window - (now - tonumber(oldest[2]))
return {0, retry_ms}
"""


@dataclass
class Decision:
    allowed: bool
    remaining: int       # requests left in window (when allowed)
    retry_after: int     # seconds until retry (when rejected)


class SlidingWindowLimiter:
    def __init__(self, redis: Redis, window_seconds: int, limit: int, prefix: str = "rl"):
        self.redis = redis
        self.window_ms = window_seconds * 1000
        self.limit = limit
        self.prefix = prefix
        self._sha: str | None = None

    async def _load(self) -> str:
        if self._sha is None:
            self._sha = await self.redis.script_load(SLIDING_WINDOW_LUA)
        return self._sha

    async def check(self, identity: str) -> Decision:
        key = f"{self.prefix}:{identity}"
        now_ms = int(time.time() * 1000)
        # A monotonic-ish unique member: ms plus a counter avoids collisions
        # when the same client fires several requests within one millisecond.
        member = f"{now_ms}:{time.perf_counter_ns()}"
        sha = await self._load()
        try:
            allowed, meta = await self.redis.evalsha(
                sha, 1, key, now_ms, self.window_ms, self.limit, member,
            )
        except Exception as exc:
            # NOSCRIPT after a Redis restart flushes the cache: reload once.
            if "NOSCRIPT" in str(exc):
                self._sha = None
                sha = await self._load()
                allowed, meta = await self.redis.evalsha(
                    sha, 1, key, now_ms, self.window_ms, self.limit, member,
                )
            else:
                raise
        if allowed == 1:
            return Decision(allowed=True, remaining=int(meta), retry_after=0)
        return Decision(allowed=False, remaining=0, retry_after=max(1, round(int(meta) / 1000)))

Apply it as a FastAPI dependency scoped to the expensive routes, keyed on the API key extracted from the request (the same identity your JWT spatial scopes establish):

# app/deps.py
from fastapi import Depends, Request, HTTPException
from app.sliding_window import SlidingWindowLimiter

def get_limiter(request: Request) -> SlidingWindowLimiter:
    # 10 requests per 1 s per key — a geofence-route budget.
    return SlidingWindowLimiter(request.app.state.redis, window_seconds=1, limit=10)

async def enforce_geofence_limit(
    request: Request,
    limiter: SlidingWindowLimiter = Depends(get_limiter),
):
    api_key = request.headers.get("x-api-key") or request.client.host
    decision = await limiter.check(f"geofence:{api_key}")
    if not decision.allowed:
        raise HTTPException(
            status_code=429,
            detail="Rate limit exceeded.",
            headers={
                "Retry-After": str(decision.retry_after),
                "RateLimit-Limit": "10",
                "RateLimit-Remaining": "0",
                "RateLimit-Reset": str(decision.retry_after),
            },
        )

# Usage on a route:
# @router.get("/within", dependencies=[Depends(enforce_geofence_limit)])

# Key parameters & options

# Gotchas & failure modes

• Non-unique members silently undercount. If two requests in the same millisecond use the same member string, the second ZADD updates the first instead of adding a row, so ZCARD reports one request where there were two — the client gets free capacity. Always append a high-resolution counter (perf_counter_ns) to the timestamp, as above.

• NOSCRIPT: No matching script after a Redis restart or failover. Redis flushes its script cache on restart, so a cached SHA stops resolving and EVALSHA raises NOSCRIPT. Catch it, SCRIPT LOAD again, and retry once — the handler above does this. A limiter that crashes on failover fails the whole route.

• Clock skew across API replicas. The score is time.time() on the application host, not Redis. If replicas’ clocks drift by more than a few tens of milliseconds, windows shift per replica and the limit becomes fuzzy. Run NTP on every node, or read the reference time from Redis with TIME inside the script if you need strict correctness.

• Unbounded memory at high limits. The log stores one member per request in the window; a limit of 100,000 makes each key ~2–4 MB. For very high limits switch to a two-counter sliding-window approximation, which is O(1) per key at the cost of small edge inaccuracy.

• Forgetting PEXPIRE. If you ZADD but never set a TTL, a client that sends one request and vanishes leaves a sorted set in Redis forever. Over millions of one-shot keys this leaks memory until eviction kicks in. Refresh PEXPIRE on every admit so active keys stay alive and idle ones expire.

# Verification

Drive the limiter past its ceiling and confirm the exact admit/reject split, then confirm the key self-expires:

# 12 requests at a 10-per-second limit → 10x200 then 2x429
for i in $(seq 1 12); do
  curl -s -o /dev/null -w "%{http_code} " \
    -H "x-api-key: demo" "http://localhost:8000/within?lng=13.4&lat=52.5&radius=500"
done; echo

# Inspect the sorted set directly (should hold <= limit members, all in-window)
redis-cli ZCARD "rl:geofence:key:demo"        # -> (integer) 10
redis-cli PTTL  "rl:geofence:key:demo"         # -> a value <= 1000 (ms), proving PEXPIRE ran

A quick atomicity assertion in Python — fire the limit concurrently and confirm no over-admission:

import asyncio
async def test_no_overadmit(limiter):
    results = await asyncio.gather(*[limiter.check("race") for _ in range(50)])
    assert sum(r.allowed for r in results) == limiter.limit   # exactly the limit, never more

# Related

• Rate Limiting Geofence & Tile Endpoints — algorithm decision matrix, keying strategies, and the full middleware
• Cost-Based Throttling for Expensive PostGIS Queries — weight the window by query cost, not a flat count
• Redis Caching for Spatial Queries — reuse the same Redis to cache tile responses so the limiter only guards misses

← Back to Rate Limiting Geofence & Tile Endpoints