AsyncDictionary - Can you break thread safety?

Question

This class is an Async/Await wrapped Dictionary. Of course it doesn't technically implement IDictionary, but the functionality is basically the same as an IDictionary. It achieves similar functionality to ConcurrentDictionary but with async/await, and is non-blocking.

Note: please pay attention to the challenge. The challenge is to see if thread safety can be broken. There may not be a strong justification for the class's existence, but this is not the question. The question is: does it stand up to testing?

Code Is Here

public class AsyncDictionary<TKey, TValue> : IAsyncDictionary<TKey, TValue>, IDisposable
{
    #region Fields
    private readonly IDictionary<TKey, TValue> _dictionary;
    private readonly SemaphoreSlim _semaphoreSlim = new SemaphoreSlim(1, 1);
    private bool disposedValue = false;
    #endregion

    #region Func
    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> ContainsKeyFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
    {
        return Task.FromResult(dictionary.ContainsKey(keyValuePair.Key));
    });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> ClearFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
   {
       dictionary.Clear();
       return Task.FromResult(true);
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<int>> GetCountFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<int>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary.Count);
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<ICollection<TValue>>> GetValuesFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<ICollection<TValue>>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary.Values);
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<ICollection<TKey>>> GetKeysFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<ICollection<TKey>>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary.Keys);
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> AddFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
   {
       dictionary.Add(keyValuePair);
       return Task.FromResult(true);
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> AddOrReplaceFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
   {
       if (dictionary.ContainsKey(keyValuePair.Key))
       {
           dictionary[keyValuePair.Key] = keyValuePair.Value;
       }
       else
       {
           dictionary.Add(keyValuePair.Key, keyValuePair.Value);
       }

       return Task.FromResult(true);
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> ContainsItemFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary.Contains(keyValuePair));
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> RemoveFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary.Remove(keyValuePair));
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>> RemoveByKeyFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<bool>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary.Remove(keyValuePair.Key));
   });

    private static readonly Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<TValue>> GetValueFunc = new Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<TValue>>((dictionary, keyValuePair) =>
   {
       return Task.FromResult(dictionary[keyValuePair.Key]);
   });
    #endregion

    #region Constructor
    public AsyncDictionary()
    {
        //Note: the constructor overload to allow passing in a different Dictionary type has been removed to disallow unsynchronized access. It can be added if you're careful.
        _dictionary = new Dictionary<TKey, TValue>();
    }

    /// <summary>
    /// This overload is used in cases where a standard Dictionary isn't the right choice. Warning: accessing the Dictionary outside this class will break synchronization
    /// </summary>
    //public AsyncDictionary(IDictionary<TKey, TValue> dictionary)
    //{
    //    _dictionary = dictionary;
    //}
    #endregion

    #region Implementation
    //Only when C# 8 comes!
    //TODO: IEnumerator<KeyValuePair<T1, T2>> GetEnumerator()
    //TODO: IEnumerator IEnumerable.GetEnumerator()

    public Task<ICollection<TKey>> GetKeysAsync()
    {
        return CallSynchronizedAsync(GetKeysFunc, default);
    }

    public Task<ICollection<TValue>> GetValuesAsync()
    {
        return CallSynchronizedAsync(GetValuesFunc, default);
    }

    public Task<int> GetCountAsync()
    {
        return CallSynchronizedAsync(GetCountFunc, default);
    }

    public Task AddAsync(TKey key, TValue value)
    {
        return CallSynchronizedAsync(AddFunc, new KeyValuePair<TKey, TValue>(key, value));
    }

    public Task AddAsync(KeyValuePair<TKey, TValue> item)
    {
        return CallSynchronizedAsync(AddFunc, item);
    }

    public Task AddOrReplaceAsync(TKey key, TValue value)
    {
        return CallSynchronizedAsync(AddOrReplaceFunc, new KeyValuePair<TKey, TValue>(key, value));
    }

    public Task ClearAsync()
    {
        return CallSynchronizedAsync(ClearFunc, default);
    }

    public Task<bool> GetContainsAsync(KeyValuePair<TKey, TValue> item)
    {
        return CallSynchronizedAsync(ContainsItemFunc, item);
    }

    public Task<bool> GetContainsKeyAsync(TKey key)
    {
        return CallSynchronizedAsync(ContainsKeyFunc, new KeyValuePair<TKey, TValue>(key, default));
    }

    public Task<bool> RemoveAsync(TKey key)
    {
        return CallSynchronizedAsync(RemoveByKeyFunc, new KeyValuePair<TKey, TValue>(key, default));
    }

    public Task<bool> RemoveAsync(KeyValuePair<TKey, TValue> item)
    {
        return CallSynchronizedAsync(RemoveFunc, item);
    }

    public Task<TValue> GetValueAsync(TKey key)
    {
        return CallSynchronizedAsync(GetValueFunc, new KeyValuePair<TKey, TValue>(key, default));
    }
    #endregion

    #region Private Methods
    private async Task<TReturn> CallSynchronizedAsync<TReturn>(Func<IDictionary<TKey, TValue>, KeyValuePair<TKey, TValue>, Task<TReturn>> func, KeyValuePair<TKey, TValue> keyValuePair)
    {
        try
        {
            await _semaphoreSlim.WaitAsync();

            return await Task.Run(async () =>
            {
                return await func(_dictionary, keyValuePair);
            });
        }
        finally
        {
            _semaphoreSlim.Release();
        }
    }
    #endregion

    #region IDisposable Support
    protected virtual void Dispose(bool disposing)
    {
        if (!disposedValue)
        {
            if (disposing)
            {
                _semaphoreSlim.Dispose();
            }

            disposedValue = true;
        }
    }

    public void Dispose()
    {
        Dispose(true);
    }
    #endregion
}

