Question

根据美国加州大学伯克利分校所做的一项名为“How Much Information?”的调查结果，2002 年人类新创造的数据总量已超过 5 艾字节（EB）。其中艾（Exa，艾克萨）是 10 的 18 次方，或者说是 2 的 60 次方的前缀。这类前缀还有很多，按顺序分别为千（Kilo，10 的 3 次方）、兆（Mega，10 的 6 次方）、吉（Giga，10 的 9 次方）、太（Tera，10 的 12 次方）、拍（Peta，10 的 15 次方）、艾（Exa，10 的 18 次方）。

此外，根据这项调查做出的预测，2006 年人类的信息总量可达到 161EB，2010 年可达到约 988EB（约等于 1ZB，Z 为 Zetta，即 10 的 21 次方字节）。这意味着，人类在 1 年内所产生并记录的数据量，已经超过了截止到 20 世纪末人类所创造的全部信息的总量。

如此大量的信息被创造、流通和记录，这被称为信息爆炸。生活在 21 世纪的我们，每天都必须要处理如此庞大的信息量。

信息爆炸并不仅仅是社会整体所面临的问题，我们每个人所拥有的数据每天也在不断增加。在我最早接触计算机的 20 世纪 80 年代初，存储媒体一般采用 5 英寸软盘。面对 320KB 的“大容量”，当时还是初中生的我曾经感叹到：这些数据容量恐怕一辈子都用不完吧。

然而，在 20 多年以后，我所使用的电脑硬盘容量就已经有 160GB 之多，相当于 5 英寸软盘的 50 万倍。更为恐怖的是，这些容量的 8 成都已经被各种各样的数据所填满了。刚刚我查了一下，就光我手头保存的电子邮件，压缩之后也足足有 3.7GB 之多，而这些邮件每天还在不断增加。

信息的尺度感

在物理学的世界中，随着尺度的变化，物体的行为也会发生很大的变化。量子力学所支配的原子等粒子世界中，以及像银河这样的天文学世界中，都会发生一些在我们身边绝对见不到的现象。

在粒子世界中，某个粒子的存在位置无法明确观测到，而只能用概率论来描述。据说，这是因为要观测粒子，必须要通过光（也就是光子这种粒子）等其他粒子的反射才能完成，而正是这种反射，就干扰了被观测粒子在下一瞬间的位置。

不仅如此，在量子力学的世界中，仿佛可以无视质量守恒定律一样，会发生一些神奇的现象，比如从一无所有的地方产生一个粒子，或者粒子以类似瞬间移动的方式穿过毫无缝隙的墙壁等，这真是超常识的大汇演。

天文世界也是一样。两端相距数亿光年的银河星团，以及由于引力太强连光都无法逃出的黑洞，这些东西仅凭日常的感觉是很难想象的。

这些超乎常理的现象的发生，是因为受到了一些平常我们不太留心的数值的影响。例如光速、原子等粒子的大小、时间的尺度等，它们的影响是无法忽略的。

在 IT 世界中也发生了同样的事情。从小尺度上来说，电路的精密化导致量子力学的影响开始显现，从而影响到摩尔定律；从大尺度上来说，则产生了信息爆炸导致的海量数据问题。

和人不同，计算机不会感到疲劳和厌烦，无论需要多少时间，最终都能够完成任务。然而，如果无法在现实的时间范围内得出结果，那也是毫无用处的。当数据量变得很大时，就会出现以前从来没有考虑过的各种问题，对于这些问题的对策必须要仔细考量。

下面我们以最容易理解的例子，来看一看关于数据保存和查找的问题。

大量数据的查找

所谓查找，就是在数据中找出满足条件的对象。最简单的数据查找算法是线性查找。所谓线性查找其实并不难，只要逐一取出数据并检查其是否满足条件就可以了，把它叫做一种算法好像也确实夸张了一些。

