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?

Answer 1

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

Answer 2

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)

Answer 3

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.

Answer 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.

Answer 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.

Answer 6

You don't need to lock the SyncRoot property in your consumer objects. The lock you have within the methods of the dictionary is sufficient.

To Elaborate: What ends up happening is that your dictionary is locked for a longer period of time than is necessary.

What happens in your case is the following:

Say thread A acquires the lock on SyncRoot before the call to m_mySharedDictionary.Add. Thread B then attempts to acquire the lock but is blocked. In fact, all other threads are blocked. Thread A is allowed to call into the Add method. At the lock statement within the Add method, thread A is allowed to obtain the lock again because it already owns it. Upon exiting the lock context within the method and then outside the method, thread A has released all locks allowing other threads to continue.

You can simply allow any consumer to call into the Add method as the lock statement within your SharedDictionary class Add method will have the same effect. At this point in time, you have redundant locking. You would only lock on SyncRoot outside of one of the dictionary methods if you had to perform two operations on the dictionary object that needed to be guaranteed to occur consecutively.

Answer 7

Just a thought why not recreate the dictionary? If reading is a multitude of writing then locking will synchronize all requests.

example

    private static readonly object Lock = new object();
    private static Dictionary<string, string> _dict = new Dictionary<string, string>();

    private string Fetch(string key)
    {
        lock (Lock)
        {
            string returnValue;
            if (_dict.TryGetValue(key, out returnValue))
                return returnValue;

            returnValue = "find the new value";
            _dict = new Dictionary<string, string>(_dict) { { key, returnValue } };

            return returnValue;
        }
    }

    public string GetValue(key)
    {
        string returnValue;

        return _dict.TryGetValue(key, out returnValue)? returnValue : Fetch(key);
    }

Answer 8

Collections And Synchronization