Distributed Rate Limiter

1. Problem and requirements

Protect APIs from overload and abuse, and enforce plan quotas fairly, across every instance of every service.

Example policies

Functional requirements

Non-functional requirements

What “strict” means here

Strict enforcement means no over-admission caused by concurrency: two simultaneous requests can never both take the last token. It does not mean perfect rolling-window precision. Token buckets allow a burst up to capacity by design. Where a rolling-window guarantee is required (login), a different algorithm is used (section 4).

2. Capacity estimation

Assumptions: 50 instances across services, 50,000 requests/s at peak, 1.5 policy checks per request on average (most requests check one policy, some check a key limit and a tenant ceiling), 2 million keys active in any hour.

These are planning estimates. Script throughput per shard must be measured on the target hardware (see validation) before fixing the shard count.

3. Architecture and APIs

High-level architecture

flowchart LR
  C[Clients] --> GW[API gateway]
  GW -->|edge policies: IP, API key| RL1[Limiter filter]
  GW --> S1[Service A x N]
  GW --> S2[Service B x N]
  S1 --> RL2[Limiter library]
  S2 --> RL3[Limiter library]
  RL1 --> RC[(Redis Cluster: 4 primaries + replicas)]
  RL2 --> RC
  RL3 --> RC
  PS[(Policy store: config repo / DB)] -->|push on change| GW
  PS -->|push on change| S1
  PS -->|push on change| S2
  RL2 -. Redis unreachable .-> LL[Local token buckets]

Two enforcement points, same library:

• Gateway: coarse edge policies that need no business context: per IP, per API key, per plan. Stops abuse before it costs any service anything.
• Service: policies that need business context the gateway does not have, such as “5 payment initiations per user” where the user comes from the authenticated session.

Response contract

Every response that passed through a limiter carries the IETF RateLimit headers:

HTTP/1.1 200 OK
RateLimit-Policy: "free";q=100;w=60
RateLimit: "free";r=73;t=12

A rejection:

HTTP/1.1 429 Too Many Requests
Retry-After: 3
RateLimit: "free";r=0;t=3
Content-Type: application/problem+json

{ "type": "/errors/rate-limited", "status": 429, "code": "RATE_LIMITED",
  "policy": "free", "retryAfterSeconds": 3 }

Retry-After comes from the script: the exact time until enough tokens exist for this request, rounded up to whole seconds.

Policy definition

policies:
  - id: api-free
    match: { plan: free }
    key: [apiKey]
    algorithm: token-bucket
    capacity: 20             # burst
    refillPerMinute: 100     # sustained rate
    onStoreFailure: local
  - id: login
    match: { route: "POST /auth/login" }
    key: [ip, username]
    algorithm: sliding-log
    limit: 10
    window: 60s
    onStoreFailure: closed

Deployment

flowchart LR
  subgraph AZ1 [Zone 1]
    G1[Gateway pods]
    A1[Service pods]
    R1[(Redis primary 1, 2)]
    R2r[(Replica of 3, 4)]
  end
  subgraph AZ2 [Zone 2]
    G2[Gateway pods]
    A2[Service pods]
    R3[(Redis primary 3, 4)]
    R1r[(Replica of 1, 2)]
  end
  G1 --> R1
  G1 --> R3
  G2 --> R1
  G2 --> R3
  A1 --> R1
  A2 --> R3

Primaries are spread across zones with replicas in the other zone, so losing a zone promotes replicas rather than losing all limiter state.

4. Internal design and workflows

Algorithms compared

Choosing the algorithm per policy

• Token bucket for API quotas: it matches how APIs are actually used (bursts, then quiet) and expresses “burst 20, sustained 100/min” directly.
• Sliding-window log for login and other security limits: “10 attempts in any 60 seconds” must hold exactly, and the limits are small, so the memory cost (10 timestamps) is trivial.

Class diagram

