8000 bug #44766 [RateLimiter] TokenBucket policy fix for adding tokens wit… · symfony/symfony@adef494 · GitHub
[go: up one dir, main page]
Skip to content

Commit adef494

Browse files
fabpotfabpot
committed
bug #44766 [RateLimiter] TokenBucket policy fix for adding tokens with 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
2 parents 7aaa92a + 7c8b6ed commit adef494

File tree

4 files changed

+44
-3
lines changed

4 files changed

+44
-3
lines changed

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -99,6 +99,18 @@ public function calculateNewTokensDuringInterval(float $duration): int
9999
return $cycles * $this->refillAmount;
100100
}
101101

102+
/**
103+
* Calculates total amount in seconds of refill intervals during $duration (for maintain strict refill frequency).
104+
*
105+
* @param float $duration interval in seconds
106+
*/
107+
public function calculateRefillInterval(float $duration): int
108+
{
109+
$cycleTime = TimeUtil::dateIntervalToSeconds($this->refillTime);
110+
111+
return floor($duration / $cycleTime) * $cycleTime;
112+
}
113+
102114
public function __toString(): string
103115
{
104116
return $this->refillTime->format('P%yY%mM%dDT%HH%iM%sS').'-'.$this->refillAmount;

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

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -79,8 +79,13 @@ public function setTokens(int $tokens): void
7979
public function getAvailableTokens(float $now): int
8080
{
8181
$elapsed = max(0, $now - $this->timer);
82+
$newTokens = $this->rate->calculateNewTokensDuringInterval($elapsed);
8283

83-
return min($this->burstSize, $this->tokens + $this->rate->calculateNewTokensDuringInterval($elapsed));
84+
if ($newTokens > 0) {
85+
$this->timer += $this->rate->calculateRefillInterval($elapsed);
86+
}
87+
88+
return min($this->burstSize, $this->tokens + $newTokens);
8489
}
8590

8691
public function getExpirationTime(): int

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

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -70,7 +70,6 @@ public function reserve(int $tokens = 1, float $maxTime = null): Reservation
7070
if ($availableTokens >= $tokens) {
7171
// tokens are now available, update bucket
7272
$bucket->setTokens($availableTokens - $tokens);
73-
$bucket->setTimer($now);
7473

7574
$reservation = new Reservation($now, new RateLimit($bucket->getAvailableTokens($now), \DateTimeImmutable::createFromFormat('U', floor($now)), true, $this->maxBurst));
7675
} else {
@@ -87,7 +86,6 @@ public function reserve(int $tokens = 1, float $maxTime = null): Reservation
8786
// at $now + $waitDuration all tokens will be reserved for this process,
8887
// so no tokens are left for other processes.
8988
$bucket->setTokens($availableTokens - $tokens);
90-
$bucket->setTimer($now);
9189

9290
$reservation = new Reservation($now + $waitDuration, new RateLimit(0, \DateTimeImmutable::createFromFormat('U', floor($now + $waitDuration)), false, $this->maxBurst));
9391
}

‎src/Symfony/Component/RateLimiter/Tests/Policy/TokenBucketLimiterTest.php

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -128,6 +128,32 @@ public function testBucketResilientToTimeShifting()
128128
$this->assertSame(100, $bucket->getAvailableTokens($serverOneClock));
129129
}
130130

131+
public function testBucketRefilledWithStrictFrequency()
132+
{
133+
$limiter = $this->createLimiter(1000, new Rate(\DateInterval::createFromDateString('15 seconds'), 100));
134+
$rateLimit = $limiter->consume(300);
135+
136+
$this->assertTrue($rateLimit->isAccepted());
137+
$this->assertEquals(700, $rateLimit->getRemainingTokens());
138+
139+
$expected = 699;
140+
141+
for ($i = 1; $i <= 20; ++$i) {
142+
$rateLimit = $limiter->consume();
143+
$this->assertTrue($rateLimit->isAccepted());
144+
$this->assertEquals($expected, $rateLimit->getRemainingTokens());
145+
146+
sleep(4);
147+
--$expected;
148+
149+
if (\in_array($i, [4, 8, 12], true)) {
150+
$expected += 100;
151+
} elseif (\in_array($i, [15, 19], true)) {
152+
$expected = 999;
153+
}
154+
}
155+
}
156+
131157
private function createLimiter($initialTokens = 10, Rate $rate = null)
132158
{
133159
return new TokenBucketLimiter('test', $initialTokens, $rate ?? Rate::perSecond(10), $this->storage);

0 commit comments

Comments
 (0)
0