不可变数据结构与并发性。

Question

我正在尝试理解如何在并发编程中使用不可变数据结构可以避免需要锁定。我在网上看了一些文章，但还没有看到任何具体的例子。

例如，假设我们有一些代码（C＃），在 Dictionary< string，object>周围使用锁定(s)来执行以下操作：

class Cache
{
    private readonly Dictionary<string, object> _cache = new Dictionary<string, object>();
    private readonly object _lock = new object();

    object Get(string key, Func<object> expensiveFn)
    {
        if (!_cache.ContainsKey("key"))
        {
            lock (_lock)
            {
                if (!_cache.ContainsKey("key"))
                    _cache["key"] = expensiveFn();
            }
        }
        return _cache["key"];
    }
}

如果_cache是不可变的，那会是什么样子呢？是否可以删除lock并确保expensiveFn不会被调用多次？

- Ben

---

为什么你不直接使用ConcurrentDictionary呢？ - Servy

那样做如何防止 expensiveFn 被调用两次？ - Ben

因为 ConcurrentDictionary 已经有一个方法可以完全替代你的 Dictionary 方法，而且它是由微软高效调优的，并且具有支持更有效的多线程访问的底层存储结构。 - Servy

我正在尝试理解如何使用不可变数据结构简化并发编程并消除锁的需求。不确定ConcurrentDictionary如何帮助实现这一点。 - Ben

@Servy，我认为他的观点是这段代码并不是解决实际问题的一部分，他只是试图理解使用不可变数据结构如何改变并发处理的理论。使用ConcurrentDictionary是解决实际问题的完全有效的解决方案，但它并不能帮助他理解这个特定问题。 - EJoshuaS - Stand with Ukraine

Answer 1

短暂回答是，至少不完全如此。

不可变性仅保证另一个线程在您使用数据结构时无法修改其内容。一旦您拥有实例，该实例就永远无法被修改，因此您始终可以安全地读取它。任何编辑都需要复制实例，但这些副本不会直接干扰已引用的任何实例。

即使使用不可变对象，多线程应用程序仍然需要锁定和同步构造。它们主要涉及与时间相关的问题，例如竞争条件或控制线程流以便在正确时间发生活动。不可变对象对于解决这些问题并没有真正帮助。

不可变性使多线程更容易，但并不容易。

---

关于不可变字典的问题，我必须说，在大多数情况下，甚至在您的例子中，使用不可变字典并没有太多意义。因为它被用作“活动”对象，随着添加和删除项目而固有地发生变化。即使是针对不可变性设计的语言，如F＃，也有可变对象用于此目的。更多详情请参见此链接。不可变版本可以在此处找到。

- Bradley Uffner

---

确实，不可变数据结构并不能完全消除对锁的需求。但我想补充一点，有时候不可变性可以让你用原子操作（例如CAS操作，详见Compare-and-swap和Interlocked.CompareExchange）来替代锁。微软的不可变集合中包含一个ImmutableInterlocked类，该类提供了一些看似“修改”不可变列表、集合、字典等的操作，实际上使用了CAS操作。 - David Schwartz

Answer 2

不可变数据结构的基本思想是减少（注意我说的是“减少”，而不是“消除”）并发中锁定的需要，因为每个线程都在本地副本或不可变数据结构上工作，所以没有锁定的必要（没有线程可以修改任何其他线程的数据，只能修改自己的数据）。只有当多个线程可以同时修改相同的可变状态时才需要锁定，否则可能会出现“脏读”和其他类似问题。

- EJoshuaS - Stand with Ukraine

---

这并不完全正确，每个线程都有自己的副本并非事实。事实上，你可以保证每个人使用的共享副本永远不会被修改，如果有人想要修改它，他们需要创建一个新对象，而不再使用共享副本。 - Scott Chamberlain

好的，这更加精确。我已经相应地编辑了我的帖子。 - EJoshuaS - Stand with Ukraine

Answer 3

一项说明为何不可变数据很重要的例子是：假设您有一个人物对象，由两个不同的线程访问。如果线程1将该人物保存到映射中（该人物哈希包含人物名称），那么另一个线程2更改了人物名称。现在，当线程1在地图中查找该人物时，将无法找到该人物，而它实际上确实存在！

如果人物是不可变的，则由不同线程持有的引用将是不同的，即使用户2更改了其名称（因为将创建人类的新实例），线程1也能在地图中找到该人物。

- mrida