Design a token-bucket rate limiter
Design a token-bucket limiter class with lazy refill, an injected clock, bounded memory and a typed decision with Retry-After, then make it work across many servers with an atomic Redis script, and choose keys and failure behaviour that hold up against a real attacker.
01Understand the problem
- Implement a token bucket with lazy refill instead of a timer per key
- Make it deterministic and testable with an injected clock
- Keep memory bounded under a flood of unique keys
- Run it atomically across servers with a Redis Lua script and decide whether to fail open or closed
What they probe: the refill maths, why lazy refill beats a background timer, what the key is (IP, user, IPv6 prefix, route), what happens when the clock jumps, how many keys fit in memory, and the race between two servers. Where candidates slip: a fixed window that allows double the rate at the boundary, a Map that grows forever, GET then SET in Redis, keying only by IP for login, no Retry-After.
A token bucket holds up to capacity tokens and gains rate tokens per second. Each request spends one (or a weighted cost); if the bucket is empty the request is refused. Capacity sets the burst you tolerate, rate sets the sustained throughput. Instead of a timer adding tokens, compute them lazily on each request from the time elapsed since the last one.
take(key, cost)returns allowed or refused, tokens remaining and, when refused, how long until enough tokens exist.- Refill is continuous:
tokens = min(capacity, tokens + elapsed * rate). - A clock that goes backwards never creates tokens.
- Memory is capped at
maxKeysbuckets. - The distributed version gives the same answer as the local one, atomically.
| Algorithm | Burst behaviour | State per key | Weakness |
|---|---|---|---|
| Fixed window counter | Up to 2x the limit across a window boundary | 1 counter | Boundary burst |
| Sliding window log | Exact | One timestamp per request | Memory grows with the limit |
| Sliding window counter | Close to exact | 2 counters | Approximation |
| Token bucket | Up to capacity, then smooth | Tokens and a timestamp | Burst size must be chosen deliberately |
02Interfaces first
export interface BucketConfig {
capacity: number; // maximum burst, in tokens
refillPerSec: number; // sustained rate
maxKeys: number; // memory bound for the in-process limiter
}
export interface Decision {
allowed: boolean;
remaining: number; // whole tokens left after this request
retryAfterMs: number; // 0 when allowed
}
export interface RateLimiter {
take(key: string, cost?: number): Promise<Decision>;
}| Endpoint | Key | Capacity / rate | Why |
|---|---|---|---|
| POST /login | account id and, separately, client IP | 5 burst, 1 per minute | Stops guessing one account and spraying many |
| POST /password-reset | email and IP | 3 burst, 1 per 10 minutes | Stops email bombing |
| Public API | API key | 100 burst, 10 per second | Fair share per customer |
| Anonymous IPv6 traffic | /64 prefix, not the full address | per policy | One host can own 2^64 addresses |
03In-process bucket and the Redis script
interface Bucket { tokens: number; lastMs: number }
export class TokenBucketLimiter implements RateLimiter {
private readonly buckets = new Map<string, Bucket>(); // insertion order doubles as LRU order
constructor(private readonly cfg: BucketConfig, private readonly now: () => number = Date.now) {
if (!(cfg.capacity >= 1) || !(cfg.refillPerSec > 0) || !Number.isInteger(cfg.maxKeys) || cfg.maxKeys < 1) {
throw new RangeError("invalid limiter config");
}
}
async take(key: string, cost = 1): Promise<Decision> {
if (!(cost > 0) || cost > this.cfg.capacity) throw new RangeError("cost must be in (0, capacity]");
const now = this.now();
let b = this.buckets.get(key);
if (b) this.buckets.delete(key); // re-inserted below, so it becomes most recent
else b = { tokens: this.cfg.capacity, lastMs: now };
const elapsed = Math.max(0, now - b.lastMs); // a backwards clock adds nothing
b.tokens = Math.min(this.cfg.capacity, b.tokens + (elapsed * this.cfg.refillPerSec) / 1000);
b.lastMs = Math.max(b.lastMs, now);
let d: Decision;
if (b.tokens >= cost) {
b.tokens -= cost;
d = { allowed: true, remaining: Math.floor(b.tokens), retryAfterMs: 0 };
} else {
d = { allowed: false, remaining: 0, retryAfterMs: Math.ceil(((cost - b.tokens) * 1000) / this.cfg.refillPerSec) };
}
this.buckets.set(key, b);
if (this.buckets.size > this.cfg.maxKeys) {
const oldest = this.buckets.keys().next().value;
if (oldest !== undefined) this.buckets.delete(oldest); // evicting resets that key: size maxKeys generously
}
return d;
}
}Across several servers an in-process map lets an attacker multiply their budget by the number of replicas. Moving state to Redis is only correct if read, refill, spend and write happen atomically; a Lua script runs as one unit on the Redis server. Using the server's own TIME avoids clock skew between application hosts.
-- KEYS[1] = bucket key; ARGV = capacity, refill per second, cost
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t = redis.call('TIME') -- { seconds, microseconds }
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or capacity
local ts = tonumber(s[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate / 1000)
local allowed, retry = 0, 0
if tokens >= cost then
tokens = tokens - cost
allowed = 1
else
retry = math.ceil((cost - tokens) * 1000 / rate)
end
redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', tostring(math.max(ts, now)))
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity * 1000 / rate) + 1000) -- a full bucket needs no state
return { allowed, math.floor(tokens), retry }import type { Redis } from "ioredis";
export class RedisTokenBucket implements RateLimiter {
constructor(private readonly redis: Redis, private readonly script: string, private readonly cfg: Omit<BucketConfig, "maxKeys">,
private readonly onError: "open" | "closed") {}
async take(key: string, cost = 1): Promise<Decision> {
try {
const [allowed, remaining, retry] = (await this.redis.eval(this.script, 1, "rl:" + key,
this.cfg.capacity, this.cfg.refillPerSec, cost)) as [number, number, number];
return { allowed: allowed === 1, remaining, retryAfterMs: retry };
} catch {
// Login and password reset fail closed; a read-only public API may prefer to fail open. Choose per route.
return this.onError === "open" ? { allowed: true, remaining: 0, retryAfterMs: 0 } : { allowed: false, remaining: 0, retryAfterMs: 1000 };
}
}
}04Edge cases and tests
| Edge case | Risk | Handling |
|---|---|---|
| Flood of unique keys | Unbounded map, out of memory | maxKeys with LRU eviction; a global bucket in front |
| Eviction of an attacker's key | Their bucket resets to full | Size maxKeys for peak, or evict only buckets that are already full |
| Clock steps backwards (NTP) | Negative elapsed would remove or mint tokens | Clamp elapsed at zero and never move lastMs back |
| IPv6 | A host rotates through a /64 | Key anonymous traffic by /64 |
| Shared IPs (offices, mobile carriers) | One abuser locks out thousands | Key by account where possible; layer IP limits loosely |
| Login keyed only by IP | Botnet sprays one password across accounts | Limit per account as well as per IP, plus global failure alerts |
Return 429 with a Retry-After header in seconds (Math.ceil(retryAfterMs / 1000)). Well-behaved clients back off; for abusive ones, the header costs nothing. Optional RateLimit headers from the IETF draft expose remaining quota.
import { describe, it, expect } from "vitest";
describe("TokenBucketLimiter", () => {
const setup = (maxKeys = 100) => {
let t = 1_000_000;
const clock = { now: () => t, advance: (ms: number) => { t += ms; } };
return { clock, rl: new TokenBucketLimiter({ capacity: 5, refillPerSec: 1, maxKeys }, clock.now) };
};
it("allows a burst up to capacity, then tells the caller when to retry", async () => {
const { rl } = setup();
for (let i = 0; i < 5; i++) expect((await rl.take("k")).allowed).toBe(true);
expect(await rl.take("k")).toEqual({ allowed: false, remaining: 0, retryAfterMs: 1000 });
});
it("refills continuously", async () => {
const { rl, clock } = setup();
for (let i = 0; i < 5; i++) await rl.take("k");
clock.advance(1500);
expect((await rl.take("k")).allowed).toBe(true); // 1.5 tokens -> 0.5 left
expect((await rl.take("k")).allowed).toBe(false);
});
it("does not mint tokens when the clock goes backwards", async () => {
const { rl, clock } = setup();
for (let i = 0; i < 5; i++) await rl.take("k");
clock.advance(-60_000);
expect((await rl.take("k")).allowed).toBe(false);
});
it("keeps memory bounded", async () => {
const { rl } = setup(2);
await rl.take("a"); await rl.take("b"); await rl.take("c");
expect((rl as unknown as { buckets: Map<string, unknown> }).buckets.size).toBe(2);
});
});05Extensions, follow-ups, how to say it
- Weighted costs: expensive endpoints (search, export) spend more tokens from the same bucket.
- Layering: a per-key limiter behind a global one protects the store itself during a flood.
- Local plus global: a small in-process bucket in front of Redis absorbs obvious floods without a network round trip.
- Script caching: load the Lua once with SCRIPT LOAD and call EVALSHA, falling back to EVAL on NOSCRIPT.
Q1Why not GET the bucket, compute in the app, then SET it?+
Two servers can read the same state, both spend the last token, and both write back. The Lua script runs atomically on Redis, so read, refill, spend and write are one step.
Q2Fail open or fail closed when Redis is down?+
Per route. Login and password reset fail closed, because an outage would otherwise remove brute-force protection. A low-risk read API can fail open with an in-process fallback limiter.
Q3How do you choose capacity and rate for login?+
From the guessing maths: allow a few typos as burst and roughly one attempt a minute sustained, then check how many guesses that permits per month against your password policy, and alert on lockout patterns.
"Each key has a bucket of tokens and a timestamp. On each call I refill lazily, tokens plus elapsed times rate, capped at capacity, with elapsed clamped at zero so clock steps cannot mint tokens, then spend the cost or return a refusal with the exact time until enough tokens exist, which becomes Retry-After. In process the map is an LRU capped at maxKeys. Across servers the same logic runs as a Lua script in Redis using Redis TIME, so it is atomic and skew-free. Login is keyed per account and per IP, IPv6 by /64, and fails closed if Redis is down."
Two app servers share a Redis-backed limiter. Each does `GET bucket`, computes the new token count, then `SET bucket`. With one token left, two requests arrive at once. What happens?