System Design 21: Design a Distributed Rate Limiter | Token Bucket | Leaky Bucket | Sliding Window

A rate limiter is a critical infrastructure component used to control the rate of traffic sent by a client or service, protecting backend systems from overload, preventing resource exhaustion, and mitigating abusive behaviors like DDoS attacks or web scraping. In high-stakes system design interviews, candidates are expected to articulate architectural placements, data consistency trade-offs, and implement functional algorithm code using object-oriented design patterns (such as the Strategy and Factory patterns).

1. Why Do We Need a Rate Limiter? (Problem Statement & Status Quo)

Modern architectures—especially those backed by expensive resources like Large Language Models (LLMs)—require strict traffic governance. Without rate limiting, a malicious script or misconfigured client can exhaust backend compute power, degrade performance, or incur catastrophic cloud infrastructure bills.

Real-Life Analogy

Mental Hook: Think of an exclusive nightclub or a popular buffet restaurant with a strict fire-code capacity and a bouncer at the front door. The bouncer checks IDs, counts how many people enter per minute, and denies entry when the venue is full, handing out a polite voucher ("Please try again in 15 minutes") rather than letting the building collapse from overcrowding.

• Backend Protection: Shields downstream microservices from unexpected traffic spikes or automated scraper bots.
• Cost Control: Prevents runaway billing on third-party or resource-intensive APIs (e.g., image generation via LLMs).
• Fairness and Quality of Service (QoS): Ensures that high-paying enterprise users do not experience latency degradation caused by free-tier users flooding the system.

2. Functional Requirements

Before diving into architectural diagrams, system design interviews require establishing clear boundaries of what the rate limiter must accomplish:

• 1. Request Restriction: Limit the number of requests a client can make within a specific time window based on attributes like User ID, API Key, or IP Address.
• 2. Runtime Configurability: All rules, thresholds, and limits must be dynamically modifiable by system administrators at runtime without requiring service restarts.
• 3. Meaningful Error Responses: When a limit is breached, return an appropriate HTTP status code (429 Too Many Requests) along with informative headers indicating quota status.
• 4. Burst Traffic Handling: The system must gracefully absorb sudden traffic surges without dropping legitimate requests prematurely.
• 5. Tier-Based Policies: Support multi-tier application models (e.g., Free, Gold, Platinum, Enterprise tiers), where each tier enforces distinct rate limits.

3. Non-Functional Requirements & CAP Theorem Trade-offs

High-scale rate limiters operate on the critical request path, imposing stringent operational constraints:

4. Core Entities

Analyzing the functional requirements reveals three fundamental data structures and entities required for the system:

• Rules / Config: Stores threshold parameters (max_requests, window_size, algorithm_type) per endpoint or tenant.
• Client: Represents the entity executing requests against the system, mapped to an auth token or IP address.
• Request Counter: The mutable numerical state recording current consumption within the active timeframe.

5. API Design & HTTP 429 Response Standards

Internal Administrative REST Endpoints

Because rate limiter policies are runtime-configurable, administrative services expose CRUD endpoints:

Production-Grade 429 Response Payload

When a client exceeds their quota, returning a blank error page is unacceptable. Production systems return structured telemetry headers and bodies:

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

{
  "error": "Rate limit exceeded",
  "message": "You have exhausted your API quota. Please retry after 60 seconds.",
  "retry_after_seconds": 60
}

6. High-Level Architecture & Deployment Topologies

Where should the rate limiter live within a distributed microservice architecture? There are three primary placement strategies:

Comparative Analysis of Rate Limiter Placement

Complete Distributed Data Flow Walkthrough

In a production-grade distributed deployment, multiple API gateway instances sit behind a load balancer, requiring a centralized state store:

7. Distributed State Management with Redis

