云计算初探

http://pan.baidu.com/share/link?shareid=514281&uk=4010979762

网盘内为文章的word版本。。。。。。

云计算技术分析

数据库专题作业

前言

对于云计算，在我看来更多的是一种商业的广告效应而非真正的技术应用，具体而言就是希望获得一种动态分配资源、高效高可靠性并且使用廉价的计算资源和存储资源，通过向用户提供这些资源进行收费以达到盈利的目的。

云计算主要的技术集中在三个方面：分布式存储和计算、系统稳定性保障以及网络通信安全。其中，分布式存储和计算是整个云计算系统的核心，提供客户的基本应用；系统稳定性保障是要求，云计算所使用的平台并不能总是保障每个节点的稳定性，所以需要通过冗余备份保障整个系统的数据完备；网络通信安全是保障，云计算搭建在互联网上，对公司敏感的数据或是可以通过数据挖掘获得敏感信息的数据在公共网络上传输，容易造成敏感信息泄露，这三个技术缺一不可，任何一个技术都是云计算作为一个理念的基本组成部分。本文主要涉及云计算的基础部分，关于如何在由多个相互之间使用网络通信互联的处理机构建的计算平台上进行数据的存储和计算。

由于篇幅所限，本文并未涉及云计算所特别强调的虚拟化技术，主要是由于现有的云计算平台对于虚拟化技术的具体讲述并不确切，而理论上虚拟化技术又只是计算机体系结构当中非常常用的一个概念而云计算领域这个概念并无特殊含义，所以本文并不涉及对虚拟化技术的描述。

本文主要分成个部分：首先对云计算进行基本的概述，讲述云计算作为一个新兴理论的特点和已有的应有；接下来对云计算的存储进行简单分析，着重分析hadoop的HDFS文件管理系统；第三章和第四章两个章节，讲述了云计算平台上两个比较有特点的计算框架MapReduce和BSP；在第五章，通过几个具体的应用，具体阐述了云计算的应用方式。

由于本人学识所限，文中必然存在疏漏，所以希望读者不吝赐教。如果文中有明显错误，请在老师在博客回复。

第1章云计算初探

——无论商业运作如何红火，冰冷的代码总能平静浮躁的心灵

云的基本概念，是通过网络将庞大的计算处理程序自动分拆成无数个较小的子程序，再由多部服务器所组成的庞大系统搜索、计算分析之后将处理结果回传给用户。通过这项技术，远程的服务供应商可以在数秒之内，达成处理数以千万计甚至亿计的信息，达到和“超级电脑”同样强大性能的网络服务。

云计算就是将多个计算机组成一个网络，然后通过网络的数据传输机制，完成计算任务和结果返回，在这一过程中，作为一个计算，着重考虑的就是数据的存储和数据的计算。

云计算通常分成四个种类，分别对应计算机不同的处理层面，而作为一个整体可以视为一个完整的超级计算机，只不过这个超级计算机，是通过多台计算机提供计算，通过网络进行通信，通过不同类型的终端提供服务。

1.1 IaaS

IaaS(Infrastructure-as-a- Service)：基础设施即服务。消费者通过Internet可以从完善的计算机基础设施获得服务。

这类应用包括各种数据中心，计算中心以及在此基础上搭建的云平台，在中国，阿里云提供一个“高效的绿色数据中心以及能支持不同互联网应用的大规模分布式存储应用”就是这类应用的典型代表。

Iaas通过网络向用户提供计算机（物理机和虚拟机）、存储空间、网络连接、负载均衡和防火墙等基本计算资源；用户在此基础上部署和运行各种软件，包括操作系统和应用程序。

1.2 PaaS

PaaS(Platform-as-a- Service)：平台即服务。PaaS实际上是指将软件研发的平台作为一种服务，以SaaS的模式提交给用户。因此，PaaS也是SaaS模式的一种应用。但是，PaaS的出现可以加快SaaS的发展，尤其是加快SaaS应用的开发速度。

同样以阿里云为例，作为中国目前最成功的云平台，阿里云也提供了云计算平台服务。飞天开放平台（Apsara）负责管理数据中心Linux集群的物理资源，控制分布式程序运行，隐藏下层故障恢复和数据冗余等细节，从而将数以千计的服务器联成一台“超级计算机”，并且将这台超级计算机的存储资源和计算资源，以公共服务的方式提供给互联网上的用户。

通常情况下，平台通常包括操作系统、编程语言的运行环境、数据库和 Web 服务器，用户在此平台上部署和运行自己的应用。用户不能管理和控制底层的基础设施，只能控制自己部署的应用。

1.3 SaaS

SaaS(Software-as-a- Service)：软件即服务。它是一种通过Internet提供软件的模式，用户无需购买软件，而是向提供商租用基于Web的软件，来管理企业经营活动。

在中国，云软件服务，通常包括地图、搜索、邮件、云空间以及帐号、支付、天气、翻译等基础云服务，阿里云官网为这些服务提供了统一的访问入口。

云提供商在云端安装和运行应用软件，云用户通过云客户端（通常是 Web 浏览器）使用软件。云用户不能管理应用软件运行的基础设施和平台，只能做有限的应用程序设置。

1.4 ACaaS

ACaaS（Access control as a Service）：门禁即服务，是基于云技术的门禁控制，当今市场有两种典型的门禁即服务：真正的云服务与机架服务器托管。真正的云服务是具备多租户、可扩展及冗余特点的服务，需要构建专用的数据中心，而提供多租户解决方案也是一项复杂工程，因此会导致高昂的成本，所以大部分的门禁即服务仍属于机架服务器托管，而非真正的云服务。

也许上述的名词缩写让人无所适从，但是这些事实上就是一些商业分类，做硬件的说自己是IaaS，做平台的大公司都会提自己公司PaaS的平台的技术特点，外包和具体应用，如果平台搭建在分布式环境下，当然就可以毫不客气的宣称自己的应用是SaaS；而ACaaS，作为一个新兴的概念，似乎是为了那些无法在云计算领域上插一脚的运维公司而量身定做。当电视的在线点播都能够与云计算扯上关系的时代，云计算的核心——数据的云端存储和应用于云端运行，作为一个基础应该受到技术人员更多的关注。

第2章分布式文件管理系统

——数据是计算的灵魂

计算机计算任务核心就是如何处理各种数据，云计算需要处理的数据来自多个处理机，这就需要一个分布式文件管理系统进行数据管理，这也是云计算的核心环节，如何高效的管理分布在不同计算机上的数据。

