面向大数据平台基于最大化收益的MapReduce作业调度方法及装置

摘要

本发明公开了一种云服务商奖惩收益模式下的MapReduce作业调度方法和装置，所述方法包括以下步骤：接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。本发明根据服务商收益最大化的目标对作业的收益与赔付代价进行衡量评估，满足服务商最大收益、平台最大资源利用以及作业最短完成时间的作业调度目标。

说明书

技术领域

本发明属于云平台作业调度优化领域，具体涉及一种云服务商奖惩收益模式下的MapReduce作业调度方法和装置。

背景技术

近些年，随着各种各样的数据呈现出爆炸式的增长趋势，对于海量数据更高效的分析和处理需求也越来越迫切。传统的数据处理技术和工具已无法满足当前的分析和处理需求，因此新出现的大数据计算平台为解决新需求提供了强有力的支撑。由于大量数据的高效处理要求与处理成本之间的矛盾关系，从而产生了大数据计算平台服务提供商为用户提供便捷和较低成本的计算服务。服务商依据现有的大数据技术建立了可以公用的大数据计算平台，用户只需要向计算平台提交自定义的作业，按照服务商与用户签订的服务等级协议(Service Level Agreement,SLA)规定服务的具体细节。通常SLA中定义了服务类型、服务质量以及收益模式等内容。常见的服务商收益模式主要是用户按完成效果付费或称为按完成时限付费，即用户在提交作业的同时也给出完成时间的要求，服务商只有在规定时间完成该作业才能获得相应额报酬，否则将会按照协议中签订的要求进行赔偿。然而在多用户共享平台资源的条件下，会出现平台资源利用率最大化与最大程度满足用户Qos需求的矛盾，这样会使得服务商无法获得最大收益，同时也会导致平台资源利用率降低，所以平台服务商制定高效的作业调度策略就显得尤为重要。

由于本文针对的研究对象主要是在平台现有的计算资源条件下，多用户提交的大量有截止时间的离线作业，所以在满足原有收益模式的前提下，用户提交的作业包括以下部分：1)用户自定义的应用程序，即提交作业的具体内容；2)每个作业的截止时间，即用户对作业最终完成时间的要求；3)服务商在指定时间内完成每个作业可获得的收益；4)作业完成时间超过了截止时间时服务商将会按照收益的比例进行赔偿。基于原有收益模式策略和现有的作业调度策略，服务商没有考虑到用户对于作业截止时间的准确考量和对于作业执行的迫切性需求，并且也没有考虑作业调度结果对平台资源利用率的影响。

如何在一定的大数据计算资源环境下，制定高效的作业调度策略使得服务商能够获得最大收益的同时，为用户确定每个作业较准确的完成时间，以及达到平台资源利用率最大的要求，尚缺乏有效的解决方案。

发明内容

为克服上述现有技术的不足，本发明在Hadoop2.x的Yarn资源管理系统的基础上提出了一种云服务商奖惩收益模式下的MapReduce作业调度方法，根据服务商收益最大化的目标对作业的收益与赔付代价进行衡量评估，经过整体收益权衡后选择放弃一些收益较小，赔付代价较小的作业，满足服务商最大收益、平台最大资源利用以及作业最短完成时间的作业调度目标。该方法能够根据用户提交的作业信息和集群中已有的资源信息，将当前所有用户提交的作业生成相应的作业调度策略。具体任务分配方法仍然遵循MapReduce的动态分配原则，因此不会对MapReduce中负载均衡等其他性能特性造成影响。

为实现上述目的，本发明采用如下技术方案：

一种云服务商奖惩收益模式下的MapReduce作业调度方法，包括以下步骤：

接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；

根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；

根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。

进一步地，所述作业对应的任务执行时间和数量确定方法为：接收用户提交的作业后，对作业进行预执行，确定任务的执行时间和对应数量。

进一步地，作业的奖惩收益模式为：

其中，j_profit表示该作业在截止时间之前完成的收益与，f(j_profit)为奖惩共存函数，表示额外的奖励或惩罚；j_Nm和j_Nr分别表示该作业Reduce任务数量和Map任务数量；R为平台中可以使用的总计算资源，J为需要调度的作业总数量。

