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.

● MediumFREEBy ·Design problem·16 min read·Beginner → Intermediate
rate limitingtoken bucketRedisLuaRetry-Afterbrute-force protection

01Understand the problem

✓What you will learn
  • 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
◎Interview radar

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.

  1. take(key, cost) returns allowed or refused, tokens remaining and, when refused, how long until enough tokens exist.
  2. Refill is continuous: tokens = min(capacity, tokens + elapsed * rate).
  3. A clock that goes backwards never creates tokens.
  4. Memory is capped at maxKeys buckets.
  5. The distributed version gives the same answer as the local one, atomically.
AlgorithmBurst behaviourState per keyWeakness
Fixed window counterUp to 2x the limit across a window boundary1 counterBoundary burst
Sliding window logExactOne timestamp per requestMemory grows with the limit
Sliding window counterClose to exact2 countersApproximation
Token bucketUp to capacity, then smoothTokens and a timestampBurst size must be chosen deliberately

02Interfaces first

The contractts
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>;
}
EndpointKeyCapacity / rateWhy
POST /loginaccount id and, separately, client IP5 burst, 1 per minuteStops guessing one account and spraying many
POST /password-resetemail and IP3 burst, 1 per 10 minutesStops email bombing
Public APIAPI key100 burst, 10 per secondFair share per customer
Anonymous IPv6 traffic/64 prefix, not the full addressper policyOne host can own 2^64 addresses

03In-process bucket and the Redis script

TokenBucketLimiterts
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.

token_bucket.lualua
-- 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 }
Redis-backed limiterts
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 };
    }
  }
}
▭On the whiteboard · Design choices4 points
01
refill
lazy and continuous on each call; no timers, no background job
02
clock
injected locally; Redis TIME in the distributed version; never move backwards
03
memory
LRU map capped at maxKeys; Redis keys expire once the bucket would be full
04
failure
chosen per route: closed for login and reset, open only where abuse is cheap

04Edge cases and tests

Edge caseRiskHandling
Flood of unique keysUnbounded map, out of memorymaxKeys with LRU eviction; a global bucket in front
Eviction of an attacker's keyTheir bucket resets to fullSize maxKeys for peak, or evict only buckets that are already full
Clock steps backwards (NTP)Negative elapsed would remove or mint tokensClamp elapsed at zero and never move lastMs back
IPv6A host rotates through a /64Key anonymous traffic by /64
Shared IPs (offices, mobile carriers)One abuser locks out thousandsKey by account where possible; layer IP limits loosely
Login keyed only by IPBotnet sprays one password across accountsLimit per account as well as per IP, plus global failure alerts
iTell the client when to come back

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.

vitestts
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.

“How to say it in the room

"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."

Test yourself

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?

Finished this one?
Tick it and it shows as done on the roadmap and the course.