I set up some some unit tests here, but I'd like to see if anyone can break the thread safety of this.

Can you add to the unit tests? Can you make the dictionary return the wrong results? Can you cause an exception that shouldn't come up from normal use of this class? Can you detect any other concurrency issues? Can find any other bugs

Note: PRs are more than welcome, and the more unit tests, the better!

Code Is Here

public class AsyncDictionaryTests
{
    #region Fields
    private const int max = 800;
    #endregion

    #region Tests
    [Test]
    public async Task TestAddAndRetrieveKeys()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        await asyncDictionary.AddAsync(key, key.ToString());
        var keys = (await asyncDictionary.GetKeysAsync()).ToList();
        Assert.AreEqual(key, keys[0]);
    }

    [Test]
    public async Task TestAddAndRetrieveValues()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        var value = key.ToString();
        await asyncDictionary.AddAsync(key, value);
        var values = (await asyncDictionary.GetValuesAsync()).ToList();
        Assert.AreEqual(value, values[0].ToString());
    }

    [Test]
    public async Task TestContainsKey()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        await asyncDictionary.AddAsync(key, key.ToString());
        var contains = await asyncDictionary.GetContainsKeyAsync(key);
        Assert.True(contains);
    }


    [Test]
    public async Task TestContains()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        var value = key.ToString();
        var kvp = new KeyValuePair<int, string>(key, value);
        await asyncDictionary.AddAsync(kvp);
        var contains = await asyncDictionary.GetContainsAsync(kvp);
        Assert.True(contains);
    }

    [Test]
    public async Task TestRemoveByKey()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        await asyncDictionary.AddAsync(key, key.ToString());
        var contains = await asyncDictionary.GetContainsKeyAsync(key);
        Assert.True(contains);
        await asyncDictionary.RemoveAsync(key);
        contains = await asyncDictionary.GetContainsKeyAsync(key);
        Assert.False(contains);
    }

    [Test]
    public async Task TestRemove()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        var kvp = new KeyValuePair<int, string>(key, key.ToString());
        await asyncDictionary.AddAsync(kvp);
        var contains = await asyncDictionary.GetContainsKeyAsync(key);
        Assert.True(contains);
        await asyncDictionary.RemoveAsync(kvp);
        contains = await asyncDictionary.GetContainsKeyAsync(key);
        Assert.False(contains);
    }

    [Test]
    public async Task TestGetValue()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        await asyncDictionary.AddAsync(key, key.ToString());
        var value = await asyncDictionary.GetValueAsync(key);
        Assert.AreEqual(key.ToString(), value);
    }

    [Test]
    public async Task TestClear()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();
        const int key = 1;
        var value = key.ToString();
        await asyncDictionary.AddAsync(key, value);
        await asyncDictionary.ClearAsync();
        var values = (await asyncDictionary.GetValuesAsync()).ToList();
        Assert.IsEmpty(values);
    }

    [Test]
    public async Task TestAnotherType()
    {
        var asyncDictionary = new AsyncDictionary<string, Thing>();
        var thing = new Thing { Name="test", Size=100 };
        await asyncDictionary.AddAsync(thing.Name, thing);
        var newthing = await asyncDictionary.GetValueAsync(thing.Name);
        Assert.True(ReferenceEquals(thing, newthing));
    }

    [Test]
    public async Task TestThreadSafety()
    {
        var asyncDictionary = new AsyncDictionary<int, string>();

        var tasks = new List<Task> { AddKeyValuePairsAsync(asyncDictionary), asyncDictionary.ClearAsync(), AddKeyValuePairsAsync(asyncDictionary) };

        await Task.WhenAll(tasks);

        tasks = new List<Task> { AddKeyValuePairsAsync(asyncDictionary), AddKeyValuePairsAsync(asyncDictionary), AddKeyValuePairsAsync(asyncDictionary) };

        await Task.WhenAll(tasks);

        tasks = new List<Task> { DoTestEquality(asyncDictionary), DoTestEquality(asyncDictionary), DoTestEquality(asyncDictionary), DoTestEquality(asyncDictionary), AddKeyValuePairsAsync(asyncDictionary) };

        await Task.WhenAll(tasks);
    }
    #endregion

    #region Helpers
    private static async Task DoTestEquality(AsyncDictionary<int, string> asyncDictionary)
    {
        var tasks = new List<Task>();
        for (var i = 0; i < max; i++)
        {
            tasks.Add(TestEquality(asyncDictionary, i));
        }

        await Task.WhenAll(tasks);
    }

    private static async Task TestEquality(AsyncDictionary<int, string> asyncDictionary, int i)
    {
        var expected = i.ToString();
        var actual = await asyncDictionary.GetValueAsync(i);

        Console.WriteLine($"Test Equality Expected: {expected} Actual: {actual}");

        Assert.AreEqual(expected, actual);
    }

    private static async Task AddKeyValuePairsAsync(AsyncDictionary<int, string> asyncDictionary)
    {
        var tasks = AddSome(asyncDictionary);
        await Task.WhenAll(tasks);
    }

    private static List<Task> AddSome(AsyncDictionary<int, string> asyncDictionary)
    {
        var tasks = new List<Task>();
        for (var i = 0; i < max; i++)
        {
            tasks.Add(AddByNumber(asyncDictionary, i));
        }

        return tasks;
    }

    private static Task AddByNumber(AsyncDictionary<int, string> asyncDictionary, int i)
    {
        return asyncDictionary.AddOrReplaceAsync(i, i.ToString());
    }
    #endregion
}

