Leaky bucket algorithm for rate limiting

[tontonsb]

As far as I can tell, the current rate limiting algorithm uses a bucket that is emptied once per period. I.e. on a fresh request a bucket is made that holds infinitely many droplets and it gets emptied (forgotten) after $decaySeconds. A request is denied if bucket has more than $maxAttempts droplets (and actually no additional droplets get deposited).

Could we have the leaky bucket instead — a bucket that holds up to $maxAttempts droplets and leak a droplet every $decaySeconds/$maxAttempts seconds? Overflowing droplets just get dropped/denied.

As far as I know, leaky bucket is the standard algorithm for rate limiting. The bursting capabilities would remain the same and throttling is similar (same on average), but it wouldn't lock you out for all of the period. For example, if one is limited to 3600 requests per hour, but accidentally drops 5000 requests at once, they still get the allowance of one additional request every second instead of getting locked out for an hour.

The general idea of the leaker implementation could be something like this:

// Illuminate/Cache/RateLimiter
public function leak($key, $timeframe = 60, $capacity = 60)
{
    $lastLeak = $this->cache->get($key.':leaked');

    if (!$lastLeak)
    {
        $this->cache->put($key.':leaked', $this->currentTime(), $timeframe);
        return;
    }

    $timeSinceLastLeak = $lastLeak - $this->currentTime();

    $droplets = $this->cache->get($key, 0);
    $leaked = floor($capacity * $timeSinceLastLeak / $timeframe);

    if (!$leaked)
        return;

    $remaining = max(0, $droplets - $leaked);
    $this->cache->put($key, $remaining, $timeframe);

    $newTime = $this->currentTime();
    if ($remaining)
    {
        $leakingTime = $timeframe * $leaked / $capacity;
        $newTime = $lastLeak + $leakingTime;
    }

    $this->cache->put($key.':leaked', $this->currentTime(), $timeframe);
}

There might be some additional pitfalls, but before investigating further and rewriting the other limiter methods I would like to know if this feature would be desired at all.

[williamjulianvicary]

Edit: Scratch that, the behaviour is slightly more sane than first glance.