What's the best way of implementing a thread-safe Dictionary?

Question

I was able to implement a thread-safe Dictionary in C# by deriving from IDictionary and defining a private SyncRoot object:

public class SafeDictionary<TKey, TValue>: IDictionary<TKey, TValue>
{
    private readonly object syncRoot = new object();
    private Dictionary<TKey, TValue> d = new Dictionary<TKey, TValue>();

    public object SyncRoot
    {
        get { return syncRoot; }
    } 

    public void Add(TKey key, TValue value)
    {
        lock (syncRoot)
        {
            d.Add(key, value);
        }
    }

    // more IDictionary members...
}

I then lock on this SyncRoot object throughout my consumers (multiple threads):

Example:

lock (m_MySharedDictionary.SyncRoot)
{
    m_MySharedDictionary.Add(...);
}

I was able to make it work, but this resulted in some ugly code. My question is, is there a better, more elegant way of implementing a thread-safe Dictionary?

Solution 1

As Peter said, you can encapsulate all of the thread safety inside the class. You will need to be careful with any events you expose or add, making sure that they get invoked outside of any locks.

public class SafeDictionary<TKey, TValue>: IDictionary<TKey, TValue>
{
    private readonly object syncRoot = new object();
    private Dictionary<TKey, TValue> d = new Dictionary<TKey, TValue>();

    public void Add(TKey key, TValue value)
    {
        lock (syncRoot)
        {
            d.Add(key, value);
        }
        OnItemAdded(EventArgs.Empty);
    }

    public event EventHandler ItemAdded;

    protected virtual void OnItemAdded(EventArgs e)
    {
        EventHandler handler = ItemAdded;
        if (handler != null)
            handler(this, e);
    }

    // more IDictionary members...
}

Edit: The MSDN docs point out that enumerating is inherently not thread safe. That can be one reason for exposing a synchronization object outside your class. Another way to approach that would be to provide some methods for performing an action on all members and lock around the enumerating of the members. The problem with this is that you don't know if the action passed to that function calls some member of your dictionary (that would result in a deadlock). Exposing the synchronization object allows the consumer to make those decisions and doesn't hide the deadlock inside your class.

Solution 2

The .NET 4.0 class that supports concurrency is named ConcurrentDictionary.

Solution 3

Attempting to synchronize internally will almost certainly be insufficient because it's at too low a level of abstraction. Say you make the Add and ContainsKey operations individually thread-safe as follows:

public void Add(TKey key, TValue value)
{
    lock (this.syncRoot)
    {
        this.innerDictionary.Add(key, value);
    }
}

public bool ContainsKey(TKey key)
{
    lock (this.syncRoot)
    {
        return this.innerDictionary.ContainsKey(key);
    }
}

Then what happens when you call this supposedly thread-safe bit of code from multiple threads? Will it always work OK?

if (!mySafeDictionary.ContainsKey(someKey))
{
    mySafeDictionary.Add(someKey, someValue);
}

The simple answer is no. At some point the Add method will throw an exception indicating that the key already exists in the dictionary. How can this be with a thread-safe dictionary, you might ask? Well just because each operation is thread-safe, the combination of two operations is not, as another thread could modify it between your call to ContainsKey and Add.

Which means to write this type of scenario correctly you need a lock outside the dictionary, e.g.

lock (mySafeDictionary)
{
    if (!mySafeDictionary.ContainsKey(someKey))
    {
        mySafeDictionary.Add(someKey, someValue);
    }
}

But now, seeing as you're having to write externally locking code, you're mixing up internal and external synchronisation, which always leads to problems such as unclear code and deadlocks. So ultimately you're probably better to either:

1. Use a normal Dictionary<TKey, TValue> and synchronize externally, enclosing the compound operations on it, or

2. Write a new thread-safe wrapper with a different interface (i.e. not IDictionary<T>) that combines the operations such as an AddIfNotContained method so you never need to combine operations from it.

