Design a Distributed Rate Limiter

An API serves 40 application servers behind a load balancer. One customer's buggy script starts calling it 5,000 times a second, and everyone else's requests slow to a crawl. A limit of "100 requests per second per API key" would have stopped it, but where should that limit live? Each server only sees about a fortieth of the traffic, so a counter in each server's memory would allow 40 times the intended rate. The limit has to be shared across servers, checked on every request, and must add almost no latency.

That is the distributed rate limiter, one of the most frequently asked component designs. It is small enough to cover completely in an interview, and deep enough to show algorithm choice, atomicity, latency budgets and failure behaviour.

• Why rate limiting exists and what to limit by.
• Where a rate limiter can sit in an architecture.
• Five algorithms, compared with a runnable simulation.
• A distributed implementation with atomic Redis operations.
• Local-plus-global hybrids for very high throughput.
• What to do when the limiter's store fails, and limits across regions.
• Responses, headers and client behaviour.

Build a rate-limiting component for a public API used by mobile apps, web clients and third-party developers. It must enforce limits such as "100 requests per second per API key" and "5 login attempts per minute per account" across a fleet of API servers, reject excess requests quickly, and tell clients when they may retry.

Rate limiting serves three purposes:

• Protection: prevent any client from exhausting shared capacity (article 23).
• Fairness: share capacity between clients, and enforce paid plan quotas.
• Abuse resistance: slow down credential stuffing, scraping, spam and brute-force attacks (article 28).

Microsoft's Rate Limiting pattern and Throttling pattern describe these goals from the service's point of view: controlling consumption so the system stays within capacity and meets service levels (Rate Limiting pattern, Throttling pattern).

Functional requirements

1. Decide allow or reject for each request against one or more rules.
2. Support rules by API key, user, IP and endpoint, with configurable rates and bursts.
3. Return 429 Too Many Requests with retry information when rejecting.
4. Let operators change limits without redeploying.

Out of scope: billing for usage, detailed analytics of rejected requests, bot detection based on behaviour (a related but separate system).

Non-functional requirements

API traffic at peak: 200,000 requests per second across 40 gateway instancesRules checked per request: about 2 (for example per API key, plus a per-endpoint rule)Limiter operations at peak: about 400,000 per secondActive keys: 10 million users + 50,000 API keys + several million IPs per hourState per key: about 100 bytes (count or tokens, timestamp, key name, overhead)Hot state: 20 million keys x 100 bytes = 2 GB (keys expire when idle)

Conclusions: the state is small (gigabytes, in memory), but the operation rate is high: 400,000 operations per second, each on the request's critical path. A single in-memory store node can typically handle a large number of simple operations per second, but you should confirm with load tests and plan to partition keys across several nodes for headroom and availability.

The limiter is a component, so its "API" is internal:

check(rules: [ {key: "apikey:ak_51", limit: 100/s, burst: 200},               {key: "endpoint:POST /v1/messages:apikey:ak_51", limit: 10/s, burst: 20} ])  -> { allowed: true | false,       remaining: 87,       retry_after_ms: 0 | 1200 }

What clients of the public API see:

HTTP/1.1 429 Too Many RequestsRetry-After: 2Content-Type: application/problem+json{"title": "Rate limit exceeded", "status": 429, "detail": "Limit of 100 requests per second for this API key exceeded."}

RFC 6585 defines 429 Too Many Requests and says the response may include a Retry-After header saying how long to wait (RFC 6585). Many APIs also return headers telling clients their limit and what remains; an IETF draft proposes standard RateLimit header fields for this (RateLimit header fields draft). Until such headers are standardised, document whichever headers you return.

Rules are configured separately:

rules:  - match: { plan: "free" }        key: apikey   rate: 10/s   burst: 20  - match: { plan: "pro" }         key: apikey   rate: 100/s  burst: 200  - match: { path: "/v1/login" }   key: account  rate: 5/min  burst: 5   strict: true  - match: { anonymous: true }     key: ip       rate: 20/s   burst: 40

