Hello, I am Laszlo

ConcurrentDictionary over List 1

09/13/2018

4 minutes

One of the rare situations, I face is having a dictionary of key-value pairs, where the values are a collection of some items. One example could be the following dictionary, where the keys are strings, and the values are a list of integers.

ConcurrentDictionary<string, List<int>>

In the series of this and the following posts, I will investigate how these collections can be made thread-safe.

Problem

09/13/2018

4 minutes

The problem starts when we have multiple threads using (writing and reading) this dictionary at the same time. To avoid state corruption, we need to control this access by making it thread-safe.

The Wrong Solution

09/13/2018

4 minutes

The first part of these series will approach a wrong solution, and I will point out why it is the wrong one.One can pose that the quickest solution is to simply replace to the Dictionary with a Concurrent one.

public ConcurrentDictionary<string, List<int>> _data = new ConcurrentDictionary<string, List<int>>();

Once this is done, we can use the GetOrAdd, AddOrUpdate, TryGetValue, TryAdd, TryUpdate, etc. methods to access the dictionary. In this case, I will focus on using the AddOrUpdate method along with the TryGetValue method. In other words, I will do concurrent Adds/Updates while also reading the collections items stored at a given key.

When using the AddOrUpdate, I prefer to use the overload which takes a key and two Function parameters to save resources/allocations.

There is one very important remark mentioned on the documentation of AddOrUpdate:

If you call AddOrUpdate simultaneously on different threads, addValueFactory may be called multiple times, but its key/value pair might not be added to the dictionary for every call.

According to this remark our functions passed to the AddOrUpdate method will run concurrently. So in case there are multiple threads amending the very same key entry in the collection (adding, removing or iterating items on the List) the solution is not thread-safe.

Let me demonstrate this with very simple example, I will use over-and-over in the following posts of this series.

Proving it to be wrong

I will have the following test environment:

public static async Task Main(string[] args)
{
  const int Interations = 5000000;
  var test = new NonConcurrent();
  var taskAddA = Task.Run(() =>
  {
    int i = 0;
    while(i++ < Interations)
    {
      test.TestAdd();
    }
  });
  var taskRead = Task.Run(() =>
  {
    int i = 0;
    while(i++ < Interations)
    {
      test.TestRead();
    }
  })
  await Task.WhenAll(taskAddA, taskRead);
}

There are two tasks running parallel, one is constantly adding an item to the list with TestAdd() method, one is constantly enumerating the list under a given key with the TestRead() method.

In the above code, I use the following test class (NonConcurrent):

public class NonConcurrent
{
  public ConcurrentDictionary<string, List<int>> _data = new ConcurrentDictionary<string, List<int>>();
  public void TestAdd()
  {
    _data.AddOrUpdate("key", key => new List<int>(), (key, list) =>
    {
      list.Add(100);
      return list;
    });
  }
  public int TestRead()
  {
    int sum = 0;
    if(_data.TryGetValue("key", out List<int> mylist))
    {
      foreach(var item in mylist)
      {
        sum += item;
      }
    }
    return sum;
  }
}

In the TestAdd() method of the test class I add the integer of 100 to the list under the "key" string as the key of dictionary. In the TestRead() method, I read the list under the "key" string key, and once the list is read, I enumereate the values.

Running this solution is very likely to throw an exception at some point, because we are modifying the list while enumerating it at the same time, and the list itself is not thread-safe.

Note, that you can get lucky with concurrency, and may not see this exception at all. It is unlikely with this number of iterations, but there is still a small chance for that.

In the following post, I will take another approach proving this solution to be wrong, which does not throw an exception, hence it is a lot more difficult to notice.