Designing Rate Limiters: Algorithms, Distributed Systems, and Tradeoffs

Introduction

Rate limiters protect APIs, databases, and third-party integrations from abuse and overload. They cap how many requests a client can make in a time window—enforcing fair usage, preventing DDoS adjacency, and controlling cost on metered services.

Designing rate limiters spans algorithm choice (token bucket vs sliding window), single-node vs distributed storage (Redis), HTTP response semantics (429, Retry-After), and placement (edge gateway vs service mesh vs application). This article compares approaches and shows production-ready patterns.

Table of Contents

• Why Rate Limiting Matters
• Fixed Window Counter
• Sliding Window Log
• Sliding Window Counter
• Token Bucket and Leaky Bucket
• Distributed Rate Limiting with Redis
• API Gateway and Edge Limiting
• Best Practices
• Common Mistakes
• Interview Questions
• Summary
• References

Why Rate Limiting Matters

Without limits:

• One client can exhaust DB connections or CPU
• Brute-force attacks on auth endpoints succeed faster
• SaaS margins erode on unlimited API usage
• Cascading failures propagate when downstream has no backpressure

Rate limiting provides backpressure at the boundary. Pair with authentication, WAF, and quotas for tiered plans.

Fixed Window Counter

Count requests per clock window (e.g. per minute):

# Pseudocode
window_key = f"rate:{user_id}:{current_minute}"
count = INCR(window_key)
if count == 1:
    EXPIRE(window_key, 60)
if count > LIMIT:
    reject()

Pros: Simple, memory efficient.

Cons: Burst at window edges—100 requests at 00:59 and 100 at 01:00 = 200 in 2 seconds while limit is 100/minute.

Sliding Window Log

Store timestamps of each request in a sorted set or list; remove entries older than window; count remaining.

MULTI
ZREMRANGEBYSCORE rate:user:1 0 (now - window_ms)
ZADD rate:user:1 now request_id
ZCARD rate:user:1
EXPIRE rate:user:1 window_seconds
EXEC

Pros: Accurate smooth limiting.

Cons: Memory per request—expensive at high QPS.

Sliding Window Counter

Hybrid: combine previous window count with current window weighted by elapsed fraction:

estimated = prev_count * (1 - elapsed/window) + current_count
if estimated > limit: reject

Good balance of accuracy and memory—used by many API gateways.

Token Bucket and Leaky Bucket

Token bucket: Bucket holds capacity tokens; refill at rate tokens/sec. Each request consumes one token; reject if empty. Allows bounded bursts while maintaining average rate.

class TokenBucket {
  constructor(capacity, refillPerSec) {
    this.capacity = capacity;
    this.tokens = capacity;
    this.refillPerSec = refillPerSec;
    this.lastRefill = Date.now();
  }

  allow() {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.refillPerSec);
    this.lastRefill = now;
    if (this.tokens < 1) return false;
    this.tokens -= 1;
    return true;
  }
}

Leaky bucket: Requests queue; processed at fixed rate—smoother output, can queue or drop overflow.

Token bucket is common for APIs needing burst tolerance (Stripe, AWS style).

Distributed Rate Limiting with Redis

Single-node in-memory limiters fail with multiple app instances. Redis centralizes counters:

-- Atomic token bucket sketch in Redis with Lua
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
-- ... load tokens, refill, decrement, SET

Use Lua scripts or Redis Cell module for atomicity. Handle Redis failures—fail open (allow) vs fail closed (reject) is a product decision.

Sharding: High-cardinality keys (user_id) distribute naturally. Hot keys (global limit) need dedicated treatment.

API Gateway and Edge Limiting

Limit at CDN/edge (Cloudflare, AWS WAF) for cheap rejection before origin.

Kong, Envoy, NGINX support rate limit plugins. Application-level limits remain useful for fine-grained rules (per endpoint cost).

HTTP response:

HTTP/1.1 429 Too Many Requests
Retry-After: 32
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1704067200

Document limits in API docs and OpenAPI.

