20.4 映射-归并算法和磁盘索引程序
现在我们要从理论转向实践。首先，我们要来看看高阶函数mapreduce，然后我们会在一个简单的索引引擎中使用这种技术。在这里，我们的目标并不是要做一个世上最快最好的索引引擎，而是要通过这一技术来解决相关应用场景下真实面对的设计问题。
20.4.1 映射-归并算法
在图20-2中，向我们展示了映射-归并（map-reduce）算法的基本思想。开启一定数量的映射进程，让它们负责产生一系列的{Key, Value}这样的键-值对。映射进程把这些键-值对发送给一个归并进程，它负责合并这些键-值对，合并的方式就是把有相同键的值组合起来。
警告
这里提到的map这个词，尤其是在mapreduce的上下文中，与本书其他部分中提到的map函数全然不同，切忌混淆。
mapreduce（映射-归并算法）是由Google公司的Jeffrey Dean和Sanjay Ghemawat提出的高阶并行函数，据说Google的集群中每天都要大量使用这个算法。
图20-2 映射-归并算法
我们可以用多种不同的方式来实现多种不同语意的映射-归并算法。这个算法与其说是一个特定的算法，还不如说是一个算法族。
mapreduce是这么定义的：
F1(Pid, X)是映射函数。F1的任务是发送一组{Key, Value}数据给Pid，然后退出。mapreduce每次会给列表中的每个X创建一个新的进程。
F2(Key, [Value], Acc0) -> Acc是归并函数。当所有的映射函数都退出的时候，归并函数要负责针对每一个键，将它对应的所有的值合并到一起。此时，它会对每一个它收集到的{Key, [Value]}调用F2(Key, [Value], Acc)函数。Acc是一个累加器，它的初始值是Acc0。F2会返回一个新的累加器（另外一种描述方式是这样，F2在所有它收集到的{Key, [Value]}对上执行一个折叠操作）。
Acc0是累加器的初始值，当调用F2时会被使用。
L是一个X的列表。F1(Pid, X)会对列表L中的每一个X进行运算，Pid是由mapreduce创建的归并进程的进程标识符。
mapreduce定义在phofs（parallel higher-order function的缩写）模块中：
进一步深入之前，先来对这个mapreduce函数做一下测试，这样我们能更加理解它的工作机制。
我们要写一个小程序，以统计这本书所附的代码中所有单词的出现频率，代码是这样的：
运行的时候，代码目录里有102个Erlang模块，因此mapreduce也就创建了102个并发进程，它们每一个都向归并进程发送由键值对组成的数据流。这在100个核心处理上应该运行得很好（如果硬盘跟得上的话）。
现在我们已经明白mapreduce是怎么回事了，可以回到索引引擎了。