线性查找的计算量为 O(n) ¹，也就是说，和查找对象的数据量成正比。在算法的性能中，还有很多属于 O(n²)、O(n·log n) 等数量级的，相比之下 O(n) 还算是好的（图 1）。

^{1 这里的记法被称为} O ^{记法（或者大} O ^{记法），指的是计算量随参数} n^{（大多数情况下为输入的数据量）的变化情况。（原书注）}

图 1 算法计算性能的差异

即便如此，随着数据量的增加，查找所需的时间也随之不断延长。假设对 4MB 的数据进行查找只需要 0.5 秒，那么对 4GB（=4000MB ²）的查找计算就需要 8 分 20 秒，这个时间已经算比较难以忍受的了。而如果是 4TB（=4000GB）的数据，单纯计算的时间就差不多需要 6 天。

^{2 关于 K、M、G 等表示数量级的前缀，有 1000 倍递增的十进制和 1024 倍递增的二进制两种算法，在表示硬盘容量等场合（为了看起来更多）一般都采用十进制，因此这篇文章中也采用了十进制。其实，如果要明确表示 1024 倍递增的二进制方式，则有另外的 Ki、Mi、Gi 等前缀，如“320KiB”，但这种写法一般不太常见。（原书注）}

像 Google 等搜索引擎所搜索的数据量，早已超过 TB 级，而达到了 PB 级。因此很明显，采用单纯的线性查找是无法实现的。那么，对于这样的信息爆炸，到底应该如何应对呢？

二分法查找

从经验上看，计算性能方面的问题，只能用算法来解决，因为小修小补的变更只能带来百分之几到百分之几十的改善而已。

在这里，我们来介绍一些在一定前提条件下，可以极大地改善查找计算量的算法，借此来学习应对信息爆炸在算法方面的思考方式。

对于没有任何前提条件的查找，线性查找几乎是唯一的算法，但实际上，大多数情况下，数据和查找条件中都存在着一定的前提。利用这些前提条件，有一些算法就可以让计算量大幅度减少。首先，我们来介绍一种基本的查找算法——二分法查找（binary search）。

使用二分法查找的前提条件是，数据之间存在大小关系，且已经按照大小关系排序。利用这一性质，查找的计算量可以下降到 O(log n)。

线性查找大多数是从头开始，而二分法查找则是从正中间开始查找的。首先，将要查找的对象数据和正好位于中点的数据进行比较，其结果有三种可能：两者相等；查找对象较大；查找对象较小。

如果相等则表示已经找到，查找就结束了。否则，就需要继续查找。但由于前提条件是数据已经按照大小顺序进行了排序，因此如果查找对象数据比中点的数据大，则要找的数据一定位于较大的一半中，反之，则一定位于较小的一半中。通过一次比较就可以将查找范围缩小至原来的一半，这种积极缩小查找范围的做法，就是缩减计算量的诀窍。

这个算法用 Ruby 编写出来如图 2 所示。图 2 中定义的方法接受一个已经排序的数组 data，和一个数值 value。如果 value 在 data 中存在的话，则返回其在 data 中的元素位置索引，如果不存在则返回 nil。

def bsearch(data, value)
  lo = 0
  hi = data.size
  while lo < hi
    mid = (lo + hi) / 2 # Note: bug in Programming Pearl
    if data[mid] < value
      lo = mid + 1;
    else
      hi = mid;
    end
  end
  if lo < data.size && data[lo] == value
    lo # found
  else
    nil # not found
  end
end

图 2 二分法查找程序

二分法查找的计算量在 n（= 数据个数）较小时差异不大，但随着 n 的增大，其差异也变得越来越大。

表 1 显示了随着数据个数的增加，log n 的增加趋势。当只有 10 个数据时，n 和 log n 的差异为 4.3 倍；但当有 100 万个数据时，差异则达到了 72000 倍。

表1 O(n)和O(log n)的计算量变化

n

