面向云计算的任务调度优化关键技术

在云计算系统中，任务种类多、规模大，且每个任务还会分为多个子任务。子任务的数量远大于云计算节点数，使得每个节点均要执行多个子任务。在这种情况下，任务调度优劣直接影响云计算的服务质量，因此如何对云计算任务进行合理调度是云计算系统研究中的一个难题。

在云计算实际环境中，一个虚拟资源可以抽象为一个具有一定属性的节点，该节点具有内存属性、CPU属性或带宽属性。云计算系统的任务优化调度模型是指根据最优化方法，依托云计算系统架构不同层的任务调度的需求而建立的任务优化问题求解模型，其要素包括模型建立、策略生成、调度优化调整、应用调度策略等过程，即进行问题求解，生成调度策略，使得任务合理地映射到节点上，最终按照最优调度方式执行完成。

在云计算系统的任务优化调度研究过程中，经典的任务调度模型被广泛地应用在云计算系统的任务调度研究领域，并不断地在多个方面得到改进。这些调度模型具有快速进行任务调度处理的优势，但是同样也存在着调度决策优化目标需要进一步改进和提高的缺陷。

（1）Hadoop是目前应用于大数据处理的热门分布式计算框架，具有可靠性、可伸缩性。HDFS的上一层是MapReduce引擎，其广泛地应用于各类应用程序中，如在Google的应用中，包括分布排序、Web连接图反转、反向索引构建、文档聚类、机器学习等。Hadoop按位存储和处理数据，在可用的计算机集簇间分配数据并完成计算任务；在节点之间动态地移动数据，保证了各个节点的动态平衡，并且自动保存数据的多个副本，使失效的副本能够自动得到重新分配。

Hadoop由许多元素构成，其最底部是 HDFS（Hadoop Distributed File System）。HDFS是一个能够面向大规模数据使用的、可进行扩展的文件存储与传递系统。它使得实际上通过网络访问文件的动作，在用户看来，就像访问本地磁盘一般。其结构如图2-1所示。

图2-1　HDFS数据传输简化结构

从用户使用的角度来说，MapReduce强制定义了映射（Map）和规约（Reduce）两个阶段，且定义了两阶段之间的数据输入输出格式，如图2-2所示。

图2-2　MapReduce的执行流程

用户程序首先调用的MapReduce库将输入文件分成多个数据片段，然后用户程序在集群中每个计算节点上创建程序副本。在副本程序中有一个特殊的程序，称为Master，除此以外，副本中其他的程序称为Worker程序。Master分配M个Map任务（Map Task）和R个Reduce任务（Reduce Task），Map任务对一些独立元素组成列表的每一个元素进行指定的操作，同时，每个元素都能被独立操作。该过程中原始列表没有被更改，更改的数据被存放在创建的一个新的列表中，即Map的操作是可以高度并行的。Reduce的操作指的是对一个列表的元素进行适当的合并，如定义一个化简函数，通过让列表中的元素跟自己相邻的元素相加，把列表减半，依次进行迭代运算直到列表只剩下一个元素。当具有大规模的运算并且相对独立的情况下，Reduce操作在高度并行的环境下也同样适用。

用户程序通过套用这种模型来抽象自身的运算逻辑，以此简化用户编程接口，降低编程难度，同时在这种模型的基础上，MapReduce框架可以自动完成各种调度优化和容错处理工作，但是固定的编程模型在一定程度上限制了它的通用性，比如MR模型中所有的计算节点只能接受统一格式的一组输入数据，也只能输出一组数据，无论是否需要，用户逻辑都必须由匹配的Map和Reduce阶段组成。

（2）Percolator是由Google推出，在海量数据（PB级）上实现增量计算的平台［65］。它使得在已有的结果集上进行小粒度的更新更加快速，它能持续更新索引系统，从而无须从头重新处理一遍整个系统。为了提高效率，MapReduce和其他批量处理系统可以进行大数据批量处理，却无法处理单个小规模的数据更新。Percolator系统解决了该问题，它能对一个大数据集增量处理更新，因此从数据更新的方面，用Percolator替代MapReduce，每天处理相同数量的文档，能在搜索结果中将文档平均搜索时间减少50%。