classDiagram
  class RateLimiter {
    +check(RequestContext) RateLimitDecision
  }
  class PolicyResolver {
    +resolve(RequestContext) List~RateLimitPolicy~
  }
  class RateLimitPolicy {
    +id
    +keyParts List~KeyPart~
    +algorithm Algorithm
    +capacity
    +refillPerSecond
    +onStoreFailure FailureMode
  }
  class RateLimitKey {
    +policyId
    +hashTag
    +value
    +render() String
  }
  class RateLimitDecision {
    +allowed bool
    +remaining long
    +retryAfter Duration
    +policyId
  }
  class RateLimitStore {
    <<interface>>
    +acquire(keys, policies, cost) List~RateLimitDecision~
  }
  class RedisLuaStore
  class LocalBucketStore
  class FallbackStore {
    -primary RateLimitStore
    -fallback LocalBucketStore
    -breaker CircuitBreaker
  }
  class KeyBuilder {
    +build(policy, ctx) RateLimitKey
  }
  RateLimiter --> PolicyResolver
  RateLimiter --> KeyBuilder
  RateLimiter --> RateLimitStore
  RateLimitStore <|.. RedisLuaStore
  RateLimitStore <|.. LocalBucketStore
  RateLimitStore <|.. FallbackStore
  FallbackStore --> RedisLuaStore
  FallbackStore --> LocalBucketStore
  RateLimiter ..> RateLimitDecision

public interface RateLimitStore {
    /** Atomically consumes `cost` from every bucket, or from none if any would be rejected. */
    List<RateLimitDecision> acquire(List<RateLimitKey> keys, List<RateLimitPolicy> policies, int cost);
}

Key design

rl:{t:acme}:api-free:k:ak_9f21…        token bucket for an API key, tenant acme
rl:{t:acme}:tenant-ceiling              tenant-wide bucket
rl:{ip:203.0.113.7}:login:u:manoj        sliding log for one IP + username

• The hash tag in braces decides the Redis Cluster slot. A request’s key limit and its tenant ceiling share {t:acme}, so both live on one shard and one script can check them together atomically.
• Secrets never appear in keys: API keys are hashed (first 16 hex characters of SHA-256).
• Every key has a TTL equal to the time a bucket takes to refill completely, so idle keys expire on their own and memory stays bounded.

Preventing bypass:

• IP-based keys use the client IP from the trusted proxy chain only (the gateway strips client-supplied X-Forwarded-For and sets its own). IPv6 addresses are limited per /64, because one host can rotate through a whole /64.
• Login limits key on IP and username, plus a separate per-username limit, so rotating IPs does not bypass the per-account limit and one IP cannot lock out many accounts unnoticed.
• Authenticated limits key on the account, not on anything the client controls.

The atomic token bucket (Redis Lua)

-- KEYS[1..n]  bucket keys (same hash slot)
-- ARGV[1]     cost
-- ARGV[2..]   capacity_i, refill_per_ms_i for each key, in order
local t = redis.call('TIME')                         -- Redis clock: no client clock skew
local now = t[1] * 1000 + math.floor(t[2] / 1000)
local cost = tonumber(ARGV[1])
local state, ok, wait = {}, true, 0

for i, key in ipairs(KEYS) do
  local cap  = tonumber(ARGV[2 * i])
  local rate = tonumber(ARGV[2 * i + 1])
  local v = redis.call('HMGET', key, 'tk', 'ts')
  local tokens = tonumber(v[1]) or cap
  local ts = tonumber(v[2]) or now
  if now > ts then tokens = math.min(cap, tokens + (now - ts) * rate) end
  if tokens < cost then
    ok = false
    wait = math.max(wait, math.ceil((cost - tokens) / rate))
  end
  state[i] = { tokens, cap, rate }
end

local out = {}
for i, key in ipairs(KEYS) do
  local tokens, cap, rate = state[i][1], state[i][2], state[i][3]
  if ok then tokens = tokens - cost end              -- all or nothing
  redis.call('HSET', key, 'tk', tokens, 'ts', now)
  redis.call('PEXPIRE', key, math.ceil(cap / rate))  -- idle buckets disappear when full again
  out[i] = math.floor(tokens)
end
table.insert(out, 1, ok and 1 or 0)
table.insert(out, 2, wait)
return out                                           -- {allowed, retry_ms, remaining_1, ...}

Why this is correct under concurrency: Redis runs a script to completion before running anything else on that shard, so refill, check and consume happen as one step. Two requests racing for the last token are serialised; exactly one sees tokens >= cost.

