Marco.org

This simple hits-per-minute rate-limiter works:

public function allow_hit($id, $limit_per_minute)
{
    $key = md5($id) . idate('i');
    $count = intval(Cache::get('rate-limiter', $key));
    if ($count > $limit_per_minute) return false;
    Cache::set('rate-limiter', $key, $count + 1, /* ttl */ 60);
    return true;
}

…but it’s “dumb” with its definition of “per minute” — it just means “limit for each calendar minute” (using idate('i') as part of the cache key), not “limit for any rolling 60-second period”. That’s not as elegant or correct as I’d like.

But 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 aware that this has a race condition. For its purpose, I accept that. It would have been much more of a PITA to use the atomic Memcache::increment() function because it doesn’t work when the key doesn’t exist — it would be a lot more useful if, on a nonexistent key, it would atomically set it to either 0 or 1.)

Update: Bjorn Stromberg wins!