System Design · 22 min read
System Design: How to Design an API Rate Limiter (Token Bucket vs Leaky Bucket)
This guide explores a distributed API rate limiter design, including Token Bucket, Leaky Bucket, Sliding Window Counter, synchronization across gateways, Redis scripting, capacity estimation, and failure-mode trade-offs.
Published by PrepVisor · Guide publisher · Updated 2026-09-20
Quick Answer
An API rate limiter controls request volume by client, IP, or endpoint. For distributed gateways, a Token Bucket backed by Redis can allow controlled bursts. Place checks at the API Gateway and use atomic Redis Lua updates to avoid race conditions. When a limit is exceeded, return HTTP 429 with Retry-After; choose fail-open or fail-closed behavior for outages based on system priorities.
Key Takeaways
- Clarify whether limits apply globally, per user, per IP, or per endpoint.
- Token Bucket permits controlled bursts; Leaky Bucket smooths output at a constant rate.
- Place rate limiting at the API Gateway to reject throttled traffic before it consumes backend resources.
- Use atomic Redis Lua scripts to avoid check-then-act races across gateway servers.
- Choose fail-open or fail-closed behavior deliberately, and use Redis server time where token refill depends on time.
1. Functional & Non-Functional Requirements
Clarifying limits, granularity, and failure modes
Before architecting a rate limiter, clarify the limit granularity and failure behavior. The numerical limits below are EXAMPLE / ASSUMPTION values for discussion, not universal tiers or measured service requirements.
Functional Requirements:
- Granular Rate Limiting: Limit requests based on client identifier (authenticated user ID, API token) or IP address for unauthenticated traffic.
- Configurable Tiers: Support multiple rate limiting tiers (e.g. Free Tier: 100 req/min; Enterprise: 5,000 req/min; Login Endpoint: 5 attempts/min to prevent brute-force attacks).
- Informative HTTP Headers (design choice): Consider documenting quota and reset headers (for example,
X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset) for clients. - Graceful Throttling: When limits are breached, return HTTP 429 (Too Many Requests); RFC 6585 permits a
Retry-After header indicating how long to wait.
Non-Functional Requirements:
- Latency target (example): A scenario might set an overhead target of 2 to 3 milliseconds; define the measurement boundary and percentile.
- Availability target (example): A scenario might specify 99.999% availability; this is a target, not a guarantee.
- Distributed State Synchronization: Support hundreds of edge API gateway nodes querying a distributed, consistent token store.
- Memory efficiency (example scale assumption): A scenario could ask the design to track hundreds of millions of active IP addresses and user accounts; estimate state from the chosen key and data representation, then validate it against deployment limits.
2. Algorithm Comparison: Token Bucket vs Leaky Bucket vs Sliding Window
Selecting a rate-limiting algorithm for the workload
Compare rate-limiting algorithms against the traffic shape, state model, and failure requirements of the system being designed:
1. Token Bucket
- Mechanism: A bucket holds up to a maximum of $b$ tokens. Tokens are continuously added at a fixed rate of $r$ tokens per second. Each incoming request consumes 1 token. If the bucket is empty, the request is dropped (or throttled).
- Burst Behavior: Allows controlled bursts. If the bucket is full, up to $b$ requests can be processed immediately in a single instant.
- Memory Footprint: Extremely compact ($O(1)$ space). You only need to store two numbers per user: the remaining token count and the last refill timestamp.
2. Leaky Bucket (Traffic Shaping)
- Mechanism: Incoming requests enter a FIFO queue of fixed capacity. Requests are pulled from the queue and processed at a constant, fixed rate (the 'leak'). If the queue is full, incoming requests overflow and are discarded.
- Burst Behavior: Zero burst tolerance. Flattens traffic spikes into a smooth, steady output stream.
- Trade-off: Not ideal for general user-facing APIs where bursty web traffic is normal. However, it is ideal for egress traffic shaping when calling downstream legacy services that cannot tolerate sudden spikes.
3. Fixed Window Counter
- Mechanism: Divides time into fixed windows (e.g. 1 minute from 12:00 to 12:01). A counter increments with each request.
- The Boundary Burst Trap: A client can send 100 requests at 12:00:59 and another 100 requests at 12:01:01. In a 2-second interval, 200 requests were processed, doubling the intended rate limit!
4. Sliding Window Log
- Mechanism: Stores the epoch timestamp of every request in a sorted set (such as Redis ZSET). When a request arrives, all timestamps older than
now - window_size are purged, and the remaining elements are counted. - Trade-off: Tracks requests in the configured rolling window without the fixed-window boundary approximation, but uses $O(N)$ state for the requests in that window. Size and protect the state store for the expected workload.
5. Sliding Window Counter (weighted estimate)
- Mechanism: Combines the fixed window of the previous interval and the current interval using a weighted formula:
$\text{Estimated Count} = \text{Previous Window Count} \times (1 - \text{elapsed fraction}) + \text{Current Window Count}$
- Trade-off: Uses constant state per client for a fixed number of windows and estimates usage across a boundary. Accuracy depends on traffic distribution and assumptions; no universal error rate is implied here.
3. High-Level Architecture & Gateway Placement
Where should the rate limiter live in the infrastructure?
In a modern microservices architecture, placing the rate limiter in individual application services causes duplication and wastes application CPU cycles.
Recommended Topology: Edge API Gateway with Distributed Cache
- Client Request: The mobile app or third-party client makes an HTTPS call to
api.prepvisor.in. - Reverse Proxy / API Gateway: A selected gateway can terminate TLS, authenticate JWTs or API keys, and extract the client identifier.
- Rate Limiter Middleware: Before routing to backend microservices, the gateway queries an in-memory distributed cache cluster (Redis Cluster).
- Decision Evaluation:
- Allowed: Gateway appends headers (
X-RateLimit-Remaining: 42) and proxies the request to the upstream target service. - Throttled: Gateway immediately short-circuits with HTTP 429 Too Many Requests, payload
{"error": "rate_limit_exceeded", "retry_after": 6}, saving backend compute.
4. Distributed Concurrency & The Race Condition Trap
Why naive GET + SET fails and Redis Lua scripts provide atomic execution
A useful concurrency question is: "What happens when two concurrent requests arrive at different gateway servers simultaneously?"
The Race Condition Trap (Check-then-Act)
Suppose a user has 1 token remaining.
- Server A receives Request 1, calls
GET user:123, and reads tokens = 1. - Server B receives Request 2, calls
GET user:123, and also reads tokens = 1. - Server A calculates
tokens - 1 = 0 and writes SET user:123 tokens=0. - Server B calculates
tokens - 1 = 0 and writes SET user:123 tokens=0.
Result: Both requests can succeed even though only 1 token was available. Under a high-throughput workload (for example, an assumed 50,000 requests/second), the race can cause quota overruns.
The Solution: Redis Lua Scripts
Redis guarantees atomic script execution: while a script runs, other server activity is blocked. Keep scripts short because they occupy the server during execution. The following is an illustrative Token Bucket script, not a production-ready implementation. Redis scripting documentation
Illustrative Redis Lua Script for an Atomic Token Bucket Update-- KEYS[1]: rate limit key (e.g., "ratelimit:user_12345")
-- ARGV[1]: bucket capacity (e.g., 100)
-- ARGV[2]: refill rate per second (e.g., 10 tokens/sec)
-- ARGV[3]: requested tokens (e.g., 1)
-- ARGV[4]: current server epoch timestamp in seconds
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local requested = tonumber(ARGV[3])
local now = tonumber(ARGV[4])
-- Retrieve current bucket state: [tokens, last_refill_time]
local data = redis.call("HMGET", key, "tokens", "last_refill")
local current_tokens = tonumber(data[1])
local last_refill = tonumber(data[2])
if current_tokens == nil then
-- Bucket does not exist yet; initialize to full capacity
current_tokens = capacity
last_refill = now
else
-- Calculate tokens accumulated since last request
local elapsed = math.max(0, now - last_refill)
local generated_tokens = elapsed * refill_rate
current_tokens = math.min(capacity, current_tokens + generated_tokens)
last_refill = now
end
-- Evaluate if sufficient tokens exist
if current_tokens >= requested then
current_tokens = current_tokens - requested
redis.call("HMSET", key, "tokens", current_tokens, "last_refill", last_refill)
-- Set TTL to allow automatic cleanup of inactive keys (e.g. 1 hour)
redis.call("EXPIRE", key, 3600)
-- Return [1 = allowed, remaining_tokens, retry_after_seconds = 0]
return { 1, math.floor(current_tokens), 0 }
else
-- Rate limited; calculate seconds until next token is available
local missing = requested - current_tokens
local retry_after = math.ceil(missing / refill_rate)
-- Persist state with updated refill timestamp
redis.call("HMSET", key, "tokens", current_tokens, "last_refill", last_refill)
redis.call("EXPIRE", key, 3600)
-- Return [0 = denied, remaining_tokens = 0, retry_after_seconds]
return { 0, 0, retry_after }
end
5. Capacity Estimation & Redis Memory Sizing
Back-of-the-envelope capacity calculation (example assumptions)
EXAMPLE / ASSUMPTION — The following values are hypothetical inputs for demonstrating a sizing method, not observed user counts, Redis object sizes, or benchmark results.
Assumptions:
- Total User Base: 100 Million registered accounts.
- Daily Active Users (DAU): 10 Million users.
- Average QPS: 10,000 requests/second.
- Peak Burst QPS: 50,000 requests/second.
Redis Memory Footprint per Client Key:
- Key:
"rl:usr:10008492" $\approx$ 16 bytes. - Fields:
tokens (8-byte double/int) + last_refill (8-byte epoch int) $\approx$ 16 bytes. - Redis Internal Hash Overhead: Hash entry overhead, dict pointers,
robj metadata, and jemalloc chunk alignment $\approx$ 32 bytes. - Total per Key: $\approx 64\text{ bytes}$.
Total Memory for Active Working Set:
- If tracking all 100 Million users simultaneously:
$100{,}000{,}000 \times 64 \text{ bytes} = 6{,}400{,}000{,}000 \text{ bytes} \approx 6.4 \text{ GB}$
- Interpretation: The simple estimate is 6.4 GB of payload under these assumptions. Redis overhead, allocator behavior, replication, and headroom are omitted, so this arithmetic does not establish a suitable node size.
Network Bandwidth:
- $50{,}000 \text{ QPS} \times 150 \text{ bytes per Lua payload} \approx 7.5 \text{ MB/sec}$.
- $7.5 \text{ MB/sec} = 60 \text{ Mbps}$ at the assumed inputs, excluding protocol overhead; network suitability depends on the deployment and competing traffic.
6. Edge Cases, Multi-Tier Limits & Failover Resilience
Bulletproofing against DDoS, clock drift, and cache outages
Discuss operational resilience and failure modes explicitly:
1. The Clock Skew Problem
In distributed environments, server system clocks drift by milliseconds (NTP synchronization skew). If API Gateways pass their local machine timestamp to Redis, race conditions and negative time deltas can corrupt token refills.
- One option: Use Redis
TIME within the script to obtain a timestamp from the Redis server handling that operation. This avoids comparing gateway-supplied timestamps for the operation; it does not synchronize clocks across Redis nodes. Redis TIME command
2. Multi-Tier Rate Limiting Defense
A single rate limiter cannot solve all security and operational problems. Employ a multi-tier defense:
- L1 Edge Protection: An edge provider or managed DDoS protection service may filter traffic before it reaches the application network.
- L2 API Gateway Rate Limiting (Token Bucket in Redis): Per-user and per-API-key quotas to enforce billing plans.
- L3 Service-Level Circuit Breakers: Protect internal databases and microservices from cascading failures if a specific endpoint experiences unexpected load.
3. Cache Outage: Fail-Open vs Fail-Closed
What happens if the Redis cluster crashes or network partitions occur?
- Fail-Closed: Reject requests when the limiter is unavailable; this preserves the configured limit but may deny legitimate requests.
- Fail-Open: Allow requests when the limiter is unavailable; this favors availability but can expose downstream services to excess traffic. Choose per endpoint and risk model.
References & Further Reading
Frequently Asked Questions
What is the primary difference between Token Bucket and Leaky Bucket?
Token Bucket can allow bursts up to its configured capacity while enforcing a longer-term refill rate. A Leaky Bucket can smooth output when paired with a queue; exact behavior depends on implementation and configuration.
How do you prevent race conditions in a distributed rate limiter?
Separate Redis GET and SET operations can interleave and create check-then-act races. A short Redis Lua script can perform the check and update atomically; Redis blocks other server activity while the script runs. See Redis scripting documentation.
Where can a rate limiter be positioned in a microservice architecture?
An edge gateway can reject requests before they consume application resources. Service-level limits may also be useful for internal calls or specific resources; place controls according to the threat model and architecture.
What HTTP status code and response headers should be returned when rate limited?
HTTP 429 indicates that the client has sent too many requests; RFC 6585 says a response may include Retry-After. Other rate-limit headers are design choices and should be documented consistently by the API.
Should a rate limiter fail open or fail closed during a Redis outage?
Choose fail-open or fail-closed behavior per endpoint. Fail-open favors availability but can expose downstream services to excess traffic; fail-closed preserves the limit but can reject legitimate traffic during an outage.
How do you handle clock drift across distributed rate limiting servers?
Redis TIME returns the current time from the Redis server handling the command. It avoids relying on a gateway-provided timestamp for that operation, but it does not establish globally synchronized time across servers.