Why TIME inside the script: if each instance passed its own clock, a server 2 seconds fast would grant extra tokens. Using the shard’s clock gives every caller the same time.

Sliding-window log (login)

-- KEYS[1] zset of attempt timestamps; ARGV: limit, window_ms, request_id
local t = redis.call('TIME')
local now = t[1] * 1000 + math.floor(t[2] / 1000)
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - tonumber(ARGV[2]))
if redis.call('ZCARD', KEYS[1]) >= tonumber(ARGV[1]) then
  local oldest = redis.call('ZRANGE', KEYS[1], 0, 0, 'WITHSCORES')
  return {0, tonumber(oldest[2]) + tonumber(ARGV[2]) - now}
end
redis.call('ZADD', KEYS[1], now, ARGV[3])
redis.call('PEXPIRE', KEYS[1], ARGV[2])
return {1, 0}

Decision sequence

sequenceDiagram
  participant Cl as Client
  participant F as Limiter filter
  participant P as PolicyResolver
  participant R as Redis shard
  participant H as Handler
  Cl->>F: request
  F->>F: extract identity (API key, user, trusted IP, tenant)
  F->>P: resolve(route, plan)
  P-->>F: [api-free, tenant-ceiling]
  F->>R: EVALSHA token_bucket (2 keys, same slot)
  alt allowed
    R-->>F: {1, 0, 73, 18450}
    F->>H: proceed
    H-->>Cl: 200 + RateLimit headers
  else rejected
    R-->>F: {0, 2400, 0, 18450}
    F-->>Cl: 429, Retry-After 3
  else Redis timeout (5 ms) or breaker open
    F->>F: policy.onStoreFailure: local / open / closed
  end

Token bucket, worked

Capacity 20, refill 100 per minute (1 token every 0.6 s):

Dynamic policies

Policies live in a versioned repository (or table). On change, a message on a config topic tells every instance to reload. Each instance also polls every 30 seconds in case it missed the message. A policy change takes effect on the next request, and existing bucket state carries over: lowering capacity simply clamps tokens to the new cap on the next refill.

Data ownership

The limiter owns only ephemeral counters. Losing all of Redis loses at most one refill period of state, so Redis runs without persistence for this workload (or with relaxed appendfsync everysec), which keeps latency low.

5. Failure modes and consistency

Fail open or fail closed?

Concurrency and idempotency

Rate limiting consumes a token per attempt, including retries. Retried requests carrying the same Idempotency-Key are answered from the idempotency store before the limiter runs, so a client’s safe retry does not spend quota twice.

6. Scaling evolution

7. Operations and validation

Metrics and SLOs

Test plan (to build)

Benchmark (to measure)

Measure: script calls per second per shard, decision latency p50, p95 and p99 at 25%, 50% and 100% of estimated peak, and accuracy (allowed ÷ limit) under 200 concurrent clients sharing one key. Run once with Redis healthy and once with one shard killed. Results will be added only after the runs.

8. Decision records

DR-1: Redis-backed token bucket rather than local counters

• Context: 50 instances; quotas are per customer, not per instance.
• Decision: shared state in Redis, refill and consume in one Lua script.
• Rejected: local counters (a limit of 100 becomes up to 5,000 across 50 instances); INCR with a fixed window (allows 2× bursts at window edges and cannot express burst plus sustained rate); a database (too slow and too much write load for every request).

DR-2: Redis TIME, not the caller’s clock

• Decision: every bucket calculation uses the shard’s clock.
• Why: removes clock skew as a source of over-admission at no cost.

DR-3: Failure mode is part of each policy

• Decision: onStoreFailure is mandatory in every policy definition.
• Why: “what happens when Redis is down” has different right answers for login and for search. Forcing the choice at definition time prevents an implicit global default being wrong for security endpoints.

9. Limitations, and implemented versus proposed

Known limitations

• Replica promotion after a Redis failure can over-admit for a short window.
• Local leasing (stage 4) trades accuracy for latency by up to one batch per instance.
• Rate limiting is not DDoS protection; volumetric attacks must be absorbed at the network edge before they reach the gateway.

Status