（3）Pregel是Google公司的一个基于分布式内存的支持图计算的分布式框架［66］。由于众多的图算法都包含迭代过程，而Pregel采用BSP模型，即“计算—通信—同步的模式，来实现分布式迭代计算。同时Pregel采用消息传递机制在分布式节点间通信，并通过“Superstep”来控制同步。Pregel将目标图类问题的运算模型归结为在图的拓扑节点上迭代执行特定的算法，每次迭代称为一个Superstep。在Pregel中，数据模型的主要概念包括节点、边和消息。在每个Superstep步骤中，各个节点执行相同的用户定义函数来处理数据，更新自身的状态乃至更改整个图的拓扑结构（如增减节点、边等）。每个节点的边则用来链接相关的目标节点，通过发送消息给其他节点传递数据。整个处理流程中，数据的接收和处理是以Superstep为节拍来同步的，在一个Superstep中各个节点所发送的消息，直到下一个Superstep里才会被目标节点所接收和处理，同时触发状态变更。这种基于节拍的处理流程，很大程度上简化了数据同步的处理。每个节点在当前Superstep中处理完数据后，会投票决定自身是否停止处理，如果没有被消息再次触发，在以后的Superstep中就不会调度该节点进行运算。当所有节点都停止后，整个迭代过程结束。

在实现过程中，Pregel的进程也分为Master和Worker，每个Worker负责处理一部分的节点（以特定的算法对节点进行分区Partition），Master则负责调度Superstep。为了减少Worker之间数据传输的开销，一方面Worker内部所有节点的消息会被放入队列中批量传输；另一方面，Combiner类在一些场合里（如Sum）可以被用来在消息传递前进行消息（也就是数据）合并。此外Pregel还提供了Aggregator类来实现全局的通信、数据同步、统计等工作，每个Worker先在本地做规约，再将结果发送给Master，Master做完全局规约后会在下一个Superstep开始的时候将结果再分发给各个节点使用。Pregel同时提供了许多类似消息聚集（Combiner）的系统优化，并提供容错等功能。此外，Pregel的编程模型以结点为基础，编程模型简单易用，弥补了涉及图的算法的不足。

（4）Piccolo是一个提供分布式键—值数据表结构的系统架构，用户通过调用常用的表操作（Put和Get等）来实现各种算法，通常包括PageRank、K-means等具有迭代计算的算法［67］。每个 Piccolo节点在内存中维护相应的数据表，通过MPI实现节点间通信，根据节点间传递的消息来更新远程数据表项。同时，Piccolo提供基于位置的数据访问优化，并且利用累加的操作函数来避免写—写冲突。Piccolo提供的API允许用户像操作单机数据表一样来操作分布式数据表，极大地减轻了用户编写分布式程序的压力。

（5）Nova是雅虎所使用的分布式数据处理架构，其原理是把数据处理过程看成数据不断采集、持续计算的过程［68］。Nova系统将数据相关的操作分为计算过程和数据容器，计算过程的数据会根据逻辑的设置复制（Snapshot）到一个新的数据容器内。

（6）Dryad是一个通用的粗粒度的分布式框架［69］。Dryad的程序运行结构如图2-3所示。

图2-3　Dryad程序运行结构

Dryad的核心数据模型由计算节点（Vertex）和数据通道（Channel）两部分组成，用户通过实现自定义的Vertex节点来执行定制的运算逻辑，节点之间通过各种形式的数据通道传输数据。用户的运算逻辑本身通常是顺序执行的，而与分布式相关部分的逻辑则由Dryad框架来实现。

Dryad的任务管理模块RM在应用程序内部维护了一个基于有向无环图DAG的计算节点依赖关系图。任务管理模块通过命名服务器来获取可用的服务器列表，然后通过在这些服务器上运行的守护进程来调度和执行计算节点。各个计算节点之间通过例如文件、管道、网络等形式的数据通道交换数据。

对于应用了DAG图的Dryad，在其应用中，允许用户动态地改变DAG调度拓扑图，该操作主要是通过在计算节点中把实际所处理的数据相关信息反馈给作业管理模块来实现的。这样操作使得最优的调度拓扑结构形式会取决于实际的输入数据、中间计算结果或者当时所处的运行环境等因素。

（7）Storm是个实时的、分布式的“流处理”框架［70］。同Hadoop一样，Storm也可以处理大批量的数据，除此之外，Storm在保证高可靠性的前提下，还可以让处理进行得更加实时，即所有的信息都会被处理。Storm同样还具备容错和分布计算等特性，这使得Storm可以扩展到不同的机器上进行大批量的数据处理。

