Design rate limiting for a public API with tiered plans

➔? Design rate limiting for a public REST API where free users get 100 req/min and paid users 2,000 req/min, keyed by API key

Concepts Involved

Rate Limiting API Gateway Redis REST APIs Consistent Hashing

Problem Statement

Design a rate limiter for a public REST API that enforces different limits based on subscription tier (free: 100 req/min, paid: 2,000 req/min), keyed by API key, while being fair at scale and providing clear feedback to clients.

Core challenge: Multiple tiers mean the limiter must look up tier config per request, apply per-key counters with different thresholds, and handle tier upgrades/downgrades in real-time without restarting services or losing counter state.

100

req/min (free tier)

2,000

req/min (paid tier)

API Key

rate limit key

429

Too Many Requests

Functional Requirements

What the system must do · the core rate limiting behaviours

Must Have (Core)

1. Enforce per-key rate limits based on API key identity
2. Support tiered plans (free: 100 req/min, paid: 2,000 req/min, enterprise: 10K req/min)
3. Return standard rate limit headers (X-RateLimit-Limit, Remaining, Reset)
4. Reject excess requests with 429 Too Many Requests + Retry-After
5. Real-time tier change propagation when billing tier is upgraded/downgraded

Out of Scope (this design)

✗ DDoS mitigation (L3/L4 volumetric attack protection)
✗ Geographic distribution (multi-region rate limiting coordination)
✗ Per-endpoint limits (this design is per-key only, not per-route)
✗ Billing / usage analytics (separate metering pipeline)
✗ IP-based rate limiting (complementary but separate concern)

Non-Functional Requirements

The quality constraints that shape every architectural decision

Property	Target	Why It Matters / Design Impact
Latency	<2ms overhead per request	Redis RTT in same datacenter. Rate check must be invisible to end-user experience.
Throughput	100K+ rate-check operations/sec	Every inbound API request hits the rate limiter. Must handle full platform traffic.
Availability	99.99% (fail-open if Redis down)	Rate limiter failure must not become a platform outage. Fail-open with degraded local limits.
Accuracy	±1 request at window boundaries	Sliding window counter provides near-exact enforcement without memory cost of full log.
Scalability	Linear with number of unique API keys	Redis sharding by key hash. Each shard handles a subset of keys independently.

Key tension: Availability vs. Accuracy. We choose availability · if Redis is unreachable, allow traffic through (fail-open) rather than blocking legitimate customers. Sliding window counter trades perfect accuracy for memory efficiency.

Scale Estimation

Given numbers from the question → derive infrastructure sizing

Given (from question): 100K active API keys · 50% free (100 req/min) · 40% paid (2,000 req/min) · 10% enterprise (10K req/min)

Step	What to Derive	Calculation	Result	Design Decision
1	Peak rate checks/sec	100K keys checking simultaneously (worst case)	~150K peak	Single Redis instance handles 1M ops/sec · comfortable headroom
2	Average rate checks/sec	50K free + 40K paid + 10K enterprise, weighted by activity	~50K avg	No need for Redis Cluster at this scale · single primary + replica
3	Redis memory	100K keys × 3 fields (count, prev_count, window_ts) × ~100 bytes	~10MB	Trivial memory footprint. Fits in any Redis instance easily.
4	Redis ops/sec	150K INCR/sec at peak	150K ops/sec	Well within single Redis capacity (1M+ ops/sec). No sharding needed yet.
5	Network bandwidth	150K round trips/sec × ~200 bytes each	~30MB/sec	Standard 1Gbps link handles this easily.

Interview tip: Start with the number of unique API keys (defines memory), then derive peak ops/sec (defines Redis throughput needs). The key insight: rate limiting is extremely lightweight per-key — a single Redis instance can handle millions of keys.

APIs

Rate limit middleware intercepts all API requests · transparent to endpoint handlers

