[RateLimiter] fix incorrect retryAfter of FixedWindow

RobertMe · RobertMe · commit c612584e80c5 · 2023-01-23T08:42:09.000+01:00
A FixedWindow always ends `intervalInSeconds` after the start time
(`timer`). So when calculating the time to consume some tokens the
tokens will always be available at `timer + intervalInSeconds`. But
currently this is reported incorrectly as `calculateTimeForTokens()`
calculates the time based on the desired amount of tokens (and cycles)
while it doesn't take into account `maxSize` amount of tokens become
available at the windows end.

Furthermore calculating the amount of needed cycles is incorrect. This
as all tokens become available at once (at the windows end) and you
can't consume more tokens than `maxSize` (which is validated at the
start of `FixedWindowLimiter::reserve`, in case of `tokens &gt; limit` it
throws).
diff --git a/src/Symfony/Component/RateLimiter/Policy/FixedWindowLimiter.php b/src/Symfony/Component/RateLimiter/Policy/FixedWindowLimiter.php
@@ -68,7 +68,7 @@ public function reserve(int $tokens = 1, float $maxTime = null): Reservation
 
                 $reservation = new Reservation($now, new RateLimit($window->getAvailableTokens($now), \DateTimeImmutable::createFromFormat('U', floor($now)), true, $this->limit));
             } else {
-                $waitDuration = $window->calculateTimeForTokens($tokens);
+                $waitDuration = $window->calculateTimeForTokens($tokens, $now);
 
                 if (null !== $maxTime && $waitDuration > $maxTime) {
                     // process needs to wait longer than set interval
diff --git a/src/Symfony/Component/RateLimiter/Policy/Window.php b/src/Symfony/Component/RateLimiter/Policy/Window.php
@@ -75,15 +75,13 @@ public function getAvailableTokens(float $now)
         return $this->maxSize - $this->hitCount;
     }
 
-    public function calculateTimeForTokens(int $tokens): int
+    public function calculateTimeForTokens(int $tokens, float $now): int
     {
         if (($this->maxSize - $this->hitCount) >= $tokens) {
             return 0;
         }
 
-        $cyclesRequired = ceil($tokens / $this->maxSize);
-
-        return $cyclesRequired * $this->intervalInSeconds;
+        return ceil($this->timer + $this->intervalInSeconds - $now);
     }
 
     public function __serialize(): array
diff --git a/src/Symfony/Component/RateLimiter/Tests/Policy/FixedWindowLimiterTest.php b/src/Symfony/Component/RateLimiter/Tests/Policy/FixedWindowLimiterTest.php
@@ -37,6 +37,7 @@ protected function setUp(): void
 
     public function testConsume()
     {
+        $now = time();
         $limiter = $this->createLimiter();
 
         // fill 9 tokens in 45 seconds
@@ -51,6 +52,9 @@ public function testConsume()
         $rateLimit = $limiter->consume();
         $this->assertFalse($rateLimit->isAccepted());
         $this->assertSame(10, $rateLimit->getLimit());
+        // Window ends after 1 minute
+        $retryAfter = \DateTimeImmutable::createFromFormat('U', $now + 60);
+        $this->assertEquals($retryAfter, $rateLimit->getRetryAfter());
     }
 
     /**

Original file line number	Diff line number	Diff line change
`@@ -75,15 +75,13 @@ public function getAvailableTokens(float $now)`
`75`	`75`	`return $this->maxSize - $this->hitCount;`
`76`	`76`	`}`
`77`	`77`
`78`		`- public function calculateTimeForTokens(int $tokens): int`
	`78`	`+ public function calculateTimeForTokens(int $tokens, float $now): int`
`79`	`79`	`{`
`80`	`80`	`if (($this->maxSize - $this->hitCount) >= $tokens) {`
`81`	`81`	`return 0;`
`82`	`82`	`}`
`83`	`83`
`84`		`- $cyclesRequired = ceil($tokens / $this->maxSize);`
`85`		`-`
`86`		`- return $cyclesRequired * $this->intervalInSeconds;`
	`84`	`+ return ceil($this->timer + $this->intervalInSeconds - $now);`
`87`	`85`	`}`
`88`	`86`
`89`	`87`	`public function __serialize(): array`
Original file line number	Diff line number	Diff line change
`@@ -37,6 +37,7 @@ protected function setUp(): void`
`37`	`37`
`38`	`38`	`public function testConsume()`
`39`	`39`	`{`
	`40`	`+ $now = time();`
`40`	`41`	`$limiter = $this->createLimiter();`
`41`	`42`
`42`	`43`	`// fill 9 tokens in 45 seconds`
`@@ -51,6 +52,9 @@ public function testConsume()`
`51`	`52`	`$rateLimit = $limiter->consume();`
`52`	`53`	`$this->assertFalse($rateLimit->isAccepted());`
`53`	`54`	`$this->assertSame(10, $rateLimit->getLimit());`
	`55`	`+ // Window ends after 1 minute`
	`56`	`+ $retryAfter = \DateTimeImmutable::createFromFormat('U', $now + 60);`
	`57`	`+ $this->assertEquals($retryAfter, $rateLimit->getRetryAfter());`
`54`	`58`	`}`
`55`	`59`
`56`	`60`	`/**`