3.4　云计算中的编程模型

3.4.1　分布式计算

3.4.1.1　分布式计算的概念

分布式计算是一门计算机科学，研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，并由许多相互独立的计算机进行协同处理，以得到最终结果。分布式计算让几个物理上独立的组件作为一个单独的系统协同工作，这些组件可能指多个CPU，或者网络中的多台计算机。它做了如下假定：如果一台计算机能够在5秒钟内完成一项任务，那么5台计算机以并行方式协同工作时就能在1秒钟内完成。实际上，由于协同设计的复杂性，分布式计算并不能都能满足这一假设。对于分布式编程而言，核心的问题是如何把一个大的应用程序分解成若干可以并行处理的子程序。有两种可能的处理方法：一种是分割计算，即把应用程序的功能分割成若干个模块，由网络上多台机器协同完成；另一种是分割数据，即把数据集分割成小块，由网络上的多台计算机分别计算。对于海量数据分析等数据密集型问题，通常采取分割数据的分布式计算方法，对于大规模分布式系统则可能同时采取这两种方法。

3.4.1.2　分布式计算的基本原理

大量分布式系统通常会面临如何把应用程序分割成若干个可并行处理的功能模块，并解决各功能模块间协同工作的问题。这类系统可能采用以C/S结构为基础的三层或多层分布式对象体系结构，把表示逻辑、业务逻辑和数据逻辑分布在不同的机器上，也可能采用Web体系结构。基于C/S架构的分布式系统可借助CORBA、EJB、DCOM等中间件技术解决个模块间的协同工作问题。基于Web体系架构或称为Web Service的分布式系统，则通过基于标准的Internet协议支持不同平台和不同应用程序的通信。Web Service是未来分布式体系架构的发展趋势。对于数据密集型问题，可以采用分割数据的分布式计算模型，把需要进行大量计算的数据分割成小块，由网络上的多台计算机分别计算，然后对结果进行组合得出数据结论。Map-reduce是分割数据型分布式计算模型的典范，在云计算领域被广泛采用。

3.4.2　并行编程模型

为了使用户能更轻松地享受云计算带来的服务，让用户能利用编程模型编写简单的程序来实现特定的目的，云计算上的编程模型必须十分简单，必须保证后台复杂的并行执行和任务调度向用户和编程人员透明。

云计算大部分采用Map-reduce的编程模型。现在大部分IT厂商提出的“云”计划中采用的编程模型，都是基于Map-reduce的思想开发的编程工具。Map-reduce不仅仅是一种编程模型，同时也是一种高效的任务调度模型。Map-reduce这种编程模型不仅适用于云计算，在多核和多处理器、cell processor以及异构机群上同样有良好的性能。该编程模型仅适用于编写任务内部松耦合、能够高度并行化的程序。如何改进该编程模型，使程序员能够轻松地编写紧耦合的程序，运行时能高效地调度和执行任务，是Map-reduce编程模型未来的发展方向。

3.4.2.1　何谓Map-reduce

Map-reduce是Google开发的Java、Python、C++编程模型，它是一种简化的分布式编程模型和高效的任务调度模型，用于大规模数据集（大于1TB）的并行计算。严格的编程模型使云计算环境下的编程十分简单。Map-reduce模型的思想是将要执行的问题分解成Map（映射）和Reduce（归约）的方式，先通过Map程序将数据切割成不相关的区块，分配（调度）给大量计算机处理，达到分布式运算的效果，再通过Reduce程序将结果汇总输出。

