simple rolling rate-limit algorithm

Ok my last post on rate limiting. You had the right idea with averages. This uses 3 values per id to determine their rate. You can reduce it to a single cache item stored as a serialized array.

public function allow_hit($id, $limit_per_minute) {
  $key = md5($id);
  $thistime = time();

  $count = intval(Cache::get('rate-count', $key));
  $lasttime = intval(Cache::get('rate-last', $key));
  $average = intval(Cache::get('rate-average', $key));

  $diff = $thistime - $lasttime;
  $total = $count * $average;
  $newtotal = $total + $diff;
  $newaverage = $newtotal / ($count + 1);

  Cache::set('rate-count', $key, $count + 1, 60);
  Cache::set('rate-last', $key, $thistime, 60);
  Cache::set('rate-average', $key, $newaverage, 60);
        
  if ($count > $limit_per_minute && $newaverage < $limit_per_minute / 60) {
    return false;
  }

  return true;
}

Posted: 2009-03-12 14:17