进一步地，根据奖惩共存函数的奖惩分段范围，得到最大标准时间T的集合：

当时，完成作业j可获得相应奖励；当t_standard＝j_deadline时，完成作业j的奖励为0；当t_standard＝b×j_deadline时，完成作业j后的惩罚达到最大值。

进一步地，所述每个作业在不同奖惩阶段的最大轮数组合方案集确定方法包括：

根据作业的已知信息计算了每个作业的Map和Reduce任务的最少执行轮数，每轮任务的最短执行时间以及在每个奖惩阶段的最大标准时间；

根据任务的每轮最短执行时间与每个奖惩阶段的最大标准时间，得到作业的最大轮数组合方案集。

进一步地，任务的最少执行轮数计算方法为：

在全部动态可分配资源只分配给一个作业的情况下，RN_m是作业j的Map任务的最少执行轮数；RN_r是Reduce任务的最少执行轮数；t_least表示作业j最短的执行时间。

进一步地，所述作业的在每个奖惩阶段的最大轮数组合方案集的确定方法包括：

对于每个奖惩阶段，如果最大标准时间大于等于任务最短执行时间，则获取Map和Reduce任务的轮数组合方案A；

判断采用方案A的剩余时间是否大于等于k轮Map任务执行时间，若是，得到轮数组合方案B，以及采用方案A和B的剩余时间，执行下一步；否则，得到该奖惩阶段的轮数组合方案集plan_{jm_t}＝{A,B}；

进一步判断采用方案A和B的剩余时间是否大于等于i轮Reduce任务执行时间，若是，得到轮数组合方案C，方案A、B和C构成该奖惩阶段的轮数组合方案集plan_{jm_t}＝{A,B,C}；

判断采用方案A的剩余时间是否大于等于i轮Reduce任务执行时间，若是，得到轮数组合方案D，执行下一步；否则，得到该奖惩阶段的轮数组合方案集plan_{jr_t}＝{A,D}；

进一步判断采用方案A和D的剩余时间是否大于等于k轮Map任务执行时间，若是，得到轮数组合方案，得到该奖惩阶段的轮数组合方案集plan_{jr_t}＝{A,D,E}；

该任务的轮数组合方案集为Plan_{j_t}＝{A}∪plan_{jm_t}∪plan_{jr_t}；

根据同一奖惩阶段中，轮数不超过任务数量的原则，获取参数i和k的最大值，得到最大轮数组合方案集。

进一步地，所述作业调度方法包括：

根据所有作业在j_t_standard＝j_deadline/a时的最大奖励值，确定被调度的作业并且选择最大轮数组合方案集；

所述作业调度过程中，当资源利用率大于给定阈值时，则空闲资源，直到前一任务执行完成后，在剩余任务中选择局部收益最大的任务进行串行调度；

而当资源利用率小于给定阈值时，将要调度的任务与前一任务并行执行；

将所有作业加入到调度队列，根据每个作业相应的任务轮数组合方案，计算全局收益值，全局受益值最大的组合方案即调度策略。

进一步地，在选择局部收益最大的作业时，通过每个作业的截止时间与前一任务的完成时间差所在范围，比较每个作业在该时间范围内可获得的奖励或惩罚值，选择出使得局部收益最大的作业和相应的任务轮数组合方案。

进一步地，在选择作业加入到调度队列之前，记录前一任务有空余资源时的开始时间点，与每个作业的最大标准时间进行比较，当剩余资源能够满足最大标准时间范围内的任务最大轮数要求时，选择奖惩值最大的作业加入到调度队列，对于惩罚值已达到最大的作业则放在调度队列最后进行调度。

根据本发明的第二目的，本发明还提供了一种云服务商奖惩收益模式下的MapReduce作业调度优化装置，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现以下步骤，包括：

接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；

根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；

根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。

根据本发明的第三目的，本发明还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时执行以下步骤：

接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；

根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；

根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。

本发明的有益效果

1、本发明提出一种云服务商奖惩收益模式下的MapReduce作业调度方法，以RPModel中的收益值为标准，根据各个作业的Map和Reduce任务执行时间，确定出作业在不同奖惩阶段的Map和Reduce的最大轮数组合以及最大标准时间；在满足平台资源利用率的前提下，选择出具有全局最大收益的作业和该作业的任务最大轮数方案，从而制定出TS策略。本发明设计的调度优化方法所生成的TS策略能够最大程度的缩短每个作业的完成时间，提高平台资源利用率。

