Implementing Token Bucket Rate Limiting at Scale with Redis and Lua

#programming

Your traffic is uneven: a few spikes turn into tail-latency spikes, billing surprises, and tenant interference when everyone shares a small keyspace. Naive counters and fixed-window approaches either punish legitimate burst traffic or fail to prevent sustained overload when scaled to thousands of tenants; what you need is a deterministic, atomic token-bucket check that runs in single-digit milliseconds at the edge and scales by sharding keys, not logic.

Contents

[Why the token bucket is the right primitive for bursty APIs]
[Why Redis + Lua meets high-throughput demands for edge rate limiting]
[A compact, production-ready Redis Lua token-bucket script (with pipelining patterns)]
[Sharding approaches and multi-tenant throttling that avoid cross-slot failures]
[Testing, metrics, and failure modes that break naive designs]
[Practical Application — production checklist and playbook]

Why the token bucket is the right primitive for bursty APIs

At its core the token bucket gives you two knobs that match real requirements: an average rate (tokens added per second) and a burst capacity (bucket depth). That combination maps directly to the two behaviors you want to control in an API: steady throughput and short burst absorption. The algorithm fills tokens at a fixed rate and removes tokens when requests pass; a request is allowed if enough tokens exist. This behavior is well documented and forms the basis of most production throttling systems.

Why this beats fixed-window counters for most public APIs:

Fixed-window counters create edge-boundary anomalies and poor UX around resets.
Sliding windows are more accurate but heavier in storage/ops.
Token bucket balances memory cost and burst tolerance while giving predictable long-term rate control.

Quick comparison

Algorithm	Burst tolerance	Memory	Accuracy	Typical use
Token bucket	High	Low	Good	Public APIs with bursty clients
Leaky bucket / GCRA	Medium	Low	Very good	Traffic shaping, precise spacing (GCRA)
Fixed window	Low	Very low	Poor near boundaries	Simple protections, low scale

The Generic Cell Rate Algorithm (GCRA) and leaky-bucket variants are useful in corner cases (strict spacing or telecom use), but for most multi-tenant API gating the token bucket is the most pragmatic choice.

Why Redis + Lua meets high-throughput demands for edge rate limiting

Redis + EVAL/Lua gives you three things that matter for rate limiting at scale:

Locality and atomicity: Lua scripts execute on the server and run without interleaving other commands, so a check+update is atomic and fast. That eliminates race conditions that plague client-side multi-command approaches. Redis guarantees the script’s atomic execution in the sense that other clients are blocked while the script runs.
Low RTT with pipelining: Pipelining batches network round trips and dramatically increases operations per second for short operations (you can get order-of-magnitude throughput improvements when you reduce per-request RTTs). Use pipelining when you batch checks for many keys or when bootstrapping many scripts on a connection.
Server time and determinism: Use Redis’s TIME from inside Lua to avoid clock skew between clients and Redis nodes — the server time is the single source of truth for token refills. TIME returns seconds + microseconds and is cheap to call.

Important operational caveats:

Important: Lua scripts run on Redis’s main thread. Long-running scripts will block the server and may trigger BUSY responses or require SCRIPT KILL / other remediation. Keep scripts short and bounded; Redis has lua-time-limit controls and slow-script diagnostics.

The scripting cache and EVALSHA semantics are also operationally important: scripts are cached in-memory and may be evicted on restart or failover, so your client should handle NOSCRIPT properly (preload scripts on warm connections or fall back safely).

A compact, production-ready Redis Lua token-bucket script (with pipelining patterns)

Below is a compact Lua token-bucket implementation designed for per-key token state stored in a single Redis hash. It uses TIME for server-side clocking and returns a tuple indicating allowed/denied, remaining tokens, and suggested retry wait.

