离线数据处理功能及其优势

分布式计算框架（执行层）是云平台的关键组件之一。它基于分布式存储（存储层）。它的功能是封装计算并行性、任务调度和容错、数据分配、负载平衡等功能。为上层应用程序提供计算服务。语言层是服务接口的封装，SQL语言的编程接口提供给用户，不同计算框架的类SQL编程语言是不同的。

（一）Map Reduce（Hadoop 0.20.2）

Map Reduce是Google提出的并行计算框架。它可以在大量的PC机上并行执行大量的数据采集和分析任务，并对如何并行执行任务、如何分配数据、如何容错、如何延迟网络带宽等问题进行编码。封装在库中的用户只需要执行数据操作，而不必担心复杂的细节，如并行计算、容错、数据分布、负载平衡等等。同时，它为上层应用程序提供了一个良好而简单的抽象接口。

Apache是指Google的论文进行Java Hadoop的开源实现，主要是复制和实现分布式文件系统和计算框架Map Reduce。

1.系统体系结构

Map Reduce计算框架属于主/从体系结构。它有两个守护进程，Job Tracker和Task Tracker，其中Job Tracker是主进程，Task Tracker是从进程。Task Tracker调用Job Tracker的进程远程完成通信，但Job Tracker通常只响应Task Tracker请求，并不主动发起通信。Job Tracker按其功能可分为六个模块。

（1）作业请求：向用户实例分配唯一的作业ID（Job ID）。

（2）提交职务：为用户实例提供提交任务的界面。

（3）任务初始化：创建作业（作业）对象、创建作业地图和减少任务队列。

（4）作业调度：映射和减少任务调度。

（5）作业监控：作业、任务状态、作业计数器值等。

（6）任务和节点失效处理：任务重新调度、任务/作业失败、任务/作业删除。

任务跟踪器根据其功能可分为五个模块。

（1）连接维护：定期检查与Job Tracker的连接。

（2）任务请求报告：定期向Job Tracker发送心跳消息，检查本地任务的数量和本地磁盘的空间使用情况，并向Job Tracker报告任务执行的状态和是否可以接受新任务。

（3）数据I/O：MAP/Remote数据输入和Map/Reduce数据输出。

（4）任务失败处理：将错误报告发送给Task Tracker，Task Tracker发布任务槽。

（5）任务执行：配置运行环境，启动Java虚拟机的（Java Virtual Machine，JVM）进程，并运行Map/Reduce。

2.容错

Map Reduce允许数据错误、节点内进程错误和Task Tracker节点故障，但目前Map Reduce无法避免Job Tracker故障的一个点。当发现错误时，Job Tracker会重新安排任务（在无法重新调度单个任务时被放弃）以实现容错。

Task Tracker定期检查和清除以下任务：①无响应的任务；②空间溢出任务；③文件系统错误；④Reduce任务的洗牌错误；⑤JVM错误。然后将错误任务的ID反馈给Job Tracker。

Job Tracker需要处理文件系统错误和Reduce任务的执行错误，其中文件系统错误通常是由任务失败引起的。当Job Tracker发现任务执行失败时，它会重新安排任务的执行时间，如果任务失败4次（系统默认4次，可以配置），则将任务标记为不可恢复。如果不可恢复的任务达到某个极限值，则任务被标记为不可恢复，其所有任务，包括已执行任务和未执行任务，都将被删除。

当Job Tracker发现节点故障时，它会重新安排该节点上所有未完成的任务并完成Map任务。完成的减少任务不需要重新安排时间，因为它的结果保存在HDFS中。

3.任务分配与调度

Map Reduce配置三个任务调度程序：FIFO调度器、优先级调度程序和公平调度程序。目前，默认的是FIFO调度程序。

（1）FIFO调度器是Map Reduce早期版本采用的策略。每个作业都可以使用整个集群，所以作业必须等到轮到它运行为止。当出现空闲资源时，后一个作业只能在当前作业不需要该资源时才能使用该资源。

（2）优先级调度器在FIFO调度器的基础上引入了优先级策略。通过设置mapred.job.priority属性或者利用set Job Priority方法设置作业的优先级，先执行优先级最高的作业的任务，但是，优先级并不支持抢占。

（3）公平调度器。对于映射任务和减少任务，Task Tracker有固定数量的插槽。Task Trackere默认为两个Map插槽和两个缩减插槽（即两个Map任务和两个精简任务可以同时运行），并且可以根据Task Tracker核心的数量和内存大小来配置槽数。

在默认情况下，每个用户都有自己的池。用户池的最小容量可以由Map中的插槽数来定义，或者可以设置每个池的权重。

公平调度程序支持抢占。如果某个池在一定时间内得不到资源的公平分配，则公平调度程序将终止过多资源的作业，并将时间分配给资源不足的池。

（二）Pregel

