Unsafe Thread Safety
I daresay that any longtime .NET developer must have had at least one dream (or nightmare) about the following two sentences: Any public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe. If you have any experience reading the MSDN documentation, you know this piece of text is ubiquitous there – it denotes types whose instances aren’t safe for parallel access from multiple threads (surprise, surprise).
One such type is the generic Dictionary class. Exactly what implications does this “lack of thread safety” have for its instances? In a nutshell, in this particular case, concurrent read operations are safe, but simultaneous write attempts (i.e., addition, modification or removal of elements) could make your dictionary lose its internal consistency. Simply put, you could break it.
Today I would like to compare the Dictionary class and its thread safe counterpart, ConcurrentDictionary. I’ll start, however, by pretending the latter doesn’t exist and writing my own version of it.
Note: As usual, I’m using examples from .NET. I do, however, believe that my point (if I have one) is equally applicable in other environments (e.g., Java).
Sweet naiveté…
Let’s assume I don’t know of the existence of ConcurrentDictionary, or I’m using an old version of .NET that doesn’t include it. (It was only introduced in .NET 4.) Also assume I need a dictionary impervious to concurrent access, which is why I’m going to write a wrapper around the regular Dictionary class to ensure thread safety.
As I don’t want to change the conceptual functionality of the class at all (I really like it), the public interface of my wrapper will be identical to that of the “wrapee”. The following code snippet shows my intended design:
{
private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();
private object instanceLock = new object();
...
public void Add(TKey key, TValue value)
{
lock(this.instanceLock)
{
this.dictionary.Add(key, value);
}
}
...
public void Remove(TKey key)
{
lock(this.instanceLock)
{
return this.dictionary.Remove(key);
}
}
...
}
Wow, that was easy! I always knew they were wrong when they told me I didn’t have what it takes… Finally, after all these years, I can take the following piece of code…
{
dictionaryWrapper.Add(myKey, myValue);
}
…and execute it concurrently without fear, huh? I am using my thread safe dictionary – what could go wrong…?
…unfortunately, a lot could go wrong. If two threads try to add a value for the same key at the same time, a race condition will exist. The first thread might check for the presence of the key in the dictionary, finding out it’s not there yet. The second thread could perform the same operation shortly after that, getting the same answer. Now, the first thread will successfully add the key/value pair to the dictionary, upon which the second thread attempts the same thing, but the operation will fail, as the first one has already added a value for the key. Put in a different way, another thread might add a value for your key in between the time you perform the check (ContainsKey) and attempt the addition (Add).
People have always called me naïve, and – like father, like son – my thread safe dictionary implementation reflects this naiveté, it appears…
Don’t reinvent the wheel!
Okay, I think my amnesia is going away now (and I also upgraded to the latest version of .NET); I do remember that there is an out-of-the-box ConcurrentDictionary class, and I’ll use it in lieu of my wrapper. It’s designed for this; surely the smart guys at Microsoft did a better job than me, eh?
As a matter of fact they did, and, as a result, my code doesn’t even compile now – the class exposes no Add method. Instead, you have at least three alternatives to choose from: TryAdd, AddOrUpdate and GetOrAdd.
Unlike me, the designers of ConcurrentDictionary decided not to preserve the public interface of the original Dictionary class. They replaced it with one more suitable for concurrent use; it makes it harder for you to shoot yourself in the foot with the class. By collapsing the ContainsKey and Add operations into one (TryAdd), they eliminated the possibility of a race condition.
It does make it harder, but by no means impossible for you to pump that foot of yours full of lead. Suppose, for example, that your solution includes operations that span multiple instances of the class. (I.e., you use two or more concurrent dictionaries as part of a single, conceptually indivisible, “atomic” operation.) All of a sudden, your solution is prone to the same problems as my code snippet above.
Nor is my wrapper all bad and unusable, as a matter of fact. Imagine I’m using the wrapper to maintain an actual dictionary (the keys represent words in English, the values their Swedish translations). In order to make my application more scalable, I decide to spawn multiple threads to process words in parallel. Maybe I could get a little clever here. What if I dedicate one thread to words starting with each letter in the English alphabet – a thread for all words starting with A, another one for B words, etc.?
Interestingly enough, this makes the race condition (in the snippet above) go away! I no longer have to worry about the possibility of another thread adding a value for my key, as I know that my thread’s word (i.e., key) will be outside the “jurisdiction” of any other thread. (It is, for example, a word starting with M, and mine is the only thread processing those words.) The dictionary itself is thread safe, so I don’t have to worry about breaking its internal consistency, and I designed my solution in a way that obviates race conditions. Voila!
The bottom line is this: Although some designs of thread safe classes (such as ConcurrentDictionary) make it easier for you to write code suitable for concurrent use than others (such as my very own DictionaryWrapper), the ultimate responsibility is yours.
Leakage and leakage by design
Here’s what I see as the moral of the story: If we view my wrapper and the ConcurrentDictionary class as attempts to abstract away from concurrency-related issues, we have to conclude that they represent leaky abstractions. Mine leaks in a very insidious way, as it doesn’t even nudge you in the right direction. ConcurrentDictionary does nudge you in the right direction – its designers obviously tried to facilitate your fall into the proverbial “pit of success” – but it still leaks.
I find it interesting to observe that they could only achieve this “nudge” by changing the public interface of the class, which means that you, its user, will have to change your code (if you’re replacing the regular Dictionary class with ConcurrentDictionary). In other words, the way I see it, not only does this abstraction leak, it leaks by design.
In Stop Leak, my previous post, I express the conviction that abstractions are more likely to leak if they abstract away from something conceptual (i.e., essential) as opposed to technical (i.e., accidental) in nature. This is how I believe you can relate those ideas to the discussion presented here:
- Both my naïve wrapper and the wise ConcurrentDictionary class abstract away from the technical (accidental) complexities of parallel access – you cannot “break” instances of either class the way you can break instances of the regular Dictionary class; apart from probably incurring a small performance penalty, this part of the abstraction is, in my opinion, fairly “airtight” (i.e., not leaky)
- As briefly alluded to in Stop Leak, I believe that the introduction of multiple threads into your application represents a conceptual (i.e., essential) shift from single-threaded software; this is where both my implementation and ConcurrentDictionary leak: The developer using them will have to deal with the consequences of something they had hoped to be able to ignore
Note: I’m not going to reintroduce what is meant by essence and accident here. Instead, I will refer you to the Stanford Encyclopedia of Philosophy, Frederick Brooks’ essay, No Silver Bullet – Essence and Accident in Software Engineering, as well as Stop Leak, my previous post. Suffice it to say, for the purposes of this article, that the technical lack of thread safety of the regular Dictionary class is accidental (which in this case doesn’t mean ‘occurring by chance’), whereas the problems that leak into your code are essential (i.e., conceptual) – in my opinion, that is…
Conclusion
In addition to using the various dictionary incarnations as a case study to support my point from Stop Leak, I believe that all of this nicely demonstrates something we (hopefully) all intuitively know: You can’t expect any technical solution to allow you to completely abstract away from all complexities associated with parallelism and asynchrony.
There are times when you don’t have to understand how things behind a particular abstraction work: I can build even relatively sophisticated graphics applications without understanding the details of the workings of video adapters. Concurrency is not one of those things.
The various libraries, frameworks and language constructs (such as Task Parallel Library and async/await) are no doubt extremely useful in that they make developers way more productive, and allow them to write nicer, cleaner and more readable code. However, they are not a replacement for deep knowledge. If you do use them, I think you’d better know what you’re doing and why.
Postscript: Sadly, after I'd written the initial draft of this article, Microsoft changed the two dream sentences mentioned in the first paragraph. The replacement one-sentence thread safety message pales in comparison with the original, and I won’t even quote it here.