LLD: Rate Limiter

A rate limiter is an architectural pattern and traffic control mechanism used to limit the number of requests a client (e.g., an individual user, IP address, or API key) can perform within a specific time frame. In production distributed systems, rate limiting acts as a critical line of defense against Denial of Service (DoS/DDoS) attacks, brute-force credential stuffing, resource starvation, and cascading microservice failures.

1. Architectural Foundations & Placement

When designing a production rate limiter, the primary architectural decision is determining where the enforcement boundary should reside across the infrastructure network topology.

flowchart LR
    Client([Client / App]) --> Edge[CDN / WAF Edge]
    Edge --> APIGateway[API Gateway / Ingress]
    APIGateway <--> Redis[(Distributed Cache\nRate Limit Store)]
    APIGateway --> ServiceA[Microservice A]
    APIGateway --> ServiceB[Microservice B]
    
    subgraph Rate Limit Enforcement Layer
        APIGateway
        Redis
    end

Enforcement Boundaries

1. Client-Side (Local Throttling):

   • Mechanism: Implemented in the client API SDK or UI client using queues or local timers.
   • Limitations: Easily bypassed by malicious actors; client system clocks are untrustworthy and subject to arbitrary skew. Useful solely as a UX optimization to reduce redundant network transfers.

2. Server-Side (App Middleware):

   • Mechanism: Implemented via filters or interceptors directly within microservice framework runtimes (e.g., Spring Cloud Gateway, Express middleware).
   • Trade-offs: Highly adaptable to domain logic (e.g., tier-based limits for basic vs. enterprise users) but wastes computing cycles processing TCP handshakes and TLS decryption on application servers before dropping bad traffic.

3. API Gateway / Edge Proxy (Recommended):

   • Mechanism: Centralized routing infrastructure (e.g., Envoy, Kong, Nginx, Cloudflare WAF) evaluates traffic against an in-memory or external state store prior to upstream routing.
   • Advantages: Decouples defensive traffic shedding from domain logic, centralizes security monitoring, and enables hardware-accelerated drop rates at the outer network perimeter.

2. Core Rate Limiting Algorithms & Mathematical Modeling

A. Token Bucket Algorithm

The Token Bucket is the industry standard algorithm for API rate limiting (used extensively by Amazon and Stripe) due to its memory efficiency and controlled tolerance for temporary bursts.

Mathematical Model

Let a bucket have a maximum capacity of $C$ tokens and a refill rate of $R$ tokens/second. At any timestamp $t_2$, given a previous execution timestamp $t_1$ and token count $T_1$, the available tokens $T_2$ before request evaluation are modeled as:

$T_2 = \min\left(C, \; T_1 + (t_2 - t_1) \times R\right)$

A request requiring $k$ tokens is permitted if and only if $T_2 \ge k$. Upon acceptance, the updated state is $T_{2}' = T_2 - k$.

Trade-offs

• Pros: Minimal memory usage ($O(1)$ per key, requiring only two floats: last_updated_time and current_token_count). Supports short bursts of requests up to capacity $C$.
• Cons: Tuning both capacity ($C$) and refill rate ($R$) properly requires historical traffic profiling and load simulation.

B. Leaky Bucket Algorithm

Inspired by classical telecommunications networking and traffic shaping, the Leaky Bucket implements a FIFO queue with a strict execution capacity and an egress processing rate.

graph TD
    A[Incoming Requests] -->|Overflow Dropped| B[FIFO Buffer / Bucket]
    B -->|Leaks at Constant Rate R| C[Processor / Upstream Service]

• Pros: Smooths abrupt traffic spikes into a predictable, fixed-rate stream. Ideal for asynchronous worker pipelines with rigid capacity bounds.
• Cons: A burst of older, slow-to-process requests can consume queue slots, causing newly arriving high-priority requests to be rejected once the queue reaches saturation.

C. Fixed Window Counter

Divides time into arbitrary durations (e.g., 60-second intervals from 00:00:00 to 00:01:00) and tracks cumulative hit counts within the active epoch.

• Critical Failure Mode: The Boundary Burst Problem. If a client sends 1,000 requests during the final 500ms of Window $N$, and another 1,000 requests during the initial 500ms of Window $N+1$, the server experiences $2 \times \text{Capacity}$ throughput over a single 1-second interval, violating backend protection limits.

D. Sliding Window Log & Sliding Window Counter

Sliding Window Log

Stores timestamp records for every incoming request inside a sorted set (e.g., Redis ZSET). To validate a request at timestamp $T$, all records older than $T - \text{WindowSize}$ are purged, and the remaining entry count is verified against the threshold.

