--- # === IDENTITY === id: software/system-design/rate-limiter/2026 canonical_question: "How do I design a distributed rate limiter?" aliases: - "distributed rate limiting" - "API rate limiter design" - "token bucket algorithm" - "sliding window rate limiter" - "rate limiting system design interview" - "Redis rate limiter" - "leaky bucket algorithm" - "API throttling architecture" - "rate limiter microservices" - "distributed rate limiting Redis" entity_type: software_reference domain: software > system-design > rate_limiter region: global jurisdiction: global temporal_scope: 2020-2026 # === VERIFICATION === last_verified: 2026-02-23 confidence: 0.93 version: 1.0 first_published: 2026-02-23 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-22 change_sensitivity: low # === CONSTRAINTS === constraints: - "All counter operations (read-check-increment) must be atomic — use Redis Lua scripts or CAS operations to prevent race conditions" - "Clock skew across distributed nodes causes inconsistent windowing — use a centralized time source or wall-clock-aligned windows" - "Redis single-instance is a SPOF — always deploy with master-replica replication and Sentinel or Cluster for production" - "Never fail-open by default in security-critical contexts (DDoS, auth brute-force) — design explicit fail-open vs fail-closed policy per limiter" - "Memory grows linearly with unique keys — set TTL on all rate limit keys and monitor Redis memory usage" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need application-level circuit breaking (service unavailable, not rate exceeded)" use_instead: "Circuit breaker pattern — different failure domain (availability vs throttling)" - condition: "Need DDoS mitigation at network layer (L3/L4)" use_instead: "CDN/edge rate limiting (Cloudflare, AWS Shield) — L7 rate limiting does not protect against volumetric attacks" - condition: "Single-server rate limiting only (no distributed coordination needed)" use_instead: "In-process rate limiter (e.g., Guava RateLimiter, golang.org/x/time/rate) — simpler, no Redis dependency" # === AGENT HINTS === inputs_needed: - key: algorithm_choice question: "What is your primary concern: burst tolerance, strict accuracy, or simplicity?" type: choice options: ["Burst tolerance (token bucket)", "Strict accuracy (sliding window log)", "Simplicity (fixed window)", "Smooth output rate (leaky bucket)", "Not sure — recommend based on scale"] - key: scale question: "What is your expected request volume?" type: choice options: ["<1K requests/sec", "1K-100K requests/sec", ">100K requests/sec"] - key: deployment question: "Where will rate limiting be enforced?" type: choice options: ["API gateway/reverse proxy", "Application middleware", "Sidecar/service mesh", "Edge/CDN"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/system-design/rate-limiter/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-23)" # === RELATED UNITS === related_kos: related_to: - id: "software/debugging/postgresql-connection-pool/2026" label: "PostgreSQL Connection Pool Exhaustion" - id: "software/migrations/monolith-to-microservices/2026" label: "Monolith to Microservices Migration" solves: - id: "software/system-design/api-gateway/2026" label: "API Gateway Design" alternative_to: - id: "software/system-design/circuit-breaker/2026" label: "Circuit Breaker Pattern" often_confused_with: - id: "software/system-design/load-balancer/2026" label: "Load Balancer Design (distributes traffic, does not limit it)" # === SOURCES (7 authoritative sources) === # Types: official_docs, technical_blog, rfc_spec, academic_paper, community_resource, industry_report # Reliability: high, moderate_high, moderate, moderate_low, low, authoritative sources: - id: src1 title: "Scaling your API with rate limiters" author: Stripe Engineering url: https://stripe.com/blog/rate-limiters type: technical_blog published: 2017-01-18 reliability: high - id: src2 title: "How we built rate limiting capable of scaling to millions of domains" author: Cloudflare Engineering url: https://blog.cloudflare.com/counting-things-a-lot-of-different-things/ type: technical_blog published: 2017-10-23 reliability: high - id: src3 title: "Rate Limiting" author: Redis url: https://redis.io/glossary/rate-limiting/ type: official_docs published: 2024-01-15 reliability: high - id: src4 title: "Build 5 Rate Limiters with Redis: Comparing Algorithms from Fixed Window to Leaky Bucket" author: Redis url: https://redis.io/tutorials/howtos/ratelimiting/ type: official_docs published: 2024-06-10 reliability: high - id: src5 title: "Rate Limiter For The Real World" author: Alex Xu (ByteByteGo) url: https://blog.bytebytego.com/p/rate-limiter-for-the-real-world type: technical_blog published: 2023-08-15 reliability: moderate_high - id: src6 title: "Rate limiting overview — Google Cloud Armor" author: Google Cloud url: https://cloud.google.com/armor/docs/rate-limiting-overview type: official_docs published: 2024-09-01 reliability: high - id: src7 title: "From Token Bucket to Sliding Window: Pick the Perfect Rate Limiting Algorithm" author: API7.ai url: https://api7.ai/blog/rate-limiting-guide-algorithms-best-practices type: technical_blog published: 2024-03-20 reliability: moderate_high --- # Designing a Distributed Rate Limiter ## TL;DR - **Bottom line**: Use a Redis-backed token bucket or sliding window counter at the API gateway layer; wrap all counter operations in Lua scripts for atomicity; deploy Redis with replication for availability. - **Key tool/command**: `redis-cli EVAL "lua_script" 1 key limit window` (atomic rate-limit check via Lua) - **Watch out for**: Race conditions from non-atomic read-then-write operations — two concurrent requests can both pass the check before either increments the counter. - **Works with**: Any language with a Redis client; deploy at API gateway (Kong, NGINX, Envoy), application middleware, or edge (Cloudflare, AWS WAF). ## Constraints - All counter operations (read-check-increment) must be atomic — use Redis Lua scripts or CAS operations to prevent race conditions - Clock skew across distributed nodes causes inconsistent windowing — use a centralized time source or wall-clock-aligned windows - Redis single-instance is a SPOF — always deploy with master-replica replication and Sentinel or Cluster for production - Never fail-open by default in security-critical contexts (DDoS protection, auth brute-force) — design explicit fail-open vs fail-closed policy per limiter - Memory grows linearly with unique keys — set TTL on all rate limit keys and monitor Redis memory usage ## Quick Reference | Component | Role | Technology Options | Scaling Strategy | |---|---|---|---| | **Rate Limit Algorithm** | Core counting logic | Token bucket, sliding window counter, fixed window, leaky bucket | Algorithm choice depends on burst tolerance vs accuracy requirements | | **Centralized Counter Store** | Atomic counters shared across nodes | Redis (primary), Memcached, DynamoDB | Redis Cluster with hash slots; read replicas for high-read workloads | | **API Gateway / Proxy** | Enforcement point before application | NGINX, Kong, Envoy, AWS API Gateway, Cloudflare | Horizontal scaling; each instance queries shared counter store | | **Lua Script Engine** | Atomic multi-step operations | Redis EVAL/EVALSHA | Scripts cached server-side via SHA; no additional scaling needed | | **Rule Configuration Store** | Per-client/tier rate limits | Config file, database, feature flags | Hot-reload without restart; hierarchical rules (global > tenant > endpoint) | | **Client Identity Resolver** | Extracts rate-limit key from request | API key, JWT claims, IP address, combination | Consistent hashing to same Redis shard per client key | | **Response Header Formatter** | Communicates limit status to clients | X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After, RateLimit (draft RFC) | Standard headers; no scaling concern | | **Async Counter Sync** | Reduces latency for non-critical limits | Local counters + periodic sync to Redis | Eventual consistency; configurable sync interval | | **Monitoring & Alerting** | Tracks rejection rates, Redis latency | Prometheus + Grafana, Datadog, CloudWatch | Alert on rejection spike, Redis memory, counter key cardinality | | **Fallback / Circuit Breaker** | Handles Redis outage gracefully | In-memory local limiter, fail-open, fail-closed | Degrade to local approximate limiting; log for reconciliation | | **Load Shedder** | Protects system under extreme load | Priority-based traffic classification | Stripe model: critical > POSTs > GETs > test traffic [src1] | | **Clock Synchronization** | Consistent time across nodes | NTP, wall-clock-aligned windows | Align windows to Unix epoch seconds; tolerate small skew with weighted windows | ## Decision Tree ``` START ├── Request volume <1K/sec and single datacenter? │ ├── YES → In-process rate limiter (Guava RateLimiter, Go rate.Limiter) — no Redis needed │ └── NO ↓ ├── Need to allow short traffic bursts above steady rate? │ ├── YES → Token bucket algorithm (Redis + Lua) │ │ ├── Stripe-style API? → Add concurrent request limiter + load shedder [src1] │ │ └── Standard API? → Token bucket with per-key buckets │ └── NO ↓ ├── Need precise per-second accuracy (billing, compliance)? │ ├── YES → Sliding window log (Redis sorted sets) — higher memory cost │ └── NO ↓ ├── Need smooth output rate (queue processing, webhooks)? │ ├── YES → Leaky bucket (process at fixed rate, queue excess) │ └── NO ↓ ├── Simple implementation, tolerant of boundary burst? │ ├── YES → Fixed window counter (simplest Redis INCR) │ └── NO ↓ └── DEFAULT → Sliding window counter (Cloudflare approach) — best accuracy/memory trade-off [src2] ``` ## Step-by-Step Guide ### 1. Choose your rate-limiting key Define what identifies a unique client. Common keys: API key, user ID, IP address, or composite (user + endpoint). The key determines the granularity of your limits. [src1] ``` Rate-limit key examples: - Per user: ratelimit:{user_id}:{endpoint} - Per API key: ratelimit:{api_key} - Per IP: ratelimit:{client_ip}:{endpoint} - Per tenant: ratelimit:{tenant_id}:{tier} ``` **Verify**: Ensure keys are unique per client scope — duplicate keys cause shared limits across unrelated clients. ### 2. Implement atomic counter operations with Redis Lua All rate-limit checks must be atomic. A Lua script ensures the read-check-increment cycle cannot be interrupted by concurrent requests. [src3] [src4] ```lua -- Token bucket rate limiter (Redis Lua script) -- KEYS[1] = rate limit key -- ARGV[1] = max tokens (bucket capacity) -- ARGV[2] = refill rate (tokens per second) -- ARGV[3] = current timestamp (seconds) -- ARGV[4] = tokens to consume (usually 1) -- Returns: {allowed (0/1), remaining_tokens} local key = KEYS[1] local capacity = tonumber(ARGV[1]) local refill_rate = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local requested = tonumber(ARGV[4]) local bucket = redis.call('HMGET', key, 'tokens', 'last_refill') local tokens = tonumber(bucket[1]) local last_refill = tonumber(bucket[2]) if tokens == nil then tokens = capacity last_refill = now end -- Refill tokens based on elapsed time local elapsed = math.max(0, now - last_refill) tokens = math.min(capacity, tokens + (elapsed * refill_rate)) local allowed = 0 local remaining = tokens if tokens >= requested then tokens = tokens - requested allowed = 1 remaining = tokens end redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now) redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2) return {allowed, remaining} ``` **Verify**: `redis-cli EVAL "$(cat token_bucket.lua)" 1 "ratelimit:user123" 10 1 $(date +%s) 1` → `{1, 9}` (allowed, 9 tokens remaining) ### 3. Add response headers Communicate rate-limit state back to clients so they can self-throttle. Use the IETF draft standard headers. [src7] ``` HTTP/1.1 200 OK X-RateLimit-Limit: 100 X-RateLimit-Remaining: 42 X-RateLimit-Reset: 1708732800 Retry-After: 30 # Only on 429 responses HTTP/1.1 429 Too Many Requests X-RateLimit-Limit: 100 X-RateLimit-Remaining: 0 X-RateLimit-Reset: 1708732800 Retry-After: 30 Content-Type: application/json {"error": "rate_limit_exceeded", "message": "Rate limit of 100 requests/min exceeded. Retry after 30 seconds."} ``` **Verify**: Check client receives correct headers — `curl -v https://api.example.com/endpoint 2>&1 | grep X-RateLimit` ### 4. Deploy Redis with high availability A single Redis instance is a single point of failure. Use Redis Sentinel or Redis Cluster for production. [src3] ```yaml # Redis Sentinel configuration (sentinel.conf) sentinel monitor mymaster 10.0.0.1 6379 2 sentinel down-after-milliseconds mymaster 5000 sentinel failover-timeout mymaster 10000 sentinel parallel-syncs mymaster 1 # Application connection (use sentinel-aware client) # Python: redis-py with SentinelConnectionPool # Node.js: ioredis with sentinels option ``` **Verify**: `redis-cli -p 26379 SENTINEL master mymaster` → confirms master is up and replicas are connected. ### 5. Implement fallback for Redis outages Rate limiters must handle Redis failures gracefully. Decide on fail-open (allow all) or fail-closed (reject all) based on your use case. [src1] ``` Fallback strategy: 1. Try Redis rate-limit check (Lua script) 2. If Redis unavailable (timeout/connection error): a. Security-critical (auth, payment): FAIL CLOSED → reject with 503 b. General API: FAIL OPEN → allow request, log the bypass c. Optional: fall back to in-memory approximate counter per node 3. Set circuit breaker: stop retrying Redis for 30s after 3 consecutive failures 4. Alert on fallback activation — extended Redis outage needs manual intervention ``` **Verify**: Kill Redis replica, confirm application logs fallback activation and requests are handled per policy. ### 6. Configure tiered rate limits Different clients need different limits. Implement a hierarchical rule system. [src1] [src6] ``` Rate-limit tiers (example): free_tier: 100 req/min, 1000 req/hour pro_tier: 1000 req/min, 50000 req/hour enterprise: 10000 req/min, unlimited/hour Per-endpoint overrides: POST /api/search: 50 req/min (expensive query) GET /api/status: 600 req/min (lightweight) POST /api/payments: 20 req/min (critical, strict limit) Priority classification (Stripe model): P0 — Critical (payments, charges): never shed P1 — POST operations: shed at 90% capacity P2 — GET operations: shed at 80% capacity P3 — Test mode / analytics: shed at 70% capacity ``` **Verify**: Send requests with different API keys → confirm each tier receives its correct `X-RateLimit-Limit` value. ## Code Examples ### Python: Redis-Based Sliding Window Counter > Full script: [python-redis-based-sliding-window-counter.py](scripts/python-redis-based-sliding-window-counter.py) (45 lines) ```python # Input: client_key (str), max_requests (int), window_seconds (int) # Output: (allowed: bool, remaining: int, retry_after: int) # Requires: redis>=5.0.0 import time import redis # ... (see full script) ``` ### Node.js: Express Middleware Rate Limiter > Full script: [node-js-express-middleware-rate-limiter.js](scripts/node-js-express-middleware-rate-limiter.js) (61 lines) ```javascript // Input: Express request object // Output: next() if allowed, 429 response if rate-limited // Requires: ioredis@^5.0.0, express@^4.18.0 const Redis = require('ioredis'); // Token bucket via Lua — atomic check-and-consume [src3][src4] # ... (see full script) ``` ## Anti-Patterns ### Wrong: Non-atomic read-then-write counter ```python # BAD — race condition: two concurrent requests both read count=99 (limit=100), # both increment to 100, both pass. Actual count = 101, limit bypassed. count = redis_client.get(f"rl:{client_id}") if int(count or 0) < rate_limit: redis_client.incr(f"rl:{client_id}") allow_request() else: reject_request() ``` ### Correct: Atomic Lua script ```python # GOOD — entire read-check-increment runs atomically in Redis [src3] result = redis_client.eval(""" local count = redis.call('INCR', KEYS[1]) if count == 1 then redis.call('EXPIRE', KEYS[1], ARGV[2]) end if count > tonumber(ARGV[1]) then return 0 else return 1 end """, 1, f"rl:{client_id}", rate_limit, window_seconds) ``` ### Wrong: Fixed window without boundary burst protection ```python # BAD — client sends 100 requests at 0:59 and 100 at 1:00. # Each window sees 100 (within limit), but 200 requests hit in 2 seconds. window = int(time.time() / 60) key = f"rl:{client_id}:{window}" count = redis_client.incr(key) ``` ### Correct: Sliding window counter to smooth boundaries ```python # GOOD — weighted average across adjacent windows prevents boundary burst [src2] # Cloudflare approach: estimated = prev_count * ((window - elapsed) / window) + curr_count # At 0:45 with 60s window: weight = (60-45)/60 = 0.25, so 25% of previous window counts ``` ### Wrong: Storing rate-limit state only in application memory ```python # BAD — each server tracks independently. 4 servers with 100/min limit # means client can actually send 400/min across the fleet. request_counts = {} # In-memory dict — not shared across instances def check_rate(client_id): request_counts[client_id] = request_counts.get(client_id, 0) + 1 return request_counts[client_id] <= 100 ``` ### Correct: Centralized counter store (Redis) ```python # GOOD — all instances share the same counter via Redis [src3] # One source of truth, atomic operations, TTL-based cleanup result = redis_client.evalsha(script_sha, 1, f"rl:{client_id}", max_requests, window_seconds, time.time()) ``` ### Wrong: No TTL on rate-limit keys ```python # BAD — keys accumulate forever, Redis memory grows unbounded redis_client.hmset(f"rl:{client_id}", {"tokens": tokens, "ts": now}) # No EXPIRE set — if client disappears, key stays forever ``` ### Correct: Always set TTL on rate-limit keys ```python # GOOD — TTL = 2x window ensures cleanup even with clock drift redis_client.hmset(f"rl:{client_id}", {"tokens": tokens, "ts": now}) redis_client.expire(f"rl:{client_id}", window_seconds * 2) # Or set TTL inside Lua script for atomicity (preferred) ``` ## Common Pitfalls - **Race conditions from non-atomic operations**: Two concurrent requests both read the same counter value, both pass the check, both increment — actual count exceeds limit. Fix: use Redis Lua scripts (`EVAL`/`EVALSHA`) to make read-check-increment atomic. [src3] - **Fixed-window boundary burst**: A client sends max requests at the end of window N and max at the start of window N+1, effectively doubling throughput in a short period. Fix: use sliding window counter (weighted average of adjacent windows) as Cloudflare does. [src2] - **Redis SPOF causing total outage**: If the single Redis instance goes down and your rate limiter has no fallback, all requests are either blocked or unthrottled. Fix: deploy Redis Sentinel or Cluster; implement in-memory fallback with circuit breaker. [src1] - **Clock skew in distributed nodes**: Different servers have clocks offset by seconds, causing inconsistent window boundaries — some servers reject requests that others allow. Fix: use wall-clock-aligned windows (e.g., `floor(timestamp / window) * window`) and keep NTP synchronized. [src5] - **Forgetting Retry-After header on 429 responses**: Clients without backoff guidance will retry immediately, creating a thundering herd. Fix: always include `Retry-After` header with seconds until the window resets. [src7] - **Over-granular rate-limit keys**: Using `user_id + endpoint + method + IP` creates millions of unique keys, consuming excessive Redis memory. Fix: keep keys at the right granularity — usually `user_id` or `api_key` + optional endpoint grouping. [src1] - **Not differentiating request priority**: Treating all requests equally means low-priority analytics calls consume the same budget as critical payment operations. Fix: implement tiered load shedding — Stripe classifies traffic into 4 priority levels and sheds low-priority first. [src1] - **Testing rate limits only at low traffic**: Rate limiters that work at 10 req/sec may fail at 10K req/sec due to Redis latency or Lua script contention. Fix: load test with production-scale traffic; benchmark Redis latency under concurrent `EVALSHA` calls. [src4] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Protecting APIs from abuse (brute force, scraping) | Single-server application with no distributed requirements | In-process rate limiter (Guava, Go rate, node-rate-limiter-flexible) | | Enforcing SLA/tier-based API quotas | Need to block L3/L4 DDoS attacks | Network-level DDoS mitigation (Cloudflare, AWS Shield, Cloud Armor) | | Preventing resource exhaustion in microservices | Service is failing (unhealthy, not overloaded) | Circuit breaker pattern (Resilience4j, Polly, Hystrix) | | Multi-datacenter API with shared rate limits | Rate limiting is per-user with small user base and single server | Simple in-memory counter with mutex | | Cost control for expensive downstream calls (LLM APIs, payment processors) | Need request queuing with guaranteed delivery | Message queue (RabbitMQ, SQS) with consumer rate control | ## Important Caveats - Sliding window counter (Cloudflare approach) is an approximation — Cloudflare reports 0.003% error rate across 400M requests, which is acceptable for most use cases but not for billing-precise metering [src2] - Redis Cluster splits keyspace into 16384 hash slots — ensure your rate-limit key hashing distributes evenly; use hash tags `{user_id}` if you need related keys on the same shard - Token bucket `capacity` and `refill_rate` are independent parameters — capacity controls burst size, refill_rate controls sustained throughput; misconfiguring either produces unexpected behavior - Lua scripts block the Redis event loop during execution — keep scripts under 100 microseconds; complex scripts at high concurrency will increase p99 latency for all Redis operations - Distributed rate limiting with strict consistency requires synchronous Redis calls on the hot path — this adds 1-5ms latency per request; if sub-millisecond latency is critical, consider local approximate counting with periodic sync ## Related Units - [PostgreSQL Connection Pool Exhaustion](/software/debugging/postgresql-connection-pool/2026) - [Monolith to Microservices Migration](/software/migrations/monolith-to-microservices/2026)