Designing a Distributed Rate Limiter

At 09:00 a partner launches a campaign and traffic jumps tenfold. At 09:01 one tenant’s retry loop consumes every worker. At 09:02 the API is returning 503 to customers who did nothing wrong. A rate limiter is supposed to prevent this story, but a counter in each application process cannot: every replica sees only part of the traffic, replicas scale in and out, and retries move between them.

A distributed rate limiter turns a policy such as “120 writes per minute per tenant” into one decision shared by many callers. That sounds like a counter problem. In production it is also a time, identity, consistency, availability, and abuse problem. The useful design is not the mathematically purest algorithm; it is the smallest mechanism whose errors match the risk of the protected operation.

We will build a Redis-backed token bucket in TypeScript. The same design can protect an HTTP gateway, a queue consumer, or an expensive internal capability, provided policy and identity are made explicit.

Start with policy, then choose the algorithm #

A limit needs four values: a subject, an operation, a capacity, and a refill rate. “Per IP” is incomplete. “Allow each authenticated tenant 100 report exports per hour, with a burst of 5” is executable. Separate policies for reads, writes, login attempts, and costly exports; one global number rewards cheap endpoints for competing with expensive ones.

Common algorithms make different promises:

For a token bucket with capacity $C$, refill rate $r$ tokens per millisecond, elapsed time $\Delta t$, and request cost $w$, the available balance is

The request is accepted when $T' \ge w$, after which the stored balance becomes $T' - w$. Capacity controls the permitted burst; refill rate controls sustained traffic. Weighted costs let a cached lookup consume one token while a video transcode consumes fifty.

Token buckets do not guarantee a perfectly even output stream. If downstream requires exactly ten jobs each second, a leaky bucket or queue scheduler is a better shaper. If the requirement is “no more than five password guesses in any rolling ten minutes,” a sliding log may justify its memory cost.

Make the key represent the real subject #

The storage key is part of the security model. A useful shape includes policy version, operation, and normalized subject:

rl:v3:{tenant_7f2}:reports.export

The braces are a Redis Cluster hash tag. Keys for the same tenant land in one slot, which matters if a future script updates both a tenant bucket and an endpoint bucket. Do not put raw API keys, email addresses, or session tokens in Redis keys or metrics. Resolve credentials to an internal identifier, normalize it, bound its length, and hash untrusted values when necessary.

Identity precedence should be deliberate. For an authenticated API, use tenant or account ID, optionally followed by user ID. Use API key ID when keys carry separate quotas. IP is a fallback for anonymous traffic, not a universal identity: carrier NAT can put thousands of users behind one address, while an attacker can rotate IPv6 addresses or proxies. Parse client IP only from trusted proxy headers; accepting arbitrary X-Forwarded-For lets clients choose their own bucket.

Layering is often stronger than searching for one perfect key. A login route might enforce a small bucket per account, a larger one per network prefix, and a global emergency ceiling. An export route might check both tenant budget and user budget. Keep cardinality bounded: attackers can invent subject IDs to create millions of Redis keys. Authenticate before allocating durable state where possible, reject malformed identities, set expiry on every bucket, and cap the number of anonymous identities admitted at the edge.

Policy changes also need versioning. Including v3 avoids reinterpreting old token balances when capacity or units change. Old keys disappear through TTL instead of requiring a risky scan-and-delete operation.

Make refill and consumption one atomic operation #

A naive implementation performs GET, calculates tokens in the application, then performs SET. Two application replicas can read the same balance and both admit the final token. A Redis transaction with optimistic retries can work, but one Lua script is simpler: Redis executes the script atomically, next to the data, in one network round trip.

-- token_bucket.lua
-- KEYS[1]: bucket key
-- ARGV: capacity, refill tokens/ms, request cost, idle TTL ms
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_per_ms = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local idle_ttl_ms = tonumber(ARGV[4])

if not capacity or not refill_per_ms or not cost or
   capacity <= 0 or refill_per_ms <= 0 or cost <= 0 then
  return redis.error_reply('invalid token bucket arguments')
end

local redis_time = redis.call('TIME')
local now_ms = redis_time[1] * 1000 + math.floor(redis_time[2] / 1000)
local state = redis.call('HMGET', key, 'tokens', 'refilled_at_ms')
local tokens = tonumber(state[1]) or capacity
local refilled_at_ms = tonumber(state[2]) or now_ms
local elapsed_ms = math.max(0, now_ms - refilled_at_ms)

tokens = math.min(capacity, tokens + elapsed_ms * refill_per_ms)

local allowed = 0
local retry_after_ms = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_after_ms = math.ceil((cost - tokens) / refill_per_ms)
end

redis.call('HSET', key,
  'tokens', tostring(tokens),
  'refilled_at_ms', tostring(now_ms))
redis.call('PEXPIRE', key, idle_ttl_ms)

return { allowed, math.floor(tokens), retry_after_ms, now_ms }

Using Redis TIME gives all application replicas one clock for a bucket. A client-provided timestamp would let clock skew refill a bucket twice or move it backward. math.max(0, ...) is still defensive against a Redis clock adjustment. The clock is wall time, not a perfect monotonic clock, so monitor host time synchronization and avoid deriving billing-grade usage records solely from limiter state.

The TypeScript boundary validates policy, builds the key, executes the cached script, and returns enough information for HTTP headers and telemetry. This example uses ioredis; production code should load the script and prefer EVALSHA, falling back to EVAL after NOSCRIPT.

import type Redis from 'ioredis';
import tokenBucketLua from './token-bucket.lua.js';

