一种最小化租赁成本的公有云服务租赁方法

摘要

本发明涉及云计算资源调度技术领域，公开了一种最小化租赁成本的公有云服务租赁方法，包括数据预处理、设置任务的虚拟截止时间和任务调度。其中，数据预处理考虑可能发生的数据倾斜现象，利用采样的方法来对数据进行预处理，缓解数据倾斜。设置任务的虚拟截止时间，是为了方便在任务调度的时候，能够在截止期约束下选择合适虚拟机资源。与现有技术相比，本发明有效地降低了云服务代理商的运营成本，解决了现有技术中没有考虑到的数据倾斜问题，并且在截止期约束下为云服务代理商提供了Spark应用在公有云环境中的合理租赁方法，优化了租赁成本。

权利要求

1.一种最小化租赁成本的公有云服务租赁方法，其特征在于，包括：

步骤1，获取Spark应用程序的采样数据，并标记所述采样数据中可能出现数据倾斜的任务为慢任务，将所述慢任务划分成多个子任务；

步骤2，根据所述Spark应用程序的截止期，基于关键路径长度的截止期的截止期划分方法，确定所述Spark应用程序中每个并行计算阶段和计算任务组的子截止期，所述计算任务组包括多个计算单元；

步骤3，根据就绪的计算任务组确定待调度的计算单元优先队列Q，所述待调度的计算单元优先队列Q中计算单元的优先级根据每个计算单元待处理的数据量大小按照降序排列；

步骤4，将所述待调度的计算单元优先队列Q的队头出队作为调度任务，将所述调度任务调度到公有云的资源上进行处理；调度任务时，在满足每个任务子截止期的前提下，将任务调度到多个按需资源中租赁价格代价最小的按需资源上；

所述步骤1包括：

步骤1-1，采用蓄水池算法对用户提交的每个所述Spark应用程序进行采样，将每个计算任务组作为一个蓄水池，采样部分计算单元，作为采样数据，计算所有样本所需处理数据量的均值，即获得每个所述计算任务组中计算单元所需处理数据量的均值；

步骤1-2，根据所述蓄水池算法的抽样比例，建立分布直方图，用于观察数据分布的总体特征；

步骤1-3，根据 ，获得所述计算单元的偏斜因子，所述偏斜因子用于判定是否为可能出现数据倾斜的任务；

其中，表示计算单元所需处理数据量，表示计算任务组中每个计算单元所需处理数据量的均值；

若所述任务的偏斜因子大于或等于0.5，即判定为可能出现数据倾斜的任务，将所述任务标记为慢任务；

步骤1-4，将被标记为所述慢任务的任务放入慢任务集合；

步骤1-5，根据所述采样数据，将所述慢任务的数据划分成计算任务组中每个计算单元所需处理数据量的均值 的预设倍数个数据分区，为每个所述数据分区对应生成一个子任务，所述预设倍数的值为 。

2.根据权利要求1所述的一种最小化租赁成本的公有云服务租赁方法，其特征在于，所述步骤2包括：步骤2-1，根据用户提交的截止期约束和公有云中虚拟机资源的执行速度以及并行计算阶段与计算任务组间的偏序关系，生成相应的拓扑序列，设使用处理速度最快公有云资源预估的时间参数，所述时间参数包括最早开始时间和最晚开始时间；

步骤2-2，根据所述拓扑序列计算每个并行计算阶段的子截止期；

步骤2-3，跟据所述计算任务组所在的层次 ，通过以下公式，确定每个并行计算阶段及计算任务组的子截止期 ：其中， 为计算得到的第j个计算任务组的子截止期， 表示第j个计算任务组的最晚结束时间，为给定的Spark应用的截止期；所述计算单元 的子截止期等于计算单元 所在第j个计算任务组的子截止期；

步骤2-4，将初始并行计算阶段队列SJ的队头元素，即计算任务组队列S出队，将所述初始并行计算阶段队列SJ队头元素中的所有计算单元加入待调度计算单元优先队列Q中；