• Drawback: Memory prohibitive ($O(N)$ storage per consumer). Under attack scenarios, logging thousands of denied request timestamps can quickly exhaust cache memory capacity.

Sliding Window Counter (Optimal Hybrid)

Combines low-overhead counter arithmetic with a linear decay model to resolve boundary bursting without logging per-request timestamps.

Mathematical Formulation

Let $C_{\text{prev}}$ be the cumulative request count of the prior time window, and $C_{\text{curr}}$ be the count in the active time window. If the current timestamp is at percentage $w$ ($0 \le w \le 1$) through the active time window, the smoothed effective request count $C_{\text{effective}}$ is calculated as:

$C_{\text{effective}} = \lfloor C_{\text{prev}} \times (1 - w) + C_{\text{curr}} \rfloor$

If $C_{\text{effective}} < \text{Threshold}$, increment $C_{\text{curr}}$ and allow the request.

3. Low-Level Design (LLD): Object-Oriented Blueprint

To implement a clean, extensibility-focused low-level architectural pattern, we apply the Strategy Pattern for dynamic rate-limit scheduling and an abstractions layer for storage engines.

classDiagram
    class RateLimiter {
      <<interface>>
      +allowRequest(String key, int tokens) boolean
    }
    
    class RateLimitPolicy {
      +int maxRequests
      +long windowDurationMs
      +PolicyType type
    }
    
    class TokenBucketRateLimiter {
      -StorageEngine store
      -RateLimitPolicy policy
      +allowRequest(String key, int tokens) boolean
      -refill(TokenBucketState state) void
    }
    
    class SlidingWindowRateLimiter {
      -StorageEngine store
      -RateLimitPolicy policy
      +allowRequest(String key, int tokens) boolean
    }
    
    class StorageEngine {
      <<interface>>
      +get(String key) Object
      +put(String key, Object value, long ttl) void
      +evalAtomicScript(String script, List keys, List args) Object
    }
    
    class RedisStorageEngine {
      +evalAtomicScript(...) Object
    }
    
    class InMemoryStorageEngine {
      -ConcurrentHashMap cache
      +get(...) Object
    }

    RateLimiter <|.. TokenBucketRateLimiter
    RateLimiter <|.. SlidingWindowRateLimiter
    TokenBucketRateLimiter --> StorageEngine : relies on
    SlidingWindowRateLimiter --> StorageEngine : relies on
    StorageEngine <|.. RedisStorageEngine
    StorageEngine <|.. InMemoryStorageEngine

4. Production Implementation: Distributed Rate Limiting via Redis & Lua

When rate limiters are distributed across horizontally scaled proxy instances, accessing a shared Redis node using independent GET and SET operations creates classic Read-Modify-Write race conditions.

Resolving Race Conditions with Atomic Lua Scripts

By executing a compiled Lua script inside Redis, the evaluation, token subtraction, and TTL expiration occur as an atomic transaction without distributed locking overhead.

Production TypeScript Interface & Script Pipeline

import Redis from 'ioredis';

export interface RateLimitResult {
  allowed: boolean;
  limit: number;
  remaining: number;
  retryAfterMs: number;
}

export class DistributedTokenBucket {
  private redis: Redis;
  private readonly scriptSha: Promise<string>;

  // Atomic Lua Script executing entirely on the Redis server process
  private readonly LUA_SCRIPT = `
    local key = KEYS[1]
    local capacity = tonumber(ARGV[1])
    local refill_rate = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])
    local requested_tokens = tonumber(ARGV[4])

    local data = redis.call("HMGET", key, "tokens", "last_updated")
    local tokens = tonumber(data[1])
    local last_updated = tonumber(data[2])

    if not tokens then
      tokens = capacity
      last_updated = now
    else
      local delta = math.max(0, now - last_updated)
      local new_tokens = math.floor(delta * refill_rate / 1000)
      if new_tokens > 0 then
        tokens = math.min(capacity, tokens + new_tokens)
        last_updated = now
      end
    end

    local allowed = 0
    local remaining = tokens
    local retry_after = 0

    if tokens >= requested_tokens then
      tokens = tokens - requested_tokens
      allowed = 1
      remaining = tokens
    else
      local needed = requested_tokens - tokens
      retry_after = math.ceil((needed * 1000) / refill_rate)
    end

    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    -- Expire bucket dynamically based on maximum time required to fully refill
    local ttl = math.ceil((capacity / refill_rate)) * 2
    redis.call("EXPIRE", key, ttl)

    return { allowed, capacity, remaining, retry_after }
  `;

