Rate Limiter LLD Design

A Rate Limiter is one of the most common LLD/System Design interview questions asked by companies like Amazon, Uber, PhonePe, Walmart, Microsoft, Google, and Atlassian.

A strong interview solution should demonstrate:

• OOP design
• SOLID principles
• Thread safety
• Extensibility
• Selection of appropriate algorithms
• Clean architecture

---

Problem Statement

Design a Rate Limiter that:

• Limits requests per user/API/IP.
• Supports multiple algorithms.
• Is thread-safe.
• Is easy to extend with new algorithms.
• Can be integrated with Spring Boot APIs.

Example:

Allow 5 requests per minute

Request 1 -> Allowed
Request 2 -> Allowed
...
Request 5 -> Allowed
Request 6 -> Rejected

---

Functional Requirements

• Limit requests
• Multiple clients
• Configurable limits
• Different algorithms
• Fast lookup
• Thread-safe

---

Non-Functional Requirements

• High throughput
• Low latency
• Extensible
• Memory efficient
• Distributed-ready

---

Supported Algorithms

Algorithm	Time	Memory	Interview Frequency
Fixed Window	O(1)	Low	⭐⭐⭐⭐⭐
Sliding Window Log	O(log n)	High	⭐⭐⭐⭐
Sliding Window Counter	O(1)	Medium	⭐⭐⭐⭐⭐
Token Bucket	O(1)	Low	⭐⭐⭐⭐⭐
Leaky Bucket	O(1)	Low	⭐⭐⭐⭐

---

High-Level Design

        Client
         │
       B ▼
     RateLimiter
         │
         ▼
 RateLimiterStrategy
         │
 ┌──────┼──────────┐
 ▼      ▼            ▼
Fixed  Token      Sliding
Window Bucket      Window

        │
        ▼
Storage
(HashMap / Redis)

---

Design Patterns

Pattern	Usage
Strategy	Different rate-limiting algorithms
Factory	Create algorithm implementations
Singleton	Configuration/manager (optional)
Dependency Injection	Inject strategy into service
Template Method (optional)	Common workflow

---

Core Models

Request Context

public class RequestContext {

    private final String clientId;
    private final long timestamp;

    public RequestContext(String clientId) {
        this.clientId = clientId;
        this.timestamp = System.currentTimeMillis();
    }

    public String getClientId() {
        return clientId;
    }

    public long getTimestamp() {
        return timestamp;
    }
}

---

Strategy Interface

public interface RateLimiterStrategy {

    boolean allow(RequestContext request);

}

---

Implementation 1: Fixed Window Counter

Idea

Window = 60 seconds

Counter

User A

1
2
3
4
5

Next request

Rejected

After 60 sec

Counter resets

Data Structure

ConcurrentHashMap

Key
↓

UserId

Value

Window Counter

Window Model

class Window {

    long startTime;
    AtomicInteger count;

}

Fixed Window Strategy

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class FixedWindowRateLimiter implements RateLimiterStrategy {

    private final long windowSizeMillis;
    private final int maxRequests;

    private final ConcurrentHashMap<String, Window> windows =
            new ConcurrentHashMap<>();

    public FixedWindowRateLimiter(int maxRequests,
                                  long windowSizeMillis) {

        this.maxRequests = maxRequests;
        this.windowSizeMillis = windowSizeMillis;
    }

    @Override
    public boolean allow(RequestContext request) {

        Window window = windows.computeIfAbsent(
                request.getClientId(),
                k -> new Window(System.currentTimeMillis()));

        synchronized (window) {

            long current = System.currentTimeMillis();

            if(current - window.startTime >= windowSizeMillis) {

                window.startTime = current;
                window.count.set(0);

            }

            if(window.count.incrementAndGet() <= maxRequests)
                return true;

            return false;

        }

    }

    static class Window {

        long startTime;

        AtomicInteger count = new AtomicInteger();

        Window(long startTime) {
            this.startTime = startTime;
        }

    }

}

---

Rate Limiter Service

public class RateLimiter {

    private final RateLimiterStrategy strategy;

    public RateLimiter(RateLimiterStrategy strategy) {
        this.strategy = strategy;
    }

    public boolean allow(String clientId) {
        return strategy.allow(new RequestContext(clientId));
    }
}

---

Client

public class Main {

    public static void main(String[] args) {

        RateLimiter limiter =
                new RateLimiter(
                        new FixedWindowRateLimiter(
                                5,
                                60000));

        for(int i=1;i<=7;i++) {

            System.out.println(
                    limiter.allow("USER-1"));

        }

    }

}

Output:

true
true
true
true
true
false
false

---

How to Add More Algorithms

Since the design uses the Strategy Pattern, adding a new algorithm is straightforward:

• TokenBucketRateLimiter implements RateLimiterStrategy
• SlidingWindowRateLimiter implements RateLimiterStrategy
• LeakyBucketRateLimiter implements RateLimiterStrategy

No changes are required in the RateLimiter service, satisfying the Open/Closed Principle.

---

Thread Safety

• ConcurrentHashMap for concurrent client access.
• AtomicInteger for efficient counter updates.
• Synchronization at the per-client window level, avoiding a global lock.
• Minimal contention because each client has its own window object.

---

SOLID Principles

Principle	Application
Single Responsibility	Each strategy implements one algorithm.
Open/Closed	New algorithms can be added without modifying existing code.
Liskov Substitution	Any RateLimiterStrategy can be substituted.
Interface Segregation	Small, focused strategy interface.
Dependency Inversion	RateLimiter depends on the abstraction, not concrete implementations.

---

Production Enhancements

For a production-ready distributed rate limiter, consider:

• Use Redis with atomic operations (INCR, EXPIRE) or Lua scripts for shared state across instances.
• Support configurable limits per API, tenant, or user.
• Implement asynchronous cleanup of inactive clients.
• Add metrics (allowed, rejected, latency) via Micrometer/Prometheus.
• Return Retry-After headers for HTTP 429 responses.
• Support burst traffic using the Token Bucket algorithm.
• Integrate with API gateways (NGINX, Envoy, Kong, Spring Cloud Gateway).

---

Common Interview Follow-up Questions

1. Why use ConcurrentHashMap instead of HashMap?
2. Why is AtomicInteger used instead of int?
3. How would you implement a distributed rate limiter?
4. How do you avoid memory leaks from inactive clients?
5. Which algorithm handles burst traffic best?
6. How would you implement rate limiting in Redis?
7. How would you support different limits for different users or APIs?
8. How would you expose remaining quota and reset time?
9. How would you benchmark the implementation under high concurrency?
10. When would you choose Token Bucket over Sliding Window?

This design is suitable for Java LLD interviews and can be progressively extended into a production-grade, distributed rate-limiting service.