How can I count the number of requests in the last second, minute and hour?

Question

I have a web server which supports only one very simple API- count the number of requests received in the last hour, minute and second. This server is very popular in the world and received thousands of requests per second.

Aim it to find how to return accurately these 3 values to every request?

Requests are coming all the time, so the window of one hour, one minute and one second is different per request. How to manage a different window per request so that the counts are correct per request?

Answer 1

If 100% accuracy is required:

Have a linked-list of all requests and 3 counts - for the last hour, the last minute and the last second.

You will have 2 pointers into the linked-list - for a minute ago and for a second ago.

An hour ago will be at the end of the list. Whenever the time of the last request is more than an hour before the current time, remove it from the list and decrement the hour count.

The minute and second pointers will point to the first request that occurred after a minute and a second ago respectively. Whenever the time of the request is more than a minute / second before the current time, shift up the pointer and decrement the minute / second count.

When a new request comes in, add it to all 3 counts and add it to the front of the linked-list.

Requests for the counts would simply involve returning the counts.

All of the above operations are amortised constant time.

If less than 100% accuracy is acceptable:

The space-complexity for the above could be a bit much, depending on how many requests per second you would typically get; you can reduce this by sacrificing slightly on accuracy as follows:

Have a linked-list as above, but only for the last second. Also have the 3 counts.

Then have a circular array of 60 elements indicating the counts of each of the last 60 seconds. Whenever a second passes, subtract the last (oldest) element of the array from the minute count and add the last second count to the array.

Have a similar circular array for the last 60 minutes.

Loss of accuracy: The minute count can be off by all the requests in a second and the hour count can be off by all the requests in a minute.

Obviously this won't really make sense if you only have one request per second or less. In this case you can keep the last minute in the linked-list and just have a circular array for the last 60 minutes.

There are also other variations on this - the accuracy to space used ratio can be adjusted as required.

A timer to remove old elements:

If you remove old elements only when new elements come in, it will be amortised constant time (some operations might take longer, but it will average out to constant time).

If you want true constant time, you can additionally have a timer running which removes old elements, and each invocation of this (and of course insertions and checking the counts) will only take constant time, since you're removing at most a number of elements inserted in the constant time since the last timer tick.

Answer 2

To do this for time window of T seconds, have a queue data structure where you queue the timestamps of individual requests as they arrive. When you want to read the number of requests arrived during the most recent window of T seconds, first drop from the "old" end of the queue those timestamps that are older than T seconds, then read the size of the queue. You should also drop elements whenever you add a new request to the queue to keep its size bounded (assuming bounded rate for incoming requests).

This solution works up to arbitrary precision, e.g. millisecond accuracy. If you are content with returning approximate answers, you can e.g. for time window of T = 3600 (an hour), consolidate requests coming within same second into a single queue element, making queue size bounded by 3600. I think that would be more than fine, but theoretically loses accuracy. For T = 1, you can do consolidation on millisecond level if you want.

In pseudocode:

queue Q  proc requestReceived()   Q.insertAtFront(now())   collectGarbage()  proc collectGarbage()   limit = now() - T   while (! Q.empty() && Q.lastElement() < limit)     Q.popLast()  proc count()   collectGarbage()   return Q.size()