System.Threading.Ratelimiting does not effectively maximize requests for its parameters

Description

I was exploring the recently-announced System.Threading.Ratelimiting APIs, when I noticed some peculiar behavior that I haven't noticed with other rate limiting frameworks.

When rate-limiting a function/request, it stands to reason that the average time taken for a batch of requests should approximate the rate limit.

When I set a rate limit with the intent of permitting one request per second, I notice that the rate is approximately 1.5 seconds per request. If I try to permit one request per half second, I notice that the rate is approximately 0.75 seconds per request.

Reproduction Steps

using System.Threading.RateLimiting;

RateLimiter limiter = new FixedWindowRateLimiter(
  new FixedWindowRateLimiterOptions(permitLimit: 1, queueProcessingOrder: QueueProcessingOrder.OldestFirst, queueLimit: 100, window: TimeSpan.FromSeconds(1), autoReplenishment: true)
);

async Task printLimited(int message) {
  await limiter.WaitAsync(1);

  Console.WriteLine(message);
}

int[] nums = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 };

DateTime start = System.DateTime.Now;

var tasks = nums.Select(x => printLimited(x));
await Task.WhenAll(tasks);

DateTime end = System.DateTime.Now;
TimeSpan delta = end - start;

Console.WriteLine("Time elapsed: " + delta.TotalSeconds.ToString());

Expected behavior

The above should complete in approximately n seconds, where n is the number of elements in nums.

Actual behavior

The above completes in approximately 1.5n seconds, where n is the number of elements in nums.

Regression?

No response

Known Workarounds

No response

Configuration

Dotnet 6.0.200
MacOS Monterey 12.5
ARM64

Other information

No response

Tagging subscribers to this area: @mangod9
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

I was exploring the recently-announced System.Threading.Ratelimiting APIs, when I noticed some peculiar behavior that I haven't noticed with other rate limiting frameworks.

When rate-limiting a function/request, it stands to reason that the average time taken for a batch of requests should approximate the rate limit.

When I set a rate limit with the intent of permitting one request per second, I notice that the rate is approximately 1.5 seconds per request. If I try to permit one request per half second, I notice that the rate is approximately 0.75 seconds per request.

Reproduction Steps

using System.Threading.RateLimiting;

RateLimiter limiter = new FixedWindowRateLimiter(
  new FixedWindowRateLimiterOptions(permitLimit: 1, queueProcessingOrder: QueueProcessingOrder.OldestFirst, queueLimit: 100, window: TimeSpan.FromSeconds(1), autoReplenishment: true)
);

async Task printLimited(int message) {
  await limiter.WaitAsync(1);

  Console.WriteLine(message);
}

int[] nums = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 };

DateTime start = System.DateTime.Now;

var tasks = nums.Select(x => printLimited(x));
await Task.WhenAll(tasks);

DateTime end = System.DateTime.Now;
TimeSpan delta = end - start;

Console.WriteLine("Time elapsed: " + delta.TotalSeconds.ToString());

Expected behavior

The above should complete in approximately n seconds, where n is the number of elements in nums.

Actual behavior

The above completes in approximately 1.5n seconds, where n is the number of elements in nums.

Regression?

No response

Known Workarounds

No response

Configuration

Dotnet 6.0.200
MacOS Monterey 12.5
ARM64

Other information

No response

Author:	Catradora
Assignees:	-
Labels:	area-System.Threading
Milestone:	-

[BrennanConroy]

Looks like this is because of how System.Threading.Timer works. It doesn't wait for the current callback to complete before scheduling the next callback which means that when we grab the current timestamp a small amount of time may have passed, and that small amount of time may show up the next time the timer callback is called and we grab the next timestamp. We then use the previously recorded timestamp and the current timestamp to check if we should replenish, and because of that small amount of time the difference could be lower than expected so we'll skip the current timer callback, which essentially doubles the time for the next refresh to occur. Also, I know Windows has a ~15ms precision which might also come into play here.

One solution to this may be to skip the check when auto replenish is on and trust that the timer loop is scheduling correctly, and that our callback finishes quickly.

A better solution is probably to replenish multiple times if we see that more time than expected has passed. This would mean over the lifetime of the application you would see the expected replenish rate, although it is possible if you zoomed in on specific small windows you may see multiple replenishes occur at once. I think that is ok though.

[viceroypenguin]

A better solution is probably to replenish multiple times if we see that more time than expected has passed. This would mean over the lifetime of the application you would see the expected replenish rate, although it is possible if you zoomed in on specific small windows you may see multiple replenishes occur at once. I think that is ok though.

I found this issue when looking for an explanation for missed window replenishments.

In my opinion, this description of a better solution will not satisfy expected behavior.

Example: I am working with a remote API that limits to 75 calls/min. Using a FixedWindowRateLimiter with permitLimit: 75 and a custom DelegatingHandler I submit all of my api calls at once and allow the limiter to trickle the calls to the server according to the limit.

If multiple replenishments are done to cover the gap (i.e. a missed window happens and the next window does double-replenishment to restore the overall average), then I will exceed my limits with 150 attempted calls according to the remote server, even though averaged out I met the requirements.

I think the PR that you have written, according to the first proposed solution (trusting that the timer is working as expected) will provide more accurate behavior.

[BrennanConroy]

If multiple replenishments are done to cover the gap (i.e. a missed window happens and the next window does double-replenishment to restore the overall average), then I will exceed my limits with 150 attempted calls according to the remote server, even though averaged out I met the requirements.

The proposed "better solution" wouldn't apply to FixedWindow and only partially apply to SlidingWindow because of that. But like you noticed, the PR uses the other method because it seems better in practice.