Map-reduce是一种分布式编程模型，它以数据为中心，把数据分割成小块供网络上的多台计算机分别计算，而后对计算结果进行汇总得出最终结论。Map-reduce提供了泛函编程的一个简化版本，与传统编程模型中函数参数只能代表明确的一个数或数的集合不同，泛函编程模型中函数参数能够代表一个函数，这使得泛函编程模型的表达能力和抽象能力更高。在Map-reduce模型中，输入数据和输出结果都被视作有一系列key/value对组成的集合，对数据的处理过程，就是Map和Reduce过程，Map过程将一组key/value映射成另一组key/value，Reduce是一个归约过程，把具有相同key的value值合并在一起。Map-reduce模型简单，并能满足绝大多数网络数据分析工作，因此被Google、Hadoop等云计算平台广泛采用。基于Map-reduce的分布式系统隐藏了并行化、容错、数据分布、负载均衡等复杂的分布式处理细节，提供简单有力的接口来实现自动的并行化和大规模分布式计算，从而在大量普通PC上实现高性能计算。在这些系统里，用户指定map函数对输入的key/value集进行处理，形成中间形式的key/value集；系统按照key值把中间形式的value集中起来，传给用户指定的reduce函数；reduce函数把具有相同key的value值合并在一起，最终输出一系列的key/value对作为结果。

3.4.2.2　为什么需要Map-reduce

Map-reduce是最早由Google提出的一项分布式编程模型，用以进行大数据量的计算。它借鉴了Lisp等函数编程语言的思想，把对数据的处理归结为映射map和归约reduce两个操作。Google最初将其应用在内部海量的Web页面索引上，在效率和健壮性上取得了极大的成功。实际上，Map-reduce是一种简化的并行计算编程模型，这对开发人员而言具有重要的意义。随着互联网数据的急剧增长，开发人员面临越来越多的大数据量计算问题，处理这类问题的主要方法是并行计算，然而并行计算是一个相对复杂的技术，不易掌握。Map-reduce的出现降低了并行应用开发的入门门槛，它隐藏了并行化、容错、数据分布、负载均衡等复杂的分布式处理细节，使得开发人员可以专注于程序逻辑的编写。Map-reduce使并行计算得以广泛应用，是云计算的一项重要技术。

3.4.2.3　Map-reduce的执行

Map-reduce是一种处理和产生大规模数据集的编程模型，程序员在map函数中指定对各分块数据的处理过程，在reduce函数中指定如何对分块数据处理的中间结果进行归约。用户只需要指定map和reduce函数来编写分布式的并行程序。当在集群上运行Map-reduce程序时，程序员不需要关心如何将输入的数据分块、分配和调度，同时系统还将处理集群内节点失败以及节点间通信的管理等。图3-6给出了一个Map-reduce程序的具体执行过程。

图3-6　Map-reduce程序的具体执行过程

从图3-6可以看出，执行一个Map-reduce程序需要5个步骤：输入文件、将文件分配给多个工作机并行地执行、写中间文件（本地写）、多个Reduce工作机同时运行、输出最终结果。本地写中间文件在减少了对网络带宽压力的同时减少了写中间文件的时间耗费。执行Reduce时，根据从Master获得的中间文件位置信息，Reduce使用远程过程调用，从中间文件所在节点读取所需的数据。Map-reduce模型具有很强的容错性，当工作机节点出现错误时，只需将该工作机节点屏蔽在系统外等待修复，并将该工作机上执行的程序迁移到其他工作机上重新执行，同时将该迁移信息通过Master发送给需要该节点处理结果的节点。Map-reduce使用检查点的方式来处理Master出错失败的问题，当Master出现错误时，可以根据最近的一个检查点重新选择一个节点作为Master并由此检查点位置继续运行。

Map-reduce仅为编程模型的一种，微软提出的DryadLINQ是另外一种并行编程模型，但它局限于.NET的UNG系统的同时并不开源，这限制了它的发展前景。

Map-reduce作为一种较为流行的云计算编程模型，在云计算系统中应用广阔。但是基于它的开发工具Hadoop并不完善。特别是其调度算法过于简单，判断需要进行推测执行的任务的算法造成过多任务需要推测执行，降低了整个系统的性能。改进Map-reduce的开发工具，包括任务调度器、底层数据存储系统、输入数据切分、监控“云”系统等方面是将来一段时间的主要发展方向。