M.Talim
Back to projects
4 min read
Volter

A rate limiting library for Python implementing two algorithms — token bucket and sliding window log — each with an in-memory backend and a Redis-backed backend for correctness across multiple processes. Ships with FastAPI middleware for drop-in use.

from volter import TokenBucketLimiter

limiter = TokenBucketLimiter(capacity=10, refill_rate=1)
if limiter.allow("user:123"):
    process_request()
else:
    reject_with_429()

The problem with most rate limiter examples

Most tutorials implement one algorithm, in memory, in a single file, and stop. That’s fine for a demo but doesn’t reflect production: behind a load balancer, across multiple app instances, sharing state that has to stay correct under concurrent access. volter takes each algorithm from “correct in a single process” to “correct across N processes sharing Redis” — including the concurrency bugs that show up at each step and how they were fixed.

Two algorithms, genuine tradeoffs

Token bucket costs O(1) memory (two numbers per key) and tolerates bursty-then-steady traffic — the right fit for most APIs. Sliding window log costs O(requests in window) but gives an exact count over the exact window, no averaging. Neither is strictly better; the memory cost of the sliding window is exactly what buys its precision, and the imprecision of the token bucket is exactly what buys its O(1) footprint.

From single-process to multi-process correctness

The in-memory limiter protects its read-compute-write sequence with a per-key threading.Lock — an outer lock guards only key creation (double-checked locking, so the common path never blocks), and a per-key lock guards the actual logic, so concurrent requests for different keys never contend.

That approach breaks down across processes: there’s no shared memory to hold a lock in, and Redis doesn’t give multi-command atomicity for free — HMGET → compute → HSET is three round trips, and two processes can race on the same stale read. The fix: Redis is single-threaded, so a Lua script run via EVAL executes as one atomic command from the event loop’s perspective. The script becomes the critical section, replacing the Python-level lock with Redis’s own execution guarantee.

The sliding window’s Redis version uses a sorted set (ZSET), evicting expired entries with ZREMRANGEBYSCORE — the direct equivalent of the in-memory version’s queue-popping loop, and cheap for the same structural reason (skip-list eviction stops at the cutoff instead of scanning everything). Getting this right required generating a UUID per request as the ZSET member rather than using the timestamp itself — same-microsecond requests would otherwise silently collide and undercount real traffic.

Other engineering decisions

  • time.monotonic() instead of time.time() for all elapsed-time math, since wall-clock time can jump backward (NTP sync, clock changes) and corrupt refill/eviction logic.
  • A running total (current_sum) for the in-memory sliding window instead of recomputing on every call, making each request amortized O(1) instead of O(n).
  • Redis-backed limiters get free key expiry via EXPIRE, solving a real limitation of the in-memory versions (whose per-key dicts grow forever).
  • FastAPI middleware written against a Protocol, not a concrete class, so it works unmodified with any of the four limiter implementations.
  • Concurrency correctness verified differently per backend: ThreadPoolExecutor for in-memory (shared process memory), real OS processes via multiprocessing for Redis-backed (proving correctness with zero shared state).

Stack

Python · Redis · Lua · FastAPI · pytest · uv

GitHub · PyPI