并行趋势
免费午餐已经结束。尽管我们可以使用的 CPU 频率已经越来越高,以至于我们不少人称这是一个“CPU计算能力过剩的时代”。但是其实事实恰恰相反。CPU 性能提升在两年前就开始碰壁,但大多数人到了最近才有所觉察。大概在2003年初,一路高歌猛进的CPU时钟速度突然急刹车。受制于一些物理学问题,如散热(发热量太大且难以驱散)、功耗(太高)以及泄漏问题等,时钟速度的提升已经越来越难。从单个CPU角度来讲,摩尔定律已经不再适用了。
接下来数年里,新型芯片的性能提升将主要从三个方面入手,其中仅有一个沿袭是过去的:
1、超线程
2、多核
3、缓存
这些趋势看来归纳起来就一句话:并行趋势已经变得非常明朗,软件在历史性地向并发靠拢。
共享内存并行模型的宿命
随着多核趋势的明朗,对软件来说,这意味着一次巨变。多核时代,注定要改变计算机发展历史。在我们还在努力学习OO方法论时,须不知,一场新的颠覆性的编程革命到来了。
这场编程革命是什么呢?那就是“并行编程”。也许你会说,不就是“CreateThread和锁”吗,我已经会了。但这是完全不同的“并行编程”风格,我们可以称之为“无锁并行编程”,也可以称之为“基于异步消息传递的并行编程模型”。
在传统的并行模型中,我们通常的做法在线程之间共享内存,并基于“锁”技术来进行并发控制。这种编程模型,我们称之为“共享内存并行模型”。
核的增加导致一个结果,那就是基于传统锁机制实现的并行,产生线程竞争状态的概率越来越高。这就像在集群的机器数量到达一定数量后,机器发生宕机会成为常态一样,随着核的增加,线程锁冲突也将成为常态。而这使得本来可以并行执行线程因为锁的关系而实际在串行执行。为了改善这种情况,在“共享内存并行模型”中,有一个很流行的技术,称为“software transactional memory(事务内存)”。它本质上是一个乐观的锁,在多核下仍然存在性能瓶颈。我们看一组数据(来自:Lock Free Data Structures using STM in Haskell1):
数据的横坐标为:线程数/每线程的迭代次数,纵坐标为:平均每线程的执行时间。深蓝色/粉红色线条分别表示常规锁技术/STM技术进行并发控制的测试结果。各个图依次在单核,2核,4核,6核,8核的情况下测试。
这组数据里表明,在单核的情况下,STM的性能和常规锁几乎等同,多核情况下STM确实降低了锁的开销。但是,这里面有几个关键点需要注意:
- 无论是常规锁还是STM,做同样的事情的代价随着核个数的增加反而变慢(随着核的增加,两条曲线都变得更陡)。这听起来似乎很奇怪,怎么我机器变好了,性能反而差了?
- 尽管STM对锁的性能有不错的改善,但是,随着核个数的增加,STM的改善越来越不显著(随着核的增加,两条曲线越来越逼近)。按照上图的趋势,可以想象,在32核的情况下,STM(粉红色线条)的曲线将逼近常规锁(深蓝色线条)。
可见,STM不能解决多核下的线程竞态问题。只要基于锁技术,那么多核的优势将难以体现。这一点其实也可以从人类的工作模式中得到启示。我们大家都有独立的记忆,可以各自独立去思考,去做当前的事情,如果我们所有的人都共享了记忆,那么我们真的很难想象如何去协调彼此的工作。
我们不难有结论:多核时代,意味着对“共享内存并行模型”宣判了死刑。
为什么我们需要一种新的语言,而不是运行时库
从并行编程的角度来讲,我们传统计算机的体系结构模型(多个核共享同一内存总线,彼此竞争的方式去访问内存)走错了方向。基于上面对“共享内存并行模型”的讨论,我们可以想象,在核(不完全和CPU等价,但是我们这里不作区分)的个数上一定规模时,其实每个CPU有自己独立的记忆体(内存),CPU内部的计算完全独立于外界(其他的CPU),CPU和CPU之间仅仅通过消息传递进行通信,就如同我们人类彼此之间做的那样,其效率无疑是最好的。
这就是另一种并行编程模型,我们称之为“异步消息传递并行模型”。
但是我们的计算机并没有这样去设计。而Erlang这样做了。所以在我的观念里,其实Erlang是另一种计算机模型。虽然目前它由软件来实现,但是其实它最佳的工作环境是硬件级的:即对目前物理的计算机体系结构进行调整。
从上面我们的数据可以看出,线程个数并不是越多越好,基本上接近物理的CPU个数(略高于)是最好的。如果我们盲目增加线程个数,只会使线程的竞争成为常态而反而降低了性能。那么怎么让物理的CPU个数和我们程序中的线程个数适配呢?传统的解决方案是:线程池。线程池技术本质上是把更多的任务让有限的CPU串行地完成它们。在这当中,我们有很多和我们业务无关的技术细节需要处理。
Erlang其实是更加高明的做法。在Erlang中有一个概念叫进程(Process),我们可以将其理解为一个软CPU,可以非常轻量地进行创建和销毁。Erlang进程(Process)拥有独立的记忆体(内存),可进行独立的计算。不同的Erlang进程(Process)间通过异步的消息传递进行通讯。
所以使用Erlang,其实我们是在一个设计更为合理的计算机体系中工作。它不是运行时库,而是一个虚拟机。它是基于现实计算机结构基础之上的一个更佳抽象。
Erlang风格的并行
随着Erlang的逐步流行,出现了大量的在某某语言实现Erlang风格的并行(Erlang Style Concurrency)之说。这是对Erlang的认可,但也不乏误导,让人以为Erlang风格的并行只需要一个运行时库的支持。我们这里就讨论一下什么是Erlang风格的并行,以及实现它的代价。
Erlang开发者之一,Ulf Wiger,对什么是Erlang风格的并行进行了阐述2。我们这里援引下他的观点。一个Erlang风格的并行,至少包含以下特性:
- 迅速的进程创建和销毁
- 不费力的支持至少10K以上的并行进程
- 迅速的异步消息传递
- 复制的消息传递机制(无共享的并行)
- 进程监控
- 选择性的消息接收机制
进程创建/消息传递的速度和伸缩性
要让并行成为一种具有实用价值的基本建模手段,必须要让程序员能放心的创建解决问题所需的大量进程,而无需担心会因此而影响效率。若要以一句话来概况“Erlang 风格并行”的精髓,那就是——它让你可以按照问题自身内在的并行模式来构建应用。如果认为创建进程代价高昂,程序员就会尽量重用已有的进程;如果认为消息传递代价高昂,就会发明出其它的技术以避免传递消息。而这些手段通常是有害的(对于并行来说)。
异步消息传递
异步或者同步的消息传递,孰优孰劣曾经有过争论。的确,同步消息传递更易于理解。但在分布式的环境下,异步通讯(也就是所谓的“发送-祈祷”)则更符合直觉。基于同步消息传递的系统,在分布式的环境下也必须诉诸于某种形式的异步通讯机制,方可完成任务。
复制的消息传递
这里的并不意味着说在所有的情况下都必须要完全复制所有的消息,重点不在方式,而在效果。因为:
- 从可靠性角度考虑,进程不能共享内存
- 在分布的环境下,复制不可避免,我们尽可能的在本地和远程的消息传递中都保持相同的机制
进程监控与速错(Fail Fast)
这是“边界外”错误处理机制的根基。在 Erlang 中,典型的错误处理哲学是——速错(Fail Fast)。如果程序出现异常,就让它崩溃。其要义就在于,你的程序只处理正常情况,出现异常的情况则交由监控进程来负责处理。这么做的结果是,在大型系统中,能漂亮的实现容错。
选择性的消息接收
有N中方法可以实现选择性的消息接收,但对于复杂的多路并行而言,你必须至少要支持其中的一种。在达致并发的路上,这一点很容易被忽视。简单的程序之中,你也不会很明显的感到它的必要,但若当你真正发现它的价值,你很可能已经被“复杂性爆炸”折磨很久了。所以我建议将选择性的消息接收机制列为 Erlang 风格并发的一个充分条件。
小结
现在我们回头看其他语言中实现Erlang风格的并行。迅速的异步消息传递、复制的消息传递机制(无共享的并行)、进程监控、选择性的消息接收机制,这些特性通过一个运行时库完全可以做到的。但是,如何支持迅速的进程创建和销毁,不费力的支持至少10K以上的并行进程?如果不去修改语言本身的机制,达到这样的能力相当困难。而诚如Ulf Wiger所言,“Erlang 风格并行”的精髓,那就是——它让你可以按照问题自身内在的并行模式来构建应用。
所以,在其他语言中实现Erlang风格的并行非常困难,包括大家也许认为无所不能的C/C++(我个人很喜欢C/C++,但是它们确实没有很简单的方法在该语言中引入这方面的特性)。有一条路也许可行,因为Erlang虚拟机和Erlang语言本身并无必然的关联,虽然也许Erlang最能体现Erlang虚拟机的特性。所以,将Erlang虚拟机当作一个新的操作系统平台,移植各种语言到该平台上,也就是说让其他语言的编译器生成Erlang虚拟机的字节码(这要求Erlang虚拟机的字节码和CPU指令一样,稳定兼容地发展),这也许是支持Erlang风格的并行最简单的办法。
Erlang语言特性
上面“Erlang风格的并行”涉及的内容,可以说是Erlang最精髓的内容。下面我们谈的是关于Erlang其他一些重要特性。他们包括:
- 不可变状态(Immutable State)
- 函数式编程(FP)而不是面向对象编程(OOP)
不可变状态(Immutable State)
几乎所有目前的流行语言中,都有一个概念叫做“变量”,也就是说我们可以改变内存的状态(内存存储的数据)。但是,在Erlang语言中,“变量”不可以被修改(所以看起来并不适合用“变量”一词来称呼它)。
如果我们坚持内存是不可以在进程间(物理上)共享的话,那么“不可变状态(Immutable State)”并不是必须的。但是有两个原因,让我觉得不可变状态是自然的:
- 容易写出更加可靠的代码
- 优化本机进程间的消息传递
如果一个量它可以发生变化,那么就我们就需要清晰地知道它某个时刻的含义,甚至在不同时刻它们含义完全不同的。“不可变状态”禁止了这一点。这对编写可靠、清晰的代码是有利的。
另外,由于变量不可变,这使得本机进程间的消息传递可以非常轻量。虽然从逻辑上消息传递是基于“拷贝”的,但是既然变量不可修改,这意味着多个进程同时访问一块内存是安全的,不需要额外加一把锁。消息可以“不拷贝”就传递到另一个进程。
但是,不可变状态确实带来了很大的不同。例如:
- 你没有办法写一个for循环。因为没有自变量。
- 没有一个简单的基于线性内存的Vector(动态数组)。因为修改意味着整个Vector复制,而这是一个高额的代价。
第一点还并不特别严重。而没有一个基于线性内存的Vector,很多人也许无法理解。我这里解释下这个问题。
和在多核时代,共享内存并行模型将走向死亡之路一样,在海量数据下,基于动态线性内存的数据结构也将走向死亡。为什么这样说呢?我们以字符串类的实现为例。我们知道,C/C++程序性能卓越,但是,C/C++中,综合性能最好的字符串类,不是std::basic_string,而是SGI STL的rope类3。而rope类怎么实现的?其一,rope不是线性数据结构,它是一个二叉树。其二,rope这个字符串类它作了和Erlang一样的假定:“不可变状态(Immutable State)”。也就是说,rope类永远不会修改字符串的内容;要修改字符串,rope就会产生新的副本。由此可知,Erlang同样可以高效地实现rope(排除由于虚拟机本身的性能削弱外,Erlang与C/C++相比,没有任何特性导致低性能)。相反,rope这样的数据结构,更适合在Erlang中实现,而不是C/C++中。
关于动态线性内存的数据结构的缺陷,还可以看我另一篇文章:“喜欢Erlang的三大理由4”。
函数式编程(FP)而不是面向对象编程(OOP)
面向对象编程(OOP)的核心理念之一是“封装变化”,即“把可变状态(Mutable State)隐藏在对象里面”(正是这个特性使得并行成为一个几乎不可能解决的难题)。而Erlang的哲学是“不可变状态(Immutable State)”,因而面向对象编程(OOP)非但不适合Erlang,而且违背Erlang的哲学。
Erlang它有效吗?
Erlang确实改变了一些原有的习惯(对于那些习惯了命令式语言编程的人来说,包括我)。但是,应当看到,Erlang虽然在做某些事情的时候让你觉得略微麻烦了,但是它同时也提供了很多本来需要花费大量精力去做才可以做到的事情。从开发效率来讲,Erlang的1行代码通常抵得上10行C/C++代码。
Erlang的资料
Erlang经典
- Making reliable distributed systems in the presence of software errors5
- Programming Erlang
- Concurrent Programming in Erlang, Part I
Erlang相关的中文站点
- http://code.google.com/p/ecug/
- http://erlang.org.cn/
- http://erlang-china.org/
- http://erlang.devsky.org/
Erlang中文讨论组
其他Erlang资料
- 到 http://erlang.devsky.org/cn:resources 获得详细列表。
Erlang新手建议
Erlang它确实有点与众不同。对于多数程序员,我们习惯了命令式的编程,这在学习Erlang的时候需要一段时间来适应这个变化。但是总体来说,Erlang并不难学。相比而言,Erlang 其实是一门非常小而且简单的语言。从我个人学习Erlang的经验来讲,我觉得实战是第一位的。不只是去喜欢,更重要的尝试是用它去做些你觉得有意思的东西。
作者简介
许式伟,技术总监,WPS Office 2005 首席架构师。C++ 和 Erlang 爱好者。主导了多个开源项目,如 WinxGui、StdExt、Erlana 等。WTL项目成员。组织了 ECUG(Erlang China User Group)联盟,方便Erlang爱好者的信息互通与交流。喜爱 Linux 和自由软件。感兴趣的领域为分布式存储和计算、数据中心、网络蜘蛛等。