Rate Limiter

Functional Requirements

• Rate limit requests per user, per IP address, or per API key based on configurable rules
• Support multiple rate limit rules: e.g., 100 requests/min for free tier, 1000 requests/min for premium tier
• Support different time windows: per second, per minute, per hour, per day
• Return clear error responses: HTTP 429 Too Many Requests with Retry-After header
• Allow rule updates without code deployments (dynamic configuration)

Non-Functional Requirements

• Low latency: Rate limit check adds less than 1ms overhead per request
• High availability: Rate limiter failure should not block legitimate traffic (fail open)
• Accurate counting: Counters must not drift significantly from actual values
• Distributed: Works correctly across hundreds of API servers
• Memory efficient: Storing counters for millions of users must not exhaust memory

Scale Estimation

Metric	Daily	Per Second
API requests	10B	~116K
Unique users	50M	-
Unique IPs	20M	-
Rate limit checks	10B	~116K
Redis operations	20B	~230K (read + write)

Core Entities

• RateLimitRule: user_id/IP/api_key, limit, window, tier
• Counter: key, count, window_start, ttl
• RateLimitResponse: allowed, remaining, reset_at, retry_after

Rate Limiting Algorithms

Token Bucket

• How it works: Bucket holds N tokens. Tokens are added at a fixed rate. Each request consumes one token. If bucket is empty, request is rejected.
• Parameters: bucket_size (max tokens), refill_rate (tokens per second)
• Pros: Allows controlled bursts up to bucket size, smooths traffic over time
• Cons: Two parameters to tune, slightly more complex than fixed window
• Best for: APIs that need burst tolerance

Bucket Size: 10 tokens
Refill Rate: 2 tokens/sec

Request 1: bucket=9   -> ALLOWED
Request 2: bucket=8   -> ALLOWED
Request 3: bucket=7   -> ALLOWED
... (8 more rapid requests exhaust bucket)
Request 11: bucket=0  -> REJECTED
Wait 0.5s -> bucket=1 -> Request 12: ALLOWED

Leaky Bucket

• How it works: Requests enter a FIFO queue (bucket). Requests leak out at a fixed rate. If queue is full, request is rejected.
• Parameters: bucket_size (queue capacity), leak_rate (requests per second)
• Pros: Produces perfectly smooth output rate
• Cons: Old requests may wait in queue adding latency, memory for queue
• Best for: Traffic shaping where smooth output matters (e.g., webhook delivery)

Queue: [req1, req2, req3, req4, req5]  (capacity=5)
Leak rate: 1 req/sec

req6 arrives -> queue full -> REJECTED
0.5s later -> req1 leaks out -> req6 -> ALLOWED (enters queue)

Fixed Window

• How it works: Divide time into fixed windows (e.g., 1-minute intervals). Count requests in current window. Reject if count exceeds limit.
• Parameters: limit, window_size (e.g., 60 seconds)
• Pros: Simple to implement, low memory (one counter per key per window)
• Cons: Burst at window boundary allows 2x traffic (e.g., 100 requests at 11:59:59 + 100 at 12:00:00 = 200 in 1 second)
• Best for: Simple use cases where exact accuracy isn't critical

Window: 12:00:00 - 12:01:00
Limit: 100 requests

12:00:55 - 12:00:59: 95 requests -> counter=95, ALLOWED
12:01:00: New window, counter=0
12:01:01: 100 requests in 1 second -> counter=100, ALLOWED
Result: 200 requests in a 1-second span at the boundary

Sliding Window Log

• How it works: Store timestamp of every request in a sorted set. On new request, remove entries older than window. Count remaining entries.
• Parameters: limit, window_size
• Pros: Most accurate, no boundary burst problem
• Cons: High memory usage (stores every timestamp), O(N) for cleanup
• Best for: When accuracy is paramount and request volume is moderate

Limit: 5 requests per 60 seconds
Sorted Set: [t1, t2, t3, t4, t5]

New request at t6:
1. Remove entries older than t6-60s
2. Count remaining = 5
3. Reject (5 >= limit)

After 60s, t1 expires:
1. Remove t1
2. Count remaining = 4
3. Allow (4 < limit)

Sliding Window Counter

• How it works: Combine the count from the previous window with the current window using a weighted formula. Previous window count is weighted by how much of it overlaps with the current window.
• Parameters: limit, window_size
• Pros: Most practical algorithm - accurate, memory efficient, no burst problem
• Cons: Approximation (not 100% precise), but very close
• Best for: Production systems (used by most major companies)

Window: 60 seconds
Limit: 100 requests
Previous window count: 80
Current window count: 30 (20 seconds into current window)

Weighted count = prev_count * (overlap %) + current_count
              = 80 * (40/60) + 30
              = 53.33 + 30
              = 83.33

83.33 < 100 -> ALLOWED

Algorithm Comparison

Algorithm	Accuracy	Memory	Burst Handling	Complexity
Token Bucket	High	Low	Allows bursts	Medium
Leaky Bucket	High	Medium	Smooth output	Medium
Fixed Window	Medium	Very Low	Window boundary issue	Low
Sliding Window Log	Very High	High	No bursts	High
Sliding Window Counter	High	Low	No bursts	Medium

