How to execute tasks in parallel but not more than N tasks per T seconds?

Question

I need to run many tasks in parallel as fast as possible. But if my program runs more than 30 tasks per 1 second, it will be blocked. How to ensure that tasks run no more than 30 per any 1-second interval?

In other words, we must prevent the new task from starting if 30 tasks were completed in the last 1-second interval.

My ugly possible solution:

private async Task Process(List<Task> taskList, int maxIntervalCount, int timeIntervalSeconds)
{
    var timeList = new List<DateTime>();

    var sem = new Semaphore(maxIntervalCount, maxIntervalCount);
    var tasksToRun = taskList.Select(async task =>
    {
        do
        {
            sem.WaitOne();
        }
        while (HasAllowance(timeList, maxIntervalCount, timeIntervalSeconds));

        await task;

        timeList.Add(DateTime.Now);

        sem.Release();
    });

    await Task.WhenAll(tasksToRun);
}

private bool HasAllowance(List<DateTime> timeList, int maxIntervalCount, int timeIntervalSeconds)
{
    return timeList.Count <= maxIntervalCount 
    || DateTime.Now.Subtract(TimeSpan.FromSeconds(timeIntervalSeconds)) > timeList[timeList.Count - maxIntervalCount];
}

Answer 1

User code should never have to control how tasks are scheduled directly. For one thing, it can't - controlling how tasks run is the job of the TaskScheduler. When user code calls .Start(), it simply adds a task to a threadpool queue for execution. await executes already executing tasks.

The TaskScheduler samples show how to create limited concurrency schedulers, but again, there are better, high-level options.

The question's code doesn't throttle the queued tasks anyway, it limits how many of them can be awaited. They are all running already. This is similar to batching the previous asynchronous operation in a pipeline, allowing only a limited number of messages to pass to the next level.

ActionBlock with delay

The easy, out-of-the-box way would be to use an ActionBlock with a limited MaxDegreeOfParallelism, to ensure no more than N concurrent operations can run at the same time. If we know how long each operation takes, we could add a bit of delay to ensure we don't overshoot the throttle limit.

In this case, 7 concurrent workers perform 4 requests/second, for a total of 28 maximum request per second. The BoundedCapacity means that only up to 7 items will be stored in the input buffer before downloader.SendAsync blocks. This way we avoid flooding the ActionBlock if the operations take too long.

var downloader = new ActionBlock<string>(
        async url => {
            await Task.Delay(250);
            var response=await httpClient.GetStringAsync(url);
            //Do something with it.
        },
        new ExecutionDataflowBlockOptions { MaxDegreeOfParallelism = 7, BoundedCapacity=7 }
);

//Start posting to the downloader
foreach(var item in urls)
{
    await downloader.SendAsync(item);
}
downloader.Complete();
await downloader.Completion;

ActionBlock with SemaphoreSlim

Another option would be to combine this with a SemaphoreSlim that gets reset periodically by a timer.

var refreshTimer = new Timer(_=>sm.Release(30));

var downloader = new ActionBlock<string>(
        async url => {
            await semaphore.WaitAsync();
            try 
            {
                var response=await httpClient.GetStringAsync(url);
                //Do something with it.
            }
            finally
            {
                semaphore.Release();
            }
        },
        new ExecutionDataflowBlockOptions { MaxDegreeOfParallelism = 5, BoundedCapacity=5 }
);

//Start the timer right before we start posting 
refreshTimer.Change(1000,1000);
foreach(....)
{

}

Answer 2

This is the snippet:

var tasks = new List<Task>();

foreach(item in listNeedInsert)
{
    var task = TaskToRun(item);
    tasks.Add(task);

    if(tasks.Count == 100)
    {
        await Task.WhenAll(tasks);
        tasks.Clear();
    }
}

// Wait for anything left to finish
await Task.WhenAll(tasks);

Notice that I rather add the task into a List<Task>(); and after all is added, I await all in the same List<Task>();

