基于SLA最小化跨站点数据分析成本的方法及装置

IPRDB

API 数据接口

专利申请

使用指引 chat嘟嘟

会员体验

联系我们

交流群

现在联系顾问~

基于SLA最小化跨站点数据分析成本的方法及装置
申请号	CN202011220199.0	申请日	2020-11-05	公开(公告)号	CN112039714A	公开(公告)日	2020-12-04
申请人	中国人民解放军国防科技大学;			发明人	郭得科; 罗来龙; 陈亦婷; 廖汉龙;
摘要	本说明书一个或多个实施例提供一种基于SLA最小化跨站点数据分析成本的方法及装置，包括确定按照最小化作业完成时间策略执行数据处理作业时的第一作业完成时间；若第一作业完成时间小于等于设定的截止时间，确定按照最小化作业成本策略执行数据处理作业时的第二作业完成时间；若第二作业完成时间小于等于截止时间，则选取最小化作业成本策略执行数据处理作业，若第二作业完成时间大于截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以尽量低的作业成本执行数据处理作业。本说明书的方法能够实现数据处理作业的完成时间和成本达到均衡，解决跨站点数据处理的作业效率问题。
权利要求	1.一种基于SLA最小化跨站点数据分析成本的方法，其特征在于，包括：确定按照最小化作业完成时间策略执行数据处理作业的第一作业完成时间；若第一作业完成时间小于等于设定的截止时间，确定按照最小化作业成本策略执行数据处理作业的第二作业完成时间；若第二作业完成时间小于等于截止时间，则选取最小化作业成本策略执行数据处理作业，若第二作业完成时间大于截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业。 2.根据权利要求1所述的方法，其特征在于，所述调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，包括：将所述最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间。 3.根据权利要求2所述的方法，其特征在于，将所述最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间，包括：若最小化作业成本策略下，从站点r到站点d的map阶段的传输数据量为，站点d执行reduce任务的比例为，最小化作业完成时间策略下，从站点r到站点d的map阶段的传输数据量为，站点d执行reduce任务的比例，所述步长为，则，当时，调整中间变量为，当时，调整中间变量为；当时，调整中间变量为，当时，调整中间变量为；按照调整后的中间变量，获得相应的作业完成时间，当小于所述截止时间时，此时对应的中间变量为确定出的map阶段的传输数据量，为确定出的执行reduce任务的比例。 4.根据权利要求1所述的方法，其特征在于，还包括：对于每个站点，按照所述最小化作业完成时间策略执行具有多个阶段的数据处理作业的第三作业完成时间；若所述第三作业完成时间小于等于所述截止时间，确定按照所述最小化作业成本策略执行所述具有多个阶段的数据处理作业的第四作业完成时间；若所述第四作业完成时间大于所述截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，得到调整后的第五作业完成时间；按照上述过程对每个站点进行处理之后，从小于截止时间的第四作业完成时间和所述第五作业完成时间中选取出最小的完成时间，确定所述最小的完成时间所对应的站点，利用该站点执行所述具有多个阶段的数据处理作业。 5.根据权利要求1所述的方法，其特征在于，所述最小化作业成本策略包括map阶段的任务放置策略和reduce阶段的任务放置策略；所述map阶段的任务放置策略的线性规划模型为：（15）（16）（17）所述reduce阶段的任务放置策略的模型为：（18）（19）（20）其中，、、、分别表示数据聚合过程，map计算过程，shuffle过程和reduce 计算过程四个过程的成本，为站点d执行reduce任务的比例，为从站点r到站点d的map阶段的传输数据量，为map阶段的输入数据，为站点r中的数据量。 6.根据权利要求5所述的方法，其特征在于，所述最小化作业完成时间策略包括map阶段的任务放置策略和reduce阶段的任务放置策略；所述map阶段的任务放置策略的线性规划模型为：（21）（22）（23）（24）（25）（26）所述reduce阶段的任务放置策略为: （27）（28）（29）（30）其中，分别表示数据聚合过程，map计算过程，shuffle过程和reduce计算过程四个过程的计算时间，，分别是站点r的上传带宽和下载带宽，，分别是站点d的上传带宽和下载带宽，，分别是站点d上的map阶段和reduce阶段的计算资源的数量，是站点d的计算资源数量，为站点d上的中间数据量，分别是执行map阶段和reduce阶段的计算时间。 7.根据权利要求6所述的方法，其特征在于，构建的任务放置问题为：（1）（2）（3）（4）（5）。 8.一种基于SLA最小化跨站点数据分析成本的装置，其特征在于，包括：第一处理模块，用于确定按照最小化作业完成时间策略执行数据处理作业的第一作业完成时间；第二处理模块，用于判断所述第一作业完成时间小于等于设定的截止时间时，确定按照最小化作业成本策略执行数据处理作业的第二作业完成时间；第三处理模块，用于判断所述第二作业完成时间小于等于所述截止时间时，选取最小化作业成本策略执行数据处理作业，判断所述第二作业完成时间大于所述截止时间时，调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业。 9.根据权利要求8所述的装置，其特征在于，所述第三处理模块，用于将所述最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间。 10.根据权利要求8所述的装置，其特征在于，还包括：第四处理模块，用于对于每个站点，按照所述最小化作业完成时间策略执行具有多个阶段的数据处理作业的第三作业完成时间；若所述第三作业完成时间小于等于所述截止时间，确定按照所述最小化作业成本策略执行所述具有多个阶段的数据处理作业的第四作业完成时间；若所述第四作业完成时间大于所述截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，得到调整后的第五作业完成时间；按照上述过程对每个站点进行处理之后，从小于截止时间的第四作业完成时间和所述第五作业完成时间中选取出最小的完成时间，确定所述最小的完成时间所对应的站点，利用该站点执行所述具有多个阶段的数据处理作业。
说明书全文	基于SLA最小化跨站点数据分析成本的方法及装置技术领域 [0001] 本说明书一个或多个实施例涉及数据处理技术领域，尤其涉及一种基于SLA最小化跨站点数据分析成本的方法及装置。背景技术 [0002] 目前，许多数据提供商在不同地区部署了大量站点用于支持各种分布式数据应用。对跨地区跨站点分布的数据进行收集分析处理有利于制定更优的部署策略，从而节约资源；然而，跨区域的各站点存在容量、带宽、价格等资源方面的异构性，各站点同时执行大量数据处理会造成严重的地理分布资源销耗，且会出现很高的时延。如何在跨站点同时执行数据处理作业时，实现作业时间和成本的均衡，提高作业效率，维持合理成本，是本领域技术人员致力于解决的技术问题。发明内容 [0003] 有鉴于此，本说明书一个或多个实施例的目的在于提出一种基于SLA最小化跨站点数据分析成本的方法及装置，以解决跨站点数据处理的作业效率和成本问题。 [0004] 基于上述目的，本说明书一个或多个实施例提供了一种基于SLA最小化跨站点数据分析成本的方法，包括：确定按照最小化作业完成时间策略执行数据处理作业的第一作业完成时间；若第一作业完成时间小于等于设定的截止时间，确定按照最小化作业成本策略执行数据处理作业的第二作业完成时间；若第二作业完成时间小于等于截止时间，则选取最小化作业成本策略执行数据处理作业，若第二作业完成时间大于截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业。 [0005] 可选的，所述调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，包括：将所述最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间。 [0006] 可选的，将所述最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间，包括：若最小化作业成本策略下，从站点r到站点d的map阶段的传输数据量为，站点 d执行reduce任务的比例为，最小化作业完成时间策略下，从站点r到站点d的map阶段的传输数据量为，站点d执行reduce任务的比例，所述步长为，则，当时，调整中间变量为，当时，调整中间变量为；当时，调整中间变量为，当时，调整中间变量为；按照调整后的中间变量、，获得相应的作业完成时间，当小于所述截止时间时，此时对应的中间变量为确定出的map阶段的传输数据量，为确定出的执行reduce任务的比例。 [0007] 可选的，所述方法还包括：对于每个站点，按照所述最小化作业完成时间策略执行具有多个阶段的数据处理作业的第三作业完成时间；若所述第三作业完成时间小于等于所述截止时间，确定按照所述最小化作业成本策略执行所述具有多个阶段的数据处理作业的第四作业完成时间；若所述第四作业完成时间大于所述截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，得到调整后的第五作业完成时间；按照上述过程对每个站点进行处理之后，从小于截止时间的第四作业完成时间和所述第五作业完成时间中选取出最小的完成时间，确定所述最小的完成时间所对应的站点，利用该站点执行所述具有多个阶段的数据处理作业。 [0008] 可选的，所述最小化作业成本策略包括map阶段的任务放置策略和reduce阶段的任务放置策略；所述map阶段的任务放置策略的线性规划模型为：（15）（16）（17）所述reduce阶段的任务放置策略的模型为：（18）（19）（20）其中，、、、分别表示数据聚合过程，map计算过程， shuffle过程和reduce 计算过程四个过程的成本，为站点d执行reduce任务的比例，为从站点r到站点d的map阶段的传输数据量，为map阶段的输入数据，为站点r中的数据量。 [0009] 可选的，所述最小化作业完成时间策略包括map阶段的任务放置策略和reduce阶段的任务放置策略；所述map阶段的任务放置策略的线性规划模型为：（21）（22）（23）（24）（25）（26）所述reduce阶段的任务放置策略为: （27）（28）（29）（30）其中，分别表示数据聚合过程，map计算过程，shuffle 过程和reduce计算过程四个过程的计算时间，，分别是站点r的上传带宽和下载带宽，，分别是站点d的上传带宽和下载带宽，，分别是站点d上的map阶段和reduce阶段的计算资源的数量，是站点d的计算资源数量，为站点d上的中间数据量，分别是执行map阶段和reduce阶段的计算时间。 [0010] 可选的，构建的任务放置问题为：（1）（2）（3）（4）（5）。 [0011] 本说明书实施例还提供一种基于SLA最小化跨站点数据分析成本的装置，包括：第一处理模块，用于确定按照最小化作业完成时间策略执行数据处理作业的第一作业完成时间；第二处理模块，用于判断所述第一作业完成时间小于等于设定的截止时间时，确定按照最小化作业成本策略执行数据处理作业的第二作业完成时间；第三处理模块，用于判断所述第二作业完成时间小于等于所述截止时间时，选取最小化作业成本策略执行数据处理作业，判断所述第二作业完成时间大于所述截止时间时，调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业。 [0012] 可选的，所述第三处理模块，用于将所述最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间。 [0013] 可选的，所述装置还包括：第四处理模块，用于对于每个站点，按照所述最小化作业完成时间策略执行具有多个阶段的数据处理作业的第三作业完成时间；若所述第三作业完成时间小于等于所述截止时间，确定按照所述最小化作业成本策略执行所述具有多个阶段的数据处理作业的第四作业完成时间；若所述第四作业完成时间大于所述截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，得到调整后的第五作业完成时间；按照上述过程对每个站点进行处理之后，从小于截止时间的第四作业完成时间和所述第五作业完成时间中选取出最小的完成时间，确定所述最小的完成时间所对应的站点，利用该站点执行所述具有多个阶段的数据处理作业。 [0014] 从上面所述可以看出，本说明书一个或多个实施例提供的基于SLA最小化跨站点数据分析成本的方法及装置，通过确定按照最小化作业完成时间策略执行数据处理作业时的第一作业完成时间；若第一作业完成时间小于等于设定的截止时间，确定按照最小化作业成本策略执行数据处理作业时的第二作业完成时间；若第二作业完成时间小于等于截止时间，则选取最小化作业成本策略执行数据处理作业，若第二作业完成时间大于截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以尽量低的作业成本执行数据处理作业。本说明书能够实现数据处理作业的完成时间和成本达到均衡，解决跨站点数据处理的作业效率问题。附图说明 [0015] 为了更清楚地说明本说明书一个或多个实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本说明书一个或多个实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。 [0016] 图1为本说明书一个或多个实施例的方法流程示意图；图2为本说明书一个或多个实施例的算法流程示意图；图3为本说明书另一个实施例的算法流程示意图；图4为本说明书一个或多个实施例的四种方法的平均作业完成成本的对比示意图；图5为本说明书一个或多个实施例的四种方法的平均作业完成时间的对比示意图；图6为本说明书一个或多个实施例的四种方法的平均运行时间的对比示意图；图7为本说明书一个或多个实施例的不同截止时间的平均作业完成成本与作业完成时间示意图；图8为本说明书一个或多个实施例的不同截止时间的传输成本和计算成本在总成本中的占比示意图；图9为本说明书一个或多个实施例的不同截止时间的传输时间和计算时间在总时间中的占比示意图；图10为本说明书一个或多个实施例的不同站点规模下的平均作业完成成本的示意图；图11为本说明书一个或多个实施例的不同站点规模下的平均作业完成时间的示意图；图12为本说明书一个或多个实施例的利用四种方法处理多阶段作业的平均作业完成成本的示意图；图13为本说明书一个或多个实施例的利用四种方法处理多阶段作业的平均作业完成时间的示意图；图14为本说明书一个或多个实施例的装置结构示意图；图15为本说明书一个或多个实施例的电子设备的结构示意图。具体实施方式 [0017] 为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本公开进一步详细说明。 [0018] 需要说明的是，除非另外定义，本说明书一个或多个实施例使用的技术术语或者科学术语应当为本公开所属领域内具有一般技能的人士所理解的通常意义。本说明书一个或多个实施例中使用的“第一”、“第二”以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的组成部分。“包括”或者“包含”等类似的词语意指出现该词前面的元件或者物件涵盖出现在该词后面列举的元件或者物件及其等同，而不排除其他元件或者物件。“连接”或者“相连”等类似的词语并非限定于物理的或者机械的连接，而是可以包括电性的连接，不管是直接的还是间接的。“上”、“下”、“左”、“右”等仅用于表示相对位置关系，当被描述对象的绝对位置改变后，则该相对位置关系也可能相应地改变。 [0019] 一些方式中，在跨区域跨站点的数据处理工作中，各站点通过广域网相连接，这些站点在存储容量、计算资源、网络带宽、价格等方面存在高度异构的特点，如表1所示，不同地区的计算资源、网络带宽、存储资源均不同。 [0020] 表1 不同地区的资源价格在跨地区跨站点的数据处理工作中，一种方法是，考虑工作的完成时间，使用有效的任务放置策略来最小化作业完成时间，这种方案往往会选取计算资源和网络资源丰富的站点进行数据处理工作，成本较高；另一种方法是，考虑到工作成本，使用有效的任务放置策略来最小化作业成本，然而这种方案往往需要耗费大量的时间，有可能会超出工作要求的截止时间；在实际的数据处理工作中，作业完成时间和成本都是非常重要的，期望找到一种既能够在要求的截止时间之内完成数据处理作业，同时能够最大化的降低成本的任务放置策略。 [0021] 如图1、2所示，本说明书一个或多个实施例提供一种基于SLA最小化跨站点数据分析成本的方法，包括：S101：确定按照最小化作业完成时间策略执行数据处理作业的第一作业完成时间； S102：若第一作业完成时间小于等于设定的截止时间，确定按照最小化作业成本策略执行数据处理作业的第二作业完成时间；本实施例中，首先按照最小化作业完成时间策略执行数据处理作业，得到利用该策略完成作业的第一作业完成时间。如果第一作业完成时间大于作业完成的截止时间，判断数据处理作业无法在截止时间之内完成，即该数据处理作业无法完成；如果第一作业完成时间小于等于截止时间，判断数据处理作业可以在截止时间之内完成，进一步按照最小化作业成本策略执行数据处理作业，得到利用该策略完成作业的第二作业完成时间，由于最小化作业成本策略是以成本最低为目标，作业完成时间有可能会超出截止时间。 [0022] S103：若第二作业完成时间小于等于截止时间，则选取最小化作业成本策略执行数据处理作业，若第二作业完成时间大于截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业。 [0023] 本实施例中，当判断第二作业时间小于等于截止时间时，确定最小化作业成本策略是数据处理作业的最优策略，因为既可以在截止时间内完成作业，又能保证成本最低。一些情况下，最小化作业成本策略的第二作业时间往往大于截止时间，因而，为保证在截止时间内完成作业，同时最大化的降低成本，需要调整数据处理作业的任务放置策略，使得数据处理作业能够在作业完成时间和所需成本之间达到均衡。 [0024] 以下结合具体实施例对本说明书的数据处理方法进行详细的说明。 [0025] 在大数据处理过程中，数据处理作业可以包含多个map-reduce阶段，其中，map阶段用于数据过滤分发，reduce阶段用于数据计算归并，reduce阶段的数据来源于map阶段的输出数据，从map阶段的输出数据到reduce阶段的输入数据称为shuffle阶段。将map阶段划分为数据聚合过程和map计算过程两部分，将reduce阶段划分为shuffle过程和reduce计算过程两部分。 [0026] map阶段的输入数据分布于不同区域的多个站点上，表示为，表示站点r中的数据量。表示在map阶段从站点r传输到站点 d 的数据量。表示在站点d 中执行的reduce任务的比例，设分别表示数据聚合过程，map计算过程，shuffle过程和reduce 计算过程四个过程的成本。分别表示数据聚合过程，map计算过程，shuffle过程和 reduce计算过程四个过程的计算时间；设完成数据处理作业的截止时间是，构建如下任务放置问题P1：（1）（2）（3）（4）（5）上述任务放置问题P1的目标是最小化数据处理作业成本，整个数据处理作业在截止时间T内完成（式（2）），同时确保传输至站点d的总数据量等于站点r的总数据量（式（3））。在问题P1中，map阶段的任务放置会影响reduce阶段的任务放置，因此，问题P1是一个二次约束的二次规划问题（QCQP问题），该问题通常为NP-hard问题，很难获得最优解。 [0027] 对于数据聚合过程，map计算过程，shuffle过程和reduce 计算过程四个阶段的成本，，，计算方法为：（6）其中，为从站点r到站点 d传输每单位数据的价格。 [0028] （7）（8）其中，为站点d上的中间数据量，中间数据由map阶段生成并作为reduce阶段的输入数据，q表示中间数据量与输入数据量的比例。是在站点r中执行reduce任务的比例。（9）（10）其中，站点d上的map阶段和reduce阶段的计算资源的数量分别是，，为站点d上单位时间内一个计算资源的价格，分别为执行map阶段和 reduce阶段的计算时间。 [0029] 对于数据聚合过程、map计算过程，shuffle过程和reduce计算过程四个过程的时间，计算方法为：从站点d传出的数据量是，站点d需下载的数据量是。假设，表示站点d的上传带宽和下载带宽，因此，站点d的上传时间和下载时间分别是和。在reduce阶段，从站点d传出的数据量是，站点d的传入数据量是，为站点r上的中间数据量，在reduce阶段的上传时间和下载时间分别是、；由于传输的完成时间是由最晚完成数据传输的时间决定的，从而得到：（11）（12）每个阶段的任务经常会采用多波的方式完成。假设站点d有个计算资源，在map阶段和reduce阶段分别需要和次来完成map任务和reduce任务，用和分别表示完成一个map任务和一个reduce任务所需时间。因此，站点d上map任务和reduce任务的计算时间分别是：、。使用和分别表示map阶段和reduce阶段的计算时间，同样是由最晚完成map任务和reduce任务的时间所决定的；可以得到：（13）（14）在不考虑时间约束条件下，问题P1是一个QP（Quadratic programmin）问题，二次项的系数矩阵是非正定的，QP问题通常是NP-hard问题，然而，广域网中的数据处理作业不能保证系数矩阵一定是正定的。为了确定最小化作业成本策略，分别确定map阶段和reduce阶段的任务放置策略。具体的： map阶段的最小化作业成本任务放置策略构建为如下的线性规划模型：（15）（16）（17）其中，该模型的目标为最小化map阶段的成本（式15），式16包含了n个等式约束，n是站点的数量，每个约束代表站点d上剩余的总的数据量和传输至其他站点的数据量等于站点d的总数据量。 [0030] 由于每个reduce任务需要从所有的map任务的输出数据获得输入数据，因此，应确定reduce任务在每个站点上执行的比例。reduce阶段的最小化作业成本任务放置策略构建为如下模型：（18）（19）（20）该模型的目标是最小化reduce阶段的成本（式18），决策变量是站点d上执行 reduce任务的比例，式20表示所有站点必须完成分配的所有任务。 [0031] 按照公式（15）-（17）以及（18）-（20）所示模型执行任务放置策略，能够得到最小化作业成本策略下的完成数据处理作业的总成本、总时间，站点d上执行reduce任务的比例、在map阶段从站点r传输到站点 d 的数据量。 [0032] 在不考虑成本约束条件下，希望尽快完成数据处理作业。不同的跨区域数据处理作业有不同的SLA（Service Level Agreement，服务级别协议）约束，有些数据处理作业属于时间敏感型的作业（例如流数据处理作业），有些数据处理作业只需要在规定的最后期限前完成即可（例如批处理作业）。为了确定最小化作业完成时间策略，分别确定map阶段和reduce阶段的任务放置策略。具体的：map阶段的最小化作业完成时间任务放置策略构建为如下的线性规划模型：（21）（22）（23）（24）（25）（26）该模型的目标是最小化数据聚集过程的计算时间和map计算过程的计算时间，约束条件为数据聚集过程的计算时间取决于最晚完成数据传输的时间（式22、23），map计算过程的计算时间取决于最后一个map任务的完成时间，该模型的输出结果为从站点r传输至站点d的数据量。，分别是站点r的上传带宽和下载带宽。 [0033] 完成map阶段后，站点d上的中间数据量为。reduce阶段的最小化作业完成时间任务放置策略构建为: （27）（28）（29）（30）（31）按照公式（21）-（26）以及（27）-（31）所示模型执行任务放置策略，能够得到最小化作业完成时间策略下的的完成数据处理作业的总成本、总时间、在map阶段从站点 r传输到站点 d 的数据量、站点d上执行reduce任务的比例。 [0034] 本实施例的跨站点分布式数据处理方法，首先按照最小化作业完成时间策略确定采用该策略执行数据处理作业所需的第一作业完成时间，判断第一作业完成时间是否小于截止时间，若否则认为数据处理作业无法在截止时间内完成；若是，进一步按照最小化作业成本策略确定采用该策略执行数据处理作业所需的第二作业完成时间，判断第二作业完成时间是否小于截止时间，若是，则认为按照最小化作业成本策略既能够在截止时间内完成作业，又可以最小化作业成本，确定采用最小化成本策略执行数据处理作业，若第二作业完成时间大于截止时间，则需调整每个站点上执行的map阶段的传输数据量和reduce任务的比例，使得能够在截止时间内完成作业的前提下，最大限度的降低作业成本。 [0035] 其中，调整每个站点上执行的map阶段的传输数据量和reduce任务的比例的方法为：将最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于截止时间。 [0036] 一些方式中，调整算法可以是：设中间变量为，，首先将变量、、赋值给、、；按照一定的步长，循环调整、，使得在当前、的条件下，作业完成时间小于截止时间。 [0037] 为了有效地获得可行解，采用了一个贪婪的策略去改变决策变量。例如：如果当前中间变量是、，调整步长是，当时，调整中间变量为在，当时，调整中间变量为；当时，调整中间变量为，当时，调整中间变量为；按照调整后的中间变量，获得相应的作业完成时间（按照公式（21）-（26）以及（27）-（31）所示模型执行任务放置策略，得到完成数据处理作业的总时间），当小于截止时间T时，此时对应的中间变量为确定出的map阶段的传输数据量，为确定出的执行reduce任务的比例。由于作业完成时间和作业成本之间有一定的反向关系，将求解方案从最优化时间的方案向最优化成本方案不断调整，从而尽可能使用少的成本，并满足时延要求。同时，本实施例的方法会返回最终的可行解。 [0038] 本实施例中，提供了map阶段和reduce阶段共两个阶段的数据处理作业的最优化的任务放置策略，能够保证在截止时间内完成作业同时保证成本最低。然而，有些数据处理作业通常包括多个独立的阶段，而不仅仅是两个阶段，通常可被抽象为一个有向无环图。另外，为了获得最终的数据处理结果，需要将所有站点的数据传输汇聚于一个主站点，跨站点的数据传输会增加作业时间和成本。 [0039] 结合图3所示，为了能够实现在截止时间内完成多阶段的数据处理作业同时保证成本最低，选取一个主站点接收map阶段和reduce阶段所生成的数据，并由该主站点基于接收的数据执行后续各个阶段的数据处理作业。具体方法是：对于每个站点，按照最小化作业完成时间策略执行具有多个阶段的数据处理作业的第三作业完成时间；若第三作业完成时间小于等于设定的截止时间，确定按照最小化作业成本策略执行具有多个阶段的数据处理作业的第四作业完成时间；若第四作业完成时间大于截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，得到调整后的第五作业完成时间；按照上述过程对每个站点进行处理之后，从小于截止时间的第四作业完成时间和调整后的第五作业完成时间中选取出最小的完成时间，确定最小的完成时间所对应的站点，将该站点作为主站点，利用主站点执行包括多个阶段的数据处理作业。这样，对于具有多个阶段的数据处理作业，能够保证在截止日期之内，利用最低的成本完成数据处理作业。 [0040] 以下结合测试数据说明本实施例的数据处理方法的效果。 [0041] 数据准备：模拟包含10个站点的跨地理位置分布的网络，每个站点都具有异构的资源和异构的资源价格。具体来说，每个广域网链路的带宽在100Mbps到2Gbps之间，价格是在0.02到0.5$/GB之间。每个站点上的计算资源的数量在100到1000之间，每个计算资源的价格在4.5 到7.5 $/每秒。默认情况下，将比例q设置为0.5，调整步长为0.1，每个任务能够处理的数据量是，一个map任务所需时间在60s到180s之间，一个reduce任务所需时间为在30s到90s之间。 [0042] 采用Google公司真实的数据集去模拟广域网数据处理作业的场景。Google集群数据收集了1.25万台机器上的机器、作业和任务的信息。机器、作业和任务的事件都由一条或者多条记录描述，每条记录通常包含时间戳、ID、事件类型、资源请求量等。 [0043] 采用阿里巴巴集团于2018年发布的数据集模拟数据处理作业场景。该数据集包含了8天内大约4k台机器的记录，该数据集包括许多类型的批处理作业，其中大多数是DAG作业，很容易得到每个作业的阶段信息，跟踪包含大约350k个作业的运行记录。 [0044] 这两个数据集都是在单个数据中心中的作业运行数据。为了模拟跨地理位置分布的大数据处理作业的运行情况，将这些机器划分为不同的站点，根据这些机器上每个作业的任务分布，可以得到每个作业在所有站点上的输入数据量。 [0045] 分别以平均作业完成时间、平均作业完成成本、平均运行时间、作业完成时间与截止时间之间的平均差异比为指标，评价本说明书提供的数据处理方法（简称MCGL方法）以及三种现有的数据处理方法，Tetrium方法（完成作业时间最少的方法）、MinCost 方法（完成作业成本最低的方法）和Centralized方法（将所有站点的数据汇聚于一个主站点，该主站点是作业完成时间最小的站点）的有效性。 [0046] 设Tetrium方法的作业完成时间为t1，MinCost 方法的作业完成时间为t2，设定截止时间T为t1+（t2−t1）×0.7。 [0047] 如图4所示，根据输入数据量的大小，将Google数据集中的数据处理作业划分为小规模作业（small）和大规模作业（large），小规模作业的平均成本非常低，大规模工作的平均成本要高得多。此外，与Tetrium方法相比，MCGL方法对任何作业的总完成成本都要少，也就是说，对于任何一个作业，MCGL方法都能保证在截止期限内完成作业，且作业完成成本是能够按时完成作业的所有方法中最低的，虽然作业完成成本高于MinCost方法，但是MinCost方法不能满足工作的最后期限。 [0048] 如图5所示，大规模作业需要处理更多的数据，站点之间传输数据的时间和计算时间都需花费更多的时间，相较之下，MCGL方法只比Tetrium方法的平均作业完成时间高，而Tetrium方法的平均成本较高。 [0049] 如图6所示，对于平均运行时间，四种方法的平均运行时间都在3毫秒以下，虽然MCGL方法的平均运行时间较长，但与其他方法差距较小，且毫秒级的平均运行时间对于实际的应用程序调度请求是有效的；而且，在实际应用中，由于可以并行运行可以进一步降低MCGL方法的运行时间。 [0050] 如图7所示，当将截止时间T（横坐标为deadline）按照时间间隔（t2−t1）×0.1，从t1+（t2−t1）×0.1调整至t1+（t2−t1）×0.9时，作用完成时间随截止时间的增加而显著缩短，这是因为，更长的截止时间可能允许MCGL方法利用更便宜的链路传输更多的数据，并在更便宜的计算资源上执行更多的任务。MCGL方法可以根据用户的需求在作业完成时间和作业成本之间进行适当的权衡。 [0051] 如图8所示，随着截止时间的增加，传输成本（transCost）所占的比例继续下降，这一现象表明，使用更廉价的链路传输更多的数据可以有效地降低总的作业完成成本。如图9所示，传输时间（tranTime）和计算时间（comTime）在作业完成时间中的比例是稳定的，随着截止时间的增加，作业的传输时间和计算时间以相同的速度增长。 [0052] 结合表2所示，将调整步长由0.001调整为0.1，对MCGL方法进行测试，测试结果表明，对于时间敏感型的作业，适于采用较大的调整步长，如果用户希望花费更少的成本，适于采用较小的调整步长。 [0053] 表2 步长与平均作业完成成本、平均作业完成时间的关系将站点数量设置为10和30进一步进行测试，每个站点间链路的带宽设置在100Mbps和 2Gbps之间，每个链路单位带宽的数据传输成本在[0.02，0.5]$/GB的范围内进行调整。不同站点的计算时隙（计算资源）从100到1000不等，每个时隙的价格在每秒4.5×10−5美元和 7.5×10−5美元之间。每项工作的截止时间为t1+（t2−t1）×0.7。 [0054] 如图10所示，增加站点的数量会导致Tetrium方法和MCGL方法的总成本增加一些，原因是Tetrium方法和MCGL方法希望缩短作业完成时间，而更多的站点意味着需要交换更多的数据，从而增加了作业完成成本。因此，跨多个站点的地理分布数据处理工作可以加快MCGL方法的完成过程，但要付出更多的代价。Central方法和Mincost方法试图最小化作业完成成本，并且可以选择更便宜的链路和计算资源来完成更多站点的作业，因此，Central方法和Mincost方法的作业完成成本随着站点的增加而降低。此外，无论涉及多少个站点，MCGL方法的作业完成成本仅高于Mincost方法的作业完成成本。如图11所示，当更多站点参与地理分布数据处理作业时，作业完成时间减少，原因是更多的站点意味着更多的数据并行传输和计算，从而加快了数据处理过程。 [0055] 利用阿里巴巴的数据集对本说明书的具有多阶段的数据处理作业的数据处理方法（称为MCGL+方法）进行测试，同样将数据集划分为小规模作业和大规模作业，每个站点间链路的带宽设置在100Mbps到2Gbps之间。每个链路单位带宽的数据传输成本在[0.02，0.5]$/GB范围内调整。不同站点的计算时隙从100到1000不等，每个时隙的价格在每秒4.5×10−5美元和7.5× 美元之间。 [0056] 对于每个站点，分别设按照最小化作业完成时间策略执行数据处理作业，确定完成时间最少的站点所需时间为t1，按照最小化作业成本策略执行数据处理作业，确定完成时间最多的站点所需时间为t2，设截止时间为t1+（t2−t1）×0.5。 [0057] 如图12、13所示，Centralized方法比MCGL+方法产生更多的作业完成成本和作业完成时间，根本原因是Centralized方法在不同站点之间传输过多的数据，所以将花费更多的时间并导致更高的传输成本。同时，在一个站点上执行整个作业也会导致较长的计算时间。MCGL+方法的平均作业完成成本和平均作业完成时间介于Tetrium方法和MinCost方法的结果之间，MCGL+方法能够在作业完成时间和作业完成成本之间取得较好的均衡。需要说明的是，本说明书一个或多个实施例的方法可以由单个设备执行，例如一台计算机或服务器等。本实施例的方法也可以应用于分布式场景下，由多台设备相互配合来完成。在这种分布式场景的情况下，这多台设备中的一台设备可以只执行本说明书一个或多个实施例的方法中的某一个或多个步骤，这多台设备相互之间会进行交互以完成所述的方法。 [0058] 上述对本说明书特定实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。 [0059] 如图14所示，本说明书实施例还提供一种SLA代价最小的跨站点分布式数据处理装置，包括：第一处理模块，用于确定按照最小化作业完成时间策略执行数据处理作业的第一作业完成时间；第二处理模块，用于判断所述第一作业完成时间小于等于设定的截止时间时，确定按照最小化作业成本策略执行数据处理作业的第二作业完成时间；第三处理模块，用于判断所述第二作业完成时间小于等于所述截止时间时，选取最小化作业成本策略执行数据处理作业，判断所述第二作业完成时间大于所述截止时间时，调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业。 [0060] 一些实施例中，第三处理模块，用于将最小化作业成本策略下的map阶段的传输数据量和reduce任务的比例按照一定的步长进行调整，使得按照调整后的map阶段的传输数据量和reduce任务的比例执行数据处理的作业完成时间小于所述截止时间。 [0061] 一些实施例中，所述装置还包括：第四处理模块，用于对于每个站点，按照所述最小化作业完成时间策略执行具有多个阶段的数据处理作业的第三作业完成时间；若所述第三作业完成时间小于等于所述截止时间，确定按照所述最小化作业成本策略执行所述具有多个阶段的数据处理作业的第四作业完成时间；若所述第四作业完成时间大于所述截止时间，则调整每个站点的数据处理作业放置，使得在截止时间内能够以最小化的作业成本执行数据处理作业，得到调整后的第五作业完成时间；按照上述过程对每个站点进行处理之后，从小于截止时间的第四作业完成时间和所述第五作业完成时间中选取出最小的完成时间，确定所述最小的完成时间所对应的站点，利用该站点执行所述具有多个阶段的数据处理作业。 [0062] 为了描述的方便，描述以上装置时以功能分为各种模块分别描述。当然，在实施本说明书一个或多个实施例时可以把各模块的功能在同一个或多个软件和/或硬件中实现。 [0063] 上述实施例的装置用于实现前述实施例中相应的方法，并且具有相应的方法实施例的有益效果，在此不再赘述。 [0064] 图15示出了本实施例所提供的一种更为具体的电子设备硬件结构示意图，该设备可以包括：处理器1010、存储器1020、输入/输出接口1030、通信接口1040和总线 1050。其中处理器1010、存储器1020、输入/输出接口1030和通信接口1040通过总线1050实现彼此之间在设备内部的通信连接。 [0065] 处理器1010可以采用通用的CPU（Central Processing Unit，中央处理器）、微处理器、应用专用集成电路（Application Specific Integrated Circuit，ASIC）、或者一个或多个集成电路等方式实现，用于执行相关程序，以实现本说明书实施例所提供的技术方案。 [0066] 存储器1020可以采用ROM（Read Only Memory，只读存储器）、RAM（Random Access Memory，随机存取存储器）、静态存储设备，动态存储设备等形式实现。存储器1020可以存储操作系统和其他应用程序，在通过软件或者固件来实现本说明书实施例所提供的技术方案时，相关的程序代码保存在存储器1020中，并由处理器1010来调用执行。 [0067] 输入/输出接口1030用于连接输入/输出模块，以实现信息输入及输出。输入输出/ 模块可以作为组件配置在设备中（图中未示出），也可以外接于设备以提供相应功能。其中输入设备可以包括键盘、鼠标、触摸屏、麦克风、各类传感器等，输出设备可以包括显示器、扬声器、振动器、指示灯等。 [0068] 通信接口1040用于连接通信模块（图中未示出），以实现本设备与其他设备的通信交互。其中通信模块可以通过有线方式（例如USB、网线等）实现通信，也可以通过无线方式（例如移动网络、WIFI、蓝牙等）实现通信。 [0069] 总线1050包括一通路，在设备的各个组件（例如处理器1010、存储器1020、输入/输出接口1030和通信接口1040）之间传输信息。 [0070] 需要说明的是，尽管上述设备仅示出了处理器1010、存储器1020、输入/输出接口1030、通信接口1040以及总线1050，但是在具体实施过程中，该设备还可以包括实现正常运行所必需的其他组件。此外，本领域的技术人员可以理解的是，上述设备中也可以仅包含实现本说明书实施例方案所必需的组件，而不必包含图中所示的全部组件。 [0071] 本实施例的计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存（PRAM）、静态随机存取存储器（SRAM）、动态随机存取存储器（DRAM）、其他类型的随机存取存储器（RAM）、只读存储器（ROM）、电可擦除可编程只读存储器（EEPROM）、快闪记忆体或其他内存技术、只读光盘只读存储器（CD-ROM）、数字多功能光盘（DVD）或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。 [0072] 所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围（包括权利要求）被限于这些例子；在本公开的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如上所述的本说明书一个或多个实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。 [0073] 另外，为简化说明和讨论，并且为了不会使本说明书一个或多个实施例难以理解，在所提供的附图中可以示出或可以不示出与集成电路（IC）芯片和其它部件的公知的电源/接地连接。此外，可以以框图的形式示出装置，以便避免使本说明书一个或多个实施例难以理解，并且这也考虑了以下事实，即关于这些框图装置的实施方式的细节是高度取决于将要实施本说明书一个或多个实施例的平台的（即，这些细节应当完全处于本领域技术人员的理解范围内）。在阐述了具体细节（例如，电路）以描述本公开的示例性实施例的情况下，对本领域技术人员来说显而易见的是，可以在没有这些具体细节的情况下或者这些具体细节有变化的情况下实施本说明书一个或多个实施例。因此，这些描述应被认为是说明性的而不是限制性的。 [0074] 尽管已经结合了本公开的具体实施例对本公开进行了描述，但是根据前面的描述，这些实施例的很多替换、修改和变型对本领域普通技术人员来说将是显而易见的。例如，其它存储器架构（例如，动态RAM（DRAM））可以使用所讨论的实施例。 [0075] 本说明书一个或多个实施例旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、修改和变型。因此，凡在本说明书一个或多个实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本公开的保护范围之内。