Per limited key, the store holds a tiny piece of state whose shape depends on the algorithm:

Keys look like rl:{rule_id}:{subject} (for example rl:pro-apikey:ak_51), and every key has a TTL slightly longer than its window or refill time, so idle keys disappear and memory stays bounded. Rules (limits per plan and endpoint) live in a configuration store and are cached in every gateway instance.

Partition key: the full limiter key. Each check touches one key, so keys spread across cache nodes by hash, and each check is a single-node operation.

Clients --> Load balancer --> API gateway instances (x40) --> Services                                   |   check(rules)                                   v                          Rate-limit store (Redis), shared by all gateways                                   ^                    Rule configuration service --(cached in each gateway)

Where to put the limiter:

Most designs put general limits in the gateway (as a library or plugin talking directly to the store) and add a few in-service limits for business rules ("10 password resets per day per account").

1. Choosing an algorithm that allows the right bursts and is cheap to compute.
2. Race conditions: 40 gateways reading and updating the same counter concurrently can over-admit if read and write are separate steps (article 14).
3. Latency: one store round trip per rule per request.
4. The store's availability: if it is down or slow, every request is affected.
5. Hot keys: one huge client's key receives a large share of operations.

Fixed window. Count requests in fixed clock windows (10:00:00 to 10:00:09.999, and so on). Simple: one counter per window. Problem: a client can send a full window's quota at the end of one window and another full quota at the start of the next, doubling the rate briefly.

Sliding log. Store the timestamp of each accepted request; reject if the number in the last window length is at or above the limit. Accurate, but memory grows with the limit (one entry per request).

Sliding window counter. Keep counts for the current and previous fixed windows, and estimate the sliding count as previous_count x (portion of the previous window still inside the sliding window) + current_count. Close to the sliding log's accuracy with two counters of memory; slightly approximate.

Token bucket. A bucket holds up to capacity tokens and refills at a steady rate. Each request takes a token; if the bucket is empty, the request is rejected. It allows bursts up to the capacity, then a steady rate. Only two numbers of state. A common default for APIs.

Leaky bucket. Requests enter a queue (the bucket) and are processed at a fixed rate; if the queue is full, new requests are dropped. It smooths output to a constant rate, which suits protecting a downstream system that cannot absorb bursts, but it adds queueing delay. (The name is sometimes also used for a rejecting variant equivalent to a token bucket.)

This Java program sends the same requests to a fixed-window limiter, a sliding-log limiter and a token bucket, each configured for "5 requests per 10 seconds" (the bucket holds 5 tokens and refills one every 2 seconds, the same long-run rate). Five requests arrive just before a window boundary and five just after.

// File: RateLimiters.javaimport java.util.ArrayDeque;import java.util.Deque;import java.util.Locale;public class RateLimiters {    static final int LIMIT = 5;              // at most 5 requests ...    static final long WINDOW_MS = 10_000;    // ... per 10 seconds    // Fixed window: one counter per 10-second block of the clock.    static long currentWindow = -1;    static int windowCount = 0;    static boolean fixedWindow(long nowMs) {        long window = nowMs / WINDOW_MS;        if (window != currentWindow) {            currentWindow = window;            windowCount = 0;        }        if (windowCount < LIMIT) {            windowCount++;            return true;        }        return false;    }    // Sliding log: remember the times of accepted requests in the last 10 seconds.    static final Deque<Long> log = new ArrayDeque<>();    static boolean slidingLog(long nowMs) {        while (!log.isEmpty() && log.peekFirst() <= nowMs - WINDOW_MS) {            log.pollFirst();        }        if (log.size() < LIMIT) {            log.addLast(nowMs);            return true;        }        return false;    }    // Token bucket: capacity 5 tokens, refilled at 1 token every 2 seconds (same long-run rate).    static final long CAPACITY_MILLI = LIMIT * 1000L;  // tokens are counted in thousandths    static long tokensMilli = CAPACITY_MILLI;           // the bucket starts full    static long lastRefillMs = 0;    static boolean tokenBucket(long nowMs) {        tokensMilli = Math.min(CAPACITY_MILLI, tokensMilli + (nowMs - lastRefillMs) / 2); // 0.5 token per second        lastRefillMs = nowMs;        if (tokensMilli >= 1000) {            tokensMilli -= 1000;            return true;        }        return false;    }    public static void main(String[] args) {        long[] arrivals = {9_100, 9_300, 9_500, 9_700, 9_900, 10_100, 10_300, 10_500, 10_700, 10_900, 12_000, 15_000};        int fixed = 0;        int sliding = 0;        int bucket = 0;        System.out.println("time(s)  fixed-window  sliding-log  token-bucket");        for (long t : arrivals) {            boolean f = fixedWindow(t);            boolean s = slidingLog(t);            boolean b = tokenBucket(t);            fixed += f ? 1 : 0;            sliding += s ? 1 : 0;            bucket += b ? 1 : 0;            System.out.printf(Locale.US, "%7.1f  %-12s  %-11s  %s%n", t / 1000.0,                    f ? "allow" : "reject", s ? "allow" : "reject", b ? "allow" : "reject");        }        System.out.println("allowed: fixed=" + fixed + " sliding=" + sliding + " bucket=" + bucket);    }}

