System Design — Design a Rate Limiter

In a network system, a Rate Limiter controls the rate of traffic sent by a client or a service. In HTTP APIs, it limits the number of client requests allowed to be sent over a specified time period (e.g., 100 requests per minute). If the request count exceeds the defined threshold, all further excess calls are blocked or throttled with an HTTP 429 (Too Many Requests) response.

1. Why Do We Need a Rate Limiter?

Prevent Denial of Service (DoS / DDoS) Attacks: Prevents malicious actors or buggy clients from flooding servers with continuous requests, starving legitimate users.
Reduce Cost: Enforces usage quotas on paid third-party APIs (e.g., OpenAI, Stripe, Google Maps, Twilio) where extra API calls directly increase billing.
Prevent Server Overload: Protects database connection pools, memory, and backend services from sudden traffic spikes.
Fair Resource Allocation: Ensures multi-tenant systems distribute bandwidth and compute resources equally without a few heavy users starving others.

2. System Scope & Requirements

Functional Requirements:

Accurately limit excessive requests based on IP address, User ID, or API Token.
Return clear HTTP status code 429 (Too Many Requests) with standard rate-limit headers when throttled.
Support configurable rate-limiting rules across different API endpoints (e.g., /login vs /posts).

Non-Functional Requirements:

Ultra-Low Latency: The rate limiter must not introduce measurable overhead to API requests (< 2–5 ms).
Distributed & Scalable: Must work reliably across a distributed cluster of application servers.
Fault Tolerance: If the rate limiter service or cache goes down, it should gracefully fail-open without blocking user traffic.
High Concurrency & Thread Safety: Prevent race conditions in high-throughput environments.

3. Where to Place the Rate Limiter?

Option A: Client-Side (Unreliable ❌)
[ Client App ] ─── (Easy to bypass, manipulate, or forge) ───> [ Server ]

Option B: Server-Side Application Layer (Mixed ⚠️)
[ Client ] ────────> [ App Server (Rate Limiter Filter inside App) ] ───> [ DB ]

Option C: API Gateway / Middleware (Recommended ✅)
[ Client ] ────────> [ API Gateway / Reverse Proxy (Rate Limiter) ] ───> [ Microservices ]
                                  │
                                  ▼
                         [ In-Memory Store (Redis) ]

Placement	Pros	Cons	Verdict
Client-Side	Saves bandwidth by stopping calls at source	Easily tampered with or bypassed by malicious actors	❌ Not recommended
App Server	Direct control in code; custom business logic	Coupled to app code; consumes app compute; hard to reuse	⚠️ Only for small monoliths
API Gateway / Middleware	Centralized enforcement, decoupled, handles SSL & auth before reaching services	Additional architectural component to manage	✅ Industry standard (Cloudflare, Kong, AWS API Gateway)

4. In-Memory Store: Why Redis?

Disk-based databases (e.g., PostgreSQL, MySQL) are too slow for rate limiting because every single API call requires a read and write.

Redis is the preferred choice because:

Operates entirely in RAM, providing sub-millisecond lookups.
Native support for fast atomic operations (INCR, EXPIRE, ZADD, ZREMRANGEBYSCORE).
Built-in Time-To-Live (TTL) support for automatic counter expiration.

5. Rate Limiting Algorithms Deep Dive

There are 5 primary algorithms used for rate limiting. Each comes with distinct trade-offs:

┌──────────────────────────────┬───────────────────────────────┬───────────────────────────────┐
│ Algorithm                    │ How It Works                  │ Best For                      │
├──────────────────────────────┼───────────────────────────────┼───────────────────────────────┤
│ 1. Token Bucket              │ Refills tokens at fixed rate  │ Bursty traffic (Stripe, AWS)  │
│ 2. Leaky Bucket              │ Drips requests at steady rate │ Smooth egress rate (Shopify)  │
│ 3. Fixed Window Counter      │ Counts requests in time slice │ Simple memory-efficient limit │
│ 4. Sliding Window Log        │ Stores timestamp of each call │ Strict 100% precision         │
│ 5. Sliding Window Counter    │ Blends current & past windows │ Low-memory smooth limiting    │
└──────────────────────────────┴───────────────────────────────┴───────────────────────────────┘

1. Token Bucket Algorithm

Widely used by tech leaders like Stripe and Amazon Web Services (AWS).

                   Refill Rate: 4 tokens / second
                              │
                              ▼
                 ┌─────────────────────────┐
                 │  Token Bucket           │
                 │  (Capacity = 4)         │
                 │  [●] [●] [●]            │
                 └────────────┬────────────┘
                              │
         Incoming Request     │ 1 Token Available?
                 ─────────────┼──────────────────────────────┐
                              │                              │
                             YES                             NO
                              ▼                              ▼
                       [ Consume Token ]               [ Drop Request ]
                       [ Forward to API]               [ HTTP 429 Error ]

