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.