Why Distributed?

In production, API servers run behind a load balancer. Each server independently counting would allow N * limit requests (where N = number of servers). A centralized counter in Redis solves this.

         Client Request
              |
         Load Balancer
        /      |       \
   Server1  Server2  Server3
      \       |       /
         Redis Cluster
      (central counter)

Redis-Based Implementation

Sliding Window Counter with Redis

import time
import redis

class SlidingWindowRateLimiter:
    def __init__(self, redis_client, limit, window_seconds):
        self.redis = redis_client
        self.limit = limit
        self.window = window_seconds
    
    def is_allowed(self, key):
        now = time.time()
        window_start = now - self.window
        
        pipe = self.redis.pipeline(True)
        try:
            # Remove old entries
            pipe.zremrangebyscore(key, 0, window_start)
            # Count current entries
            pipe.zcard(key)
            # Add current request timestamp
            pipe.zadd(key, {str(now): now})
            # Set expiry
            pipe.expire(key, self.window)
            results = pipe.execute()
            
            current_count = results[1]
            
            if current_count >= self.limit:
                # Remove the entry we just added (rejected)
                self.redis.zrem(key, str(now))
                return False, self.limit - current_count, self._get_retry_after(key)
            
            return True, self.limit - current_count - 1, None
        finally:
            pipe.close()
    
    def _get_retry_after(self, key):
        oldest = self.redis.zrange(key, 0, 0, withscores=True)
        if oldest:
            return max(0, self.window - (time.time() - oldest[0][1]))
        return 0

Token Bucket with Redis Lua Script

-- Token Bucket Algorithm in Redis
-- KEYS[1] = bucket key
-- ARGV[1] = bucket_size, ARGV[2] = refill_rate, ARGV[3] = now, ARGV[4] = ttl

local key = KEYS[1]
local bucket_size = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local ttl = tonumber(ARGV[4])

