Design: Rate Limiter

A rate limiter controls how many requests a client can make in a time period. It protects APIs from abuse, prevents DoS attacks, and enforces pricing tiers.

Requirements

Limit requests per user/IP: e.g., 100 req/min
Distributed: multiple API servers, shared state
Low latency: < 1ms overhead per check
No false positives: legitimate requests shouldn't be rejected

Algorithm 1: Fixed Window Counter

// Redis key: "rate:{userId}:{currentMinute}"
public boolean allowRequest(String userId) {
    String key = "rate:" + userId + ":" + (System.currentTimeMillis() / 60000);
    long count = redis.incr(key);
    if (count == 1) redis.expire(key, 120); // 2 min TTL
    return count <= LIMIT; // LIMIT = 100
}

❌ Problem: allows burst at window boundary (99 req at 0:59 + 99 req at 1:00 = 198 in 2 seconds)

Algorithm 2: Sliding Window Log

// Store timestamps of all requests in a sorted set
public boolean allowRequest(String userId) {
    long now = System.currentTimeMillis();
    long windowStart = now - 60000; // 1 minute window
    String key = "ratelimit:" + userId;

    redis.pipeline()
        .zremrangeByScore(key, 0, windowStart) // remove old entries
        .zadd(key, now, UUID.randomUUID().toString()) // add current request
        .expire(key, 120)
        .sync();

    return redis.zcard(key) <= LIMIT;
}

✅ Accurate, no boundary burst ❌ High memory: stores every request timestamp

Algorithm 3: Token Bucket (recommended)

// Tokens fill up at a steady rate; requests consume tokens
// Allow burst up to bucket capacity

public boolean allowRequest(String userId) {
    String key = "bucket:" + userId;
    long now = System.currentTimeMillis();

    // Lua script for atomicity
    String script = """
        local tokens = tonumber(redis.call('get', KEYS[1])) or CAPACITY
        local last = tonumber(redis.call('get', KEYS[2])) or NOW
        local refill = (NOW - last) / INTERVAL * RATE
        tokens = math.min(CAPACITY, tokens + refill)
        local allowed = tokens >= 1
        if allowed then tokens = tokens - 1 end
        redis.call('set', KEYS[1], tokens)
        redis.call('set', KEYS[2], NOW)
        return allowed and 1 or 0
        """;
    return redis.eval(script, 2, key + ":tokens", key + ":last") == 1L;
}

✅ Allows controlled bursts ✅ Smooth rate limiting

Algorithm 4: Sliding Window Counter (approximation)

// Current window count + previous window count weighted by overlap
public boolean allowRequest(String userId) {
    long now = System.currentTimeMillis() / 1000;
    long currentWindow = now / 60;
    double windowFraction = (now % 60) / 60.0;

    long prevCount  = getLong("rate:" + userId + ":" + (currentWindow - 1));
    long currCount  = getLong("rate:" + userId + ":" + currentWindow);

    double estimatedCount = prevCount * (1.0 - windowFraction) + currCount;
    if (estimatedCount >= LIMIT) return false;

    incr("rate:" + userId + ":" + currentWindow);
    return true;
}

Distributed Rate Limiting

With multiple API servers, use Redis as shared state:

         ┌──────────┐
User →  │  Server  │ ──→ Redis INCR
         └──────────┘      (shared counter)
         ┌──────────┐           ↑
User →  │  Server  │ ──────────┘
         └──────────┘

Use Redis Lua scripts for atomic increment + check.

Architecture

Request → API Gateway → Rate Limiter Middleware
                              ↓ Redis check
                         Allow → Controller
                         Block → 429 Too Many Requests

Headers

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 45
X-RateLimit-Reset: 1699123200  # Unix timestamp when limit resets
Retry-After: 30  # seconds to wait (on 429)

Interview Tips

Token bucket is the standard answer — it allows bursts while maintaining average rate.
Always use Lua scripts in Redis for atomic read-modify-write.
Mention rate limiting per IP for anonymous, per user for authenticated, and per API key for third-party integrations.

