Rate Limiter implementation in Java

Question

I have been working on implementing rate limiter in Java. Following is my approach.

I have used 'sliding window with counters' technique to implement this rate limiter. What I do is instead of rate limiting per second I rate limit per minute. This allows me to create 60 buckets (one for each minute) for each hour for each user. Any time the user has crossed the threshold I reject the requests.

Reason for adopting this approach is that it can easily scale to any number of users as each user can have at most 60 buckets keeping track of the number of requests. After every hour the buckets are refreshed.

Please take a look at this and let me know what's good and what's bad about this approach.

Steps:

1. First we will use a HashMap to store the number of requests for every user.
2. For every user, fill up the map with 60 fixed minute slots.
3. For every request timestamp we will truncate it to the closest rounded minute just passed.
   • if the current timestamp is within the current minute then
     • we increment the counter for current minute if the current request is within the limit
     • we reject the request if it has exceeded the rate limit
   • if the new timestamp has passed the current minute then create the new minute key and set the counter to 1
   • if the current timestamp is in the next hour then delete the entries from the previous hour and create new set of 60 minute slots. Whenever we step into a new hour, all the minute slots are recycled.

    public class RateLimitService {
    
        private static final long MILLIS_IN_SECOND = 1000;
        private static final long MILLIS_IN_MIUTE = 60000;
        private static final long MILLIS_IN_HOUR = 3600000;
        private static final long MILLIS_IN_DAY = 86400000;
        
        private static final int RATE_LIMIT_PER_MIN = 3;
        
        private static final int RATE_LIMIT_PER_HOUR = 10;
        
        private static Map<Long, ConcurrentSkipListMap<Long, Integer>> limitMap = new HashMap<Long, ConcurrentSkipListMap<Long, Integer>>();
        private static Map<Long, Integer> requestCounterHourly = new HashMap<Long, Integer>();
        
        public static void main(String[] args) {
            
            RateLimitService rls = new RateLimitService();
            rls.test();
        }
        
        private void test() {
            
            System.out.println("=============================");
            System.out.println(String.format("Max reqs in minute: %d | Max reqs in hour: %d", RATE_LIMIT_PER_MIN, RATE_LIMIT_PER_HOUR));
            System.out.println("=============================");
            
            Long userId = 1L;
            refreshMinuteSlots(userId, System.currentTimeMillis());
            
            long reqT = System.currentTimeMillis();
            int sleepTime = 10000;
            
            for (int i=0; i<6; i++) {
                reqT = System.currentTimeMillis();
                boolean isAllowed = isAllowed(reqT, 1L);
                System.out.println(String.format("Req at %d allowed? %s (totalRequestsInHour: %d) ", reqT, isAllowed, requestCounterHourly.get(userId)));
                
                sleepTime *= 2; // exponential
                sleep(sleepTime);
            }
            
            System.out.println("=============================");
            printTimes(limitMap.get(userId));
            System.out.println("=============================");
            
        }
        
        private void sleep(int time) {
            try {
                Thread.sleep(time);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        
    
        private boolean isAllowed(Long reqT, Long userId) {
            
            ConcurrentSkipListMap<Long, Integer> times = limitMap.get(userId);
            
            Long truncatedMin = truncate(reqT, ChronoUnit.MINUTES); // truncate to the beginning of minute
            
            if (times != null) {
                Long truncatedHour = truncate(reqT, ChronoUnit.HOURS); // truncate to the beginning of hour
                Long truncatedDay = truncate(reqT, ChronoUnit.DAYS); // truncate to the beginning of the day
                
                if ((truncatedMin - truncatedDay >= MILLIS_IN_DAY)
                        || (truncatedMin - truncatedHour >= MILLIS_IN_HOUR)) {
                    
                    refreshMinuteSlots(userId, reqT);
                    requestCounterHourly.put(userId, 0);
                }
                
            } else {
                refreshMinuteSlots(userId, reqT);
                
            }
            
            times = limitMap.get(userId);
            
            // Reject if greater than rate limit threshold
            if ((times.get(truncatedMin) >= RATE_LIMIT_PER_MIN) || (requestCounterHourly.getOrDefault(userId, 0) >= RATE_LIMIT_PER_HOUR)) {
                return false;
            }
            
            System.out.println(String.format("Putting reqT %d in the bucket %d", reqT, truncatedMin));
            times.put(truncatedMin, times.get(truncatedMin) + 1);
            limitMap.put(userId, times);
            requestCounterHourly.put(userId, requestCounterHourly.getOrDefault(userId, 0) + 1);
            
            return true;
        }
        
        
        /*
         * Truncates the timestamp to the closest time unit.
         * 
         */
        private Long truncate(Long time, ChronoUnit unit) {
            SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss'Z'");
            sdf.setTimeZone(TimeZone.getTimeZone("UTC"));
            Date date = new Date(time);
            String dateStr = sdf.format(date);
            
            Instant instant = Instant.parse(dateStr);
            Instant returnValue = instant.truncatedTo(unit);
            
            return returnValue.toEpochMilli();
        }
        
        /* Add new set of minute slots.
         * 
         * @param userId
         * @param reqT
         */
        private void refreshMinuteSlots(Long userId, Long reqT) {
            Long minofDay = truncate(reqT, ChronoUnit.HOURS); // start min of the hour
            
            ConcurrentSkipListMap<Long, Integer> times = new ConcurrentSkipListMap<Long, Integer>();
            
            for (int i=0; i<=59; i++) { // add rounded minutes in an hour to the map
                times.put(minofDay, 0);
                minofDay += MILLIS_IN_MIUTE;
            }
            
            limitMap.put(userId, times);
        }
        
        /*
         * Prints the current requests numbers from the map.
         */
        private void printTimes(ConcurrentSkipListMap<Long, Integer> times) {
            
            System.out.println("Current state of the times for user...");
            for (Long time : times.keySet()) {
                System.out.println(time + " : " + times.get(time));
            }
        }
    }

Answer 1

You can uses the java.util.concurrent.TimeUnit to calculate the number of x

Java offers a class that convert time into other units.

In your case, you can replace, if you want, the hardcoded constants.

    private static final long MILLIS_IN_SECOND = TimeUnit.SECONDS.toMillis(1); //1000
    private static final long MILLIS_IN_MIUTE = TimeUnit.MINUTES.toMillis(1); //60000
    private static final long MILLIS_IN_HOUR = TimeUnit.HOURS.toMillis(1);//3600000
    private static final long MILLIS_IN_DAY = TimeUnit.DAYS.toMillis(1);//86400000

You can omit the values in the right diamond operator

Since you already defined the values in the left diamond operator, you can add an empty one in the right.

before

private static Map<String, String> values = new HashMap<String, String>();

after

private static Map<String, String> values = new HashMap<>();

Use java.io.PrintStream#printf instead of java.io.PrintStream#println when you have to concatenate

java.io.PrintStream#printf offer you to use patterns to build the string without concatenating it manually. The only downside is you will be forced to add the break line character yourself; in java you can use the %n to break the line (portable between various platforms) or uses the traditional \n / \r\n.

before

System.out.println(String.format("Max reqs in minute: %d | Max reqs in hour: %d", RATE_LIMIT_PER_MIN, RATE_LIMIT_PER_HOUR));

after

System.out.printf("Max reqs in minute: %d | Max reqs in hour: %d%n", RATE_LIMIT_PER_MIN, RATE_LIMIT_PER_HOUR);

Always use the primitives when possible

When you know that it's impossible to get a null value with the number, try to use the primitives; this can prevent the unboxing of the value in some case.

RateLimitService#refreshMinuteSlots method

In my opinion, you can use the java.time.Instant#ofEpochMilli to convert the timestamp into an java.time.Instant; I can be wrong on this, but I don’t see the advantages of formatting a date to reconvert it to an instant since the java.lang.System#currentTimeMillis already return the timestamp in UTC.

before

private static long truncate(long time, ChronoUnit unit) {
   SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss'Z'");
   sdf.setTimeZone(TimeZone.getTimeZone("UTC"));
   Date date = new Date(time);
   String dateStr = sdf.format(date);

   Instant instant = Instant.parse(dateStr);
   Instant returnValue = instant.truncatedTo(unit);

   return returnValue.toEpochMilli();
}

after

private static long truncate(long time, ChronoUnit unit) {
   Instant instant = Instant.ofEpochMilli(time);
   Instant returnValue = instant.truncatedTo(unit);
   return returnValue.toEpochMilli();
}