log n

n / log n（倍)

10

2.302585092994046

4.3429448190325175

100

4.605170185988092

21.71472409516259

1000

6.907755278982137

144.76482730108395

10000

9.210340371976184

1085.7362047581294

100000

11.512925464970229

8685.889638065037

1000000

13.815510557964274

72382.41365054197

说句题外话，出人意料的是，二分法查找的实现并非一帆风顺。例如，1986 年出版的 Jon Bentley 所著的《编程珠玑》³（Programming Pearls）一书中，就介绍了二分法查找的算法。虽然其示例程序存在 bug，但直到 2006 年，包括作者自己在内，竟然没有任何人注意到。

^{3 《编程珠玑》第 2 版中译本由人民邮电出版社于 2008 年出版，黄倩、钱丽艳译。}

这个 bug 就位于图 2 的第 5 行 Note 注释所在的地方。《编程珠玑》中原始的程序是用 C 语言编写的。在 C 这样的语言中，lo 和 hi 之和有可能会超过正整数的最大值，这样的 bug 被称为整数溢出（integer overflow）。

因此，在 C 语言中，这个部分应该写成

mid = lo + ((hi - lo) / 2)

来防止溢出。在 1986 年的计算机上，索引之和超过整数最大值的情况还非常少见，因此，在很长一段时间内，都没有人注意到这个 bug。

再说句题外话的题外话，Ruby 中是没有“整数的最大值”这个概念的，非常大的整数会自动转换为多倍长整数。因此，图 2 的 Ruby 程序中就没有这样的 bug。

散列表

从计算量的角度来看，理想的数据结构就是散列表。散列表是表达一个对象到另一个对象的映射的数据结构。Ruby 中有一种名为 Hash 的内建数据结构，它就是散列表。从概念上来看，由于它是一种采用非数值型索引的数组，因此也被称为“联想数组”，但在 Ruby 中（Perl 也是一样）从内部实现上被称为 Hash。而相应地，Smalltalk 和 Python 中相当于 Hash 的数据结构则被称为字典（Dictionary）。

散列表采用了一种巧妙的查找方式，其平均的查找计算量与数据量是无关的。也就是说，用 O 记法来表示的话就是 O(1)。无论数据量如何增大，访问其中的数据都只需要一个固定的时间，因此已经算是登峰造极了，从理论上来说。

在散列表中，需要准备一个“散列函数”，用于将各个值计算成为一个称为散列值的整数。散列函数需要满足以下性质：

· 从数据到整数值（0 ～ N-1）的映射

· 足够分散

· 不易冲突

“足够分散”是指，即便数据只有很小的差异，散列函数的计算结果也需要有很大的差异。“不易冲突”是指，不易发生由不同的数据得到相同散列值的情况。

当存在这样一个散列函数时，最简单的散列表，可以通过以散列值为索引的数组来表现（图 3）。

hashtable = [nil] * N         ←---根据元素数量创建数组

def hash_set(hashtable, x, y) ←---数据存放(将散列值作为索引存入)
  hashtable[hash(x)] = y 
end

def hash_get(hashtable, x)    ←---数据取出(将散列值作为索引取出)
  hashtable[hash(x)]
end

图 3 最简单的散列表

由于散列值的计算和指定索引访问数组元素所需的时间都和数据个数无关，因此可以得出，散列表的访问计算量为 O(1)。

不过，世界上没有这么简单的事情，像图 3 这样单纯的散列表根本就不够实用。作为实用的散列表，必须能够应对图 3 的散列表没有考虑到的两个问题，即散列值冲突和数组溢出。

虽然散列函数是数据到散列值的映射，但并不能保证这个映射是一对一的关系，因此不同的数据有可能得到相同的散列值。像这样，不同的数据拥有相同散列值的情况，被称为“冲突”。作为实用的散列表，必须要能够应对散列值的冲突。