(I tend to go with #1 myself)

Solution 4

You shouldn't publish your private lock object through a property. The lock object should exist privately for the sole purpose of acting as a rendezvous point.

If performance proves to be poor using the standard lock then Wintellect's Power Threading collection of locks can be very useful.

Solution 5

There are several problems with implementation method you are describing.

1. You shouldn't ever expose your synchronization object. Doing so will open up yourself to a consumer grabbing the object and taking a lock on it and then you're toast.
2. You're implementing a non-thread safe interface with a thread safe class. IMHO this will cost you down the road

Personally, I've found the best way to implement a thread safe class is via immutability. It really reduces the number of problems you can run into with thread safety. Check out Eric Lippert's Blog for more details.

View more solutions

Comments

[Asaf R]

What is it you find ugly about it?

[Peter Meyer]

I think he's referring to all the lock statements he has throughout his code within the consumers of the SharedDictionary class -- he's locking in the calling code everytime he's accessing a method on a SharedDictionary object.

[testuser]

Instead of using Add method try doing by assigning values ex- m_MySharedDictionary["key1"]="item1", this is thread safe.

[GP.]

@fryguybob: Enumeration was actually the only reason why I was exposing the synchronization object. By convention, I would perform a lock on that object only when I'm enumerating through the collection.

[Oleg Vladimirov]

If your dictionary isn't too large you can enumerate on a copy and have that built in to the class.

[GP.]

My dictionary isn't too large, and I think that did the trick. What I did was make a new public method called CopyForEnum() which returns new instance of a Dictionary with copies of the private dictionary. This method was then called for enumarations, and the SyncRoot was removed. Thanks!

[plinth]

This is also not an inherently threadsafe class since dictionary operations tend to be granular. A little logic along the lines of if (dict.Contains(whatever)) { dict.Remove(whatever); dict.Add(whatever, newval); } is assuredly a race condition waiting to happen.

[Meydjer Luzzoli]

It's worth pointing out that .NET 4.0 will include a whole bunch of thread-safe containers such as collections and dictionaries, which have a different interface to the standard collection (i.e. they're doing option 2 above for you).

[Tim]

Not true...if you do two operations after another that are internally thread-safe, that does not mean that the overall code block is thread safe. For instance: if(!myDict.ContainsKey(someKey)) { myDict.Add(someKey, someValue); } would not be threadsafe, even it ContainsKey and Add are threadsafe

[Peter Meyer]

Your point is correct, but is out of context with my answer and the question. If you look at the question, it doesn't talk about calling ContainsKey, nor does my answer. My answer refers to acquiring a lock on SyncRoot which is shown in the example in the original question. Within the context of the lock statement one or more thread-safe operations would indeed execute safely.

[Tim]

I guess if all he is ever doing is adding to the dictionary, but since he has "// more IDictionary members...", I assume at some point he is also going to want to read back data from the dictionary. If that is the case, then there needs to be some externally accessible locking mechanism. It doesn't matter if it is the SyncRoot in the dictionary itself or another object used solely for locking, but without such a scheme, the overall code will not be thread-safe.

[Peter Meyer]

The external locking mechanism is as he shows in his example in the question: lock (m_MySharedDictionary.SyncRoot) { m_MySharedDictionary.Add(...); } -- it would be perfectly safe to do the following: lock (m_MySharedDictionary.SyncRoot) { if (!m_MySharedDictionary.Contains(...)) { m_MySharedDictionary.Add(...); } } In other words, the external locking mechanism is the lock statement that operates on the public property SyncRoot.

[El Ronnoco]

-1 I've voted this down because a) it's just a link with no explanation and b) it's just a link with no explanation!

[supercat]

It's also worth noting that the granularity offered by even crude locking will often be sufficient for a single-writer multiple-readers approach if one designs a suitable enumerator which lets the underlying class know when it's disposed (methods which would want to write the dictionary while an undisposed enumerator exists should replace the dictionary with a copy).

[Alberto León]

Please mark this as response, you don't need custom dictoniary if the own .Net has a solution

[Jeppe Stig Nielsen]

(Remember that the other answer was written long before the existence of .NET 4.0 (released in 2010).)

[Triynko]

Unfortunately it's not a lock-free solution, so it's useless in SQL Server CLR safe assemblies. You'd need something like what's described here: cse.chalmers.se/~tsigas/papers/Lock-Free_Dictionary.pdf or perhaps this implementation: github.com/hackcraft/Ariadne

[outbred]

Really old, I know, but it is important to note that using the ConcurrentDictionary vs a Dictionary can result in significant performance losses. This is most likely the result of expensive context switching, so be certain that you need a thread-safe dictionary before using one.

[György Kőszeg]

ConcurrentDictionary can be surprisingly slow in some cases. Depending on your use case some alternative ThreadSafeDictionary implementation might be better (disclaimer: written by me). See the bottom of the page for comparisons and recommended use cases. (NuGet)