parallel vs. concurrent

比较模糊的两个概念,经常听人说起 parallel computation 和 concurrency 却没弄清楚两者那些细微的区别到底是啥。

stack overflow 上某人这样解释:通常我们会使用一些 concurrent programming 的工具,如多线程、多进程来分配任务,但是实际运行中他们未必是“parallel”执行,而 parallel programming 中往往就是指能通过同时执行这些子任务而加速,因此后者更关注于如何将 task decompose 成为合适的子任务(避免无谓的 block/wait)充分利用已有的 core/CPU。

而 concurrent programming 往往关注的问题并不是完全一样,通常如何设计 distributed system 算是 concurrent programming 关注的一个问题。最近听到的一个相对“物理”的解释是说:我们知道所谓的“视界线”,即从观察者光速所能达到的“时空”,如果这个时空时间早于当前,就是过去;晚于当前则为将来。那一片光速不能达到的区域发生的事件与视界线以内的事件相比的话:如果事件发生在过去导致了当前,称为 causal relationship,而视界线以外的事件因为没有能力影响当前,因此是 concurrent 的,这个从英文构词上来看也是表达了类似的意思。

一个比较搞笑的事情是(来自所看材料,在此转述,版权不为个人所有):曾经公元 X 年某人 A 写了首歌大红大紫,X+7 年后 B 又写了首相似的歌也大红大紫,然后 A 指责 B 抄袭了 A 的作品。很明显这个地方 B 难以指责 A 抄袭,因为因果律(causal relationship)是被认为 imply 了时间先后关系的。当然如果人的思维是“单线程”的就会很自然的得到这个结论。但实际上还有另外的解释。比如说离地球 1000/1007 光年的两个方向的外星人 \alpha\beta 他们在差不多的时间(X-1000)里写了两首差不多的歌,然后通过 radio 向宇宙各处播放,然后 A 恰巧在 X 年收到了信号于是写了前首歌而 X+7 年 B 接收到了后者遭到了指责。之后在 $late \alpha$ 看来经过了 2000+ 年收到了别人播放的和自己写的差不多的歌曲,对 \beta 而言他也有类似的感受,可是两者的因果律(不正确的使用)却导致了相反的结论。

从这个角度来看,先知之类的人都是能“超光速”的观察到 concurrent 世界里面的东西而更加正确 predict 未来的人了 🙂

回到 concurrent programming 问题上来,往往两个 process 不能知晓对方的行为状态,那么如果希望协作完成一个任务就势必达成某种默契,这就是 protocol,从某种意义上来看,设计分布式系统,就是选择“合适”的 protocol。说穿了 protocol 就是 assumption,和 learning 选择 regularization 是类似的道理。当然类似的地方还在于,选择的目的也是迎合应用的需要。前面讨论了 CAP 原理,这其实就是一般 distributed system 考虑的几个基本的方面(当然还有别的很多)。

比较常见关于 consistensy 方面的讨论都会针对某个 consistency model 来进行,常见的四种(来自这个 course 上的材料):

  • strong consistency:所谓同时发生的写入和读出均不影响且能保证读出来一定是最近写入的,从某种意义上存在某个全局的 realtime 时钟,所有操作都对应在上面的一个时间戳。我们知道实际上操作是有时间长度的,strong consistency 为了保证两个操作结果的正确性,必须将后面需要发生的操作 block(如果相关),让前一个操作结束后才能进行后者,从这个某种意义上来,strong consistency 往往需要付出一定“并行程度”的代价的。
  • sequential consistency:并不假定存在这个全局的时钟,而是保证一定存在一个全局的序,使得这个序在每个进程上的投影正好是每个进程上操作的顺序。很明显 sequential consistency 是对 strong consistency 的松弛(全局时钟 imply 的序关系就是这里的序),那么就算这么简单的松弛也会导致一些 anti-intuition 的事情出现:比如进程 A 为变量写入 a 和 b 的值,在 strong consistency 下,假如 a 在 b 之前(全局时钟下)发生,进程 B 之后读取两次的结果必然都是 b,而 sequential consistency 下可能一次是 a 一次是 b。因为这个全局的序可以是 w(a)、r(a)、w(b)、r(b)。往往时钟本身难以同步,因此维系一个全局的时钟是难的,到了 sequential consistency 只要求每个 process 里面有一个时钟,这个序能在全局序投影下得以维持。这个意味着任意一个共享的单元,无论从哪个 process 看来,对其写入的顺序都是一样的。但即便是这个要求实现起来还是有很高的要求的(比如较高的网络通讯负荷):在 Ivy 的实现里面有几点,需要中心服务器来跟踪 page 的 owner 和 copy,读取时先问 master 要;写入时需要 invalidate 所有的 copy。需要说明的是证明一个系统是什么 consistency model 是比较复杂的。
  • causal consistency 和前面讨论的 causal relationship 有着密切的关系,即实际执行顺序只要能保持 causality 即可,这就给 concurrent 行为留下了足够的空间,但实际上很少有系统实现这个 consistency model。同进程的事件先后得以保持 imply 的是这个进程内部的 causality 可以保持,如果进程之间还存在通讯的话,因果关系会扩展到两个进程之间,因为全局序的存在,sequential consistency 能导致 causality consistency,但后者存在 concurrent operation 可以不遵循 global order 的情况:对同一单元的写入顺序对不同的 process 可以不同(只要他们是 concurrent 而不是 causal 的)。
  • eventual consistency,算是采用最多的 model 了,它允许 stale read 只要最终(多长时间?)能够读取到最近的写入。这常在 asynchonous network 里面见到,通常这个模型下需要解决的就是 stale read 和 conflicting write 问题。解决后者往往需要或者将整个 modification history 进行比较或者有一个 version number。eventual consistency 也被人称为 BASE 语义(basically available、soft state 和 eventual consistensy),相对于 ACID 语义。

实际学术界还有更多的 consistency model,有空可以稍微看看,比如 google 的 F1 使用的据说是最接近 strong consistency 的一个 model,Yahoo! 那边曾经见过的 Flavio 做的 zookeeper 方面的东西也有不少相关的概念(linearizability、serializability)。

——————
And Jacob came out of the field in the evening, and Leah went out to meet him, and said, Thou must come in unto me; for surely I have hired thee with my son’s mandrakes. And he lay with her that night.

Advertisements
parallel vs. concurrent

一个有关“parallel vs. concurrent”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s