每周学点大数据 | No.36并行算法

No.36期

‍并行算法‍

Mr. 王：‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍今天我们来谈一个新的话题——并行算法。

小可：并行？并行是不是说，一个任务由多个人同时做呢？

Mr. 王：通俗地讲是这样的。有很多问题，当数据规模比较大时，如果单独由一台计算机来做，就会变得费时费力，我们希望可以将一个问题交由多台计算机进行处理和解决。这就是我们要研究的并行算法。

小可：那具体要怎么做呢？如果把整个任务分开给多台计算机来做，我们就要想办法把任务分割开，还要对它们提交的结果进行综合，这对于一些复杂的问题还是有一定难度的啊。

Mr. 王：不要担心，我们有 MapReduce。

小可：那是什么？‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

Mr. 王：MapReduce是一个分布式编程模型，最初是由Google公司的Jeffery Dean 和Sanjay Ghemawat 于 2004 年开发的。

现在市面上流行的一个开源版本叫作Hadoop。这个编程模型让不精通于分布式并行开发的计算机工作者和程序员，也能有效、方便、快捷地开发并行程序。

这样，即使是不了解并行编程的程序员，也可以用 MapReduce 将自己的程序并行运行在多台计算机上，实现并行计算。

顾名思义， MapReduce 实现了两个功能：Map 和 Reduce。

Map 是将一个函数应用于数据集合中的所有成员，然后返回一个结果集合。

Reduce是把从多个Map 中，通过多个线程、进程或者独立计算机系统并行执行的结果进行分类和归纳。

MapReduce 设计并行算法的过程中，程序员首先要定义 Map 函数和 Reduce 函数，将需要求解的问题用 Map 和 Reduce 这两种操作来描述。定义好之后， MapReduce 框架就可以帮助解决问题了。

小可挠挠头，说：还是很抽象啊。

Mr. 王：我们还是举一个例子来说明吧。比如统计一篇文章中某个字母出现的数量，这在破解替换密码中是一个非常重要的手段和步骤。

所谓替换密码，就是用一个字母或者符号去替换另一个字母或者符号，比如用 x 来表示 e，用 a 来表示 t 等。

因为在英文中，某个字母在一篇文章中出现的次数往往呈现一种分布。即使在信息的传递中，选择了另一个字母来替代这个字母，也是可以通过这个字母在大量文章中的统计百分比来判断它是哪一个字母的。

假设现在需要破译一篇文章，我们猜测它使用了基于替换的密码，就需要统计每一个符号在整篇文章中的数量。

比如经过统计，发现 x 出现的次数是最多的，根据以往的经验和大量的统计结论，密码专家就会猜测 x 这个字母可能表示的是 e。

现在我们用一个结构图来表示 MapReduce 在解决这个问题时，每一部分都做了哪些工作。

整个算法的输入以 key-value 对的形式体现，由于统计单词数量这个问题比较简单，输入的单词仅有键（也就是单词）就可以了，在这个图中Map 函数解决的问题，就是对 key-value 对中出现的字母进行一个初步统计。

小可：第一个 Map 统计出的 a 有 1 个、b 有 2 个，可是第二个 Map 统计出的 c 分成了两个部分，怎么办呢？

Mr. 王：在实际的统计中，中间结果分块的情况非常常见，所以这里引入了一种机制，叫作 combine。它的引入就解决了统计结果分块的情况，注意看第二个 Map，它就将 c 的分块结果合并为 9。

这样的做法非常有利于提高整个系统的效率。在这个例子中，如果相同的字母都被有效地合并，在最终进行统计时就会变得更加方便，否则后面的步骤就会变得更加麻烦。

接下来数据会经历一个叫作 partition 的过程，这个过程要做的是决定哪一个 key 给哪一个Reducer 去处理。

MapReduce 的好处之一就是，combine 和 partition 操作是可以由系统自动实现的，这两步是可选的，可以不用程序员去实现。

接下来系统自动执行 Shuffle 和Sort，我们称之为洗牌和排序。此时MapReduce 平台会将键值相同的数据项目洗混到一起，最后将每个键值的数据交给一个 Reducer 去处理。

比如在这个例子中，第一个 Reducer 处理的就是 a 的计数；第二个 Reducer 处理 b 的计数等。

简单整理一下，一个 MapReduce 程序的重点就是， Map 和 Reduce 这两个函数的定义是必须要由程序员写程序去完成的。

combine 和 partition 是可以由 MapReduce 平台框架自动去实现的，但是自动实现的效率往往不是最高的，如果程序员希望提高 MapReduce 平台在解决某些问题时的效率，则可以去自行定义 combine 和 partition 操作。

其中 combine 操作类似于一个微型的 Reducer，在 Map 执行过之后， combine 对 Map 的结果进行一个初步 Reduce。

由于它进行的是一个合并操作，所以可以将具有相同键值的记录合并为一个，一大好处是减小了各台计算机之间的网络流量。

比如我们发送 c=1、 c=3、 c=4 这样三条记录，会产生三条记录的流量 ；而如果发送一条 c=8 记录，那么只产生一条记录的流量，而且这不会影响最终的计数结果，因为它们在最后的 Reducer 处也是要合并的。

partition 操作执行于 Reduce 之前，为不同的Reducer 去分配其需要处理的键值范围。至于其他的各种操作，MapReduce 框架可以帮助程序员去完成一切。

小可：那这个“一切”都包括些什么呢？

Mr. 王：首先是 MapReduce 要进行调度工作，也就是为 Map 和 Reduce 这些操作分配“工人”。

小可：工人？

Mr. 王：也有些书籍称之为 Slaves，也就是去执行具体操作的那些计算机。

因为在定义MapReduce 时和 MapReduce 的具体运行过程中，我们并不知道 Map 和 Reduce 这些函数究竟具体运行在哪一台计算机上。

Mapper 或 Reducer何时启动、何时结束，一个特定的 Mapper 正在处理哪种输入，一个特定的 Reducer 正在处理哪个特定的中间键值。

对于这些没有指定的工作都需要由 MapReduce 来执行，这样可以极大地减轻程序员管理大批计算机的辛苦。

其次是“数据分布”，进行将过程移动到数据的工作。“同步”完成聚集、排序、打乱中间数据的工作。

当然不能忘了“错误处理”的工作，由于参加并行运算的计算机是很多的，中间会涉及大量的网络通信。

如果有“工人”出现“失败”、死锁、宕机的情况，或者中间网络通信流量出现拥堵， MapReduce 平台要进行报警、重新启动或尝试恢复这些机器，使其正常运转。

在 MapReduce 算法的设计过程中，我们的最重要工作就是对算法用 Map 和 Reduce 来进行描述，有时还需要 combine 操作。

Combine 体现了本地聚合的思想。在前面的例子中也提到了，我们可以在进行 Mapper 发出数据之前，将其在本地进行提前聚合，目的是为了减小通信量，同时也让 Reduce 的过程变得更加轻松。

比如统计结果包括 c=2 和 c=3 两条记录，如果 Mapper 将其都发送出去，通信量就是两条记录 ；如果在本地将其相加为 c=5 的话，那么只需要发送一条记录即可。

在使用并行系统时，由于涉及很多计算机之间的通信，而通信往往是多机系统的效率瓶颈之一所以我们应尽可能多地让数据在本地计算、本地合并、传输结果，而不是将未经处理的数据一一发送出去。

内容来源：灯塔大数据