  constructor(redisClient: Redis) {
    this.redis = redisClient;
    this.scriptSha = this.redis.script('LOAD', this.LUA_SCRIPT) as Promise<string>;
  }

  public async evaluate(
    consumerKey: string,
    capacity: number,
    refillRatePerSecond: number,
    requestedTokens = 1
  ): Promise<RateLimitResult> {
    const sha = await this.scriptSha;
    const nowMs = Date.now();
    const redisKey = `ratelimit:{${consumerKey}}:bucket`;

    // Execute script via SHA to reduce bandwidth overhead
    const response = (await this.redis.evalsha(
      sha,
      1,
      redisKey,
      capacity.toString(),
      refillRatePerSecond.toString(),
      nowMs.toString(),
      requestedTokens.toString()
    )) as [number, number, number, number];

    return {
      allowed: response[0] === 1,
      limit: response[1],
      remaining: response[2],
      retryAfterMs: response[3]
    };
  }
}

5. Edge Cases & Resilience Engineering

1. Clock Synchronization & Time Drift

In a multi-region deployment, relying on local machine time ($T_{\text{curr}}$) across unsynchronized hosts causes inconsistent rate calculation.

• Mitigation: Deploy NTP (Network Time Protocol) with stringent jitter thresholds, or delegate timestamp generation exclusively to the centralized storage engine layer (e.g., using Redis TIME commands within scripts).

2. Thundering Herd & Retry Storms

When an outage or traffic spike triggers widespread 429 Too Many Requests rejections, naïvely implemented client applications may retry immediately, compounding server loads.

• Mitigation: Standardize HTTP response headers and require clients to respect exponential backoff mixed with algorithmic random jitter:

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

{
  "error": "Rate_Limit_Exceeded",
  "message": "API rate quota exhausted. Retry after 12 seconds."
}

3. Fail-Open vs. Fail-Close Policies

When the external caching cluster (e.g., Redis) suffers a partition or total network loss, the proxy must execute an explicit circuit-breaking strategy:

• Fail-Open (Availability Prioritization): Permit traffic to route straight to downstream microservices, logging an emergency metric. Recommended for public-facing consumer APIs where uptime is prioritized over hard quota compliance.
• Fail-Close (Integrity & Financial Protection): Reject incoming operations immediately. Mandatory for financial transactional services, billing engines, and third-party commercial LLM integrations where uncontrolled throughput incurs severe monetary loss or security vulnerabilities.

6. Comprehensive Interview Questions & Verification

Q1: Why should you prefer the Sliding Window Counter over the Sliding Window Log in high-volume global APIs?

Answer: While Sliding Window Log ensures absolute accuracy by preserving exact timestamp records in a sorted set, its space complexity scales linearly with traffic volume ($O(N)$ per client). Under a volumetric brute-force attempt, preserving millions of timestamps per minute leads to instantaneous out-of-memory crashes on cache nodes. Sliding Window Counter trades negligible mathematical variance (assuming linear traffic distribution inside windows) for a fixed, deterministic $O(1)$ memory footprint of just two integers per active window.

Q2: How do you prevent hotspotting in a distributed rate limiting cluster when a single enterprise user generates 50,000 requests/second?

Answer: A single high-throughput consumer routing to a single Redis partition via normal consistent hashing can cause high CPU utilization and NIC saturation on that specific shard. To remediate this:

1. Sharded Key Spaces: Sub-divide the consumer's primary key into $N$ conceptual sub-buckets (e.g., client_api_key:0 to client_api_key:9), allocating $\frac{1}{N}$ of the overall limit to each shard. Requests are randomly routed across these sub-shards.
2. Local Memory Buffering (Hybrid Aggregation): Maintain an in-memory batching counter within the gateway edge proxy (e.g., using a Local Guava cache or Envoy memory filter) that increments locally and asynchronously reconciles with the shared Redis cluster every 100 milliseconds.

Q3: Describe how you would rate limit complex GraphQL payloads where a single HTTP request can trigger an arbitrary number of downstream database resolvers.

Answer: Traditional request-per-second (RPS) metrics fail against GraphQL queries containing deeply nested operations (e.g., fetching 100 users and 500 posts per user in one call). To address this, implement a Query Complexity Analysis strategy:

• Assign intrinsic operational cost metrics (weights) to individual GraphQL Schema fields during static AST (Abstract Syntax Tree) parsing.
• Compute the comprehensive structural cost of the inbound document prior to execution.
• Pass the aggregate execution weight $W$ to the rate limiter (tokenBucket.allowRequest(key, W)). If available tokens are lower than $W$, reject the query with a 429 status code before executing resolver methods.