Designing an API Rate Limiter
High Level Design·intermediate·~25 min read
- system-design
- rate-limiter
- api-design
- distributed-systems
- hld
What you'll learn
1. Problem Statement and Requirements
What Is a Rate Limiter?
A rate limiter is a mechanism that restricts the number of requests a client can send to an API within a specified time window. It acts as a gatekeeper, protecting backend infrastructure from being overwhelmed and ensuring equitable acce…
Functional Requirements
- Accurately limit requests based on configurable thresholds (e.g., 100 requests/minute) - Support multiple limiting criteria: user ID, API key, IP address, endpoint - Return informative responses when limits are exceeded (HTTP 429 + hea…
Non-Functional Requirements
- Low latency: Adding rate limiting should not significantly increase API response time ( Parameters to configure: - Bucket capacity (C): Maximum burst size. Setting C = 100 allows 100 requests in rapid succession. - Refill rate (R): Sus…
3.2 Leaky Bucket
Produces a perfectly smooth output rate, regardless of input burstiness. Mechanism: 1. Requests enter a FIFO queue with a fixed maximum length 2. Requests are dequeued and processed at a constant rate 3. If the queue is full when a new r…
3.3 Fixed Window Counter
The simplest algorithm but with a known vulnerability. Mechanism: 1. Divide time into fixed-duration windows (e.g., every 60 seconds: 0:00-0:59, 1:00-1:59, ...) 2. Maintain a counter for each window 3. Increment the counter with each req…
3.4 Sliding Window Log
Provides mathematically precise rate limiting by tracking individual request timestamps. Mechanism: 1. Store the timestamp of every request in a sorted log (per client) 2. When a new request arrives: a. Remove all entries older than curr…
Component Breakdown
1. API Gateway: Entry point; extracts client identity (API key, JWT, IP) 2. Rate Limiter Middleware: Checks current usage against configured limits 3. Redis Cluster: Stores real-time counters/buckets; shared across all server instances 4…
Request Flow
---
Design Evolution & Trade-offs
How this system grew from an MVP to what a production version looks like -- and the choices you'd defend in an interview. Rate limiters look deceptively simple in the small: a counter, a threshold, a 429. What makes them genuinely hard i…
Stage 1 -- MVP: One box, one database
The simplest thing that could possibly work for api-rate-limiter. - A single API server (monolith) with an in-process rate-limit middleware. - A single relational database (Postgres or MySQL) holding user identity and tier metadata. - Co…
Stage 2 -- Scale-out: Multiple pods behind a load balancer
- API layer becomes stateless; N replicas behind an L7 load balancer. - Rate-limit counters have to move out of process memory -- otherwise each pod enforces its own independent limit and a client hitting 3 pods gets 3x the allowed rate.…
Stage 3 -- Bottleneck: Distributed counter accuracy under concurrency
This is the defining bottleneck of any real rate limiter. Once you have N stateless pods, every counter update becomes a distributed compare-and-swap problem. Get it wrong and your published SLA is a lie. The failure isn't rare -- for a…
Stage 5 -- Mature architecture
Everything from Stages 2-4 stitched together, plus the operational scaffolding you need to run this in anger. Key properties of this architecture: - Cache hits skip the limiter entirely (via CDN). Rate limits only exist to protect scarce…
Cost vs Complexity -- When to Pick What
| Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Counter store | In-process map | Managed Redis single node | Redis Cluster (sharded by userid) | | Algorithm | Fix…
Migration Path (MVP -> Enterprise)
A stepped list -- how to migrate a live rate limiter without dropping requests or over-limiting real users. Each step is independently deployable; you do not have to do them all at once, and later steps depend on earlier ones being stabl…
5. Placement Options
Option A: At the API Gateway
Best for: Microservices architectures where you want uniform policy enforcement. Advantages: - Single enforcement point - No changes needed in individual services - Centralized monitoring and configuration - Gateway products (Kong, Nginx…
Option B: Application-Level Middleware
Best for: Monolithic applications or when limits depend on business logic. Advantages: - Full control over limiting logic - Can implement complex per-endpoint or per-operation rules - Can consider request context (e.g., limit writes more…
Option C: Sidecar / Service Mesh
Best for: Kubernetes/service mesh deployments where infrastructure handles cross-cutting concerns.
6. Distributed Rate Limiting -- Deep Dive
The Challenge
With N application servers, each server independently cannot know the global request count. Without coordination:
Solution: Centralized State with Redis
All servers query and update a single Redis instance (or cluster) that maintains the true count.
Race Condition Prevention
Problem: Two requests arrive simultaneously at different servers: Concrete example: Two concurrent requests arrive with count=2 and limit=3. Both read count=2, both see 2 protection Fail-Closed (restrictive): - If Redis is unreachable, r…
Monitoring and Alerting
Track these metrics: - Rate limit hit rate per client/endpoint - Redis latency (p50, p95, p99) - Percentage of requests rejected - Clients consistently hitting limits (potential abuse or misconfiguration) - Redis memory utilization
10. Timer Wheel Algorithm
A specialized data structure for managing large numbers of timed requests efficiently. It is a variant of Token Bucket optimized for distributed systems where each API has a timeout-based window.
Concept
A timer wheel is a circular buffer where: - The wheel size equals the timeout duration (e.g., 60 seconds = 60 slots) - Each slot has a maximum capacity (max requests allowed per time unit) - A pointer advances with time, one slot per sec…
How Requests Flow
1. New request arrives at time T 2. Calculate target slot: slot = T % wheelsize 3. Check if slot has capacity: slot.count < maxcapacityperslot 4. If yes → add request to slot, return ALLOW 5. If no → return REJECT (RateLimitExceededExcep…
Eviction (Automatic)
Hierarchical Timer Wheel
For APIs with very long timeouts (hours or days), a single wheel would need thousands of slots. Solution: nested wheels at different granularities.
Capacity Estimation for Timer Wheel
Assuming: - 100 services, 30 APIs per service - Average timeout per API: 1 minute (= 60 buckets) - 10 requests/second/API average - 8 bytes per request ID
Why Timer Wheel Over Other Approaches
| Approach | Add Request | Evict | Memory | |----------|:-----------:|:-----:|:------:| | Sorted timestamp list | O(log N) | O(N) scan | Unbounded | | Timer Wheel | O(1) | O(1) amortized | Fixed | | Hash + TTL | O(1) | O(1) per key | Var…
11. The Oracle Pattern (Centralized Rate Limiting)
In a microservices architecture, instead of each service implementing its own rate limiting, a centralized Oracle service makes the allow/deny decision.
Architecture
Registration Flow
Each service registers with the Oracle on startup: - Service name and IP addresses - Per-API capacity configuration (max requests, time duration, per-client max) - Fallback strategy (throttle new requests / dump oldest / split queue) - H…
Oracle API Contract
Benefits
1. Single source of truth — no conflicting rate limit decisions across services 2. Global visibility — can enforce cross-service limits (e.g., total platform rate) 3. Centralized configuration — change limits without redeploying services…
12. Handling Bad Actors
Queue Partitioning
Partition incoming requests into sub-queues based on hash(requesterid) % numbuckets: Problem: A new legitimate requestor might hash to the same sub-queue as a bad actor and get throttled unfairly. Solution: Use hierarchical hashing — fir…
13. Real-Life Optimizations
Request Collapsing
When multiple identical requests arrive simultaneously (e.g., "average salary for company X"), deduplicate them: Request Batching (rare but powerful): Wait briefly for similar but different requests, then batch them into a single databas…
Client-Side Rate Limiting
Clients should implement their own retry logic based on server responses: Error Classification: - Permanent errors (4xx): Don't retry. Fix the request (wrong password, invalid format). - Temporary errors (5xx, 429): Retry with backoff.
Exponential Backoff
When a client receives a rate limit rejection: The cap prevents unbounded wait times. The threshold prevents infinite retries. With jitter: Add random variance to prevent thundering herd:
14. Backpressure
Backpressure occurs when a downstream service cannot process requests as fast as an upstream service sends them.
Strategies
| Strategy | How It Works | When to Use | |----------|--------------|-------------| | Control the Producer | Tell upstream to slow down | When you can communicate with the producer | | Buffer | Accumulate temporarily in a bounded queue |…
Key Principles
1. Buffers must be bounded — unbounded buffers are a common source of memory crashes 2. Monitor queue depth — rising queue depth signals backpressure 3. Dead letter queues — failed/expired requests go to a separate queue for analysis 4.…
Detecting Load Problems
| Metric | What Rising Value Means | |--------|------------------------| | Average response time | Service is overloaded or down | | Age of messages in queue | Processing is falling behind | | Dead letter queue size | Service is failing…
15. Memory Benchmarks
Understanding the memory footprint of each algorithm is critical when designing for scale: | Algorithm | Memory (1M users) | Notes | |-----------|-------------------|-------| | Fixed Window | ~32 MB | ~20-byte overhead per user (counter…
Redis Sorted Set Internals
The sliding window implementation using Redis sorted sets relies on ZREMRANGEBYSCORE for atomic range removal of expired entries. Internally, Redis sorted sets use a dual-ported data structure: a skip list for ordered traversal and a has…
IPv6 Memory Exhaustion Attack
When rate limiting is based on IP addresses, attackers can exploit IPv6 to exhaust server memory. A single machine with a /64 IPv6 prefix has access to 2^64 unique addresses. An attacker can rotate through massive numbers of IPv6 address…
Multi-Layer Rate Limiting Pattern
For extremely high-throughput systems, a layered approach minimizes latency: How it works: 1. Each application server maintains a local Bloom filter of recently rate-limited keys 2. Incoming requests are first checked against the Bloom f…
Write-Back Cache Strategy for Rate Limiting
To minimize per-request latency, use a write-back (write-behind) caching pattern: Approach: - All counter reads and writes hit the in-memory cache exclusively - A background process flushes accumulated counter values to persistent storag…
Revenue and Monetization
Rate limiting is not purely a defensive mechanism -- it can serve as a monetization tool. By establishing default limits on free tiers and offering progressively higher limits on paid plans, the rate limiter becomes part of the product's…
16. Advanced Considerations
Rate Limiting with Caching Layers
Weighted Rate Limiting
Not all requests are equal: - GET requests: cost 1 token - POST requests: cost 5 tokens - File upload: cost 20 tokens - Expensive queries: cost 10 tokens
Rate Limiting in Multi-Region Deployments
Options: 1. Per-region limits: Each region enforces independently. Simple but user can get Nx the global limit. 2. Global limits with local caching: Periodically sync counters across regions. Slightly imprecise but practical. 3. Single g…
Client-Side Best Practices
Well-behaved clients should: 1. Respect Retry-After headers 2. Implement exponential backoff on 429 responses 3. Monitor X-RateLimit-Remaining to preemptively slow down 4. Queue requests locally when approaching limits
11. Complete System Design Summary
Key Design Decisions: 1. Algorithm: Token Bucket for most use cases (allows bursts, memory efficient) 2. Placement: API Gateway for uniformity + per-service middleware for custom logic 3. Storage: Redis cluster with Lua scripts for atomi…