.NET Throttle algorithm

Question

i would like to implement a good throttle algorithm by in .net (C# or VB) but i cannot figure out how could i do that.

The case is my asp.net website should post requests to another website to fetch results. At maximum 300 requests per minute should be sent.

If the requests exceed the 300 limit the other party Api returns nothing (Which is something i would not like to use as a check in my code).

P.S. I have seen solutions in other languages than .net but i am a newbie and please be kind and keep your answers as simple as 123.

Thank you

Answer 1

Here's an async and sync implementation of a throttle that can limit the number of calls to a method per duration of time. It's based on a simple comparison of the current time to DateTimeOffset and Task.Delay/Thread.Sleep. It should work fine for many implementations that don't need a high degree of time resolution, and should be called BEFORE the methods that you want to throttle.

This solution allows the user to specify the number of calls that are allowed per duration (with the default being 1 call per time period). This allows your throttle to be as "burstable" as you need at the cost of no control over when the callers can continue, or calls can be as evenly spaced as possible.

Let's say let’s say the target is 300 calls/min: you could have a regular throttle with a duration of 200ms that will evenly spread out every call with at least a minimum of 200ms in between, or you could create a throttle that will allow 5 calls every second with no regard to their spacing (first 5 calls win – might be all at once!). Both will keep the rate limit under 300calls/min, but the former is on the extreme end of evenly separated and the latter is more “bursty”. Having things evenly spread out is nice when processing items in a loop, but may not be so good for things running in parallel (like web requests) where the call times are unpredictable and unnecessary delays might actually slow down throughput. Again, your use case and testing will have to be your guide on which is best.

This class is thread-safe and you'll need to keep a reference to an instance of it somewhere that is accessible to the object instances that need to share it. For an ASP.NET web application that would be a field on the application instance, could be a static field on a web page/controller, injected from the DI container of your choice as a singleton, or any other way you could access the shared instance in your particular scenario.

EDIT: Updated to ensure the delay is never longer than the duration.

    public class Throttle
    {
        /// <summary>
        /// How maximum time to delay access.
        /// </summary>
        private readonly TimeSpan _duration;

        /// <summary>
        /// The next time to run.
        /// </summary>
        private DateTimeOffset _next = DateTimeOffset.MinValue;

        /// <summary>
        /// Synchronize access to the throttle gate.
        /// </summary>
        private readonly SemaphoreSlim _mutex = new SemaphoreSlim(1, 1);

        /// <summary>
        /// Number of allowed callers per time window.
        /// </summary>
        private readonly int _numAllowed = 1;

        /// <summary>
        /// The number of calls in the current time window.
        /// </summary>
        private int _count;

        /// <summary>
        /// The amount of time per window.
        /// </summary>
        public TimeSpan Duration => _duration;

        /// <summary>
        /// The number of calls per time period.
        /// </summary>
        public int Size => _numAllowed;

        /// <summary>
        /// Crates a Throttle that will allow one caller per duration.
        /// </summary>
        /// <param name="duration">The amount of time that must pass between calls.</param>
        public Throttle(TimeSpan duration)
        {
            if (duration.Ticks <= 0)
                throw new ArgumentOutOfRangeException(nameof(duration));

            _duration = duration;
        }

        /// <summary>
        /// Creates a Throttle that will allow the given number of callers per time period.
        /// </summary>
        /// <param name="num">The number of calls to allow per time period.</param>
        /// <param name="per">The duration of the time period.</param>
        public Throttle(int num, TimeSpan per)
        {
            if (num <= 0 || per.Ticks <= 0)
                throw new ArgumentOutOfRangeException();

            _numAllowed = num;
            _duration = per;
        }

        /// <summary>
        /// Returns a task that will complete when the caller may continue.
        /// </summary>
        /// <remarks>This method can be used to synchronize access to a resource at regular intervals
        /// with no more frequency than specified by the duration,
        /// and should be called BEFORE accessing the resource.</remarks>
        /// <param name="cancellationToken">A cancellation token that may be used to abort the stop operation.</param>
        /// <returns>The number of actors that have been allowed within the current time window.</returns>
        public async Task<int> WaitAsync(CancellationToken cancellationToken = default(CancellationToken))
        {
            await _mutex.WaitAsync(cancellationToken)
                .ConfigureAwait(false);

            try
            {

                var delay = _next - DateTimeOffset.UtcNow;

                // ensure delay is never longer than the duration
                if (delay > _duration)
                    delay = _duration;
                
                // continue immediately based on count
                if (_count < _numAllowed) 
                {
                    _count++;

                    if (delay.Ticks <= 0) // past time window, reset
                    {
                        _next = DateTimeOffset.UtcNow.Add(_duration);
                        _count = 1;
                    }

                    return _count;
                }
                
                // over the allowed count within the window
                if (delay.Ticks > 0)
                {
                    // delay until the next window
                    await Task.Delay(delay, cancellationToken)
                        .ConfigureAwait(false);
                }

                _next = DateTimeOffset.UtcNow.Add(_duration);
                _count = 1;

                return _count;
            }
            finally
            {
                _mutex.Release();
            }
        }

        /// <summary>
        /// Returns a task that will complete when the caller may continue.
        /// </summary>
        /// <remarks>This method can be used to synchronize access to a resource at regular intervals
        /// with no more frequency than specified by the duration,
        /// and should be called BEFORE accessing the resource.</remarks>
        /// <param name="cancellationToken">A cancellation token that may be used to abort the stop operation.</param>
        /// <returns>The number of actors that have been allowed within the current time window.</returns>
        public int Wait(CancellationToken cancellationToken = default(CancellationToken))
        {
            _mutex.Wait(cancellationToken);

            try
            {

                var delay = _next - DateTimeOffset.UtcNow;

                // ensure delay is never larger than the duration.
                if (delay > _duration)
                    delay = _duration;
                
                // continue immediately based on count
                if (_count < _numAllowed) 
                {
                    _count++;

                    if (delay.Ticks <= 0) // past time window, reset
                    {
                        _next = DateTimeOffset.UtcNow.Add(_duration);
                        _count = 1;
                    }

                    return _count;
                }
                
                // over the allowed count within the window
                if (delay.Ticks > 0)
                {
                    // delay until the next window
                    Thread.Sleep(delay);
                }

                _next = DateTimeOffset.UtcNow.Add(_duration);
                _count = 1;

                return _count;
            }
            finally
            {
                _mutex.Release();
            }
        }
    }

This sample shows how the throttle can be used synchronously in a loop, as well as how cancellation behaves. If you think of it like people getting in line for a ride, if the cancellation token is signaled it's as if the person steps out of line and the other people move forward.

 var t = new Throttle(5, per: TimeSpan.FromSeconds(1));
 var c = new CancellationTokenSource(TimeSpan.FromSeconds(22));
 foreach(var i in Enumerable.Range(1,300)) {
     var ct = i > 250
         ? default(CancellationToken)
         : c.Token;
     try
     {
         var n = await t.WaitAsync(ct).ConfigureAwait(false);
         WriteLine($"{i}: [{n}] {DateTime.Now}");
     }
     catch (OperationCanceledException)
     {
         WriteLine($"{i}: Operation Canceled");
     }
 }

Answer 2

The simplest approach is just to time how long it is between packets and not allow them to be sent at a rate of more than one every 0.2 seconds. That is, record the time when you are called and when you are next called, check that at least 200ms has elasped, or return nothing.

This approach will work, but it will only work for smooth packet flows - if you expect bursts of activity then you may want to allow 5 messages in any 200ms period as long as the average over 1 minute is no more than 300 calls. In this case, you could use an array of values to store the "timestamps" of the last 300 packets, and then each time yoiu receive a call you can look back to "300 calls ago" to check that at least 1 minute has elapsed.

For both of these schemes, the time values returned by Environment.TickCount would be adequate for your needs (spans of not less than 200 milliseconds), as it's accurate to about 15 ms.

Answer 3

You could have a simple application (or session) class and check that for hits. This is something extremely rough just to give you the idea:

public class APIHits {
    public int hits { get; private set; }
    private DateTime minute = DateTime.Now();

    public bool AddHit()
    {
        if (hits < 300) {
            hits++;
            return true;
        }
        else
        {
            if (DateTime.Now() > minute.AddSeconds(60)) 
            {
                //60 seconds later
                minute = DateTime.Now();
                hits = 1;
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}