Simple rate-limiting algorithm?
…. [b]ut I can’t figure out a way to do a rolling 60-second period without storing every hit and its timestamp within the rolling window. Is there a good algorithm for doing that in constant space and time (maybe a trick using averages?), or am I pretty much stuck with the fixed calendar-window method?
I’m thinking that you can get a pretty good rolling window implementation by using a circular array of k counters and one additional global counter. Each array slot will contain a count of the hits in a 60/k second portion of the one-minute window. It won’t give perfect granularity, but you can increase the number of boxes in the array until you get “close enough” for your purposes.
The bookkeeping will be like this: every time a hit comes in, we check the seconds in the current time and increment the number in the corresponding array slot (as well as the global hit counter). It’s a “circular” buffer, so when we reach the end, we wrap back to the beginning, and every 60/k seconds we move on to the next array element, decrement the global hit counter by the number in the array element, and reset the element’s counter to zero.
I should have just written the (pseudo)code from the beginning, but thought it would take me less time to explain it.
3 years ago