#Design a Rate Limiter (Cloudflare Scale)

#1. Problem Statement & Clarifications

A rate limiter controls the rate of traffic a client can send to an API. It prevents abuse, protects services from overload, and ensures fair resource allocation. At scale, rate limiting must be distributed, low-latency (inline with every request), and support flexible rules per client/endpoint/tier.

#Functional Requirements

Limit API requests — Enforce configurable rate limits (e.g., 100 req/min per user)
Multiple rule dimensions — Limit by user ID, IP, API key, endpoint, or combination
Tiered limits — Different limits for free/pro/enterprise tiers
Rule management — CRUD API for rate limit rules (admin)
Informative headers — Return X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After
Soft vs Hard limits — Support warning mode (log but allow) vs enforcement mode (reject)

#Non-Functional Requirements

Requirement	Target
Latency overhead	P99 < 2ms added per request (inline)
Throughput	1M+ requests/sec across all clients
Availability	99.99% — rate limiter failure must NOT block traffic (fail-open)
Accuracy	±5% tolerance on limit enforcement (distributed counting)
Rule update propagation	< 30 seconds globally

#Out of Scope

DDoS protection at network layer (L3/L4)
Web Application Firewall (WAF) rules
Bot detection and CAPTCHA
Billing/metering integration

#Assumptions

Rate limiter runs as middleware / sidecar, NOT a standalone proxy
Limits are per sliding window (not fixed calendar windows)
Most rules are per-user + per-endpoint (millions of unique counters)
Acceptable to occasionally allow a few extra requests over the limit (distributed trade-off)

#2. Back-of-Envelope Estimation

#Traffic Estimates

Total API requests:     1M QPS across all clients
Unique clients:         10M active API keys / user IDs
Rate limit checks/sec:  1M (1 check per request)
Counter updates/sec:    1M (1 increment per request)
Rule lookups/sec:       1M (cached after first lookup)

#Storage Estimates

Counter per client-endpoint: client_id (16B) + endpoint (32B) + count (8B) + window (8B) = 64B
Active counters:        10M clients × 5 endpoints avg = 50M counters
Counter storage:        50M × 64B = 3.2GB (fits in Redis memory)
Rules storage:          ~10K rules × 200B = 2MB (trivial)

#Bandwidth

Rate limit check:       1M/sec × 64B = 64 MB/s (Redis GET+INCR)
Acceptable for Redis cluster with 10 nodes (~6.4 MB/s per node)

#Cache Estimates

Rule cache (per node):   10K rules × 200B = 2MB (in-process cache)
Rule cache TTL:          30s (refresh from config store)
No separate cache needed: Redis IS the primary counter store

#3. API Design

#Rate-Limited Request Flow (Middleware)