Design: Rate Limiter

A rate limiter controls how many requests a client can make in a time period. It protects APIs from abuse, prevents DoS attacks, and enforces pricing tiers.

Requirements

Limit requests per user/IP: e.g., 100 req/min
Distributed: multiple API servers, shared state
Low latency: < 1ms overhead per check
No false positives: legitimate requests shouldn't be rejected

Algorithm 1: Fixed Window Counter

// Redis key: "rate:{userId}:{currentMinute}"
public boolean allowRequest(String userId) {
    String key = "rate:" + userId + ":" + (System.currentTimeMillis() / 60000);
    long count = redis.incr(key);
    if (count == 1) redis.expire(key, 120); // 2 min TTL
    return count <= LIMIT; // LIMIT = 100
}

❌ Problem: allows burst at window boundary (99 req at 0:59 + 99 req at 1:00 = 198 in 2 seconds)

Algorithm 2: Sliding Window Log

// Store timestamps of all requests in a sorted set
public boolean allowRequest(String userId) {
    long now = System.currentTimeMillis();
    long windowStart = now - 60000; // 1 minute window
    String key = "ratelimit:" + userId;

    redis.pipeline()
        .zremrangeByScore(key, 0, windowStart) // remove old entries
        .zadd(key, now, UUID.randomUUID().toString()) // add current request
        .expire(key, 120)
        .sync();

    return redis.zcard(key) <= LIMIT;
}

✅ Accurate, no boundary burst ❌ High memory: stores every request timestamp

Algorithm 3: Token Bucket (recommended)

// Tokens fill up at a steady rate; requests consume tokens
// Allow burst up to bucket capacity

public boolean allowRequest(String userId) {
    String key = "bucket:" + userId;
    long now = System.currentTimeMillis();

    // Lua script for atomicity
    String script = """
        local tokens = tonumber(redis.call('get', KEYS[1])) or CAPACITY
        local last = tonumber(redis.call('get', KEYS[2])) or NOW
        local refill = (NOW - last) / INTERVAL * RATE
        tokens = math.min(CAPACITY, tokens + refill)
        local allowed = tokens >= 1
        if allowed then tokens = tokens - 1 end
        redis.call('set', KEYS[1], tokens)
        redis.call('set', KEYS[2], NOW)
        return allowed and 1 or 0
        """;
    return redis.eval(script, 2, key + ":tokens", key + ":last") == 1L;
}

✅ Allows controlled bursts ✅ Smooth rate limiting

Algorithm 4: Sliding Window Counter (approximation)

// Current window count + previous window count weighted by overlap
public boolean allowRequest(String userId) {
    long now = System.currentTimeMillis() / 1000;
    long currentWindow = now / 60;
    double windowFraction = (now % 60) / 60.0;

    long prevCount  = getLong("rate:" + userId + ":" + (currentWindow - 1));
    long currCount  = getLong("rate:" + userId + ":" + currentWindow);

    double estimatedCount = prevCount * (1.0 - windowFraction) + currCount;
    if (estimatedCount >= LIMIT) return false;

    incr("rate:" + userId + ":" + currentWindow);
    return true;
}

Distributed Rate Limiting

With multiple API servers, use Redis as shared state:

         ┌──────────┐
User →  │  Server  │ ──→ Redis INCR
         └──────────┘      (shared counter)
         ┌──────────┐           ↑
User →  │  Server  │ ──────────┘
         └──────────┘

Use Redis Lua scripts for atomic increment + check.

Architecture

Request → API Gateway → Rate Limiter Middleware
                              ↓ Redis check
                         Allow → Controller
                         Block → 429 Too Many Requests

Headers

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 45
X-RateLimit-Reset: 1699123200  # Unix timestamp when limit resets
Retry-After: 30  # seconds to wait (on 429)

Interview Tips

Token bucket is the standard answer — it allows bursts while maintaining average rate.
Always use Lua scripts in Redis for atomic read-modify-write.
Mention rate limiting per IP for anonymous, per user for authenticated, and per API key for third-party integrations.