在散列表的实现中，应对冲突的方法大体上可以分为链地址法（chaining）和开放地址法（open addressing）两种。链地址法是将拥有相同散列值的元素存放在链表中，因此随着元素个数的增加，散列冲突和查询链表的时间也跟着增加，就造成了性能的损失。

不过，和后面要讲到的开放地址法相比，这种方法的优点是，元素的删除可以用比较简单且高性能的方式来实现，因此 Ruby 的 Hash 就采用了这种链地址法。

另一方面，开放地址法则是在遇到冲突时，再继续寻找一个新的数据存放空间（一般称为槽）。寻找空闲槽最简单的方法，就是按顺序遍历，直到找到空闲槽为止。但一般来说，这样的方法太过简单了，实际上会进行更复杂一些的计算。Python 的字典就是采用了这种开放地址法。

开放地址法中，在访问数据时，如果散列值所代表的位置（槽）中不存在所希望的数据，则要么代表数据不存在，要么代表由于散列冲突而被转存到别的槽中了。于是，可以通过下列算法来寻找目标槽：

1. 计算数据（key）的散列值

2. 从散列值找到相应的槽（如果散列值比槽的数量大则取余数）

3. 如果槽与数据一致，则使用该槽→查找结束

4. 如果槽为空闲，则散列表中不存在该数据→查找结束

5. 计算下一个槽的位置

6. 返回第 3 步进行循环

由于开放地址法在数据存放上使用的是相对普通的数组方式，和链表相比所需的内存空间更少，因此在性能上存在有利的一面。

不过，这种方法也不是尽善尽美的，它也有缺点。首先，相比原本的散列冲突发生率来说，它会让散列冲突发生得更加频繁。因为在开发地址法中，会将有冲突的数据存放到“下一个槽”中，这也就意味着“下一个槽”无法用来存放原本和散列值直接对应的数据了。

当存放数据的数组被逐渐填满时，像这样的槽冲突就会频繁发生。一旦发生槽冲突，就必须通过计算来求得下一个槽的位置，用于槽查找的处理时间就会逐渐增加。因此，在开放地址法的设计中，所使用的数组大小必须是留有一定余量的。

其次，数据的删除比较麻烦。由于开放地址法中，一般的元素和因冲突而不在原位的元素是混在一起的，因此无法简单地删除某个数据。要删除数据，仅仅将删除对象的数据所在的槽置为空闲是不够的。

这样一来，开放地址法中的连锁就可能被切断，从而导致本来存在的数据无法被找到。因此，要删除数据，必须要将存放该元素的槽设定为一种特殊的状态，即“空闲（允许存放新数据）但不中断对下一个槽的计算”。

随着散列表中存放的数据越来越多，发生冲突的危险性也随之增加。假设真的存在一种理想的散列函数，对于任何数据都能求出完全不同的散列值⁴，那么当元素个数超过散列表中槽的个数时，就不可避免地会产生冲突。尤其是开放地址法中当槽快要被填满时，所引发的冲突问题更加显著。

^{4 这样的理想散列函数被称为完美散列函数。如果事先得知数据的取值范围，则构造完美散列函数是可能的。（原书注）}

无论采用哪种方法，一旦发生冲突，就必须沿着某种连锁来寻找数据，因此无法实现 O(1) 的查找效率。

因此，在实用的散列表实现中，当冲突对查找效率产生的不利影响超过某一程度时，就会对表的大小进行修改，从而努力在平均水平上保持 O(1) 的查找效率。例如，在采用链地址法的 Ruby 的 Hash 中，当冲突产生的链表最大长度超过 5 时，就会增加散列表的槽数，并对散列表进行重组。另外，在采用开放地址法的 Python 中，当三分之二的槽被填满时，也会进行重组。

即便在最好的情况下，重组操作所需的计算量也至少和元素的个数相关（即 O(n)），不过，只要将重组的频度尽量控制在一个很小的值，就可以将散列表的平均访问消耗水平维持在 O(1)。