步骤2-5，更新所述待调度计算单元优先队列Q，即将所有没有前驱计算任务组，或者，前驱计算任务组已经处理完成的计算任务组中的所有计算单元添加到待调度的计算单元优先队列Q中。

3.根据权利要求1所述的一种最小化租赁成本的公有云服务租赁方法，其特征在于，在所述步骤3之前，还包括初始化实例的资源可用区间表和待调度的计算单元优先队列Q：公有云中的所述实例的资源可用区间表表示为已租赁的预留实例资源的每个节点的可用时间段；其中，所述已租赁的虚拟机资源表示为SR={SR1,SR2,…,SRm}，是一个包含m个处理速度不同的虚拟机资源，其中m≥2，且m为正整数；

初始并行计算阶段队列SJ={Ji | i属于 1~w }，表示Spark应用程序中的所有并行计算阶段，其中w≥2，且w为正整数；

计算任务组队列S={Sj | j属于1~ wi }，其中Sj表示没有前驱计算任务组或前驱计算任务组已经处理完成的计算任务组；

待调度计算单元集合T={Tk| i属于1~wi,j }，其中Tk表示当前可被调度计算单元。

4.根据权利要求1所述的一种最小化租赁成本的公有云服务租赁方法，其特征在于，在所述步骤3之后，还包括：判断计算任务组队列S是否为空；若所述计算任务组队列S为空，则结束；若所述计算任务组队列S不为空，则执行所述步骤4的操作。

5.根据权利要求1所述的一种最小化租赁成本的公有云服务租赁方法，其特征在于，所述步骤4，包括：步骤4-1，判断使用当前云资源的计算单元的完工时间大于计算单元的子截止期的资源存在，若存在，则跳转步骤4-2，若不存在，则跳转步骤4-3；

步骤4-2，根据所述计算单元处理数据量的大小以及偏斜因子，若所述偏斜因子超过2的慢任务选择处理速度高的公有云资源，并更新所述资源可用区间表，跳转步骤4-5；

步骤4-3，检查所述资源可用区间表，若存在实际执行时间超过子截止期，则跳转步骤

4-2，否则跳转步骤4-4；

步骤4-4，为计算单元选择的资源的完工时间不超过其子截止期，且租赁价格最小的按需虚拟机实例；

步骤4-5，从所述待调度的计算单元优先队列Q中删除这一计算单元，若所述任务为计算单元所在计算任务组中的最后一个任务，则删除所述计算任务组队列S中的这一计算任务组。

6.根据权利要求5所述的一种最小化租赁成本的公有云服务租赁方法，其特征在于，在所述步骤4之后，还包括：判断所述待调度的计算单元优先队列Q是否为空；若所述待调度的计算单元优先队列Q不为空，则执行所述步骤4的操作；若所述待调度的计算单元优先队列Q为空，则判断计算任务组队列S是否为空；

若所述计算任务组队列S为空，则结束；若所述计算任务组队列S不为空，则执行所述步骤4的操作。

说明书

一种最小化租赁成本的公有云服务租赁方法

技术领域

[0001] 本发明涉及云计算资源调度技术领域，尤其涉及一种最小化租赁成本的公有云服务租赁方法。

背景技术

[0002] 如今，在云平台上现有的分布式并行计算框架仍然存在诸多挑战，其中，数据倾斜正成为提升系统性能的瓶颈。数据倾斜这一现象通常由数据本身性质引起，且普遍存在于并行计算框架中。具体的，当数据倾斜出现在计算过程中时，由于少量任务的处理时间明显地多于其它任务的处理时间，因而严重降低了整个系统的执行效率，进而严重阻碍系统并行处理的能力。由于大数据的来源主要是社交媒体、电商平台和搜索引擎三大领域，这些数据的最大特征即数据分布极其不均衡，存在着大量热点数据，例如社交媒体中的热门话题、电商平台的爆款商品和搜索引擎的搜索热点，处理这样的数据分布极其不均衡的数据时，特别容易造成在处理过程中的数据倾斜现象，出现个别“慢”任务（Straggler），从而大大延长整个应用的完工时间。

