RateLimiter algorithm


(gulyaev-dev) #1

I would like to clarify the correctness of the RateLimiter algorithm.

I want to limit users to 2 requests in 10 seconds.
When the first request occurs, I get the following headers:

HTTP/1.1 200
X-Rate-Limit-Limit: 2
X-Rate-Limit-Remaining: 1
X-Rate-Limit-Reset: 5

On second request (after 1 sec.), I get:

HTTP/1.1 200
X-Rate-Limit-Limit: 2
X-Rate-Limit-Remaining: 0
X-Rate-Limit-Reset: 10

It is OK, but if I keep making a request every second, I get such response all the time:

HTTP/1.1 429 Too Many Requests
X-Rate-Limit-Limit: 2
X-Rate-Limit-Remaining: 0
X-Rate-Limit-Reset: 10

And even after 10 seconds after the last successful request (with 200’th response) I can’t get access. All the time I get the answer above.

Is this the right behavior? If user got 429’th response, he should not make any requests during the X-Rate-Limit-Reset period?
Maybe i did something wrong?
my RateLimitInterface implementation:

public function getRateLimit($request, $action)
{
    return [$this->rate_limit, self::RATE_LIMIT_WINDOW];
}

public function loadAllowance($request, $action)
{
    $prevValues = Yii::$app->cache->get($this->getRLCacheKey());

    return [
        $prevValues['allowance'] ?? $this->rate_limit,
        $prevValues['allowance_updated_at'] ?? time()
    ];
}

public function saveAllowance($request, $action, $allowance, $timestamp)
{
    Yii::$app->cache->set(
        $this->getRLCacheKey(),
        ['allowance' => $allowance, 'allowance_updated_at' => $timestamp],
        self::RATE_LIMIT_WINDOW * 2
    );
}

private function getRLCacheKey()
{
    return self::class . $this->id;
}

(Alexander Makarov) #2

Yes. That’s correct behavior. It’s a “leaking bucket” algorithm with a moving check window.