随着应用业务的发展，用户在使用Strom时希望该系统是可扩展的，此时，用户只需要添加机器和改变对应的拓扑设置。Storm使用Hadoop Zookeeper进行集群协调，这样可以使得大型集群的良好运行得到充分保证。Strom可为上层应用提供统一的资源管理和调度，它的引入为集群在利用率、资源统一管理和数据共享等方面带来了巨大好处。对于Storm，与Hadoop不同的是，Storm是实时处理模型，是针对在线业务而存在的计算平台。Storm中的数据以Stream的方式，并按照拓扑的顺序，依次处理并最终生成结果。对于大批量数据处理，MapReduce程序在任务完成之后就停止了，但由于Storm是用于实时计算的，所以，相应的处理程序会一直执行直至手动停止。

Storm的容错机制表现为一旦某个拓扑被递交，Storm会一直运行它直到拓扑被废除或者被关闭。在执行中出现错误时，也会由 Storm重新分配任务，这样，一个节点失效了也不会影响其他的应用。Yahoo公司推出的S4计算框架、伯克利大学D-Streams计算框架以及Hadoop提出的计算框架都是基于数据流实现类Streaming概念的。

（8）YARN是在Hadoop基础上开发的，并对可伸缩性（支持1万个节点和20万个内核的集群）、可靠性和集群利用率进行了提升［71］。YARN实现这些需求的方式是把MapReduce中的JobTracker的两个主要功能，即资源管理和作业调度/监控，分成了两个独立的服务程序——全局的资源管理RM（Resource Master，RM）和针对每个应用的管理（Application Master，AM）。YARN的结构如图2-4所示。

图 2-4　YARN 结构图(www.xing528.com)

资源管理：负责接收用户请求，并启动应用管理，通过节点管理来监控其负责的服务器的状态，进行全局的资源分配和调度。资源管理中包含以下两个组件：调度器，根据所采用的具体的调度算法，将资源分配给各个应用；应用管理器，资源是以容器的形式进行封装的，应用管理器负责接收任务，并管理所有的应用管理。

节点管理：管理各个节点的信息，向资源管理器报告当前的节点状态，处理来自应用管理和资源的命令。

节点：每个任务分配一个节点，该任务只能在对应的节点中执行，使用该节点资源。

YARN从某种意义上来说可以作为一个云操作系统，其主要负责集群的资源管理。在此操作系统之上可以开发各类应用程序，例如批处理MapReduce、流式作业Storm以及实时型服务Storm等。这些应用可以同时利用Hadoop集群的计算能力和丰富的数据存储模型，共享同一个Hadoop集群和驻留在集群上的数据。此外，这些新的框架还可以利用YARN的资源管理器，提供新的应用管理器来实现。

（9）Spark Streaming是构建在Spark上处理流数据（Stream）的框架［72］。基本原理是将流数据分成小的时间片断，以类似批量处理的方式来处理这部分数据。Spark Streaming构建在Spark上，一方面是因为Spark的低延迟执行引擎虽然比不上专门的流式数据处理软件［73，74］，但也可以用于实时计算；另一方面，相比基于记录的其他处理框架（如Storm），一部分窄依赖的数据集可以从源数据重新计算从而达到容错处理的目的。此外，小批量处理的方式使得它可以同时兼容批量和实时数据处理的逻辑和算法，方便了一些需要历史数据和实时数据联合分析的特定的应用场合。

Spark的应用逐渐扩展，当前Spark已不仅仅用于实时计算，同时向通用大数据处理平台发展，Spark提供的FIFO和Fair两种调度算法也在不断地完善中。

（10）Samza同样是处理数据流的分布式架构［75］。Samza的流单位不是元组，也不是Dstream，而是消息。在Samza中，数据流被切分开来，每个部分都由一组只读消息的有序数列构成，这些消息每条都有一个特定的ID。该系统还支持批处理，即逐次处理同一个数据流分区的多条消息。Samza的执行与数据流模块都是可插拔式的。

（11）利用博弈论作为理论基础实现任务调度。博弈论主要研究公式化的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法［76］。博弈论考虑博弈中的个体的预测行为和实际行为，并研究它们的优化策略。

博弈的类型划分：

从是否具有约束的角度考虑，博弈论分为合作博弈和非合作博弈。合作博弈和非合作博弈的区别在于相互发生作用的当事人之间有没有一个具有约束力的协议，如果具有约束力，则为合作博弈，如果没有约束力，则为非合作博弈。

