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 (8 bytes) + TTL (8 bytes) + Redis key overhead (~80 bytes) = ~100 bytes
• 10M active users = ~1 GB 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 → HTTP 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       │
                 └──────────────┘

Option B: Centralized (API Gateway or Load Balancer)
┌──────────┐     ┌──────────────┐     ┌──────────────┐
│  Client  │────►│  Gateway /   │────►│  API Server  │
└──────────┘     │  ALB + WAF   │     └──────────────┘
                 │  (rate limit │
                 │   + routing) │
                 └──────┬───────┘
                        ▼
                 ┌──────────────┐
                 │  Redis       │
                 └──────────────┘

Middleware works for a single service with a few instances. Once you have multiple services at scale, centralized rate limiting avoids connection sprawl and keeps rules in one place. Failure mode: if Redis is down, fail open (pass the request through) — never fail closed or your entire site goes down when Redis does.

ALB + WAF is a strong choice in AWS. The ALB is already in your request path, so attaching WAF rate-based rules adds rate limiting with zero extra hops and zero code. The tradeoff is flexibility: WAF rate rules work well for IP-based limits but need custom header forwarding for per-user limits. Failure mode: AWS-managed, so unavailability is AWS's problem, not yours.

API Gateway gives you the most control. You define rate limits per route, per user, per API key, all in one config. The cost is an extra network hop and another service to manage. Failure mode: the gateway is now in the critical path — Request → ALB → Gateway → App. If the gateway goes down, requests can't reach your app at all unless the ALB has a bypass target group or the gateway runs with multiple redundant instances.

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. This is the sliding window counter:

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 holds tokens. This is the token bucket algorithm. Tokens aren't added by a background process. Instead, each request calculates how many tokens should exist based on elapsed time. This is called lazy refill:

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 }  TTL: 60s

On each request (lazy refill):
  1. Key missing? → New or returning user. Start with full bucket
  2. elapsed = now - last_refill
  3. new_tokens = elapsed × refill_rate (cap at bucket capacity)
  4. If tokens + new_tokens > 0: decrement, allow
  5. Else: reject
  6. Update last_refill = now, reset TTL

No background timers, no polling. The "refill" is just math on each request. A user idle for 30 seconds at 1 token/sec gets 30 tokens added (capped at capacity) when their next request arrives. Between requests, nothing happens. Same cost as any other algorithm: one Redis operation per request.

The TTL keeps Redis clean. If a user stops making requests, their key expires automatically. When they come back (even a month later), there's no key, so they get a fresh full bucket. Only active users consume memory.

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?