ANY /* (all endpoints)

Rate limit middleware intercepts BEFORE handler execution. Extracts API key from Authorization header or X-API-Key header.

// Response headers (always included)

X-RateLimit-Limit: 2000

X-RateLimit-Remaining: 1847

X-RateLimit-Reset: 1705312260

Retry-After: 12 // only on 429

429 Too Many Requests

Returned when sliding window count exceeds tier limit. Client should back off and retry after the specified time.

// 429 Response Body

{

  "error": "rate_limit_exceeded",

  "message": "API rate limit exceeded for your plan",

  "limit": 100,

  "reset_at": "2025-01-15T10:31:00Z",

  "upgrade_url": "https://api.example.com/billing/upgrade"

}

Data Model

Redis key schemas for rate counters + config DB for tier lookup

Redis · Sliding Window Counters

// Current window counter (TTL: 120s — covers current + overlap period)
ratelimit:{api_key}:{window_minute} → INTEGER (curr_count)
  Example: ratelimit:sk_free_abc:1705312200 → 47

// Previous window counter (TTL: 120s)
ratelimit:{api_key}:prev → INTEGER (prev_count)
  Example: ratelimit:sk_free_abc:prev → 92

// Weighted calculation: curr + prev × (1 - elapsed/60)

Config DB · Tier Configuration

// api_keys table
+-----------+------------+--------+-----------+------------+------------+
| api_key   | account_id | tier   | limit_rpm | burst_size | created_at |
+-----------+------------+--------+-----------+------------+------------+
| sk_free_* | acc_123    | free   | 100       | 20         | 2025-01-01 |
| sk_paid_* | acc_456    | paid   | 2000      | 200        | 2025-01-05 |
| sk_ent_*  | acc_789    | enterprise | 10000 | 1000       | 2025-01-10 |
+-----------+------------+--------+-----------+------------+------------+

// Cached in-memory per gateway (refreshed every 30s or on billing event)

Architecture · Sliding Window Counter with Tier Lookup

Per-key sliding window counters backed by Redis, with tier config loaded from a rules cache

Decision	Choice	Why
Algorithm	Sliding window counter (weighted two-bucket)	Smooth limiting without boundary burst. Simple to implement, memory-efficient.
Key	API key (from header or query param)	Per-customer identity. Maps 1:1 to billing tier.
Tier lookup	In-memory rules cache (refreshed every 30s from config DB)	Fast lookup without per-request DB hit. Tier changes propagate within 30s.
Storage	Redis HASH per key: {curr_count, prev_count, window_start}	Atomic operations, TTL-based cleanup, shared across app servers.
Response	429 + RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset, Retry-After	RFC 6585 compliant. Client can self-throttle.
Fairness	Per-key isolation (one key's traffic never affects another)	Free tier abuse cannot degrade paid tier experience.

Sliding window counter: For a 1-minute window — maintain two buckets (current minute, previous minute). Weighted count = current_count + previous_count × (1 − elapsed_seconds/60). If weighted ≥ tier_limit → reject with 429.

Token bucket alternative: If the API needs burst tolerance (e.g., paid users can burst to 200 req in first second), token bucket is better. Capacity = burst size, refill rate = steady limit. But for strict "100 per minute" semantics, sliding window is cleaner.

Anti-patterns: Fixed window · allows 2× limit at boundary (200 free requests in 2 seconds spanning two minutes). In-memory counters without shared store · user can rotate across servers to bypass. Hardcoded limits · can't change tiers without deployment.

Real-world examples: Stripe · 100 req/sec (test), 10K req/sec (live). GitHub · 60 req/hr (unauth), 5000 req/hr (auth). OpenAI · tier-based RPM + TPM. Twilio · per-account concurrency limits.

Resilience & Edge Cases

Failure	Impact	Recovery
Redis down	Cannot check/increment counters	Fail-open with degraded local counters. Alert on Redis health. Circuit breaker on Redis calls.
Tier config stale	Upgraded user still rate-limited at old tier	30s cache TTL. Force-refresh endpoint for billing system to call on tier change.
API key rotation	New key has fresh counters (bypass)	Rate limit by account_id as secondary key. Key rotation doesn't reset counter.
Burst at window edge	Sliding window smooths this naturally	Weighted calculation handles boundary precisely.
Hot key (one API key = massive traffic)	Redis hotspot on that key's shard	Local pre-check with approximate counter. Only hit Redis when near threshold.

Interview Cheat Sheet

Key points for tiered API rate limiting

1. Sliding window counter · two-bucket weighted sum prevents boundary burst
2. Redis as shared counter store · atomic INCR, TTL-based expiry, works across all app servers
3. Tier lookup from config cache · in-memory rules refreshed every 30s, no per-request DB call
4. Per-key isolation · one customer's abuse never affects another's quota
5. Standard headers · RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset + Retry-After
6. Graceful tier changes · cache refresh propagates upgrades within seconds, counter resets optional

System Design Case Study