🚦

Design a Rate Limiter

Protect APIs with token bucket or sliding window — asked at Google, Meta, Stripe, and almost every backend LLD round tied to system design.

📊 Medium⏱ 35–45 min🏢 Google · Meta · Amazon · Stripe · Uber · Cloudflare-style infra interviews

🎯 Interview goal

Expose boolean allow(String key). Implement Token Bucket (smooth burst) or Sliding Window (accurate count). Use Strategy + Factory so gateway code stays stable when algorithms change.

📋

The interview question

“Design a rate limiter for an API.” Given a user or IP key, return whether a request is allowed within N requests per time window.

Often a follow-up to HLD gateway questions — here they want working code and algorithm trade-offs.

💡

Clarify distributed vs single-node early. Code the single-node version; describe Redis + Lua for distributed.

❓

Clarifying questions (ask before coding)

1Per user, per IP, or per API key?

Why askDefines the key passed to allow().

2Fixed window, sliding window, or token bucket?

Why askDifferent burst/smoothness — pick one and implement cleanly.

3What happens when limited — 429, queue, or drop silently?

Why askReturn false vs throw — document contract.

4Distributed across many servers?

Why askIn-memory map is v1; Redis atomic counters for production.

✅

Requirements & assumptions (state aloud)

API: allow(String key) → boolean.
Rules: max R requests per W seconds (configurable).
Thread-safe for concurrent requests same key.
v1: in-process; mention Redis for multi-instance.
Out of scope: billing tiers UI — extension only.

🧩

High-level design

Gateway calls RateLimiter.allow(clientId) before forwarding. Denied → HTTP 429.

Token bucket: refill tokens at steady rate; allow burst up to bucket size.

Sliding window: store timestamps of recent hits; count in last W seconds.

RateLimiter interface
TokenBucketRateLimiter / SlidingWindowRateLimiter
RateLimiterFactory for algorithm swap

Rate limiter flow — Client → limiter → allow or 429

📐

UML class diagram (optional)

Draw interface + 2 implementations + factory — under 5 minutes on board.

Rate limiter UML — Strategy implementations behind one interface

🎨

Design patterns used (and why)

Pattern	Where	Why (interview soundbite)
🎯Strategy	`RateLimiter` implementations	Swap algorithm without changing gateway.
🏭Factory	`RateLimiterFactory`	Construct limiter from config / env.

💻

Full solution — interface & token bucket

1. Interface & configjava

public interface RateLimiter {
    // Returns true if request for key is within limit; false → reject (429)
    boolean allow(String key);
}

public record RateLimitConfig(int maxRequests, int windowSeconds) {}

public enum LimiterType { TOKEN_BUCKET, SLIDING_WINDOW }

2. Token bucket (smooth burst)java

public class TokenBucketRateLimiter implements RateLimiter {
    private final int capacity;
    private final double refillPerSecond;
    private final Map<String, BucketState> buckets = new ConcurrentHashMap<>();

    // capacity = max burst; refillPerSecond = steady refill rate
    public TokenBucketRateLimiter(int capacity, int refillPerSecond) {
        this.capacity = capacity;
        this.refillPerSecond = refillPerSecond;
    }

    // Refills bucket for key, consumes one token if available
    @Override
    public boolean allow(String key) {
        BucketState state = buckets.computeIfAbsent(key, k -> new BucketState(capacity));
        synchronized (state) {
            state.refill(refillPerSecond, capacity);
            if (state.tokens >= 1) {
                state.tokens -= 1;
                return true;
            }
            return false;
        }
    }

    private static class BucketState {
        double tokens;
        long lastRefillNanos;

        // Starts full at capacity
        BucketState(int capacity) {
            this.tokens = capacity;
            this.lastRefillNanos = System.nanoTime();
        }

        // Adds tokens based on elapsed time, capped at capacity
        void refill(double rate, int cap) {
            long now = System.nanoTime();
            double elapsed = (now - lastRefillNanos) / 1_000_000_000.0;
            tokens = Math.min(cap, tokens + elapsed * rate);
            lastRefillNanos = now;
        }
    }
}

⚙️

Full solution — sliding window & factory

3. Sliding window logjava

public class SlidingWindowRateLimiter implements RateLimiter {
    private final int maxRequests;
    private final long windowMillis;
    private final Map<String, Deque<Long>> hits = new ConcurrentHashMap<>();

    // maxRequests allowed within rolling windowSeconds
    public SlidingWindowRateLimiter(int maxRequests, int windowSeconds) {
        this.maxRequests = maxRequests;
        this.windowMillis = windowSeconds * 1000L;
    }

    // Drops timestamps outside window; denies if count already at max
    @Override
    public boolean allow(String key) {
        Deque<Long> q = hits.computeIfAbsent(key, k -> new ArrayDeque<>());
        synchronized (q) {
            long now = System.currentTimeMillis();
            while (!q.isEmpty() && now - q.peekFirst() >= windowMillis)
                q.pollFirst();
            if (q.size() >= maxRequests) return false;
            q.addLast(now);
            return true;
        }
    }
}

4. Factory + demojava

public class RateLimiterFactory {
    // Builds the limiter implementation from type + config
    public static RateLimiter create(LimiterType type, RateLimitConfig cfg) {
        return switch (type) {
            case TOKEN_BUCKET -> new TokenBucketRateLimiter(cfg.maxRequests(), cfg.maxRequests() / cfg.windowSeconds());
            case SLIDING_WINDOW -> new SlidingWindowRateLimiter(cfg.maxRequests(), cfg.windowSeconds());
        };
    }
}

public class RateLimiterDemo {
    // Fires 5 requests against same key to show allow/deny
    public static void main(String[] args) {
        RateLimiter limiter = RateLimiterFactory.create(
            LimiterType.SLIDING_WINDOW, new RateLimitConfig(3, 60));
        for (int i = 0; i < 5; i++)
            System.out.println("req " + i + ": " + limiter.allow("user-42"));
    }
}

🎤

While you code — questions interviewers ask

🚀

Extensions & follow-ups

Leaky bucket variant.
Hierarchical limits (global + per user).
Redis cell (fixed window counter) for cheap distributed v1.

⚠️

Common mistakes (fail signals)

Non-thread-safe counter under concurrency.
Fixed window only — double traffic at boundary (mention fix).
No key abstraction — hard-coded global counter.

🧾

60-second cheat sheet

APIallow(key) → bool

AlgorithmsToken bucket (burst) · Sliding window (accurate)

PatternsStrategy + Factory

DistributedRedis atomic counter / sorted set

HTTP429 + Retry-After header

🔗