目前的分布式文件系统，不仅仅用在云计算领域，传统的分布式计算领域也有广泛的应用，现今已有大量的商用或是开源的分布式文件系统可供使用，下面就对数种分布式文件系统进行简单的介绍。当前比较流行的分布式文件系统包括：Lustre、Hadoop、MogileFS、FreeNAS、FastDFS、NFS、OpenAFS、MooseFS、pNFS、以及GoogleFS。

在本章中，首先以Hadoop的HDFS文件管理系统为例，讲述分布式文件管理形体的具体特点，在了解了HDFS这种相对比较流行的文件管理系统之后，再对其他的应用于云平台的分布式文件系统进行简单的分析，具体说明这些文件管理系统的特点。分布式文件系统，架设在多台计算机之上，在获得较大的存储空间的基础上，也带来了极大的不稳定性，多处理机文件系统有着与单处理机相当不同的差异。分布式文件管理系统有如下特点（以HDFS为例）：

硬件错误是常态，而非异常情况，HDFS可能是有成百上千的server组成，任何一个组件都有可能一直失效，因此错误检测和快速、自动的恢复是HDFS的核心架构目标。
跑在HDFS上的应用与一般的应用不同，它们主要是以流式读为主，做批量处理；比之关注数据访问的低延迟问题，更关键的在于数据访问的高吞吐量。
HDFS以支持大数据集合为目标，一个存储在上面的典型文件大小一般都在千兆至T字节，一个单一HDFS实例应该能支撑数以千万计的文件。
HDFS应用对文件要求的是write-one-read-many访问模型。一个文件经过创建、写，关闭之后就不需要改变。这一假设简化了数据一致性问题，使高吞吐量的数据访问成为可能。典型的如MapReduce框架，或者一个web crawler应用都很适合这个模型。
移动计算的代价比之移动数据的代价低。一个应用请求的计算，离它操作的数据越近就越高效，这在数据达到海量级别的时候更是如此。将计算移动到数据附近，比之将数据移动到应用所在显然更好，HDFS提供给应用这样的接口。
在异构的软硬件平台间的可移植性。

2.1 HDFS系统概述

2.1.1 HDFS采用master/slave架构。

一个HDFS集群是有一个Namenode和一定数目的Datanode组成。Namenode是一个中心服务器，负责管理文件系统的namespace和客户端对文件的访问。Datanode在集群中一般是一个节点一个，负责管理节点上它们附带的存储。在内部，一个文件其实分成一个或多个block，这些block存储在Datanode集合里。Namenode执行文件系统的namespace操作，例如打开、关闭、重命名文件和目录，同时决定block到具体Datanode节点的映射。Datanode在Namenode的指挥下进行block的创建、删除和复制。Namenode和Datanode都是设计成可以跑在普通的廉价的运行linux的机器上。HDFS采用java语言开发，因此可以部署在很大范围的机器上。一个典型的部署场景是一台机器跑一个单独的Namenode节点，集群中的其他机器各跑一个Datanode实例。这个架构并不排除一台机器上跑多个Datanode，不过这比较少见。

单一节点的Namenode大大简化了系统的架构。Namenode负责保管和管理所有的HDFS元数据，因而用户数据就不需要通过Namenode（也就是说文件数据的读写是直接在Datanode上）。

2.2 HDFS数据操作

任何的文件系统，都要支持用户对数据的读取和写入这两个基本操作，HDFS作为一个设计之时就定位为处理大规模计算的分布式文件系统，适合处理频繁数据读取的计算任务而不适合处理需要频繁数据写入的计算任务。比较常见的对HDFS的应用，都是一次数据写入，多次数据使用。

HDFS为了支持对数据的并行读取，有一套自己独有的数据管理机制，不同于通常操作系统的文件管理使用的B树结构，HDFS将更多的关注放在数据安全和数据备份，并且由于数据分布在多个处理机上，数据可能通过网络进行通信，在这种情况下，HDFS定义了自己的网络通信接口，通过更加高效和全局的通信空间进行数据的转移和数据备份。不过由于数据从多个处理机之间进行数据传递需要大量的网络通信代价，所以通常情况下，与其传递计算数据，不如传递计算任务。

2.2.1 HDFS文件系统的namespace

HDFS支持传统的层次型文件组织，与大多数其他文件系统类似，用户可以创建目录，并在其间创建、删除、移动和重命名文件。HDFS不支持user quotas和访问权限，也不支持链接（link)，不过当前的架构并不排除实现这些特性。Namenode维护文件系统的namespace，任何对文件系统namespace和文件属性的修改都将被Namenode记录下来。应用可以设置HDFS保存的文件的副本数目，文件副本的数目称为文件的 replication因子，这个信息也是由Namenode保存。

2.2.2 HDFS数据复制

HDFS被设计成在一个大集群中可以跨机器地可靠地存储海量的文件。它将每个文件存储成block序列，除了最后一个block，所有的block都是同样的大小。文件的所有block为了容错都会被复制。每个文件的block大小和replication因子都是可配置的。Replication因子可以在文件创建的时候配置，以后也可以改变。HDFS中的文件是write-one，并且严格要求在任何时候只有一个writer。Namenode全权管理block的复制，它周期性地从集群中的每个Datanode接收心跳包和一个Blockreport。心跳包的接收表示该Datanode节点正常工作，而Blockreport包括了该Datanode上所有的block组成的列表。

副本的存放

副本的存放是HDFS可靠性和性能的关键。HDFS采用一种称为rack-aware的策略来改进数据的可靠性、有效性和网络带宽的利用。这个策略实现的短期目标是验证在生产环境下的表现，观察它的行为，构建测试和研究的基础，以便实现更先进的策略。庞大的HDFS实例一般运行在多个机架的计算机形成的集群上，不同机架间的两台机器的通讯需要通过交换机，显然通常情况下，同一个机架内的两个节点间的带宽会比不同机架间的两台机器的带宽大。

通过一个称为Rack Awareness的过程，Namenode决定了每个Datanode所属的rack id。一个简单但没有优化的策略就是将副本存放在单独的机架上。这样可以防止整个机架（非副本存放）失效的情况，并且允许读数据的时候可以从多个机架读取。这个简单策略设置可以将副本分布在集群中，有利于组件失败情况下的负载均衡。但是，这个简单策略加大了写的代价，因为一个写操作需要传输block到多个机架。

在大多数情况下，replication因子是3，HDFS的存放策略是将一个副本存放在本地机架上的节点，一个副本放在同一机架上的另一个节点，最后一个副本放在不同机架上的一个节点。机架的错误远远比节点的错误少，这个策略不会影响到数据的可靠性和有效性。三分之一的副本在一个节点上，三分之二在一个机架上，其他保存在剩下的机架中，这一策略改进了写的性能。

副本的选择

