云计算
图2-3 MapReduce执行流程图
3）一个分配了Map任务的Worker读取并处理相关的输入块。它处理输入的数据，并且将分析出的
4）这些缓冲到内存的中间结果将被定时写到本地硬盘，这些数据通过分区函数分成R个区。中间结果在本地硬盘的位置信息将被发送回Master，然后Master负责把这些位置信息传送给Reduce Worker。
5）当Master通知Reduce的Worker关于中间
6）Reduce Worker根据每一个唯一中间key来遍历所有的排序后的中间数据，并且把key和相关的中间结果值集合传递给用户定义的Reduce函数。Reduce函数的结果输出到一个最终的输出文件。
7）当所有的Map任务和Reduce任务都已经完成的时候，Master激活用户程序。此时MapReduce返回用户程序的调用点。
由于MapReduce是用在成百上千台机器上处理海量数据的，所以容错机制是不可或缺的。总的说来，MapReduce是通过重新执行失效的地方来实现容错的。
1．Master失效
在Master中，会周期性地设置检查点（checkpoint），并导出Master的数据。一旦某个任务失效了，就可以从最近的一个检查点恢复并重新执行。不过由于只有一个Master在运行，如果Master失效了，则只能终止整个MapReduce程序的运行并重新开始。
16 1
第2章 Google云计算原理 2．Worker失效
相对于Master失效而言，Worker失效算是一种常见的状态。Master会周期性地给Worker发送ping命令，如果没有Worker的应答，则Master认为Worker失效，终止对这个Worker的任务调度，把失效Worker的任务调度到其他Worker上重新执行。
2.2.4 案例分析
单词计数（Word Count）是一个经典的问题，也是能体现MapReduce设计思想的最简单算法之一。该算法主要是为了完成对文字数据中所出现的单词进行计数，如图2-4所示。
图2-4 单词计数
伪代码如下：
Map(K,V){
For each word w in V Collect(w , 1); }
Reduce(K,V[ ]){ int count = 0; For each v in V count += v; Collect(K , count); }
下面就根据MapReduce的四个执行步骤对这一算法进行详细的介绍。
1）根据文件所包含的信息分割（Split）文件，在这里把文件的每行分割为一组，共三组，如图2-5所示。这一步由系统自动完成。
图2-5 分割过程
2）对分割之后的每一对
17 1 云计算
图2-6 Map过程
3）Map输出之后有一个内部的Fold过程，和第一步一样，都是由系统自动完成的，如图2-7所示。
图2-7 Fold过程
4）经过Fold步骤之后的输出与结果已经非常接近，再由用户定义的Reduce步骤完成最后的工作即可，如图2-8所示。
图2-8 Reduce过程
18 1
第2章 Google云计算原理 2.3 分布式锁服务Chubby
Chubby是Google设计的提供粗粒度锁服务的一个文件系统，它基于松耦合分布式系统，解决了分布的一致性问题。通过使用Chubby的锁服务，用户可以确保数据操作过程中的一致性。不过值得注意的是，这种锁只是一种建议性的锁（Advisory Lock）而不是强制性的锁（Mandatory Lock），如此选择的目的是使系统具有更大的灵活性。
GFS使用Chubby来选取一个GFS主服务器，Bigtable使用Chubby指定一个主服务器并发现、控制与其相关的子表服务器。除了最常用的锁服务之外，Chubby还可以作为一个稳定的存储系统存储包括元数据在类的小数据。同时Google内部还使用Chubby进行名字服务（Name Server）。本节首先简要介绍Paxos算法，因为Chubby内部一致性问题的实现用到了Paxos算法；然后围绕Chubby系统的设计和实现展开讲解。通过本节的学习读者应该对分布式系统中一致性问题的一般性算法有初步的了解，着重掌握Chubby系统设计和实现的精髓。
2.3.1 Paxos算法
Paxos算法[14][15]是由供职于微软的Leslie Lamport最先提出的一种基于消息传递（Messages Passing）的一致性算法。在目前所有的一致性算法中，该算法最常用且被认为是最有效的。要想了解Paxos算法，我们首先需要知道什么是分布式系统中的一致性问题，因为Paxos算法就是为了解决这个问题而提出的。简单地说分布式系统的一致性问题，就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时，看到的指令序列是完全一致的，并且最终得到完全一致的结果。在Lamport提出的Paxos算法中节点被分成了三种类型：proposers、acceptors和 learners。其中proposers 提出决议（Value），acceptors批准决议，learners获取并使用已经通过的决议。一个节点可以兼有多重类型。在这种情况下，满足以下三个条件[15]就可以保证数据的一致性：
1）决议只有在被 proposers 提出后才能批准。 2）每次只批准一个决议。
3）只有决议确定被批准后learners才能获取这个决议。
Lamport通过约束条件的不断加强，最后得到了一个可以实际运用到算法中的完整约束条件：如果一个编号为n的提案具有值v，那么存在一个多数派，要么他们中没有人批准过编号小于n的任何提案，要么他们进行的最近一次批准具有值 v。为了保证决议的唯一性，acceptors也要满足一个如下的约束条件：当且仅当 acceptors 没有收到编号大于n的请求时，acceptors 才批准编号为n的提案。
在这些约束条件的基础上，可以将一个决议的通过分成两个阶段。
1）准备阶段：proposers选择一个提案并将它的编号设为n，然后将它发送给acceptors中的一个多数派。Acceptors 收到后，如果提案的编号大于它已经回复的所有消息，则acceptors将自己上次的批准回复给proposers，并不再批准小于n的提案。
2）批准阶段：当proposers接收到acceptors 中的这个多数派的回复后，就向回复请求的acceptors发送accept请求，在符合acceptors一方的约束条件下，acceptors收到accept请求后即批准这个请求。
19 1 云计算
为了减少决议发布过程中的消息量，acceptors将这个通过的决议发送给learners 的一个子集，然后由这个子集中的learners 去通知所有其他的learners。一般情况下，以上的算法过程就可以成功地解决一致性问题，但是也有特殊情况。根据算法一个编号更大的提案会终止之前的提案过程，如果两个proposer在这种情况下都转而提出一个编号更大的提案，那么就可能陷入活锁。此时需要选举出一个president，仅允许 president提出提案。
以上只是简要地向大家介绍了Paxos算法的核心内容，关于更多的实现细节读者可以参考Lamport关于Paxos算法实现的文章。
2.3.2 Chubby系统设计
通常情况下Google的一个数据中心仅运行一个Chubby单元[13]（Chubby cell,下面会有详细讲解），而这个单元需要支持包括GFS、Bigtable在内的众多Google服务。这种苛刻的服务要求使得Chubby在设计之初就要充分考虑到系统需要实现的目标以及可能出现的各种问题。
Chubby的设计目标主要有以下几点。
1）高可用性和高可靠性。这是系统设计的首要目标，在保证这一目标的基础上再考虑系统的吞吐量和存储能力。
2）高扩展性。将数据存储在价格较为低廉的RAM，支持大规模用户访问文件。 3）支持粗粒度的建议性锁服务。提供这种服务的根本目的是提高系统的性能。
4）服务信息的直接存储。可以直接存储包括元数据、系统参数在内的有关服务信息，而不需要再维护另一个服务。
5）支持通报机制。客户可以及时地了解到事件的发生。
6）支持缓存机制。通过一致性缓存将常用信息保存在客户端，避免了频繁地访问主服务器。
前面提到在分布式系统中保持数据一致性最常用也最有效的算法是Paxos，很多系统就是将Paxos算法作为其一致性算法的核心。但是Google并没有直接实现一个包含了Paxos算法的函数库，相反，Google设计了一个全新的锁服务Chubby。Google做出这种设计主要是考虑到以下几个问题[13]。
1）通常情况下开发者在开发的初期很少考虑系统的一致性问题，但是随着开发的不断进行，这种问题会变得越来越严重。单独的锁服务可以保证原有系统的架构不会发生改变，而使用函数库的话很可能需要对系统的架构做出大幅度的改动。
2）系统中很多事件的发生是需要告知其他用户和服务器的，使用一个基于文件系统的锁服务可以将这些变动写入文件中。这样其他需要了解这些变动的用户和服务器直接访问这些文件即可，避免了因大量的系统组件之间的事件通信带来的系统性能下降。
3）基于锁的开发接口容易被开发者接受。虽然在分布式系统中锁的使用会有很大的不同，但是和一致性算法相比，锁显然被更多的开发者所熟知。
一般来说分布式一致性问题通过quorum机制（简单来说就是根据少数服从多数的选举原则产生一个决议）做出决策，为了保证系统的高可用性，需要若干台机器，但是使用单独的锁服务的话一台机器也能保证这种高可用性。也就是说，Chubby在自身服务的实现时利用若干台机器实现了高可用性，而外部用户利用Chubby则只需一台机器就可以保证高可用性。
20 2