Hit counter for the last five minutes

Record hits (or events) as they arrive with a timestamp, and answer how many happened in the last five minutes (more generally, the last W seconds) at any moment. Discuss which structure to use and how old entries are dropped. Then improve memory: you do not need to keep every hit; bucket them by second in a fixed ring of counters.

Follow-up reported: many threads record and query at the same time, so make the counter thread-safe and say how you would keep the lock from limiting throughput.