To see a UWP sample application, please clone the repo and run the sample there.

Notes: this class is designed for: maintainability first, concurrency, and flexibility. It is modeled after IDictionary but embraces the async-await paradigm. It comes after years of frustration in trying to synchronise cache in async-await C# apps while trying to avoid blocking calls.

It is heavily based on SemaphoreSlim with a maximum request concurrency of 1. Experience seems to indicate that this class behaves in a FIFO manner. However, the notes on SemaphoreSlim are a little worrying:

If multiple threads are blocked, there is no guaranteed order, such as FIFO or LIFO, that controls when threads enter the semaphore.

Is this an Achilles heal? The SemaphoreSlim code can be found here.

Can you create a scenario where the FIFO is not honored in a way that breaks the functionality of the class?

Conclusion: the marked answer exploits a mistake in the original code to break thread safety. However, the exercise was informative, as the larger question arose: what would the point of this class be? From my naieve perspective, it's designed in such a way that beginner programmers could use it, and likely achieve success with thread safety which is a little less complex than using ConcurrentDictionary, and uses the async-await pattern. Would this approach be recommended? Certainly not for performance reasons. But, the question would need to be asked in a different way to determine whether this class is useful or not.

Answer 1

If you modify the AsyncDictionary while enumerating its keys/values it throws InvalidOperationException (if the backing dictionary is a Dictionary).

var numbers = new AsyncDictionary<int, int>();

foreach(var number in Enumerable.Range(1, 1000))
{
    await numbers.AddAsync(number, number);
}

foreach(var number in await numbers.GetKeysAsync())
{
    await numbers.RemoveAsync(number);
}

A ConcurrentDictionary handles this scenario just fine.

Answer 2

The reason why there is no async API for a dictionary is, that all operations on a dictionary are so fast, that there is no need for asynchronicity.

For concurrent scenarios there is the thread safe variant - the ConcurrentDictionary.

Adding an async API to these dictionaries has absolutely zero value. Rather it increases complexity and reduces performance.

Answer 3

Threading Design

Your implementation has a very intrusive lock for all read and write operations, using the SemaphoreSlim with max concurrency 1.

try
{
    await _semaphoreSlim.WaitAsync()// <- both read/write operations acquire single mutex

    return await Task.Run(async () =>
    {
        return await func(_dictionary, keyValuePair);
    });
}
finally
{
    _semaphoreSlim.Release();
}

CallSynchronizedAsync is hence thread-safe to the extend you introduce possible fairness issues. In .NET, multiple threads awaiting a lock to get signaled are not notified in a fair way, meaning thread B may get the lock before A even if A asked to acquire the lock before B.

ConcurrentDictionary mitigates the risk on unfair thread signaling by using the following behavior:

• Read operations are volatile/atomic. No locks are used (Source: TryGetValue).
• Write operations are optimized for fast access and minimum lock timespans (Source: TryAddInternal).