[0003] 数据倾斜被认为是影响并行分布式框架如Spark平台的执行效率的一个关键问题，并且数据量越大，其导致的执行效率问题就越突出。现如今，对于Spark平台中数据倾斜问题的解决方法较少，但是Hadoop平台上的数据倾斜问题的解决方法已有了一些积累。通常，可以按照处理阶段将数据倾斜划分为Map型、Reduce型、Map&Reduce型和Shuffle型这四种类型。对于Map&Reduce型，在SkewTune系统中，如果任务的剩余时间超过1分钟并且集群中有空闲节点，则该系统在不改变默认分区函数的前提下，在检测到任务为Straggler时，重新分配任务中未被处理的数据给其他闲置节点的新任务，通过连接任务的输入顺序和重新组合输出结果的这种独特的方式来缓解数据倾斜问题。但是这种方法的设计和使用均为针对Hadoop平台进行的，难以直接迁移到Spark平台上使用。

[0004] 目前，并行计算框架中数据倾斜问题的解决方法通常大多基于Hadoop平台，并且由于Spark平台基于内存计算的特性，这些方法大多无法直接应用到解决Spark平台中的数据倾斜问题。而现有基于Spark平台数据倾斜问题的研究存在着顾此失彼的现象，片面性地缓解数据倾斜问题，使得SLA问题凸显。

发明内容

[0005] 发明目的：针对现有技术中存在的问题与不足，本发明提供了一种最小化租赁成本的公有云服务租赁方法，从云服务代理商的角度出发，在满足用户应用截止期的情况下，同时考虑数据倾斜问题，采用按需实例的方式，动态按需租赁合适的虚拟机以保证应用在截止期内完成，并最小化云服务代理商的租赁成本。

[0006] 本发明提供的一种最小化租赁成本的公有云服务租赁方法，包括：

[0007] 步骤1，获取Spark应用程序的采样数据，并标记所述采样数据中可能出现数据倾斜的任务为慢任务，将所述慢任务划分成多个子任务；

[0008] 步骤2，根据所述Spark应用程序的截止期，基于关键路径长度的截止期划分方法，确定所述Spark应用程序中每个并行计算阶段和计算任务组的子截止期，所述计算任务组包括多个计算单元；

[0009] 步骤3，根据就绪的所述计算任务组确定待调度的计算单元优先队列Q，所述待调度的计算单元优先队列Q中计算单元的优先级根据每个计算单元的数据量大小按照降序排列；

[0010] 步骤4，将所述待调度的计算单元优先队列Q的队头出队作为调度任务，将所述调度任务调度到公有云的资源上进行处理；调度所述调度任务时，在满足每个所述调度任务的子截止期的前提下，将所述调度任务调度到租赁价格代价较小的按需资源上。

[0011] 进一步地，在一种实现方式中，所述步骤1包括：

[0012] 步骤1-1，采用蓄水池算法对用户提交的每个所述Spark应用程序进行采样，将每个计算任务组作为一个蓄水池，采样部分计算单元作为采样数据，计算所有样本所需处理数据量的均值，即获得每个所述计算任务组中计算单元所需处理数据量的均值；

[0013] 步骤1-2，根据所述蓄水池算法的抽样比例，建立分布直方图；

[0014] 步骤1-3，根据 ，获得所述计算单元的偏斜因子：

[0015] 其中， 表示计算单元所需处理数据量， 表示每个计算任务组中每个计算单元所需处理数据量的均值；

[0016] 若所述偏斜因子大于或等于0.5，则将任务标记为慢任务；

[0017] 步骤1-4，将被标记为所述慢任务的任务放入慢任务集合；

[0018] 步骤1-5，根据所述采样数据，将所述慢任务的数据划分成均值的预设倍数个数据分区，为每个所述数据分区对应生成一个子任务，所述预设倍数的值为 。

[0019] 进一步地，在一种实现方式中，所述步骤2包括：