ANY /api/v1/*
X-Api-Key: <key>

Rate Limiter injects response headers:
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 42
  X-RateLimit-Reset: 1716984000       // Unix timestamp
  X-RateLimit-Policy: "100;w=60"      // 100 per 60s window

If rate exceeded:
  HTTP 429 Too Many Requests
  Retry-After: 23                     // seconds
  {
    "error": "rate_limit_exceeded",
    "limit": 100,
    "window": "60s",
    "retry_after": 23
  }

#Admin: Create/Update Rule

POST /api/v1/rate-limits/rules
Authorization: Bearer <admin_token>

{
  "rule_id": "api-free-tier",
  "match": {
    "tier": "free",
    "endpoint_pattern": "/api/v1/*"
  },
  "limit": 100,
  "window_seconds": 60,
  "action": "reject",               // reject | log_only
  "burst_allowance": 10             // allow 10 extra in burst
}

Response 201:
{
  "rule_id": "api-free-tier",
  "created_at": "2025-05-29T12:00:00Z",
  "status": "active"
}

#Admin: Get Current Usage

GET /api/v1/rate-limits/usage/{client_id}

Response 200:
{
  "client_id": "user_12345",
  "rules": [
    { "rule_id": "api-free-tier", "limit": 100, "current": 58, "window_resets_at": "..." }
  ]
}

#4. Data Model

#Rate Limit Rules (PostgreSQL — config store, not on hot path)

CREATE TABLE rate_limit_rules (
  rule_id         VARCHAR(100) PRIMARY KEY,
  tier            VARCHAR(50),              -- free | pro | enterprise
  endpoint_pattern VARCHAR(200),            -- /api/v1/*, /api/v1/search
  limit_count     INT NOT NULL,
  window_seconds  INT NOT NULL,
  burst_allowance INT DEFAULT 0,
  action          ENUM('reject','log_only') DEFAULT 'reject',
  is_active       BOOLEAN DEFAULT true,
  created_at      TIMESTAMP DEFAULT NOW(),
  updated_at      TIMESTAMP DEFAULT NOW()
);

CREATE INDEX idx_rules_tier ON rate_limit_rules(tier, is_active);

#Rate Counters (Redis — the hot path store)

Sliding Window Counter approach:

Key:   rl:{client_id}:{endpoint}:{window_start}
Value: <request_count>
TTL:   window_seconds × 2 (auto-cleanup)

Example:
  rl:user_123:/api/v1/search:1716984000 → 42
  rl:user_123:/api/v1/search:1716984060 → 17

#Rule Cache (In-Process — per application node)

HashMap<rule_key, RateRule> refreshed every 30s from PostgreSQL
Matching: tier + endpoint_pattern → rule (longest prefix match)

#Access Patterns

Query	Store	Index/Key
Check + increment counter	Redis	Key: rl:{client}:{endpoint}:{window}
Load rate limit rules	PostgreSQL → in-process cache	IX: tier + is_active
Get client usage stats	Redis SCAN	Pattern: rl:{client_id}:*
Update/create rules	PostgreSQL	PK: rule_id

#5. High-Level Design (HLD) & Scale Evolution

#Stage 1: MVP / Single Server (10K QPS)

Architecture: Rate limiter as in-process middleware. Counters in local memory (HashMap).
Algorithm: Fixed window counter.
Bottleneck: Not distributed — each server has its own counters. Client hitting different servers bypasses limits.

#Stage 2: Growth Scale (100K QPS)

Key Changes:
- Centralized Redis for shared counters across all app servers.
- Sliding window counter algorithm (better accuracy than fixed window).
- Rule caching in-process with 30s refresh.
Bottleneck: Single Redis instance becomes SPOF and throughput bottleneck.

#Stage 3: Cloudflare Scale (1M+ QPS)

#Architecture Diagram

                    ┌───────────────────────────────┐
                    │        API Gateway / LB        │
                    └───────────────┬───────────────┘
                                    │
              ┌─────────────────────┼─────────────────────┐
              ▼                     ▼                     ▼
     ┌──────────────────┐  ┌──────────────────┐  ┌──────────────────┐
     │   App Server 1    │  │   App Server 2    │  │   App Server N    │
     │ ┌──────────────┐  │  │ ┌──────────────┐  │  │ ┌──────────────┐  │
     │ │ Rate Limiter  │  │  │ │ Rate Limiter  │  │  │ │ Rate Limiter  │  │
     │ │ Middleware     │  │  │ │ Middleware     │  │  │ │ Middleware     │  │
     │ │              │  │  │ │              │  │  │ │              │  │
     │ │ • Rule cache  │  │  │ │ • Rule cache  │  │  │ │ • Rule cache  │  │
     │ │ • Local count │  │  │ │ • Local count │  │  │ │ • Local count │  │
     │ └──────┬───────┘  │  │ └──────┬───────┘  │  │ └──────┬───────┘  │
     └────────┼──────────┘  └────────┼──────────┘  └────────┼──────────┘
              │                      │                      │
              └──────────────────────┼──────────────────────┘
                                     │
                    ┌────────────────▼────────────────┐
                    │      Redis Cluster (6 nodes)    │
                    │   Counters: rl:{client}:{ep}    │
                    │   Partitioned by client_id hash  │
                    └────────────────┬────────────────┘
                                     │
                    ┌────────────────▼────────────────┐
                    │     PostgreSQL (Config Store)    │
                    │    Rate limit rules + audit log  │
                    └─────────────────────────────────┘

#Component Breakdown

Component	Responsibility	Tech Choice
Rate Limiter Middleware	Inline check on every request; rule matching; header injection	Go / Lua (OpenResty)
Redis Cluster	Distributed counters; atomic INCR; auto-TTL cleanup	Redis Cluster (6 nodes)
PostgreSQL	Rule storage; audit log; NOT on hot path	Single primary + replica
Rule Config Service	Push rule updates to all nodes; 30s polling or pub/sub	Sidecar / config watcher
Load Balancer	Consistent hashing by client_id (optional)	Nginx / Envoy

#Data Flow

Rate Limit Check (Inline — on every request):

Request arrives → Rate Limiter Middleware
  → 1. Extract client_id (API key / user_id / IP)
  → 2. Match rule: tier + endpoint → limit + window
        (from in-process cache, refreshed every 30s)
  → 3. Compute window key: rl:{client}:{endpoint}:{window_start}
  → 4. Redis: INCR key, EXPIRE if new key
  → 5. Compare count vs limit
        count <= limit → ALLOW, set X-RateLimit-Remaining header
        count > limit  → REJECT with 429, set Retry-After header
  → 6. If action = log_only → allow but log violation

#6. Deep Dive — Core Components

#Rate Limiting Algorithms — Detailed Design

#Algorithm Comparison

Algorithm	Accuracy	Memory	Burst Handling	Complexity
Fixed Window	Low (boundary burst)	Very Low	Poor — 2x burst at boundary	Simple
Sliding Window Log	Exact	High (store every timestamp)	Perfect	Moderate
Sliding Window Counter	~99.x% accurate	Low	Good — weighted average	Moderate
Token Bucket	Good	Low	Excellent — configurable burst	Moderate
Leaky Bucket	Good	Low	Smoothest output	Moderate

Chosen: Sliding Window Counter (primary) + Token Bucket (for burst-tolerant endpoints)

#Sliding Window Counter — How It Works

Window: 60 seconds, Limit: 100 requests
Current time: 12:01:25

Previous window (12:00:00 - 12:01:00): 70 requests
Current window  (12:01:00 - 12:02:00): 25 requests so far

Weighted count = prev × (1 - elapsed%/100) + current
               = 70 × (1 - 25/60) + 25
               = 70 × 0.583 + 25
               = 40.8 + 25
               = 65.8 → round to 66

66 < 100 → ALLOW

#Redis Operations — Detailed Design

Atomic Counter with Lua Script:

Rate limit check + increment MUST be atomic to prevent race conditions.
Using Redis Lua scripting for atomicity:

EVAL script 2 {current_key} {prev_key} {limit} {window} {now}

Script runs entirely in Redis → no network roundtrip race.
Single Redis command → < 0.1ms.

#Fail-Open Design

Critical: Rate limiter failure must NOT block legitimate traffic.

Rate Limiter Check:
  → Redis reachable? → Normal rate limit flow
  → Redis timeout (> 5ms)? → ALLOW request + log warning
  → Redis cluster down? → ALLOW all + P0 alert

Rationale: False negatives (letting extra requests through) are
better than false positives (blocking legitimate users).

#Scaling Strategy

Component	Strategy
Middleware	Scales with app servers; no independent scaling needed
Redis	Cluster mode; partition counters by client_id hash; 6+ nodes
Rule propagation	In-process cache + 30s poll OR Redis Pub/Sub for instant push
Multi-region	Per-region Redis clusters; accept ±5% inaccuracy across regions

#Caching Strategy

┌──────────────────────────────────────────────────────┐
│ Layer 1: In-Process Rule Cache                        │
│ • All rate limit rules cached in HashMap              │
│ • Refreshed every 30s from PostgreSQL                 │
│ • ~2MB memory; instant lookup (< 0.01ms)             │
├──────────────────────────────────────────────────────┤
│ Layer 2: Redis Cluster (Counters)                     │
│ • Distributed counters with auto-TTL                  │
│ • Atomic Lua scripts for check+increment             │
│ • ~3.2GB for 50M active counters                     │
└──────────────────────────────────────────────────────┘

#Consistency Models

Data	Model	Rationale
Rate counters	Eventually consistent (across regions)	Per-region Redis; accept ±5% global inaccuracy
Rate counters	Strongly consistent (within region)	Atomic Lua scripts in Redis
Rules	Eventually consistent (< 30s)	In-process cache refreshed periodically
Audit logs	Eventually consistent	Async write to PostgreSQL

#7. Low-Level Design — Core Functionality

#Key Algorithms

1. Sliding Window Counter

def check_rate_limit(client_id, endpoint, rule):
    """Sliding window counter rate limit check. Returns (allowed, remaining)."""
    now = int(time.time())
    window = rule.window_seconds
    current_window = (now // window) * window
    prev_window = current_window - window
    elapsed = now - current_window

    current_key = f"rl:{client_id}:{endpoint}:{current_window}"
    prev_key = f"rl:{client_id}:{endpoint}:{prev_window}"

    # Atomic Redis operation (Lua script)
    prev_count, curr_count = redis.mget(prev_key, current_key)
    prev_count = int(prev_count or 0)
    curr_count = int(curr_count or 0)

    # Weighted count across sliding window
    weight = 1 - (elapsed / window)
    estimated_count = prev_count * weight + curr_count

    if estimated_count >= rule.limit_count:
        retry_after = window - elapsed
        return False, 0, retry_after

    # Increment current window counter (atomic)
    pipe = redis.pipeline()
    pipe.incr(current_key)
    pipe.expire(current_key, window * 2)
    pipe.execute()

    remaining = rule.limit_count - int(estimated_count) - 1
    return True, max(0, remaining), 0

2. Token Bucket Algorithm

def token_bucket_check(client_id, endpoint, rule):
    """Token bucket rate limit. Allows configurable burst."""
    bucket_key = f"tb:{client_id}:{endpoint}"
    now = time.time()

    # Get current bucket state
    bucket = redis.hgetall(bucket_key)
    tokens = float(bucket.get("tokens", rule.limit_count))
    last_refill = float(bucket.get("last_refill", now))

    # Refill tokens based on elapsed time
    elapsed = now - last_refill
    refill_rate = rule.limit_count / rule.window_seconds  # tokens/sec
    tokens = min(rule.limit_count + rule.burst_allowance,
                 tokens + elapsed * refill_rate)

    if tokens < 1:
        retry_after = (1 - tokens) / refill_rate
        return False, 0, retry_after

    # Consume one token
    tokens -= 1
    redis.hmset(bucket_key, {"tokens": tokens, "last_refill": now})
    redis.expire(bucket_key, rule.window_seconds * 2)

    return True, int(tokens), 0

3. Redis Lua Script (Atomic Sliding Window)

SLIDING_WINDOW_LUA = """
local current_key = KEYS[1]
local prev_key = KEYS[2]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local current_window = math.floor(now / window) * window
local elapsed = now - current_window
local weight = 1 - (elapsed / window)

local prev_count = tonumber(redis.call('GET', prev_key) or '0')
local curr_count = tonumber(redis.call('GET', current_key) or '0')
local estimated = prev_count * weight + curr_count

if estimated >= limit then
    return {0, 0, window - elapsed}  -- rejected
end

curr_count = redis.call('INCR', current_key)
redis.call('EXPIRE', current_key, window * 2)

local remaining = limit - math.ceil(prev_count * weight + curr_count)
return {1, math.max(0, remaining), 0}  -- allowed
"""

#Design Patterns Used

Pattern	Where	Why
Middleware / Interceptor	Rate limiter as request interceptor	Transparent to application; cross-cutting concern
Circuit Breaker	Redis connection; fail-open on timeout	Never block traffic due to rate limiter failure
Strategy Pattern	Pluggable algorithms (sliding window / token bucket)	Different endpoints need different algorithms
Observer / Pub-Sub	Rule update propagation	Push rule changes to all nodes via Redis Pub/Sub

#8. Failure Handling & Edge Cases

#What Happens When X Fails?

Failure	Impact	Mitigation
Redis down	Rate limits not enforced	Fail-open: allow all traffic + P0 alert
Redis slow (> 5ms)	Request latency spikes	Timeout at 5ms; fail-open; circuit breaker
Rule config DB down	Can't update rules	In-process cache serves stale rules (last known good)
Clock skew between servers	Window boundaries misaligned	Use Redis server time (not app server time) via `TIME` command
App server crash	Local rule cache lost	Rebuild from PostgreSQL on restart (< 1s)

#Edge Cases

Distributed counting inaccuracy → Accept ±5% tolerance; use Lua scripts for single-region atomicity
Thundering herd at window boundary → Sliding window smooths this; no sudden counter reset
Client spoofing X-Forwarded-For → Trust only the last proxy hop; validate API keys for authenticated clients
Rate limit rule conflicts → Most specific rule wins (exact endpoint > wildcard > global)
Clock skew → All window calculations use Redis TIME, not local clock
Counter overflow → Redis INCR handles 64-bit integers; overflow at 9.2 quintillion

#9. Monitoring & Observability

#Key Metrics

Metric	Target	Alert Threshold
Rate limit check latency (P99)	< 2ms	> 10ms
Redis operation latency	< 1ms	> 5ms
429 response rate	< 1% of traffic	> 5% (may indicate misconfiguration)
Fail-open events/min	0	> 10 (Redis issues)
Rule cache staleness	< 30s	> 120s
Redis memory usage	< 80%	> 90%

#Alerting Strategy

P0 (Page immediately): Redis cluster unreachable (fail-open mode active), all nodes fail-open
P1 (15 min response): Redis latency spike, rule cache > 2min stale, 429 rate > 5%
P2 (Next business day): Counter memory growth anomaly, rule audit log failures

#SLAs / SLOs

Rate limit check latency:  P99 < 2ms overhead per request
Availability:               99.99% (fail-open ensures no downtime)
Accuracy:                   ±5% of configured limit (distributed)
Rule propagation:           < 30 seconds to all nodes

#10. Trade-off Summary

Decision	Chose	Over	Because
Primary algorithm	Sliding window counter	Fixed window / token bucket	Best balance of accuracy, memory, and burst handling
Counter store	Redis (distributed)	In-process memory	Shared counters across all app servers; consistent limiting
Failure mode	Fail-open	Fail-closed	Blocking legitimate traffic is worse than brief over-limit
Rule storage	PostgreSQL + in-process cache	Redis-only	Rules are relational (tier/endpoint combos); infrequent reads
Atomicity	Redis Lua scripts	Multi-command pipelines	Lua executes atomically; no race conditions on check+incr
Multi-region	Per-region counters	Global counters	Lower latency; accept ±5% cross-region inaccuracy
Rule propagation	30s polling	Real-time push	Simpler; 30s delay acceptable; push adds complexity
Response code	429 Too Many Requests	503 Service Unavailable	429 is semantically correct; 503 implies server failure

#11. Extensions & Follow-ups

#What Would You Add With More Time?

Adaptive Rate Limiting — Auto-adjust limits based on server health (CPU, latency)
Rate Limit by Cost — Weight different endpoints (search=5, read=1) against a single budget
Distributed Token Bucket — Sync tokens across regions for global rate limits
Rate Limit Dashboard — Real-time visualization of top rate-limited clients
Webhook on Limit — Notify service owners when specific clients hit limits
Gradual Degradation — Instead of hard 429, progressively increase latency (tarpit)

#How Would This Change at 100x Scale?

100M QPS: Local rate limiting with periodic sync to Redis (reduce Redis load 90%); accept lower accuracy
1B unique clients: Shard Redis by client_id hash across 100+ nodes; consider Memcached for simpler counter workload
Global deployment: Per-region rate limiting with periodic cross-region sync; eventual consistency across regions
Cost optimization: Move cold counters (inactive clients) from Redis to disk; keep only active in memory

#12. Cross-References

Topic	Connection
URL Shortener (#1)	Rate limiting protects the create endpoint
Key-Value Store (#3)	Redis counter store is a specialized KV usage
E-Commerce (#11)	API rate limiting for checkout/search endpoints

#Building Blocks Used

Redis — Distributed counter store; Lua scripts for atomicity
PostgreSQL — Rule configuration store; audit logging
Load Balancer — Consistent hashing to route same client to same server (optional optimization)

#Concepts Used

Circuit Breaker — Fail-open when Redis is unreachable
Consistency Models — Eventually consistent counters across regions