December 3rd, 2011

Coalescing CancellationTokens from Timeouts

Stephen Toub - MSFT
Partner Software Engineer

In the .NET Framework 4.5 Developer Preview, you’ll find that CancellationTokenSource now has timeout support built directly into its implementation.  This makes it very easy to create a token that will automatically have cancellation requested after a particular time interval, e.g.

public static CancellationToken FromTimeout(int millisecondsDue)
{
    return new CancellationTokenSource(millisecondsDue).Token;
}

Under the covers here, CancellationTokenSource is creating and configuring a new System.Threading.Timer to call the source’s Cancel method after the particular duration passes.  The CLR team did some great work for .NET 4.5 to significantly improve the performance of Timer over .NET 4, making this approach not only easy but also well-performing.  Of course, there are always scenarios the push the boundaries of performance, and we’ve recently seen some high-throughput cases where folks were creating one such CancellationToken for each of thousands upon thousands of asynchronous calls being made per second.  That’s a lot of Timer and CancellationTokenSource instances.  Even with that, the overhead was reasonable, but we’re constantly looking for ways to decrease costs.

One such solution for the consumer is to coalesce tokens.  Rather than using a unique CancellationToken per request, we can create one CancellationToken for all timeout requests that will expire at approximately the same time (where we get to configure the size of the span that defines “approximately the same time”).  That way, we can pick how much flexibility we’re willing to accept in the timeout (there already needs to be some flexibility anyway given what the OS can guarantee, what other work is on the system consuming cycles, etc.), and trade that off against resource utilization.  Here’s one way this can be implemented, here using a 50 millisecond coalescing span:

public static class CoalescedTokens

{

    private const uint COALESCING_SPAN_MS = 50;

 

    private readonly static
       
ConcurrentDictionary<long, CancellationToken>
s_timeToToken =
       
new ConcurrentDictionary<long, CancellationToken>();

 

    public static CancellationToken FromTimeout(int millisecondsTimeout)

    {

        if (millisecondsTimeout <= 0)

            return new CancellationToken(true);

 

        uint currentTime = (uint)Environment.TickCount;

        long targetTime = millisecondsTimeout + currentTime;

        targetTime = ((targetTime + (COALESCING_SPAN_MS – 1))

            / COALESCING_SPAN_MS) * COALESCING_SPAN_MS;

 

        CancellationToken token;

        if (!s_timeToToken.TryGetValue(targetTime, out token))
        {

            token = new CancellationTokenSource(
                (int)(targetTime – currentTime).Token;

            if (s_timeToToken.TryAdd(targetTime, token))

            {

                token.Register(state => {

                    CancellationToken ignored;

                    s_timeToToken.TryRemove((long)state, out ignored);

                }, targetTime);

            }
        }

        return token;

    }

}

With that, we can now use CoalescedTokens.FromTimeout to get a CancellationToken that will be canceled within approximately 50 milliseconds of the timeout I requested, such that this same token will be handed out to anyone else asking for a timeout that would expire in the same span.  The tokens are all stored in a ConcurrentDictionary, indexed by the time at which the token will have cancellation requested.  We first figure out what coalescing interval the incoming request maps to, and look that up in the dictionary.  If the token exists, we return it.  If it doesn’t, we create a new token that will have cancellation requested at the right time, try to add it to the dictionary, and return it.  If we were successful at adding it to the dictionary, we also register a cancellation callback that will remove it from the dictionary once cancellation is requested, avoiding a potential leak.  Of course, there’s a chance there’s a race where two requests come in concurrently, don’t find an existing token, and each create their own… and that’s fine.  It’s a “benign” race, in that each will just get its own token that will expire at the right time, though only one of them will be published for subsequent requestors to use.

For all but the most intensive of scenarios, if you need a token that will have cancellation requested after some timeout, just do the simple thing of using “new CancellationTokenSource(timeout).Token” and all should be well.  But, if after careful profiling and measurement, you find that this is a bottleneck, hopefully this approach and example can help you to address it… one more bit of code for your bag of tricks.

Author

Stephen Toub - MSFT
Partner Software Engineer

Stephen Toub is a developer on the .NET team at Microsoft.

0 comments

Discussion are closed.