Safely removing list mapping from ConcurrentDictionary

Question

I have a ConcurrentDictionary which maps a simple type to a list:

var dict = new ConcurrentDictionary<string, List<string>>();

I can use AddOrUpdate() to cater for both initialization of the list when the first value is added, and addition of subsequent values to the list.

However, the same isn't true for removal. If I do something like:

public void Remove(string key, string value)
{
    List<string> list;
    var found = dict.TryGetValue(key, out list);

    if (found)
    {
        list.Remove(value);
        if (list.Count == 0)
        {
            // warning: possible race condition here
            dict.TryRemove(key, out list);
        }
    }
}

...where my intention is to remove the key completely if the corresponding list no longer has any values (similar to reference counting, in concept), then I'm risking a race condition because someone might have added something to the list right after I checked whether it's empty.

Although I am using a list in this simple example, I usually have a ConcurrentBag or ConcurrentDictionary in such scenarios, and the risk is quite similar.

Is there any way of safely removing a key when the corresponding collection is empty, short of resorting to locks?

Is there also a potential race between calling `TryGetValue` and the `Remove`? — doctorlove, Dec 04 '14 at 15:19
I could be wrong, but I don't think so... if someone adds something before the emptiness check, then it won't be empty... — Gigi, Dec 04 '14 at 15:35
If two things are removed concurrently, and then one of them finds the list empty and removes it, that's expected behaviour. The real danger is losing a list that isn't empty because of the race condition. — Gigi, Dec 04 '14 at 16:03

xxbbcc · Accepted Answer · 2014-12-04T15:26:32.677

1

Your ConcurrentDictionary is protected but your list is not. If your list can be accessed from multiple threads (I assume this is the case) you need to use locking around all accesses to the list or you need to use a different construct.

After you call TryGetValue in your Remove function, you access the list multiple times - since List<T> is not safe for multithreading, you run the risk of various threading issues.

If you use nested ConcurrentDictionaries in dict, you only run the problem of removing something that's not empty - as you wrote, it's possible that an item is added to the nested ConcurrentDictionary after you check its size. Removing the nested list / dictionary itself is thread-safe: the containing dict is a ConcurrentDictionary and it'll handle removing items safely. However, if you want to guarantee that a list/dictionary is only removed if it's empty, you have to use a lock around the whole operation.

This is because the container dict and the nested list/dictionary are two different constructs and touching one has no effect on the other - if you need the entire multi-step operation to be atomic, you'll have to make sure only one thread can attempt to do it at a time.

Your code would be something like this:

if (found)
{
    lock ( _listLock )
    {
        list.Remove(value);

        if (list.Count == 0)
        {
            // warning: possible race condition here
            dict.TryRemove(key, out list);
        }
    }
}

Again, if you're using an unprotected construct (like a List<T> then you have to use locking around every access to that list.

edited Dec 04 '14 at 15:26

answered Dec 04 '14 at 15:18

xxbbcc

16,930
5
50
83

I wonder if the lock needs to be a bit higher up - i.e. before `found` is set – doctorlove Dec 04 '14 at 15:56
@doctorlove I don't think so (but I don't mean to sound authorative on this :) ). Once `TryGetValue` returns, you hold a reference to the list so nothing can happen to it (it won't go away, etc). `found` is a local variable, other threads cannot mess with it. The actual work that's supposed to be atomic happens inside the `if` block, so I think it's enough to lock that. – xxbbcc Dec 04 '14 at 15:59
If you protect the `TryRemove` with a `lock` then you must use the same `lock` on every access to the concurrent dictionary. Otherwise this single `lock` achieves nothing. – Theodor Zoulias Mar 15 '20 at 20:22
@TheodorZoulias I don't believe in this case the `ConcurrentDictionary` needs the lock. The lock is in place because the list instance is modified and that same list may be modified in another thread at the same time. Getting / Removing the list instance from the dictionary don't need the lock; the `TryRemove()` call is inside the lock because of the `if()` that acts on the list instance that must be protected. Do you think my reasoning is flawed? – xxbbcc Mar 16 '20 at 17:40
I guess that items can be inserted in the list from another thread concurrently. If you don't protect with the same lock the code that inserts items, then an item could be added after the line `if (list.Count == 0)` and before the line `dict.TryRemove(key, out list)`. In that case a non-empty list will be removed from the dictionary. Isn't it a problem? – Theodor Zoulias Mar 16 '20 at 17:50
You're right, all access to the _list_ should be protected using the same lock. In the above example, the list is already protected but I thought your comment was about the dictionary - the dictionary doesn't need further protection. The list size check is inside the lock and another thread adding to the same list should be proctected by the same lock so that the Count check cannot return invalid data. – xxbbcc Mar 16 '20 at 17:58
Unfortunately the dictionary needs protection too. Otherwise a thread could remove a wrong list instead of the original list that was retrieved earlier with the `TryGetValue`. Even if the `TryRemove` was conditional, by accepting a third `comparand` parameter, the problem would probably still be unsolvable, at least with mutable lists. @mafu has tried to solve it [here](https://stackoverflow.com/questions/60695167/concurrentdictionary-with-multiple-values-per-key-removing-empty-entries/60696087#60696087) with locks, immutable lists and spinning, but I have not tested his solution. – Theodor Zoulias Mar 17 '20 at 10:09

Safely removing list mapping from ConcurrentDictionary

1 Answers1

Linked