Chapter 66: Design Rate Limiter Service

1. Requirements

Functional Requirements

• Limit requests based on configurable rules (per-user, per-API endpoint, per-IP, global)
• Support multiple tenants with isolated rate limits
• Return clear feedback when limits are exceeded (429 status, retry headers)
• Support different time windows (seconds, minutes, hours, days)
• Allow rule updates without service restart

Non-Functional Requirements

• Low latency: Rate limit check must add minimal overhead (< 5ms)
• High availability: Service must not be a single point of failure
• Scalability: Handle millions of requests per second
• Accuracy: Limits should be enforced with reasonable precision (some over-limit allowed in distributed scenarios)
• Multi-tenant isolation: One tenant cannot exhaust resources for others

Capacity Estimation & Infrastructure Sizing

Target Scale

• Target: 1M rate-limited requests/sec across all tenants
• Each rate check = 2 Redis ops: GET current count + INCR. Total: 2M Redis ops/sec needed

Infrastructure Requirements

Scaling Tiers

Storage Notes

• Ephemeral data: Counters use TTL = window size (60s, 3600s, etc.)
• No persistent storage needed: All data is in-memory with TTL expiration
• Rule configuration: Stored in persistent DB (PostgreSQL/MySQL), cached in service memory

2. High-Level Design

Component Breakdown

• API Servers: Application servers that need rate limiting protection
• Rate Limiter Service: Middleware that intercepts requests, checks limits, and returns allow/deny decisions
• Redis Cluster: Distributed cache storing request counters with atomic operations
• Rule Engine: Configuration service managing rate limit rules (limits, windows, entity types)
• Admin Panel: Interface for configuring and updating rate limit rules

3. Algorithm: Sliding Window Counter

We use a sliding window counter algorithm that combines the benefits of fixed window (memory efficiency) and sliding window log (accuracy).

How It Works

1. Divide time into fixed windows (e.g., 1-minute buckets)
2. Track request count in current window and previous window
3. Calculate sliding window count using weighted formula:

   count = (prev_count * overlap_percentage) + current_count

4. Compare against limit and allow/deny request

Example Calculation

Limit: 100 requests per minute
Current time: 10:00:45 (45 seconds into current minute)

Previous window (9:59:00-10:00:00): 80 requests
Current window (10:00:00-10:01:00): 30 requests

Overlap: 15 seconds from previous window (25% of 60s)
Sliding count = (80 * 0.25) + 30 = 20 + 30 = 50 requests

50 < 100, so request is ALLOWED

4. Rule Engine

The rule engine manages multi-dimensional rate limiting with hierarchical rule evaluation.

Rule Types

Rule Configuration Schema

{
  "ruleId": "user_api_limit_001",
  "entityType": "user",
  "resource": "/api/v1/upload",
  "limit": 100,
  "window": 60,
  "windowUnit": "seconds",
  "priority": 1,
  "enabled": true,
  "tenantId": "tenant_123"
}

Rule Evaluation Order

1. Most specific rules first (user + API)
2. Medium specificity (per-user or per-API)
3. Least specific rules last (global, per-tenant)
4. Deny on first rule violation

5. Distributed Implementation

Redis Atomic Operations

Use Redis commands to ensure atomicity in distributed environment:

// Simple approach (race condition possible)
INCR rate:user:123:minute:12345
EXPIRE rate:user:123:minute:12345 60

// Better: Lua script for atomicity
EVAL "
  local current = redis.call('INCR', KEYS[1])
  if current == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[1])
  end
  return current
" 1 rate:user:123:minute:12345 60

Sliding Window Lua Script

-- keys: [current_key, previous_key]
-- args: [limit, current_window_start, previous_window_start, window_size]

local current = redis.call('GET', KEYS[1]) or 0
local previous = redis.call('GET', KEYS[2]) or 0
local now = tonumber(ARGV[2])
local prev_start = tonumber(ARGV[3])
local window = tonumber(ARGV[4])

local overlap_pct = (window - (now - prev_start)) / window
local sliding_count = math.floor(previous * overlap_pct + current)

if sliding_count < tonumber(ARGV[1]) then
  redis.call('INCR', KEYS[1])
  redis.call('EXPIRE', KEYS[1], window * 2)
  return {1, sliding_count + 1}
else
  return {0, sliding_count}
end

6. Response Handling

429 Too Many Requests

When rate limit is exceeded, return HTTP 429 with informative headers:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1620000000
Retry-After: 45
Content-Type: application/json

{
  "error": "Rate limit exceeded",
  "message": "You have exceeded the rate limit of 1000 requests per hour",
  "retryAfter": 45,
  "limit": 1000,
  "window": "1 hour"
}

Success Response Headers

Include rate limit info in all responses for client awareness:

HTTP/1.1 200 OK
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 847
X-RateLimit-Reset: 1620000000

Client Retry Strategy

• Clients should respect Retry-After header
• Implement exponential backoff for persistent failures
• Monitor X-RateLimit-Remaining to throttle proactively

7. Scalability and Performance

Redis Cluster Sharding

• Shard Redis by key hash (consistent hashing)
• Each shard handles a subset of users/keys
• Use Redis Cluster or client-side sharding

Caching Rate Limit Rules

• Cache rule configurations in rate limiter service memory
• Refresh cache every 30-60 seconds or on rule updates
• Reduces database load for rule lookups

Performance Optimizations

Handling Failures

• Redis unavailable: Fail open (allow requests) or fail closed (deny all) based on security requirements
• Timeout: Set aggressive timeouts (10-50ms) and fail open to avoid cascading failures
• Split-brain: Use Redis Sentinel or Cluster for automatic failover

8. Monitoring and Observability

Key Metrics

• Rate limit hit rate: % of requests rate limited (per rule, per tenant)
• Latency: P50/P95/P99 of rate limiter check latency
• Redis health: Connection pool usage, operation latency, error rate
• Rule effectiveness: Which rules are most frequently triggered
• False positives: Legitimate users hitting limits (tune rules)

Alerting

• Alert on Redis cluster degradation or failover
• Alert on rate limiter service latency > 10ms P95
• Alert on sudden spikes in rate limit hits (possible attack)

Summary

A production-grade rate limiter service requires:

• Sliding window counter algorithm for accuracy and efficiency
• Redis with Lua scripts for atomic distributed counters
• Flexible rule engine supporting multi-dimensional limits
• Clear HTTP responses with 429 status and retry headers
• Horizontal scaling via Redis sharding and stateless rate limiter services
• Graceful degradation when Redis is unavailable

The design balances performance (sub-5ms latency), scalability (millions of RPS), and reasonable accuracy (1-5% over-limit tolerance in race conditions).