1.3 并行计算

一般而言，数据量大了，所需的计算量自然也大。计算量与数据量之间的关系不一定是线性关系，一般是某种多项式的关系，甚至有可能是指数的关系。计算复杂性和算法分析就是专门研究各种问题和算法的计算量与数据量之间的关系。最理想的是常数关系，就是不管数据量有多大，计算量都固定不变，人们把这样的复杂性记为O(1)。比方说，根据下标访问数组中的元素就是这样。理论上不管数组有多大，不管下标的值是什么，访问任何一个数组元素的开销都是一样的，与数组大小无关。可惜这样的算法是很少的。比这复杂一点的是O(log2N)，这里的log2是以2为底的对数，例如“对分搜索”的计算量就是这样。再复杂一点，就是线性复杂度，记为O(N)，意为计算量跟数据量N成正比，这里的N表示数据的个数。再往上就是O(Nlog2N)、O(N2)等多项式复杂度。而指数复杂度，例如O(2N)，则对于大数据显然是不现实的了。但是，即使是对于线性复杂度的计算，由于大数据条件下的N很大，其计算量也是很大的。

当计算机的计算能力小于具体计算所需的计算量时，一个办法就是换用计算能力更强、计算更快的机器。在计算机技术发展的早期，人们就是这样做的，小型机不够快就用大型机，大型机不够快就用巨型机。但是，计算速度的提高毕竟赶不上数据量的增长，也赶不上复杂问题的涌现，于是人们就设法“分而治之”，一台机器算不过来就两台、三台、N台，使这些机器并行计算，希望N台机器合在一起可以使计算能力提高到N倍。另一方面，也在单台机器的系统结构上想办法，把机器做成“向量机”、SIMD(单指令多数据)、多核、多处理器等结构，总之是设法提高计算的并行度。并行度的增加就意味着综合计算能力的提高和计算速度的提高。

即便在单处理器的机器上，人们也设法通过多进程(或多线程)并发来增加并行度。读者也许会感到疑惑，在单处理器(且为单核)的机器上，一共就只有一个处理器在计算，多进程并发怎么能提高并行度，怎么能提高计算速度？确实，并发不等于并行，一共只有一个处理器，就不会有处理器之间的并行了。但是，在单进程的系统中处理器常常会因为要等待输入、输出的完成而空转，等待的时间长度一般取决于外部设备。例如读磁盘文件的一个记录块，就可能会让处理器等上数十毫秒。可是，如果是多进程并发，那就可能把这数十毫秒的时间用于别的进程的运行。在磁盘驱动器忙于寻道，让磁头镇定下来，然后等磁道上的目标扇区转到磁头下面的过程中，CPU在执行另一个进程的代码。数十毫秒的时间，已经可以做很多计算了。所以，此时的并行度是在CPU与外部设备之间。虽然一共才一个处理器，但是并行度确实还是增加了。

但是人们很快就发现，把机器或处理器的数量从1个提高到K个，一般而言并不能使计算能力也增加到K倍。这是因为，在这样的情况下需要把相当大的开销花在不同的机器或处理器之间的通信与同步上。更糟的是，许多问题其实很难找到合适的算法可以将其分解到不同的机器或处理器上去分头计算，然后再加以综合。所以，从前曾经有个猜想：把K个处理器合在一起，当K充分大时，综合的计算能力(速度)只能提高log2K倍。这就是说，假如我们把256个CPU连在一起，其综合的计算能力也许只能提高8倍。这当然是很令人沮丧的。这种现象特别多见于一些输入数据量不大而关系很复杂的问题。然而，如果虽然输入数据量很大，可是数据之间独立性很好，而且针对每一项数据所做的计算又很简单，那么K个处理器就真的能将综合的计算能力提高到K倍。所以，并行计算能否有效提高系统的计算能力，最终还是取决于数据的性质，取决于具体的问题和算法。

而MapReduce则正是这样一种并行计算的模型，它试图以K个处理器来分担对于N个数据的计算，希望能把总的计算时间降到1/K。但是这个愿望只有在N个数据的计算互相独立，也即算法的复杂度为O(N)时才能实现。在这种情况下，假设对N个数据的计算量(以计算时间表征)为aN+c，那么K个处理器并行就有望将计算时间降至aN/K+c。如果算法的复杂度高于O(N)，则计算时间一般也能有所降低，只是不能按比例降低到1/K了。所以，人们称MapReduce那样的并行计算为“极简并行”。

实践中我们可以看到两种不同的典型：一种是小数据大计算，即输入数据的量很小，但是计算量却很大、很复杂，这样的问题不适合于MapReduce那样的极简并行计算，需要为之搭建更复杂的数据流；另一种是大数据小计算，即输入数据的量很大，但是针对每项数据的计算却很小、很简单，而且这些计算互相独立，这样的问题就适合于MapReduce。当然，还有一种可能是大数据大计算，即输入数据的量很大，而且针对每项数据的计算量也很大并且很复杂。这样的问题当然更不适合MapReduce，更有待于算法上的突破。