export interface RateLimitPolicy {
  readonly name: string;
  readonly version: number;
  readonly capacity: number;
  readonly refillPerSecond: number;
  readonly idleTtlSeconds: number;
}

export interface RateLimitDecision {
  readonly allowed: boolean;
  readonly remaining: number;
  readonly retryAfterMs: number;
  readonly decidedAtMs: number;
}

function safeSubject(subject: string): string {
  if (!/^[a-zA-Z0-9_-]{1,96}$/.test(subject)) {
    throw new Error('Invalid rate-limit subject');
  }
  return subject;
}

export class RedisTokenBucket {
  constructor(private readonly redis: Redis) {}

  async consume(
    policy: RateLimitPolicy,
    subject: string,
    cost = 1,
  ): Promise<RateLimitDecision> {
    if (!Number.isSafeInteger(cost) || cost <= 0) {
      throw new Error('Cost must be a positive integer');
    }

    const identity = safeSubject(subject);
    const key = `rl:v${policy.version}:{${identity}}:${policy.name}`;
    const refillPerMs = policy.refillPerSecond / 1000;
    const result = (await this.redis.eval(
      tokenBucketLua,
      1,
      key,
      policy.capacity,
      refillPerMs,
      cost,
      policy.idleTtlSeconds * 1000,
    )) as [number, number, number, number];

    return {
      allowed: result[0] === 1,
      remaining: result[1],
      retryAfterMs: result[2],
      decidedAtMs: result[3],
    };
  }
}

Choose an idle TTL long enough that an unused bucket can refill completely before deletion. Deletion then behaves like a full bucket, not an accidental quota increase. Reject a request whose cost exceeds capacity at policy validation time; otherwise it can never succeed.

Place enforcement close, and choose regional semantics #

Enforce coarse abuse limits at the CDN or gateway before expensive authentication, then enforce identity-aware quotas after authentication and before business work. Queue consumers should reserve budget before taking irreversible action. Avoid charging multiple times for an idempotent retry: either use an idempotency record before the limiter or make the quota explicitly count attempts rather than successful operations.

A single global Redis gives a strict global quota but adds cross-region latency and a large failure domain. Independent regional buckets are fast and available but can allow approximately $N$ times the intended burst across $N$ active regions. For most APIs, allocate each region a share of the global budget and rebalance slowly. Sticky routing by tenant improves accuracy. High-value operations may justify a home region or a globally consistent store, accepting latency for stronger enforcement.

Asynchronous replication cannot provide strict global admission: two regions can spend the same logical token before replication converges. State this as a product tradeoff, not an implementation footnote.

Hot keys are the other scaling limit. A global bucket for every request serializes the busiest path on one Redis shard. Prefer per-tenant keys, shard coarse global limits into several buckets with a conservative aggregate allowance, or enforce global protection locally at the edge. Pipeline independent checks, but keep checks that must succeed together in one same-slot script.

Define failure behavior and the HTTP contract #

Redis will eventually time out. “Fail open or fail closed?” must be answered per operation. Public reads may fail open briefly to preserve availability, guarded by a small in-process emergency bucket. Login, password reset, payment, and resource-creation endpoints usually fail closed or degrade to a stricter local limit. Never silently fail open for abuse-sensitive operations.

Return 429 Too Many Requests for an enforced quota, not 503. Include Retry-After in whole seconds and consistent rate-limit fields such as RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset. Document whether reset means seconds until sufficient tokens or a fixed-window boundary. Do not expose internal tenant IDs or key structure.

Successful responses should also include remaining budget when useful to clients. Clamp values to zero, round reset upward, and avoid promising exactness when regional allocation is approximate. A machine-readable error code such as RATE_LIMITED lets SDKs distinguish throttling from authorization failure.

Observe, test, and defend the limiter itself #

Measure decisions by policy and region: allowed count, denied count, Redis latency, script errors, degraded-mode entries, and retry-after distribution. Do not label metrics by subject or raw key; that creates unbounded cardinality and leaks identifiers. Sample structured logs with policy, region, decision, cost, and a one-way subject hash. Trace the Redis call so a latency spike is visible in the request path.

Test the model before load testing the infrastructure. A deterministic reference implementation with an injected clock can verify refill, capacity, weighted costs, backward time, TTL, and exact-boundary behavior. Then run concurrent integration tests against Redis: hundreds of consumers racing for a bucket of 100 must produce exactly 100 admissions. Test script reload after Redis failover, cluster slot placement, timeout behavior, and policy version migration. Multi-region simulations should quantify expected overshoot rather than assert impossible global precision.

Load tests need skewed traffic, not only uniform random keys. Exercise one extremely hot tenant, many one-request identities, synchronized bursts at a minute boundary, costly weighted requests, Redis latency injection, and a client that ignores Retry-After. Verify memory stabilizes after TTL and that the limiter still protects the application when it is under attack.

Rate limiting is only one abuse control. Pair it with authentication, request-size limits, concurrency limits, idempotency, bot detection, and account-level anomaly rules. A patient attacker can stay below any simple rate while consuming expensive resources; cap concurrent work and total daily budget as well as request frequency.

Final takeaways #

A production limiter begins with a precise policy and identity, not a Redis counter. Token buckets are a strong default because they express both sustained rate and burst capacity. Store policy version and normalized subject in a bounded, expiring key. Use Redis server time and one Lua script so refill and consumption are atomic across replicas.

Decide explicitly how much regional overshoot is acceptable, how hot keys are distributed, and which operations fail open or closed. Make 429 responses actionable through headers, watch decisions without high-cardinality labels, and test races, skew, failover, and hostile identity creation. The limiter is successful when overload becomes a controlled product behavior instead of an accidental outage.