time(s)  fixed-window  sliding-log  token-bucket    9.1  allow         allow        allow    9.3  allow         allow        allow    9.5  allow         allow        allow    9.7  allow         allow        allow    9.9  allow         allow        allow   10.1  allow         reject       reject   10.3  allow         reject       reject   10.5  allow         reject       reject   10.7  allow         reject       reject   10.9  allow         reject       reject   12.0  reject        reject       allow   15.0  reject        reject       allowallowed: fixed=10 sliding=5 bucket=7

The fixed window let ten requests through within two seconds, double the intended rate, because a window boundary fell in the middle of the burst. The sliding log never allowed more than 5 in any 10-second span, and kept rejecting until the earlier requests aged out. The token bucket allowed the initial burst, then admitted requests as tokens refilled (one every 2 seconds), which is usually the behaviour API clients find most natural.

Decision: token bucket for general API limits (bursts are friendly to real clients), sliding log for strict security limits with low counts (login attempts per account), fixed daily windows for plan quotas.

Each check must read and update state atomically; otherwise two gateways can both see "1 token left" and both admit a request. Options in Redis:

• Atomic commands for simple counters: INCR increments and returns the new value atomically. Redis's documentation describes rate-limiter patterns built on INCR and EXPIRE, and points out a race in a naive version where the counter can be created without its expiry, fixed by making the increment and expiry atomic, for example with a Lua script (INCR).
• Lua scripts for algorithms with more logic (token bucket, sliding window): Redis runs a script atomically, with no other command interleaved (Scripting with Lua).

A token-bucket script (illustrative):

-- KEYS[1] = bucket key; ARGV = capacity, refill_per_ms, now_ms, costlocal capacity   = tonumber(ARGV[1])local refill     = tonumber(ARGV[2])local now        = tonumber(ARGV[3])local cost       = tonumber(ARGV[4])local state      = redis.call('HMGET', KEYS[1], 'tokens', 'ts')local tokens     = tonumber(state[1]) or capacitylocal ts         = tonumber(state[2]) or nowtokens = math.min(capacity, tokens + (now - ts) * refill)local allowed = 0if tokens >= cost then  tokens = tokens - cost  allowed = 1endredis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / refill) + 1000)return {allowed, tokens}

One round trip, atomic, constant memory. Passing now from the gateway introduces clock differences between gateways; using the Redis server's own time inside the script avoids that, at a small cost.

Shard limiter keys across several Redis primaries (for example Redis Cluster, which assigns keys to hash slots, article 32), each with a replica. 400,000 operations per second spread over, say, 8 primaries is about 50,000 per node, leaving headroom. Because each check touches one key, there are no cross-node operations.

For extremely high rates, or to save latency:

• Batch decrements: each gateway takes a small lease of tokens from the global bucket (for example 20 at a time) and spends them locally, returning to Redis only when its local allowance is used. Fewer round trips; accuracy drops slightly (unused local tokens are "reserved").
• Local pre-check: each gateway also enforces a generous local limit (the global limit divided by the number of gateways, with slack) so that a runaway client is cut off locally even before the global check.
• Asynchronous sync: gateways count locally and push counts to the store every 100 ms. Very cheap, but a client can exceed the limit briefly. Acceptable for soft limits, not for login limits.

A single very large API key can generate a large share of operations on one Redis node. Mitigations: local token leases (above) for that key, or splitting its bucket into several sub-buckets on different nodes, each with a share of the rate.

The most important decision: what if the limiter's store is unavailable or slow?

Combine the policy with protections:

• A strict timeout on limiter calls (for example 5 ms); a slow store must not slow every request.
• A circuit breaker on the store client; when open, apply the rule's failure policy immediately.
• Local fallback limits: when failing open, each gateway still enforces a coarse local limit, so abusive clients are not completely unlimited during a store outage.
• Replicas and failover for each store shard; after a failover, recent counts may be lost (asynchronous replication), which briefly resets some limits: acceptable for soft limits.

Limits are counters shared across gateways; the atomic script gives correct behaviour per key within one store node. Across replicas, asynchronous replication means a failover can lose a few recent updates; for soft limits, slightly inaccurate counts during rare failovers are fine. For strict limits, keep counts on primaries only and fail closed when unsure.

Multiple regions. A truly global limit ("1,000 requests per minute across all regions") would need cross-region coordination on every request, adding tens or hundreds of milliseconds. Practical options: split the limit between regions (for example by each region's normal share of traffic), or keep regional limits and reconcile periodically (regions exchange counts every few seconds). Accept approximate global enforcement in exchange for low latency: the same trade-off as the stock-allocation answer in article 19.

• Choose the right key: API keys and user ids are harder to rotate than IPs, so they make better identities. IPs are shared (offices, mobile carriers) and easy to change (botnets), so IP limits should be generous and combined with others.
• Protect sensitive flows with strict, fail-closed limits keyed by account (not only IP), to slow credential stuffing that rotates IPs.
• Do not leak information in error messages (for example, whether an account exists).
• Limit the limiter: an attacker sending requests with millions of random keys can fill the store; apply limits keyed by IP before limits keyed by request-supplied identifiers, and keep TTLs short.
• Business-flow abuse (sneaker bots, ticket scalping, coupon abuse) needs more than rate limits: per-account quotas, queues and behavioural detection (article 28's OWASP API6).

"The rate limiter enforces per-API-key, per-user, per-IP and per-endpoint rules across 40 gateway instances, adding under 2 ms at p99. At peak it handles about 400,000 checks a second over a few gigabytes of state.

It runs as a library in the API gateway, so excess requests are rejected before reaching services, with 429 and Retry-After. Rules come from a configuration service and are cached in each gateway. State lives in a sharded Redis cluster; each check is one atomic Lua script on one key.

General limits use a token bucket, which allows short bursts but caps the long-run rate; strict security limits like login attempts use a sliding log. Limiter calls have a 5 ms timeout and a circuit breaker; general rules fail open with a local fallback limit, and security rules fail closed. Very hot keys use local token leases to save round trips. Across regions we split global limits into regional shares rather than coordinating on every request. The trade-off throughout is a little accuracy for low latency and high availability, except on security rules, where we choose strictness."

Gateway 1: GET key -> 99Gateway 2: GET key -> 99Gateway 3: GET key -> 99Gateway 1: SET key 100, allowGateway 2: SET key 100, allowGateway 3: SET key 100, allow-> 3 requests admitted where 1 should have been; the counter shows 100, hiding it

Checks per second = 1.2M x 3 = 3.6 million script executions per secondPrimaries = 3.6M / 80,000 = 45 primaries (plus a replica each); round up for headroom, say 50 to 60

• Next: Design a Distributed Cache, the kind of in-memory store this limiter depends on.
• Related: overload protection (article 23) and abuse prevention (article 28).