关于并行:关于并发和并行Go和Erlang之父都弄错了

作者|Yossi.Kreinin
起源|OSChina 网站
翻译|Andy、袁不语、YuanyuanL、姜鹏飞
校对|胡燕君（OneFlow）

依据字面词义，并发（concurrent）是指竞争或反抗，而并行（parallelism）指两条直线永不相交的状态。在计算机中的并行和并发问题上，我与 Joe Armstrong（译注：Erlang 语言发明者）和 Rob Pike（译注：Go 语言发明者）这俩人的认识并不统一。

上面我以自动售货机和分礼物为例来阐明我的观点。

首先，并行和并发都是十分风行的概念，很多编程语言和工具通常都会重点宣传本人“兼具高度并行性和高度并发性”。但我却认为，并行和并发须要的是不同的工具，而对单个工具来说，并行和并发不可兼得。例如：

• Erlang、Rust、Go 和 STM Haskell 善于并发解决
• Flow、Cilk、checkedthreads 和 Haskell 偏重并行处理

也有像 Haskell 这样的语言或零碎，既能解决并行，也能解决并发，但在 Haskell 外部，并行和并发分属两套不同的工具集。而且 Haskell 的官网 wiki（
http://www.haskell.org/haskel…）也解释了两者的应用准则，如果谋求并行，那么不应该应用并发工具：

经验总结：优先应用纯并行，而后再思考并发。

Haskell 早就意识到一个工具难以同时解决这两个问题。专门针对并行环境设计的新编程语言 ParaSail，也面临同样的难处，尽管它也兼备针对并行和并发的工具集，但它也倡议在并行、非并发程序中尽量不要应用并发性能。

这就与很多人的观点天壤之别了，尤其是一些并发性能的铁粉，他们认为本人的并发工具解决起并行任务时也能熟能生巧。Rob Pike 就说，因为 Go 是一种并发性语言，所以它也很适宜并行（http://talks.golang.org/2012/…）。

并发使得并行变得更容易（进步可扩展性等）。

同样，Joe Armstrong 也是这么说 Erlang 语言的。他甚至还说：当初还想用非并发的思维去解决并行的问题是缘木求鱼。

到底是什么起因导致这种一致，为什么 Haskell 和 ParaSail 的开发者认为并发和并行要用不同的工具，而 Go 和 Erlang 的开发者却认为并行语言也能解决并发呢？

我感觉这是因为大家要解决的问题不同，对并行和并发的区别有不同了解，才导致最终论断不同。Joe Armstrong 已经画过一张图来解释两者的区别，经自己的灵魂画手还原如下：

尽管并发在很多时候只波及繁多队列，但我还是依照 Joe Armstrong 的原图画了 2 个队列。从图中咱们能够看出：

• “并行”意味着可乐散发速度更快；
• 从部分来看，“并行”实质上还是并发问题；
• 先排队者先失去可乐；
• 谁先拿到可乐都没关系，反正最终每个人都会拿到；
• 当然，如果自动售货机里的可乐中途卖完了，前面的人就会拿不到——那也是没有方法，人生就是这样。

以上是用自动售货机举例，如果换一个比喻，假如是给一群孩子散发礼物呢，这两种类比之间有实质性区别吗？

有区别。自动售货机是一个事件处理零碎：人们不定时地到来，并且从机器中取不定数量的可乐。而分礼物是一个计算零碎：你晓得每个孩子想要什么，你晓得你买了什么礼物，并且你要决定哪个礼物分给哪个孩子。

在分礼物的场景中，“并发”与“并行”有不同的意义：

从下面的例子中，能够看出“并行”和“并发”有如下区别：

• 和自动售货机一样，“并发”也遵循“先到先得”的规定；
• “并行”则不一样：礼物已有标签，每个孩子拿到什么都是确定的；
• “并发”必须靠队列来维持秩序，防止两个孩子同时抢一个礼物——就像零碎要避免多个工作争先访问共享的数据，防止零碎瘫痪一样；
• “并行”模式下，就不须要队列了，不论谁先谁后，每个人都会拿到属于本人的礼物。

