1.4 数据流

在为增加并行度而发展起来的各种并行处理系统结构中，最引人注目的是“数据流(data flow)”结构。其原理是这样：考察数据从进入系统，经过各种处理，直到离开系统的整个流程，将此流程分解成若干阶段，其中的每个阶段都是一种相对独立的处理和计算，然后将这些阶段的计算分布在不同的机器节点上，不同节点之间只有数据的流通。这样，由于处理和计算的不同阶段之间，或者说上、下游之间(而不是数据样本之间)的并行度，就实现了另一种形式的并行处理。这好比一条河，在上游的水往下流的同时下游的水也在往下流，数据就像河水一样形成了数据流。这也很像工厂里的生产流水线，一个节点就是一个工位，数据就像流水线上的部件或半成品。

当年Unix(以及现在Linux)的管道(pipe)和流水线机制就体现了数据流的思想。我们不妨从一个Unix命令行说起：

      cat shakespeare/*.txt|normalize|sort|uniq ＞ vocabulary

这里的cat、sort、uniq都是由Unix提供的工具软件(utility), normalize则是由程序员补充开发的一个工具软件，其功能是将输入的每个单词还原成它的原型，例如works和worked的原型是work, did和done的原型是do，等等。这个命令行把4个工具软件串在一起，启动后就建立起4个独立的进程。竖线“|”是由操作系统提供的“管道(pipe)”机制，将前面一个进程的输出传给下一个进程作为其输入。这样，第一个进程cat从文件系统逐个读出目录shakespeare下的所有．txt文件，那是莎士比亚所有著作的字符文件，本来是要输出在显示屏上的，但是现在就由管道机制传到后一个进程normalize的输入端了。同样，normalize的输出被传到sort的输入端，在那里进行排序，而sort的输出则被传到uniq，消去重复出现的单词。最后uniq的输出被写入词汇表文件vocabulary，这就是莎士比亚在其著作中用过的所有词汇。本来，如果我们要写一个从文本中提取词汇表的软件，这软件中对文本内容的处理也应该有这么几个阶段，而且这几个阶段各自所做的处理都有一定的代表性，都有重复使用的价值。事实上cat和sort都是很常用的工具。现在这样就可以把此类工具很灵活地加以组合，搭建出功能很强的流水作业线。因为进程之间流通的都是数据(没有控制信息，也没有地址信息)，所以这是个数据流，其中的进程互相并发。当年Unix的成功在很大程度上来自这个新颖而强大的功能以及由此而来的编程风格，以至于“Unix风格”成为一时的热门。

但是我们更感兴趣的是这里面的数据流思想。

先看对于这些进程的驱动。以normalize为例，它的操作是针对每个单词的，显然它只是在有输入数据到来时才工作，没有数据到来时就睡眠。换言之，这个进程是受输入数据驱动的。事实上，整个流水线，即整个数据流中所有的进程都是这样。所以，Unix的这些工具性软件有个共同的结构模式：

      while(e=next_element()! =EOF){
        o=f (e); //对输入流中的每项数据进行处理，调用函数f()。
        output(o)；
      }

每个进程都是在一个while循环中打转。每次都企图从输入端读取一项数据，然后加以处理，并输出本次处理的结果(如果有的话)。执行着不同工具软件的进程，其输入数据的单位可以是不一样的。如果是以字符为单位，那么这里的next_element()就是getchar()；如果是以行为单位，那么next_element()就是getline()；余可类推。注意：输入数据也可以是复合数据，例如KV对，即由一个键(key)及其值(value)构成的“键/值”对，例如“Name:Shakespeare”；甚至也可以是数据结构。不管是getchar()还是getline()，或者是别的什么next_element()，都是只有在读到了数据的时候才返回，否则这个进程就会睡眠等待，让出CPU，直到有数据到来时才被唤醒，这就是“数据驱动”，是数据流的一个重要特点。

再看数据在这些进程，或者说“节点”之间的流通。除输入数据的到来之外，各个进程之间并无别的同步机制，所以进展速度一定有快有慢。如果上游节点产生的输出数据快于下游进程对数据的耗用，那么数据就会在两个进程之间堆积起来。所以，每个进程的输入端一定得有缓冲和排队的机制。Unix的管道机制保证了这一点。

在上面这个例子中，normalize这个节点对其输入数据是处理一个输出一个，所以在节点内部不会有堆积。更重要的是这样有利于维持一个均匀的流，就像河里的水，一边流进来一边就流出去了。从这个角度看，节点之间数据传输和处理的单位似乎是越小越好，因为那样可以使数据流变得更平稳均匀。但是，数据的传输是有开销的，如果单位太小了，开销所占的比重就会上升，那就不划算了。所以数据传输的单位大小需要加以权衡。

另一个节点sort就不同了。我们知道，排序是不能让数据随到随走的，必须等所有数据都到位之后才能进行操作。所以，数据会在sort这个节点上堆积起来，直至所有数据都流入这个节点之后才会有输出。所以，像sort这样的操作就像一座水坝一样，对数据流有破坏作用，这个节点与下个节点之间的数据流变成了工作流。所以，只要一个流程中含有排序操作，这个流程就天然带有“批处理”的特征。不过，尽管如此，流的形状或拓扑却保持不变，所以我们常常不加细分而仍旧称之为数据流。

再看并行度。Unix的流水线是建在单机上的，进程之间是并发而不是并行的关系。如前所述，并发确实也会带来一点并行度，但是毕竟有限。要有更大的并行度，就得变并发为并行，办法之一就是把cat、normalize、sort、uniq放在不同的机器上，形成一个数据流机群。画成拓扑图如图1-1所示。

在图1-1中，节点之间的边都是有向的，代表着数据的流向，所以是个有向图。另外，这个图中并没有形成环，节点之间并无反馈。这样的图，就称为“有向无环图”，缩写为DAG。不过，这只是一个链状的一维DAG，也即链状的一维数据流。这样的数据流当然是简单的数据流。复杂一点的会有分叉而成为树状，那就是二维的数据流、二维的DAG了。再复杂一点的数据流还会有反馈，那就不是“无环”，不称其为DAG了。

Unix的管道机制并未提供分叉的功能，它确实提供了一个工具软件tee，意为可以用作T形节点，但是tee的输出只能到文件，而不是到stdout，也不允许重定向tee的输出。所以Unix在单机上只允许构建链状数据流。

显然，把这些节点放在不同的机器上就获得了真正的并行度，这种并行度存在于上下游节点之间。在这个例子中，开始时前面三个节点可以并行，只有uniq暂时空着；后来前面三个节点都完成了操作，这时候就只有uniq在忙了。姑且假定每个节点的计算量都是1/4，用于数据传输的计算量忽略不计，并且耗费的时间完全取决于计算量，那么原来完全串行时的总时间是1，现在则降到了1/2略多。如果不是sort把数据流变成了工作流，那么速度还可以提高。

可是这里只有上下游节点之间的并行，也即前后工位的并行，却没有同一工位内部，即数据之间的并行。如normalize就始终只有一个节点在工作，当数据量很大时显然我们也需要在这里引入并行。于是我们可能就有如图1-2所示的一个拓扑图。

这里配备了三个normalize节点。这样一来，原来一维的链就成了二维的图。不过我们也可以仍把它想象成一维的链，只是在normalize节点的位置上是三个叠在一起，就像三张相同的透明胶片叠在一起，我们仍旧只看到一个。或者也可以说，这个图的投影仍是一维的链、一维的DAG。

但是cat仍只有一个，这是因为从磁盘读出的速度总是比逐个单词处理的速度快，因而一个cat节点的读出就足够三个normalize节点之用了。图1-2中cat的输出被分发给三个normalize节点，严格说来相当于在cat后面还有一个实现负载均衡的distribute节点。

值得指出的是，sort也只有一个，这就不合理了。按理说，sort的计算量比normalize还大，理应有更高的并行度才对，为什么反倒只有一个呢？这显然是应该改进的。问题是sort这种计算不太容易并行化，比方说“冒泡排序”，就难以并行化。幸好还有一种“合并排序(merge-sort)”的算法，可以先分块进行局部排序，然后再加以合并。于是我们就把这个数据流的拓扑变成图1-3所示的那样。

这样明显合理得多，性能也肯定会好很多。这个数据流的拓扑看似是个DAG，但仍属于很简单的DAG，本质上仍是一维的链状DAG。

这里的每个节点都是运行着某种软件的处理器，但也完全可以是某种专用的硬件芯片或器件。从这个意义上说，我们可以把收音机、电视机等也看成是数据流系统。作为一个数据流系统，电视机的输入来自天线，里面经过调谐、放大、检波等节点，然后就分叉成视频和音频两个分支，各自又经过种种处理，最后视频分支的输出投射到显示屏，音频分支的输出则用来驱动扬声器。这整个拓扑画下来就是个DAG，只是每个节点都是专用芯片而不是处理器，而且在节点间流通的主要是模拟信号，而不是数字化了的信息(现在有数字电视了)。所以，数据流在某种意义上是对电子线路的模仿。另外，像电视机那样，从某一节点的输出开始就分成音频和视频两个不同的支流，才是实质上的二维数据流。

仍以电视机进行类比。电视机的运转与电视机的装配是两码事，装配归装配，运转归运转。数据流系统也体现和遵循着同样的思路。以前面的Shell命令行为例：Unix为使用者提供了cat、sort、uniq等“元器件”，因为不够就自己开发一个normalize；同时Unix又为使用者提供了Shell及其语言。于是使用者就运用shell语言搭建了一个数据流。一旦搭建起来之后它就一直运转下去，直到输入数据为EOF或Ctrl-C等特殊字符时为止。但是Unix并没有提供跨机器搭建数据流的手段和语言。

综上所述可见，虽然Unix的pipe机制中有数据流的思想，但是把它从并发变成并行，从单机推到多机，从一维推到二维，需要跨越的台阶还是不低的。

最后还要指出，数据流系统是一种非冯·诺依曼结构，因为在数据流的拓扑中不存在一个全局的中央控制器，更没有供这个中央控制器使用的全局内存。