Polly rate limiting too early [duplicate]

Question

I'm trying to get my head around Polly rate-limit policy.

public class RateLimiter
{
    private readonly AsyncRateLimitPolicy _throttlingPolicy;
    private readonly Action<string> _rateLimitedAction;

    public RateLimiter(int numberOfExecutions, TimeSpan perTimeSpan, Action<string> rateLimitedAction)
    {       
        _throttlingPolicy = Policy.RateLimitAsync(numberOfExecutions, perTimeSpan);
        _rateLimitedAction = rateLimitedAction;
    }

    public async Task<T> Throttle<T>(Func<Task<T>> func)
    {
        var result = await _throttlingPolicy.ExecuteAndCaptureAsync(func);

        if (result.Outcome == OutcomeType.Failure)
        {
            var retryAfter = (result.FinalException as RateLimitRejectedException)?.RetryAfter ?? TimeSpan.FromSeconds(1);
            _rateLimitedAction($"Rate limited. Should retry in {retryAfter}.");
            return default;
        }

        return result.Result;
    }
}

In my console application, I'm instantiating a RateLimiter with up to 5 calls per 10 seconds.

var rateLimiter = new RateLimiter(5, TimeSpan.FromSeconds(10), err => Console.WriteLine(err));
var rdm = new Random();

while (true)
{
    var result = await rateLimiter.Throttle(() => Task.FromResult(rdm.Next(1, 10)));

    if (result != default) Console.WriteLine($"Result: {result}");

    await Task.Delay(200);
}

I would expect to see 5 results, and be rate limited on the 6th one. But this is what I get

Result: 9
Rate limited. Should retry in 00:00:01.7744615.
Rate limited. Should retry in 00:00:01.5119933.
Rate limited. Should retry in 00:00:01.2313921.
Rate limited. Should retry in 00:00:00.9797322.
Rate limited. Should retry in 00:00:00.7309150.
Rate limited. Should retry in 00:00:00.4812646.
Rate limited. Should retry in 00:00:00.2313643.
Result: 7
Rate limited. Should retry in 00:00:01.7982864.
Rate limited. Should retry in 00:00:01.5327321.
Rate limited. Should retry in 00:00:01.2517093.
Rate limited. Should retry in 00:00:00.9843077.
Rate limited. Should retry in 00:00:00.7203371.
Rate limited. Should retry in 00:00:00.4700262.
Rate limited. Should retry in 00:00:00.2205184.

I've also tried to use ExecuteAsync instead of ExecuteAndCaptureAsync and it didn't change the results.

public async Task<T> Throttle<T>(Func<Task<T>> func)
{
    try
    {
        var result = await _throttlingPolicy.ExecuteAsync(func);

        return result;
    }
    catch (RateLimitRejectedException ex)
    {
        _rateLimitedAction($"Rate limited. Should retry in {ex.RetryAfter}.");
        return default;
    }
}

This doesn't make any sense to me. Is there something I'm missing?

Inez

In. NET 7 there will be a built-in support: devblogs.microsoft.com/dotnet/… – Longdistance

Answer 1

The rate limiter works in a bit different way than you might expect.

Let's suppose I have 500 requests and I want to throttle it to 50 per minute.

Expectation: After the first 50 executions the rate limiter kicks in if they were executed less than a minute.

This intuitive approach does not put into account the equal distribution of the incoming load. This might induce the following observable behaviour:

• Let's suppose the first 50 executions took 30 seconds
• Then you have to wait another 30 seconds to execute the 51st request

---

Polly's rate limiter uses the Leaky bucket algorithm

This works in the following way:

• The bucket has a fix capacity
• The bucket has a leak at the bottom
• Water drops are leaving the bucket on a given frequency
• The bucket can receive new water drops from top
• The bucket can overflow if the incoming frequency is greater than the outgoing

So, technically speaking:

• it is a fixed sized queue
• the dequeue is called periodically
• if the queue is full then the enqueue throws an exception

The most important information from the above description is the following: the leaky bucket algorithm uses a constant rate to empty the bucket.

---

UPDATE 14/11/22

Let me correct myself. Polly's rate limiter is using token bucket not leaky bucket. There are also other algorithms like fixed window counter, sliding window log or sliding window counter. You can read about the alternatives here or inside the System Design Interview Volume 1 book's chapter 4

So, let's talk about the token bucket algorithm:

• The bucket has a fix capacity
• Tokens are put into the bucket in a fixed periodic rate
• If the bucket is full no more token is added to it (overflow)
• Each request tries to consume a single token
  • If there is at least one then the request consumes it and the request is allowed
  • If there isn't at least one token inside the bucket then the request is dropped

(Source)

---

If we scrutinise the implementation then we can see the following things:

• The RateLimiterPolicy calls the RateLimiterEngine's static method
• The RateLimiterEngine calls a method on a IRateLimiter interface
  • There is only one class (at the time of writing) which implements this interface
• The RateLimiterFactory exposes a method to create LockFreeTokenBucketRateLimiter

public static IRateLimiter Create(TimeSpan onePer, int bucketCapacity)
    => new LockFreeTokenBucketRateLimiter(onePer, bucketCapacity);

Please be aware of how the parameters are named (onePer and bucketCapacity)!

If you are interested about the actual implementation then you can find here. (Almost each line is commented)

---

I want to emphasize one more thing. The rate limiter does not perform any retry. If you want to continue the execution after the penalty time is over then you have to do it yourself. Either by writing some custom code or by combining a retry policy with the rate limiter policy.

Longdistance

Answer 2

There is an overload accepting third parameter - maxBurst:

The maximum number of executions that will be permitted in a single burst (for example if none have been executed for a while).

The default value is 1, if you will set it to numberOfExecutions you will see the desired effect for the first execution, though after that it will deteriorate to the similar pattern as you observe (I would guess it is based on how the limiter "frees" the resources and var onePer = TimeSpan.FromTicks(perTimeSpan.Ticks / numberOfExecutions); calculation, but I have not dug too deep, but based on the docs and code it seems that rate limiting is happening with "1 execution per perTimeSpan/numberOfExecutions" rate rather than "numberOfExecutions in any selected perTimeSpan"):

_throttlingPolicy = Policy.RateLimitAsync(numberOfExecutions, perTimeSpan, numberOfExecutions);

Adding periodic wait for several seconds brings back the "bursts" though.

Also see:

• docs
• allow for bursts part of the doc
• issue about rate limiter engine.

Christianachristiane