Design a Rate Limiter

A rate limiter restricts how many requests a client can make in a time window and rejects the excess. It protects services from overload and abuse, keeps one tenant from consuming a shared resource, and bounds cost. This article designs a rate limiting service used by many API servers. The algorithms themselves (token bucket, leaky bucket, fixed and sliding windows) are compared in rate limiting algorithms. Here the focus is the system around them.

Requirements

Functional requirements

• Limit requests by a configurable key: user ID, API key, IP address, or a combination with the endpoint.
• Support several rules at once (for example 10 requests per second and 1,000 per hour) and different limits per client tier.
• Return a clear rejection to the caller (HTTP 429 Too Many Requests) with information about when to retry.
• Rules can be changed at runtime without a deploy.

Non-functional requirements

• Low latency. The check runs on every request. Its added latency budget is a few milliseconds at most.
• Accuracy. Limits should hold under concurrent requests to many servers. Small overshoot is acceptable. Large overshoot is not.
• High availability. A failure of the limiter must not take down the API. The default on failure is to allow traffic (fail open).
• Scalability. Handle the full request rate of the platform and millions of distinct keys.
• Memory efficiency. State per key must be small.

Estimation

Assumptions: 500,000 requests per second across the platform at peak, 10 million active keys in a limiting window, and one rule per key for sizing.

• Checks: every request needs one limiter check: 500,000 checks per second. This rate is above what a single Redis node sustains for scripted operations (a single node typically handles on the order of 100,000 simple operations per second, and scripted operations cost more than plain commands), so the state must be partitioned across nodes. With 10 shards, each takes about 50,000 checks per second.
• State per key: a token bucket needs a token count and a last-refill timestamp: 16 bytes of payload. With key name (about 40 bytes) and Redis overhead, assume about 100 bytes per key.
• Memory: 10,000,000 x 100 bytes = 1 GB. That fits in one node, so shards exist for throughput, not memory.
• Latency: an in-datacenter Redis round trip is on the order of 0.5 ms. A check adds about 1 ms including network.

What each number implies:

• 500,000 checks/s: one shared Redis node cannot carry it, so state is sharded by key (10 shards, about 50,000 scripted checks/s each, leaving headroom below the roughly 100,000 ops/s ceiling).
• 1 GB of state: memory is not the constraint; TTLs still matter so idle keys disappear.
• About 1 ms added per request: acceptable against a typical 50 to 200 ms API latency, but it is a hard dependency on every request path, so the fail-open policy is a requirement, not a nicety.
• Local batching of 10 tokens: cuts store traffic about 10x to roughly 50,000 checks/s, which a single node could handle, at the price of bounded overshoot.

See back-of-envelope estimation for the method.

API design

The limiter can be a library embedded in the gateway, or a service with an RPC interface. The service interface:

CheckLimit(request) -> response
  request:  { "client_key": "user:42", "resource": "POST /orders", "cost": 1 }
  response: { "allowed": true|false,
              "limit": 100,
              "remaining": 37,
              "retry_after_ms": 0,
              "reset_after_ms": 4200 }

When the caller is an HTTP gateway, it converts a rejection to:

HTTP/1.1 429 Too Many Requests
Retry-After: 3
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 3

Retry-After is a standard header. The X-RateLimit-* headers are a widespread convention and have no single binding definition, so the units (seconds until reset versus an epoch timestamp) must be documented. See API pagination, idempotency and versioning for error model conventions.

A configuration API manages rules:

PUT /rules/{rule_id}
  { "match": { "resource": "POST /orders", "tier": "free" },
    "algorithm": "token_bucket", "capacity": 20, "refill_per_second": 10 }

Data model

Two kinds of data.

Rules are small, change rarely, and are read constantly. Store them in a durable database or configuration store (a relational table or a key-value store), and have each limiter node load them into memory and refresh them by polling or by pushed updates. A rule change then takes effect within seconds and no request reads the rule database.

Counters are hot, small, and short-lived. Store them in an in-memory key-value store such as Redis, keyed by client key, rule, and (for window algorithms) window ID. Each key has a TTL slightly longer than the rule's window so idle keys are reclaimed automatically. Losing counters on a crash is acceptable: clients briefly get a fresh allowance. See Redis and Memcached.

High-level design

Placement options:

The common design is enforcement in the API gateway, which calls the counter store directly through a small library, and an optional limiter service for internal callers.

flowchart LR
    C[Client] --> GW[API gateway with limiter library]
    GW -->|allowed| S[Backend services]
    GW -->|rejected| R429[429 response]
    GW <--> RC[("Redis cluster: counters")]
    GW -. loads rules .-> RS[(Rules store)]
    AD[Admin API] --> RS

Request flow:

sequenceDiagram
    participant C as Client
    participant G as Gateway
    participant R as Redis shard
    participant S as Service
    C->>G: request with API key
    G->>G: match rule for key and resource
    G->>R: run token bucket script for key
    R-->>G: allowed, remaining
    alt allowed
        G->>S: forward request
        S-->>G: response
        G-->>C: response with X-RateLimit headers
    else rejected
        G-->>C: 429 with Retry-After
    end

