There was one interesting problem I have encounter while preparing for a multithreading coding interview.
Question: We have an application for which we need to implement RateLimiter,
Rate Limiter is an interface which will play a role to limit the number of Request client send to Server in a given time.
In the Current Question, it was asked to implement a rate limit who will do 2 things.
1) It will only allow one client to send 100 requests in 1 hrs. ( one client will be identified by the client Id).
2) It will allow a total of 10000 requests to be passed to the server in 1 hrs.
Rate Limiter Interface
interface RateLimiter{
boolean accept(String clientId);
}Java Implementation of Rate Limiter
When we need to Implement such things where there is any restriction of accessing the resource for limited count We always start thinking using Semaphores
Why Semaphores?
Because it maintains the multi-access locking on its own with defined number of threads to access the critical section.
MyRateLimiter.java
class MyRateLimiter {
private Semaphore semaphore;
private int maxPermits;
private TimeUnit timePeriod;
private ScheduledExecutorService scheduler;
public static MyRateLimiter create(int permits, TimeUnit timePeriod) {
MyRateLimiter limiter = new MyRateLimiter(permits, timePeriod);
limiter.schedulePermit();
return limiter;
}
private MyRateLimiter(int permits, TimeUnit timePeriod) {
this.semaphore = new Semaphore(permits);
this.maxPermits = permits;
this.timePeriod = timePeriod;
}
public boolean tryAcquire() {
return semaphore.tryAcquire();
}
public void stop() {
scheduler.shutdownNow();
}
public void schedulePermit() {
scheduler = Executors.newScheduledThreadPool(1);
scheduler.scheduleAtFixedRate(() -> {
semaphore.release(maxPermits - semaphore.availablePermits());
}, 0, 1, timePeriod);
}
} RateLimiterImpl.java
class RateLimiterImpl implements RateLimiter{
private static long MINUTE_TIME_LIMIT=1000*60L; // update as per question
private static long REQUEST_ALLOWED_PER_MINUTE=10000; // Update as per question
Queue<Long> q = new LinkedList<>();
private static int minuteLimit=100;
private Map<String, Optional<MyRateLimiter>> limiters = new ConcurrentHashMap<>();
@Override
public boolean accept(String clientId) {
if(!hit(System.currentTimeMillis())) {
return false;
}
Optional<MyRateLimiter> rateLimiter = getRateLimiter(clientId);
if(rateLimiter.isPresent()) {
boolean canAcquire= rateLimiter.get().tryAcquire();
if(canAcquire)
return q.add(System.currentTimeMillis());
}
return false;
}
private boolean hit(long timestamp) {
while(!q.isEmpty() && timestamp-q.peek() >= MINUTE_TIME_LIMIT) q.poll();
if(q.size() < REQUEST_ALLOWED_PER_MINUTE)
{
q.offer(timestamp);
return true;
}
return false;
}
private Optional<MyRateLimiter> getRateLimiter(String clientId) {
return limiters.computeIfAbsent(clientId, id -> {
return Optional.of(createRateLimiter(id));
});
}
private MyRateLimiter createRateLimiter(String clientId) {
return MyRateLimiter.create(minuteLimit, TimeUnit.MINUTES);
}
}
Main Class Calling
public class RateLimiterDemo {
public static void main(String[] args) {
RateLimiter limiter = new RateLimiterImpl();
System.out.println("test1 " + limiter.accept("test1"));
System.out.println("test1 " +limiter.accept("test1"));
System.out.println("test1 " +limiter.accept("test1"));
System.out.println("test1 " +limiter.accept("test1"));
System.out.println("test2 " +limiter.accept("test2"));
System.out.println("test2 " +limiter.accept("test2"));
System.out.println("test2 " +limiter.accept("test2"));
System.out.println("test2 " +limiter.accept("test2"));
System.out.println("test1 " +limiter.accept("test1"));
}
}You can also check the Code from HERE
Hope this will help you in understanding the Code
