Sweaty Imposter

Design a Distributed Rate Limiter

System DesignLow LatencyShared StateMid3 min readUpdated

Every request in the fleet pays for this check, so it has to cost almost nothing. The interview is about the counting algorithm, where the counters live, and what happens when that store goes down.

1 · Requirements

The Prompt

Throttle API requests to N per minute per API key across a fleet of services, with low overhead and consistent behavior across regions.

Functional

  • Allow up to N requests a minute per API key and route
  • Reject over-limit requests with a 429 and a Retry-After header
  • Let admins change a key's limit and burst without a deploy

Non-Functional

  • The check adds under 2 ms to p99 latency
  • Limits hold across every service in the fleet and across regions
  • A limiter outage never takes the API down with it

2 · Estimates

Drill This Phase First

Show the Answer and Estimates

Answer

About 500,000 a second

100 times 5,000 is 500,000 checks a second. A 16-shard Redis cluster handles about 1M operations a second, which leaves about 2x headroom.

Checks
100 services at about 5,000 requests a second each: about 500,000 checks a second
Throughput
One INCR and EXPIRE per check at about 0.2 ms: a 16-shard Redis cluster gives about 1M operations a second
Memory
10M active API keys, about 100 bytes a bucket, and four windows each: about 4 GB per region, which fits easily in RAM
Latency
Under 2 ms added at p99, so Redis sits in the same availability zone as the API gateway
Regions
Replicate counters with conflict-free replicated data types (CRDTs) or shard by key region; eventual consistency is fine for soft limits

3 · API

Internal: rateLimit.check(api_key, route) → { allowed, remaining, reset_at }
PUT /admin/limits/:api_key { rps, burst } → 204 (control plane)
GET /admin/limits/:api_key → { rps, burst, current_usage }
Response header on throttle: 429 + Retry-After + X-RateLimit-Remaining

Data Model

buckets (Redis, key = "rl:{api_key}:{route}:{window}"):
  value          : int counter
  ttl            : window_size_seconds

policies (SQL, control plane):
  api_key (PK)   : string
  tier           : enum(free|pro|enterprise)
  rps            : int
  burst          : int
  updated_at     : timestamp

audit_log (Kafka topic):
  api_key, route, ts, allowed, remaining

4 · High-Level Design

Each request costs one atomic Redis call that increments the key's counter and sets its expiry. Allowed requests pass through to the backends, and rejected ones get a 429 with Retry-After. Admins change limits in the policy store, and the gateways cache them.

5 · Deep Dives

Choosing the Algorithm

A fixed window counter is one INCR, but it lets twice the limit through at a window edge. A sliding window log is exact, at the cost of one sorted-set entry per request. A token bucket allows short bursts up to a set size and is the common default for APIs.

Atomic Updates

Reading, comparing, and writing in separate calls races under load and lets extra requests through. Do the check in one step: INCR with EXPIRE, or a short Lua script that runs atomically on the Redis shard that owns the key.

When Redis Is Down

Decide up front whether to fail open or fail closed. Most public APIs fail open with a local in-memory limit on each node, so a limiter outage weakens protection while requests keep flowing.

6 · Wrap Up

Wrap up with what comes next: limits by user and IP alongside the API key, a global limit for one expensive route, and dashboards that show who is being throttled and why.

The Short Version

Token bucket or sliding window log/counter in Redis. Atomic INCR + EXPIRE. Per-region shard if global isn't required.

Building Blocks