Rate Limiter System Design (HLD & LLD)

Problem Statement

Design a Rate Limiter that:

• Limits requests per user / API key / IP
• Example: 100 requests per minute
• Returns HTTP 429 (Too Many Requests) when the limit is exceeded.

Functional Requirements

• Limit requests per user
• Configurable limits
• Reject requests beyond the configured threshold

Non-Functional Requirements

• Low latency
• Highly scalable
• Distributed
• Fault tolerant

---

Where to Implement a Rate Limiter

Typical deployment locations:

• CDN
• API Gateway
• Reverse Proxy
• Application Layer
• Service Mesh

The most common production placement is the API Gateway.

flowchart TD
    C[Client] --> G["API Gateway<br/>Rate Limiter"]
    G --> L[Load Balancer]
    L --> A[Application Servers]
    A --> D[(Database)]

---

High-Level Design (HLD)

Architecture

flowchart TD
    C[Client] --> G[API Gateway]
    G --> R[Rate Limiter]
    R --> Redis["Redis Cluster<br/>Request Counters"]
    R --> A[Application Servers]

Request Flow

1. Client sends request.
2. API Gateway extracts the identity (user ID, API key, or IP).
3. Rate limiter checks the counter in Redis.
4. If the counter is below the configured limit, the request is forwarded.
5. Otherwise, return HTTP 429.

---

Rate Limiting Algorithms

Fixed Window Counter

All requests are counted in a single fixed time bucket.

Example:

• Limit: 100 requests/minute
• 100 requests at 12:00:59
• 100 requests at 12:01:01

Result: 200 requests within roughly two seconds.

Advantages

• Simple
• Fast

Disadvantages

• Burst problem at window boundaries

---

Sliding Window Log

Store the timestamp of every request.

For every incoming request:

1. Remove timestamps older than the window.
2. Count remaining timestamps.
3. Allow or reject.

Advantages

• Highly accurate

Disadvantages

• High memory usage

---

Sliding Window Counter

Uses weighted counts from the previous and current windows.

Example:

• Current window = 70 requests
• Previous window = 40 requests

Weighted count:

70 + (40 * overlap_ratio)

Advantages

• Accurate
• Lower memory than Sliding Window Log

---

Token Bucket (Most Popular)

Configuration:

• Bucket capacity = 100 tokens
• Refill rate = 10 tokens/second

Each request consumes one token.

If no tokens remain, reject the request.

Advantages

• Handles bursts efficiently
• Widely used in production

---

Leaky Bucket

Incoming requests enter a queue and are processed at a constant rate.

Useful for traffic shaping.

---

Algorithm Comparison

Algorithm	Advantages	Disadvantages
Fixed Window	Simple, fast	Burst problem
Sliding Window Log	Highly accurate	High memory
Sliding Window Counter	Accurate, efficient	More complex
Token Bucket	Burst-friendly, widely used	Refill logic required
Leaky Bucket	Smooth traffic	May increase latency

Recommended production choice: Token Bucket + Redis

---

Distributed Rate Limiter

When multiple application servers exist, local counters become inconsistent.

flowchart LR
    U[User] --> S1[Server 1]
    U --> S2[Server 2]
    S1 --> Redis[(Shared Redis)]
    S2 --> Redis

Shared storage options:

• Redis
• Memcached
• DynamoDB

Redis is the most common choice.

---

Redis-Based Design

Use atomic Redis operations.

Key example:

rate_limit:user123:minute

Redis operations:

INCR key
EXPIRE key

Pseudo-flow:

count = INCR(key)

if count == 1
    EXPIRE(key, 60)

if count > limit
    reject request

Atomic operations prevent race conditions.

---

Low-Level Design (LLD)

Core Components

• RateLimiter
• RateLimitConfig
• RateLimitStrategy
• RedisService
• RequestContext

Class Diagram

classDiagram
    class RateLimiter{
        +isAllowed()
    }

    class RateLimitStrategy{
        +allowRequest()
    }

    class TokenBucket
    class SlidingWindow

    RateLimiter --> RateLimitStrategy
    RateLimitStrategy <|-- TokenBucket
    RateLimitStrategy <|-- SlidingWindow

---

Java Implementation

RateLimiter Interface

public interface RateLimiter {
    boolean allowRequest(String userId);
}

Token Bucket Implementation

public class TokenBucketRateLimiter implements RateLimiter {

    private int capacity;
    private int tokens;
    private long refillRate;
    private long lastRefillTimestamp;

    public TokenBucketRateLimiter(int capacity, int refillRate) {
        this.capacity = capacity;
        this.tokens = capacity;
        this.refillRate = refillRate;
        this.lastRefillTimestamp = System.currentTimeMillis();
    }

    @Override
    public synchronized boolean allowRequest(String userId) {

        refill();

        if (tokens > 0) {
            tokens--;
            return true;
        }

        return false;
    }

    private void refill() {
        long now = System.currentTimeMillis();
        long tokensToAdd = (now - lastRefillTimestamp) / 1000 * refillRate;

        if (tokensToAdd > 0) {
            tokens = Math.min(capacity, tokens + (int) tokensToAdd);
            lastRefillTimestamp = now;
        }
    }
}

---

Production Redis Implementation

Pseudo-code:

key = "rate_limit:user123"

count = redis.incr(key)

if count == 1
    redis.expire(key, 60)

if count > limit
    reject

---

Edge Cases

Clock Drift

Use the Redis server time instead of application server time.

Redis Failure

Fallback strategies:

• Local in-memory limiter
• Temporarily allow requests

Hot Keys

Popular APIs can overload a single Redis key.

Possible mitigation:

rate_limit:user123:1
rate_limit:user123:2

Shard keys across multiple partitions.

---

Scaling Strategy

Large-scale deployments often use multiple layers of rate limiting.

flowchart TD
    C[Client]
    CDN[CDN Rate Limiter]
    GW[API Gateway Rate Limiter]
    SV[Service-Level Rate Limiter]

    C --> CDN --> GW --> SV

---

Real-World Examples

System	Algorithm
AWS API Gateway	Token Bucket
Stripe	Token Bucket
Cloudflare	Sliding Window
NGINX	Leaky Bucket

---

Interview Answer Structure

1. Gather functional and non-functional requirements.
2. Explain multiple rate limiting algorithms.
3. Justify choosing Token Bucket.
4. Present a distributed HLD using Redis.
5. Discuss distributed consistency challenges.
6. Explain the LLD and key classes.
7. Cover failure scenarios and edge cases.
8. Explain horizontal scaling and multi-layer rate limiting.

---

Key Takeaways

• Token Bucket is the most common production algorithm because it supports controlled bursts.
• Redis is widely used for distributed rate limiting due to atomic operations such as INCR and EXPIRE.
• Shared storage is essential when multiple application servers enforce limits.
• Rate limiting can be implemented at several layers, with the API Gateway being the most common.
• Strong interview answers discuss algorithms, architecture, implementation, edge cases, and scalability.