在私有领域中使用Bcl ImmutableDictionary

Question

假设我有一个将从多个线程调用的类,并且我将在此类的私有字段中将一些数据存储在ImmutableDictionary中

public class Something {
    private ImmutableDictionary<string,string> _dict;
    public Something() {
       _dict = ImmutableDictionary<string,string>.Empty;
    }

    public void Add(string key, string value) {

       if(!_dict.ContainsKey(key)) {
          _dict = _dict.Add(key,value);
       }
    }
}

这可以通过多个线程以这种方式调用,你会得到关于字典中已存在的密钥的错误吗？

Thread1检查字典看到false Thread2检查字典看到false Thread1添加值并引用_dict更新Thread2添加值,但它已经添加,因为它使用相同的引用？

Answer 1

在使用不可变字典时，您绝对可以是线程安全的。数据结构本身是完全线程安全的，但是您在多线程环境中对其应用更改时必须仔细编写，以避免在您自己的代码中丢失数据。

这是我经常在这种情况下使用的模式。它不需要锁，因为我们所做的唯一变化是单个内存分配。如果必须设置多个字段，则需要使用锁。

using System.Threading;

public class Something {
    private ImmutableDictionary<string, string> dict = ImmutableDictionary<string, string>.Empty;

    public void Add(string key, string value) {
       // It is important that the contents of this loop have no side-effects
       // since they can be repeated when a race condition is detected.
       do {
          var original = _dict;
          if (local.ContainsKey(key)) {
             return;
          }

          var changed = original.Add(key,value);
          // The while loop condition will try assigning the changed dictionary
          // back to the field. If it hasn't changed by another thread in the
          // meantime, we assign the field and break out of the loop. But if another
          // thread won the race (by changing the field while we were in an 
          // iteration of this loop), we'll loop and try again.
       } while (Interlocked.CompareExchange(ref this.dict, changed, original) != original);
    }
}

事实上，我经常使用这种模式，为此我定义了一个静态方法：

/// <summary>
/// Optimistically performs some value transformation based on some field and tries to apply it back to the field,
/// retrying as many times as necessary until no other thread is manipulating the same field.
/// </summary>
/// <typeparam name="T">The type of data.</typeparam>
/// <param name="hotLocation">The field that may be manipulated by multiple threads.</param>
/// <param name="applyChange">A function that receives the unchanged value and returns the changed value.</param>
public static bool ApplyChangeOptimistically<T>(ref T hotLocation, Func<T, T> applyChange) where T : class
{
    Requires.NotNull(applyChange, "applyChange");

    bool successful;
    do
    {
        Thread.MemoryBarrier();
        T oldValue = hotLocation;
        T newValue = applyChange(oldValue);
        if (Object.ReferenceEquals(oldValue, newValue))
        {
            // No change was actually required.
            return false;
        }

        T actualOldValue = Interlocked.CompareExchange<T>(ref hotLocation, newValue, oldValue);
        successful = Object.ReferenceEquals(oldValue, actualOldValue);
    }
    while (!successful);

    Thread.MemoryBarrier();
    return true;
}

然后您的 Add 方法变得更简单：

public class Something {
    private ImmutableDictionary<string, string> dict = ImmutableDictionary<string, string>.Empty;

    public void Add(string key, string value) {
       ApplyChangeOptimistically(
          ref this.dict,
          d => d.ContainsKey(key) ? d : d.Add(key, value));
    }
}

Answer 2

是的，与通常相同的竞争适用（两个线程都读取，什么也没找到，然后两个线程都写入）。线程安全不是数据结构的属性，而是整个系统的属性。

还有另一个问题：对不同键的并发写入只会丢失写入。

你需要的是一个ConcurrentDictionary. 如果没有额外的锁或 CAS 循环，您就无法使用不可变的来实现这一点。

更新：这些评论让我相信，ImmutableDictionary如果写入不频繁，那么与 CAS 循环一起使用进行写入实际上是一个非常好的主意。读取性能将非常好，并且写入性能与同步数据结构一样便宜。