2、本发明首次考虑到了用户对服务商的一种奖励政策，即当服务商在作业截止时间之前的一定时间范围内完成作业时对服务商给予相应的奖励值。此收益模式针对的是不确定作业截止时间是否准确的用户，并且该类用户有较短的时间需求要完成所提交作业。但由于用户提供的作业截止时间并非准确，服务商为了满足用户较短的作业完成时间需求，所以尽量缩短每个作业的完成时间。当该完成时间范围比用户提供的截止时间短时，服务商将该作业的完成时间作为较准确的截止时间反馈给用户，使得用户以后提交相同的作业时就可以提供较准确的截止时间，并且推进了用户处理作业群的整体行为。奖惩共存收益模式的提出首次实现了服务商与用户的利益共赢。

附图说明

构成本申请的一部分的说明书附图用来提供对本申请的进一步理解，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。

图1为云服务商奖惩收益模式下的MapReduce作业调度方法流程；

图2为FIFO,Fair,EDF和MPCRS4个对比算法在全部作业的平均完成时间指标上的结果；

图3为每个作业在不同调度器的调度下执行完毕后的完成时间结果；

图4为使用各个调度器调度作业时的作业延迟比例；

图5为使用各个调度器调度作业时的作业延迟时间；

图6为使用不同调度器时的最大化收益；

图7为不同调度器为各个作业在9个统计间隔时的资源利用率情况；

图8为使用不同的调度器为作业分配资源后，作业在各个统计间隔时的平台资源利用率；

图9为不同数据量情形下作业延迟率；

图10为不同数据量情形下作业完成时间；

图11为不同数据量情形下资源利用率；

图12为不同数据量情形下最大利益；

图13为平台不同资源利用率的阈值下作业延迟比例。

具体实施方式

应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

本文设计了一种云服务商奖惩收益模式下的MapReduce作业调度方法，针对作业截止时间非准确性设定和作业有迫切性执行需求的特定用户，结合服务商与用户之间的利益关系，以奖惩共存收益模式(RP Model)中的收益值为评价标准，根据各个作业的Map和Reduce任务执行时间，确定出作业在不同奖惩阶段的Map和Reduce的最大轮数组合以及最大标准时间，形成该作业的最短完成时间方案；在此基础上，根据多用户提交的作业集合的内容和已知作业的情况，生成相应的基于任务的作业调度策略(TS)，使得服务商能够获得最大收益和达到平台资源利用率最大的要求。

实施例一

本实施例公开了一种云服务商奖惩收益模式下的MapReduce作业调度方法，包括以下步骤：

接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；

根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；

根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。

作业收益模式

根据以上关于作业的收益与赔付信息，结合平台中可分配的资源数量，收益最大化的评价标准RP Model如下：

公式(1)表示完成所有作业后可获得的收益和，其中每个作业的实际收益是由该作业在截止时间之前完成的收益j_profit与额外的奖励或者惩罚f(j_profit)组成。公式(2)确保了将要运行的任务每次并行请求资源时资源数不超过平台中可动态分配的资源总和。奖惩共存函数f(j_profit)表示如下：

其中α是在作业实际完成时间比规定的截止期限短a倍时可获得的奖励比率，β是作业的实际完成时间比规定的截止期限长但没有超过截止时间的b倍时作业的赔付比率，γ是作业实际完成时间超过规定截止时间b倍时所要赔付的收益倍数。在考虑到尽量使每个作业都在截止期限之前完成，所以设置赔付率值要比奖励率值大，即α≤β≤1；而作为长时间超出截止期限的惩罚设置γ≥1。由于不能简单的根据作业实际完成时间和截止时间的大小就规定用户要付出奖励值或服务商付出赔付值，而应该是在两者差值超过一定范围后用户才需要支付额外的奖励值或服务商支付额外的赔付值，故设a，b＞1。

确定每个作业的Map和Reduce任务执行时间。