散列表通过使用散列函数避免了线性查找，从而使得计算量大幅度减少，真是一种巧妙的算法。

布隆过滤器

下面我们来介绍另一种运用了散列函数的有趣的数据结构——布隆过滤器（Bloom filter）。

布隆过滤器是一种可以判断某个数据是否存在的数据结构，或者也可以说是判断集合中是否包含某个成员的数据结构。布隆过滤器的特点如下：

· 判断时间与数据个数无关（O(1)）

· 空间效率非常好

· 无法删除元素

· 偶尔会出错（！）

“偶尔会出错”这一条貌似违背了我们关于数据结构的常识，不过面对大量数据时，我们的目的是缩小查找的范围，因此大多数情况下，少量的误判并不会产生什么问题。

此外，布隆过滤器的误判都是假阳性（false positive），也就是说只会将不属于该集合的元素判断为属于该集合，而不会产生假阴性（false negative）的误判。像布隆过滤器这样“偶尔会出错”的算法，被称为概率算法（probabilistic algorithm）。

布隆过滤器不但拥有极高的时间效率（O(1)），还拥有极高的空间效率，理论上说（假设误判率为 1%），平均每个数据只需要 9.6 比特的空间。包括散列表在内，其他表示集合的数据结构中都需要包含原始数据，相比之下，这样的空间效率简直是压倒性的。

布隆过滤器使用 k 个散列函数和 m 比特的比特数组（bit array）。作为比特数组的初始值， 所有比特位都被置为 0。向布隆过滤器插入数据时，会对该数据求得 k 个散列值（大于 0 小于 m）， 并以每个散列值为索引，将对应的比特数组中的比特位全部置为 1。

要判断布隆过滤器中是否包含某个数据，则需求得数据的 k 个散列值，只要其对应的比特位中有任意一个为 0，则可以判断集合中不包含该数据。

即便所有 k 个比特都为 1，也可能是由于散列冲突导致的偶然现象而已，这种情况下就产生了假阳性。假阳性的发生概率与集合中的数据个数 n、散列函数种类数 k，以及比特数组的大小 m 有关。如果 m 相对于 n 太小，就会发生比特数组中所有位都为 1，从而将所有数据都判定为阳性的情况。

此外，当 k 过大时，每个数据所消耗的比特数也随之增加，比特数组填充速度加快，也会引发误判。相反，当 k 过小时，比特数组的填充速度较慢，但又会由于散列冲突的增多而导致误判的增加。

在信息爆炸所引发的大规模数据处理中，像布隆过滤器这样的算法，应该会变得愈发重要。

一台计算机的极限

刚才我们介绍的二分法查找、散列表和布隆过滤器，都是为了控制计算量，从而在现实的时间内完成大量数据处理的算法。

然而，仅仅是实现了这些算法，还不足以应对真正的信息爆炸，因为信息爆炸所产生的数据，其规模之大是不可能由一台计算机来完成处理的。最近，一般能买到的一台电脑中所搭载的硬盘容量最大也就是几 TB，内存最大也就是 8GB 左右吧。

在摩尔定律的恩泽下，虽然这样的容量已然是今非昔比，但以数 TB 的容量来完成对 PB 级别数据的实时处理，还是完全不够的。

那该怎么办呢？我们需要让多台计算机将数据和计算分割开来进行处理。一台计算机无法处理的数据量，如果由 100 台、1000 台，甚至是 1 万台计算机进行合作，就可以在现实的时间内完成处理。幸运的是，计算机的价格越来越便宜，将它们连接起来的网络带宽也越来越大、越来越便宜。Google 等公司为了提供搜索服务，动用了好几个由数十万台 PC 互相连接起来所构成的数据中心。“云”这个词的诞生，也反映出这种由多台计算机实现的分布式计算，重要性越来越高。