在俄语中，“concurrent（并发，读作 kon-koo-rent）”和“competitor（竞争对手）”是同义词。这种含意正好符合了分礼物中的“并发”情景的竞争属性：每个人都心愿本人最早到，这样就能挑到最好的礼物。

但“并行”场景则不同，每个礼物盒都写上了对应小朋友的名字。在逻辑上，孩子和礼物之间一一对应，互不穿插，互不烦扰。（但为什么我在图中画的连线却相交呢？一会儿我会解释这个问题。咱们能够先这么想：每个孩子奔向本人的礼物时路线会有相交，就像不同处理器寻找本人想要的数据时门路会相撞，但这并不影响到谁最终拿到什么礼物。）

1

计算和事件处理

咱们能够联想电话客服、Web 服务器、银行柜台等利用场景，它们和自动售货机是相似的事件处理零碎，都要解决并发工作，都必须解决不可预知的申请带来的不可避免的抵触。并行设计能够在肯定水平上进步处理速度，但其问题的本源还是在于并发中的抵触。

而在计算零碎中，例如分礼物、图形处理、计算机视觉、科学计算等中，则不会呈现并发抵触。输出是确定的，只需依据输出进行计算，而后输入，不会有意外烦扰。这时，并行的办法能够进步计算速度，但也容易呈现 bug。

接下来咱们将持续探讨计算零碎和事件处理零碎的差异。

2

确定性：现实 VS 妄想

在计算零碎中，咱们须要更多的确定性，因为这能够使编程人员轻松很多 —- 如果程序的输入后果是可确定的，那咱们就能够释怀地去测试优化或者重构代码，只有输入后果没变，就阐明咱们没做错。

而且这种确定性要求的只是一种大略的确定，并不需要 100% 雷同 —- 例如，在计算机视觉训练中，你并不要求机器每次找到的 100 张图片都是同一组，只有下面都有小猫就行；你也不要求机器每次都求出截然不同的圆周率近似值，只有它是在 3 和 4 之间就能够了。

在计算零碎中，领有确定性是现实状况，而且是能够达到的。

然而在事件处理零碎中，一切都是不确定的。如果事件产生程序不同，产生的后果也不同。譬如，如果我比你来得早，那罐仅剩的可乐就是我的；如果咱俩的银行联名账户只剩一块钱，而我的取款操作比你晚了 0.001 秒，钱就会打给你。

但如果再给我一次机会，那么钱属谁手就不肯定了。这就是事件处理零碎的不确定性。同样的程序运行屡次，后果能够背道而驰。而所有可能的后果数将随抵触的数量指数式增长。还有比这更让人头疼的事吗？

3

如何判断并行平安：确定性 VS 正确性

当程序以不同的程序处理事件时，你怎么确定其中没有 bug？

在计算零碎中，只有你每次运行程序都能失去雷同的后果，即便是谬误的后果，你也能够根本判定程序是并行平安的。就像运行一个搜寻小猫的程序，你每次都搜出了同一种类的小狗，那阐明你的程序有问题，然而不存在并行方面的问题。

然而在事件处理零碎中，状况就简单了一些，只有当零碎每次都能失去正确的后果，你能力确定零碎是并行平安的。

比方程序要模仿两个人同时取钱，不可能要求每次都是同一个人取到最初的一块钱，那如何判断这个程序没有 bug？咱们只能从侧面来看，例如账户有没有呈现的负余额，会不会间断两次取空一个账户，会不会凭空减少账户金额等等。如果上述这些异常情况都没有产生，你就能够认为你的模拟程序没有问题。

对电话服务来说也是这样，你须要先定义出一系列“正确的后果”，而后用这些“正确的后果”验证你的电话服务是否失常。

但很遗憾，如果一个零碎的后果不能体现时序相干的问题，那你就无奈晓得零碎的时序有没有 bug。这也是个头疼的问题。

4

并行谬误：易定位 VS 难定义

对于标好名字的礼物来说，如果呈现并行谬误，是很容易发现的 – 即便礼物上的名字是用外语写的，孩子看不懂，这都没关系，为什么？请看下图：

