In theory I have a formal education as a programmer (although it was a long time ago). In practice my knowledge from it isn't comprehensive, and every so often I run into an area where I know there's relevant knowledge and algorithms but I don't know what they are and I'm not sure how to find them. Today's area is scalable rate-limiting with low storage requirements .

Suppose, not hypothetically, that you want to ratelimit a collection of unpredictable sources and not use all that much storage per source. One extremely simple and obvious approach is to store, for each source, a start time and a count. Every time the source makes a request, you check to see if the start time is within your rate limit interval; if it is, you increase the count (or ratelimit the source), and if it isn't, you reset the start time to now and the count to 1.

(Every so often you can clean out entries with start times before your interval.)

The disadvantage of this simple approach is that it completely forgets about the past history of each source periodically. If your rate limit intervals are 20 minutes, a prolific source gets to start over from scratch every 20 minutes and run up its count until it gets rate limited again. Typically you want rate limiting not to forget about sources so fast.

I know there are algorithms that maintain decaying averages or moving (rolling) averages. The Unix load average is maintained this way, as is Exim ratelimiting . The Unix load average has the advantage that it's updated on a regular basis, which makes the calculation relatively simple . Exim has to deal with erratic updates that are unpredictable intervals from the previous update, and the comment in the source is a bit opaque to me . I could probably duplicate the formula in my code but I'd have to do a bunch of work to convince myself the result was correct.

(And now I've found Tony Finch's exponential rate limiting ( via ), which I'm going to have to read carefully, along with the previous GCRA: leaky buckets without the buckets .)

Given that rate limiting is such a common thing these days, I suspect that there are a number of algorithms for this with various different choices about how the limits work. Ideally, it would be possible to readily find writeups of them with internet searches, but of course as you know internet search is fairly broken these days.

(For example you can find a lot of people giving high level overviews of rate limiting without discussing how to actually implement it.)

Now that I've found Tony Finch's work I'm probably going to rework my hacky rate limiting code to do things better, because my brute force approach is using the same space as leaky buckets (as covered in Tony Finch's article ) with inferior results. This shows the usefulness of knowing algorithms instead of just coding away.

(Improving the algorithm in my code will probably make no practical difference, but sometimes programming is its own pleasure.)