Implement rate limiting by cookie ID

Question

I want to develop a simple in-memory web request rate limiting module, I am allowed to have 50 requests from each unique cookie ID every 60 seconds.

I am wondering if the following code is an optimal way of implementing such functionality:

class RateLimiter {

    private static final int MAX_REQUESTS = 50;

    private Map<String, List<Long>> cookieMap = new HashMap<>();

    private boolean isRateLimited(String cookieId) {
      long time = System.currentTimeMillis();
      long oldestTime = time - 60000;
      List<Long> timestamps = cookieMap.getOrDefault(cookieId, new LinkedList<>());
      timestamps.add(0, time);
      int count = 0;
      int tooOldIndex = -1;
      for (int i = 0; i < timestamps.size(); i++) {
          if (timestamps.get(i) >= oldestTime) {
              count++;
          } else {
              tooOldIndex = i;
              break;
          }
      }
      List<Long> newTimestamps = new LinkedList<>();
      // clean up timestamps older than the 60 second window
      for (int i = 0; i < tooOldIndex; i++) {
          newTimestamps.add(timestamps.get(i));
      }
      cookieMap.put(cookieId, newTimestamps);
      if (count >= MAX_REQUESTS) {
         return false;
      } else {
         return true;
      }
  }
}

Answer 1

Accessing elements of a linked list with .get(i) is expensive, because it's an \$O(N)\$ operation compared to \$O(1)\$ of array backed structures. You should avoid doing this, and use an enhanced for-each loop instead, for example:

for (Long currentTimeStamp : timestamps) {
    if (currentTimeStamp  >= oldestTime) {
        newTimestamps.add(currentTimeStamp);
    } else {
        break;
    }
}

If you need the element index, you can add a counting variable "manually" (declared before the loop, and increments in the loop body).

Answer 2

  if (count >= MAX_REQUESTS) {
     return false;
  } else {
     return true;
  }

This bit looks like it could be simplified to a simple return statement, by reverting the condition:

return count < MAX_REQUESTS

That said, are you sure you want to return false when count is equal to MAX_REQUESTS? The actual maximum number of requests is MAX_REQUESTS - 1 otherwise...

Answer 3

Conceptually your RateLimiter works incorrectly. You shouldn't put current time into cookieMap if your isRateLimited finally returns false because it's only attempt to request your server for the request execution. You shouldn't count it. You should keep in the map only successfully processed attempts.

Also I would reuse exist Google Guava com.google.common.util.concurrent.RateLimiter implementation.

Answer 4

You are iterating twice over timestamps which isn't necessary at all, because you can just add each item which meets the criteria timestamps.get(i) >= oldestTime to the newTimestamps like so

  List<Long> newTimestamps = new LinkedList<>();
  newTimestamps.add(time);
  for (int i = 0; i < timestamps.size(); i++) {
      Long currentTimeStamp = timestamps.get(i);
      if (currentTimeStamp  >= oldestTime) {
          newTimestamps.add(currentTimeStamp);
      } else {
          break;
      }
  }
  cookieMap.put(cookieId, newTimestamps);

So there is no cleaning up needed anymore. You need neither the count nor the tooOldIndex variable, so I have removed both. You can simply evaluate the return value by checking size of the newTimestamps.

---

After taking a second look at your code I recognized that the method isRateLimited() has side effects which a caller of this method wouldn't expect. If one calls a method like boolean isXXX() he/she wouldn't expect that some state would be changed like the cookieMap in that method.

I would suggest splitting this method into several methods like so (also taking into account the answers of @janos, @Mat'sMug and @ AndriyKryvtsun)

private List<Long> getTimestampRange(String cookieId, Long maxTime) {

    List<Long> timeStampRange = new LinkedList<>();

    List<Long> timestamps = cookieMap.getOrDefault(cookieId, new LinkedList<>());

    for (Long currentTimeStamp : timestamps) {
        if (currentTimeStamp  >= oldestTime) {
            timeStampRange.add(currentTimeStamp);
        } else {
            break;
        }
    }
    return timeStampRange; 
}

private boolean isLimitExceeded(List<Long> timespans) {

    return timspans.size() > REQUESTS;
}

private boolean updateCookiesIfInRange(String cookieId) {
    Long time = System.currentTimeMillis();

    List<Long> timeStampRange = getTimestampRange(cookieId, time - 60000);
    if (isLimitExceeded(timeStampRange)) {
        return false;
    }

    timeStampRange.add(0, time);
    cookieMap.put(cookieId, timeStampRange);
    return true;
}

In this way the responsibilities are clearly separated but what I just recognized is a little bit strange. How in the world should this method be called ? Anything in this class is private !

Answer 5

In addition to the points made in the other excellent answers...

Java 8 way (or the highway)

There's a few Java 8 methods that you can use to do your computations in a more fluent manner. Map.computeIfAbsent() returns you either the current (existing or computed) value associated with the key, so you do not have to put() the new List later:

List<Long> timestamps = cookieMap.computeIfAbsent(cookieId, k -> new ArrayList<>());
// do something with timestamps, which is a reference to the value in the map

You probably do not require the doubly-linked characteristics of a LinkedList.

Then, instead of finding the index where you want to trim away the 'older' timestamps, you can apply a Predicate<Long> using the Collection.removeIf(Predicate<T>) method:

timestamps.removeIf(l -> l >= oldestTime);

There's also a better way to model timestamps than a simple Long, using an Instant. This lets you work with more fluent time-based methods instead of simple arithmetic. For example, you can do something like this:

timestamps.removeIf(instant -> ChronoUnit.MINUTES.between(instant, Instant.now()) >= 1);

Answer 6

I want to add one point missing from all current answers: Thread safety

If your code will be called by multiple threads at the same time you need to use different implementations of your cookieMap and potentially the lists in the map or make your method synchronized.

A simple way would be to wrap the map using Collections.synchronizedMap(…) or to use a ConcurrentHashMap.

If multiple requests with the same cookieId may be processed at the same time and the lists are used as in your question you would need a synchronized list too, as the same list may be available to and modified by multiple threads. You can use Collections.synchronizedList(…) or e.g. a CopyOnWriteArrayList.

Note that you don't need synchronized lists when you use the lists like in the longer example of Heslachers answer as only new lists are modified and put in the map, the lists in the map are never modified.

Note that even if you make your code "thread safe" (I don't like this term, because safety depends on context, IMO) by correctly synchronizing the map you could miss requests (and let more then 50 requests pass) or take not yet completed requests in the consideration (and deny requests while the limit is not yet reached), depending on the implementation.