How to Build an Atomic Token-Bucket Rate Limiter in Python & Redis
Implement lazy token replenishment without background timers for single-node and distributed API gateways.
A Token Bucket rate limiter stores two numbers per client: current tokens and last_refill_ts. On each request at timestamp now, it lazily computes replenished tokens (now - last_refill_ts) * refill_rate capped at burst capacity B, and consumes 1 token if tokens >= 1—requiring zero background cron threads.
Interactive Runnable CodeSandbox
Lazy-Refill TokenBucket Rate Limiter
Lazy Token Replenishment Equation
B is maximum burst capacity and r is sustained refill rate in tokens per second.
Step-by-Step Implementation Breakdown
Compute Token Refill Lazily on Request Arrival
Never run background timer threads per user; compute (now - last_ts) * refill_rate on demand in O(1).
Execute Read-Modify-Write Inside a Single Redis Lua Script
In distributed clusters, wrap HMGET + token math + HMSET + EXPIRE inside a single Redis EVAL script to prevent race conditions.
Production Edge Cases & Interview Traps
- Always pass Redis TIME (server clock) into the Lua script rather than application server clocks to avoid NTP clock skew across gateway pods.
Frequently Asked Questions
How does Token Bucket differ from Leaky Bucket?
Token Bucket permits short bursts up to capacity B while bounding average rate r; Leaky Bucket drains requests at a strictly constant output rate, smoothing out all bursts.