为了降低整体的带宽消耗和读延时，HDFS会尽量让reader读最近的副本。如果在reader的同一个机架上有一个副本，那么就读该副本。如果一个HDFS集群跨越多个数据中心，那么reader也将首先尝试读本地数据中心的副本。

SafeMode

Namenode启动后会进入一个称为SafeMode的特殊状态，处在这个状态的Namenode是不会进行数据块的复制的。Namenode从所有的 Datanode接收心跳包和Blockreport。Blockreport包括了某个Datanode所有的数据块列表。每个block都有指定的最小数目的副本。当Namenode检测确认某个Datanode的数据块副本的最小数目，那么该Datanode就会被认为是安全的；如果一定百分比（这个参数可配置）的数据块检测确认是安全的，那么Namenode将退出SafeMode状态，接下来它会确定还有哪些数据块的副本没有达到指定数目，并将这些block复制到其他Datanode。

2.2.3 文件系统元数据的持久化

Namenode存储HDFS的元数据。对于任何对文件元数据产生修改的操作，Namenode都使用一个称为Editlog的事务日志记录下来。例如，在HDFS中创建一个文件，Namenode就会在Editlog中插入一条记录来表示；同样，修改文件的replication因子也将往 Editlog插入一条记录。Namenode在本地OS的文件系统中存储这个Editlog。整个文件系统的namespace，包括block到文件的映射、文件的属性，都存储在称为FsImage的文件中，这个文件也是放在Namenode所在系统的文件系统上。

Namenode在内存中保存着整个文件系统namespace和文件Blockmap的映像。这个关键的元数据设计得很紧凑，因而一个带有4G内存的 Namenode足够支撑海量的文件和目录。当Namenode启动时，它从硬盘中读取Editlog和FsImage，将所有Editlog中的事务作用（apply)在内存中的FsImage ，并将这个新版本的FsImage从内存中flush到硬盘上,然后再truncate这个旧的Editlog，因为这个旧的Editlog的事务都已经作用在FsImage上了。这个过程称为checkpoint。在当前实现中，checkpoint只发生在Namenode启动时，在不久的将来我们将实现支持周期性的checkpoint。

Datanode并不知道关于文件的任何东西，除了将文件中的数据保存在本地的文件系统上。它把每个HDFS数据块存储在本地文件系统上隔离的文件中。 Datanode并不在同一个目录创建所有的文件，相反，它用启发式地方法来确定每个目录的最佳文件数目，并且在适当的时候创建子目录。在同一个目录创建所有的文件不是最优的选择，因为本地文件系统可能无法高效地在单一目录中支持大量的文件。当一个Datanode启动时，它扫描本地文件系统，对这些本地文件产生相应的一个所有HDFS数据块的列表，然后发送报告到Namenode，这个报告就是Blockreport。

数据组织

1、数据块

兼容HDFS的应用都是处理大数据集合的。这些应用都是写数据一次，读却是一次到多次，并且读的速度要满足流式读。HDFS支持文件的write- once-read-many语义。一个典型的block大小是64MB，因而，文件总是按照64M切分成chunk，每个chunk存储于不同的 Datanode

2、步骤

某个客户端创建文件的请求其实并没有立即发给Namenode，事实上，HDFS客户端会将文件数据缓存到本地的一个临时文件。应用的写被透明地重定向到这个临时文件。当这个临时文件累积的数据超过一个block的大小（默认64M)，客户端才会联系Namenode。Namenode将文件名插入文件系统的层次结构中，并且分配一个数据块给它，然后返回Datanode的标识符和目标数据块给客户端。客户端将本地临时文件flush到指定的 Datanode上。当文件关闭时，在临时文件中剩余的没有flush的数据也会传输到指定的Datanode，然后客户端告诉Namenode文件已经关闭。此时Namenode才将文件创建操作提交到持久存储。如果Namenode在文件关闭前挂了，该文件将丢失。

上述方法是对通过对HDFS上运行的目标应用认真考虑的结果。如果不采用客户端缓存，由于网络速度和网络堵塞会对吞估量造成比较大的影响。

3、流水线复制

当某个客户端向HDFS文件写数据的时候，一开始是写入本地临时文件，假设该文件的replication因子设置为3，那么客户端会从Namenode 获取一张Datanode列表来存放副本。然后客户端开始向第一个Datanode传输数据，第一个Datanode一小部分一小部分（4kb)地接收数据，将每个部分写入本地仓库，并且同时传输该部分到第二个Datanode节点。第二个Datanode也是这样，边收边传，一小部分一小部分地收，存储在本地仓库，同时传给第三个Datanode，第三个Datanode就仅仅是接收并存储了。这就是流水线式的复制。

2.3 HDFS系统数据交互

2.3.1 通讯协议

所有的HDFS通讯协议都是构建在TCP/IP协议上。客户端通过一个可配置的端口连接到Namenode，通过ClientProtocol与 Namenode交互。而Datanode是使用DatanodeProtocol与Namenode交互。从ClientProtocol和 Datanodeprotocol抽象出一个远程调用(RPC），在设计上，Namenode不会主动发起RPC，而是是响应来自客户端和 Datanode 的RPC请求。

2.3.2 健壮性

HDFS的主要目标就是实现在失败情况下的数据存储可靠性。常见的三种失败：Namenode failures, Datanode failures和网络分割（network partitions)。

l 硬盘数据错误、心跳检测和重新复制

每个Datanode节点都向Namenode周期性地发送心跳包。网络切割可能导致一部分Datanode跟Namenode失去联系。 Namenode通过心跳包的缺失检测到这一情况，并将这些Datanode标记为dead，不会将新的IO请求发给它们。寄存在dead Datanode上的任何数据将不再有效。Datanode的死亡可能引起一些block的副本数目低于指定值，Namenode不断地跟踪需要复制的 block，在任何需要的情况下启动复制。在下列情况可能需要重新复制：某个Datanode节点失效，某个副本遭到损坏，Datanode上的硬盘错误，或者文件的replication因子增大。

l 集群均衡

HDFS支持数据的均衡计划，如果某个Datanode节点上的空闲空间低于特定的临界点，那么就会启动一个计划自动地将数据从一个Datanode搬移到空闲的Datanode。当对某个文件的请求突然增加，那么也可能启动一个计划创建该文件新的副本，并分布到集群中以满足应用的要求。这些均衡计划目前还没有实现。

l 数据完整性

从某个Datanode获取的数据块有可能是损坏的，这个损坏可能是由于Datanode的存储设备错误、网络错误或者软件bug造成的。HDFS客户端软件实现了HDFS文件内容的校验和。当某个客户端创建一个新的HDFS文件，会计算这个文件每个block的校验和，并作为一个单独的隐藏文件保存这些校验和在同一个HDFS namespace下。当客户端检索文件内容，它会确认从Datanode获取的数据跟相应的校验和文件中的校验和是否匹配，如果不匹配，客户端可以选择从其他Datanode获取该block的副本。