[0020] 步骤2-1，根据用户提交的截止期约束和公有云中虚拟机资源的执行速度以及并行计算阶段与计算任务组间的偏序关系，生成相应的拓扑序列，设使用处理速度最快公有云资源预估的时间参数，所述时间参数包括最早开始时间和最晚开始时间；

[0021] 步骤2-2，根据所述拓扑序列计算每个并行计算阶段的子截止期；

[0022] 步骤2-3，跟据所述计算任务组所在的层次 ，通过以下公式，确定每个并行计算阶段及计算任务组的子截止期：

[0023]

[0024] 其中， 为计算得到的第j个计算任务组的子截止期， 表示第j个计算任务组的最晚结束时间，为给定的Spark应用的截止期；所述计算单元的子截止期等于计算单元所在计算任务组的子截止期；

[0025] 步骤2-4，将初始并行计算阶段队列SJ的队头元素，即计算任务组队列S出队，将所述初始并行计算阶段队列SJ队头元素中的所有计算单元加入待调度的计算单元优先队列Q中；

[0026] 步骤2-5，更新所述待调度的计算单元优先队列Q，即将所有没有前驱计算任务组，或者，所述前驱计算任务组已经处理完成的计算任务组中的所有计算单元添加到待调度的计算单元优先队列Q中。

[0027] 进一步地，在一种实现方式中，在所述步骤2-4之前，还包括初始化实例的资源可用区间表和待调度的计算单元优先队列Q，公有云中的所述实例的资源可用区间表表示为已租赁的预留实例资源的每个节点的可用时间段；其中，已租赁的虚拟机资源表示为SR={SR1,SR2,…,SR }，是一个包含 个处理速度不同的虚拟机资源， ，且 为正整数；

[0028] 所述初始化实例的资源可用区间表和待调度的计算单元优先队列Q，包括：

[0029] 初始并行计算阶段队列SJ={  | i属于 1 }，其中 表示所述Spark应用程序中~的所有并行计算阶段，其中 表示并行计算阶段的数量， ，且 为正整数；

[0030] 计算任务组队列S={  | j属于1 }，其中 表示没有前驱计算任务组或前驱~计算任务组已经处理完成的计算任务组， 表示第i个并行计算阶段中计算任务组的数量，其中 ，且 为正整数；

[0031] 待调度计算单元集合T={  | i属于1 }，其中 表示当前可被调度计算单~元， 表示第i个并行计算任务阶段中第j个计算任务组的任务数量，其中 ，且为正整数。

[0032] 进一步地，在一种实现方式中，在所述步骤3之后，还包括：

[0033] 判断所述计算任务组队列S是否为空；若所述计算任务组队列S为空，则结束；若所述计算任务组队列S不为空，则执行所述步骤4的操作。

[0034] 进一步地，在一种实现方式中，所述步骤4，包括：

[0035] 步骤4-1，判断使用当前云资源的计算单元的完工时间大于计算单元的子截止期的资源是否存在，若存在，则跳转步骤4-2，若不存在，则跳转步骤4-3；

[0036] 步骤4-2，根据所述计算单元处理数据量的大小以及偏斜因子，为所述偏斜因子超过2的慢任务选择处理速度高的公有云资源，并更新所述资源可用区间表，跳转步骤4-5；

[0037] 步骤4-3，检查所述资源可用区间表，判断实际执行时间超过子截止期是否存在，若存在，则跳转步骤4-2，若不存在，则跳转步骤4-4；

[0038] 步骤4-4，为所述计算单元选择的资源的完工时间不超过其子截止期，且租赁价格最小的按需虚拟机实例；

[0039] 步骤4-5，从所述待调度的计算单元优先队列Q中删除这一计算单元，若所述任务为计算单元所在计算任务组中的最后一个任务，则更新所述计算任务组的完工时间，并删除所述计算任务组队列S中的这一计算任务组。

[0040] 进一步地，在一种实现方式中，在所述步骤4之后，还包括：

