Rate Limiting

One-line summary: Rate limiting caps how many requests a client can make in a time window — protecting your system from abuse, overload, and runaway costs while ensuring fair use.

🧩 Core Concepts — Why Rate Limit?

Without limits, a single client (buggy loop, scraper, or attacker) can exhaust your capacity and degrade service for everyone. Rate limiting enforces a quota per client, endpoint, or API key.

Why it matters:

Prevent abuse & DoS — block brute-force logins and floods.
Ensure fairness — no single tenant starves others.
Control cost — cap usage of expensive downstream calls (e.g., paid APIs, LLMs).
Protect stability — shed excess load before it topples the system.

flowchart LR
    C[Client requests] --> RL{Within limit?}
    RL -->|Yes| Fwd[Forward to service]
    RL -->|No| Rej[Reject with 429]
    Fwd --> S[Backend Service]

🎛️ Rate Limiting Algorithms

Each algorithm trades memory, accuracy, and burst behavior differently.

flowchart TD
    A[Algorithms] --> TB[Token Bucket]
    A --> LB[Leaking Bucket]
    A --> FW[Fixed Window Counter]
    A --> SL[Sliding Window Log]
    A --> SC[Sliding Window Counter]

Token Bucket

A bucket holds up to N tokens and refills at a steady rate. Each request consumes one token; if the bucket is empty, the request is rejected. Allows short bursts (up to bucket size) while enforcing an average rate. Widely used (e.g., API gateways, AWS).

flowchart LR
    Refill[Refill r tokens/sec] --> Bucket[(Bucket capacity N)]
    Req[Request] -->|take 1 token| Bucket
    Bucket -->|token available| Allow[Allow]
    Bucket -->|empty| Deny[Reject 429]

Leaking Bucket

Requests enter a queue (bucket) and are processed ("leak") at a fixed constant rate. Smooths bursts into a steady output stream. Great when the downstream needs a stable rate; excess overflows and is dropped.

Fixed Window Counter

Count requests per fixed interval (e.g., 100/min). Simple and memory-cheap, but suffers the boundary burst problem: a client can send 100 at 0:59 and 100 at 1:00 — 200 in ~2 seconds.

Sliding Window Log

Store a timestamp for every request and count those within the trailing window. Perfectly accurate, but memory grows with request volume — expensive at scale.

Sliding Window Counter

A hybrid: combines the current and previous fixed-window counts, weighted by how far into the current window we are. Approximates the sliding log with tiny memory — the popular production sweet spot.

flowchart LR
    Prev[Previous window count] --> Calc[weighted sum]
    Cur[Current window count] --> Calc
    Calc --> Decision{<= limit?}
    Decision -->|Yes| Allow
    Decision -->|No| Deny[429]

Algorithm	Bursts	Accuracy	Memory	Notes
Token Bucket	Allows bursts	Good	Low	Average rate + burst cap
Leaking Bucket	Smooths bursts	Good	Low–med (queue)	Constant output rate
Fixed Window	Boundary bursts	Low	Very low	Simplest
Sliding Log	No bursts	Exact	High	Costly at scale
Sliding Counter	Minimal	High (approx)	Low	Best general choice

🌐 Distributed Rate Limiting

With many app servers behind a load balancer, each instance seeing only its own traffic can't enforce a global limit. The counter must live in a shared, fast store — typically Redis (see Caching) — so all instances share one source of truth.

flowchart TD
    C[Client] --> LB[Load Balancer]
    LB --> A1[App Server 1]
    LB --> A2[App Server 2]
    LB --> A3[App Server 3]
    A1 --> R[(Redis - shared counter)]
    A2 --> R
    A3 --> R
    R --> Verdict{Over limit?}

Atomicity — use atomic ops (Redis INCR/Lua scripts) so concurrent updates don't race.
Latency vs. accuracy — a central store is accurate but adds a network hop; some systems allow small per-node quotas for speed and reconcile centrally.
Consistency — relates to broader trade-offs in Consistency Models.

📍 Where to Place Rate Limiting

flowchart LR
    Client --> Edge[CDN / Edge]
    Edge --> GW[API Gateway / L7 LB]
    GW --> Svc[Service]
    Svc --> Down[Downstream / DB]

Edge / CDN — stops floods before they reach your infrastructure.
API Gateway / L7 load balancer — the most common place; centralized policy per API key/route (see API Design).
Within a service / microservice — fine-grained, business-aware limits (e.g., per-user-tier quotas).

Rule of thumb: limit as early (close to the edge) as possible to save resources, but add finer per-user/per-endpoint limits deeper in where business context lives.

📡 Response Handling (HTTP 429)

When a client exceeds the limit, return 429 Too Many Requests with headers so well-behaved clients can back off:

