Design (LLD) Rate Limiter - Machine Coding
Below Solution is only for single-threaded env, multi-threading and distributed are covered in premium course.
Features Required:
Configurable Limits: Ability to set request limits per unit of time.
Support for Different Time Windows: Support for different types of time windows (e.g., sliding window, fixed window).
Thread Safety: Ensure that the rate limiter can handle concurrent access correctly.
Ease of Configuration: Easily configurable limits and time windows.
Extensibility: Allow extension for different rate-limiting strategies.
Metrics and Logging: Provide metrics and logging for monitoring purposes.
Design Patterns
Strategy Pattern: Allows for flexibility in changing rate-limiting algorithms without modifying the client code.
Singleton Pattern: Ensures only one instance of the rate limiter exists, maintaining a consistent state.
Factory Pattern: Encapsulates the creation logic for different rate-limiting strategies, promoting clean code and adherence to the Open/Closed principle.
Template Method Pattern: Provides a standard process for rate-limiting while allowing specific steps to be defined by subclasses.
Multiple Algorithms :
Fixed Window Algorithm: Counts the number of requests in fixed time windows.
Sliding Window Algorithm: Uses a rolling time window to count requests.
Code (Java)
1. RateLimiter Interface
public interface RateLimiter {
boolean allowRequest(String clientId);
}
2. FixedWindowRateLimiter Class
import java.util.HashMap;
import java.util.Map;
public class FixedWindowRateLimiter implements RateLimiter {
private final int maxRequests;
private final long windowSizeInMillis;
private Map<String, Integer> requestCounts;
private Map<String, Long> windowStartTimes;
public FixedWindowRateLimiter(int maxRequests, long windowSizeInMillis) {
this.maxRequests = maxRequests;
this.windowSizeInMillis = windowSizeInMillis;
this.requestCounts = new HashMap<>();
this.windowStartTimes = new HashMap<>();
}
@Override
public boolean allowRequest(String clientId) {
long currentTime = System.currentTimeMillis();
windowStartTimes.putIfAbsent(clientId, currentTime);
requestCounts.putIfAbsent(clientId, 0);
long windowStartTime = windowStartTimes.get(clientId);
if (currentTime - windowStartTime >= windowSizeInMillis) {
windowStartTimes.put(clientId, currentTime);
requestCounts.put(clientId, 0);
}
int requestCount = requestCounts.get(clientId);
if (requestCount < maxRequests) {
requestCounts.put(clientId, requestCount + 1);
return true;
}
return false;
}
}
3. SlidingWindowRateLimiter Class
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;
public class SlidingWindowRateLimiter implements RateLimiter {
private final int maxRequests;
private final long windowSizeInMillis;
private Map<String, Queue<Long>> requestTimestamps;
public SlidingWindowRateLimiter(int maxRequests, long windowSizeInMillis) {
this.maxRequests = maxRequests;
this.windowSizeInMillis = windowSizeInMillis;
this.requestTimestamps = new HashMap<>();
}
@Override
public boolean allowRequest(String clientId) {
long currentTime = System.currentTimeMillis();
requestTimestamps.putIfAbsent(clientId, new LinkedList<>());
Queue<Long> timestamps = requestTimestamps.get(clientId);
while (!timestamps.isEmpty() && currentTime - timestamps.peek() > windowSizeInMillis) {
timestamps.poll();
}
if (timestamps.size() < maxRequests) {
timestamps.add(currentTime);
return true;
}
return false;
}
}
4. RateLimiterFactory Class
public class RateLimiterFactory {
public static RateLimiter createRateLimiter(String type, int maxRequests, long windowSizeInMillis) {
switch (type.toLowerCase()) {
case "fixed":
return new FixedWindowRateLimiter(maxRequests, windowSizeInMillis);
case "sliding":
return new SlidingWindowRateLimiter(maxRequests, windowSizeInMillis);
default:
throw new IllegalArgumentException("Unknown rate limiter type");
}
}
}
5. Singleton RateLimiterManager Class
public class RateLimiterManager {
private static RateLimiterManager instance;
private RateLimiter rateLimiter;
private RateLimiterManager() {
// Example initialization with a fixed window rate limiter
this.rateLimiter = RateLimiterFactory.createRateLimiter("fixed", 100, 60000);
}
public static RateLimiterManager getInstance() {
if (instance == null) {
synchronized (RateLimiterManager.class) {
if (instance == null) {
instance = new RateLimiterManager();
}
}
}
return instance;
}
public boolean allowRequest(String clientId) {
return rateLimiter.allowRequest(clientId);
}
}
6. Template Method Pattern - Abstract RateLimiter Class
public abstract class AbstractRateLimiter implements RateLimiter {
protected int maxRequests;
protected long windowSizeInMillis;
public AbstractRateLimiter(int maxRequests, long windowSizeInMillis) {
this.maxRequests = maxRequests;
this.windowSizeInMillis = windowSizeInMillis;
}
@Override
public boolean allowRequest(String clientId) {
return isRequestAllowed(clientId);
}
protected abstract boolean isRequestAllowed(String clientId);
}
7. FixedWindowRateLimiter Using Template Method Pattern
import java.util.HashMap;
import java.util.Map;
public class FixedWindowRateLimiterWithTemplate extends AbstractRateLimiter {
private Map<String, Integer> requestCounts;
private Map<String, Long> windowStartTimes;
public FixedWindowRateLimiterWithTemplate(int maxRequests, long windowSizeInMillis) {
super(maxRequests, windowSizeInMillis);
this.requestCounts = new HashMap<>();
this.windowStartTimes = new HashMap<>();
}
@Override
protected boolean isRequestAllowed(String clientId) {
long currentTime = System.currentTimeMillis();
windowStartTimes.putIfAbsent(clientId, currentTime);
requestCounts.putIfAbsent(clientId, 0);
long windowStartTime = windowStartTimes.get(clientId);
if (currentTime - windowStartTime >= windowSizeInMillis) {
windowStartTimes.put(clientId, currentTime);
requestCounts.put(clientId, 0);
}
int requestCount = requestCounts.get(clientId);
if (requestCount < maxRequests) {
requestCounts.put(clientId, requestCount + 1);
return true;
}
return false;
}
}
8. SlidingWindowRateLimiter Using Template Method Pattern
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;
public class SlidingWindowRateLimiterWithTemplate extends AbstractRateLimiter {
private Map<String, Queue<Long>> requestTimestamps;
public SlidingWindowRateLimiterWithTemplate(int maxRequests, long windowSizeInMillis) {
super(maxRequests, windowSizeInMillis);
this.requestTimestamps = new HashMap<>();
}
@Override
protected boolean isRequestAllowed(String clientId) {
long currentTime = System.currentTimeMillis();
requestTimestamps.putIfAbsent(clientId, new LinkedList<>());
Queue<Long> timestamps = requestTimestamps.get(clientId);
while (!timestamps.isEmpty() && currentTime - timestamps.peek() > windowSizeInMillis) {
timestamps.poll();
}
if (timestamps.size() < maxRequests) {
timestamps.add(currentTime);
return true;
}
return false;
}
}
9. Main Class to Test the Implementation
public class Main {
public static void main(String[] args) {
RateLimiter fixedWindowRateLimiter = RateLimiterFactory.createRateLimiter("fixed", 10, 60000);
RateLimiter slidingWindowRateLimiter = RateLimiterFactory.createRateLimiter("sliding", 10, 60000);
// Testing Fixed Window Rate Limiter
System.out.println("Fixed Window Rate Limiter:");
for (int i = 0; i < 12; i++) {
System.out.println(fixedWindowRateLimiter.allowRequest("client1"));
}
// Testing Sliding Window Rate Limiter
System.out.println("Sliding Window Rate Limiter:");
for (int i = 0; i < 12; i++) {
System.out.println(slidingWindowRateLimiter.allowRequest("client2"));
}
}
}
Explanation:
RateLimiter Interface: Defines the contract for any rate limiter.
FixedWindowRateLimiter and SlidingWindowRateLimiter Classes: Implement the fixed window and sliding window rate-limiting algorithms.
RateLimiterFactory Class: Provides a factory method to create instances of different rate limiters.
RateLimiterManager Class: Implements the Singleton pattern to ensure a single instance of the rate limiter.
AbstractRateLimiter Class: Implements the Template Method pattern, providing a skeleton for rate limiting.
Q. What if we want to change the limits in runtime dynamically ?