用户提交作业时已知的各种信息中包括作业j中每一轮Map任务的执行时间j_Tm和每一轮Reduce任务的执行时间j_Tr，并且j具有的Map数量j_Nm和Reduce数量j_Nr，但可能存在用户不知道任务的执行时间和数量的问题。针对这样已知信息不全的情况，在用户提交作业后，服务商首先在平台中执行一遍作业，得到任务的执行时间和对应数量，将得到的结果存入属于该作业的配置文件中。

根据任务执行时间确定作业轮数计算任务最大轮数组合方案与最大标准时间。

根据每个作业的Map和Reduce任务执行时间，以根据Profit Model获得的收益值为标准，确定出每个作业在不同奖惩阶段的Map和Reduce最大轮数组合以及最大标准时间。

本文主要是在MapReduce框架基础上提出的，在计算平台中认为每个节点的处理能力都大致相同，由于平台中的资源是统一进行管理和分配，所以可动态分配的Container资源用R表示。

由于此收益模式针对的是不确定作业截止时间是否准确的用户，并且该类用户有较短的时间需求要完成所提交的作业。对于该类任意用户提交的作业j已知如下信息：

1)j的截止时间j_deadline；

2)在j_deadline之前j被完成后服务商可获得的收益j_profit；

3)如果j的实际完成时间j_completion的a倍比j_deadline还要短，那么用户要按照SLA中规定的奖励比率α，支付除收益以外的奖励值j_profit×α×a；

4)j的实际完成时间j_completion超过j_deadline时，按照服务商与用户签订的SLA中规定的赔付比率β进行赔偿，即当j_deadline＜j_completion≤b×j_deadline时，服务商需要赔付给用户的费用为j_profit×β×b；当j_completion＞b×j_deadline时，则需要赔付给用户原本j收益的γ倍，即j_profit×γ；

5)j具有的Map数量j_Nm和Reduce数量j_Nr；

6)j中每一轮Map任务的执行时间j_Tm和每一轮Reduce任务的执行时间j_Tr。

为了提高作业的执行效率，在平台资源条件充足情况下，要尽量使同一个作业的多个任务并行执行，而每次并行执行任务的时间称为一轮任务的执行时间，本文不考虑数据倾斜等问题的出现，所以默认每一轮任务的执行时间为单个任务的执行时间且都相等。

根据作业的已知信息计算了每个作业的Map和Reduce任务的最少执行轮数，每轮任务的最短执行时间t_least以及在每个奖惩阶段的最大标准时间t_standard；

其中有关确定任务轮数的因素具体包括：

在全部动态可分配资源只分配给一个作业的情况下，RN_m是作业j的Map任务的最少执行轮数；RN_r则是Reduce任务的最少执行轮数；公式(6)表达的是作业j最短的执行时间t_least是由任务的最少轮数与每轮任务的执行时间组成。

在不同奖惩阶段时会有相应的最大标准时间t_standard,即根据奖惩共存函数f(j_profit)的奖惩分段范围，可以得到有关最大标准时间的T集合。

当时，完成作业j可获得相应奖励；当t_standard=j_deadline时，完成作业j的奖励为0；当t_standard=b×j_deadline时，完成作业j后的惩罚达到最大值。为了获得在各奖惩阶段的任务最大轮数组合方案，最大标准时间成为衡量任务轮数是否达到最大的标准。

根据任务的每轮最短执行时间与每个奖惩阶段的最大标准时间，得到作业的最大轮数组合方案；

计算作业最大轮数组合方案的方法具体为：

针对每个作业，在每个奖惩阶段，执行以下操作：

如果最大标准时间大于等于任务最短执行时间，则获取Map和Reduce任务的轮数组合方案A(RN_m,RN_r)，以及采用该方案的剩余时间(t_standard-t_least)；

判断剩余时间(t_standard-t_least)是否大于等于k轮Map任务执行时间，若是，得到轮数组合方案B(RN_m+k,RN_r)，以及采用方案A和B的剩余时间(t_standard-t_least-j_Tm×k)，执行下一步；否则，方案A和B构成轮数组合方案集，plan_{jm_t}＝{A,B}；

