8000 calculateTimeForTokens for SlidingWindow · symfony/symfony@d52042a · GitHub
[go: up one dir, main page]
Skip to content

Commit d52042a

Browse files
JeroenyJeroeny
committed
calculateTimeForTokens for SlidingWindow
1 parent fcb754a commit d52042a

File tree

4 files changed

+71
-26
lines changed

4 files changed

+71
-26
lines changed

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

+19-2
Original file line numberDiff line numberDiff line change
@@ -100,9 +100,26 @@ public function getHitCount(): int
100100
return (int) floor($this->hitCountForLastWindow * (1 - $percentOfCurrentTimeFrame) + $this->hitCount);
101101
}
102102

103-
public function getRetryAfter(): \DateTimeImmutable
103+
public function calculateTimeForTokens(int $maxSize, int $tokens): float
104104
{
105-
return \DateTimeImmutable::createFromFormat('U.u', sprintf('%.6F', $this->windowEndAt));
105+
$remaining = $maxSize - $this->getHitCount();
106+
if ($remaining >= $tokens) {
107+
return 0;
108+
}
109+
110+
$time = microtime(true);
111+
$startOfWindow = $this->windowEndAt - $this->intervalInSeconds;
112+
$timePassed = $time - $startOfWindow;
113+
$windowPassed = min($timePassed / $this->intervalInSeconds, 1);
114+
$releasable = max(1, $maxSize - floor($this->hitCountForLastWindow * (1 - $windowPassed))); // 2 * (0.7) =1, 3
115+
$remainingWindow = $this->intervalInSeconds - $timePassed;
116+
$needed = $tokens - $remaining;
117+
118+
if ($releasable >= $needed) {
119+
return $needed * ($remainingWindow / max(1, $releasable));
120+
}
121+
122+
return ($this->windowEndAt - $time) + ($needed - $releasable) * ($this->intervalInSeconds / $maxSize);
106123
}
107124

108125
public function __serialize(): array

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

+34-14
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@
1313

1414
use Symfony\Component\Lock\LockInterface;
1515
use Symfony\Component\Lock\NoLock;
16-
use Symfony\Component\RateLimiter\Exception\ReserveNotSupportedException;
16+
use Symfony\Component\RateLimiter\Exception\MaxWaitDurationExceededException;
1717
use Symfony\Component\RateLimiter\LimiterInterface;
1818
use Symfony\Component\RateLimiter\RateLimit;
1919
use Symfony\Component\RateLimiter\Reservation;
@@ -53,14 +53,10 @@ public function __construct(string $id, int $limit, \DateInterval $interval, Sto
5353

5454
public function reserve(int $tokens = 1, float $maxTime = null): Reservation
5555
{
56-
throw new ReserveNotSupportedException(__CLASS__);
57-
}
56+
if ($tokens > $this->limit) {
57+
throw new \InvalidArgumentException(sprintf('Cannot reserve more tokens (%d) than the size of the rate limiter (%d).', $tokens, $this->limit));
58+
}
5859

59-
/**
60-
* {@inheritdoc}
61-
*/
62-
public function consume(int $tokens = 1): RateLimit
63-
{
6460
$this->lock->acquire(true);
6561

6662
try {
@@ -71,19 +67,43 @@ public function consume(int $tokens = 1): RateLimit
7167
$window = SlidingWindow::createFromPreviousWindow($window, $this->interval);
7268
}
7369

70+
$now = microtime(true);
7471
$hitCount = $window->getHitCount();
7572
$availableTokens = $this->getAvailableTokens($hitCount);
76-
if ($availableTokens < $tokens) {
77-
return new RateLimit($availableTokens, $window->getRetryAfter(), false, $this->limit);
78-
}
73+
if ($availableTokens >= $tokens) {
74+
$window->add($tokens);
75+
76+
$reservation = new Reservation($now, new RateLimit($this->getAvailableTokens($window->getHitCount()), \DateTimeImmutable::createFromFormat('U', floor($now)), true, $this->limit));
77+
} else {
78+
$waitDuration = $window->calculateTimeForTokens($this->limit, max(1, $tokens));
7979

80-
$window->add($tokens);
81-
$this->storage->save($window);
80+
if (null !== $maxTime && $waitDuration > $maxTime) {
81+
// process needs to wait longer than set interval
82+
throw new MaxWaitDurationExceededException(sprintf('The rate limiter wait time ("%d" seconds) is longer than the provided maximum time ("%d" seconds).', $waitDuration, $maxTime), new RateLimit($this->getAvailableTokens($window->getHitCount()), \DateTimeImmutable::createFromFormat('U', floor($now + $waitDuration)), false, $this->limit));
83+
}
8284

83-
return new RateLimit($this->getAvailableTokens($window->getHitCount()), $window->getRetryAfter(), true, $this->limit);
85+
$window->add($tokens);
86+
87+
$reservation = new Reservation($now + $waitDuration, new RateLimit($this->getAvailableTokens($window->getHitCount()), \DateTimeImmutable::createFromFormat('U', floor($now + $waitDuration)), false, $this->limit));
88+
}
89+
90+
if (0 < $tokens) {
91+
$this->storage->save($window);
92+
}
8493
} finally {
8594
$this->lock->release();
8695
}
96+
97+
return $reservation;
98+
}
99+
100+
public function consume(int $tokens = 1): RateLimit
101+
{
102+
try {
103+
return $this->reserve($tokens, 0)->getRateLimit();
104+
} catch (MaxWaitDurationExceededException $e) {
105+
return $e->getRateLimit();
106+
}
87107
}
88108