许多实际应用涉及大型图形算法，如Web链接关系和社会关系图。这些应用程序具有相同的特性：图的规模很大，通常达到数十亿个顶点和数万亿个边。这对需要高效计算的应用程序提出了巨大的挑战。

（1）构建一个专用的分布式框架：每次引入新的算法或数据结构都需要付出很大的努力。

（2）在现有的分布式平台Map Reduce的基础上，存在一些易用性和性能不适用于图形算法的问题（图形算法更适合于消息传递模型）。

（3）单机不能适应问题规模的扩大。

（4）现有的并行图模型系统没有考虑大型系统的容错等更重要的问题。

Google针对这类问题提出了一种迭代计算框架——Pregel，它可以在每次迭代时从前一次迭代中接收信息，并将信息传输到下一个顶点。在修改自身状态信息的过程中，从顶点作为状态信息的起点，或者改变整个图的拓扑结构。同时，Pregel具有高效率、可扩展性和容错性等特点，并隐藏了分布式的细节，只向用户展示了一个强大的性能，易于编程的大型图形算法处理计算框架。

Pregel计算系统的灵感来源于Valiant提出的大型同步模型。Pregel计算由一系列迭代组成，每个迭代都称为Super Step。在每个步骤中，计算框架调用每个顶点的用户定义函数。

1.系统体系结构

Pregel是为Google的集群架构设计的。每个集群都包含数千台机器，它们被组合在多个机架上，内部通信带宽非常高。集群在内部是相互关联的，但在地理上是分布的。该系统提供了一个名称服务系统，因此每个任务都可以通过逻辑名称标识绑定到机器上。

（1）节点维护。每个计算节点都有一个全局唯一的节点ID，该节点维护主节点内的计算节点列表，记录每个计算节点的ID、地址信息和节点生存状态。(www.xing528.com)

（2）数据分布。Pregel将输入数据分解为多个分区，每个分区包含从这些顶点开始的顶点和边，默认的分区函数只使用顶点IDMo7V。主节点将这些分区分配给计算节点，每个节点可以有一个或多个分区（类似于一致的散列）。主节点上的计算节点列表还记录节点上的分区分布。

（3）全局同步。主节点负责全局同步，称为障碍同步。主节点向所有计算节点发送相同的指令，然后从每个计算中等待节点的响应。如果任何计算节点失败，主节点进入恢复模式；如果障碍同步成功，主节点将添加全局超步骤的索引并进入下一个超级步骤。

（4）通知节点备份数据。在每个步骤的开始，主节点通知计算节点将计算节点上的分区状态保存到持久存储设备，包括顶点值、边界值和接收的消息。

（5）错误恢复。主节点确定计算节点是否与ping消息错误。如果计算节点在一定时间内没有接收到ping消息，则计算节点上的计算终止。如果主节点在一定时间内没有收到来自计算节点的反馈，则该节点将被视为失败。主节点将这些节点上的分区重新分配给其他可用的计算节点。此外，主节点还保存整个计算过程的统计数据以及整个图的状态，如图的大小、输出程度的直方图、活动顶点数、当前Super Step中消息传输的时间以及所有用户定义的聚合。主节点运行内部HTTP服务，该服务显示对此数据信息的监视。

2.就业效率

Pregel的数据输入是一个有向图，有向图的每个顶点都有一个唯一的ID，一些属性可以修改，其初始值由用户定义。每个有向边缘与其源顶点相关联，具有用户定义的属性和值，并记录其目标顶点的ID。

在每个步骤中，顶点被并行地计算，每次执行相同的用户定义的函数。每个顶点可以修改自己的状态信息或启动信息，计算上一步中接受的消息，然后将结果作为消息发送到其他顶点供下一步使用，或者修改整个图的拓扑。

（1）应用主节点向主节点提交任务，主节点计算数据资源分配和计算节点资源。

（2）主节点告诉哪些计算节点参与计算，这些节点保持分区的顶点状态。

（3）计算节点获取数据。

（4）数据准备完成后，通知主节点。

（5）主节点通知越级启动。

（6）计算节点以实现消息的异步传输，并接收来自其他节点的消息。

（7）计算和通信完成后，通知主节点。

（8）主节点收到所有计算节点完成的消息后，通知计算节点报告活动节点数。

（9）如果活动节点数为零，则任务完成；否则，将通知所有计算节点数据备份。

（10）计算节点完成数据备份后，通知主节点。

（11）主节点通知下一步开始并返回到步骤（6）。

Pregel程序的输出是所有顶点输出的集合。通常，Pregel程序的输出是一个与输入同构的有向图，但并不一定是这样，因为在计算过程中可以添加和删除顶点和边，例如聚类算法。为了满足需要，可以从一个大图中选择几个不连通点；图挖掘算法只能输出从图中提取的聚合数据等。

3.容错