How it works:

A bucket has a fixed maximum Capacity (e.g., 10 tokens).
A refiller adds tokens to the bucket at a constant Refill Rate (e.g., 2 tokens per second).
If the bucket is full, extra refilled tokens overflow and are discarded.
Each request requires 1 token to pass:
- If tokens are available $\ge 1$ , 1 token is removed, and the request is processed.
- If tokens $= 0$ , the request is dropped (HTTP 429).

Pros: Easy to implement, memory-efficient (stores only integer count & timestamp), allows short bursts of traffic as long as tokens are in the bucket.
Cons: Tuning parameters (Bucket Size vs Refill Rate) can be challenging.

2. Leaky Bucket Algorithm

Used by platforms like Shopify to produce a constant, predictable output rate.

       Incoming Requests (Bursty)
       ▼   ▼       ▼   ▼   ▼
     ┌────────────────────────┐
     │  Queue / Bucket        │
     │  (Capacity = 5 reqs)   │
     │  [Req 3][Req 2][Req 1] │
     └───────────┬────────────┘
                 │
                 ▼ Constant Outflow Rate (e.g. 1 req / 500ms)
        [ Processed by API ]

How it works:

Modeled as a FIFO queue with a fixed capacity.
When a request arrives, if the queue has free space, the request is added to the queue; otherwise, it leaks out (dropped).
Requests are pulled from the queue and processed at a constant, smooth outflow rate.

Pros: Smooths out traffic spikes, ideal for stable egress throughput.
Cons: Traffic bursts fill the queue quickly, causing subsequent fresh requests to be dropped; requests in the queue face processing delay.

3. Fixed Window Counter Algorithm

Divides time into fixed intervals (e.g., 1 minute, 1 hour) and assigns a counter to each window.

Window 1 [00:00 - 01:00]        Window 2 [01:00 - 02:00]
Limit: 5 requests / min         Limit: 5 requests / min
┌───────────────────────────┐   ┌───────────────────────────┐
│ Count: 5 / 5  (Allowed)   │   │ Count: 5 / 5  (Allowed)   │
└───────────────────────────┘   └───────────────────────────┘

The Boundary Burst Problem:

If a user sends 5 requests at 00:59 and another 5 requests at 01:01, the system processes 10 requests within a 2-second interval, which is 2x the intended limit.

Time:          00:00            00:59   01:00   01:01            02:00
Requests:                         5       |       5
                                 ▲        |      ▲
                                 └────────┴──────┘
                           10 requests in 2-sec window! (2x Limit)

Pros: Highly memory-efficient (single key-value pair per window).
Cons: Traffic spikes at window edges allow up to 2x the limit.

4. Sliding Window Log Algorithm

Fixes the boundary problem by recording the exact Unix timestamp of every request in a sorted set (e.g., Redis ZSET).

Window Size: 1 minute (60s) | Limit: 3 requests / min
Current Time: 01:00:45

Sorted Set for user:101
┌────────────┬────────────┬────────────┐
│  01:00:10  │  01:00:30  │  01:00:40  │  <── Count = 3 (Limit Reached)
└────────────┴────────────┴────────────┘
Incoming at 01:00:45:
1. Remove all timestamps older than (01:00:45 - 60s = 00:59:45)
2. Check remaining count (3 elements).
3. Result: 3 >= Limit ──> REJECT with HTTP 429

Pros: 100% mathematically accurate. Never exceeds rate limit at any arbitrary rolling window.
Cons: High Memory Consumption. Storing timestamps for millions of requests consumes vast amounts of Redis RAM.

5. Sliding Window Counter Algorithm

A hybrid approach that combines the low memory overhead of the Fixed Window with the smooth boundary handling of the Sliding Window Log.

Previous 1-Min Window (Count = 6)       Current 1-Min Window (Count = 3)
[ 01:00:00                   01:01:00 ] [ 01:01:00                   01:02:00 ]
               ┌──────────────────────────┐
               │ Current Request @ 01:01:30 (50% into current window)
               └──────────────────────────┘

Weighted Approximation Formula:

$\text{Requests in Window} = (\text{Count in Prev Window} \times (1 - \text{Overlap \%})) + \text{Count in Current Window}$

Example Calculation:

Previous window request count = 6
Current window request count = 3
Request comes at 01:01:30 (30 seconds into a 60-second window, so overlap = $50\% = 0.5$ ):
$\text{Estimated Requests} = (6 \times (1 - 0.5)) + 3 = (6 \times 0.5) + 3 = 3 + 3 = 6$