What you do here:

 var tasks = taskList.Select(async task =>
    {
        do
        {
            sem.WaitOne();
        }
        while (timeList.Count <= maxIntervalCount 
        || DateTime.Now.Subtract(TimeSpan.FromSeconds(timeIntervalSeconds)) > timeList[timeList.Count - maxIntervalCount]);

        await task;

is blocking until the task finishes it's work thus making this call:

Task.WhenAll(tasks).Wait();

completely redundant. Furthermore, this line Task.WhenAll(tasks).Wait(); is performing unnecessary blocking on the WhenAll method.

Answer 3

Is the blocking due to some server/firewall/hardware limit or it is based on observation?

You should try to use BlockingCollection<Task> or similar thread safe collections especially if the job of your tasks are I/O-bound. You can even set the capacity to 30:

var collection = BlockingCollection<Task>(30);

Then you can start 2 async method:

var population = Task.Factory.Start(Populate);
var processing = Task.Factory.Start(Dequeue);
await Task.WhenAll(population, processing);

Task Populate()
{
    foreach (...)
        collection.Add(...);
    collection.CompleteAdding();
}
Task Dequeue
{
    while(!collection.IsComplete)
        await collection.Take();                            //consider using TryTake()
}

If the limit presists due to some true limitation (should be very rare) change Populate() as follows:

var stopper = Stopwatch.StartNew();
for (var i = ....)                                          //instead of foreach
{
    if (i % 30 == 0)
    {
        if (stopper.ElapsedMilliseconds < 1000)
            Task.Delay(1000 - stopper.ElapsedMilliseconds); //note that this race condition should be avoided in your code
        stopper.Restart();
    }
    collection.Add(...);
}
collection.CompleteAdding();

Answer 4

I think that this problem can be solved by a SemaphoreSlim limited to the number of maximum tasks per interval, and also by a Task.Delay that delays the release of the SemaphoreSlim after each task's completion, for an interval equal to the required throttling interval. Below is an implementation based on this idea. The rate limiting can be applied in two ways:

1. With includeAsynchronousDuration: false the rate limit affects how many operations can be started during the specified time span. The duration of each operation is not taken into account.

2. With includeAsynchronousDuration: true the rate limit affects how many operations can be counted as "active" during the specified time span, and is more restrictive (makes the enumeration slower). Instead of counting each operation as a moment in time (when started), it is counted as a time span (between start and completion). An operation is counted as "active" for a specified time span, if and only if its own time span intersects with the specified time span.

/// <summary>
/// Applies an asynchronous transformation for each element of a sequence,
/// limiting the number of transformations that can start or be active during
/// the specified time span.
/// </summary>
public static async Task<TResult[]> ForEachAsync<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, Task<TResult>> action,
    int maxActionsPerTimeUnit,
    TimeSpan timeUnit,
    bool includeAsynchronousDuration = false,
    bool onErrorContinue = false, /* Affects only asynchronous errors */
    bool executeOnCapturedContext = false)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (action == null) throw new ArgumentNullException(nameof(action));
    if (maxActionsPerTimeUnit < 1)
        throw new ArgumentOutOfRangeException(nameof(maxActionsPerTimeUnit));
    if (timeUnit < TimeSpan.Zero || timeUnit.TotalMilliseconds > Int32.MaxValue)
        throw new ArgumentOutOfRangeException(nameof(timeUnit));

    using var semaphore = new SemaphoreSlim(maxActionsPerTimeUnit,
        maxActionsPerTimeUnit);
    using var cts = new CancellationTokenSource();
    var tasks = new List<Task<TResult>>();
    var releaseTasks = new List<Task>();

    try // Watch for exceptions thrown by the source enumerator
    {
        foreach (var item in source)
        {
            try
            {
                await semaphore.WaitAsync(cts.Token)
                    .ConfigureAwait(executeOnCapturedContext);
            }
            catch (OperationCanceledException) { break; }

            // Exceptions thrown synchronously by invoking the action are breaking
            // the loop unconditionally (the onErrorContinue has no effect on them).
            var task = action(item);
            if (!onErrorContinue) task = ObserveFailureAsync(task);
            tasks.Add(task);
            releaseTasks.Add(ScheduleSemaphoreReleaseAsync(task));
        }
    }
    catch (Exception ex) { tasks.Add(Task.FromException<TResult>(ex)); }
    cts.Cancel(); // Cancel all release tasks

    Task<TResult[]> whenAll = Task.WhenAll(tasks);
    try { return await whenAll.ConfigureAwait(false); }
    catch (OperationCanceledException) when (whenAll.IsCanceled) { throw; }
    catch { whenAll.Wait(); throw; } // Propagate AggregateException
    finally { await Task.WhenAll(releaseTasks); }

    async Task<TResult> ObserveFailureAsync(Task<TResult> task)
    {
        try { return await task.ConfigureAwait(false); }
        catch { cts.Cancel(); throw; }
    }

    async Task ScheduleSemaphoreReleaseAsync(Task<TResult> task)
    {
        if (includeAsynchronousDuration)
            try { await task.ConfigureAwait(false); } catch { } // Ignore exceptions
        // Release only if the Task.Delay completed successfully
        try { await Task.Delay(timeUnit, cts.Token).ConfigureAwait(false); }
        catch (OperationCanceledException) { return; }
        semaphore.Release();
    }
}

Usage example:

int[] results = await ForEachAsync(Enumerable.Range(1, 100), async n =>
{
    await Task.Delay(500); // Simulate some asynchronous I/O-bound operation
    return n;
}, maxActionsPerTimeUnit: 30, timeUnit: TimeSpan.FromSeconds(1.0),
    includeAsynchronousDuration: true);

The reasons for propagating an AggregateException using the catch+Wait technique, are explained here.