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 ?
To dynamically change the limits at runtime, we need to modify our design to support updating the configuration of the rate limiter. We have covered this in our premium course.
Q. Other Issues in the Above Design ?
Lack of Persistence: The current design doesn't persist the rate-limiting state. If the system restarts, all counters and timestamps will reset. This could lead to abuse if the service is restarted frequently.
Single Point of Failure: The Singleton pattern used for
RateLimiterManagerintroduces a single point of failure. If the instance is compromised or corrupted, it can affect the entire system's rate limiting.Scalability Issues: The current design is more suited for single-threaded environments. For multi-threaded or distributed systems, additional mechanisms are required to ensure consistency and scalability (e.g., using distributed data stores like Redis).
Granularity of Configuration Updates: Updating the configuration applies globally to all clients. This design does not support per-client rate-limiting configuration, which might be necessary for more fine-grained control.
Performance Overhead: Using synchronized blocks or methods for ensuring thread safety can introduce performance overhead, especially under high load.
Limited Rate-Limiting Strategies: Only fixed window and sliding window strategies are implemented. There are other strategies like token bucket and leaky bucket which might be more suitable for certain scenarios.
No Support for Burst Traffic: The design does not accommodate burst traffic scenarios where occasional spikes are allowed within a larger rate limit.
Complexity in Dynamic Updates: The dynamic update mechanism can become complex if there are many observers or if the update process is not efficient.
Inadequate Monitoring and Logging: Basic metrics and logging are suggested, but a comprehensive monitoring and logging system is necessary for production environments to track rate-limiting events and anomalies.
Potential Memory Leaks: Using
HashMapandLinkedListto store request counts and timestamps can lead to memory leaks if client identifiers are not cleaned up properly.
Addressing the Issues
We have covered this in our premium course.
Complete Working Code in IDE
Soon will add YouTube video on this channel - https://www.youtube.com/channel/UCgdIgkU_hq0VtGPhVPA0CPQ