l 元数据磁盘错误

FsImage和Editlog是HDFS的核心数据结构。这些文件如果损坏了，整个HDFS实例都将失效。因而，Namenode可以配置成支持维护多个FsImage和Editlog的拷贝。任何对FsImage或者Editlog的修改，都将同步到它们的副本上。这个同步操作可能会降低 Namenode每秒能支持处理的namespace事务。这个代价是可以接受的，因为HDFS是数据密集的，而非元数据密集。当Namenode重启的时候，它总是选取最近的一致的FsImage和Editlog使用。

Namenode在HDFS是单点存在，如果Namenode所在的机器错误，手工的干预是必须的。目前，在另一台机器上重启因故障而停止服务的Namenode这个功能还没实现。

l 快照

快照支持某个时间的数据拷贝，当HDFS数据损坏的时候，可以恢复到过去一个已知正确的时间点。HDFS目前还不支持快照功能。

2.3.3 可访问性

HDFS给应用提供了多种访问方式，可以通过DFSShell通过命令行与HDFS数据进行交互，可以通过java API调用，也可以通过C语言的封装API访问，并且提供了浏览器访问的方式。正在开发通过WebDav协议访问的方式。具体使用参考文档。

l 空间的回收

1、文件的删除和恢复

用户或者应用删除某个文件，这个文件并没有立刻从HDFS中删除。相反，HDFS将这个文件重命名，并转移到/trash目录。当文件还在/trash目录时，该文件可以被迅速地恢复。文件在/trash中保存的时间是可配置的，当超过这个时间，Namenode就会将该文件从namespace中删除。文件的删除，也将释放关联该文件的数据块。注意到，在文件被用户删除和HDFS空闲空间的增加之间会有一个等待时间延迟。

当被删除的文件还保留在/trash目录中的时候，如果用户想恢复这个文件，可以检索浏览/trash目录并检索该文件。/trash目录仅仅保存被删除文件的最近一次拷贝。/trash目录与其他文件目录没有什么不同，除了一点：HDFS在该目录上应用了一个特殊的策略来自动删除文件，目前的默认策略是删除保留超过6小时的文件，这个策略以后会定义成可配置的接口。

2、Replication因子的减小

当某个文件的replication因子减小，Namenode会选择要删除的过剩的副本。下次心跳检测就将该信息传递给Datanode， Datanode就会移除相应的block并释放空间，同样，在调用setReplication方法和集群中的空闲空间增加之间会有一个时间延迟。

2.4 现有的文件管理系统

2.4.1 Hadoop（hadoop.apache.com）

　　hadoop并不仅仅是一个用于存储的分布式文件系统，而是设计用来在由通用计算设备组成的大型集群上执行分布式应用的框架。

　　如下图是hadoop的体系结构：

　　授权协议apache,开发语言java。

2.4.2 googleFs

GFS是一个比较不错的一个可扩展分布式文件系统，用于大型的，分布式的，对大量数据进行访问的应用。它运行于廉价的普通硬件上，但可以提供容错功能，它可以给大量的用户提供性能较高的服务。google自己开发的。

它的设计原则是：

部件错误不再被当作异常，而是将其作为常见的情况加以处理。因为文件系统由成百上千个用于存储的机器构成，而这些机器是由廉价的普通部件组成并被大量的客户机访问。部件的数量和质量使得一些机器随时都有可能无法工作并且有一部分还可能无法恢复。所以实时地监控、错误检测、容错、自动恢复对系统来说必不可少。按照传统的标准，文件都非常大。长度达几个GB的文件是很平常的。每个文件通常包含很多应用对象。当经常要处理快速增长的、包含数以万计的对象、长度达TB的数据集时，我们很难管理成千上万的KB规模的文件块，即使底层文件系统提供支持。因此，设计中操作的参数、块的大小必须要重新考虑。对大型的文件的管理一定要能做到高效，对小型的文件也必须支持，但不必优化。
大部分文件的更新是通过添加新数据完成的，而不是改变已存在的数据。在一个文件中随机的操作在实践中几乎不存在。一旦写完，文件就只可读，很多数据都有这些特性。一些数据可能组成一个大仓库以供数据分析程序扫描。有些是运行中的程序连续产生的数据流。有些是档案性质的数据，有些是在某个机器上产生、在另外一个机器上处理的中间数据。由于这些对大型文件的访问方式，添加操作成为性能优化和原子性保证的焦点。而在客户机中缓存数据块则失去了吸引力。
工作量主要由两种读操作构成：对大量数据的流方式的读操作和对少量数据的随机方式的读操作。在前一种读操作中，可能要读几百KB，通常达1MB和更多。来自同一个客户的连续操作通常会读文件的一个连续的区域。随机的读操作通常在一个随机的偏移处读几个KB。性能敏感的应用程序通常将对少量数据的读操作进行分类并进行批处理以使得读操作稳定地向前推进，而不要让它来来回回的读。
工作量还包含许多对大量数据进行的、连续的、向文件添加数据的写操作。所写的数据的规模和读相似。一旦写完，文件很少改动。在随机位置对少量数据的写操作也支持，但不必非常高效。
系统必须高效地实现定义完好的大量客户同时向同一个文件的添加操作的语义。

2.4.3 Lustre（www.lustre.org）

lustre是一个大规模的、安全可靠的，具备高可用性的集群文件系统，它是由SUN公司开发和维护。该项目主要的目的就是开发下一代的集群文件系统，可以支持超过10000个节点，数以PB的数量存储系统。

Lustre是HP， Intel，Cluster File System公司联合美国能源部开发的Linux集群并行文件系统。该系统目前推出 1.0 的发布版本，是第一个基于对象存储设备的，开源的并行文件系统。其结构如图所示，它由客户端，两个MDS，OSD 设备池通过高速的以太网或 QWS Net 所构成。目前可以支持 lustre 系统结构

1000 个客户端节点的 I/O 请求，两个 MDS 采用共享存储设备的 Active－Standby方式的容错机制，存储设备跟普通的，基于块的 IDE 存储设备不同，是基于对象的智能存储设备。Lustre 采用分布式的锁管理机制来实现并发控制，元数据和文件数据的通讯链路分开管理。与 PVFS 相比，Lustre 虽然在性能，可用行和扩展性上略胜一踌，但它需要特殊设备的支持，而且分布式的元数据服务器管理还没有实现。

运行在linux下,开发语言c/c++

2.4.4 其他分布式文件系统

l MogileFs（www.danga.com）

