Design a Rate Limiter system

Problem Statement

Design a Rate Limiter system that controls how many requests a user or service can make in a given time window. The system should prevent abuse, protect backend services, and ensure fair usage across all users.

Asked In Companies

Google Amazon Microsoft Meta Stripe Uber Netflix Atlassian LinkedIn Salesforce Oracle PayPal Twitter

---

Functional Requirements

• The system should limit the number of requests per user or IP
• It should support Fixed Window algorithm
• It should support Sliding Window algorithm
• Each request should be either allowed or rejected
• The limiter should work in-memory (can be extended later to distributed systems)

---

Objects Required

• RateLimiter
• FixedWindowRateLimiter
• SlidingWindowRateLimiter
• RequestBucket
• UserKey (identifier)

---

RateLimiter Interface

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

The RateLimiter interface defines a simple contract for all rate limiting strategies. Any implementation must decide whether a request should be allowed or blocked.

---

FixedWindowRateLimiter Class

import java.util.concurrent.ConcurrentHashMap;

public class FixedWindowRateLimiter implements RateLimiter {

    private final int maxRequests;
    private final long windowSizeInMillis;

    private static class WindowData {
        int count;
        long windowStart;
    }

    private ConcurrentHashMap store = new ConcurrentHashMap<>();

    public FixedWindowRateLimiter(int maxRequests, long windowSizeInMillis) {
        this.maxRequests = maxRequests;
        this.windowSizeInMillis = windowSizeInMillis;
    }

    @Override
    public synchronized boolean allowRequest(String userId) {

        long currentTime = System.currentTimeMillis();

        WindowData data = store.getOrDefault(userId, new WindowData());

        if (currentTime - data.windowStart > windowSizeInMillis) {
            data.windowStart = currentTime;
            data.count = 0;
        }

        if (data.count < maxRequests) {
            data.count++;
            store.put(userId, data);
            return true;
        }

        return false;
    }
}

The Fixed Window strategy divides time into fixed intervals (like 1 minute windows).

The constructor sets the maximum allowed requests and the time window size.

The allowRequest() method checks whether the current request falls into the same window. If the window has expired, it resets the counter.

If the request count is within limit, it is allowed; otherwise, it is rejected.

---

SlidingWindowRateLimiter Class

import java.util.*;

public class SlidingWindowRateLimiter implements RateLimiter {

    private final int maxRequests;
    private final long windowSizeInMillis;

    private static class RequestLog {
        Queue timestamps = new LinkedList<>();
    }

    private Map store = new HashMap<>();

    public SlidingWindowRateLimiter(int maxRequests, long windowSizeInMillis) {
        this.maxRequests = maxRequests;
        this.windowSizeInMillis = windowSizeInMillis;
    }

    @Override
    public synchronized boolean allowRequest(String userId) {

        long now = System.currentTimeMillis();

        RequestLog log = store.getOrDefault(userId, new RequestLog());

        while (!log.timestamps.isEmpty()
                && now - log.timestamps.peek() > windowSizeInMillis) {
            log.timestamps.poll();
        }

        if (log.timestamps.size() < maxRequests) {
            log.timestamps.add(now);
            store.put(userId, log);
            return true;
        }

        return false;
    }
}

The Sliding Window strategy is more accurate because it considers the exact timestamps of requests.

The constructor defines how many requests are allowed in a time window.

The allowRequest() method first removes expired timestamps from the queue.

If the remaining number of requests is within the limit, the request is allowed and timestamp is added.

Otherwise, the request is rejected.

---

RequestBucket Class (Optional Abstraction)

import java.util.*;

public class RequestBucket {

    private Queue timestamps = new LinkedList<>();

    public void addRequest(long timestamp) {
        timestamps.add(timestamp);
    }

    public void removeOldRequests(long currentTime, long windowSize) {

        while (!timestamps.isEmpty()
                && currentTime - timestamps.peek() > windowSize) {
            timestamps.poll();
        }
    }

    public int size() {
        return timestamps.size();
    }
}

The RequestBucket class isolates request tracking logic.

addRequest() stores a new request timestamp.

removeOldRequests() cleans up expired requests outside the time window.

size() returns the current number of active requests in the window.

---

Main Class

public class Main {

    public static void main(String[] args) {

        RateLimiter fixedLimiter =
                new FixedWindowRateLimiter(3, 10000);

        System.out.println(fixedLimiter.allowRequest("U1"));
        System.out.println(fixedLimiter.allowRequest("U1"));
        System.out.println(fixedLimiter.allowRequest("U1"));
        System.out.println(fixedLimiter.allowRequest("U1"));

        RateLimiter slidingLimiter =
                new SlidingWindowRateLimiter(3, 10000);

        System.out.println(slidingLimiter.allowRequest("U1"));
        System.out.println(slidingLimiter.allowRequest("U1"));
        System.out.println(slidingLimiter.allowRequest("U1"));
        System.out.println(slidingLimiter.allowRequest("U1"));
    }
}

The main method demonstrates both fixed window and sliding window rate limiting.

We simulate multiple requests from the same user and observe how the limiter blocks excess requests.

---

Class Diagram

Also See

• Most Commonly Asked Low Level Design Interview Questions
• Top 10 Low Level Design Interview Questions