System Design: [Rate limiter name]

Reference design for a distributed rate limiter that protects APIs from overload and abuse and enforces per-customer quotas. It compares token bucket, leaky bucket, fixed window and sliding window algorithms, specifies a Redis-based implementation with atomic scripts, discusses multi-region limits, response headers (Retry-After and the IETF RateLimit header fields draft) and the fail-open versus fail-closed decision. It follows the structure of the System Design Document template and is pre-filled with a worked design to adapt. Values marked Example are assumptions.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Each API instance limits clients in local memory, so a client spread across 40 instances gets 40 times its quota. A single customer's batch job caused a 25-minute brownout last month, and paid tiers cannot be enforced reliably.]

1.2 Proposed solution

[Example: The API gateway calls a rate-limit module on every request. The module identifies the client (API key, user, or IP for anonymous traffic), looks up the policy, and runs an atomic token-bucket script in a sharded Redis cluster in the same region. Rejected requests get HTTP 429 with Retry-After and RateLimit headers. A small in-process cache blocks keys that are already exhausted without calling Redis. If Redis is unavailable, the gateway fails open for quota limits and falls back to coarse local limits for protection.]

1.3 Decisions requested from reviewers

2. Requirements

2.1 Functional requirements

2.2 Non-functional requirements

2.3 Out of scope

• [Example: billing for overage usage (separate metering pipeline)]
• [Example: volumetric DDoS protection at layers 3 and 4 (handled by the edge provider)]
• [Example: concurrency limits on long-running jobs]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Redis operations

Without a local cache every policy check is one script call:

The local deny cache (7.4) and batching of the two policies into one script call reduce this to one call per request, about $10^{6}$/s globally, or per region:

The factor 1.5 keeps headroom for uneven slot distribution; 8 is chosen as the next power of two for even resharding.

3.3 Memory

Keys expire when idle (TTL equal to the time to refill the bucket plus one second), so memory follows active keys, not all keys ever seen. With one replica per primary the cluster holds about 9.6 GB per region.

3.4 Latency

A same-zone Redis round trip is typically 0.2 to 0.5 ms; the script itself runs in microseconds. With a 2 ms budget there is room for one round trip and a timeout of 5 ms after which the request falls back (7.6).

3.5 Summary

4. API design

4.1 Interfaces

The limiter is an in-process library in the gateway plus an admin API for policies.

4.2 Response headers

Every response carries the current quota state; a rejected request also gets Retry-After (RFC 9110) with status 429 (RFC 6585). The RateLimit fields below follow the structured-field syntax of the IETF httpapi working group draft; the syntax has changed between draft revisions, so pin the revision you implement and say so in your API documentation.

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 3
RateLimit-Policy: "burst";q=100;w=1, "daily";q=50000;w=86400
RateLimit: "burst";r=0;t=3

{"type": "https://api.example.com/problems/rate-limited", "title": "Rate limit exceeded", "status": 429, "detail": "Policy 'burst' allows 100 requests per second for this key.", "instance": "/v1/orders"}

4.3 Policy format

Policies are versioned JSON documents managed through the admin API; a new version starts in shadow mode unless the reviewer sets enforce:

{"id": "pro-default", "version": 7, "match": {"tier": "pro", "routes": ["/v1/*"]}, "algorithm": "token_bucket", "rate_per_sec": 100, "burst": 200, "cost": {"POST /v1/exports": 10}, "on_store_failure": "open", "mode": "enforce"}

5. Data model

5.1 Entities

Policies and overrides are configuration; buckets are short-lived counters.

5.2 Storage choices

Keys use a hash tag on the subject (rl:{key_8f2a}:burst) so all policies for one subject land on the same slot and can be checked in one script call.

6. High-level design

The decision is made inside the gateway; only the bucket state is remote.

7. Detailed design

7.1 Policies

7.2 Algorithms compared

Token bucket, with refill rate $r$ tokens per second and capacity $b$:

Sliding window counter estimate for window length $w$ and elapsed time $e$ in the current window:

For example with $w = 60$ s, $e = 15$ s, $n_{prev} = 80$, $n_{curr} = 30$: $\hat{n} = 30 + 80 \times 0.75 = 90$, so a limit of 100 allows 10 more.

7.3 Atomic Redis script

Read, refill, decide and write must be one atomic step, otherwise two gateways can both read 1 token and both allow. The script uses Redis server time so gateway clock skew cannot mint tokens.

-- KEYS[1] = bucket key; ARGV = rate_per_sec, burst, cost
local rate  = tonumber(ARGV[1])
local burst = tonumber(ARGV[2])
local cost  = tonumber(ARGV[3])
local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1]) or burst
local ts = tonumber(data[2]) or now
tokens = math.min(burst, tokens + math.max(0, now - ts) / 1000 * rate)
local allowed, retry_ms = 0, 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) / rate * 1000)
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(burst / rate * 1000) + 1000)
return {allowed, math.floor(tokens), retry_ms}

The sequence for one request on the critical path:

Retry-After is in whole seconds, so 1 200 ms rounds up to 2.

7.4 Local deny cache and hot keys

A client hammering after rejection would otherwise cost one Redis call per request and concentrate load on one slot. The gateway remembers rejected keys until their retry time and rejects locally. Over-admission is bounded: a key that becomes allowed again is checked in Redis on its next request.

7.5 Multi-region and consistency model

• Per region, strongly consistent: each region's Redis is the single source of truth for its buckets; the script is atomic, so within a region the limit is exact (NFR-02).
• Globally, approximate: each region enforces a share of the global limit, initially $L_{global}/n$. Every 10 s regions publish observed usage per key to the others and shares are rebalanced toward where traffic is. A client that moves all traffic to one region may be under-served for up to one rebalance interval; one that spreads evenly gets the full limit.
• Daily quotas use fixed-window counters replicated asynchronously; the worst-case overshoot is the traffic served during replication lag, which is accepted for non-billing quotas. Billing-grade quotas are reconciled from metering, not from the limiter.

7.6 Fail-open versus fail-closed

A circuit breaker opens after 50% errors over 10 s so failing calls stop adding latency; it probes again after 5 s.

8. Scalability and performance

Latency budget for the limiter step (target p99 2 ms):

9. Reliability, security and operations

9.1 Failure modes

9.2 Security and abuse

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Every new policy starts in shadow mode for 7 days. Enforcement is enabled per tier with a feature flag; rollback sets the policy mode back to shadow, which takes effect within 60 s.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Standard and licence note

Based on common industry practice for distributed rate limiting and on the HTTP specifications cited in 12.3; the RateLimit header fields are an IETF draft, not a published RFC. This is a reference design to adapt, with illustrative numbers. Original text written for this collection. Template licence: MIT.