进一步判断剩余时间是否大于等于i轮Reduce任务执行时间，若是，得到轮数组合方案C(RN_m+k,RN_r+i)，以及采用方案A、B和C的剩余时间(t_standard-t_least-j_Tm×k-j_Tr×i)，方案A、B和C构成轮数组合方案集，plan_{jm_t}＝{A,B,C}；

判断剩余时间(t_standard-t_least)是否大于等于i轮Reduce任务执行时间，若是，得到轮数组合方案D(RN_m,RN_r+i)，以及采用方案A和D的剩余时间(t_standard-t_least-j_Tr×i)，执行下一步；否则，方案A和D构成轮数组合方案集，plan_{jr_t}＝{A,D}；

进一步判断剩余时间是否大于等于k轮Map任务执行时间，若是，得到轮数组合方案E(RN_m+k,RN_r+i)，以及采用方案A、B和C的剩余时间(t_standard-t_least-j_Tm×k-j_Tr×i)，方案A、B和C构成轮数组合方案集，plan_{jr_t}＝{A,D,E}；

该任务的轮数组合方案集为Plan_{j_t}＝{A}∪plan_{jm_t}∪plan_{jr_t}

根据同一奖惩阶段中，轮数不超过任务数量的约束条件下，即(RN_m+k)＜j_Nm且(RN_r+i)＜j_Nr，获取最大轮数组合方案。

算法1展示了如何在各奖惩阶段获得任务最大轮数组合方案以及最大标准时间。首先，算法根据作业的已知信息计算了每个作业的Map和Reduce任务的最少执行轮数、最短执行时间t_least以及在每个奖惩阶段的最大标准时间t_standard(line2-line5)；其次，在每个最大标准时间时，比较了作业最短执行时间与最大标准时间的大小，根据奖惩共存函数f(j_profit)的模式要求，最大标准时间的最小值一定是大于等于最短执行时间，所以在每个奖惩阶段都可以得到一种轮数组合方案A—最大限度地以空间换时间方案，即(RN_m,RN_r,t_standard-t_least)(line8)；最后，根据剩余时间值的大小，找到能够满足执行一轮Map和一轮Reduce任务时间的最大变量值k,i，从而得到方案集(plan_{jm_t}∪plan_{jr_t})—最大限度的以时间换空间方案。由于作业完成时间超过截止时间后服务商就要对用户进行赔偿，所以要尽量保证每个作业的完成时间能够达到最短，而任务的执行轮数会直接影响到作业的完成时间。同一奖惩阶段中，在轮数不超过任务数量的前提下，即(RN_m+k)＜j_Nm且(RN_r+i)＜j_Nr，每个作业轮数越多,不同作业的任务能够并行执行的数量就越多，从而缩短了每个作业的完成时间，保证了服务商的最大收益。

基于最大轮数方案进行作业调度

所述作业调度方法主要步骤如下(参见算法2)：

根据所有作业在j_t_standard＝j_deadline/a时的最大奖励值f(j_profit)，确定被调度的作业并且选择最大轮数组合方案集(line1-line7)；

在前一作业的所有轮数组合方案集中，选择具有局部最大收益的轮数组合方案进行调度(line8-line49)；

将所有作业加入到调度队列后，根据每个作业相应的任务轮数组合方案，计算全局的最大收益值(line50)。

在选择具有局部最大收益的轮数组合方案时，优先考虑平台的资源利用率。

当资源利用率大于给定阈值时，则空闲资源，直到前一任务执行完成后，在剩余任务中选择局部收益最大的任务进行串行调度(line11-line34)：

其中，在选择局部收益最大的任务时，通过每个任务的截止时间与前一任务的完成时间差所在范围，比较每个任务在该时间范围内可获得的奖励或惩罚值，选择出使得局部收益最大的任务和相应的任务轮数组合方案。

假如此时有4个任务备选，当满足f(j₁_profit)>f(j₂_profit)>f(j₃_profit)>f(j₄_profit)>0时，则将j₁号任务加入调度队列并且选择相应时间范围内的轮数组合方案；

当f(j₁_profit)>f(j₂_profit)>0≥f(j₃_profit)>f(j₄_profit)且满足f(j₁_profit)≥|-j₃_profit×γ|+|-j₄_profit×γ|时，则将j₁号任务加入调度队列，如果不满足第二个条件，则选择惩罚值最大的任务加入调度队列；