然而，在数万台计算机构成的高度分布式环境中，如何高效进行大量数据保存和处理的技术还没有得到普及。因为在现实中，能够拥有由如此大量的计算机所构成的计算环境的，也只有 Google 等屈指可数的几家大公司而已。

假设真的拥有了大量的计算机，也不能完全解决问题。在安装大量计算机的大规模数据中心中，最少每天都会有几台计算机发生故障。也就是说，各种分布式处理中，都必须考虑到由于计算机故障而导致处理中断的可能性。这是在一台计算机上运行的软件中不太会考虑的一个要素。其结果就是，相比不包含分布式计算的程序开发来说，高度分布式编程得难度要高出许多。

DHT（分布式散列表）

在分布式环境下工作的散列表被称为 DHT（Distributed Hash Table，分布式散列表）。DHT 并非指的是一种特定的算法，而是指将散列表在分布式环境中进行实现的技术的统称。实现 DHT 的算法包括 CAN、Chord、Pastry、Tapestry 等。

DHT 的算法非常复杂，这种复杂性是有原因的。在分布式环境，尤其是 P2P ⁵环境中实现散列表，会遇到以下问题：

^{5 P2P，是 Peer-to-Peer（点对点）的缩写，是一种无中央服务器的对等式通信架构。}

· 由于机器故障等原因导致节点消失

· 节点的复原、添加

· 伴随上述问题产生的数据位置查找（路由）困难的问题

因此，基本上数据都会以多份副本进行保存。此外，为了应对节点的增减，需要重新计算数据的位置。

近年来，运用 DHT 技术，在分布式环境下实现非关系型数据库的键 - 值存储（key-value store）数据库受到越来越多的关注。键 - 值存储的例子包括 CouchDB、TokyoTyrant、Kai、Roma 等。

简单来说，这些数据库是通过网络进行访问的 Hash，其数据分别存放在多台计算机中。它们都有各自所针对的数据规模、网络架构和实现语言等方面的特点。

关于分布式环境下的数据存储，除了键 - 值存储以外，还有像 GFS（Google File System）这样的分布式文件系统技术。GFS 是后面要讲到的 MapReduce 的基础。

GFS 并不是开源的，只能在 Google 公司内部使用，但其基本技术已经以论文的形式公开发表，基于论文所提供的信息，也出现了（一般认为）和 GFS 具备同等功能的开源软件“HFS”（Hadoop File System）。

Roma

作为键 - 值存储数据库的一个例子，下面介绍我参与开发的 Roma。Roma（Rakuten OnMemory Architecture）是乐天技术研究所开发的键 - 值存储数据库，是在乐天公司内部为满足灵活的分布式数据存储需求而诞生的。其特点如下：

· 所有数据都存放在内存中的内存式数据库（In-Memory Database，IMDB）

· 采用环状的分布式架构

· 数据冗余化：所有数据除了其本身之外，还各自拥有两个副本

· 运行中可自由增减节点

· 以开源形式发布

Roma 是由多台计算机构成的，这些节点的配置形成了一个虚拟的环状结构（图 4）。这种圆环状的结构让人联想到罗马竞技场，这也正是 Roma 这个名字的由来。

图 4 Roma 的架构

当客户端需要向 Roma 存储一个键 - 值对时，首先根据键的数据求出其散列值。Roma 中的散列值是一个浮点数，在圆环状的结构中，每个节点都划定了各自所负责的散列值范围，客户端根据散列值找出应该存放该数据的节点，并向该节点请求存储键所对应的值。由于节点的选择是通过散列函数来计算的，因此计算量是固定的。

Roma 中一定会对数据进行冗余化，所以在数据被写入时，该节点会向其两边相邻的节点发起数据副本请求。因此，对于所有的数据，都会在其负责节点以及两个相邻节点的总共三个节点中保存副本。

