Design Rate Limiter - System Design Interview (4 Algorithms Explained)

📌The Interview Question

"Design a rate limiter that limits API requests to 100 requests per minute per user"

📌Why Rate Limiting?

Prevent DoS attacks

Control costs

Ensure fair usage

Prevent server overload

📌Step 1: Requirements

Functional

Limit requests per user/IP/API key

Return 429 Too Many Requests when exceeded

Configurable limits

Non-Functional

Low latency (add < 1ms overhead)

Highly available

Distributed (work across multiple servers)

📌Algorithm 1: Token Bucket

How it works:

Bucket holds tokens (capacity = rate limit)

Tokens added at fixed rate

Each request consumes 1 token

No tokens = request rejected

public class TokenBucket {
    private final int capacity;
    private final int refillRate; // tokens per second
    private double tokens;
    private long lastRefillTime;
    
    public synchronized boolean tryConsume() {
        refill();
        if (tokens >= 1) {
            tokens--;
            return true;
        }
        return false;
    }
    
    private void refill() {
        long now = System.currentTimeMillis();
        double tokensToAdd = (now - lastRefillTime) / 1000.0 * refillRate;
        tokens = Math.min(capacity, tokens + tokensToAdd);
        lastRefillTime = now;
    }
}

Pros: Allows bursts, smooth rate limiting Cons: Memory for storing tokens

📌Algorithm 2: Leaky Bucket

How it works:

Requests enter a queue (bucket)

Processed at fixed rate

Overflow = request rejected

Pros: Smooth output rate Cons: Recent requests may wait long

📌Algorithm 3: Fixed Window Counter

How it works:

Divide time into windows (1 minute)

Count requests in current window

Reset at window boundary

public class FixedWindowCounter {
    private final int limit;
    private final long windowSizeMs;
    private long windowStart;
    private int count;
    
    public synchronized boolean tryConsume() {
        long now = System.currentTimeMillis();
        if (now - windowStart >= windowSizeMs) {
            windowStart = now;
            count = 0;
        }
        if (count < limit) {
            count++;
            return true;
        }
        return false;
    }
}

Pros: Simple, memory efficient Cons: Burst at window boundaries

📌Algorithm 4: Sliding Window Log

How it works:

Store timestamp of each request

Count requests in last N seconds

Remove old timestamps

Pros: Accurate, no boundary issues Cons: Memory intensive

📌Algorithm 5: Sliding Window Counter

How it works:

Combines fixed window + sliding

Weighted average of current and previous window

Requests = Previous window count * overlap% + Current window count

Best choice for most cases!

📌Distributed Rate Limiting

Challenge

Rate limiter must work across multiple servers

User might hit different servers

Solution: Redis

// Using Redis with Lua script for atomicity
String script = """
    local current = redis.call('INCR', KEYS[1])
    if current == 1 then
        redis.call('EXPIRE', KEYS[1], ARGV[1])
    end
    return current
""";
Long count = jedis.eval(script, 1, "user:123:minute", "60");
return count <= limit;

📌System Architecture

System Architecture

Live

Client

Rate Limiter

Middleware

Redis Cluster

Cache

API Server

⚡ High Availability🔄 Auto-scaling🛡️ Fault Tolerant

📌Interview Tips

1Start with requirements

2Discuss multiple algorithms

3Explain trade-offs

4Address distributed scenario

5Discuss failure handling

What if Redis is down?

Fail open (allow requests)

Local fallback limiter

Circuit breaker pattern

Our System Design course includes hands-on implementation of all these algorithms.

Design Rate Limiter - System Design Interview (4 Algorithms Explained)

📌The Interview Question

📌Why Rate Limiting?

📌Step 1: Requirements

Functional

Non-Functional

📌Algorithm 1: Token Bucket

📌Algorithm 2: Leaky Bucket

📌Algorithm 3: Fixed Window Counter

📌Algorithm 4: Sliding Window Log

📌Algorithm 5: Sliding Window Counter

📌Distributed Rate Limiting

Challenge

Solution: Redis

📌System Architecture

📌Interview Tips

🚀 Master System Design

📚 Related Articles

LLD Interview: 7 Machine Coding Rounds You Must Practice (With Solutions)

Top 5 System Design Patterns for Senior Developer Interviews

Design URL Shortener (TinyURL) - Complete System Design Interview Guide