Redis + Lua Atomic Rate Limiters

flowchart TB
  gateway["Gateway Got reply"]
  redis["Redis Replied"]
  gateway_b["Gateway B Idle"]
  bucket["Token bucket Debited"]
  gateway -->|EVALSHA| redis
  redis -->|NOSCRIPT| gateway
  gateway -->|EVAL| redis
  redis -->|HMGET| bucket
  redis -->|Debit| bucket
  redis -->|Reply 1| gateway
  redis -->|Admit| gateway
  gateway -->|GET 99| redis
  gateway_b -->|GET 99| redis
  gateway -->|SET 100| redis
  gateway_b -->|SET 100| redis
  gateway -->|Clock skew| bucket
  redis -->|KEYS slot| bucket
  gateway -->|WATCH| redis
  redis -->|Long script| bucket

Overview

A correct in-process token bucket is still wrong across 40 pods: each pod has its own memory. The distributed answer in interviews is Redis + Lua (or Redis Cell / GCRA).

GET then SET from application code is a TOCTOU race and over-admits under concurrency. Production also cares about script latency, key cardinality, and fail-open vs fail-closed.

By the end of this lesson you should be able to:

• Draw the GET/SET race and the EVALSHA path that closes it
• Say why a script blocks every client, and why that means the script stays short
• Put both sliding-window keys in KEYS under one hash tag
• Read the server clock with TIME inside the script, and say why replicas still match
• Choose fail-open vs fail-closed and name retry double-count

Diagrams - step by step

Three small diagrams for Redis + Lua rate limiters. Step numbers in the labels give the animation order.

Diagram 1 - Happy path: EVALSHA token bucket check and debit

The gateway sends only the script hash; Redis runs the whole refill and debit with no other command in between. If the script is not cached yet, Redis replies NOSCRIPT and the client sends the full body once. The reply tells the gateway whether to admit or return 429.

Diagram 2 - Failure path: client-side GET then SET over-admits

Each command is atomic on its own, but the check and the write are two round trips, so another replica can read the same old value in between. That TOCTOU gap over-admits exactly when traffic is highest. Putting the check and the debit in one Lua script closes the gap.

Diagram 3 - Decision: Lua vs MULTI/WATCH vs plain commands

A bare INCR is atomic and fine for a fixed window. WATCH with MULTI/EXEC is optimistic: it aborts and retries on conflict, which degrades on hot keys. A short Lua script is the usual answer for token bucket or sliding window, but it runs on the Redis main thread, so keep it small.

Atomicity

A Lua script runs on the single Redis main thread and blocks the whole server (every key, every client) until it returns, so no other command can interleave mid-script. That is the atomicity you want for check-plus-debit, and it is why scripts stay short: O(1) work per call, no loops over big keys, no JSON parsing of request bodies.

MULTI/EXEC queues commands. It cannot say "if current is under the limit, then increment, else skip" based on a value you just read, unless you WATCH the key and retry when EXEC returns nil. Retries under contention become a storm on a hot key. Prefer a short script for a token bucket or a sliding window.

A bare INCR plus PEXPIRE is already atomic and is enough for a fixed window. Reach for Lua when you need a refill, a weight, or more than one key.

EVALSHA sends a hash. On NOSCRIPT (first call, restart, or SCRIPT FLUSH), the client sends EVAL with the full body once. Redis caches it. Do not ship the body on every request.

Hash tags and KEYS

{user:42}:rl:0 and {user:42}:rl:1 hash to the same Cluster slot because the tag is the text inside the braces. Pass every key the script touches in KEYS. A key name built inside the script is invisible to Cluster routing and fails with a non-local key error (Script attempted to access a non local key in a cluster node).

The sliding-window sample declares both slots up front:

KEYS[1] = {user:42}:rl:0
KEYS[2] = {user:42}:rl:1

The script picks the current and previous slot by bucket parity (bucket % 2). With server time, the client does not know the bucket number, so it cannot build those names itself either. Both keys share the tag {user:42}.

{user:42}:rl       token bucket hash
{user:42}:rl:0     sliding slot 0
{user:42}:rl:1     sliding slot 1

No TTL means unbounded memory. Every write sets PEXPIRE. Idle identities must die. The token bucket uses 60000 ms. The sliding window uses two window lengths.