[0041] 判断所述计算任务组是否为所在并行计算阶段中的最后一个计算任务组；若是，则更新所述计算任务组所在并行计算阶段的完工时间；若不是，则判断所述待调度的计算单元优先队列Q是否为空；若所述待调度的计算单元优先队列Q不为空，则执行所述步骤4的操作；若所述待调度的计算单元优先队列Q为空，则判断计算任务组队列S是否为空；

[0042] 若所述计算任务组队列S为空，则结束；若所述计算任务组队列S不为空，则执行所述步骤4的操作。

[0043] 由以上技术方案可知，本发明实施例提供一种最小化租赁成本的公有云服务租赁方法，包括：步骤1，获取Spark应用程序的采样数据，并标记所述采样数据中可能出现数据倾斜的任务为慢任务，将所述慢任务划分成多个子任务；步骤2，根据所述Spark应用程序的截止期，基于关键路径长度的截止期划分方法，确定所述Spark应用程序中每个并行计算阶段和计算任务组的子截止期，所述计算任务组包括多个计算单元；步骤3，根据就绪的所述计算任务组确定待调度的计算单元优先队列Q，所述待调度的计算单元优先队列Q中计算单元的优先级根据每个计算单元的数据量大小按照降序排列；步骤4，将所述待调度的计算单元优先队列Q的队头出队作为调度任务，将所述调度任务调度到公有云的资源上进行处理；调度任务时，在满足每个任务子截止期的前提下，将任务调度到租赁价格代价较小的按需资源上。

[0044] 现有技术中，大多基于Hadoop平台的并行计算框架中数据倾斜问题的解决方法无法直接应用到解决Spark平台中的数据倾斜问题，且现有基于Spark平台数据倾斜问题的研究存在着顾此失彼的现象。而采用前述方法，从云服务代理商的角度出发，在满足用户应用截止期的情况下，同时考虑数据倾斜问题，采用按需实例的方式，动态按需租赁合适的虚拟机以保证应用在截止期内完成，达到了最小化云服务代理商的租赁成本的效果。因此相对于现有技术，本发明考虑了现有技术中没有考虑到的数据倾斜问题，并且在截止期约束下为云服务代理商提供了Spark应用在公有云环境中的合理租赁方法优化了租赁成本。

附图说明

[0045] 为了更清楚地说明本发明的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而言，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0046] 图1是本发明实施例部分提供的一种最小化租赁成本的公有云服务租赁方法的任务调度的工作流程示意图。

具体实施方式

[0047] 为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

[0048] 本发明实施例公开一种最小化租赁成本的公有云服务租赁方法，本方法应用于使用公有云搭建的Spark集群处理具有数据倾斜特性的任务的场景，包括云服务代理商、云服务提供者和待调度的应用。本实施例中假定云服务提供商提供三种处理速度不同的虚拟机资源：处理速度最快的虚拟机（large）、处理速度中等的虚拟机（medium）和处理速度最慢的虚拟机（small），并且假定云服务代理商采用按需租赁方式，都有其可用区间表。

[0049] 本实施例提供一种最小化租赁成本的公有云服务租赁方法，包括：

[0050] 步骤1，获取Spark应用程序的采样数据，并标记所述采样数据中可能出现数据倾斜的任务为慢任务，将所述慢任务划分成多个子任务；

[0051] 步骤2，根据所述Spark应用程序的截止期，基于关键路径长度的截止期划分方法，确定所述Spark应用程序中每个并行计算阶段和计算任务组的子截止期，所述计算任务组包括多个计算单元；

[0052] 步骤3，根据就绪的所述计算任务组确定待调度的计算单元优先队列Q，所述待调度的计算单元优先队列Q中计算单元的优先级根据每个计算单元的数据量大小按照降序排列；

[0053] 步骤4，将所述待调度的计算单元优先队列Q的队头出队作为调度任务，将所述调度任务调度到公有云的资源上进行处理；调度所述调度任务时，在满足每个所述调度任务子截止期的前提下，将所述调度任务调度到租赁价格代价较小的按需资源上。

[0054] 本实施例所述的一种最小化租赁成本的公有云服务租赁方法中，所述步骤1包括：