Perhaps you should wrap a ConcurrentDictionary with async/await Task.Run or Task.FromResult functionality to take advantage of the built-in locking mechanism.

---

API Design

After discussing a bit with you in the comments, it became apparent you would like normal dictionary method signatures. This should not be a problem. Let's say you have a private field of type concurrent dictionary _dictionary. One option is to call the code synchronously and return Task.CompletedTask to make it fit the async/await pattern.

public async Task AddAsync(TKey key, TValue value)
{
    _dictionary.TryAdd(key, value);
    return Task.CompletedTask;
}

You could decide to also provide async/await-aware methods with concurrent dictionary signatures:

public async Task<bool> TryAddAsync(TKey key, TValue value)
{
    return Task.FromResult(_dictionary.TryAdd(key, value));
}

Answer 4

It's pretty hard to break something that uses a global lock around everything. So this seems pretty thread-safe. But that doesn't answer the question of why you'd want to use this.

Asynchronous calls are useful for things that take a long time, particularly if you can delegate the "waiting" to some low-level event based solution (HTTP requests for example).

For anything else, they not only make for a very awkward use of the API, they also are rather slow and involve a lot of compiler generated machinery (which if you're using it for a long running task won't matter much, but for something as simple as adding to a dictionary is plain awful).

When optimising, it's always important to first figure out what you want to optimise (what scenarios are you particularly worried about? how many readers to writers? how much 'global' concurrency on the dictionary? how much races on existing keys?) and then to measure.

Just as a baseline here is the overhead your solution has when simply adding elements sequentially compared to a concurrent dictionary, the standard dictionary and the standard dictionary with a simple lock around it:

|            Method |       N |        Mean |      Error |     StdDev | Ratio |
|------------------ |-------- |------------:|-----------:|-----------:|------:|
|         AddSimple | 1000000 |    34.94 ms |  0.4827 ms |  0.4515 ms |  1.00 |
|                   |         |             |            |            |       |
| AddSimpleWithLock | 1000000 |    52.14 ms |  0.7828 ms |  0.7323 ms |  1.00 |
|                   |         |             |            |            |       |
|     ConcurrentDic | 1000000 |   241.46 ms |  1.2975 ms |  1.2137 ms |  1.00 |
|                   |         |             |            |            |       |
|          AddAsync | 1000000 | 3,214.79 ms | 30.9326 ms | 28.9344 ms |  1.00 |

The following code was used to generate the results. If you haven't used BenchmarkDotNet before it's recommended to read up on it first to avoid getting incorrect results, but you can easily extend it for your other more interesting scenarios. In any case, the results are even worse than I imagined them to be (15 times slower than the concurrent dictionary is impressive even with all the boxing and async overhead - I guessed it'd be about 10 times at the start). (What shouldn't come as a surprise is how cheap uncontended locks are these days, everyone always running to ConcurrentDictionary and co might want to rethink that).

[ClrJob(baseline: true)]
public class DictionaryComparison
{
    private Random _rand;

    private Dictionary<int, int> _simpleDic;

    private Dictionary<int, int> _simpleDicWithLock;

    private readonly object _lock = new object();

    private ConcurrentDictionary<int, int> _concurrentDic;

    private AsyncDictionary<int, int> _asyncDictionary;

    [Params( 1_000_000)]
    public int N;

    [IterationSetup]
    public void IterationSetup()
    {
        _rand = new Random(0xdead);
        _simpleDic = new Dictionary<int, int>();
        _simpleDicWithLock = new Dictionary<int, int>();
        _concurrentDic = new ConcurrentDictionary<int, int>();
        _asyncDictionary = new AsyncDictionary<int, int>();
    }

    [Benchmark]
    public void AddSimple()
    {
        for (int i = 0; i < N; i++)
        {
            _simpleDic[i] = i;
        }
    }

    [Benchmark]
    public void AddSimpleWithLock()
    {
        for (int i = 0; i < N; i++)
        {
            lock (_lock)
            {
                _simpleDicWithLock[i] = i;
            }
        }
    }

    [Benchmark]
    public void ConcurrentDic()
    {
        for (int i = 0; i < N; i++)
        {
            _concurrentDic[i] = i;
        }
    }

    [Benchmark]
    public async Task AddAsync()
    {
        for (int i = 0; i < N; i++)
        {
            await _asyncDictionary.AddAsync(i, i);
        }
    }

}


public sealed class Program
{
    private static async Task Main(string[] args)
    {
        var summary = BenchmarkRunner.Run<DictionaryComparison>();
    }
}

PS: The work is so little even when adding a million elements, that the results are a bit dubious for the two AddSimple variants.