Thursday, June 25, 2020

[Multi threading Interview Question ]Rate Limiter Implementation in java

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

1 comment:

  1. This extremely technical apprenticeship program requires a thorough understanding of the material taught on this program. SCREW PLASTICATING INJECTION MOLDING– A approach during which the plastic is transformed from pellets to a viscose soften by Vacuum Storage Bags means of an extruder screw which is an integral half of} the molding machine. Machines are both single stage or double stage during which the material is plasticated in a single cylinder and then fed to a second for injection right into a mildew. EMBOSSING– Techniques used to create depressions of a specific pattern in plastics movie and sheeting. Such embossing in the type of floor patterns on molded half by the therapy of the mildew floor by photoengraving or different course of.

    ReplyDelete