The key is hashed to choose a Redis shard, using consistent hashing or Redis Cluster hash slots. All checks for one key reach the same shard, so its state has a single home.

Deep dive

The token bucket check

A token bucket holds up to capacity tokens and gains tokens at a fixed rate. Each request removes one token, and a request that finds no token is rejected. It allows bursts up to capacity and a sustained rate equal to the refill rate. The tokens are computed lazily on each request from the elapsed time, so no background timer runs per key.

The logic, with integer arithmetic to avoid floating-point drift (tokens are stored in thousandths):

public class Main {
    static final class TokenBucket {
        private final long capacityMilli;
        private final long refillPerSec;
        private long tokensMilli;
        private long lastMs;

        TokenBucket(long capacity, long refillPerSec, long nowMs) {
            if (capacity < 1 || refillPerSec < 1) {
                throw new IllegalArgumentException("capacity and refill rate must be at least 1");
            }
            this.capacityMilli = capacity * 1000;
            this.tokensMilli = capacity * 1000;
            this.refillPerSec = refillPerSec;
            this.lastMs = nowMs;
        }

        boolean allow(long nowMs) {
            // refill: elapsed ms x tokens per second = thousandths of a token
            long elapsed = Math.max(0, nowMs - lastMs);
            tokensMilli = Math.min(tokensMilli + elapsed * refillPerSec, capacityMilli);
            lastMs = nowMs;
            if (tokensMilli >= 1000) {
                tokensMilli -= 1000;
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        var bucket = new TokenBucket(5, 2, 0);
        long[] times = {0, 0, 0, 0, 0, 0, 500, 500, 1500, 1500, 1500};
        for (long t : times) {
            System.out.println("t=%4d ms allowed=%b".formatted(t, bucket.allow(t)));
        }
    }
}

t=   0 ms allowed=true
t=   0 ms allowed=true
t=   0 ms allowed=true
t=   0 ms allowed=true
t=   0 ms allowed=true
t=   0 ms allowed=false
t= 500 ms allowed=true
t= 500 ms allowed=false
t=1500 ms allowed=true
t=1500 ms allowed=true
t=1500 ms allowed=false

The bucket starts full with 5 tokens, so five requests at time 0 succeed and the sixth fails. After 500 ms, 1 token has been added (2 tokens per second). After another 1,000 ms, 2 tokens are added.

Atomicity in a distributed setting

With many gateway instances updating the same key, the read-modify-write sequence "read tokens, compute, write tokens" is a race: two instances read the same count and both allow a request that only one token could cover. Options:

1. Atomic increment counters. A fixed window counter counts requests per window (for example per minute) in a key named after the client and the window ID. A sliding window counter combines the counts of the current and the previous window. Both use INCR on a key with a TTL, which is atomic in Redis. Simple, but it supports only counting algorithms.
2. Lua script. Redis executes a script as one uninterrupted operation, and the script reads the bucket, refills, decrements, and writes back. This gives correct token bucket semantics with a single round trip. Because Redis executes commands on one thread, no other command interleaves. Pass the current time as an argument or use the Redis server time so all gateways agree on one clock and their clock skew does not matter.

-- KEYS[1] = bucket key; ARGV = capacity, refill_per_sec, now_ms, ttl_ms
local b = redis.call('HMGET', KEYS[1], 'tokens_milli', 'last_ms')
local tokens = tonumber(b[1]) or (tonumber(ARGV[1]) * 1000)
local last = tonumber(b[2]) or tonumber(ARGV[3])
tokens = math.min(tonumber(ARGV[1]) * 1000,
                  tokens + (tonumber(ARGV[3]) - last) * tonumber(ARGV[2]))
local allowed = 0
if tokens >= 1000 then tokens = tokens - 1000; allowed = 1 end
redis.call('HSET', KEYS[1], 'tokens_milli', tokens, 'last_ms', ARGV[3])
redis.call('PEXPIRE', KEYS[1], ARGV[4])
return allowed

3. Optimistic concurrency (WATCH/MULTI) retries on conflict and performs worse under contention on a hot key.

Do not use a separate GET followed by SET from the application. That is the race described above.

When several rules apply to one request (for example per second and per hour), the request is allowed only if every rule allows it, and a rejected request should not consume tokens from the rules that passed. Evaluate all buckets in one script. In Redis Cluster, a script may only touch keys in the same hash slot, so the keys of one client must share a hash tag (for example {user:42}:sec and {user:42}:hour).

Reducing load on the counter store

A round trip to Redis per request costs latency and throughput. Two mitigations:

• Local pre-aggregation. Each gateway keeps a local allowance for a key, obtained in batches from Redis (for example, 10 tokens at a time), and synchronizes periodically. Latency drops to zero for most requests, at the cost of overshoot: the total allowed can exceed the limit by up to the batch size times the number of gateways. Use small batches for strict limits and larger ones for coarse protection.
• Sticky routing. If the load balancer routes a client's requests to the same gateway (for example by consistent hashing on the API key), each gateway can hold that key's counter locally with no shared store. This breaks when a gateway fails or the cluster resizes, and it skews load if one client is very large.

Numbers for the trade-off: with G gateways each holding a batch of b tokens, worst-case overshoot is G x b. With 100 gateways and b = 10 that is up to 1,000 extra requests, which is negligible against a limit of 100,000 per hour but wrong for a limit of 100 per minute. For small limits, use b = 1 (a Redis call per request) or sticky routing. A fixed-window counter can allow up to 2x the limit across a window boundary (a full burst at the end of one window and again at the start of the next); the sliding window counter estimates the count as previous x (1 - elapsed_fraction) + current, which removes most of that error using two counters and about 16 bytes per key.

Hot tenant: one key at, say, 100,000 requests/s lands on one shard. Split it into k sub-keys (for example k = 8), give each sub-bucket 1/k of the limit, and pick one at random per request. Accuracy drops slightly (a sub-bucket can be empty while another has tokens), so use it only for keys that need it.

Multiple regions

A global limit needs cross-region coordination, which adds tens to hundreds of milliseconds and is unsuitable on the request path. Common approaches: divide the limit statically among regions (each region gets a share), enforce per-region limits with asynchronous synchronization of usage between regions, or route each client to a home region for limiting. Accept some overshoot in exchange for keeping checks local. See multi-region and disaster recovery.

Failure handling

• Redis shard down. Fail open: allow the request and log the failure. Failing closed turns a limiter outage into a full outage. For endpoints where overload is dangerous (expensive queries, login attempts), fall back to a conservative local in-memory limit per gateway instead of unlimited access.
• Timeouts. Set a short timeout on the limiter call (a few milliseconds), and treat a timeout as a failure of the limiter.
• Replication. Replicating counters asynchronously to a replica lets a failover keep approximately correct counts. Loss of a few recent updates only grants small extra allowances.

Failure modes

• Redis shard slow or down. Requests hit a 2 to 5 ms timeout. A circuit breaker (for example open after 5 failures in 1 second, retry probes every 5 seconds) stops gateways from paying the timeout on each call and switches them to a local in-memory limiter. Effects: only the keys on that shard (about 10% of clients) lose global accuracy.
• Failover. An asynchronous replica may lack the last few milliseconds of updates, granting slightly extra tokens. Losing all state (restart with no persistence) resets buckets to full, so clients get one extra burst; this is usually acceptable.
• Rule store down. Gateways keep the last known rules in memory; never block requests on rule fetch.
• Limiter overloaded. Shed load inside the limiter by skipping checks for low-priority keys before the shard saturates, rather than queuing.
• Clock jumps. Pass server time to the script and clamp negative elapsed time to zero so a clock change cannot mint tokens.
• At 10x scale (5 million checks/s): about 100 shards and many more gateways, so local batching becomes necessary, not optional. Adding shards moves keys and resets their counters (brief overshoot); use consistent hashing so only about 1/N of keys move. Memory reaches about 10 GB, still not the constraint.

Bottlenecks and scaling

• Redis throughput. Shard by key across nodes. Watch for one very hot key (a single tenant with very high traffic): its shard cannot be split by key hashing. Local pre-aggregation removes that bottleneck.
• Memory. Use TTLs on all counter keys and store the minimum state (two numbers for a token bucket). The sliding window log stores one entry per request and costs much more memory than a token bucket or sliding window counter.
• Rule lookup. Keep rules in memory on each gateway, keyed for fast matching, with periodic refresh.
• Clock use. Take timestamps from a single source (the Redis server or the script argument passed consistently) to avoid skew between gateways.
• Observability. Export counters for allowed and rejected requests per rule, and the limiter's own latency and error rate. A sudden rise in rejections can indicate an attack or a misconfigured rule.

Trade-offs and follow-up questions

• Which algorithm? Token bucket allows bursts and uses little memory. The leaky bucket smooths output to a constant rate. The sliding window counter approximates a true sliding window with two counters and low memory. The sliding window log is exact but memory-heavy. See rate limiting algorithms.
• Where to limit? At the edge to protect the platform, and again per service to protect each service from its own callers.
• Hard or soft limits? A hard limit rejects at once. A soft limit can degrade (queue, lower priority) before rejecting.
• What identifies a client? API keys and user IDs are reliable. IP addresses misidentify clients behind shared NAT and are easy to rotate. Combine several keys for abuse protection.
• How to handle bursts of legitimate traffic? Increase the bucket capacity, keeping the refill rate at the sustainable average.
• What if the limit is 1 request per second and there are 100 gateways? Local batching cannot work at that granularity; use a shared counter per request or sticky routing so that each key has one owner.
• How do you rate limit by cost rather than count? Deduct a variable number of tokens per request (for example 1 for a read, 10 for an export), using the same script with a cost argument.
• What about login attempts and password guessing? Limit per account and per IP together, and fail closed or fall back to strict local limits, since failing open helps an attacker.
• How do you roll out a new rule safely? Run it in shadow mode first: evaluate and log would-be rejections without enforcing, compare with expected traffic, then enforce.
• How should clients react to 429? Honor Retry-After and use exponential backoff with jitter. See timeouts, retries, backoff and jitter.