Roma 的数据基本上是保存在各个节点的内存中的，但为了避免数据丢失，会在适当的时机以文件的形式输出快照。万一遇到 Roma 系统整体紧急关闭的情况，通过快照和数据写入日志，就可以恢复所有的数据。数据的取出也是同样通过计算散列值找到相应的节点，并对该节点发出请求。

对于像 Roma 这样的分布式键 - 值存储数据库来说，最大的难题在于节点的增减。由大量计算机所构成的系统，必须时刻考虑到发生故障的情况。此外，有时候为了应对数据量和访问量的急剧增加，也会考虑在系统工作状态下增加新节点。

在故障等原因导致节点减少的情况下，一直保持联系的相邻节点会注意到这个变化，并对环状结构进行重组。首先，消失的节点所负责的散列值范围由两端相邻的节点承担。然后，由于节点减少导致有些数据的副本数减少到两个，因此这些数据需要进行搬运，以便保证副本数为三个。

增加节点的处理方法是相同的。节点在圆环的某个地方被插入，并被分配新的散列值负责范围。属于该范围的数据会从两端相邻节点获取副本，新的状态便稳定下来了。

假设，由于网络状况不佳导致某个节点暂时无法访问时，由于数据无法正常复制，可能出现三个数据副本无法保持一致性的问题。实际上，Roma 中的所有数据都通过一种时间戳来记录最后的更新时间。当复制的数据之间发生冲突时，其各自的时间戳必然不同，这时会以时间戳较新的副本为准。

Roma 的优点在于容易维护。只要系统搭建好，节点的添加和删除是非常简单的。根据所需容量增加新的节点也十分方便。

MapReduce

数据存储的问题，通过键 - 值存储和分布式文件系统，在一定程度上可以得到解决，但是在高度分布式环境中进行编程依然十分困难。在分布式散列表中我们也已经接触到了，要解决多个进程的启动、相互同步、并发控制、机器故障应对等分布式环境特有的课题，程序就会变得非常复杂。在 Google 公司，通过 MapReduce 这一技术，实现了对分布式处理描述的高效化。MapReduce 是将数据的处理通过 Map（数据的映射）、Reduce（映射后数据的化简）的组合来进行描述的。

图 5 是用 MapReduce 统计文档中每个单词出现次数的程序（概念）。实际上要驱动这样的过程还需要相应的中间件，不过这里并没有限定某种特定的中间件。

def map(name， document) ←---接收一个文档并分割成单词
  # name: document name
  # document: document contents
  for word in document
    EmitIntermediate(word， 1)
  end
end

def reduce(word， values) ←---对每个单词进行统计并返回合计数
  # key: a word
  # values: a list of counts of the word
  result = 0
  for v in values
    result += v.to_i
  end
  Emit(result)
end

图 5 MapReduce 编写的单词计数程序（概念）

根据图 5 这样的程序，MapReduce 会进行如下处理：

· 将文档传递给 map 函数

· 对每个单词进行统计并将结果传递给 reduce 函数

MapReduce 的程序是高度抽象化的，像分配与执行 Map 处理的数据接近的最优节点、对处理中发生的错误等异常情况进行应对等工作，都可以实现高度的自动化。对于错误的应对显得尤其重要，在混入坏数据的情况下，对象数据量如果高达数亿个的话，一个一个去检查就不现实了。

在 MapReduce 中，当发生错误时，会对该数据的处理进行重试，如果依然发生错误的话则自动进行“最佳应对”，比如忽略掉该数据。

和 GFS 一样，MapReduce 也没有开源，但基于 Google 发表的论文等信息，也出现了 Hadoop 这样的开源软件。在 Google 赞助的面向大学生的高度分布式环境编程讲座中，也是使用的 Hadoop。

小结

随着信息爆炸和计算机的日用品化，分布式编程已经与我们近在咫尺，但目前的软件架构可以说还不能完全应对这种格局的变化，软件层面依然需要进化。