Skip to content

[RateLimiter] TokenBucket policy is not adding tokens if interval between requests is smaller than the interval provided in config #42627

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
AdamKatzDev opened this issue Aug 18, 2021 · 6 comments
Closed

[RateLimiter] TokenBucket policy is not adding tokens if interval between requests is smaller than the interval provided in config #42627

AdamKatzDev opened this issue Aug 18, 2021 · 6 comments
Labels
Bug Keep open RateLimiter Status: Needs Review

Comments

@AdamKatzDev
Copy link
Contributor

Symfony version(s) affected: tested on 5.2, but seems that this is not fixed in any newer verison (5.3, 5.4, 6.0).

Description
TokenBucket policy is not adding tokens if the interval between requests is smaller than the interval provided in config.

How to reproduce
Basic configuration is sufficient. Storage type doesn't matter. It does not matter if locks are configured or not.

Limit: 1200, Interval: 1 minute, Amount: 1200
If the interval between requests is less than 1 minute then the bucket is never getting replenished. You will get throttled eventually.

Limit: 1200, Interval: 1 seconds, Amount: 20
If the interval between requests is less than 1 second then the bucket won't get replenished.
If you make the requests a bit slower then you will see that the bucket is getting new tokens.

Possible Solution
No suggestions so far but I've tracked the cause of this.
My theory is that after every successful consume request the policy writes it's execution timestamp to storage:

symfony/src/Symfony/Component/RateLimiter/Policy/TokenBucketLimiter.php

Lines 70 to 78 in 0cb1b5d

$now = microtime(true);
$availableTokens = $bucket->getAvailableTokens($now);
if ($availableTokens >= $tokens) {
// tokens are now available, update bucket
$bucket->setTokens($availableTokens - $tokens);
$bucket->setTimer($now);
$reservation = new Reservation($now, new RateLimit($bucket->getAvailableTokens($now), \DateTimeImmutable::createFromFormat('U', floor($now)), true, $this->maxBurst));
} else {

The next request uses the saved timestamp and current timestamp to add new tokens to the bucket:

symfony/src/Symfony/Component/RateLimiter/Policy/TokenBucket.php

Lines 68 to 73 in 0cb1b5d

public function getAvailableTokens(float $now): int
{
$elapsed = $now - $this->timer;
return min($this->burstSize, $this->tokens + $this->rate->calculateNewTokensDuringInterval($elapsed));
}

symfony/src/Symfony/Component/RateLimiter/Policy/Rate.php

Lines 82 to 92 in 0cb1b5d

/**
* Calculates the number of new free tokens during $duration.
*
* @param float $duration interval in seconds
*/
public function calculateNewTokensDuringInterval(float $duration): int
{
$cycles = floor($duration / TimeUtil::dateIntervalToSeconds($this->refillTime));
return $cycles * $this->refillAmount;
}

The $cycles variable will be 0 if $duration is less than $this->refillTime. If a user sets $this->refillTime in hours or days then the algorithm is not usable at all. If $this->refillTime is a few seconds then it can be somewhat usable in some conditions.

Additional context
In the end we've moved to sliding window policy (the burst limit was the same as fill rate anyway) and it looks like this.
User that is limited to 120 requests per minute (exceeds usage, gets throttled frequently):
image
image

User that is limited to 1200 requests per minute (shouldn't be throttled at all):
image
image
@relo-san
Copy link
Contributor

Any news here?
I confirm the existence of this bug. I can prepare PR with fix.

@fabpot
Copy link
Member

fabpot commented Dec 22, 2021

@relo-san If you can prepare a PR, that would be great. Thank you.

@relo-san relo-san mentioned this issue Dec 22, 2021
Merged
@carsonbot
Copy link

Hey, thanks for your report!
There has not been a lot of activity here for a while. Is this bug still relevant? Have you managed to find a workaround?

@carsonbot
Copy link

Hello? This issue is about to be closed if nobody replies.

@fabpot fabpot added Keep open and removed Stalled labels Aug 14, 2022
@TCM-dev
Copy link

TCM-dev commented Oct 6, 2023

@AdamKatzDev I'm sorry to ask this on an issue but I couldn't figure out another way to contact you.
Your screens shows a graph of your rate limit usage, what tool do you use for that ? Or is that an internal tool ?

@AdamKatzDev
Copy link
Contributor Author

@TCM-dev the tool is Datadog.

@fabpot fabpot closed this as completed Oct 10, 2023
fabpot added a commit that referenced this issue Oct 10, 2023
@fabpot
bug #44766 [RateLimiter] TokenBucket policy fix for adding tokens wit…
adef494 
…h a predefined frequency (relo-san)

This PR was squashed before being merged into the 5.4 branch.

Discussion
----------

[RateLimiter] TokenBucket policy fix for adding tokens with a predefined frequency

| Q             | A
| ------------- | ---
| Branch?       | 5.4
| Bug fix?      | yes
| New feature?  | no
| Deprecations? | no
| Tickets       | Fix #42627
| License       | MIT
| Doc PR        | symfony/symfony-docs#... <!-- required for new features -->

Fixes bug, explained in issue #42627: when interval between requests smaller than rate interval, new tokens can not be added to bucket, because each request updates timer, and therefore rate interval never be reached.
I replace this with approach where timer updates to time, when should have been last updated, and only when rate interval reached.
I added test case for test adding tokens.
As far as I see, there is no BC and no deprecations.
There is method calculateNextTokenAvailability() on Symfony\Component\RateLimiter\Policy\Rate. It does not work correctly (does not match the name and the description), but as far as I can see, it is not used anywhere, so I left it unchanged. The Rate class simply cannot return this data, because it does not have a timer and does not know when the previous addition was made and, accordingly, what to calculate the next from.

Commits
-------

7c8b6ed [RateLimiter] TokenBucket policy fix for adding tokens with a predefined frequency
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Bug Keep open RateLimiter Status: Needs Review
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@fabpot @relo-san @carsonbot @TCM-dev @AdamKatzDev