第2章 Google云计算原理 不间断的数据存储服务是GFS最核心的问题。GFS的精彩在于它采用了多种方法，从多个角度，使用不同的容错措施来确保整个系统的可靠性。
2.1.1 系统架构
GFS的系统架构如图2-1[1]所示。GFS将整个系统的节点分为三类角色：Client（客户端）、Master（主服务器）和Chunk Server（数据块服务器）。Client是GFS提供给应用程序的访问接口，它是一组专用接口，不遵守POSIX规范，以库文件的形式提供。应用程序直接调用这些库函数，并与该库链接在一起。Master是GFS的管理节点，在逻辑上只有一个，它保存系统的元数据，负责整个文件系统的管理，是GFS文件系统中的大脑。Chunk Server负责具体的存储工作。数据以文件的形式存储在Chunk Server上，Chunk Server的个数可以有多个，它的数目直接决定了GFS的规模。GFS将文件按照固定大小进行分块，默认是64MB，每一块称为一个Chunk（数据块），每个Chunk都有一个对应的索引号（Index）。
图2-1 GFS体系结构
客户端在访问GFS时，首先访问Master节点，获取将要与之进行交互的Chunk Server信息，然后直接访问这些Chunk Server完成数据存取。GFS的这种设计方法实现了控制流和数据流的分离。Client与Master之间只有控制流，而无数据流，这样就极大地降低了Master的负载，使之不成为系统性能的一个瓶颈。Client与Chunk Server之间直接传输数据流，同时由于文件被分成多个Chunk进行分布式存储，Client可以同时访问多个Chunk Server，从而使得整个系统I/O高度并行，系统整体性能得到提高。
相对于传统的分布式文件系统，GFS针对Google应用的特点从多个方面进行了简化，从而在一定规模下达到成本、可靠性和性能的最佳平衡。具体来说，它具有以下几个特点。
1．采用中心服务器模式
GFS采用中心服务器模式来管理整个文件系统，可以大大简化设计，从而降低实现难度。Master管理了分布式文件系统中的所有元数据。文件划分为Chunk进行存储，对于Master来说，每个Chunk Server只是一个存储空间。Client发起的所有操作都需要先通过Master才能执行。这样做有许多好处，增加新的Chunk Server是一件十分容易的事情，
11 1 云计算
Chunk Server只需要注册到Master上即可，Chunk Server之间无任何关系。如果采用完全对等的、无中心的模式，那么如何将Chunk Server的更新信息通知到每一个Chunk Server，会是设计的一个难点，而这也将在一定程度上影响系统的扩展性。Master维护了一个统一的命名空间，同时掌握整个系统内Chunk Server的情况，据此可以实现整个系统范围内数据存储的负载均衡。由于只有一个中心服务器，元数据的一致性问题自然解决。当然，中心服务器模式也带来一些固有的缺点，比如极易成为整个系统的瓶颈等。GFS采用多种机制来避免Master成为系统性能和可靠性上的瓶颈，如尽量控制元数据的规模、对Master进行远程备份、控制信息和数据分流等。
2．不缓存数据
缓存机制是提升文件系统性能的一个重要手段，通用文件系统为了提高性能，一般需要实现复杂的缓存（Cache）机制。GFS文件系统根据应用的特点，没有实现缓存，这是从必要性和可行性两方面考虑的。从必要性上讲，客户端大部分是流式顺序读写，并不存在大量的重复读写，缓存这部分数据对系统整体性能的提高作用不大；而对于Chunk Server，由于GFS的数据在Chunk Server上以文件的形式存储，如果对某块数据读取频繁，本地的文件系统自然会将其缓存。从可行性上讲，如何维护缓存与实际数据之间的一致性是一个极其复杂的问题，在GFS中各个Chunk Server的稳定性都无法确保，加之网络等多种不确定因素，一致性问题尤为复杂。此外由于读取的数据量巨大，以当前的内存容量无法完全缓存。对于存储在Master中的元数据，GFS采取了缓存策略，GFS中Client发起的所有操作都需要先经过Master。Master需要对其元数据进行频繁操作，为了提高操作的效率，Master的元数据都是直接保存在内存中进行操作；同时采用相应的压缩机制降低元数据占用空间的大小，提高内存的利用率。
3．在用户态下实现
文件系统作为操作系统的重要组成部分，其实现通常位于操作系统底层。以Linux为例，无论是本地文件系统如Ext3文件系统，还是分布式文件系统如Lustre等，都是在内核态实现的。在内核态实现文件系统，可以更好地和操作系统本身结合，向上提供兼容的POSIX接口。然而，GFS却选择在用户态下实现，主要基于以下考虑。
1）在用户态下实现，直接利用操作系统提供的POSIX编程接口就可以存取数据，无需了解操作系统的内部实现机制和接口，从而降低了实现的难度，并提高了通用性。
2）POSIX接口提供的功能更为丰富，在实现过程中可以利用更多的特性，而不像内核编程那样受限。
3）用户态下有多种调试工具，而在内核态中调试相对比较困难。
4）用户态下，Master和Chunk Server都以进程的方式运行，单个进程不会影响到整个操作系统，从而可以对其进行充分优化。在内核态下，如果不能很好地掌握其特性，效率不但不会高，甚至还会影响到整个系统运行的稳定性。
5）用户态下，GFS和操作系统运行在不同的空间，两者耦合性降低，从而方便GFS自身和内核的单独升级。
4．只提供专用接口
通常的分布式文件系统一般都会提供一组与POSIX规范兼容的接口。其优点是应用程序可以通过操作系统的统一接口来透明地访问文件系统，而不需要重新编译程序。GFS在设计之初，是完全面向Google的应用的，采用了专用的文件系统访问接口。接口以库
12 1
第2章 Google云计算原理 文件的形式提供，应用程序与库文件一起编译，Google应用程序在代码中通过调用这些库文件的API，完成对GFS文件系统的访问。采用专用接口有以下好处。
1）降低了实现的难度。通常与POSIX兼容的接口需要在操作系统内核一级实现，而GFS是在应用层实现的。
2）采用专用接口可以根据应用的特点对应用提供一些特殊支持，如支持多个文件并发追加的接口等。
3）专用接口直接和Client、Master、Chunk Server交互，减少了操作系统之间上下文的切换，降低了复杂度，提高了效率。
2.1.2 容错机制
1．Master容错
具体来说，Master上保存了GFS文件系统的三种元数据。 1）命名空间（Name Space），也就是整个文件系统的目录结构。 2）Chunk与文件名的映射表。
3）Chunk副本的位置信息，每一个Chunk默认有三个副本。
首先就单个Master来说，对于前两种元数据，GFS通过操作日志来提供容错功能。第三种元数据信息则直接保存在各个Chunk Server上，当Master启动或Chunk Server向Master注册时自动生成。因此当Master发生故障时，在磁盘数据保存完好的情况下，可以迅速恢复以上元数据。为了防止Master彻底死机的情况，GFS还提供了Master远程的实时备份，这样在当前的GFS Master出现故障无法工作的时候，另外一台GFS Master可以迅速接替其工作。
2．Chunk Server容错
GFS采用副本的方式实现Chunk Server的容错。每一个Chunk有多个存储副本（默认为三个），分布存储在不同的Chunk Server上。副本的分布策略需要考虑多种因素，如网络的拓扑、机架的分布、磁盘的利用率等。对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入。在其后的过程中，如果相关的副本出现丢失或不可恢复等状况，Master会自动将该副本复制到其他Chunk Server，从而确保副本保持一定的个数。尽管一份数据需要存储三份，好像磁盘空间的利用率不高，但综合比较多种因素，加之磁盘的成本不断下降，采用副本无疑是最简单、最可靠、最有效，而且实现的难度也最小的一种方法。
GFS中的每一个文件被划分成多个Chunk，Chunk的默认大小是64MB，这是因为Google应用中处理的文件都比较大，以64MB为单位进行划分，是一个较为合理的选择。Chunk Server存储的是Chunk的副本，副本以文件的形式进行存储。每一个Chunk以Block为单位进行划分，大小为64KB，每一个Block对应一个32bit的校验和。当读取一个Chunk副本时，Chunk Server会将读取的数据和校验和进行比较，如果不匹配，就会返回错误，从而使Client选择其他Chunk Server上的副本。
2.1.3 系统管理技术
严格意义上来说，GFS是一个分布式文件系统，包含从硬件到软件的整套解决方案。除了上面提到的GFS的一些关键技术外，还有相应的系统管理技术来支持整个GFS的应
13 1 云计算
用，这些技术可能并不一定为GFS所独有。
1．大规模集群安装技术
安装GFS的集群中通常有非常多的节点，文献[1]中最大的集群超过1000个节点，而现在的Google数据中心动辄有万台以上的机器在运行。那么，迅速地安装、部署一个GFS的系统，以及迅速地进行节点的系统升级等，都需要相应的技术支撑。
2．故障检测技术
GFS是构建在不可靠的廉价计算机之上的文件系统，由于节点数目众多，故障发生十分频繁，如何在最短的时间内发现并确定发生故障的Chunk Server，需要相关的集群监控技术。
3．节点动态加入技术
当有新的Chunk Server加入时，如果需要事先安装好系统，那么系统扩展将是一件十分烦琐的事情。如果能够做到只需将裸机加入，就会自动获取系统并安装运行，那么将会大大减少GFS维护的工作量。
4．节能技术
有关数据表明，服务器的耗电成本大于当初的购买成本，因此Google采用了多种机制来降低服务器的能耗，例如对服务器主板进行修改，采用蓄电池代替昂贵的UPS（不间断电源系统），提高能量的利用率。Rich Miller 在一篇关于数据中心的博客文章中表示，这个设计让 Google 的 UPS 利用率达到99.9%，而一般数据中心只能达到92%～95%。
2.2 并行数据处理MapReduce
MapReduce是Google提出的一个软件架构，是一种处理海量数据的并行编程模式，用于大规模数据集（通常大于1TB）的并行运算。“Map（映射）”、“Reduce（化简）”的概念和主要思想，都是从函数式编程语言和矢量编程语言借鉴来的[5]。正是由于MapReduce有函数式和矢量编程语言的共性，使得这种编程模式特别适合于非结构化和结构化的海量数据的搜索、挖掘、分析与机器智能学习等。
2.2.1 产生背景
MapReduce这种并行编程模式思想最早是在1995年提出的，文献[6]首次提出了“map”和“fold”的概念，和现在Google所使用的“Map”和“Reduce”思想是相吻合的。
与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。通过这个接口，可以把大尺度的计算自动地并发和分布执行，从而使编程变得非常容易。还可以通过由普通PC构成的巨大集群来达到极高的性能。另外，MapReduce也具有较好的通用性，大量不同的问题都可以简单地通过MapReduce来解决。
MapReduce把对数据集的大规模操作，分发给一个主节点管理下的各分节点共同完成，通过这种方式实现任务的可靠执行与容错机制。在每个时间周期，主节点都会对分节点的工作状态进行标记，一旦分节点状态标记为死亡状态，则这个节点的所有任务都将分配给其他分节点重新执行。
14 1
第2章 Google云计算原理 据相关统计，每使用一次Google搜索引擎，Google的后台服务器就要进行1011次运算。这么庞大的运算量，如果没有好的负载均衡机制，有些服务器的利用率会很低，有些则会负荷太重，有些甚至可能死机，这些都会影响系统对用户的服务质量。而使用MapReduce这种编程模式，就保持了服务器之间的均衡，提高了整体效率。
2.2.2 编程模型
MapReduce的运行模型如图2-2所示。图中有M个Map操作和R个Reduce操作。 简单地说，一个Map函数就是对一部分原始数据进 原始数据1 原始数据2 原始数据M 行指定的操作。每个Map操作都针对不同的原始数据，因此Map与Map之间是互相独立的，这就使得它们可以Map Map ? Map 充分并行化。一个Reduce操作就是对每个Map所产生的一部分中间结果进行合并操作，每个Reduce所处理的Map中间结果是互不交叉的，所有Reduce产生的最终结
Reduce ? Reduce 果经过简单连接就形成了完整的结果集，因此Reduce也可以在并行环境下执行。
结果1 结果R 在编程的时候，开发者需要编写两个主要函数： Map: (in_key, in_value) ? {(keyj, valuej) | j = 1…k} 图2-2 MapReduce的运行模型
Reduce: (key, [value1,…,valuem]) ? (key, final_value)
Map和Reduce的输入参数和输出结果根据应用的不同而有所不同。Map的输入参数是in_key和in_value，它指明了Map需要处理的原始数据是哪些。Map的输出结果是一组
例如，假设我们想用MapReduce来计算一个大型文本文件中各个单词出现的次数，Map的输入参数指明了需要处理哪部分数据，以<在文本中的起始位置，需要处理的数据长度>表示，经过Map处理，形成一批中间结果<单词，出现次数>。而Reduce函数则是把中间结果进行处理，将相同单词出现的次数进行累加，得到每个单词总的出现次数。
2.2.3 实现机制
实现MapReduce操作的执行流程图[7]如图2-3所示。
当用户程序调用MapReduce函数，就会引起如下操作（图中的数字标示和下面的数字标示相同）。
1）用户程序中的MapReduce函数库首先把输入文件分成M块，每块大概16M～64MB（可以通过参数决定），接着在集群的机器上执行处理程序。
2）这些分派的执行程序中有一个程序比较特别，它是主控程序Master。剩下的执行程序都是作为Master分派工作的Worker（工作机）。总共有M个Map任务和R个Reduce任务需要分派，Master选择空闲的Worker来分配这些Map或者Reduce任务。
15 1