使用不可变/持久类型和数据结构的并发是如何工作的？

Question

我最近读了很多关于函数式语言的文章.由于那些只使用不可变结构,因此他们声称并发问题得到了极大改善/解决.我在理解如何在真实环境中实现这一点时遇到了一些麻烦.让我们假设我们有一个网络服务器,其中一个线程正在监听端口(好吧,IO是另一件我难以绕过头脑的东西,但现在让我们忽略它); 在任何连接尝试中,创建套接字并将其传递给新创建的线程,该线程对其进行一些操作,并且根据接收的通信,可以将更改应用于对服务器应用程序是全局的大列表/数据结构.那么,这个列表访问如何工作,以便所有线程具有一致的列表视图(或者至少为了在线程以正确的方式死亡时将一个线程所做的所有更改应用于列表) ？

我的理解问题是:

• 显然,任何线程都可以获得列表的不可更改的"快照".但是,在通过创建应用了更改的列表的新版本来"更改"内容之后,我们仍然留下每个线程都有自己的列表版本.这些如何合并在一起？
• 另一种方法可能包括使用传统的锁定机制,如互斥/ cond或go-like-channels.但是,当所有变量都是不可变的时候,你甚至会怎样创建这样的东西？
• 我听说过STM,但不能处理副作用(即列表是否也会透明地将数据备份到文件或db)

那么你如何用函数式语言模拟这样的东西呢？

Answer 1

不可变值有几个适合它们的应用程序.并发/并行处理只是其中之一,最近变得更加重要.以下是经验中最基本的摘要以及关于该主题的许多书籍和谈话.您最终可能需要深入了解一些.

你在这里展示的主要例子是关于管理全局状态,所以它不能完全"不可变"地完成.但是,即使在这里,也有很好的理由使用不可变数据结构.其中一些来自我的头脑:

• try - catch表现得更好,因为你不修改可能被中途修改的共享对象,使用不可变值,它会自动保持最后的一致状态
• 在非常有限的全局变量集(最好是一个)上将更改状态减少到多核安全的"比较和交换"操作,完全消除了死锁
• 数据结构的自由传递,没有任何防御性复制,这在被遗忘时经常出现神秘错误(在调用函数和被调用函数中都会创建很多次防御性副本,因为经过几次调试后开发人员开始倾向于"比对不起更安全"会议)
• 更简单的单元测试,因为在不可变值上运行的许多函数都是无副作用的
• 通常更容易的序列化和更透明的比较语义更容易调试和记录(记录)系统状态的当前快照,甚至异步

回到你的问题.

在最简单的情况下,在这种情况下,全局状态通常使用顶部保持不可变数据结构的一个可变引用来建模.

该引用仅由CAS原子操作更新.

不可变数据结构由副作用自由函数转换,并且当完成所有转换时,引用以原子方式交换.

如果两个线程/核心想要同时交换从同一个旧值获得的新值,那么首先获胜的另一个不会成功(CAS语义)并且需要重复操作(取决于转换,要么更新当前的一个)使用新值,或从头开始转换新值).这可能看起来很浪费,但这里假设重做一些工作通常比永久锁定/同步开销更便宜.

当然,这可以通过例如对不可变数据结构的独立部分进行分区来优化,以通过使多个引用独立地更新来进一步减少潜在的冲突.

对数据结构的访问是无锁且非常快速的,并始终提供一致的响应.边缘情况,例如当您发送更新而另一个客户端之后接收到较旧的数据时,在任何系统中都会出现这种情况,因为网络请求也会出现故障......

STM非常有用,通常您最好使用包含来自STM事务中使用的引用的所有值的数据结构的原子交换.