当0>f(j₁_profit)>f(j₂_profit)>f(j₃_profit)>f(j₄_profit)时，判断所有任务的最大惩罚值，选择惩罚值最大的任务加入调度队列，这样做的目的是使得服务商所付出的代价最小。

而当资源利用率小于给定阈值时(line35-line48)，将要调度的任务与前一任务并行执行，充分利用平台资源，使得资源利用率达到最大。

在选择合适的作业加入到调度队列之前，记录前一任务有空余资源时的开始时间点t_r，t_r与每个作业的最大标准时间t_standard进行比较，当剩余资源能够满足最大标准时间范围内的任务最大轮数要求时，则选择|f(j_profit)|值最大的作业加入到调度队列，对于惩罚值已经达到最大的作业(-j_profit*γ)则放在调度队列最后进行调度。|f(j_profit)|值最大的作业为奖励值最大的作业，或除已达到最大惩罚值作业(-j_profit*γ)以外的惩罚值最大的作业(-j_profit*β*b)。

由于每个被选中的任务都有多种最大轮数组合方案，所以在每选择出一种调度组合方案后则计算相应的局部收益值，最终选择全局收益值最大的调度队列与调度策略进行调度。

调度策略中包含了已选择的任务轮数与开始时间点，这样在调度前就预先指定了对于每个任务中任务的资源分配数与分配时间点。

最终确定的调度队列和调度策略会写入到配置文件中，ASM将会根据配置文件和作业资源请求启动相应作业的AM，为其分配Container资源，使得该作业得以开始运行。在为作业分配了计算资源后，将作业分为Map和Reduce任务，由于MPCRS产生的调度策略是基于任务级别的，所以在分配资源时为作业分配资源即为相应的Map或Reduce任务分配资源。

实施例二

本实施例的目的是提供一种计算装置。

一种云服务商奖惩收益模式下的MapReduce作业调度优化装置，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现以下步骤，包括：

接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；

根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；

根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。

实施例三

本实施例的目的是提供一种计算机可读存储介质。

一种计算机可读存储介质，其上存储有计算机程序，用于指纹图谱相似度计算，该程序被处理器执行时执行以下步骤：

接收用户提交的作业，获取每个作业每一轮Map任务和Reduce任务的执行时间，以及任务数量；

根据每个作业的Map和Reduce任务执行时间和任务数量，根据奖惩收益模式，确定出每个作业在不同奖惩阶段的最大轮数组合方案集以及最大标准时间；

根据奖惩收益模式，基于每个作业的最大轮数方案获取作业调度策略。

以上实施例二和三中涉及的各步骤与方法实施例一相对应，具体实施方式可参见实施例一的相关说明部分。术语“计算机可读存储介质”应该理解为包括一个或多个指令集的单个介质或多个介质；还应当被理解为包括任何介质，所述任何介质能够存储、编码或承载用于由处理器执行的指令集并使处理器执行本发明中的任一方法。

实验验证

实验环境与设置

我们在一个基于Hadoop框架的计算平台中对本发明提出的算法进行验证，使用的版本是Hadoop2.7.1。平台中的所有节点都是同构节点，其中包含1个主节点和20个从节点。每个节点的配置信息为CPU8cores,16GB RAM,1TBhard disk,Red Hat EnterpriseLinux6.2 System。资源管理和调度使用Yarn资源框架，设置Container大小为1core和2GRAM，这样每个节点上有8个container，整个平台中共有160个container。在实验中设置块大小为默认的64M。

实验数据集与实验指标

为了评估算法性能，我们使用PUMA benchmark suits[]中的MapReduce标准应用程序，对于每个应用程序包括多个不同输入数据规模的作业，并且设置每个作业具有相同的优先级，如表1所示，其中包括每个程序的数量、输入数据规模、截止时间以及数据来源。根据作业的开始时间和最长执行时间可以得出作业的截止时间。

表1

MapReduce程序作业数量输入数据规模(GB)截止时间(min)数据来源WordCountJ1/J2/J3/J4/J520/50/100/200/5001/5/15/35/60WikipediaTeraSortJ6/J7/J8/J9/J1020/50/100/200/5001/5/15/35/60TeraGenInverted-IndexJ11/J12/J13/J14/J1520/50/100/200/5001/5/15/35/60Wikipedia

