Why are thread safe collections so hard?
Writing a collection which is mutable, thread safe and usable is an extremely difficult process. At least that’s what you’ve likely been told all through your schooling. But then you get out on the web and see a multitude of thread safe lists, maps and queues. If it’s so hard, why are there so many examples?
The problem is there are several levels of thread safe collections. I find that when most people say thread safe collection what they really mean “a collection that will not be corrupted when modified and accessed from multiple threads”. Lets call this “data thread safe” for brevity. This type of collection is rather easy to build. Virtually any collection that is not thread safe can be made “data thread safe” by synchronizing access via a simple locking mechanism.
For Example, lets build a data thread safe List<T>.
public sealed class ThreadSafeList<T> : IEnumerable<T> {
private List<T> m_list = new List<T>();
private object m_lock = new object();
public void Add(T value) {
lock (m_lock) {
m_list.Add(value);
}
}
public void Remove(T value) {
lock (m_lock) {
m_list.Remove(value);
}
}
public bool Contains(T value) {
lock (m_lock) {
return m_list.Contains(value);
}
}
public int Count { get { lock (m_lock) { return m_list.Count; } } }
public T this[int index] {
get { lock (m_lock) { return m_list[index]; } }
set { lock (m_lock) { m_list[index] = value; } }
}
// IEnumerable<T> left out
}
And there you have it. The lock statement prevents concurrent access from multiple threads. So the actual m_list instance is only ever accessed by a single thread at a time which is all it’s designed to do. This means instances of ThreadSafeList<T> can be used from any thread without fear of corrupting the underlying data.
But if building a data thread safe list is so easy, why doesn’t Microsoft add these standard collections in the framework?
Answer: ThreadSafeList<T> is a virtually unusable class because the design leads you down the path to bad code.
The flaws in this design are not apparent until you examine how lists are commonly used. For example, take the following code which attempts to grab the first element out of the list if there is one.
static int GetFirstOrDefault(ThreadSafeList<int> list) {
if (list.Count > 0) {
return list[0];
}
return 0;
}
This code is a classic race condition. Consider the case where there is only one element in the list. If another thread removes that element in between the if statement and the return statement, the return statement will throw an exception because it’s trying to access an invalid index in the list. Even though ThreadSafeList<T> is data thread safe, there is nothing guaranteeing the validity of a return value of one call across the next call to the same object.
I refer to procedures like Count as decision procedures. They server only to allow you to make a decision about the underlying object. Decision procedures on a concurrent object are virtually useless. As soon as the decision is returned, you must assume the object has changed and hence you cannot use the result to take any action.
Decision procedures are one of the reasons why Immutable Collections are so attractive. They are both data thread safe and allow you to reason about there APIs. Immutable Collections don’t change ever. Hence it’s perfectly ok to have decision procedures on them because the result won’t get invalidated.
The fundamental issue with ThreadSafeList<T> is it is designed to act like a List<T>. Yet List<T> is not designed for concurrent access. When building a mutable concurrent collection, in addition to considering the validity of the data, you must consider how design the API to deal with the constantly changing nature of the collection.
When designing a concurrent collection you should follow different guidelines than for a normal collection class. For example.
- Don’t add an decision procedures. They lead users down the path to bad code.
- Methods which query the object can always fail and the API should reflect this.
Based on that, lets look at a refined design for ThreadSafeList<T>
public sealed class ThreadSafeList<T> {
private List<T> m_list = new List<T>();
private object m_lock = new object();
public void Add(T value) {
lock (m_lock) {
m_list.Add(value);
}
}
public bool TryRemove(T value) {
lock (m_lock) {
return m_list.Remove(value);
}
}
public bool TryGet(int index, out T value) {
lock ( m_lock ) {
if( index < m_list.Count ) {
value = m_list[index];
return true;
}
value = default(T);
return false;
}
}
}
Summary of the changes
- Both the Contains and Count procedures were removed because they were decision procedures
- Remove was converted to TryRemove to indicate it’s potential to fail
- The TryGet property was added and is reflective of the fragile nature of the method. Sure it’s possible for users to simply ignore the return value and plow on with the invalid value. However the API is not lulling the user into a false sense of security
- The collection no longer implements IEnumerable<T>. IEnumerable<T> is only valid when a collection is not changing under the hood. There is no way to easily make this guarantee with a collection built this way and hence it was removed.
- The indexers were removed as well. I’m a bit wishy washy in this particular point as there is nothing in the API which gives a user a false sense of security. But at the same time mutable concurrent collections are dangerous and should be treated with a heightened sense of respect so the indexers were removed.
This version of ThreadSafeList is more resilient, but not immune to, accidental user failure. The design tends to lead users on the path to better code.
But is it really usable? Would you use it in your application?
Comments
Anonymous
February 11, 2009
PingBack from http://www.clickandsolve.com/?p=6304Anonymous
February 11, 2009
This is a good post, but I would avoid using lock though. It is like using a sledge hammer to tap a picture hook into the wall. It is very inefficient. Using ReaderWriterLock is better, but ReaderWriterLockSlim is better again if you can use the 3.5 framework. The main issue with lock is that it is an exclusive lock regardless of whether the request is a read or write action. The ReaderWriterLock/ReaderWriterLockSlim implementations allow concurrent reads because they don't change state while writes get appropriately queued for exclusive write access.Anonymous
February 11, 2009
@Rory, The last time I read a bit about ReaderWriterLock (non slim version), it said that ReaderWriterLock is actually only more efficient if the number of reads at least doubles the number of writes. I think that's probably a reasonable expectation for a list class but it would still be highly usage dependent. But this post was definitely not about efficiency, more about usage :)Anonymous
February 11, 2009
I generally find that kind of complexity to be not unusable but definitely not worth the limitations. I prefer to keep my data objects (classes of properties and collections of those classes) "stupid" and pass the responsibility for concurrency up the chain of command (either have the owning instance itself non-threadsafe or let it manage all its concurrency - especially if it has multiple collections)Anonymous
February 11, 2009
Great post. The truth is, mutable collections are only as thread-safe as the code that uses them. An enumerator will never be thread-safe, the whole if (exists) { remove } scenario will never be either. You mention that Microsoft doesn't ship these classes. Oh but they do. :) Remember the whole .NET 1.0-era convention of using a Synchronized() method that returned an instance of the collection that had locks around its accessors? Then there's the big SyncRoot blunder. So they did go down this path at first and realized it was a lost cause. Immutable lists, while they are certainly attractive, will not be suitable for some of the more performance sensitive scenarios. But they'd be a welcome addition to the framework.Anonymous
February 11, 2009
That a thread-safe collection can't possibly be enumerable is a nice little packet of insight.Anonymous
February 12, 2009
Thank you for submitting this cool story - Trackback from DotNetShoutoutAnonymous
February 12, 2009
Sure that should be: if( index < m_list.Count ) { value = m_list[index]; //index not 0 return true; } (in the public bool TryGet method)Anonymous
February 12, 2009
@Josh Einstein & Larry Lard > An enumerator will never be thread-safe, the whole if (exists) { remove } scenario will never be either. > That a thread-safe collection can't possibly be enumerable is a nice little packet of insight. It depends of what "enumerator" or "enumerable" means to you. If it's solely the Java/C# external enumeration (an externally consumed sequence object extracted from the collection) then yeah. If on the other hand it's the general concept of traversing a sequence/collection and applying an operation (reduction, filtering, transformation, combination, side-effectful operation) at each step then it should be possible to iterate in a thread-safe manner using internal iterators, where you tell the collection/sequence the kind of iteration you want (or call a function that does it) and provide the block of code to run at each iterative step, as in Smalltalk, Ruby or most functional languages.Anonymous
February 12, 2009
@FredV, yep that was a typo, updated now. Thanks for pointing it out!Anonymous
February 12, 2009
A collection can be made both thread-safe and enumerable by using copy on write semantics. The enumerator that the client is given is then a snapshot of the list and is guaranteed not to change.Anonymous
February 12, 2009
@Jordan, Yes that certainly does the trick. Essentially you hook into the IEnumerable<T>.GetEnumerator() call and return a snapshot of the list. Then the data contract portion of IEnumerator<T> can be easily implemented. But this does create a semantic difference. Most IEnumerator<T> implementations are completely invalidated when the collection is modified. The new version won't be which is fine (it's in fact much more reliable). But how do you convey that semantic change to the user? Users who don't understand the concrete details of the collection class are likely to assume that like any other collection, changing this thread safe collection, will also invalidate the enumerator. They are likely to take steps to prevent it from occurring. Astute users will see the insane complexity in getting that correct. Instead of implementing IEnumerable<T>, it think it's much better to have a method called GetSnapshot() which returns an IEnumerable<T>. The name is more indicative of the behavior than just implemeting IEnumerable<T> would be.Anonymous
February 12, 2009
@Jared The problem with only providing a GetSnapshot method is that by not implementing the IEnumerable<T> interface you're excluding the programmer from participating in any functions that work on IEnumerable<T> objects.Anonymous
February 12, 2009
@Jordan I disagree. Because GetSnapshot() provides an IEnumerable<T>, participation is just as possible. All this method prevents is implicit participation. I feel this is justified because the implicit behavior is likely to be behavior the user is not expecting. GetSnapshot() is (at least hopefully) and unambiguous method and makes it clear to the user that the IEnumerable<T> used won't ever change.Anonymous
February 12, 2009
You've been kicked (a good thing) - Trackback from DotNetKicks.comAnonymous
February 12, 2009
@Jared Sorry, I see my mistake. I was taking GetSnapshot() to return an enumerator, not an enumerable. Still, I'd personally rather the collection just be directly enumerable. Like Java's CopyOnWriteArrayList<E>Anonymous
February 12, 2009
"Immutable lists, while they are certainly attractive, will not be suitable for some of the more performance sensitive scenarios." Josh, can you explain? Clojure uses exclusively immutable lists (and hashtables), and it's no performance slouch, to say the least. I've seen demonstrations of how easy it is with Clojure to write correct code that distributes easily across hundreds of cores. ISTM that the value of being able to easily write working multicore code will, except in pathological cases, far outweigh the minimal overhead that immutable data structures might have.Anonymous
February 12, 2009
It is not hard to do that. However, threading is a topic that isn't easily explained. I couldn't develop using threads until I discovered the book "C# 2008 and 2005 threaded programming", by Gaston Hillar, Packt Publishing. The book makes threading and multicore programming easy, with real life examples. http://www.packtpub.com/beginners-guide-for-C-sharp-2008-and-2005-threaded-programming Most C# books teach threading using Console.Writeline ...... Console.Writeline ....... Console.Writeline Yeah! I know how to write lines, but when I have to update the UI ,....... I'm dead man!! :( That's the problem. The aforementioned book saved my life with multithreading! Highly recommended.Anonymous
February 13, 2009
Jared to answer your question, no I don't think I would want to use the ThreadSafeList class in my application. The lack of Contains and Count methods just make the api of the class cumbersome to use for any real world application. I can't think of hardly any times I've used a collection or list when I didn't need to check the "Count" or see what it "Contains".Anonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
I haven't yet seen a need for any thread safe collections, at least in ASP.NET programming. I let IIS or the database handle concurrency. If I have to start a long running process, I usually do it by submitting a database job and not by starting a new .NET worker thread (or using one from a thread pool). If I'm bulk updating database, and I know there is very light user activity, I can use parallel query facilities. I know there has been a lot of programming effort recently in the area of multi-threading, probably in response to the availability of multi-core processors. Are people mainly using threading in client GUI applications? I don't get it. It seems theoretical to me. I guess I'm asking where does this fit into an overall application design? In a web application, don't we want to avoid sharing data structures between sessions?Anonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
Great article. With multi-core sparking more concurrecny discussion it is a good thing to really make people aware of the possible pitfalls. The only thing I would add to your second, more appropriate implementation, would be to provide an example of how the try methods could be used. A perfect example would be a SQL Server deadlock. Keep trying to access the resource until a specified amount of time has passed and based off of the architecture decide the appropriate approach if the resource is still locked after that amount of time has passed. This shows that even an application as extremely concurrent and mission critical can and will fail and that there never is a true thread safe based application. We can do our best to try but thread safety will never be perfect.Anonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
@Gregory Kornblum, "We can do our best to try but thread safety will never be perfect." This is wrong. There are models in which applications can be proven to be correct, even though they use multiple threads. The key is to not share state.Anonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
@wekempf "It's discussions like this that illustrate why the current threading models that "shared state" languages use need to be abandoned." Are you including languages like C and C++? But haven't people been writing very effective multi-threaded code in these languages for many years? IIS or Oracle for example. I wish I could understand the motivation for doing multi-threading in .NET applications. I don't know if many developers will need to worry about it, multi-core processors notwithstanding. Can anyone please give me an example where you would want to use a shared collection like a list in a real world .NET application? Is it for client code?Anonymous
February 13, 2009
"You can definitely make the mistake of using TryGet to incorrectly reason about a future TryGet. Exmaple: "I TryGet'd 1 so TryGet(0) must work". But I'd argue that having functions where the volatility is called out in the name makes it less likely that people will make these types of reasoning. More importantly, it won't take them by surprise when it fails. This is speculative though." Then by including the index in the signature of TryGet you've accidentally exposed a "decision property". Give me ANY scenario in which you could call this function with anything other than 0, and effectively reason about the results. "I prefer immutable ;) Reason about them all you want." Then why did you bother with a mutable list here?Anonymous
February 13, 2009
The comment has been removedAnonymous
February 13, 2009
@wekempf [wekempf] Then by including the index in the signature of TryGet you've accidentally exposed a "decision property". I can see that argument. [wekempf] Then why did you bother with a mutable list here? Becaues customers use them. The post is meant as an education post to the dangers of "supposedly" thread safe mutable collections. And a first step towards designing API's that make mutable collections more managable. I'd love it if the world only used immutable collections for multi-threaded scenarios but the reality is people don't. There's a good portion of the population who just want mutable thread safe collections (and several who have good reasons). The next post includes a much more usable design for mutable collections.Anonymous
February 14, 2009
@wekempf "Immutable collections don't do away with "Count" and "Contains". String is such a type in the .NET realm." I never said that it did. My comment was specifically about the final ThreadList implementation which did do away with the two methods I mentioned leaving it to the client code to figure it out somehow. Also, according to your own words and the code the ThreadList isn't immutable so you can't really compare it to the String class. "Your ThreadSafeList isn't immutable, and thus is not thread safe."Anonymous
February 14, 2009
As some people have already pointed out, I don't thin the new proposal of Thread safe collection makes any difference. You're just getting a bool instead of an exception.. so what? I'm with Keith who made one of the first comments in this post: The best you can do is just to have an external lock. Because the user of the list will be the one who really now how to make it thread safe. So you want to make a thread-safe list easier to do? Okey then, just create a new kind of list which is like the first one but shares the internal lock object with the user, so that he doesn't need to create an external one. What about that?Anonymous
February 14, 2009
Uh oh of course you can't share exactly the same lock you use internally in the list with the user, otherwise if the user captures the lock because he is going to use the list, he can't use the list because it's locked. What I meant is that the list could come with another lock accessible by a getter like lock() so that the user itself doesn't need to create it.Anonymous
February 14, 2009
@Eduardo [Eduardo] I don't thin the new proposal of Thread safe collection makes any difference. You're just getting a bool instead of an exception.. so what? The difference is in creating an API by which it makes it harder for the user to shoot themselves in the foot. Having a count and an indexer is just asking the user to make an incorrect assumption about the state of the list. My argument is that eliminating procedures/properties like this make it harder for the user to get into a bad situation. Note harder, not impossible. Short of immutable collections it's not possible to be completely safe. [Eduardo] Okey then, just create a new kind of list which is like the first one but shares the internal lock object with the user My next post goes into the ups and downs of this approachAnonymous
February 15, 2009
@wekempf: You say "anyone who says writing threaded code is easy, doesn't understand threading (or they are using a functional language... and event then...)" You are right, threading is difficult reading horrible threading books that just explain to write lines to console. I agree with you. I was trying to exploit multicore CPUs for many months now. It is really hard. However, if you follow my advice and read the code samples (if you don't want to buy a book), you can download its code. You'll see that this book is completely different from any other book about threading. That's why I do recommend it. Because, it made is possible for me (an average C# developer, not an expert), to understand threading!!! I must say that's nearly a miracle. You can enter here: http://www.packtpub.com/support Download the code and tell me if I am wrong :) You'll see, the examples are amazing. Neither the author nor the publisher pay me to promote "C# 2008 and 2005 threaded programming". Cheers, Erik GuerreroAnonymous
February 16, 2009
In my last post we discussed the problems with designing a safer API for mutable thread safe collectionsAnonymous
February 16, 2009
The comment has been removedAnonymous
February 17, 2009
@Erik Guerrero I just purchased the book...very good resource so far. @Wekempf I agree with a couple of your comments that if you think multithreading is easy, you don't understand multithreading. Furthermore, I agree if you want true collections that are thread-safe use a funcional language like F#. I think that there are some abstraction patterns (like the callback, backgroundthreadinvoker) make beginner multithreading easy (equivelant of drag and drop programming). I am by no means an expert...I do understand a bit more than that, but there is a lot more to go. I do think the Parallel Task library will help a lot of us out in .NET 4.0 and allow you to add parallelism in functional areas in your code (i.e. LINQ)Anonymous
February 18, 2009
The comment has been removedAnonymous
February 19, 2009
in order to make a class thread safe,i think we have to make the lock object static and methods too.Did u forget to put static ?.Otherwise other thread will get a different lock object. Please correct me if i am wrong.Anonymous
February 23, 2009
SharePoint SharePoint Wiki: Create pages based on a template Archiving and intercepting large files withAnonymous
February 25, 2009
The comment has been removedAnonymous
March 10, 2009
The comment has been removedAnonymous
March 15, 2009
Why do you lock on m_lock instead of m_list directly?Anonymous
March 16, 2009
The comment has been removedAnonymous
March 31, 2009
If the index for TryGet() is an ordinal 32-bit integer, it's unclear what semantics it could have that wouldn't be rendered meaningless by the possibility of items being deleted asynchronously. On the other hand, it's not uncommon to have a situation where data may be put into a collection by multiple threads and yet only removed by one; in such a situation, the one thread which is removing items might be able to safely use "decision" procedures if it alone would be able to invalidate the result (e.g. if the thread determines that list.Count is 20, it may be able to safely process the first 20 items). Further, I'm not quite clear why it wouldn't be useful to have an iEnumerable object which would allow insertions or deletions, with the promises that: (1) Every item that existed throughout the lifetime of the enumeration, without change to the key, would be included exactly once. (2) No item would be included in the enumeration that did not exist at any time within its lifetime. (3) Items that exist for part of the enumerator's lifetime may be included zero or one times. For purposes of this rule, changing an item's key would be regarded as creating a new item and deleting the old one, so an existing enumeration may legitimately return the old value, new value, both, or neither. (3) All items that are returned will be given in a valid sequence, though not necessarily the same sequence as would have occurred in the absence of insertions and deletions. (4) It should be possible to determine, e.g. using a 64-bit update counter, whether anything has happened to a collection since a time just before an enumeration began. Some data structures would have difficulty dealing with such constraints, but others would not. Such behavior would seem more useful than always invalidating enumerators on any list change.