　　Mogile Fs是一个开源的分布式文件系统，主要特征包括：

　　1、应用层的组件

　　2、无单点故障

　　3、自动文件复制

　　4、具有比RAID更好的可靠性

　　5、无需RAID nigukefs支持，运行在linux下。

l FreeNAS（www.openqrm.org）

　　FreeNAS是网络附加存储(NAS)服务专用操作系统(FreeBSD的简化版 )。基于m0n0wall防火墙，该系统通过提供磁盘管理及RAID软件，可让用户home将PC转换为NAS服务器，支持FTP/NFS/RSYNC/CIFS/AFP/UNISON/SSH sourceforge.net/pro协议，旨在让人们重新使用旧硬件.

l FastDFS（code.google.com/p/fastdfs）

　　FastDFS是一个开源的分布式文件系统，它对文件进行管理，功能包括:文件存储、文件同步、文件访问(文件上传、文件下载)等，解决了大容量存储和负载均衡的问题。

　　开发语言c/c++，运行在linux系统下。

l NFS（www.tldp.org/HOWTO/NFS-HOWTO/index.html）

　　网络文件系统是FreeBSD支持的文件系统中的一种，也被称为NFS。

　　NFS允许一个系统在网络上与它人共享目录和文件。通过使用NFS，用户和程序可以象访问本地文件一样访问远端系统上的文件。

　　开发语言c/c++,可跨平台运行。

l OpenAFS（www.openafs.org）

OpenAFS是一套开放源代码的分布式文件系统，允许系统之间通过局域网和广域网来分享档案和资源。

这不是基于通常的Linux和Unix安全模型。开发协议IBM Public，运行在linux下。

l MooseFs（derf.homelinux.org）

　　Moose File System是一个具备容错功能的网路分布式文件统，它将数据分布在网络中的不同服务器上，MooseFs通过FUSE使之看起来就是一个Unix的文件系统。但有一点问题，它还是不能解决单点故障的问题。开发语言perl,可跨平台操作。

l pNFS（www.pnfs.com）