Best Practices

1. Identify limit key—IP, user ID, API key, combination.
2. Tier limits—free vs paid; different endpoints different costs.
3. Return actionable 429 with Retry-After and remaining quota headers.
4. Monitor reject rates—alert on spikes (attack or misconfigured client).
5. Test limit behavior in integration tests.
6. Coordinate with idempotency—retries should not double-charge quota unfairly.

Common Mistakes

1. Fixed window without awareness of edge burst problem.
2. Non-atomic counters in distributed env—race allows excess.
3. Limiting by IP only—NAT and mobile carriers share IPs.
4. No bypass for health checks—killed by orchestrator.
5. Fail closed on Redis outage—total outage vs abuse tradeoff ignored.
6. Same limit for read and write—expensive writes need stricter caps.

Interview Questions

1. Compare fixed window, sliding window, and token bucket.
2. How to implement distributed rate limiting?
3. What is the burst problem in fixed windows?
4. Token bucket vs leaky bucket?
5. Where to place rate limiters in architecture?
6. How to rate limit GraphQL (cost-based)?
7. Redis down—fail open or closed?
8. Design rate limiter for 1M QPS API.

Rate Limiting in Multi-Region Deployments

Global APIs face uneven traffic—US peak differs from EU. Regional counters in Redis with local aggregation:

[US API] → Redis US (user:123 → 45 req/min)
[EU API] → Redis EU (user:123 → 12 req/min)
Global limit 100/min → sum regions at edge or sync periodically

Strict global limits need cross-region Redis replication or centralized limiter service—latency tradeoff.

Adaptive limits increase caps for trusted enterprise customers via API key metadata stored with limit tiers.

Client SDK Guidance

Document retry behavior for 429 responses:

async function fetchWithRetry(url: string, options: RequestInit, maxRetries = 3) {
  for (let i = 0; i < maxRetries; i++) {
    const res = await fetch(url, options);
    if (res.status !== 429) return res;
    const retryAfter = Number(res.headers.get("Retry-After") || 1);
    await sleep(retryAfter * 1000);
  }
  throw new Error("Rate limited");
}

Exponential backoff with jitter prevents retry storms after outages.

Observability

Track metrics:

• rate_limit_rejected_total by client tier and endpoint
• P99 latency of limiter check (Redis round-trip)
• False positive rate if using anomaly detection

Sudden rejection spikes may indicate attack, misconfigured client, or limit set too aggressively after product launch.

Gateway Rate Limiting vs Application

Layer	Pros	Cons
Edge/Gateway	Cheap rejection, DDoS absorption	Coarse rules
Application	Per-user tier, endpoint cost	Uses app CPU
Database	Last resort	Too late

Layer limits: edge blocks obvious abuse; app enforces business tiers; sensitive endpoints have stricter per-route limits.

app.use("/api/search", rateLimit({ max: 30 }));
app.use("/api/export", rateLimit({ max: 5 }));

Distributed Rate Limiter Failure Modes

When Redis is unavailable:

• Fail open — availability over abuse protection (consumer apps)
• Fail closed — security over availability (auth, payment)
• Local fallback — in-memory limit per instance (uneven but bounded)

Document and drill the chosen policy—incident playbooks should not debate fail mode during outage.

Review rate limit thresholds quarterly against actual traffic growth—limits set at launch become bottlenecks after tenfold user growth unless product and infrastructure teams revisit caps together with data showing p99 utilization per tier and rejection rates normalized by legitimate usage patterns rather than attack traffic alone.

Summary

Rate limiters combine algorithms, distributed state, and HTTP semantics. Token bucket and sliding window counter cover most API needs; Redis provides shared atomic state; edge gateways drop junk early. Choose keys and tiers deliberately, return clear 429 responses, and monitor rejection patterns as security and capacity signals.

References

• Stripe — Rate Limiters
• AWS — Token Bucket
• Redis — INCR rate limiting
• Google SRE — Handling overload
• MDN — 429 Too Many Requests