After yesterday's entry where I discovered it , I went and implemented Tony Finch's exponential rate limiting for HTTP request rate limiting in DWiki , the engine underlying this blog , replacing the more brute force and limited version I had initially implemented. I chose exponential rate limiting over GCRA or leaky buckets because I found it much easier to understand how to set the limits (partly because I'm somewhat familiar with the whole thing from Exim). Exponential rate limiting needed me to pick a period of time and a number of (theoretical) requests that can be made in that time interval, which was easy enough; GCRA 'rate' and 'burst' numbers were less clear to me. However, exponential rate limiting has some slightly surprising things that I want to remember.

(Exponential ratelimits don't have a 'burst' rate as such but you can sort of achieve this by your choice of time intervals .)

In my original simple rate limiting, any rate limit record that had a time outside of my interval was irrelevant and could be dropped in order to reduce space usage (my current approach uses basically the same hack as my syndication feed ratelimits , so I definitely don't want to let its space use grow without bound). This is no longer necessarily true in exponential rate limiting, depending on how big of a rate the record (the source) had built up before it took a break. This old rate 'decays' at a rate I will helpfully put in a table for my own use:

(This is, eg, 'exp(-1)' for we only last saw the source 'interval' time ago.)

Where this becomes especially relevant is if you opt for 'strict' rate limiting instead of 'leaky', where every time the source makes a request you increase its recorded rate even if you reject the request for being rate limited. A high-speed source that insists on hammering you for a while can build up a very large current rate under a strict rate limit policy, and that means its old past behavior can affect it (ie, possibly cause it to be rate limited) well beyond your nominal rate limit interval. Especially with 'strict' rate limiting, you could opt to cap the maximum age a valid record could have and drop everything that you last saw over, say, 3x your interval ago; this would be generous to very high rate old sources, but not too generous (since their old rate would be reduced to 0.05 or less of what it was even if you counted it).

As far as I can see, the behavior with leaky rate limiting and a cost of 1 (for the simple case of all HTTP requests having the same cost) is that if the client keeps pounding away at you, one of its requests will get through on a semi-regular basis. The client will make a successful request, the request will push its rate just over your limit, it will get rate limited some number of times, then enough time will have passed since its last successful request that its new request will be just under the rate limit and succeed. In some environments, this is fine and desired. However, my current goal is to firmly cut off clients that are making requests too fast, so I don't want this; instead, I implemented the 'strict' behavior so you don't get through at all until your request rate and the interval since your last request drops low enough.

Mathematically, a client that makes requests with little or no gap between them (to the precision of your timestamps) can wind up increasing its rate by slightly over its 'cost' per request. If I'm understanding the math correctly, how much over the cost is capped by Tony Finch's ' max(interval, 1.0e-10) ' step, with 1.0e-10 being a small but non-zero number that you can move up or down depending on, eg, your language and its floating point precision. Having looked at it, in Python the resulting factor with 1.0e-10 is '1.000000082740371', so you and I probably don't need to worry about this. If the client doesn't make requests quite that fast, its rate will go up each time by slightly less than the 'cost' you've assigned. In Python, a client that makes a request every millisecond has a factor for this of '0.9995001666249781' of the cost; slower request rates make this factor smaller.

This is probably mostly relevant if you're dumping or reporting the calculated rates (for example, when a client hits the rate limit) and get puzzled by the odd numbers that may be getting reported.