When an API Gateway scales out horizontally into dozens of instances, local in-memory counters cause severe counter mismatch (e.g., Request 1 hits Gateway A, Request 2 hits Gateway B, splitting the user's quota incorrectly).

To solve this, state must be externalized into an ultra-fast distributed cache:

• Redis Cluster: Acts as the global memory store holding atomic request counters and token states.
• Write-Through Policy Database Pipeline:
  • Admins modify rules via the Admin UI -> stored in PostgreSQL (Policy DB).
  • Changes propagate via a write-through pattern to the Redis Cache cluster, ensuring rate limiters evaluate up-to-date rules with sub-millisecond latency.

Policy Database Schema (PostgreSQL)

CREATE TABLE rate_limit_rules (
    rule_id SERIAL PRIMARY KEY,
    subject_type VARCHAR(50) NOT NULL,    -- e.g., 'USER_ID', 'API_KEY', 'IP_ADDRESS', 'TIER'
    subject_value VARCHAR(255) NOT NULL,  -- e.g., 'FREE_TIER', 'user_12345'
    endpoint VARCHAR(255) NOT NULL,       -- e.g., '/api/v1/generate-image' or '*'
    algorithm VARCHAR(50) NOT NULL,       -- e.g., 'TOKEN_BUCKET', 'SLIDING_WINDOW'
    request_limit INT NOT NULL,           -- Max allowed requests
    window_size_seconds INT NOT NULL,     -- Time window duration
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

8. Deep Dive: Rate Limiting Algorithms

Interviews frequently evaluate deep knowledge of five core rate-limiting algorithms.

1. Fixed Window Counter Algorithm

Divides timeline into fixed time blocks (e.g., 0-10s, 10-20s) and maintains a simple counter per window.

• Pros: Easy to implement; low memory footprint.
• Cons: Spike at Window Edges. If a user exhausts their entire limit at 9.9s and another 5 requests at 10.1s, they execute double the allowed rate within a 0.2s window.

2. Sliding Window Log Algorithm

Keeps track of exact request timestamps in a sorted set or queue (e.g., Redis ZSET), removing timestamps older than the sliding window interval.

• Pros: Extremely accurate; eliminates edge-burst vulnerabilities.
• Cons: High Memory Consumption. Storing every individual request timestamp for millions of concurrent users consumes massive memory.

3. Sliding Window Counter Algorithm

A hybrid approach combining Fixed Window counters with a weighted sliding calculation based on the previous window's traffic density.

• Pros: Low memory footprint (stores only current and previous window counts); smooths out edge traffic spikes.
• Cons: Relies on the assumption that traffic in the previous window was distributed uniformly.

4. Token Bucket Algorithm (Industry Favorite)

A bucket holds tokens up to a maximum capacity. Tokens are added at a constant refill rate. When a request arrives, a token is consumed. If the bucket is empty, the request is rejected.

• Pros: Memory efficient; highly friendly to burst traffic (allows clients to consume up to the bucket capacity instantly if tokens are available).
• Cons: Requires careful tuning of capacity and refill rate parameters.

5. Leaky Bucket Algorithm

Requests enter a FIFO queue of fixed capacity. The system processes (drains) requests from the queue at a strict, constant rate.

• Pros: Guarantees a perfectly smooth, uniform outbound traffic rate to protect fragile downstream services.
• Cons: Can introduce queue latency during burst traffic; newer requests may be dropped if the queue overflows.

Algorithm Comparison Matrix

9. Object-Oriented Design & Code Implementation (Strategy Pattern)

In senior system design rounds, interviewers often ask you to transition from high-level architecture to clean, modular code. The Strategy Design Pattern is ideal here, allowing runtime selection of rate-limiting algorithms (Token Bucket, Leaky Bucket, etc.) wrapped behind a unified interface.

Java Implementation Example

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

// 1. Strategy Interface
interface RateLimitingStrategy {
    boolean allowRequest();
}

// 2. Concrete Strategy: Token Bucket Algorithm
class TokenBucketRateLimiter implements RateLimitingStrategy {
    private final long capacity;
    private final long refillRatePerSec;
    private long currentTokens;
    private long lastRefillTimestamp;

    public TokenBucketRateLimiter(long capacity, long refillRatePerSec) {
        this.capacity = capacity;
        this.refillRatePerSec = refillRatePerSec;
        this.currentTokens = capacity;
        this.lastRefillTimestamp = System.currentTimeMillis();
    }

    @Override
    public synchronized boolean allowRequest() {
        refillToken();
        if (currentTokens > 0) {
            currentTokens--;
            return true;
        }
        return false;
    }

    private void refillToken() {
        long now = System.currentTimeMillis();
        long elapsedSec = (now - lastRefillTimestamp) / 1000;
        if (elapsedSec > 0) {
            long tokensToAdd = elapsedSec * refillRatePerSec;
            currentTokens = Math.min(capacity, currentTokens + tokensToAdd);
            lastRefillTimestamp = now;
        }
    }
}

// 3. Factory Class for Dynamic Strategy Creation
class RateLimiterFactory {
    public static RateLimitingStrategy getLimiter(String algorithmType, long capacity, long rate) {
        if ("TOKEN_BUCKET".equalsIgnoreCase(algorithmType)) {
            return new TokenBucketRateLimiter(capacity, rate);
        }
        // Additional algorithms can be registered here
        throw new IllegalArgumentException("Unknown rate limiter algorithm: " + algorithmType);
    }
}

// 4. API Gateway Middleware Enforcement Simulator
class APIGatewayMiddleware {
    private final Map<String, RateLimitingStrategy> clientLimiters = new ConcurrentHashMap<>();

    public boolean evaluateRequest(String clientId, String algorithmType, long capacity, long rate) {
        RateLimitingStrategy limiter = clientLimiters.computeIfAbsent(clientId, id -> 
            RateLimiterFactory.getLimiter(algorithmType, capacity, rate)
        );
        return limiter.allowRequest();
    }
}

10. Summary and Key Takeaways

• Critical Dual-Ask: System design interviews on rate limiters test both high-level macro architecture (APIs, caching layers, gateway placement) and low-level object-oriented coding principles.
• Gateway Placement: Deploying the rate limiter as middleware or a plugin at the API Gateway / Reverse Proxy layer is the industry standard for intercepting and validating traffic before it reaches backend services.
• High Availability Over Consistency: Favor AP (Availability) over CP (Consistency) in the CAP theorem trade-off; an unreachable rate limiter should fail open rather than dropping all inbound user traffic.
• Externalized Distributed State: Utilize a distributed in-memory store like Redis to maintain atomic request counters across horizontally scaled API gateway instances, preventing counter mismatch.
• Token Bucket Superiority: The Token Bucket algorithm is the most widely adopted production strategy due to its memory efficiency and native support for handling burst traffic spikes.
• Strategy Design Pattern: Implement rate-limiting algorithms using the Strategy and Factory design patterns, enabling clean separation of concerns and dynamic runtime algorithm swapping.