Distributed Rate Limiter

0) Problem Restatement

Design a service that limits how often a client can call an API. For example: "each user can make at most 100 requests per minute" or "each company can use at most 1 million AI tokens per month". When a client goes over the limit, we reject the request with HTTP 429 (Too Many Requests) and tell them when to try again.

The tricky part is that our API runs on hundreds of servers. A user's requests can land on any of them, so the servers must share one view of how many requests the user has already made.

1) Requirements

1.1 Functional

• Limit by key: limit requests per user, per API key, per IP address, or per tenant (a tenant is one customer company).
• Configurable rules: e.g., 100 requests/minute for free users and 1,000 requests/minute for paid users.
• Allow short bursts: a user who was idle can send a few requests at once.
• Clear response: return 429 with a Retry-After header saying how many seconds to wait.
• Count cost, not just requests (variant): some limits count units such as LLM tokens or GB of storage.

1.2 Non-Functional

• Very low latency: the check runs on every request, so it should add less than ~2 ms.
• High availability: if the limiter breaks, the API should keep working.
• Accuracy: small over-counting or under-counting is fine; letting someone send 10x their limit is not.
• Scale: must handle the full traffic of the company.

1.3 Scale Estimates

• 50 million daily users, peak traffic 500,000 requests per second.
• Each request = 1 limiter check, so 500K checks/sec.
• Each counter is tiny (key + count + timestamp ≈ 100 bytes). With 50M active keys that is about 5 GB, which fits in memory across a small Redis cluster.

1.4 API Design

The limiter is usually called internally, not by end users:

• POST /v1/ratelimit/check with { key: "user:42", rule: "api_default", cost: 1 } → returns { allowed: true, remaining: 57, retry_after_ms: 0 }.
• PUT /v1/ratelimit/rules/{rule} with { limit: 100, window_sec: 60, burst: 20 } → admin API to change a rule.

2) High-Level Architecture

2.1 Overview

• API Gateway: every request passes through here first. It calls the rate limiter before forwarding the request.
• Rate Limiter logic: runs as a library inside the gateway (fastest) or as a small sidecar service.
• Redis cluster: stores the counters so every gateway server sees the same numbers.
• Rules service: stores the rules in a database and pushes changes to the gateways, which keep a local copy in memory.

2.2 Architecture Diagram

flowchart LR
    C["Client"] --> GW["API Gateway + Rate Limiter"]
    GW -->|"check and update counter"| R[("Redis Cluster")]
    GW -->|"allowed"| S["Backend Services"]
    GW -->|"rejected"| C
    RS["Rules Service"] -->|"push rule changes"| GW
    RS --> DB[("Rules DB")]

3) Choosing an Algorithm

This is the heart of the interview. Here are the common options in simple terms:

We only need to store two numbers per key: tokens and last_refill_time. When a request comes in, we add the tokens earned since last_refill_time, then try to take one.

4) Data Model

One Redis hash per key:

key:     rl:{rule}:{user_id}         e.g. rl:api_default:42
fields:  tokens = 12.4
         last_refill_ms = 1726740000123
TTL:     2 x window (so idle keys clean themselves up)

Rules (in a normal database, cached in memory on gateways):

CREATE TABLE rate_limit_rules (
  rule_name   TEXT PRIMARY KEY,
  limit_count INT,        -- tokens added per window
  window_sec  INT,
  burst       INT,        -- bucket size
  updated_at  TIMESTAMP
);

5) Key Flows

5.1 Checking a request

1. Request arrives at the gateway. The gateway finds the rule for this route and user tier (from its in-memory copy).
2. The gateway runs one Redis script (Lua) that refills tokens, checks if at least cost tokens are left, subtracts them, and returns the result. Running it as one script makes it atomic: two servers cannot both take the last token at the same time.
3. If allowed, forward the request. If not, return 429 with Retry-After = (cost - tokens) / refill_rate.

5.2 Changing a rule

An admin updates a rule in the Rules Service. It saves the rule and publishes an event. Every gateway receives it and updates its local copy within a few seconds.

6) Deep Dive A — Why the update must be atomic

Without atomicity, two servers can read tokens = 1 at the same time, both allow the request, and both write tokens = 0. The user got 2 requests for 1 token. Doing read-refill-subtract-write inside a single Lua script fixes this, because Redis runs one script at a time per key.

We shard Redis by key (consistent hashing), so each user's counter lives on exactly one Redis node. That keeps every check to a single network call.

7) Deep Dive B — Speed, hot keys and failures

• Latency: a Redis call inside the same data center takes about 0.5–1 ms. That fits our budget.
• Hot keys: one huge customer can send 50K requests/sec, all hitting one Redis key. Fix: give that customer a local token bucket on each gateway holding a slice of the limit (e.g., 50 gateways × 1/50 of the limit), and sync with Redis in batches every 100 ms. We trade a little accuracy for a lot of speed.
• Redis is down or slow: we must choose.
• Fail open (allow requests): the API keeps working, but nobody is limited for a while. Good for normal APIs.
• Fail closed (reject requests): safer for expensive or abuse-prone endpoints such as login or payments.
• Most teams fail open with a short timeout (e.g., 5 ms) and a fallback to a rough local limit.
• Multiple regions: keep counters per region and give each region a share of the global limit. Truly global exact counting would need cross-region calls on every request, which is too slow.

8) Trade-offs & Alternatives

9) Common Follow-up Questions

• "How do you limit monthly quotas?" Use a plain counter per tenant per month (INCRBY with the cost), stored durably because losing it would reset someone's quota. Warn the customer at 80% and 100%.
• "How do you limit LLM token usage when you don't know the cost up front?" Reserve an estimate before the call, then adjust with the real token count after the response.
• "How do clients know their limits?" Return headers like X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset on every response.

10) Wrap-Up

A good answer picks the token bucket, stores two numbers per key in a sharded Redis cluster, updates them atomically with a Lua script, and runs the check inside the API gateway. Then it explains the hard parts: hot keys, what to do when Redis fails, and why limits in multiple regions have to be approximate.