Pregel的容错性由检查点（检查点）保证。在每个步骤的开始，主节点通知计算节点将分区的状态（包括顶点值、边界值）和接收到的消息保存到持久存储设备。主节点还周期性地保存聚合值。

主节点通过周期性ping消息确定计算节点是否错误。如果计算节点在一定时间内没有接收ping消息，则计算节点上的计算终止。如果主节点在一定时间内没有收到来自计算节点的反馈，则该节点将被视为失败。

当一个或多个计算节点失败时，分配给这些计算节点的分区的状态信息将丢失。主节点将这些分区重新分配给其他可用的计算节点，这些计算节点在步骤开始时从检查点重新加载这些分区的状态信息。此步骤可能在失败的计算节点上运行的最后一步之前，此时需要重新执行几个丢失的步骤。检查站的频率也应以一定的策略为基础，以平衡检查点的成本和恢复执行的成本。

Google正在开发一种名为“封闭恢复”的检查点策略，以提高检查点和恢复执行的开销效率。除了基本检查点策略之外，计算节点还记录它发送的消息。恢复仅限于丢失的分区，该分区从检查点恢复。系统通过回放消息日志重新计算丢失的步骤到V阶段。通过这种方式，可以节省资源和时间来恢复分区计算，并减少恢复分区计算的延迟。此外，保存发送出去的消息有一定的开销，但是计算节点上的磁盘读写带宽通常不会使这成为一个瓶颈。

（三）Dryad

Dryad和Dryad LINQ是微软硅谷研究所创建的研究项目，主要用于提供基于Windows操作系统的分布式计算平台。Dryad LINQ提供了一个高级语言接口，它使普通程序员很容易进行大规模的分布式计算，结合了微软的Dryad和LINQ两项关键技术，并用于在平台上构建应用程序。

1.系统体系结构

Dryad系统的建立是为了支持有向无环图类型数据流的并行程序。Dryad的总体框架根据程序的要求完成调度，并自动完成对每个节点的任务操作。在Dryad平台上，每个Dryad工作被表示为有向无圈图，每个节点表示要执行的程序，节点之间的边缘表示数据的传输。

Dryad系统框架组件如下。

（1）任务管理器（Job Manager，JM）中每个任务的执行：由任务管理器控制，任务管理器负责实例化任务的工作图，调度集群上节点的执行，监视每个节点的执行并搜集一些信息，通过重新执行提供容错；根据用户配置策略动态调整工作图。

（2）群集（集群）：用于执行工作关系图中的节点。

（3）命名服务器（NAME Server，NS）：负责维护集群中每台机器的信息。

（4）维护过程（PDaemon，PD）：进程监控和调度。

当用户使用Dryad平台时，他们需要在任务管理节点上创建自己的任务。每个任务包括若干进程和这些进程中的数据传输。在任务管理器获得无环图之后，它已经为程序的输入通道做好了准备，并在机器可用时进行调度。任务管理器从指定的服务器获取可用计算机的列表，并通过维护过程安排程序。

2.就业效率

Dryad通过基于有向无圈图的策略建模算法为用户提供了一个清晰的编程框架。在此编程框架中，用户需要将其应用程序表示为有向无圈图，节点程序表示为串行程序，然后使用Dryad方法组织这些程序。在分布式系统中，用户不需要考虑节点的选择，节点和通信的错误处理方法简单明了，内置在Dryad框架中，满足分布式程序的可扩展性、可靠性和性能要求。

Dryad使用虚拟节点来解决分布式并行问题。根据机器的性能，一个真实的物理节点可能包含一个或多个虚拟节点（逻辑节点）。任务程序可以分为两个相等的部分（每个都是一个虚拟节点），远远超过了资源的数量。现在假设有S资源，那么每个资源承担O/S相等的份额。当一个资源节点离开系统时，它所负责的相等份额将被重新分配到其他资源节点，当一个新节点被添加时，它将从其他节点“窃取”到一定数量的等量共享。

Dryad执行过程可以看作是一个二维管道流处理过程。在每个节点可以有多个程序执行的情况下，通过该算法可以同时处理大规模数据。

微软的Dryad类似于Google的Map Reduce映射原则，但区别在于Dryad通过Dryad LINQ实现了分布式编程。通过使用Dryad LINQ编程，普通程序员编写的大型数据并行程序可以轻松地在大型集群中运行。Dryad LINQ开发的程序是一组序列LINQ代码，它可以对数据集执行任何副作用的操作，编译器会自动将部分数据并行转换成并行执行计划，由底层的Dryad平台计算。这将生成每个节点要执行的代码和静态数据，并为需要传输的数据类型生成序列化代码。

Dryad LINQ使用了与LINQ相同的编程模型，并扩展了少量的操作符和数据类型，用于数据并行分布式计算。NET强类型对象。对通用命令式和声明式编程（混合编程）的支持使LINQ代码或数据（Treocodeasdata）的性质永久化。