Count requests received in last second, minute and hour - PrismoSkills

Count requests received in last second, minute and hour - PrismoSkills

Problem: Given an extremely busy server which receives thousands of requests per second.
It is desired to find the number of requests received in the last second, minute and hour.
What algorithm and data-structures can be used to do this as accurately as possible?

Solution : Some of the first solutions that come to mind are:

1. Maintain 3 counters, one each for last hour, second and minute.
   This is quickly rejected because there is no way to remove the count of requests which fall out of the window of last hour, minute and second.
   
   
2. Maintain 3 lists, one each for last hour, second and minute
   This does solve the problem with the above counters, but since the number of requests is huge, a massive synchronization will be required for each thread adding its request to three lists.
   Given thousands of requests per second, synchronization alone will slow down the entire lists' updation process.
   
   

Best approach: A good solution is one which allows concurrent updates and does not eat up too much memory.
With this idea in mind, the following can be a good solution:

1) Create an array AtomicInteger frequencies[1000]; to store the number of requests received per second.

2) This array will store frequencies of requests for the current second i.e. from HH:MM:SS to HH:MM:SS+1 time

3) We will store current second in some variable, say currentSecond

Read full article from Count requests received in last second, minute and hour - PrismoSkills