[0055] 步骤1-1，采用蓄水池算法对用户提交的每个所述Spark应用程序进行采样，将每个计算任务组作为一个蓄水池，采样部分计算单元作为采样数据，计算所有样本所需处理数据量的均值，即获得每个所述计算任务组中计算单元所需处理数据量的均值；本实施例中，所述采样部分计算单元可选采样三分之一的计算单元。

[0056] 步骤1-2，根据所述蓄水池算法的抽样比例，建立分布直方图；本实施例中，通过所述分布直方图能够观察数据分布的总体特征；

[0057] 步骤1-3，根据 ，获得所述计算单元的偏斜因子：

[0058] 其中， 表示计算单元所需处理数据量， 表示每个计算任务组中计算单元所需处理数据量的均值；

[0059] 若所述偏斜因子大于或等于0.5，则将任务标记为慢任务；通过本步骤，即所述标记采样数据中可能出现数据倾斜的任务为慢任务；

[0060] 步骤1-4，将被标记为所述慢任务的任务放入慢任务集合；

[0061] 步骤1-5，根据所述采样数据，将所述慢任务的数据划分成均值的预设倍数个数据分区，为每个所述数据分区对应生成一个子任务，所述预设倍数的值为 。

[0062] 本实施例所述的一种最小化租赁成本的公有云服务租赁方法中，所述步骤2包括：

[0063] 步骤2-1，根据用户提交的截止期约束和公有云中虚拟机资源的执行速度以及并行计算阶段与计算任务组间的偏序关系，生成相应的拓扑序列，设使用处理速度最快公有云资源预估的时间参数，所述时间参数包括最早开始时间和最晚开始时间；

[0064] 步骤2-2，根据所述拓扑序列计算每个并行计算阶段的子截止期；

[0065] 步骤2-3，跟据所述计算任务组所在的层次 ，通过以下公式，确定每个并行计算阶段及计算任务组的子截止期：

[0066]

[0067] 其中， 为计算得到的第j个计算任务组的子截止期， 表示第j个计算任务组的最晚结束时间，为给定的Spark应用的截止期；所述计算单元的子截止期等于计算单元所在计算任务组的子截止期；

[0068] 步骤2-4，将初始并行计算阶段队列SJ的队头元素，即计算任务组队列S出队，将所述初始并行计算阶段队列SJ队头元素中的所有计算单元加入待调度的计算单元优先队列Q中；

[0069] 步骤2-5，更新所述待调度的计算单元优先队列Q，即将所有没有前驱计算任务组，或者，所述前驱计算任务组已经处理完成的计算任务组中的所有计算单元添加到待调度的计算单元优先队列Q中。

[0070] 本实施例所述的一种最小化租赁成本的公有云服务租赁方法中，在所述步骤2-4之前，还包括初始化实例的资源可用区间表和待调度的计算单元优先队列Q，公有云中的所述实例的资源可用区间表表示为已租赁的预留实例资源的每个节点的可用时间段；其中，已租赁的虚拟机资源表示为SR={SR1,SR2,…,SR }，是一个包含 个处理速度不同的虚拟机资源， ，且 为正整数；

[0071] 所述初始化实例的资源可用区间表和待调度的计算单元优先队列Q，包括：

[0072] 初始并行计算阶段队列SJ={  | i属于 1 }，其中 表示所述Spark应用程序中~的所有并行计算阶段，其中 表示并行计算阶段的数量， ，且 为正整数；

[0073] 计算任务组队列S={  | j属于1 }，其中 表示没有前驱计算任务组或前驱~计算任务组已经处理完成的计算任务组， 表示第i个并行计算阶段中计算任务组的数量，其中 ，且 为正整数；

[0074] 待调度计算单元集合T={  | i属于1 }，其中 表示当前可被调度计算单~元， 表示第i个并行计算任务阶段中第j个计算任务组的任务数量，其中 ，且为正整数。

[0075] 本实施例所述的一种最小化租赁成本的公有云服务租赁方法中，在所述步骤3之后，还包括：