所以对并行零碎来说，零碎不意识这些“标记”没关系，只有有标记就行。如果发现两个孩子抢夺同一份礼物，就能够找意识标记的人来解决抵触。

这就如同一个自动化的测试工具，不须要晓得哪个工作别离拜访什么数据，只有晓得一个工作不能拜访被别的工作批改过的数据就行了。如果产生了这种抵触拜访，那就当做 bug 报告给程序员来解决。

这样的工具当初曾经有很多了，Cilk 语言有，Checkedthreads 也带有一个基于 Valgrind 的相似工具。(注：Checkedthreads，一个 C ++ 并行框架https://github.com/yosefk/che…；Valgrind，一套反对动态分析的工具http://valgrind.org）

但 Haskell 不必这么干，因为首先它不存在副作用（side effect），这就保障了并行处理不会呈现抵触。但即使没有这种动态保障，Haskell 的动静冲突检测机制也能防止抵触。

造成的意外后果就是，在计算零碎中，你不须要精确标记出 bug 所在，也不须要指出 bug 导致的问题是什么。

而在事件处理零碎中，必须有一个常识丰盛、责任感强的“小孩儿”来掌控全局，维持秩序。

此外，事件处理零碎还隐含了一个通用的规定：他人正在解决的过程，你就不能插手了，必须乖乖地在队列里等待。在“分礼物”场景中，“小孩儿”的存在能够保障这条规定失去恪守，让分礼物的工作更顺利，但还是难以避免其余可能的抵触。

在上图中，小孩 A 中途来到，回来后没有通过排队就接触礼物，违反规定，于是被零碎检测为 bug，小孩儿呈现，重整秩序。

但纵观全程，小孩 A 先拆开了礼物，但又中途来到队列，回来后发现礼物被前面的小孩 B 领了——这种后果合乎零碎的要求吗？一方面，小孩 B 没有插队，也没有阻挡小孩 A 领礼物，并未违反零碎规定；但另一方面，小孩 B 领到本属于小孩 A 的礼物，这并不合乎零碎的预设。

上述情况体现在具体代码中是这样的：以下是一个谬误的汇款操作，能够轻易被主动调试工具检测出“有 bug”：

src.balance -= amount
dst.balance += amount

此处没有任何同步操作。src.balance 可能被两个过程同时批改，导致其中的一次批改是有效的。好在，Helgrind 等数据争用检测工具能够通过监控内存拜访发现这样的同步问题，Cilk 和 checkedthreads 外部也有类似的工具。

但下列代码中的 bug，上述工具可能就检测不进去了：

atomic {src.balance -= amount} 
atomic {dst.balance += amount}

下面代码中的“atomic”示意原子操作，意思是对账户余额的批改必须顺次进行。这样一来，检测工具就能够少操些心了——但这样就意味着没有 bug 了？

实际上，一个过程从 src.balance 里拨出一笔钱之后，转入 dst.balance 之前，可能因为某种原因被暂停，从而进入临时失落（temporarily lost）状态，那么逻辑上这笔钱就“临时失踪”了。这样算不算一个 bug？我不太理解银行业务，无奈判断，预计 Helgrind 也不能。

上面是一个谬误更显著的代码：

if src.balance - amount > 0: 
atomic {src.balance -= amount} 
atomic {dst.balance += amount}

在下面的程序中，一个过程会先查看原始账户 src.balance 里有没有足够的余额可供转账，查看结束，长期有事又先挂起了，这时另外一个过程达到了，也执行了同样的检测，发现没问题，而后就把钱转走了。而后第一个过程复原了，进入队列期待执行转账操作。问题就呈现了 —- 等轮到它的时候，账户里的钱曾经被转空了。

就像小孩 A 回来的时候发现自己的 iPhone 竟然在小孩 B 手里。这是一种竞态条件（race condition），而不是数据竞争（data race），因为每个人都在文化排队，但 bug 还是产生了。

什么是竞态条件？这和具体的利用无关，显然，上述的第三段代码有问题，但我不能确定第二段代码是否有问题，因为我不理解银行业务。如果咱们不理解程序要做什么，就无奈精确定义这个利用中的“竞态条件”，更不能指望一些自动化工具能够检测到了。

当然，你也能够避开竞态条件，只有把整个转账操作原子化即可，所有的并发办法都能让你做到这一点。

与空指针异样不同，竞态条件带来的问题没那么容易被发现。如果程序的输入后果具备不确定性，那么当你给程序提供有问题的输出，就可能只有千万分之一的概率会产生 bug，因而程序每次的输入后果都不同。而如果是输入后果能够确定的程序，状况就会好很多，每一次给它提供有问题的输出，bug 都会产生，主动调试工具也都能检测出 bug 来。

但很惋惜，事件处理零碎并不是输入后果可确定的零碎。这又是让人头疼的中央!

5

两种队列：实现细节 VS 局部接口

对于有标签的礼物，不须要排队，每个人都能够间接找到本人的礼物。或者并非如此，设想一下，如果是数千个孩子同时去找礼物会是什么境况？这时如果不排队，必定会乱成一团糟。所以这种状况下，咱们也须要排成一个或几个队列，但这里的排队形式的抉择只会在效率上有所不同，并不会影响孩子最终拿到手的礼物。

这就是在我下面的图中每个孩子和礼物的连线有穿插的起因。这些连线在逻辑上是并行的，尽管看似有穿插，然而不会产生理论抵触。(为了提供精确的解释，我对喻体的抉择和插图的表白都十分审慎。）

当四个不同的处理器通过雷同的内存总线去拜访互不相干的数据时，“逻辑上的平行在技术上穿插”，实际上，这些处理器必须在硬件层面上排队，能力顺利完成拜访。同样，如果有 1000 个逻辑上独立的过程通过负载调度器调配到 4 个处理器上时，这些过程也须要排队等待被调配。

即使在一个无抵触的并行零碎中，也会有大量的队列在运行，但它们只是操作层面的队列，不会影响最终后果。无论哪个过程在哪个队列，地位靠不靠前，程序的最终运行后果都是一样的。如下图所示：

与之相同，在并发零碎中，队列贯通零碎开始和完结的两端，例如：

• 一个信号量（semaphore）会对应一个期待锁定它的队列，谁在后面谁就能先锁定这个信号量；
• Erlang 的过程会有一个音讯队列，谁先收回音讯谁就会先影响到后果；
• Go 中的 goroutine（协程）会监听一个通道，数据写入的程序会影响执行的后果；
• 在事务内存的模型下，提交事务失败的过程都要进入队列；
• 在无锁容器内，更新失败的过程也要进入队列。

在事件处理零碎中，队列或简略或简单，但队列的程序始终会影响最终的执行后果。这种影响可能会带来问题，也可能不会——这取决于零碎的目标。

在并行的无抵触计算零碎中，队列执行程序不会影响后果，不过你须要工具来验证这个零碎的确是无抵触的。

Rob Pike 曾做过一个演示，展现了用 Go 语言构建负载均衡器有如许不便，那确实很弱小也很易用。Go 语言就是为并发环境设计的，并发就意味着排队，排队就会带来负载平衡的问题。当然，这并不是说别的语言里构建负载平衡就有多难，只是强调在有并发个性的语言里显得特地容易而已。

但这只是并行故事的一部分，接下来你想要的是无抵触的动态保障（static guarantees）或动静查看，Go 语言也确实能够做到这一点。计算零碎不能没有动态保障或动静查看，但当你真正在计算零碎下工作时，你就会发现，计算零碎所须要的动态保障和动静查看是一组不同于 goroutines 和通道的接口和工具，只管这些性能底层也是用 goroutines 和通道实现的。

6

抢占式过程的重要性

因而，计算零碎所须要的抵触预防和检测，并发工具并没有提供。那有没有并发工具提供，但计算零碎不须要的个性呢？

有，比方显式的队列（即程序会影响后果的队列），不仅不须要，而且它会成为计算零碎的阻碍。因为咱们晓得，计算零碎中队列会导致竞态条件而非数据竞争，而且你没法精确定位抵触地位。

另一个计算型零碎不须要的个性就是低成本的抢占式过程 / 线程。

对于事件处理零碎，你心愿尽可能快地解决大量不同的事件，这里就会呈现很多抢占式过程，你心愿在 10000 个过程在运行时，还能够立刻应答第 10001 个过程产生的事件。这种状况必须要有十分低成本的抢占式过程，否则无奈工作。

对于计算零碎，能够用低成本的工作来映射到绝对高老本的 OS 线程——但工作没有线程那么弱小。你不能通过事件来激活工作，工作只能在队列中等着，当工作线程闲暇时才会用来运行它们。不像 goroutines 或相似的情景，你不能让超过操作系统线程数量的工作同时处于运行状态——你也不须要这么做。

比起通过成熟的低成本过程、goroutines 等其余形式，用比拟传统的运行时（runtime）能够很好地实现工作。当然，在我看来这须要在底层运行时零碎中做更多的工作。

能够看出，以并发为指标的平台一方面对计算零碎的服务有余，提供不了它须要的性能，一方面却又服务适度，提供了不少它不须要的个性。

(偏心地说，在计算零碎中通过抢占来获取优先级在实践上是可行的——换句话说，如果它让新创建的工作（属于要害门路的一部分）抢占正在运行中的工作（不是要害门路的一部分），就能够进步吞吐量。然而，在我漫长且令人丧气的经验中，要让调度器晓得要害门路是什么，这只是实践上可行，实际上很难做到。一个愚昧的、贪心的调度器对抢占没什么用途。)

7

同类工具的不同

针对并发性事件处理零碎的工具并不都是一样的，针对并行性计算零碎的工具也如此。尽管它们都是同一类工具，但有实质性的区别。

• Erlang 齐全不容许过程共享内存。这意味着不存在数据竞争，这并不会特地感动我，因为数据竞争能够很容易被自动检测工具发现，而不容许过程共享内存却不能打消竞态条件。但好的一面是，你能够无缝扩大到多个节点，而不仅仅是扩大到同一个芯片上的多个核。
• Rust 不容许共享内存，除非它是不可扭转的。没有简略的多节点扩大，然而在单节点上有更好的性能，不须要数据竞争检测，可能会因为测试覆盖率不高导致呈现竞争检测漏报（理论并不齐全是这样，Rust 也宣称有打算引入并行工具）。
• Go 容许共享任何货色。我认为，它在验证累赘可承受的范畴内做出了最优的性能。Go 有一个数据竞争检测器，无论如何，竞态条件在事件处理零碎中还是会产生。
• STM Haskell 容许自在地共享不可扭转的数据，以及在显式要求时也能够共享可变数据。它也提供了事务内存接口，这是一个很酷的货色，有时候很难用其它办法模仿。Haskell 也有其它的并发工具——有通道，如果你想要 Erlang 式的多节点可扩展性，显然 Cloud Haskell 是个不错的抉择。

当然，最大的区别是你得别离用 Erlang、Rust、Go 和 Haskell 写代码。当初看看计算零碎：

• Parallel Haskell 仅仅并行纯代码。这是一种没有并行 bug 的动态保障，但却以没有副作用为代价。
• ParaSail 有副作用，然而不容许呈现指针等，因而，只有当不共享可变数据时，它才会并行计算（例如，如果编译器确信两个数组片不重叠，则能够并行处理这两个数组片）。与 Haskell 相似，ParaSail 也有一些并发反对——也就是能够被共享和可变的“并发对象”——而且 ParaSail 的文档强调了在你仅仅须要并行时不应用并发工具的益处。
• Flow 依赖纯功能性外围，这进一步限度了让编译器充沛了解程序中的数据流，容许它对准 Hadoop 和 CUDA 等指标平台。语法上看起来像是副作用，并行规约（parallel reduction）等被认为是外围上的一层糖衣。我抵赖我不能齐全了解它的产品宣言（“如果一个态射（morphism）是满射（surjective）和内射（injective），那么它是一个双射（bijection），因而它是可逆的”这对咱们再显著不过）
• Cilk 是加上了并行循环和函数调用的 C 语言。它容许你共享可变数据，搬石头砸本人的脚，但如果那些 bug 产生在你的测试输出中，它有工具能够确定性地找到那些 bug。当你不搬石头砸本人的脚时，应用不受禁止的共享可变数据就很有用——当并行循环计算工作部分基于副作用优化的事物，而后循环完结，大家都能够应用这些事物时。像孩子关上他们的乐高积木，它们一起去构建和玩乐高。
• Checkedthreads 很像 Cilk；它不依赖语言扩大，整个都是收费和凋谢的——不仅是接口和运行时，bug 查找工具也是。

Checkedthreads 是我写的，它在支流语言 C 和 C ++ 中是可移植的、自在的、平安的和可用的，不像很多零碎须要新语言或者语言扩大。

人们想要用 C ++1y 或者其它相似的标准标准化 Cilk，然而 Cilk 想要增加关键字，而 C ++ 开发者不想增加关键字。Cilk 在 GCC 和 LLVM 的分支是可用的，但它不能在所有平台运行（它扩大了 ABI），而且它没有合并回主线。有些新的 Cilk 个性被申请专利了，并不是全部都是自在可用的。

但 Cilk 领有一个微小劣势——它有 Intel 的反对，然而 Checkedthreads 只有鄙人反对。如果你读了 Checkedthreads 相干的博客后，认为 Cilk 更适宜你，决定应用它，那我也算是实现我的另一个指标了，那就是为自动化调试并行程序工具博得更多它应得的关注。

不是所有的并发工具都是一样的，不同的并行工具也不同——我甚至没有在我的例子中指出最大的不同。不过它们毕竟是两个不同类别，而咱们首要事件就是抉择正确的类别。

8

总结

咱们曾经探讨了并行的计算零碎和并发的事件处理零碎的不同点，包含：

• 确定性：现实 VS 妄想
• 如何判断并行平安：确定性 VS 正确性
• 并行谬误：易定位 VS 难定义
• 队列：实现细节 VS 局部接口
• 抢占：简直没用 VS 必不可少

对于事件处理零碎，并发是实质，并行是局部解决方案 ——通常来说是好的解决方案（两个自动售货机比一个好）。 对于计算零碎，并行是实质，并发是局部解决方案——通常来说是不好的解决方案（一堆混淆的礼物通常比贴了标签的礼物蹩脚）。

通过总结“并行 / 并发”和“计算 / 事件处理”，我心愿能够表述得更清晰。我也心愿没有给事件处理零碎抹太多黑——可能有一些我不晓得的主动验证策略。我并不保障我的观点和术语应用是正确的。

有人对事件处理零碎更感兴趣，他们的观点很有价值——“并发是一次解决（dealing with）几件事件，并行是一次做（doing）几件事件”。从这个角度，并行是实现细节，并发是程序的构造。

我置信我的观点也有价值——也就是说，“并发解决的是不可避免的与工夫相干的抵触，并行则防止不必要的抵触。”——“自动售货机 vs 贴了标签的礼物”。两者的逻辑看起来就像这样：

最重要的是，绝对于事件处理零碎的代码，计算零碎的代码能够通过应用主动调试工具和动态保障相当容易地做到简直没有 bug。

应用本人的工具解决并行不是什么新鲜事儿。Rob Pike 在 Sawzall 上的工作早于在并发语言 Go 上的工作，Sawzall 是一个专门的并行语言，它的代码能够做到总是没有并行 bug。

即便如此，当初并发工具的声量要比并行工具嘹亮——并发工具能够解决并行，只管成果绝对比拟差。“雷声大雨点小”的并发工具往往让咱们疏忽了“低调却有料”的并行工具，心愿大家能给予后者同样的关注。

Armstrong 说，“并行化串行代码是在解决谬误的问题。”对此，我的回应是，“为计算零碎的代码应用‘裸’并发工具就是在解决谬误的问题。”一个简略的事实是，用正确的工具进行并行化的 C 语言比 Erlang 更快、更平安。因而，咱们要“应用正确的工具”，而不是让任何人拿走你的“iPhone”。

（本文源自 OSChina 网站，该翻译工作遵循 CC 协定。原译文：https://www.oschina.net/trans…；原文：http://www.yosefk.com/blog/pa…）

欢送下载体验 OneFlow v0.7.0 最新版本：
https://github.com/Oneflow-In…