-- token_bucket.lua
-- KEYS = bucket key (e.g., "rl:{tenant}:api:analyze")
-- ARGV = capacity (integer)
-- ARGV = refill_per_second (number)
-- ARGV = tokens_requested (integer, default 1)
-- ARGV = key_ttl_ms (integer, optional; default 3600000)

local key = KEYS
local capacity = tonumber(ARGV)
local refill_per_sec = tonumber(ARGV)
local requested = tonumber(ARGV) or 1
local ttl_ms = tonumber(ARGV) or 3600000

local now_parts = redis.call('TIME')           -- { seconds, microseconds }
local now_ms = tonumber(now_parts) * 1000 + math.floor(tonumber(now_parts) / 1000)

local vals = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(vals) or capacity
local ts = tonumber(vals) or now_ms

-- Refill tokens based on elapsed time
if now_ms > ts then
  local delta = now_ms - ts
  tokens = math.min(capacity, tokens + (delta * refill_per_sec) / 1000)
  ts = now_ms
end

local allowed = 0
local wait_ms = 0

if tokens >= requested then
  tokens = tokens - requested
  allowed = 1
else
  wait_ms = math.ceil((requested - tokens) * 1000 / refill_per_sec)
end

redis.call('HSET', key, 'tokens', tokens, 'ts', ts)
redis.call('PEXPIRE', key, ttl_ms)

if allowed == 1 then
  return {1, tokens}
else
  return {0, tokens, wait_ms}
end

Line-by-line notes

Use KEYS for the bucket key so the script is cluster-safe when the key hash slot is correct (see sharding section).
Read both tokens and ts using HMGET to reduce calls.
Refill formula uses millisecond arithmetic to make refill_per_sec easy to reason about.
Script is O(1) and keeps state localized to one hash key.

Pipelining patterns and script loading

Script caching: SCRIPT LOAD once per node or per connection warm-up and call EVALSHA on checks. Redis caches scripts but it is volatile across restarts and failovers; handle NOSCRIPT gracefully by loading then retrying.
EVALSHA + pipeline caveat: EVALSHA inside a pipeline can return NOSCRIPT, and in that context it's hard to conditionally fall back — some client libraries recommend using plain EVAL in pipelines or preloading the script on every connection beforehand.

Example: pre-load + pipeline (Node + ioredis)

// Node.js (ioredis) - preload and pipeline many checks
const Redis = require('ioredis');
const redis = new Redis({ /* cluster or single-node config */ });

const lua = `-- paste token_bucket.lua content here`;
const sha = await redis.script('load', lua);

// Single-request (fast path)
const res = await redis.evalsha(sha, 1, key, capacity, refillPerSec, requested, ttlMs);

// Batch multiple different keys in a pipeline
const pipeline = redis.pipeline();
for (const k of keysToCheck) {
  pipeline.evalsha(sha, 1, k, capacity, refillPerSec, 1, ttlMs);
}
const results = await pipeline.exec(); // array of [err, result] pairs

Example: Go (go-redis) pipeline

// Go (github.com/redis/go-redis/v9)
pl := client.Pipeline()
for _, k := range keys {
    pl.EvalSha(ctx, sha, []string{k}, capacity, refillPerSec, 1, ttlMs)
}
cmds, _ := pl.Exec(ctx)
for _, cmd := range cmds {
    // parse cmd.Val()
}

Instrumentation note: every Eval/EvalSha still executes several server-side operations (HMGET, HSET, PEXPIRE, TIME) but they run in a single atomic script — counted as server internal commands but provide atomicity and reduce network RTT.

Sharding approaches and multi-tenant throttling that avoid cross-slot failures

Design your keys so the script only touches a single Redis key (or keys that hash to the same slot). In Redis Cluster a Lua script must receive all its keys in KEYS and those keys must map to the same hash slot; otherwise Redis returns a CROSSSLOT error. Use hash tags to force placement: rl:{tenant_id}:bucket.

Sharding strategies