89109
private function getAvailableTokens(int $hitCount): int

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

+6-4
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,6 @@
1313

1414
use PHPUnit\Framework\TestCase;
1515
use Symfony\Bridge\PhpUnit\ClockMock;
16-
use Symfony\Component\RateLimiter\Exception\ReserveNotSupportedException;
1716
use Symfony\Component\RateLimiter\Policy\SlidingWindowLimiter;
1817
use Symfony\Component\RateLimiter\RateLimit;
1918
use Symfony\Component\RateLimiter\Storage\InMemoryStorage;
@@ -66,14 +65,17 @@ public function testWaitIntervalOnConsumeOverLimit()
6665

6766
$start = microtime(true);
6867
$rateLimit->wait(); // wait 12 seconds
69-
$this->assertEqualsWithDelta($start + 12, microtime(true), 1);
68+
$this->assertEqualsWithDelta($start + (12 / 5), microtime(true), 1);
69+
$this->assertTrue($limiter->consume()->isAccepted());
7070
}
7171

7272
public function testReserve()
7373
{
74-
$this->expectException(ReserveNotSupportedException::class);
74+
$limiter = $this->createLimiter();
75+
$limiter->consume(8);
7576

76-
$this->createLimiter()->reserve();
77+
// 2 over the limit, causing the WaitDuration to become 2/10th of the 12s interval
78+
$this->assertEqualsWithDelta(12 / 5, $limiter->reserve(4)->getWaitDuration(), 1);
7779
}
7880

7981
private function createLimiter(): SlidingWindowLimiter

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

+12-6
Original file line numberDiff line numberDiff line change
@@ -81,12 +81,14 @@ public function testCreateFromPreviousWindowUsesMicrotime()
8181
{
8282
ClockMock::register(SlidingWindow::class);
8383
$window = new SlidingWindow('foo', 8);
84+
$window->add();
8485

8586
usleep(11.6 * 1e6); // wait just under 12s (8+4)
8687
$new = SlidingWindow::createFromPreviousWindow($window, 4);
88+
$new->add();
8789

8890
// should be 400ms left (12 - 11.6)
89-
$this->assertEqualsWithDelta(0.4, $new->getRetryAfter()->format('U.u') - microtime(true), 0.2);
91+
$this->assertEqualsWithDelta(0.4, $new->calculateTimeForTokens(1, 1), 0.1);
9092
}
9193

9294
public function testIsExpiredUsesMicrotime()
@@ -101,18 +103,22 @@ public function testIsExpiredUsesMicrotime()
101103
public function testGetRetryAfterUsesMicrotime()
102104
{
103105
$window = new SlidingWindow('foo', 10);
106+
$window->add();
104107

105108
usleep(9.5 * 1e6);
106109
// should be 500ms left (10 - 9.5)
107-
$this->assertEqualsWithDelta(0.5, $window->getRetryAfter()->format('U.u') - microtime(true), 0.2);
110+
$this->assertEquals(0.5, $window->calculateTimeForTokens(1, 1));
108111
}
109112

110113
public function testCreateAtExactTime()
111114
{
112-
ClockMock::register(SlidingWindow::class);
113-
ClockMock::withClockMock(1234567890.000000);
114115
$window = new SlidingWindow('foo', 10);
115-
$window->getRetryAfter();
116-
$this->assertEquals('1234567900.000000', $window->getRetryAfter()->format('U.u'));
116+
$this->assertEquals(30, $window->calculateTimeForTokens(1, 4));
117+
118+
$window = new SlidingWindow('foo', 10);
119+
$window->add();
120+
$window = SlidingWindow::createFromPreviousWindow($window, 10);
121+
sleep(10);
122+
$this->assertEquals(40, $window->calculateTimeForTokens(1, 4));
117123
}
118124
}

0 commit comments

Comments
 (0)
0