algorithm - Efficient way to compute number of hits to a server within the last minute, in real time

Question

Say you have a server that constantly gets HTTP requests. Your boss needs some stats, and asks you to compute the number of hits within the last minute at any given time.

What algorithm and data-structure would you use to achieve this?

Answer 1

Use a circular buffer.

Whenever you have to keep some current statistics with a built-in obsolescence, a ring buffer is a good candidate. In your case, you can easily keep count of the requests in the last minute by inserting new packets at the front of the circular buffer and keeping a one-minute-before-now pointer in the buffer, or performing a binary search on request time.