Cluster-mode with hash tags (preferable when using Redis Cluster): Keep the per-tenant bucket key hashed on the tenant id: rl:{tenant123}:api:search. This allows your Lua script to touch a single key safely.
Application-level consistent hashing (client-side sharding): Map tenant id -> node via consistent hashing (e.g., ketama) and run the same single-key script on the chosen node. This gives you fine-grained control over distribution and easier rebalancing logic at app level.
Avoid cross-key scripts: If you need to check multiple keys atomically (for composite quotas), design them so that they use the same hash tag or replicate/aggregate counters into single-slot structures.

Global quotas and fairness across shards

If you require a global quota (one counter across all shards), you need a single authoritative key — either hosted on a single Redis node (becomes a hotspot) or coordinated via a dedicated service (leases or a small Raft cluster). For most SaaS use cases, local per-edge enforcement + periodic global reconciliation gives the best cost/latency trade-off.
For fairness between tenants on different shards, implement adaptive weights: maintain a small global sampler (low RPS) that adjusts local refill rates if imbalance is detected.

Multi-tenant key naming pattern (recommendation)

rl:{tenant_id}:{scope}:{route_hash} — always include the tenant in curly braces so cluster hash-slot affinity stays safe and per-tenant scripts run on a single shard.

Testing, metrics, and failure modes that break naive designs

You need a testing and observability playbook that catches the five common failure modes: hot keys, slow scripts, script cache misses, replication lag, and network partitions.

Testing checklist

Unit test the Lua script with redis-cli EVAL on a local Redis instance. Verify behavior for boundary conditions (exactly 0 tokens, full bucket, fractional refills). Examples: redis-cli --eval token_bucket.lua mykey , 100 5 1 3600000.
Integration smoke-tests across failover: restart the primary, trigger replica promotion; ensure script cache reloads on the promoted node (use SCRIPT LOAD on startup hooks).
Load test using redis-benchmark or memtier_benchmark (or an HTTP load tool such as k6 targeting your gateway) while observing p50/p95/p99 latencies and Redis SLOWLOG and LATENCY monitors. Use pipelining in tests to simulate real client behavior and measure pipeline sizes that give the best throughput without increasing tail latency.
Chaos test: simulate script cache flush (SCRIPT FLUSH), noscript conditions, and network partitions to validate client fallback and safe-deny behavior.

Key metrics to export (instrumented at both client and Redis)

Allowed vs blocked counts (per-tenant, per-route)
Token remaining histograms (sampled)
Rejection ratio and time-to-recover (how long before a previously blocked tenant becomes allowed)
Redis metrics: instantaneous_ops_per_sec, used_memory, mem_fragmentation_ratio, keyspace_hits/misses, commandstats and slowlog entries, latency monitors. Use INFO and a Redis exporter for Prometheus.
Script-level timings: count of EVAL/EVALSHA calls and p99 execution time. Watch for sudden rise in script execution times (possible CPU saturation or long scripts).

Failure mode breakdown (what to watch for)

Script cache miss (NOSCRIPT) during pipeline: pipeline execs with EVALSHA can surface NOSCRIPT errors that are hard to recover from in-flight. Preload scripts and handle NOSCRIPT on connection warm-up.
Long-running script blocking: badly written scripts (e.g., loops per-key) will block Redis and produce BUSY replies; configure lua-time-limit and monitor LATENCY/SLOWLOG.
Hot keys / tenant storms: a single heavy tenant can overload a shard. Detect hot keys and dynamically re-shard or apply heavier penalties temporarily.
Clock skew mistakes: relying on client clocks instead of Redis TIME leads to inconsistent refills across nodes; always use server time for the token refill calculation.
Network partition / failover: script cache is volatile — reload scripts after failover and ensure your client library handles NOSCRIPT by loading and retrying.

Practical Application — production checklist and playbook

This is the pragmatic runbook I use when I push Redis + Lua rate limiting to production for a multi-tenant API.