[0076] 判断所述计算任务组队列S是否为空；若所述计算任务组队列S为空，则结束；若所述计算任务组队列S不为空，则执行所述步骤4的操作。

[0077] 本实施例所述的一种最小化租赁成本的公有云服务租赁方法中，所述步骤4，包括：

[0078] 步骤4-1，判断使用当前云资源的计算单元的完工时间大于计算单元的子截止期的资源是否存在，若存在，则跳转步骤4-2，若不存在，则跳转步骤4-3；

[0079] 步骤4-2，根据所述计算单元处理数据量的大小以及偏斜因子，为所述偏斜因子超过2的慢任务选择处理速度高的公有云资源，并更新所述资源可用区间表，跳转步骤4-5；

[0080] 步骤4-3，检查所述资源可用区间表，判断实际执行时间超过子截止期是否存在，若存在，则跳转步骤4-2，若不存在，则跳转步骤4-4；

[0081] 步骤4-4，为所述计算单元选择的资源的完工时间不超过其子截止期，且租赁价格最小的按需虚拟机实例；

[0082] 步骤4-5，从所述待调度的计算单元优先队列Q中删除这一计算单元，若所述任务为计算单元所在计算任务组中的最后一个任务，则更新所述计算任务组的完工时间，并删除所述计算任务组队列S中的这一计算任务组。

[0083] 本实施例所述的一种最小化租赁成本的公有云服务租赁方法中，在所述步骤4之后，还包括：

[0084] 判断所述计算任务组是否为所在并行计算阶段中的最后一个计算任务组；若是，则更新所述计算任务组所在并行计算阶段的完工时间；若不是，则判断所述待调度的计算单元优先队列Q是否为空；若所述待调度的计算单元优先队列Q不为空，则执行所述步骤4的操作；若所述待调度的计算单元优先队列Q为空，则判断计算任务组队列S是否为空；

[0085] 若所述计算任务组队列S为空，则结束；若所述计算任务组队列S不为空，则执行所述步骤4的操作。

[0086] 本发明实施例公开了一种最小化租赁成本的公有云服务租赁方法，利用按需租赁方式从云服务代理商的角度出发，提供了一种虚拟资源实时动态调度方法，使得能够满足用户截止期约束的需求，同时考虑了数据倾斜问题，能够最小化公有云资源的租赁成本，有效地降低了云服务代理商的运营成本。根据Spark应用程序从提交到完成的流程，其处理过程大致分为数据预处理、设置任务的虚拟截止时间和任务调度这三个部分。数据预处理是考虑可能发生的数据倾斜现象，利用采样的方法来对数据进行预处理，缓解数据倾斜。设置任务的虚拟截止时间，是为了方便在任务调度的时候，能够在截止期约束下，选择合适虚拟机资源。与现有技术相比，本发明考虑了现有技术中没有考虑到的数据倾斜问题，并且在截止期约束下为云服务代理商提供了Spark应用在公有云环境中的合理租赁方法优化了租赁成本。

[0087] 具体的，本实施例中，如图1所示，Spark应用程序的具体调度步骤如下：

[0088] 步骤s201，采用蓄水池算法，对用户提交的每个Spark应用程序进行采样，将每个计算任务组（Stage）作为一个蓄水池，采样蓄水池大小三分之一的计算单元（Task），将计算单元作为采样数据，计算得到所需处理数据量的均值；

[0089] 步骤s202，根据公式 计算Task的偏斜因子，将偏斜因子大于或等于0.5的任务标记为慢任务；本实施例中，所述步骤s201和步骤s202即步骤1。

[0090] 步骤s203，将慢任务放入慢任务集合Slow中；

[0091] 步骤s204，根据所述采样数据，将慢任务的数据划分成均值的倍数 个分区，为每个数据分区对应生成一个子任务；

[0092] 步骤s205，初始化任务的参数：最早开始时间EST，最晚开始时间LFT，最早结束时间EST，最晚结束时间LFT，并计算Stage的子截止期；

[0093] 步骤s206，判断Stage队列S是否为空，若为空，则表示调度结束，若不为空，跳转步骤s207；