local bucket = redis.call('hmget', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or bucket_size
local last_refill = tonumber(bucket[2]) or now

-- Refill tokens based on elapsed time
local elapsed = now - last_refill
local new_tokens = math.min(bucket_size, tokens + (elapsed * refill_rate))

-- Check if request can be served
if new_tokens >= 1 then
    new_tokens = new_tokens - 1
    redis.call('hmset', key, 'tokens', new_tokens, 'last_refill', now)
    redis.call('expire', key, ttl)
    return {1, new_tokens}  -- allowed, remaining tokens
else
    redis.call('hmset', key, 'tokens', new_tokens, 'last_refill', now)
    redis.call('expire', key, ttl)
    return {0, 0}  -- rejected
end

Why Lua Scripts?

• Atomicity: Lua script executes as a single atomic operation in Redis
• No race conditions: Multiple servers can't read-modify-write simultaneously
• Performance: Single round trip vs multiple round trips with MULTI/EXEC

Race Conditions & Solutions

Problem: Read-Modify-Write Race

Server A: READ counter = 99
Server B: READ counter = 99
Server A: WRITE counter = 100 (ALLOWED)
Server B: WRITE counter = 100 (ALLOWED)
Result: 101 requests when limit is 100

Solution 1: Redis MULTI/EXEC (Transaction)

MULTI
INCR rate: user123
EXPIRE rate: user123 60
EXEC

Solution 2: Lua Script (Preferred)

Single atomic operation, no intermediate reads possible.

Solution 3: Redis SETNX + EXPIRE

SETNX rate:user123 1 EX 60
INCR rate:user123

Distributed Coordination Patterns

Local + Global Rate Limiting

• Local: Each server tracks its own count (no Redis overhead)
• Global: Redis tracks total count across all servers
• Check local first: If local count < (global_limit / num_servers), allow immediately
• Only hit Redis when approaching limit: Reduces Redis load by 90%+

Server1 (local_limit = global_limit / 3 = 33)
  local_count=30 -> CHECK REDIS (approaching local limit)
  Redis global_count=85 -> ALLOWED
  local_count=31

Server2 (local_count=10) -> ALLOWED (under local limit, no Redis call)

Multi-Region Rate Limiting

• Each region has its own Redis cluster for local rate limiting
• Async replication between regions for global limits
• Accept slight inaccuracy for lower latency
• Use eventual consistency: counts may be off by a few requests across regions

High-Level Architecture

┌─────────┐     ┌──────────────┐     ┌──────────────┐
│  Client  │────▶│ Load Balancer│────▶│  API Server  │
└─────────┘     └──────────────┘     └──────┬───────┘
                                            │
                                            ▼
                                   ┌────────────────┐
                                   │ Rate Limiter   │
                                   │   Middleware   │
                                   └───────┬────────┘
                                           │
                          ┌────────────────┼────────────────┐
                          ▼                ▼                ▼
                    ┌──────────┐    ┌──────────┐    ┌──────────┐
                    │  Redis   │    │  Rules   │    │  Config  │
                    │ Cluster  │    │  Store   │    │  Service │
                    └──────────┘    └──────────┘    └──────────┘

Middleware Implementation

@Component
public class RateLimitInterceptor implements HandlerInterceptor {
    
    @Autowired private RateLimiter rateLimiter;
    @Autowired private RulesConfigService rulesConfig;
    
    @Override
    public boolean preHandle(HttpServletRequest request,
                             HttpServletResponse response,
                             Object handler) {
        String clientKey = resolveClientKey(request);
        RateLimitRule rule = rulesConfig.getRule(request.getRequestURI());
        
        RateLimitResult result = rateLimiter.check(clientKey, rule);
        
        response.setHeader("X-RateLimit-Limit", String.valueOf(rule.getLimit()));
        response.setHeader("X-RateLimit-Remaining", String.valueOf(result.getRemaining()));
        response.setHeader("X-RateLimit-Reset", String.valueOf(result.getResetAt()));
        
        if (!result.isAllowed()) {
            response.setStatus(429);
            response.setHeader("Retry-After", String.valueOf(result.getRetryAfter()));
            response.getWriter().write("{\"error\": \"Rate limit exceeded\"}");
            return false;
        }
        
        return true;
    }
    
    private String resolveClientKey(HttpServletRequest request) {
        // Priority: API key > User ID > IP address
        String apiKey = request.getHeader("X-API-Key");
        if (apiKey != null) return "api:" + apiKey;
        
        String userId = getUserFromToken(request);
        if (userId != null) return "user:" + userId;
        
        return "ip:" + getClientIP(request);
    }
}

Rate Limit Rules Engine

rules:
  - name: "free-tier-api"
    match:
      api_key_tier: FREE
    limits:
      - window: 1s
        max_requests: 10
      - window: 1m
        max_requests: 100
      - window: 1h
        max_requests: 1000
    
  - name: "premium-tier-api"
    match:
      api_key_tier: PREMIUM
    limits:
      - window: 1s
        max_requests: 50
      - window: 1m
        max_requests: 2000
      - window: 1h
        max_requests: 50000
    
  - name: "search-endpoint"
    match:
      path: "/api/v1/search"
    limits:
      - window: 1s
        max_requests: 5
      - window: 1m
        max_requests: 30
    
  - name: "write-endpoint"
    match:
      path: "/api/v1/*"
      method: POST
    limits:
      - window: 1s
        max_requests: 20

Error Response Format

{
    "error": {
        "code": 429,
        "message": "Rate limit exceeded",
        "details": {
            "limit": 100,
            "window": "1m",
            "remaining": 0,
            "reset_at": "2026-08-16T12:01:00Z",
            "retry_after": 23
        }
    }
}

Edge Cases & Handling

Redis Failure

Strategy	Behavior	When to Use
Fail Open	Allow all requests when Redis is down	When availability is more critical than protection
Fail Closed	Reject all requests when Redis is down	When protecting backend from overload is critical
Local Fallback	Use local in-memory counters with reduced limits	Balanced approach - most production systems

Clock Skew in Distributed Systems

• Problem: Different servers have slightly different system clocks, causing window misalignment
• Solution: Use Redis server time (TIME command) instead of local system time
• Alternative: Use relative time (TTL-based expiry) instead of absolute timestamps

Burst at Window Boundary

• Problem: Fixed window allows 2x burst at boundary
• Solution: Use sliding window counter or token bucket instead
• Mitigation: Add a "burst allowance" parameter to fixed window algorithms

Key Expiration Race

• Problem: Redis key expires between INCR and EXPIRE commands
• Solution: Use Lua script for atomic operation, or SET with NX+EX for initial creation

Multi-Tier Rate Limiting

• A user on free tier has 100 req/min globally
• But /search endpoint is limited to 30 req/min
• Both limits must be checked; rejection uses the tighter limit

def check_multi_tier(user_key, endpoint_key):
    user_result = limiter.check(user_key, user_rule)
    endpoint_result = limiter.check(endpoint_key, endpoint_rule)
    
    if not user_result.allowed:
        return user_result
    if not endpoint_result.allowed:
        return endpoint_result
    
    # Return the result with fewer remaining
    return min(user_result, endpoint_result, key=lambda r: r.remaining)

Monitoring & Observability

• Metrics: Total requests, allowed, rejected, latency of rate limit check
• Alerting: Alert if rejection rate exceeds threshold (e.g., 10%)
• Dashboards: Real-time view of rate limit hits per user/endpoint
• Logging: Log rejected requests with client key, endpoint, timestamp

# Prometheus metrics
rate_limiter_requests_total{status="allowed"} 9500000
rate_limiter_requests_total{status="rejected"} 500000
rate_limiter_check_duration_ms_bucket{le="1"} 9900000
rate_limiter_check_duration_ms_bucket{le="5"} 10000000

Configuration Hot Reload

• Store rules in database or ZooKeeper
• Rules config service watches for changes
• Updates propagate to all API servers within seconds
• No server restart required
• Canary rollout: apply new rules to 5% of traffic first