06 - Design a Rate Limiter

🎁 A single bad actor can send 10,000 requests per second to your API. How do you stop them without slowing down everyone else?

A rate limiter controls how many requests a user (or IP, or API key) can make in a given time window. It protects your services from abuse, prevents DDoS attacks, and ensures fair usage. This lesson introduces the core algorithms, where to place the limiter, and why Redis is the standard implementation choice.

Rate Limiter Requirements

Rate Limiter Functional Requirements

• Limit requests per user/IP/API key within a time window (e.g., 100 requests per minute)
• Return HTTP 429 (Too Many Requests) when limit is exceeded
• Include rate limit headers in every response so clients can self-throttle
• Support different limits per endpoint (e.g., /api/search: 10/min, /api/posts: 100/min)
• Distributed: works correctly across multiple API servers

Rate Limiter Non-Functional Requirements

Rate Limiter Scope Exclusions

• DDoS mitigation at the network layer (that's Cloudflare/AWS Shield)
• Billing/metering (counting for invoicing, not blocking)
• Adaptive rate limiting (adjusting limits based on server load)

Rate Limiter Estimation

Rate Limiter Traffic

• 100K requests/sec across all servers
• Each request requires one rate limit check (read + increment)
• That's 100K Redis operations/sec, well within a single Redis instance's capacity

Rate Limiter Storage

• Per user: one counter + TTL = ~50 bytes
• 10M active users = 500 MB in Redis
• Tiny. Fits easily in memory.

Rate Limiter Key Insight

The rate limiter sits in the request hot path (the code executed on every single request). Every single API request passes through it. If it adds 50ms of latency, your entire API is 50ms slower. This is why it must be in-memory (Redis) and why the algorithm must be simple.

Rate Limiter High-Level Design

┌────────────────────────────────────────────────────────────────┐
│                       RATE LIMITER                             │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  ┌──────────┐     ┌──────────────────────────┐     ┌────────┐  │
│  │  Client  │────►│  API Server              │────►│ Handler│  │
│  │          │◄────│                          │◄────│ (logic)│  │
│  └──────────┘     │  ┌────────────────────┐  │     └────────┘  │
│                   │  │ Rate Limit Check   │  │                 │
│                   │  │ (middleware)       │  │                 │
│                   │  └─────────┬──────────┘  │                 │
│                   └────────────┼─────────────┘                 │
│                                │                               │
│                                ▼                               │
│                   ┌──────────────────────┐                     │
│                   │  Redis               │                     │
│                   │  (shared counters)   │                     │
│                   │  one key per user    │                     │
│                   │  per time window     │                     │
│                   └──────────────────────┘                     │
└────────────────────────────────────────────────────────────────┘

Flow: Every request hits the rate limit middleware first. It checks Redis (is this user over the limit?). If yes → 429. If no → increment counter, pass to handler.

Rate Limiter Placement

Option A: In each API server (middleware)
┌──────────┐     ┌─────────────────────────────┐
│  Client  │────►│  API Server                 │
└──────────┘     │  ┌───────────┐  ┌────────┐  │
                 │  │Rate Limit │─►│ Handler│  │
                 │  │middleware │  └────────┘  │
                 │  └─────┬─────┘              │
                 └────────┼────────────────────┘
                          ▼
                 ┌──────────────┐
                 │  Redis       │
                 │  (shared     │
                 │   counters)  │
                 └──────────────┘

Option B: As a separate service (API Gateway)
┌──────────┐     ┌──────────────┐     ┌──────────────┐
│  Client  │────►│  API Gateway │────►│  API Server  │
└──────────┘     │  (rate limit │     └──────────────┘
                 │   + routing) │
                 └──────┬───────┘
                        ▼
                 ┌──────────────┐
                 │  Redis       │
                 └──────────────┘

Both are valid. Middleware is simpler for small teams. API Gateway (Kong, AWS API Gateway) is better when you have many services in different languages.

Why Redis is shared: If user "alice" hits Server A and Server B, both must see the same counter. A local in-memory counter per server would allow 100 × N requests (where N = number of servers).

Rate Limiter Deep Dive

Algorithm 1: Fixed Window Counter

The simplest approach. Count requests in fixed time windows:

Window: 10:00:00 - 10:00:59 → counter = 0
  Request at 10:00:05 → counter = 1 ✓
  Request at 10:00:30 → counter = 2 ✓
  ...
  Request at 10:00:55 → counter = 100 ✓
  Request at 10:00:58 → counter = 101 ✗ REJECTED

Window: 10:01:00 - 10:01:59 → counter resets to 0

Redis implementation:

key:  ratelimit:{user_id}:{minute}
      e.g., ratelimit:alice:202605271000

# Derive the minute key from current timestamp:
# minute_key = floor(unix_timestamp / 60)
# In code: Math.floor(Date.now() / 60000) or time.Now().Unix() / 60

INCR ratelimit:alice:202605271000
EXPIRE ratelimit:alice:202605271000 60

The boundary problem: A user sends 100 requests at 10:00:59 and 100 more at 10:01:00. That's 200 requests in 2 seconds, double the intended limit. The window boundary creates a loophole.

Algorithm 2: Sliding Window Counter

Fixes the boundary problem by blending the current and previous window:

Previous window (10:00): 80 requests
Current window (10:01): 30 requests
Current position: 15 seconds into the minute (25% through)

Estimated count = prev × overlap% + current
                = 80 × 0.75 + 30
                = 60 + 30 = 90

Limit is 100 → 90 < 100 → ALLOW

Why this works: Instead of a hard reset at the boundary, it smoothly transitions between windows. The estimate is ~99.7% accurate, good enough for rate limiting.

Redis implementation: Store two counters (current window + previous window) and compute the weighted sum on each request.

Algorithm 3: Token Bucket

A different mental model. Imagine a bucket that fills with tokens at a steady rate:

Bucket capacity: 10 tokens
Refill rate: 1 token per second

Request arrives:
  Tokens available? → Take one, allow request
  Bucket empty? → Reject (429)

After 10 seconds idle: bucket is full (10 tokens)
Burst of 10 requests: all allowed (empties bucket)
11th request immediately after: rejected (no tokens)
Wait 1 second: 1 token available again

Why token bucket is popular:

• Allows short bursts (up to bucket capacity) while enforcing average rate
• Simple to understand and implement
• Used by AWS, Stripe, and most API providers

Redis implementation:

Store: { tokens: 7, last_refill: 1716800000 }

On each request:
  1. Calculate tokens to add since last_refill
  2. Add tokens (cap at bucket capacity)
  3. If tokens > 0: decrement, allow
  4. Else: reject

Comparing the Algorithms

Interview default: Sliding window counter. It's the most commonly asked and balances simplicity with accuracy.

Atomic Operations with Lua

The rate limit check must be atomic. "Read counter, check limit, increment" must happen as one operation. Otherwise:

Thread A: reads counter = 99
Thread B: reads counter = 99
Thread A: 99 < 100, increments to 100 ✓
Thread B: 99 < 100, increments to 101 ✗ (over limit!)

Solution: Redis Lua script. It executes atomically on the server:

-- KEYS[1] = rate limit key (e.g., ratelimit:alice:202605271000)
-- ARGV[1] = window TTL in seconds (e.g., 60)
-- ARGV[2] = max allowed requests (e.g., 100)

local count = redis.call('INCR', KEYS[1])   -- increment counter
if count == 1 then
  redis.call('EXPIRE', KEYS[1], ARGV[1])    -- set TTL on first request only
end
if count > tonumber(ARGV[2]) then
  return 0  -- rejected: over limit
end
return 1  -- allowed: under limit

One network round trip, fully atomic. No race conditions.

Response Headers

Every response should include rate limit info so clients can self-throttle:

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 42
X-RateLimit-Reset: 1716800060  (Unix timestamp when window resets)

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

Good clients read these headers and back off before hitting 429. Bad clients ignore them. That's what the limiter is for.

Rate Limiting in the Request Lifecycle

An important subtlety: application-level rate limiting happens after the full request is received. If a user POSTs a 50 MB file and gets 429'd, your server already received all 50 MB. You just didn't process it.

To reject large requests early (before receiving the body), you need rate limiting at the load balancer or gateway level. It can reject based on headers alone without reading the body. This is another reason API Gateways are popular for rate limiting.

Redis Failure Handling

The rate limiter is in the hot path. If Redis is unreachable:

Default: Fail open. A few seconds without rate limiting is better than rejecting every request. Alert the team and fix Redis.

Rate Limiting Dimensions

You can limit by multiple dimensions simultaneously:

Per user:     100 requests/min (authenticated users)
Per IP:       50 requests/min (anonymous/unauthenticated)
Per endpoint: /api/search: 10/min, /api/upload: 5/min
Per method:   POST: 20/min, GET: 200/min

Each dimension is a separate Redis key:

ratelimit:user:alice:minute:202605271000
ratelimit:ip:203.0.113.1:minute:202605271000
ratelimit:endpoint:/api/search:user:alice:minute:202605271000

Key Takeaways

• The rate limiter sits in the hot path, and latency is critical

  Every request passes through it. Redis gives sub-millisecond checks. A slow rate limiter makes your entire API slow. Keep the algorithm simple and the data store fast.

• Sliding window counter is the interview default

  It fixes the boundary burst problem of fixed windows without the complexity of token buckets. Weighted average of current + previous window gives ~99.7% accuracy.

• Lua scripts make Redis operations atomic

  Read-check-increment must be one atomic operation to prevent race conditions. A Lua script executes on the Redis server in a single step. No interleaving from other clients.

• Fail open when Redis is down

  For user-facing APIs, rejecting all traffic is worse than allowing temporary abuse. Fail open, alert the team, fix Redis. For payment endpoints, fail closed instead.

• Shared state (Redis) is required for distributed rate limiting

  Local counters per server allow N× the limit (where N = server count). All servers must check the same counter in Redis to enforce a global limit per user.

• Response headers enable cooperative clients

  X-RateLimit-Remaining and Retry-After let well-behaved clients self-throttle before hitting 429. The limiter still protects against bad clients, but good ones never trigger it.

🎁 What if you need just two operations, GET and PUT, but they need to work across hundreds of nodes with no single point of failure?