Accuracy of LeakyBucketStrategy

[chrisleavoy]

I've discovered the algorithm implemented in LeakyBucketStrategy is far from accurate. Using limits of 3/10s, 10/1h, and 25/day all seem to function correctly. However anything quicker than 1/s is very inaccurate.

I'm struggling to identify the issue. Can you provide any reference for where this algorithm came from? It appears that there are significant floating point rounding errors when trying to implement faster rates. I suspect the following line is the issue:

https://github.com/beheh/flaps/blob/master/src/Flaps/Throttling/LeakyBucketStrategy.php#L153

$timestamp = $time - ($rate - $unfinishedSeconds);

How to reproduce:

    public function testMake110RequestsAndExpect100Failures()
    {
        $fill = 10;

        $storage = new DoctrineCacheAdapter((new ArrayCache()));
        // same issue with redis:
        //$storage = new PredisStorage(new Client());

        $flapFactory = new Flaps($storage);
        /** @var Flap $flap */
        $flap = $flapFactory->getFlap('limit');
        $flap->pushThrottlingStrategy(new LeakyBucketStrategy($fill, '10s'));
        $flap->setViolationHandler(new PassiveViolationHandler());

        $uuid = uniqid();
        $violations = 0;

        for ($i = 0; $i < $fill; $i++) {
            $ok = $flap->limit($uuid);
            $violations += $ok !== true;
            $this->assertTrue($ok, "flap ok on iteration ${i}");
        }

        for ($i = 0; $i < 100; $i++) {
            $ok = $flap->limit($uuid);
            $violations += $ok !== true;
        }

        // on my hardware, only 10-30 requests trip instead of all 100, which is incredibly inaccurate.
        // curiously, setting $fill to 11 yields a consistent 89 of 100 failures
        $this->assertEquals(100, $violations);
    }
}

[abhijitkane]

@chrisleavoy I updated the isViolator function a bit. Try this -

public function isViolator($identifier) {
    if ($this->storage === null) {
        throw new LogicException('no storage set');
    }

    $toBlock = false;
    $time = microtime(true);
    $timestamp = $time;

    $rate = (float) $this->requestsPerTimeSpan / $this->timeSpan;
    $identifier = 'leaky:'.sha1($rate.$identifier);
    $oldRequestCount = $this->storage->getValue($identifier);
    $newRequestCount = $oldRequestCount;

    if($oldRequestCount == 0) {
        $oldTimestamp = $time;
    }
    else {
        $oldTimestamp = $this->storage->getTimestamp($identifier);
    }  

    $secondsSince = $time - $oldTimestamp;
    $maxToLeak = floor($this->requestsPerTimeSpan * ($secondsSince / $this->timeSpan));
    $newRequestCount = max($newRequestCount - $maxToLeak, 0);

    if($newRequestCount + 1 > $this->requestsPerTimeSpan) {
        $toBlock = true;
    }

    $newRequestCount++;
    $newExpiryIn = $this->timeSpan - $secondsSince;

    $this->storage->setValue($identifier, $newRequestCount);
    $this->storage->setTimestamp($identifier, $timestamp);
    $this->storage->expireIn($identifier, $newExpiryIn);
    
    return $toBlock;
}