Rate Limiter Best Approach (Circular Buffer or Memory efficient approach)

Anonymous User

583

Has Anyone recently tried implementing Rate Limiter?
Basic requirement :

MAX_REQ_PER_SEC = 3
CLIENT_ID to be maintained - for different clients, max allowed request counter should be maintained.
How can you make this memory efficient, like what if the stale data is present how can that be removed or a functionality of reset data mapping.

I found some code but unable to understand how can I make this memory efficient or give a functionality on how to reset data. For example: enteries which are present System.currentTime - 5000ms is stale and should be removed from data structure we are using.

I checked ring buffer(https://en.wikipedia.org/wiki/Circular_buffer) has anyone tried implementing the same??

public class UserFixedWindowCounter {
    private final int REQUEST_LIMIT = 3;
    private final long TIME_LIMIT = 1000L;

    public class HitCounter{
        Queue<Long> q;
        HitCounter(){
            q = new LinkedList<>();
        }

        public boolean hit(long timestamp) {
            while (!q.isEmpty() && timestamp - q.peek() >= TIME_LIMIT)
                q.peek();

            if (q.size() < REQUEST_LIMIT) {
                q.offer(timestamp);
                return true;
            }

            return false;
        }
    }

    public boolean isAllow(String clientId){
        HashMap<String, HitCounter> map = new HashMap<>();
        HitCounter h = map.get(clientId);
        long currTimeStamp = System.currentTimeMillis();

        if (h == null) {
            h = new HitCounter();
            map.put(clientId, h);
        }

        return h.hit(currTimeStamp);
    }
}

Comments (1)