If the limit is 7, the request is accepted; if the limit is 5, it is rejected.

Pros: Memory-efficient (only 2 numbers stored per user), smooths traffic spikes, assumes ~99.9% real-world accuracy without storing individual timestamps.
Cons: Minor approximation error when historical requests are unevenly clustered.

6. Comparison of Rate Limiting Algorithms

Algorithm	Memory Consumption	Spike / Burst Handling	Accuracy	Complexity
Token Bucket	Minimal (2 variables)	Allows controlled bursts	High	Low
Leaky Bucket	Low (Queue capacity)	Smooths to constant rate	High	Medium
Fixed Window	Ultra-low (1 counter)	Vulnerable to 2x boundary spikes	Low at edges	Very Low
Sliding Window Log	High (stores all timestamps)	Completely smooth	100% Exact	Medium
Sliding Window Counter	Ultra-low (2 counters)	Smooth rolling boundary	~99.9% Approximate	Low

7. Rate Limiter Architecture in a Distributed System

                      Client Requests
                             │
                             ▼
 ┌────────────────────────────────────────────────────────┐
 │                   API Gateway Cluster                  │
 │  ┌──────────────────┐          ┌──────────────────┐   │
 │  │ Gateway Node 1   │          │ Gateway Node 2   │   │
 │  └────────┬─────────┘          └────────┬─────────┘   │
 └───────────┼─────────────────────────────┼──────────────┘
             │ (Atomic Lua Script)         │
             ▼                             ▼
 ┌────────────────────────────────────────────────────────┐
 │                  Redis Cluster                         │
 │     [ user_101:counter ]     [ user_102:counter ]      │
 └────────────────────────────────────────────────────────┘
             │
             ├── Allowed ──> [ Forward to Backend Microservices ]
             │
             └── Blocked ──> [ Return HTTP 429 + Headers ]

Rate Limiting Configuration Rules (YAML):

rules:
  - domain: auth
    path: /api/v1/auth/login
    limit: 5
    window_seconds: 60
    key_by: IP

  - domain: messaging
    path: /api/v1/messages
    limit: 100
    window_seconds: 60
    key_by: USER_ID

8. Distributed Challenges & Solutions

1. Race Conditions in High-Throughput Systems

When two concurrent requests arrive simultaneously at two different gateway servers, both may read the counter before either increments it:

Request 1 (Server A) ──> Read Counter (Val = 3)
Request 2 (Server B) ──> Read Counter (Val = 3)
Request 1 (Server A) ──> Write Counter = 4
Request 2 (Server B) ──> Write Counter = 4  (Counter should be 5!)

Solution: Redis Lua Scripts

Redis executes Lua scripts atomically as a single command without interruption from other clients:

-- Lua script for Sliding Window Counter in Redis
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local current = tonumber(redis.call('get', key) or "0")

if current + 1 > limit then
    return 0 -- Throttled
else
    redis.call("INCRBY", key, 1)
    if current == 0 then
        redis.call("EXPIRE", key, tonumber(ARGV[2]))
    end
    return 1 -- Allowed
end

2. Multi-Datacenter Synchronization

If rate limiter nodes exist in multiple geographic data centers (e.g., US-East and EU-West):

Centralized Global Redis: Adds cross-continent network latency (100–150 ms) to every API call.
Eventual Consistency with CRDTs / Edge Sync: Store local counters at edge PoPs and synchronize asynchronously, accepting slight temporary limit discrepancies.

9. HTTP Response Headers for Rate Limiting

When an API enforces rate limits, it returns standard informational headers:

Header	Meaning	Example
`X-Ratelimit-Limit`	Maximum number of allowed requests in current window	`100`
`X-Ratelimit-Remaining`	Remaining allowed requests in the current window	`14`
`X-Ratelimit-Retry-After`	Number of seconds to wait before making a new request	`42`

Sample HTTP 429 Response:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
X-Ratelimit-Limit: 100
X-Ratelimit-Remaining: 0
X-Ratelimit-Retry-After: 35

{
  "error": "Too Many Requests",
  "message": "You have exceeded your API rate limit of 100 requests per minute. Please retry in 35 seconds."
}

10. Summary Checklist for Interviews

Clarify Scope: Client-side vs Server-side? IP vs User ID? Return 429 with headers?
Choose the Right Algorithm:
- Use Token Bucket if bursts must be accommodated (Stripe style).
- Use Sliding Window Counter if memory efficiency and smooth rate limiting are primary goals.
Storage Tier: In-Memory key-value store (Redis) with TTL expiration.
Distributed Concurrency: Mention Redis Lua scripts or atomic operations to resolve race conditions.
Resilience & Fault Tolerance: If Redis fails, gracefully fail-open so legitimate user requests are not blocked.