作者 | David Giard 责编 | 夏萌

译者 | 弯月

并发编程之所以这么难，是因为人类大脑的局限性，还是问题本身的复杂性？

我参与过的许多规范项目都使用了并发或分布式系统。由于正确实现的难度过高，实现错误的代价过高，我们在编写规范上花费了大量的时间和金钱。由于并发与我的工作息息相关，因此我花费了大量时间思考并发的本质。

有一句老笑话说，并发是计算机科学中两大难题之一。因为并发有很多“偶然性”：很难测试、不可组合、错误可能长时间潜伏等等。但导致并发如此难的本质原因究竟是什么呢？是什么导致并发软件本质上比同步软件更难编写呢？

我经常听到的一个理由是，人类是线性思维，而不是并发，因此无法理解竞争条件。我不同意，根据我的经验，人类非常擅长并发推理。每次开车时，我们都在进行并发推理！

一些研究发现，通过框架将并发转化为人类术语，人们就能发现竞争条件。因此，虽然并发很难理解，但我认为并不是因为我们在这方面有欠缺。

在我看来，一个更重要的因素是状态空间爆炸。并发之所以难，是因为并发系统可处于许多不同的可能状态，而且状态数量的增长速度超过人们的预期。

行为、交错和不确定性

假设我们有很多代理{1、2、… n}，每个代理执行的操作都是线性序列。不同的代理可能有不同的算法。我们需要实现队列的写入、读取、计数器递增等操作。第一个进程完成p1个原子步骤，第二个完成p2个步骤，依此类推。代理严格按线性方式运行程序，但另一个进程可以在每个原子步骤后交错。假设我们使用了算法A1A2和B1B2，执行顺序为A1B1A2B2或A1B1B2A2，但不可以是A1B2B1A2。

根据这些条件，计算可能出现的执行（行为）顺序数量的方程式如下：

假设我们有3个代理，算法分2步，则行为的数量为：6!/8 = 90。序列中的每一步都可能导致一个不同的状态，因此最大不同状态数（MDS）：6*90=540。这其中任何一个都有可能是“错误”的状态。

在大多数情况下，实际状态空间将远小于最大不同状态数，因为不同的行为最终会得到相同的状态。然而，计算结果和状态空间的增长速度远远超过了我们的预期。3个代理，3个执行步骤，行为数量为1700种（15K MDS）；而4个代理，2个执行步骤，行为数量为2500种（20K MDS）。这还是所有行为都没有不确定性的情况！如果代理中的一个步骤可以执行3种操作之一（发送消息M₁、发送消息M₂、崩溃），具体执行哪一种为不确定，那么行为和MDS的数量就会增加三倍。

对于复杂的并发系统来说，拥有数百万或数千万个状态是非常常见的。即使是我的玩具模型也有大约800万个不同的状态（虽然经过改善可以减少一些）。我主要考虑状态空间的性能，因为状态空间越大，检查模型所需的时间就越长。但并发之所以难以理解，也是因为如此。如果我的理论MDS是两百万个状态，实际状态空间只有大约1%，而我的大脑可以理解剩下的99.9%的状态，那么仍将漏掉20个边缘情况。

缩小状态空间

我常用的一种启发式方法为：

降低并发难度的所有方法都应优先考虑管理状态空间。

虽然并非百分百正确（没有任何一种启发式方法是百分百正确的），正确率大约为60%，但这就足够了。状态空间增长迅速，空间越大，引发的问题就越多。如果我们想构建可维护的并发系统，首先要先缩小空间。

例如线程。线程共享内存，并且线程调度器有很大的自由度来挂起线程。因此，我们有很多步骤（一行代码一个步骤），任何交错都可能获得一个不同的状态。我们可以使用编程构造，比如互斥锁和障碍，“修剪”状态空间并给出我想要的行为，但考虑到状态空间的规模，我必须修剪掉很多状态，才能得到正确的行为。我的实现有可能出错，“扭曲”空间（例如添加死锁）或者没有注意到需要删除的错误状态。线程非常容易出错。

我会选择改为使用内存隔离的进程。调度器仍然可以安排交错，但进程不能干扰彼此的内部内存。在内部，进程的执行顺序仍为A1A2A3A4，但如果涉及外部资源（或进程间通信）的步骤只有A2和A4，那么我们只需要考虑A2A4如何影响状态空间。3个代理，4个步骤，共有35k种交错；3个步骤，2个步骤，则只有90种。这是一个很大的提升！

我们还能做些什么？低级原子指令可以在单个步骤中完成更多操作，因此没有交错的余地。数据库事务需要很多物理时间，但只表示一个逻辑时间步骤。数据变化会产生新的步骤，而不可变数据结构可以避免这种情况。

语言可以通过构造更好地修剪结果状态空间：go的通道、promise/future/async-await、nurseries等。我认为，我们可以将promise视为一种强制“非交错”的方式：等到做好准备再执行（或到达下一个暂停点）。

我认为，无冲突复制数据类型（CRDT）通过允许交错来减少状态空间，而且会进行重新排列，这样外部变化就是可交换的：A1B1和B1A1得到相同的最终结果，因此不会产生不同的状态。

再强调一次，这是非常粗略的启发式方法。

限制

简单来说，状态空间越小越好。但这种说法并没有考虑空间的拓扑结构：有些空间更为复杂。相较于无环空间，循环越多的空间越难处理。另外，不确定性的不同形式也很重要，以下两种形式，前者的行为更为复杂：“代理继续或重新开始”，“写入方发送消息M₁或M₂”。很多人遇到这两种情况，都会认为“人类不擅长理解并发”。通常，我们需要将状态简化为具有相同属性的“状态等价类”来处理并发，状态空间越复杂，需要处理的等价类就越多。

一些高级范式可以产生特定的状态空间拓扑结构，其中包含的交错更少或等价状态更多。我听说，有人声称fork-join和pipe-filter特别方便人类理解，我认为他们的意思是“不会产生复杂的状态空间”。也许事件循环也是如此？

还有一个限制是：有缺陷的状态与有缺陷的行为之间存在差异。有些行为完全可以通过安全状态，但可能引发“永远达不到一致性”之类的错误。这类错误被称为“活性bug”。

有关并发的哲学探讨就到这里。并发很难，即便你无法理解，也无需不要感到沮丧，这不是你的问题，而是一个组合学的问题。