从行为的时间序列性划分，博弈论进一步分为静态博弈、动态博弈两类。静态博弈是指在博弈中，参与人同时选择或虽非同时选择但后行动者并不知道先行动者采取了什么具体行动；动态博弈是指在博弈中，参与人的行动有先后顺序，且后行动者能够观察到先行动者所选择的行动。

按照参与人对其他参与人的了解程度可划分为完全信息博弈和不完全信息博弈。完全信息博弈是指在博弈过程中，每一位参与人对其他参与人的特征、策略空间及收益函数有准确的信息；不完全信息博弈是指如果参与人对其他参与人的特征、策略空间及收益函数信息了解得不够准确或者不是对所有参与人的特征、策略空间及收益函数都有准确的信息。

在市场经济中，由于合作博弈论比非合作博弈论复杂，因而在理论上的成熟度远远不如非合作博弈论。非合作博弈的应用更广泛，博弈论一般是指非合作博弈。非合作博弈又分为完全信息静态博弈、完全信息动态博弈、不完全信息静态博弈和不完全信息动态博弈。与上述四种博弈相对应的均衡概念分别为纳什均衡（Nash equilibrium）［77-80］、子博弈精炼纳什均衡（Subgame perfect Nash equilibrium）、贝叶斯纳什均衡（Bayesian Nash equilibrium）和精炼贝叶斯纳什均衡（perfect Bayesian Nash equilibrium）。

博弈的要素：

局中人：在一场竞赛或博弈中，每一个有决策权的参与者称为一个局中人。只有两个局中人的博弈现象称为“两人博弈”，而多于两个局中人的博弈称为“多人博弈”。

策略：一局博弈中，每个局中人都有权利选择实际可行的完整的行动方案，即方案不是某阶段的行动方案，而是指导整个行动的一个方案，一个局中人的一个可行的自始至终全局筹划的行动方案，称为这个局中人的一个策略。如果在一个博弈中，局中人都总共有有限个策略，则称为“有限博弈”，否则称为“无限博弈”。

得失：一局博弈结局时的结果称为得失。每个局中人在一局博弈结束时的得失，不仅与该局中人自身所选择的策略有关，而且与全局中人所取定的一组策略有关。所以，一局博弈结束时每个局中人的“得失”是全体局中人所取定的一组策略的函数，通常称为支付函数。

对于博弈参与者来说，存在着唯一的博弈结果。根据以上理论分析，针对云数据中心，任务调度的条件：

① 有一组具有不同工作量的任务；

② 存在一组处理速度不同的处理器。

（12）纳什均衡是一个稳定的博弈结果。纳什均衡是指在一策略组合中，所有的参与者面临某一种情况，当其他人不改变策略时，该参与者此时的策略是最好的。也就是说，此时如果参与者改变策略，参与者的支付将会降低。

在纳什均衡点上，每一个理性的参与者都不会有单独改变策略的冲动。纳什均衡点存在性证明的前提是“博弈均衡偶”。“均衡偶”是在二人零和博弈中，局中人A采取其最优策略a*，局中人B也采取其最优策略b*，如果局中人B仍采取b*，而局中人A却采取另一种策略a，那么局中人A的支付不会超过他采取原来的策略a*的支付。这一结果对局中人B亦是如此。

由此，“均衡偶”的明确定义：一对策略a*（属于策略集A）和策略b*（属于策略集B）称之为均衡偶，对任一策略a（属于策略集A）和策略b（属于策略集B），总有：偶对（a，b*）≤偶对（a*，b）≤偶对（a*，b*）。

对于非零和博弈同样有如下定义：一对策略a*（属于策略集A）和策略b*（属于策略集B）称为非零和博弈的均衡偶，对任一策略a（属于策略集A）和策略b（属于策略集B）总有：对局中人A的偶对（a，b*）≤偶对（a*，b*）；对局中人B的偶对（a*，b）≤偶对（a*，b*）。

根据上述定义，则得到纳什定理：任何具有有限纯策略的二人博弈至少有一个均衡偶，这一均衡偶就称为纳什均衡点。

经典的分配模型的表示为对不同处理器的任务分配结果，其中纳什均衡状态表示为当所有其他任务调度分配处理器策略一定时，单个任务无法通过改变其自身的任务调度策略取得更高的收益，此时则称任务组达到纳什均衡。

纳什均衡表现为两位或两位以上的竞争者参与竞争，各自具有初始效用值，在竞争中尽可能取得双赢局面，使得其总的效用值最大，该理论在云计算系统中体现为保证各个虚拟机的特定资源需求，保证虚拟机之间资源竞争的公平性［81，82］。