Walkthrough 2 — Design a Rate Limiter

The brief

Build a rate-limiting service for an API gateway. Enforce per-user and per-IP limits across distributed gateway instances.

Step 1: Requirements

• Per-user limits (e.g., 100 req/min for free, 10K req/min for pro).
• Per-IP limits (anti-abuse).
• Per-endpoint limits (expensive endpoints get tighter quotas).
• Distributed: 10+ gateway instances share state.
• Low latency: each check < 5ms.
• Graceful degradation if rate-limit service is down.

Step 2: Pick an algorithm

Compare:

• Token bucket: bursty-tolerant; simple.
• Sliding window log: accurate; memory-heavy.
• Sliding window counter: good accuracy, low memory. Best choice.

Sliding window counter:

• Current window count + (previous window count × overlap fraction).
• Reset every window (e.g., 60s).
• Memory: 2 counters per (user, endpoint).

Step 3: Storage

Redis is the canonical choice:

• Atomic INCR.
• TTL for window expiration.
• Fast (< 1ms per check).

Schema:

Key: rate_limit:{user_id}:{endpoint}:{window_id}
Value: counter
TTL: 2 × window_size

Step 4: Algorithm pseudo-code

def is_allowed(user_id, endpoint, limit, window_sec):
    now = int(time.time())
    current_window = now // window_sec
    previous_window = current_window - 1

    current_count = redis.incr(f"rl:{user_id}:{endpoint}:{current_window}")
    redis.expire(f"rl:{user_id}:{endpoint}:{current_window}", 2 * window_sec)

    previous_count = int(redis.get(f"rl:{user_id}:{endpoint}:{previous_window}") or 0)

    elapsed_in_current = (now % window_sec) / window_sec
    overlap_fraction = 1 - elapsed_in_current
    effective_count = current_count + previous_count * overlap_fraction

    if effective_count > limit:
        return False
    return True

Step 5: Architecture

[Client]
   ↓
[API Gateway (many instances)]
   ↓  (check rate limit)
[Rate Limiter Service (or library call to Redis)]
   ↓
[Redis Cluster]

In practice: most gateways have rate limiting as a library call from each gateway instance to Redis. No need for a separate service.

Step 6: Configuration

Limits need to be configurable per user, tier, endpoint:

{
  "free_tier": {
    "default": "100/min",
    "/api/expensive": "10/min"
  },
  "pro_tier": {
    "default": "10000/min",
    "/api/expensive": "1000/min"
  }
}

Stored in a config service (Consul, etc.) or DB. Loaded by gateway with caching.

Step 7: Rate-limit response

When over limit:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1614556800
Retry-After: 60
Content-Type: application/json

{"error": "rate_limit_exceeded", "limit": 100, "window": "1 minute"}

Client implements exponential backoff.

Step 8: Graceful degradation

If Redis is down:

• Fail open (allow all requests): better UX, but no protection.
• Fail closed (reject all): protects backend but visible outage.
• Local fallback: each gateway falls back to per-instance counters (allows more than intended but still bounded).

Choice depends on use case: payments → fail closed; non-critical → fail open with alerting.

Step 9: Scaling

For very high QPS (millions/sec):

• Redis Cluster: shard by user_id.
• Hot users: a single celebrity user might exceed one Redis node. Shard their key across multiple nodes (read-then-aggregate).
• Local approximation: each gateway maintains a local counter; periodically syncs to Redis. Less accurate but no per-request Redis call.

For most apps: single Redis instance handles 100K+ ops/sec; sufficient.

Step 10: Monitoring

Metrics:

• Rate-limit hits per user/endpoint.
• 429 response rate.
• Redis latency from gateway.
• Cache hit rate (for limit configuration).

Alerts:

• High 429 rate (legitimate users being throttled?).
• Redis latency spikes (rate-limit service degraded).

Common follow-ups

• What if user has variable limits (paid by usage)? Real-time quota updates from billing service.
• What about burst tolerance? Add a token-bucket layer on top of sliding window.
• What if Redis dies mid-window? TTL ensures stale data clears; brief inaccuracy acceptable.
• API key vs user_id? Same algorithm; different key.

Self-rubric

• Chose appropriate algorithm (sliding window counter)
• Identified Redis as storage; explained atomicity
• Wrote correct pseudo-code (including overlap fraction)
• Designed 429 response with proper headers
• Handled graceful degradation
• Discussed scaling (Redis Cluster, hot keys)
• Identified monitoring needs

Deliverables

• Algorithm pseudo-code.
• Architecture diagram.
• Configuration format.
• 429 response format.