这些程序是典型类型的MapReduce程序，WordCount是CPU密集型，TeraSort是I/O密集型，Inverted-Index既是CPU密集型也是I/O密集型。

在评估MPCRS的效率时，首先将MRNS分别与FIFO、Fair、EDF调度算法在作业完成时间与作业延迟比率方面进行比较。然后再评估使用不同的算法时所能获得的最大收益与平台的资源利用率，我们还讨论作业的输入数据规模对作业的延迟率、完成时间以及平台资源利用率的影响。最后我们研究参数的最优设置对MPCRS的影响。通过以下性能指标评价算法的性能：

●作业完成时间(j_completion)

●作业延迟率(P)

●最大收益(Profit)

●平台资源利用率(Utilization)

根据作业的开始时间和执行时间可以得出作业的完成时间，j_start是作业的开始执行时间，j_execute是作业j的全部任务执行完毕所经历的时间，默认全部的作业都同时到达，作业的完成时间j_completion表示为：

j_completion＝j_start+j_execute(8)

如果作业j的完成时间j_completion超过规定的截止时间j_deadline，即认为作业j已经延迟，N_late为延迟的作业数量，N_total为完成的全部作业数量，则作业延迟率P表示为：

j_profit为在SLA协议中规定的截止时间之前完成作业j可获得的收益，针对服务商可获得的最大收益，可用RP Model中奖惩共存收益函数f(j_profit)衡量：

公式(3)中所提到的α，β，γ分别为奖励比率、惩罚比率以及最大惩罚比率，设置α＝0.3，β＝0.5，γ＝2，a，b分别为时间限定倍数，设置a＝b＝1.5。

定义平台资源利用率Utilization时，使用全部作业完成后所占资源与时间的乘积和平台中整体资源与时间的乘积比例表示：

其中R_total是平台中全部资源数量，T_total是全部作业执行完毕后的总时间，R_taski是作业j中第i轮任务执行所占用的资源数量，T_taski是第i轮任务所需执行时间。

实验结果与分析

本方法的高效性

本小节使用FIFO、Fair以及EDF调度器作为对比算法，从作业执行效果、收益效果以及平台资源利用率三个方面与本发明提出的作业调度优化方法进行对比分析，从而验证其高效性。

FIFO调度是将所有作业按照优先级的顺序排成一个队列，逐个为作业分配平台中的资源，一个作业执行时，就会占用平台中的全部资源。Fair调度是为每个作业分配相对公平的资源数量。EDF算法是根据作业的截止时间需求形成运行队列，为具有较早截止时间需求的作业优先分配所需的资源数量，在一个作业尚未完成前，新到达的具有最早截止时间的作业不可以抢占其资源，只能等到该作业完成后使用。本发明提出的一种云服务商奖惩收益模式下的MapReduce作业调度方法与以上的调度器思想都不相同，是基于最大任务轮数的抢占式调度方式，不能杀死要抢占任务轮的资源，只能等待任务轮完成后，抢占该任务轮所占用的资源。

作业执行的高效性

作业执行效果从全部作业的平均完成时间、每个作业的完成时间、作业延迟比例以及每个作业的延迟倍数的结果中体现。

如图2所示，为4个对比算法在全部作业的平均完成时间指标上的结果。从图中可以看出，FIFO调度器的作业平均完成时间达到了24.3min，依次降低是EDF调度器22.3min、Fair调度器20.8min以及本发明提出的作业调度优化方法18min。FIFO调度器的作业平均完成时间最长，是因为当一个作业正在执行时会占用集群中的全部资源，不能使其他作业开始执行，所以这样就会延长大部分作业的完成时间，导致全部作业的平均完成时间延长。本方法与FIFO、EDF以及Fair相比，作业的平均完成时间有所减短。