Key design and namespacing
- Use rl:{tenant_id}:{scope}:{resource} as the canonical key. The {tenant_id} in braces is critical for Redis Cluster slot affinity.
- Keep per-bucket state minimal: tokens and ts in a single hash.
Script lifecycle and client behavior
- Embed the Lua script in your gateway service, SCRIPT LOAD the script at connection start, and store the returned SHA.
- On NOSCRIPT errors, do a SCRIPT LOAD then retry the operation (avoid doing this in a hot path; instead load proactively).
- For pipelined batches, preload scripts on each connection; where pipelining may include EVALSHA, ensure the client library supports robust NOSCRIPT handling or use EVAL as fallback.
Connection and client patterns
- Use connection pooling with warm connections that have the script loaded.
- Use pipelining for batched checks (for example: checking quotas for many tenants on startup or admin tools).
- Keep pipeline sizes modest (e.g., 16–64 commands) — tuning depends on RTT and client CPU.
Operational safety
- Set reasonable lua-time-limit (default 5000ms is high; ensure scripts are microsecond/millisecond-bound). Monitor SLOWLOG and LATENCY and alert on any script that exceeds a small threshold (e.g., 20–50ms for per-request scripts).
- Put circuit-breakers and fallback deny modes in your gateway: if Redis is unavailable, prefer safe-deny or local conservative in-memory throttle to prevent backend overload.
Metrics, dashboards, and alerts
- Export: allowed/blocked counters, tokens remaining, rejections per tenant, Redis instantaneous_ops_per_sec, used_memory, slowlog counts. Feed these into Prometheus + Grafana.
- Alert on: sudden spikes in blocked requests, p99 script execution time, replication lag, or rising evicted keys.
Scale and sharding plan
- Start with a small cluster and measure ops/s with realistic load using memtier_benchmark or redis-benchmark. Use those numbers to set shard counts and expected per-shard throughput.
- Plan for re-sharding: ensure you can move tenants or migrate hashing mappings with minimal disruption.
Runbook snippets
- On failover: verify script cache on the new primary, run a script-warmup job that SCRIPT LOAD-s your token-bucket script across nodes.
- On hot-tenant detection: automatically reduce that tenant’s refill rate or move tenant to a dedicated shard.

Sources:
Scripting with Lua (Redis Docs) - Atomic execution semantics, script cache and EVAL/EVALSHA notes, SCRIPT LOAD guidance.

Redis pipelining (Redis Docs) - How pipelining reduces RTT and when to use it.

TIME command (Redis Docs) - Use Redis TIME as server time for refill calculations.

Redis Cluster / Multi-key operations (Redis Docs) - Cross-slot restrictions, hash tags, and multi-key limitations in cluster mode.

Token bucket (Wikipedia) - Algorithm fundamentals and properties.

Redis Best Practices: Basic Rate Limiting - Redis patterns and trade-offs for rate limiting.

Redis benchmark (Redis Docs) - Examples showing throughput benefits from pipelining.

Redis configuration and lua-time-limit notes - Discussion of long-running Lua script limits and lua-time-limit behavior.

Rate Limiting, Cells, and GCRA — Brandur.org - GCRA overview and timing-based algorithms; advice on using store time.

Envoy / Lyft Rate Limit Service (InfoQ) - Real-world production use of Redis-backed rate limiting at scale.

How to collect Redis metrics (Datadog) - Practical Redis metrics to export, instrumentation tips.

How to perform Redis benchmark tests (DigitalOcean) - Practical memtier/redis-benchmark usage examples for capacity planning.

Deploy token buckets behind a gateway where you can control client backoff, measure p99 decision latency, and move tenants between shards; the combination of redis lua rate limiting, lua scripting, and redis pipelining gives you predictable, low-latency enforcement for high throughput rate limiting, provided you respect EVALSHA/pipeline semantics, server-side time, and the sharding constraints described above.