[0094] 步骤s207，先将初始并行计算阶段队列的队头元素，即Stage队列S出队得到队头元素，再将Stage中包含的所有Task加入待调度Task优先队列Q中；

[0095] 步骤s208，判断使用当前云资源的Task的完工时间大于其子截止期是否存在，若存在，则跳转步骤s210，否则，则跳转步骤s209；

[0096] 步骤s209，检查资源可用区间表，使用当前可用的虚拟机来处理该Task，从而计算得到Task的实际完工时间，再判断实际完工时间是否超过子截止期，若超过，则跳转步骤s211，若不超过，则跳转步骤s210；

[0097] 步骤s210，为任务按照策略选择合适的公有云资源，并更新资源可用区间表，转步骤s211；

[0098] 步骤s211，为任务选择可满足任务子截止期，且租赁价格最小，即处理速度最慢的按需虚拟机实例；

[0099] 步骤s212，从待调度Task优先队列Q中删除该Task；

[0100] 步骤s213，判断该任务是否为其所在Stage中的最后一个任务，若是，则跳转步骤s214，若不是，跳转步骤s217；

[0101] 步骤s214，更新该Stage的完工时间；

[0102] 步骤s215，判断该Stage是否为其所在并行计算阶段（Job）中的最后一个Stage，若是，则转步骤s216，若不是，则跳转步骤s217；

[0103] 步骤s216，更新该Stage所属的Job的完工时间；

[0104] 步骤s217，判断待调度Task优先队列Q是否为空，若不为空，则跳转步骤s208，若为空，则跳转步骤s206。

[0105] 由以上技术方案可知，本发明实施例提供一种最小化租赁成本的公有云服务租赁方法，包括：步骤1，获取Spark应用程序的采样数据，并标记所述采样数据中可能出现数据倾斜的任务为慢任务，将所述慢任务划分成多个子任务；步骤2，根据所述Spark应用程序的截止期，基于关键路径长度的截止期的截止期划分方法，确定所述Spark应用程序中每个并行计算阶段和计算任务组的子截止期，所述计算任务组包括多个计算单元；步骤3，根据就绪的计算任务组确定待调度的计算单元优先队列Q，所述待调度的计算单元优先队列Q中计算单元的优先级根据每个计算单元的数据量大小按照降序排列；步骤4，将所述待调度的计算单元优先队列Q的队头出队作为调度任务，将所述调度任务调度到公有云的资源上进行处理；调度任务时，在满足每个任务子截止期的前提下，将任务调度到租赁价格代价较小的按需资源上。

[0106] 现有技术中，大多基于Hadoop平台的并行计算框架中数据倾斜问题的解决方法无法直接应用到解决Spark平台中的数据倾斜问题，且现有基于Spark平台数据倾斜问题的研究存在着顾此失彼的现象。而采用前述方法，从云服务代理商的角度出发，在满足用户应用截止期的情况下，同时考虑数据倾斜问题，采用按需实例的方式，动态按需租赁合适的虚拟机以保证应用在截止期内完成，达到了最小化云服务代理商的租赁成本的效果。因此相对于现有技术，本发明考虑了现有技术中没有考虑到的数据倾斜问题，并且在截止期约束下为云服务代理商提供了Spark应用在公有云环境中的合理租赁方法优化了租赁成本。

[0107] 具体实现中，本发明还提供一种计算机存储介质，其中，该计算机存储介质可存储有程序，该程序执行时可包括本发明提供的一种最小化租赁成本的公有云服务租赁方法的各实施例中的部分或全部步骤。所述的存储介质可为磁碟、光盘、只读存储记忆体（read-only memory，ROM）或随机存储记忆体（random access memory，RAM）等。

[0108] 本领域的技术人员可以清楚地了解到本发明实施例中的技术可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明实施例中的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等）执行本发明各个实施例或者实施例的某些部分所述的方法。

[0109] 本说明书中各个实施例之间相同相似的部分互相参见即可。以上所述的本发明实施方式并不构成对本发明保护范围的限定。