Retry-After: 30 — seconds to wait before retrying.
X-RateLimit-Limit — the ceiling for the window.
X-RateLimit-Remaining — requests left in the current window.
X-RateLimit-Reset — when the window resets.

sequenceDiagram
    participant C as Client
    participant R as Rate Limiter
    C->>R: Request (over limit)
    R-->>C: 429 Too Many Requests<br/>Retry-After: 30<br/>X-RateLimit-Remaining: 0
    Note over C: wait, then retry with backoff

Client best practice: honor Retry-After and use exponential backoff with jitter to avoid synchronized retry storms.

⚖️ Trade-offs / When to Use

Accuracy vs. cost. Sliding-window-log is exact but memory-heavy; sliding-window-counter or token bucket give near-exact results cheaply — preferred for most APIs.
Burst tolerance. Token bucket permits bursts (good UX); leaking bucket enforces a strict smooth rate (protects fragile downstreams).
Local vs. distributed. Per-node limiting is fast but inaccurate globally; a shared store is accurate but adds latency and a dependency.
Fail open vs. fail closed. If the rate-limit store is down, decide whether to allow traffic (availability) or block it (protection) — a classic availability-vs-safety choice.
Don't over-restrict. Aggressive limits harm legitimate users; tune with real traffic data and offer higher tiers where appropriate.

Note (AI-assisted draft): The following Interview Questions, Production Checklist, and Testing & Monitoring items are a draft. Add links to throttling dashboards and SDK guidelines where available.

Interview Questions (expanded answers)

When would you choose a distributed token bucket vs per-node local quotas?

Distributed token bucket: choose when you need precise global quotas (tenant-level rate limits) and when fairness is critical. Requires a shared store (Redis, Cloud provider) and atomic operations.
Per-node local quotas: choose when per-request latency must be minimal and a small, bounded inaccuracy is acceptable. Combine with periodic central reconciliation or soft limits to maintain fairness.

Hybrid approach: allow small local bursts (local tokens) and periodically reconcile or check central counters for sustained enforcement.

How do you implement a global rate limiter with low latency and acceptable accuracy?

Pattern options:

Centralized accurate limiter: Redis Lua scripts (INCR + TTL), atomic counters, single source-of-truth — accurate but adds a network hop.
Edge-first approach: enforce coarse limits at CDN/edge, refine at API gateway with central store for strict quotas.
Approximate/local caches: grant local permits for short windows, then check central store for long-lived enforcement.

Key practices: use atomic operations, add metrics for false positives/negatives, and cache decisions briefly to reduce central load.

Describe the client and server behavior when throttled — how should SDKs politely back off?

Server behavior:

Return 429 Too Many Requests with Retry-After, X-RateLimit-* headers and an explanatory body.
Optionally include a quota window expiry or suggested retry delay.

Client/SDK behavior:

Honor Retry-After when present; otherwise use exponential backoff with jitter.
Mark non-idempotent operations with idempotency keys so safe retries are possible.
Surface rate-limit metrics to telemetry so operators can tune policies.

Production Checklist

Monitor global and per-key request rates, latency, and 429 metrics
Implement and test DLQ-like behavior for excessive clients (e.g., blocking or blacklisting)
Ensure Redis (or chosen store) is highly available and instrumented when used for counters
Provide clear client-facing headers and documented retry semantics
Publish SDK guidance: retry with exponential backoff + jitter and respect Retry-After

Testing & Monitoring

Load test under bursty and steady high-load patterns and measure false positives/negatives
Test fail-open vs fail-closed behavior of the limiter when the shared store is unavailable
Verify correct operation across multiple regions and with CDNs at the edge
Simulate latency-sensitive endpoints to validate early rejection and edge-rate limiting

Load Balancing — the L7 gateway is the usual enforcement point
Caching — Redis as the shared counter store
Microservices — per-service and per-tenant limits
API Design — quota policies, keys, and 429 semantics
Consistency Models — accuracy trade-offs of distributed counters
Scalability — rate limiting protects capacity under load
Heap — priority queues used in scheduling/limiters

🧩 Core Concepts — Why Rate Limit?​

🎛️ Rate Limiting Algorithms​

Token Bucket​

Leaking Bucket​

Fixed Window Counter​

Sliding Window Log​

Sliding Window Counter​

🌐 Distributed Rate Limiting​

📍 Where to Place Rate Limiting​

📡 Response Handling (HTTP 429)​

⚖️ Trade-offs / When to Use​

Interview Questions (expanded answers)​

When would you choose a distributed token bucket vs per-node local quotas?​

How do you implement a global rate limiter with low latency and acceptable accuracy?​

Describe the client and server behavior when throttled — how should SDKs politely back off?​

Production Checklist​

Testing & Monitoring​

🔗 Related Topics​