marco:

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?

My proposed solution:

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

($min-1) it doesn’t always work since it’s not modulo 60. I know it, but solving that is trivial, so I didn’t bother implementing it. Hope this helps.