Hot keys. A celebrity tenant on one slot becomes the limiter's p99. The script already blocks the whole node while it runs. Split with a secondary dimension (route, or a small set of shards plus a global cap), or use local and global tiers. Replicas of one hot slot do not spread that key.

Retries double-count. A gateway timeout, a retry, a second EVAL, two debits. Gate with an idempotency key (SET seen:{id} NX inside the same script) or accept that a 429 retry must not debit again if the first call already did. Pair that with HTTP 429. One key for a tenant's search, login, and webhooks is a fairness problem, not a Lua problem.

Clock

Read redis.call('TIME') inside the script so every gateway uses the server clock. Client wall clocks jump window ids and token refill.

This is safe on Redis 5+ because scripts replicate by effects: replicas receive the resulting writes, not a re-run of TIME. Since Redis 7 that is the only replication mode. A replica's bucket hash matches the primary byte for byte after a TIME-based write.

Sliding window

Weighted estimate inside one script: previous window times the fraction of the window still overlapping, plus the current count. Deny when that weight is at the limit. register_script sends EVALSHA and falls back to EVAL on NOSCRIPT.

Run python3 redis_sliding.py with redis installed and a Redis 5+ server (REDIS_URL, default redis://localhost:6379/0). This calls the network, so it stays a code sample rather than an in-page playground.

"""Sliding-window counter in one Lua script: server clock, Cluster-safe keys.

Run: python3 redis_sliding.py  (pip install redis; needs a Redis 5+ server on REDIS_URL,
default redis://localhost:6379/0, e.g. docker run -p 6379:6379 redis:7)
"""
from __future__ import annotations

import os
import time

import redis

# KEYS[1], KEYS[2] = the two window slots, e.g. {user:42}:rl:0 and {user:42}:rl:1
# ARGV[1] = window_ms, ARGV[2] = limit
# Every key the script touches is declared in KEYS, and both share the hash tag {user:42},
# so Redis Cluster maps them to one slot. Building key names inside the script would break
# Cluster routing (and the client does not even know the bucket number, because the
# script reads the server clock).
SLIDING_LUA = """
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local t = redis.call('TIME')                       -- server clock: {seconds, microseconds}
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local bucket = math.floor(now / window)
local curr_key = KEYS[1 + bucket % 2]              -- even buckets use slot 0, odd use slot 1
local prev_key = KEYS[1 + (bucket + 1) % 2]
local function count(key, b)                       -- a slot only counts if it holds bucket b
  local v = redis.call('HMGET', key, 'b', 'n')
  if tonumber(v[1]) == b then return tonumber(v[2]) end
  return 0
end
local curr = count(curr_key, bucket)
local prev = count(prev_key, bucket - 1)
local elapsed = now % window
local weight = prev * ((window - elapsed) / window) + curr
if weight >= limit then
  return {0, 0, window - elapsed}                  -- denied, retry after ms
end
if curr == 0 then
  redis.call('HSET', curr_key, 'b', bucket, 'n', 1) -- claim the slot for this bucket
else
  redis.call('HINCRBY', curr_key, 'n', 1)
end
redis.call('PEXPIRE', curr_key, window * 2)        -- TTL so idle users cost no memory
return {1, math.floor(limit - weight - 1), window - elapsed}
"""


class SlidingLimiter:
    def __init__(self, r: redis.Redis, window_ms: int, limit: int) -> None:
        self.script = r.register_script(SLIDING_LUA)  # EVALSHA, falls back to EVAL on NOSCRIPT
        self.window_ms, self.limit = window_ms, limit

    def allow(self, user: str) -> tuple[bool, int, int]:
        tag = "{user:" + user + "}"                    # hash tag = same Cluster slot
        keys = [f"{tag}:rl:0", f"{tag}:rl:1"]
        ok, remaining, retry_ms = self.script(keys=keys, args=[self.window_ms, self.limit])
        return bool(ok), int(remaining), int(retry_ms)


if __name__ == "__main__":
    r = redis.Redis.from_url(os.environ.get("REDIS_URL", "redis://localhost:6379/0"))
    r.delete("{user:42}:rl:0", "{user:42}:rl:1")
    lim = SlidingLimiter(r, window_ms=1000, limit=5)
    results = [lim.allow("42")[0] for _ in range(8)]
    print("burst of 8, limit 5 per 1s:", results)
    time.sleep(1.2)                                    # previous window now only partly counts
    print("after 1.2s:", lim.allow("42"))

Sample run on Redis 8.0: a burst of 8 with limit 5 per second returned five allows, then three denies. After 1.2 seconds the next call was allowed, because the previous window only partly counts. The same script on a local 3-node Redis Cluster allowed 5, then denied. The older pattern that built key names inside the script failed there with "attempted to access a non local key".

Token bucket

Store tokens and ts in one hash. Refill with server time, debit cost when the balance covers it, HMSET on both paths, and PEXPIRE 60000. The client computes the same SHA-1 Redis uses, calls EVALSHA, and on NOSCRIPT calls EVAL.

Run npm i ioredis && npx tsx redis_token_bucket.ts against Redis 5+. The key is {user:42}:rl, matching Diagram 1.

// Token bucket in one Lua script via ioredis: EVALSHA first, EVAL once on NOSCRIPT.
// Run: npm i ioredis && npx tsx redis_token_bucket.ts  (Redis 5+ on REDIS_URL or localhost:6379)
import { createHash } from "node:crypto";
import Redis from "ioredis";

// KEYS[1] = bucket hash, e.g. {user:42}:rl   ARGV[1] = refill per second, ARGV[2] = capacity, ARGV[3] = cost
// The clock comes from redis.call('TIME') so all gateways share one clock. This is safe on
// Redis 5+ because scripts replicate by effects (the HMSET result), not by re-running TIME.
export const TOKEN_LUA = `
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local cap = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local data = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1]) or cap
local ts = tonumber(data[2]) or now
tokens = math.min(cap, tokens + (math.max(0, now - ts) / 1000.0) * rate)
local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end
redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', key, 60000)
return {allowed, math.floor(tokens)}
`;
const TOKEN_SHA = createHash("sha1").update(TOKEN_LUA).digest("hex");  // same hash Redis uses

export class TokenBucket {
  constructor(private redis: Redis, private rate: number, private cap: number) {}

  async take(user: string, cost = 1): Promise<{ allowed: boolean; left: number }> {
    const key = `{user:${user}}:rl`;                 // hash tag keeps related keys on one slot
    const args = [this.rate, this.cap, cost];
    let res: [number, number];
    try {
      res = (await this.redis.evalsha(TOKEN_SHA, 1, key, ...args)) as [number, number];  // step 1
    } catch (e) {
      if (!String(e).includes("NOSCRIPT")) throw e;  // step 2: script cache miss only
      res = (await this.redis.eval(TOKEN_LUA, 1, key, ...args)) as [number, number];     // step 3
    }
    return { allowed: res[0] === 1, left: res[1] };
  }
}

async function main(): Promise<void> {
  const redis = new Redis(process.env.REDIS_URL ?? "redis://localhost:6379");
  await redis.script("FLUSH");                      // force the NOSCRIPT fallback once
  await redis.del("{user:42}:rl");
  const tb = new TokenBucket(redis, 2, 5);          // 2 tokens per second, burst of 5
  const burst = await Promise.all(Array.from({ length: 8 }, () => tb.take("42")));
  console.log("burst of 8, capacity 5:", burst.map((r) => (r.allowed ? "ok" : "429")).join(" "));
  await new Promise((r) => setTimeout(r, 1100));    // about 2 tokens refill
  console.log("after 1.1s:", (await tb.take("42")).allowed, (await tb.take("42")).allowed, (await tb.take("42")).allowed);
  await redis.quit();
}
main();

Sample run on Redis 8.0: a burst of 8 with capacity 5 returned ok five times, then 429 three times. After 1.1 seconds (about 2 tokens refilled at 2 per second) the next three calls were allow, allow, deny. SCRIPT FLUSH forced the NOSCRIPT path once. MONITOR showed EVALSHA followed by EVAL.

Redis down

Document the choice. Login and payments often fail closed, or fail to a tight local cap. Read-mostly GETs may fail open with an alert. Where the limiter sits is gateway layering.

Alternatives: Redis Cell (CL.THROTTLE, GCRA), an Envoy global rate limit service, DynamoDB atomic counters. Interviews still want the Lua.

Interview Q&A

Pitfalls

Go Deeper

• Redis rate limiting howto
• Redis EVAL
• Redis Cluster hash tags
• Stripe: Scaling your API with rate limiters
• Redis Lua rate limiting (YouTube search)

Cluster: algorithms · next gateways · hub