Many readers, one writer - is it possible to avoid locking?

Question

Say you have an in-memory list of strings, and a multi-threaded system, with many readers but just one writer thread.

In general, is it possible to implement this kind of system in C#, without using a lock? Would the implementation make any assumptions about how the threads interact (or place restrictions on what they can do, when)?

Answer 1

Yes. The trick is to make sure the list remains immutable. The writer will snapshot the main collection, modify the snapshot, and then publish the snapshot to the variable holding the reference to the main collection. The following example demonstrates this.

public class Example
{
  // This is the immutable master collection.
  volatile List<string> collection = new List<string>();

  void Writer()
  {
    var copy = new List<string>(collection); // Snapshot the collection.
    copy.Add("hello world"); // Modify the snapshot.
    collection = copy; // Publish the snapshot.
  }

  void Reader()
  {
    List<string> local = collection; // Acquire a local reference for safe reading.
    if (local.Count > 0)
    {
      DoSomething(local[0]);
    }
  }
}

There are a couple of caveats with this approach.

• It only works because there is a single writer.
• Writes are O(n) operations.
• Different readers may be using different version of the list simultaneously.
• This is a fairly dangerous trick. There are very specific reasons why volatile was used, why a local reference is acquired on the reader side, etc. If you do not understand these reasons then do not use the pattern. There is too much that can go wrong.
• The notion that this is thread-safe is semantic. No, it will not throw exceptions, blow up, or tear a whole in spacetime. But, there are other ways in which this pattern can cause problems. Know what the limitations are. This is not a miracle cure for every situation.

Because of the above constraints the scenarios where this would benefit you are quite limited. The biggest problem is that writes require a full copy first so they may be slow. But, if the writes are infrequent then this might be tolerable.

I describe more patterns in my answer here as well including one that is safe for multiple writers.

Answer 2

That is a fairly common request for a threading library to fulfill - that sort of lock is generally just called a "reader-writer lock", or some variation on that theme. I haven't ever needed to use the C# implementation specifically, but there is one: http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx

Of course, you run into the issue that if readers will always be reading, you'll never be able to get the writer in to write. You'll have to handle that yourself, I believe.

(Ok, so it's still technically a "lock", but it's not the C# "lock" construct, it's a more sophisticated object specifically designed for the purpose stated in the question. So I guess whether it's a correct answer depends somewhat on semantics and on why he was asking the question.)

Answer 3

To avoid locks, you might want to consider Microsoft's concurrent collections. These collections provide thread safe access to collections of objects in both ordered and unordered forms. They use some neat tricks to avoid locking internally in as many instances as possible.

Answer 4

You can also use Microsoft's new Immutable Collections library: http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx

Note: this is completely separate from the Concurrent Collections.

Answer 5

A singly-linked-list approach can be used without locks provided the writer only inserts/deletes at either the head or the tail. In either case, if you construct the new node beforehand, you only need a single atomic operation (head = newHead; or tail.next = newTail) to make the operation visible to the readers.

In terms of performance, insertions and deletions are O(1), while length calculation is O(n).