如图3所示，为每个作业在不同调度器的调度下执行完毕后的完成时间结果。首先可以看出三个类型的作业随着数据量的增大，作业完成时间在不断变长；其次在数据量相同时，不同类型的作业完成时间差距很小，说明资源的统一分配对不同类型的作业性能不会造成影响；最后通过比较在4种调度器调度下的作业不同执行性能可以看出，使用本发明提出的作业调度优化方法时的作业完成时间明显短于使用其他三种调度器时的时间，但Job9使用本发明提出的作业调度优化方法时完成时间高于使用EDF和Fair的时间。在作业执行过程中，可能会出现各种各样的情况。Job9使用本发明提出的作业调度优化方法时完成时间较长是因为在选择Job9最大轮数执行方案时，在最大标准时间范围内，所选的任务轮数最多，这样会使得作业的整体完成时间较轮数较少时有所延长，而且在计算时具有一定的时间消耗，所以在作业执行过程中完成时间有一定延长是不可避免的。这个完成时间的延长范围是在可允许的范围内，是可以容忍的。

如图4所示，为使用各个调度器调度作业时的作业延迟比例。从图中可以看出，使用FIFO调度器时延迟率达到46.7％，EDF 26.7％，Fair20％，本发明提出的作业调度优化方法13.3％。FIFO调度器的占用平台资源特点使得作业延迟率较高，从图5中可以看出Job3、Job5、Job9、Job10、Job13它们的延迟时间超出了规定的截止时间1倍，Job11、Job12的则超出了截止时间的1.5倍。EDF虽然是根据截止时间对作业排序，但一个作业在执行时，其他作业仍然不能使用平台的空余资源，只能等待其完成后再执行下一个已排好序的作业，这样同样会时部分作业有所延迟，如图5中Job3、Job10、Job12、Job14。Fair对于每个作业都分配相同的资源，没有考虑到数据量不同的作业情况，所以就会使部分数据量大的作业延迟，如图5中的Job8、Job13和Job15，它们的延迟时间都超出了规定截止时间的1倍。在使用本发明提出的作业调度优化方法调度时虽然Job9和Job10的完成时间也超过了截止时间期限，但对于作业整体执行性能而言，本发明提出的作业调度优化方法要优于FIFO、EDF以及Fair。

收益最大化

根据上节作业执行的高效性实验中可以得出每个作业的执行性能，但本文设计作业调度优化算法的最终目标是使服务商获取最大收益，所以依据公式(1)和(3)，得到了如下图6所示的使用不同调度器时的最大化收益。其中Ideal为总收益的理想值，

从图中可以看出使用不同的调度器时，服务商可以获得的最大收益差值较大。其中使用FIFO获得的总收益与理想值Ideal差值最大，使用本发明提出的作业调度优化方法可获得的总收益与理想值Ideal差值最小。由于大部分作业的奖励值仍为0和有部分延迟作业的存在，所以本方法可获得的总收益与理想值还是有一段距离的。

平台资源利用率的高效性

图7展示了4个调度器为各个作业公平分配资源后，各个作业在9个统计间隔时的资源利用率情况。如图8所示，使用不同的调度器为作业分配资源后，作业在各个统计间隔时的平台资源利用率。

作业大小对MPCRS的影响

三个不同类型的应用程序分别在20G,50G,100G,200G,500G混合有60个作业，计算在各个数据量情形下作业延迟率，60个作业在不同数据量时有相同的截止时间。如图9-12。

平台资源利用率的阈值调优

如图13所示

X：阈值大小

Y：作业延迟率

各数据量的60个作业测量。

本发明结合服务商与用户之间的利益关系，提出一种云服务商奖惩收益模式下的MapReduce作业调度优化方法，以RP Model中的收益值为标准，根据各个作业的Map和Reduce任务执行时间，确定出作业在不同奖惩阶段的Map和Reduce的最大轮数组合以及最大标准时间；在满足平台资源利用率的前提下，选择出具有全局最大收益的作业和该作业的任务最大轮数方案，从而制定出TS策略。实验结果表明，本发明设计的调度优化方法所生成的TS策略能够最大程度的缩短每个作业的完成时间，提高平台资源利用率，并且在服务商获得最大收益的同时，用户能够得到较为准确的截止时间，真正意义上实现了服务商和用户的利益共赢。

本领域技术人员应该明白，上述本发明的各模块或各步骤可以用通用的计算机装置来实现，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。本发明不限制于任何特定的硬件和软件的结合。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。