　　网络文件系统(Network FileSystem,NFS)是大多数局域网(LAN）的重要的组成部分。但NFS不适用于高性能计算中苛刻的输入书橱密集型程序，至少以前是这样。NFS标准的罪行修改纳入了Parallel NFS(pNFS），它是文件共享的并行实现，将传输速率提高了几个数量级。

　　开发语言c/c++,运行在linu下。

上述各类文件系统中，本文关注hadoop的文件管理系统HDFS，以及数据库管理系统HBase，并在随后的部分分析这两个开源项目。

2.5 分布式文件系统固有缺陷

分布式文件系统的成功之处在于通过多个处理机进行数据存储，但是它的缺陷也由此而来。数据分布到多个处理机上，造成的结果就是数据通过网络进行通信而不是通过计算机内部的总线进行通信，而网络通信既有信道容量的限制，而且网络的不稳定性和低效率也使得整个通信过程代价高昂。在对数据进行多个处理机之间的交互过程中，文件系统不稳定是常态，所以备份和频繁的复杂的数据写入机制，严重影响着系统的运行效率，分布式文件系统运行环境对系统的执行效率有很大的影响，所以平均来看单独一个处理机的分布式存储效率永远要比一个单独的处理机的执行效率差。

而且更为重要的是数据的安全问题，尽管在大多数情况下，分布式计算数据的处理的实验平台都是在一个安全的网络之上，但是通过公共网络进行数据通信的后果无疑是数据的不安全性，在网络上进行传输的数据。由于数据是以字符串的性质在传输层传递，任何在网络上的处理机都可以通过ARP地址欺骗和数据解析等方式，进行数据的盗取，在某种意义上，云计算平台的数据安全更加复杂难以处理。

除了系统的效率和数据安全问题，更为特殊的一点是平台的异构性，云计算的理念是通过对各个处理机的资源虚拟化以进行资源整合，在上层直接使用整合好的资源进行数据交流，但是在底层计算机层面，单独的一个计算机是不稳定的，所以分配到单个计算机的数据需要很高效的备份管理，而这是很难控制的一个步骤而且会极大地降低系统的效率。

HDFS通常会在整个系统上设置固定数目的备份，通常是三个，如果检测到一个副本丢失，就会自动进行副本复制。在这一过程中，数据的管理是文件系统自动进行的，这种文件管理系统带来的一个分离的文件系统——数据读取来自HDFS文件管理系统，而数据写入则通常只是在本地进行，因为如果试图将数据写入HDFS，代价很难接受，而且仅仅通过网络进行数据通信会占用特别多的通信信道。

第3章分布式环境计算框架——MapReduce

——分治策略 divide and conquer

在上一章完成对数据存储的讨论之后，本章主要讨论分布式环境下，各种成型的计算框架。分布式环境下的计算，被分成了多个不同的计算任务。在本文当中，主要讲述MapReduce以及BSP这两个分布式计算框架。

MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）"和"Reduce（化简）"，和他们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。他极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

3.1 函数式编程

MapReduce是一种近似的函数编码模型，在通常的面向过程编程以及面向对象编程这两种编程基础上，还有一类编程思想——函数式编程。

纯函数是这样一种函数：它只会查看传进来的参数，它的全部行为就是返回基于参数计算出的一个或多个值。它没有逻辑副作用。这当然只是一种抽象；在CPU层面，每个函数都是有副作用的，多数函数在堆的层面上就有副作用，但这一抽象仍然有价值。与面向对象程序设计不同的是，OO通过把移动的部件封装起来使代码可理解。FP通过把移动的部件减到最少使代码可理解。

“移动的部件”就是更改中的状态。通知一个对象改变自己，这是面向对象编程基础教材的第一课，在大多数程序员的观念中根深蒂固，但它却是一种反函数式的行为。将函数和它们操作的数据结构组织在一起，这一基本的OOP思想显然有其价值，但如果想在自己的部分代码中获得函数式编程的好处，那么在这些部分，你必须疏远一下某些面向对象的行为。

无法声明为const的类方法从定义上就是不纯的，因为它们要修改对象的部分或全部状态集合，这一集合可能十分庞大。它们也不是线程安全的，这里戳一下，那里捅一下，一点一点地把对象置成了非预期的状态，这种力量才真正是Bug的不竭之源。如果不考虑那个隐含的const this指针，从技术角度const对象方法仍可看做纯函数，但许多对象十分庞大，大到它本身就足以构成一种全局状态，从而弱化了纯函数的在简洁清晰上的一些好处。构造函数也可以是纯函数，通常应该努力使之成为纯函数——它们接受参数并返回一个对象。

函数式编程将整个程序视为一个函数（function），这种编程思想与面向过程的编程有一定的不同之处。面向过程的编程中，也存在函数这个概念，这类编程以C语言最为典型。但是C语言的函数返回值可以为空，可以为一个结构体，可以为一个指针。但是函数式编程将整个过程视为多个小的函数（function）组合而成的，多个函数将各自的计算结果返回上一层函数，然后整个程序构成一个层层递归的计算，最终的结果返回给用户。

以Kawa为例（Kawa是Scheme的一个实现，一种类型Python的语言）：

>hello world

hello world

>(+ 4 3)

>(+ (* 2 2 2) (+ 1 2 3))

>car ‘(1 3 5)

纯函数式的程序没有变量和副作用，而且函数式编程经常使用递归进行数据传递，这种思想也影响MapReduce的编程模式。Map Reduce分成两个函数，在编写一个MapReduce程序的时候，就是不断的运行函数map和reduce，这就使得MapReduce将注意力集中在这两个函数上。

3.2 Map函数和Reduce函数

map函数和reduce函数是交给用户实现的，这两个函数定义了任务本身。

map函数：接受一个键值对（key-value pair），产生一组中间键值对。MapReduce框架会将map函数产生的中间键值对里键相同的值传递给一个reduce函数。

reduce函数：接受一个键，以及相关的一组值，将这组值进行合并产生一组规模更小的值（通常只有一个或零个值）。

以统计词频的程序为例，整个统计词频的MapReduce函数的核心代码非常简短，主要就是实现这两个函数。

[plain] view plain copy print ?

map(String key, String value):

// key: document name

// value: document contents

for each word w in value:

EmitIntermediate(w, "1");

reduce(String key, Iterator values):

// key: a word

// values: a list of counts

int result = 0;

for each v in values:

result += ParseInt(v);

Emit(AsString(result));

map(String key, String value):

// key: document name

// value: document contents

for each word w in value:

EmitIntermediate(w, "1");

reduce(String key, Iterator values):

// key: a word

// values: a list of counts

int result = 0;

for each v in values:

result += ParseInt(v);

Emit(AsString(result));

统计词频的例子里，map函数接受的键是文件名，值是文件的内容，map逐个遍历单词，每遇到一个单词w，就产生一个中间键值对<w, "1">，这表示单词w咱又找到了一个；MapReduce将键相同（都是单词w）的键值对传给reduce函数，这样reduce函数接受的键就是单词w，值是一串"1"（最基本的实现是这样，但可以优化），个数等于键为w的键值对的个数，然后将这些“1”累加就得到单词w的出现次数。最后这些单词的出现次数会被写到用户定义的位置，存储在底层的分布式存储系统（GFS或HDFS），其中GFS是Google的文件管理系统，而HDFS是hadoop的文件管理系统。

MapReduce是如何工作的

上图是论文里给出的流程图。一切都是从最上方的user program开始的，user program链接了MapReduce库，实现了最基本的Map函数和Reduce函数。图中执行的顺序都用数字标记了。

MapReduce库先把user program的输入文件划分为M份（M为用户定义），每一份通常有16MB到64MB，如图左方所示分成了split0~4；然后使用fork将用户进程拷贝到集群内其它机器上。

user program的副本中有一个称为master，其余称为worker，master是负责调度的，为空闲worker分配作业（Map作业或者Reduce作业），worker的数量也是可以由用户指定的。

被分配了Map作业的worker，开始读取对应分片的输入数据，Map作业数量是由M决定的，和split一一对应；Map作业从输入数据中抽取出键值对，每一个键值对都作为参数传递给map函数，map函数产生的中间键值对被缓存在内存中。

缓存的中间键值对会被定期写入本地磁盘，而且被分为R个区，R的大小是由用户定义的，将来每个区会对应一个Reduce作业；这些中间键值对的位置会被通报给master，master负责将信息转发给Reduce worker。

master通知分配了Reduce作业的worker它负责的分区在什么位置（肯定不止一个地方，每个Map作业产生的中间键值对都可能映射到所有R个不同分区），当Reduce worker把所有它负责的中间键值对都读过来后，先对它们进行排序，使得相同键的键值对聚集在一起。因为不同的键可能会映射到同一个分区也就是同一个Reduce作业（谁让分区少呢），所以排序是必须的。

reduce worker遍历排序后的中间键值对，对于每个唯一的键，都将键与关联的值传递给reduce函数，reduce函数产生的输出会添加到这个分区的输出文件中。

当所有的Map和Reduce作业都完成了，master唤醒正版的user program，MapReduce函数调用返回user program的代码。

所有执行完毕后，MapReduce输出放在了R个分区的输出文件中（分别对应一个Reduce作业）。用户通常并不需要合并这R个文件，而是将其作为输入交给另一个MapReduce程序处理。整个过程中，输入数据是来自底层分布式文件系统（GFS）的，中间数据是放在本地文件系统的，最终输出数据是写入底层分布式文件系统（GFS）的。而且我们要注意Map/Reduce作业和map/reduce函数的区别：Map作业处理一个输入数据的分片，可能需要调用多次map函数来处理每个输入键值对；Reduce作业处理一个分区的中间键值对，期间要对每个不同的键调用一次reduce函数，Reduce作业最终也对应一个输出文件。

计算分成三个阶段：

第一阶段是准备阶段，包括1、2，主角是MapReduce库，完成拆分作业和拷贝用户程序等任务；第二阶段是运行阶段，包括3、4、5、6，主角是用户定义的map和reduce函数，每个小作业都独立运行着；第三阶段是扫尾阶段，这时作业已经完成，作业结果被放在输出文件里，就看用户想怎么处理这些输出了。

定义M=5，R=3，并且有6台机器，一台master。

这幅图描述了MapReduce如何处理词频统计。由于map worker数量不够，首先处理了分片1、3、4，并产生中间键值对；当所有中间值都准备好了，Reduce作业就开始读取对应分区，并输出统计结果。

3.3 用户的权利

用户最主要的任务是实现map和reduce接口，但还有一些有用的接口是向用户开放的。

an input reader。这个函数会将输入分为M个部分，并且定义了如何从数据中抽取最初的键值对，比如词频的例子中定义文件名和文件内容是键值对。

a partition function。这个函数用于将map函数产生的中间键值对映射到一个分区里去，最简单的实现就是将键求哈希再对R取模。

a compare function。这个函数用于Reduce作业排序，这个函数定义了键的大小关系。

an output writer。负责将结果写入底层分布式文件系统。

a combiner function。实际就是reduce函数，这是用于前面提到的优化的，比如统计词频时，如果每个<w, "1">要读一次，因为reduce和map通常不在一台机器，非常浪费时间，所以可以在map执行的地方先运行一次combiner，这样reduce只需要读一次<w, "n">了。

map和reduce函数与之前使用相同的定义，用户可以通过定义这两个函数来修改系统的具体计算行为。

第4章分布式环境计算框架——BSP模型

——控制计算，控制代价

4.1 BSP模型基本理论

BSP模型最初作为一个并行计算领域中软件和硬件之间的“过渡模型”而提出的，是一个通用的并行计算模型，相对于MapReduce更适合构建大规模图处理原型系统中。BSP，即Bulk Synchronous Parallel，“大块”同步模型，其概念由哈佛大学的Valiant和牛津大学的Bill McColl提出，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。该模型基于一个Master协调，所有的Worker同步执行, 数据从输入的队列中读取，处理过程如图3.1所示^[11]。

BSP模型基本框架

基于分布式内存存储，并行机不仅要保证全局内存的存取速度, 而且要协调同一时刻对相同内存单元的存取, 这是非常困难的。因此, 为了适应更大规模的并行性, 使并行系统具有良好的可扩展性, 采用分布式的内存是比较合理的。

全局的数据通信网络。BSP 的各个处理单元通过它和其它处理单元进行通信或远程内存的存取, 这和大多数基于分布内存或消息传递的并行模型是相同的。但是, 通常并行计算机的通信是各处理单元之间进行点对点通信的, 而 BSP 并行计算机的通信网络是一个全局的概念, 它的作用不是进行点对点的通信, 而是进行一个全局性的动作。

全局的路障同步机制。路障同步的引入使BSP 模型具有了一系列其它模型无法比拟的优点, 但路障同步以前被认为是一种代价昂贵的操作, 而许多现有的并行计算机体系结构并没有对路障同步的硬件支持, 所以一些人认为 BSP 模型是不切实际的, 是针对某一些并行体系结构的专用模型。路障同步是BSP 模型中争论最多的地方之一。但最近的大量研究表明, 路障同步在木质上并不是代价昂贵的操作,它可以在绝大多数已知的并行体系结构上用软件有效地进行实现。

BSP模型结构

一个BSP并行计算系统由3个部分组成:一组具有局部内存的处理单元；一个连接所有处理单元的数据通信网络；支持对所有处理单元进行全局路障同步的机制。客户端提交作业前，需要将源数据加载到Worker上，然后向Master提交作业并等待作业完成。Master收到作业启动通知后，向各个Worker发送通知，同步启动任务，并在接下来的时间里控制超步迭代。各Worker则负责具体执行客户端提交的作业，期间需要接收其它Worker发送的消息，进行本地计算处理，然后根据情况向其它Worker发送消息，这一过程体现在图3.2中。

4.2 BSP工作原理

BSP计算模型不仅是一种体系结构模型，也是设计并行程序的一种方法。BSP程序设计准则是 Bulk同步，其独特之处在于超步(Super Step)概念的引入。一个BSP程序同时具有水平和垂直两个方面的结构。从垂直上看,一个BSP程序由一系列串行的超步组成，每个超步又分为3个过程：

（1）各个处理机进行本地局部计算。

（2）各个处理机利用本地内存中的信息完成局部的计算工作，在这一阶段处理机发出远程内存读取和消息通信等工作。

（3）所有处理机进行全局路障同步，本次超步的通信操作在路障同步之后变为有效。

BSP程序的水平结构图

这种结构类似于一个串行程序结构。在各超步中, 每个处理器均执行局部计算, 并通过选路器（Router）接收和发送消息；然后作一全局检查，以确定该超步是否已由所有的处理器处理完成；若是，则前进到下一超步，否则等待。整个计算体现在图4.3中。

BSP模型的优点

BSP并行计算模型可以用 p/s/g/i 4个参数进行描述：^[12]

p为处理器的数目(带有存储器)

s为处理器的计算速度

g为每秒本地计算操作数目/通信网络每秒传送的字节数，即带宽因子

I为全局的同步时间开销,称之为全局同步之间的时间间隔

我们假设有p台处理器同时传送h个字节信息，则g•h就是通信的开销。同步和通信的开销都规格化为处理器的指定条数。我们可以通过上述的参数进行系统性能的估计。

整体来说BSP模型相对于其他的模型而言，具有如下几个方面的优点：

(1) BSP并行模型独立于体系结构，接近现有的并行系统，可以在绝大多数目标体系结构上有效地实现。因此，程序员可以直接依它为目标机器进行并行程序编写、实现并行算法。而且BSP 并行模型和目标机器无关，由于BSP并行模型从一开始就是作为和体系结构无关的。通用的并行计算模型提出的并行程序从一个平台换到另一平台不需要进行改动，BSP 并行程序具有很强的可移植性。

(2) BSP并行模型以超步为基本单位进行并行计算，这使得BSP并行程序设计简单清晰，有点类似顺序程序的编写。类似于串行计算机, 这样可以方便进行并行程序的编写。从某种角度看, BSP 并行模型可以看成是严格同步的并行计算模型，其中各处理机处理每一条指令都要保持同步

(3) BSP并行程序的性能是可以预测的，可以在系统编写之前进行理论分析预测系统是否可行。BSP 程序在给定目标机器上的性能是可预测的。BSP 程序的运行时间可以由 BSP 模型的几个参数来进行计算。对程序性能的预测可以帮助我们开发出具有良好可扩展性的并行算法和并行程序。

在并行计算系统中，最为主要的就是通信的处理，在这一方面，基于开源社区apache 的并行项目hadoop的BSP系统中，每个节点处理机的消息通信不是传统的，基于点对点的通信，而是一个全局性的操作。在BSP处理系统中，所有的通信操作都是非阻塞的，在进行本地计算式发出：通信操作在通信阶段完成，在路障同步以后变为有效。BSP模型实际上是将通信和同步分离开，分别进行处理。这样不仅使并行程序结构更为清晰，而且由于BSP模型中的通信操作都是非阻塞的，消除了由于通信造成的死锁。

4.3 BSP框架构建

基于BSP模型的大规模图处理原型系统是运行在云环境下的分布式处理系统。系统能够对大规模图处理进行良好的支持，整体架构如图4.1所示^[13]。

基于BSP模型的大规模图处理原型系统总体结构设计

其中，为了增加系统的普适性，设计支持多种方式的数据存储格式。例如，基于分布式文件系统（如HDFS）以及基于数据库（KVDB或RDBMS）的存储。整个系统的核心是NEU-BSP Core，是BSP并行计算引擎，负责实现数据划分、任务调度、消息通信、全局同步、容错故障恢复、集群管理、数据输入输出接口、以及本地计算等。接口访问层是系统提供的应用程序编程接口：支持各种基于图的应用，如网页的PageRank计算、社会网络分析、以及基于图数据库的分析等。

系统运行流程

图4.2从具体的应用出发，以实际作业的运行为背景，进一步阐述了基于BSP模型的大规模图处理原型系统的控制流程和处理过程。下面介绍处理流程：

系统控制流程和处理过程

客户端运行BSP程序，通过BSP JobClient向集群的BSP Master节点提交作业。

BSP Master通过数据读取模块，从普通集中式文件、数据库、分布式文件系统、或非关系数据库系统中。

BSP Master根据图数据的分块情况，给每个工作节点分配图数据分割任务。类似于MapReduce的创建Mapper任务。

每个工作节点接到任务后，读取对应的数据块，按照默认方法（对图顶点ID进行Hash的方法）或用户指定的方法对图顶点数据进行分配，并传送到目标Worker节点上。类似于MapReduce的Map阶段的处理过程，即把读取的数据（如图的顶点和边数据）按照一定原则分配到各个计算节点。关键是要能够方便地获知或计算出哪个数据在哪个Worker上。此时，使得一个Worker处理的图数据尽量在内存中。

BSP Master开始启动一个超步。

Worker节点针对其上的图数据块，以及收到的消息（第一步时消息队列为空），对每个图的顶点执行用户自定义的处理操作，并将结果封装成消息，发送给每一个图顶点的出度指向的目标顶点所在的Worker节点。

Worker节点处理图数据的同时收取其他Worker节点发送过来的消息，并且只有在下一个超步开始后才能处理这些消息。同时，Worker会定期向BSP-Master发送心跳消息，向BSP-Master汇报当前的状态。当处理结束后利用Zookeeper设置路障同步，同步所有的Worker节点。

Worker节点当前的超步任务处理完毕并且所有消息发送结束后，利用Zookeeper设置路障同步，同步所有的Worker节点。

BSP Master根据具体需求或者是所有的Worker当前超步的工作都结束后才决定是否启动下一个超步计算。如果需要启动，那么转到第5步继续执行；如果不需要启动新的超步，那么BSP处理任务结束，所有Worker节点将自己的处理结果写入到输出文件中。

BSP Master在新启动一个超步时，根据需求决定是否记录Checkpiont。记录检查点的目的主要是为了进行故障恢复。

第5章 BSP计算框架与Map Reduce的区别

——殊途同归

如果不考虑计算框架具体实现和理论构建的不同之处，BSP模型和Map Reduce模型的唯一区别就是对文件系统的不同处理策略。

Map Reduce的代价集中在各个mapreduce任务之间，每次启动一个mapreduce任务，都需要在这之前进行网络数据的传递，以hadoop的mapreduce模型和hadoop的hama为例，计算框架使用的文件系统采用HDFS。这样代价的分析就能明显看出二者的不同之处。

在讨论一个模型的计算代价过程中，不同的框架下不同的步骤有不同的代价权重。但是在通常的情况下，网络通信代价最为昂贵，这是由网络数据传输的不稳定性和信道容量的限制造成的，为了数据安全性，网络传输过程传输了额外的数据，并且这些数据是在一个比电脑总线慢的多的网路上完成的；磁盘I/O次之，由于磁盘数据的读取受到磁盘转速和数据总线的限制，现有的多层存储结构使得前端总线并不总是与计算速度挂钩；内存的运行最快，如果数据完全存储在内存当中，即使处理这个数据的算法是非多项式时间的，整个计算也能够在短时间内完成。

以Fibonacci数列计算为例，在一个内存为1G的电脑上，通常对于一个计算任务，能够提供400-600MB的内存空间，假设我们使用512MB的空间，这个大小的空间最多能够放置8,000,000 个int型数据用于存放Fibonacci数列，至于int型数据溢出并不考虑，在每次完成计算后，对得到的结果进行取模操作。这个计算在c++环境进行测试，得到的结果是整个计算可以在0.016s 内完成，可见对于内存的读取，计算机的处理速度是相对较快的。

相对于内存的数据访问和存取的能力，磁盘和网络通信能力就相对较慢，而其中网络通信速度最慢，

5.1 MapReduce的计算代价

如果将mapreduce的数据处理过程进行抽象，整个计算过程可以理解成不断地进行分治计算，每次对数据进行划分并且将划分结果按照计算任务的需求以最小计算代价进行处理，

第一阶段是准备阶段，完成拆分作业和拷贝用户程序等任务；

第二阶段是运行阶段，主角是用户定义的map和reduce函数，每个小作业都独立运行着；

第三阶段是扫尾阶段，这时作业已经完成，作业结果被放在输出文件里，就看用户想怎么处理这些输出了。

在这三个阶段当中，代价最大的就是第三阶段，由于有很多计算任务需要运行多个mapreduce作业，反复进行多次HDFS数据写入操作。每个mapreduce作业完成，数据开始写入磁盘准备提供给下一个mapreduce作业，在这一过程中，写入操作基本上都是通过网络进行通信，写入本地和远程副本当中。

通常情况下,HDFS设置的副本数目是三个，三个副本存储在不同的处理机当中，使得任何一个处理机丢失都不会导致整个系统的数据发生缺失，但是这也导致了网络通信的数据量特别大，如果计算需要开启多个mapreduce作业，或是整个作业是一个循环过程甚至是一个迭代过程，这会造成整个计算任务把大量的时间用在网络数据传输上。

5.2 BSP的计算代价

BSP是一个针对mapreduce缺陷而提出的计算模型，每次完成计算，数据不是都进行网络传递而是分成本地写和消息通信。尽管mapreduce也可以将中间结果的数据分成两块分别存储在本地和HDFS上，但是在HDFS上进行数据写入操作的代价明显高于消息通信的代价，因为消息通信是P2P的数据传输，而HDFS则是类似广播的向远端传递两个副本，在数据处理效率上，明显不如定点传输的效率。

在BSP模型上进行数据计算操作，比较适合需要多次迭代的任务，但是对于真正的数据规整的数据库，BSP模型的效率并不如mapreduce的效率高。

Mapreduce在计算过程中，进行的是反复的数据规约操作，模型的基本结构就是通过不断地进行规约操作降低需要处理的数据量。但是在BSP模型中，如果不是主动进行数据的规约操作，模型本身并不强制要求计算任务采取削减数据量的操作的。

第6章后记

并行计算两个较为出名的计算框架之间是可以互相转换的，但是这种转换并不会带来性能上的提升，而是更多的是根据计算任务进行取舍，在并行计算提出的时候，计算效率和系统容错两个成分就是跷跷板的两端。除非通过硬件方面的改进，提高跷跷板的基座，否则跷跷板提高一端的同时，总有一段在低端拖累整个系统前行的脚步。