一种跨多数据中心的数据分布式处理加速方法及其系统

摘要

本发明提出了一种跨多数据中心的数据分布式处理加速方法。本方法中每个站点只要获得所需的输入数据就能够执行对应的计算任务。每个站点的输入数据加载、map计算、shuffle传递和reduce计算过程都不需要等待其他的站点的前一个过程都完成对应的操作。同时，本发明提供了精确的计算时间估计，并使得本发明方法适应动态的广域网带宽来提升SDTP的实用性，能够极大地减少作业的响应时间。本发明还提出了一种跨多数据中心的数据分布式处理加速系统，对应于上述方法，能够充分的使用跨区域分布站点的网络和计算资源，从而有效地分析跨区域分布的数据而不必等待前一阶段的瓶颈站点完成对应的数据传输或计算任务。

说明书

技术领域

本发明涉及数据分析领域，具体公开了一种跨多数据中心的数据分布式处理加速方法及其系统。

背景技术

谷歌，亚马逊和阿里巴巴等云提供商已经在全球部署了数据中心，以提供即时服务。这些服务在全球范围内生成大量数据，包括交易数据，用户日志和性能日志等。挖掘这些地理分布的数据（也称为广域分析）对于商业建议，匿名检测，性能升级和系统维护等至关重要。通常实施诸如Map-Reduce的分布式计算框架来挖掘此类海量数据集。这种计算方式的主要挑战是地理分布站点之间硬件资源的异构性，主要包括计算，上行链路带宽和下行链路带宽。最大的在线服务提供商的计算能力可能比普通在线服务提供商大两个数量级。此外，在Amazon EC2站点之间的WAN带宽中，站点之间的带宽比站点内的带宽小15倍，而且不同站点之间的广域网带宽达到12倍的差距。。地理分布站点之间的数据量的异构性也很高，数据量的异构性会严重影响广域网数据分析的执行。作业响应时间是分析地理分布数据的关键指标，该指标主要由作业在每个阶段的瓶颈站点的完成时间决定。但是，硬件资源的异构性和地理分布站点之间数据量的多样性严重影响了作业完成时间。因此，优化此度量标准具有挑战性，因为必须考虑多个因素，包括站点之间的WAN链路带宽，WAN链路的成本，每个站点中的计算资源和数据分布等。

Iridium 考虑到WAN的异构性，旨在通过优化reduce任务来最小化跨区域分析作业的响应时间。Flutter是考虑到WAN链路的异构性和WAN带宽成本，提出了一种新的任务调度算法，用于减少大数据处理作业的响应时间和网络成本。Tetrium 在设计了map和reduce的任务放置策略时共同考虑了计算和网络资源的异构性。 Yugong提出了一种新颖的数据和作业放置策略以最小化跨DC带宽的使用并减少查询等待时间。Liu等人主动汇总map任务的输出数据，并避免在shuffle阶段重复进行数据传输，以减少作业响应时间。以上方法通过各种方式减少作业响应时间，然而这些方法中大量的WAN链路和计算资源在作业执行期间却任然处于空闲状态。此外，这些方法都忽略了可用WAN带宽的动态特性以及并行度的影响。

除此之外，CLARIENT着眼于地理分布的SQL查询，包括支持WAN的查询优化器，可以实现多查询网络感知的计划选择和任务放置，以确保较低的查询延迟。WAanalytics和Geode试图减少跨地理分布的数据中心的带宽使用，并减少SQL查询请求的延迟。Lube实时监视地理分布的数据分析查询，并在运行时检测并缓解潜在的瓶颈（例如带宽不足），以减少查询响应时间。Gaia为跨站点学习任务提供了一种机器学习同步模型，它动态消除了站点之间的对结果影响不大的通信，从而加快了机器学习作业的执行速度。tom等人引入了预测性条约来预测系统状态的演变，该方法可以减少地理分布式应用程序的协调并提高应用程序性能。Monarch 优化了图数据分析并行系统的迭代处理方式，以有效地执行跨区域的图数据分析。Liu等人提出了一种分层同步并行模式，可以降低广域网带宽的使用，加快收敛速度，并降低广域图分析的WAN成本。G-Cut通过最小化DC间数据传输时间来优化图形处理作业的性能。HPS+提供了一种新的资源分配算法以节省传输的数据量并减少运行周期。但是，这些方法主要集中在广域网机器学习、SQL分析、天文应用和某些特殊领域。因此，它们不适用于诸如MapReduce之类的常规大数据处理框架。Turbo调整地理分布的SQL查询的查询执行计划，以响应跨数据中心的运行时资源变化。AWStream自动学习准确的配置文件，以对应用程序的准确性和带宽消耗之间的关系进行建模。通过调整应用程序数据速率以匹配可用带宽，同时最大程度地实现精确性。但是，它仅专注于广域网流数据分析，不适用于其他跨区域的数据分析作业。此外，这些方法没有考虑并行度和作业响应时间之间的关系。Decima使用强化学习和神经网络来学习特定工作负载的调度算法，并为每个作业设置有效的并行度，以最小化平均作业响应时间。但是，它仅尝试优化单个数据中心的集群中的平均作业响应时间。

发明内容

本发明目的在提供一种跨多数据中心的数据分布式处理加速方法及其系统，以解决现有技术中存在的未充分考虑站点之间异构性的技术缺陷。

任务调度策略以严格的顺序方式执行map-reduce任务，这可能会使跨地理位置分布的站点资源闲置并导致不必要的等待时间。图1和2给出了一个具有三个位置的示例。图1详细说明了基本设置。假设给定一个作业，作业包含一个reduce阶段，该阶段的每个任务可以处理100 MB的数据，并且处理每个任务所需的时间为2 s。最初，站点1、2和3分别包含10、40和50 GB的本地数据。它们具有不相等数量的计算实例，一对站点之间的链路带宽表示为一个二元组（上传带宽，下载带宽）；例如（1，5）。使用这种参数设置，Tetrium生成图2（a）所示的任务放置策略。在此放置解决方案中，站点2和3需要分别将26 GB和22 GB的数据传输到站点1。在此传输期间，站点2和3的计算和下载链路始终保持空闲，并不需要从其他站点获取输入数据。只有在完成所有传输后，站点才能开始数据计算。在此示例中，Tetrium总共花费56 s。

如图2（b）所示，通过平衡和并行化数据传输与数据处理，可以改善广域网数据分析的现有工作。在此解决方案中，站点2和站点3向站点1传输的数据较少，因为即使站点1具有更多计算实例，传输时间也可能使处理时间不堪重负。此外，站点2和3在时间0s就开始处理数据，因为它们不需要获取其他站点的数据。因此，数据传输和数据处理从0到20s执行任务的并行化处理。结果，该方案下总的时间花费为40s。

跨区域分布数据分析的一个重要特征和挑战是，在硬件容量方面，不同站点之间的资源高度异构。在不同的时间和不同的地区建立了不同的站点，具有不同的目标和预算，从而导致硬件资源的高度异构性。为了说明硬件资源的异构性，本发明比较了两个最重要的硬件容量，即计算能力和广域网带宽。特别是，最大的在线服务提供商之一的计算能力可能比普通的在线服务提供商的计算能力大两个数量级。不同站点之间的链路带宽也极为不同。根据对11个不同地区的Amazon EC2的测量，站点之间的带宽比站点内的带宽小15倍，在最坏的情况下，带宽差距达60倍，而且不同站点之间的广域网带宽达到12倍的差距。

此外，在不同站点上生成的数据量是异构的，这对作业响应时间有严重影响。对从100多个不同的Azure站点获取的Skype日志进行的分析表明，所有站点的中位数，第90个百分位数和最大值是包含最少日志数据的站点的中位数，第90个百分点和最大值的8,15和22倍。因此，在某些情况下，站点之间的数据分布可能不是恒定的，甚至可能是倾斜的。

不同站点之间WAN带宽的动态性也对地理分布的数据分析作业提出了重大挑战。研究人员发现，不同站点之间存在很大的差异，在某些情况下，可用带宽低于最大带宽的25％。因此，在带宽改变之前，难以开发用于最小化广域网作业响应时间的任务布置策略。

在并行计算中，作业流程处理的数据量是变化的。即使作业包含相同数量的数据，不同的并行度也将导致不同的作业响应时间。为了确定计算时间与输入数据大小和并行度之间的关系，本发明基于11个虚拟机（1个主节点和10个从节点）构建了一个Spark集群。每个虚拟机包含8个核心和8 GB主内存。

在上述环境下测量了在BigDataBench下在Spark上运行的两个查询的运行时间，结果如图3所示。随着并行度的增加，查询2的运行时间几乎没有变化。查询1处理80 GB的输入时，显示出当计算实例从8增加到56个时，查询1的时间显著减少。当查询1处理20 GB的少量输入时，它需要不超过16个并行计算实例。因此，对于所有作业，在曲线上的“最佳位置”之外分配其他并行任务只会减少收益。从图3中可以确定计算时间与输入数据大小和并行度之间的关系。

根据上述观察和动机，为实现上述目的，本发明提供了首先提供了一种跨多数据中心的数据分布式处理加速方法，称为SDTP（Simultaneous Data Transfer andProcessing），描述如何放置map和reduce作业，以最大程度地减少系统中广域网数据分析作业的整个响应时间。每个阶段中的任务放置都涉及确定应将哪些任务放置在站点上并确定任务输入数据的来源。本方法包括以下步骤：

S1：将广域网数据分析作业分解为map阶段和reduce阶段，所述map阶段包括输入数据加载和map计算两个过程，所述reduce阶段包括shuffle传递和reduce计算两个过程。

分析作业通常包括多个map-reduce阶段。假定每个作业只有一个map阶段和一个reduce阶段，分别为每个阶段制定广域数据分析作业的任务放置。 map阶段包括输入数据加载和map计算两个过程，reduce阶段分为shuffle传递和reduce计算两个过程，如图4所示。

由于WAN带宽和地理分布站点之间计算能力的异构性，因此在不同站点上获取所需输入数据的传输时间是不均匀的。但是，在以前的方法中，只有在所有站点的传输都完成后，各站点才能执行对应map计算。这将使跨地理位置分布的站点闲置并导致不必要的等待时间。因此，在本发明的方法中，站点可以执行其任务计算，只要它获得所需的输入数据即可避免不必要的等待时间。

S2：根据站点之间所需传输的数据量和站点动态变化的带宽，计算得到该站点在所述map阶段的下载时间以及包含该站点的输入数据其他站点在所述map阶段的上传时间。

在map阶段，任务放置问题涉及确定应从站点

由于站点之间的WAN链路的带宽可能是动态的，因此

从式（2）和式（3）可以确定站点

S3：根据站点在所述map阶段的下载时间以及其他站点在所述map阶段的上传时间得到输入数据加载时间；根据站点数据总量，站点间的并行度以及分析作业操作过程计算得到所述map计算过程的时间。

站点

站点上任务的计算时间取决于要处理的数据总量，站点的并行度以及作业在map阶段的计算特性。因此，在map计算阶段使用函数

除此之外，数据量需要满足以下限制。即从站点

S4：根据所述输入数据加载时间、所述map计算阶段时间、站点在所述map阶段的下载时间、其他站点在所述map阶段的上传时间以及数据总量约束构建所述map阶段的任务放置问题。

使用上面的描述，在map阶段的任务放置问题P1如下：

S5：根据站点需下载的数据总量、站点的动态带宽计算得到站点在所述reduce阶段的下载时间以及其他站点在所述reduce阶段的上传时间。

在reduce阶段应确定要在每个站点

在shuffle阶段，站点

从式（9）和式（10）可以得出，站点

S6：根据站点在所述reduce阶段的下载时间以及其他站点在所述reduce阶段的上传时间得到shuffle过程的数据传输时间；根据所述map阶段之后的所述map任务生成的中间数据量、站点的并行度以及作业的计算特性计算得到所述reduce计算阶段时间。

根据S5可以得到：

在map阶段之后，来自站点

每个站点上的reduce任务的比率

在reduce计算阶段，站点

S7：根据站点在所述reduce阶段的下载时间、包含该站点的输入数据的其他站点在所述reduce阶段的上传时间、所述shuffle过程的时间、所述reduce计算过程的时间、任务比例约束、map阶段的map任务生成中间数据构建所述reduce阶段的任务放置问题。

使用以上描述，在reduce阶段将任务放置问题P2表示为：

S8：根据所述map阶段的任务放置问题和所述reduce阶段的任务放置问题计算得到广域网数据分析作业的响应时间。

通过式（7）和式（15）可以获得完成一个广域网数据分析作业在map和reduce阶段总的响应时间。但是，P1和P2都是非线性规划问题。由于WAN带宽的动态特性，以及获取map和reduce任务的计算时间比较复杂，问题P1和P2是NP-hard。

为了克服NP-hard问题，假设WAN是静态的，每个站点都使用固定的WAN带宽。其次，假设每个任务的计算时间是固定的，并且可以通过一个简单的公式来计算map和reduce计算过程的时间。

在map阶段：由于MapReduce生产集群中只有7％的作业是reduce繁重的作业。也就是说，减少map阶段的运行时间对于最小化整个作业的响应时间特别重要。由于WAN是静态的，因此每个站点都有固定的WAN上载和下载带宽。

为了简化计算过程中计算时间的获取，假设每个任务的计算时间是固定的，并且

map阶段问题的目标与P1相似。因此，map阶段的任务放置问题P3被表示如下：

上面的问题是非线性规划问题。使用现有的求解器也很难获得最佳解决方案。因此为了进一步简化了问题。假设map任务的计算必须等待数据传输完成。Map阶段的输入数据加载时间和map计算时间均由瓶颈站点控制。可以将这个问题的目标转化为式（21）。具体来说，此作业的map阶段中的输入数据加载时间等于所有站点上最大的输入数据加载时间，如式（22）。在此作业的map阶段中，map计算时间由所有站点上的最大计算时间所控制，如式（23）,因此问题P3可以进一步简化为问题P4，公式如下：

上面的问题是线性规划问题，可以通过现有方法在多项式时间内解决，例如内点法或许多求解器已经实现的其他线性规划算法。但是，P4的最佳解决方案可能不是P3的最佳。为此，本发明设计了一种启发式算法来计算map阶段中的任务放置问题（算法1），从而以减少的广域网作业响应时间实现最优任务放置。

在描述算法之前，需要先介绍三个定理。

定理1.当所有站点在此阶段具有相同的响应时间时，将使该阶段的响应时间最小化。

证明：假设存在一个任务放置方案，其中所有站点的响应时间都不相同，并且该任务放置方案在map阶段的时间最短。图5（a）给出了一个示例，其中站点3是响应时间最长的瓶颈站点，而站点2的响应时间最短。

因为所有站点都可以互相传输数据，所以如果站点3可以向站点2传输少量数据，并且站点2和站点1的响应时间就不会超过其他站点的最大时间。因此，站点3的任务量将减少，站点3的计算时间将随着任务数量的减少而减少。站点3的传输时间取决于站点3的下载时间与需要将数据传输到站点3的站点的上传时间之间的最大传输时间。由于站点3的下载数据不变，因此站点3的下载时间保持不变。同样，站点3的上传时间也保持不变。因此，站点3的传输时间将减少或保持不变。因此，减少了站点3的响应时间，并且站点1和2的响应时间均小于站点3的响应时间。最后，该阶段的响应时间将减少。因此，该结果与假设相矛盾，定理1得以证明。

定理2：在给定阶段，存在任务放置，其中所有站点中的最大响应时间为

证明：在并行数据分析中，阶段的响应时间由瓶颈站点决定。因此，如图5（a）所示，此阶段的响应时间为

定理3：在map阶段，如果站点1需要将

证明：假设站点

算法1：

1 基于

2 计算得到各个站点map阶段的相应时间

3 调用

4 调用

5 返回

6 Function

7

8 while

9

10 得到站点集合

11 for

12 按

13 计算新的map响应时间

14 返回

15 Function

16

17 while

18

19 将

20 Let

21 检查循环是否存在并更新

22 计算新的map响应时间

23 返回

在算法1中尝试平衡每个站点的响应时间。首先，通过使用线性规划确定初步数据传输方案来获得线性规划问题P4的数据传输解（步骤1）。此后，计算每个站点的响应时间

此后，为了进一步缩短map阶段的作业响应时间，使用另一个函数equal

在reduce阶段，WAN是静态的，每个任务的计算时间是固定的，并且每个站点上的所有任务都需要多次执行。站点

最后，将reduce阶段的任务放置问题P5可以被表示如下：

由于上述问题的复杂性，需要继续进行简化。本发明要求所有reduce任务的计算都在shuffle过程之后。因此，将reduce阶段的目标转换为式（29），将作业的shuffle时间用式（30）表示，式（31）表示作业的reduce计算过程的计算时间。问题P6可以表述如下：

这是一个线性规划问题，可以通过现有求解器在多项式时间内求解。但是，上述方案的作业响应时间还不够小。

由于计算能力的限制，一个站点的map任务不能同时执行，并且每次只能同时执行一部分任务。因此，任务将在不同的批次上执行。任务完成后，可以将这些map任务生成的中间数据先传输到其他站点，这些站点将使用这些数据执行相应的reduce任务。即map过程是CPU密集型，并且shuffle阶段是

可以通过重叠map计算和shuffle阶段来制定作业响应时间。

最后，整个作业的任务放置问题P7可以表示如下：

考虑到上述特征，本发明设计了一种称为SDTP的算法（算法2），以减少整个作业的响应时间。图8中描述了基本概念。相反，图7中显示了常规的广域网数据分析执行过程。只有在所有站点上的先前阶段均已完成时，作业才能开始新阶段。这种方式会导致作业处理期间出现大量资源空闲。本发明SDTP会尽快开始数据处理，并尝试利用这些站点的资源来加快作业执行过程。

算法2：

1 通过算法1计算

2 基于

3 通过求解P7确定

4 计算各个站点新的响应时间

5 调用

6 返回

7 Function

8

9 while

10

11 更新降低率

12 计算各个站点新的响应时间

13 返回

具体来说，首先通过

在算法1中，第17至22行的while循环的迭代次数为常数

由于WAN带宽的动态特性和并行计算中的并行度将严重影响广域网数据分析中的作业响应时间。本发明描述了尝试制定合适的任务调度方案，通过提供更准确的时间估算并将其推广到广域网带宽动态变化的情况来优化作业响应时间。

对于精确的时间估计：具有大量输入或大量中间数据的作业可以有效地利用其并行性。相反，在较小的输入数据上运行的作业或并行化操作效率较低的作业将从额外的并行性中获得很少的收益。因此，有必要了解作业运行时间与输入数据大小和并行度之间的关系。

对于重复性作业，可以对运行时间和中间数据大小进行合理估计。因此，本发明尝试设计一种改进的方法以减少作业运行时间。使用多元非线性回归算法来预测作业的运行时间。当计算在每个阶段分别计算任务放置解决方案的时间，为每个阶段的运行时间构建相关模型。在map阶段，问题P8可以表示为：

在reduce阶段，问题P9可以表示为：

如算法3所示，首先根据每个阶段的预测时间，首先建立预测模型

对于动态网络带宽：除了稀缺性之外，WAN带宽中还存在较大的差异。动态WAN带宽将显著影响广域数据分析作业的响应时间。例如，一个站点可能包含足够的带宽和丰富的计算资源，因此可以执行作业A的大量计算任务，但是在作业A的执行过程中，该站点的WAN带宽急剧下降，此时该站点必须花更多的时间获取所需的输入数据。因此，如果不改变原始任务放置策略，作业A的作业响应时间将大大增加。因此，有必要考虑WAN带宽的动态特性，尤其是对于响应时间长的批处理作业。

针对动态WAN带宽，本发明设计了一个任务放置更新模块，该模块提供了一个带宽检测组件，可以以给定的间隔检测每个站点的带宽。当WAN带宽的变化超过

在算法4中，没有循环，最耗时的过程是调用算法3进行执行。因此，算法4的复杂度由算法3支配。在算法3中，调用函数

算法3 SDTP+：

1 构建模型

2 通过解决P4计算

3 通过模型

4 调用

5 按算法2的步骤2至步骤5得到新的

6 返回

算法4 SDTP++：

1 按算法3计算得到

2 使用

3 以新的时间间隔

4 if 网络带宽变化率

5 if

6 通过

7 通过算法3计算计算

8 if

9 通过

10 返回

依托于上述方法，本发明还提供了一种跨多数据中心的数据分布式处理加速方法的系统，包括处理器、存储器以及储存于存储器上并可在处理器上运行的计算机程序，处理器执行计算机程序时实现上述任一方法的步骤。

本发明具有以下有益效果：

本发明提出了一种新的非线性规划模型，该模型通过联合考虑站点内的资源异构性和并行度以及站点之间的动态WAN链路来表征跨区域的数据分析工作，可以在数据传输和数据处理之间实现有效的平衡，并尽可能快的开始数据处理，从而减少作业处理时间。同时提供了更准确的时间估算，并将其推广到WAN带宽动态变化的情况下。本发明性能优于现有方法，总体工作响应时间相较于传统方法大大减少。

下面将参照附图，对本发明作进一步详细的说明。

附图说明

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

图1为本发明所述的三个跨区域的站点提供异构的硬件资源示意图；

图2为本发明所述的原有方法和优化后方法的作业完成时间示意图；

图3为本发明所述的不同并行度和输入数据下的作业完成时间示意图；

图4为本发明所述的一个广域网数据分析作业的执行过程示意图；

图5为本发明所述的不同的任务放置方法示意图；

图6为本发明所述的一个提升的任务放置方法示意图；

图7为本发明所述的原有方法的执行过程示意图；

图8为本发明SDTP的执行过程示意图；

图9为本发明优选实施例提供的不同站点数量下的不同方法平均响应时间以及速度降低对比图；

图10为本发明优选实施例提供的不同站点数量下的不同方法减少平均响应时间以及降低不同规模示意图；

图11为本发明优选实施例提供的不同站点数量下的不同方法减少平均响应时间并降低不同组件的速度示意图；

图12为本发明优选实施例提供的

图13为本发明优选实施例提供的计算实例数量的影响示意图；

图14为本发明优选实施例提供的绝对百分比误差和平均响应时间的减少以及预测计算时间对比图；

图15为本发明优选实施例提供的减少WAN带宽变化时的平均响应时间示意图；

图16为本发明一种同时数据传输和处理加速广域网数据分析的方法流程图。

具体实施方式

以下结合附图对本发明的实施例进行详细说明，但是本发明可以由权利要求限定和覆盖的多种不同方式实施。

本实施例构建了两个具有10或30个地理分布的异构站点的广域网分析环境。资源容量是根据Amazon EC2设置的。具体配置为：每个站点之间链路的带宽范围从100 Mbps到2Gbps；每个站点上的计算实例数范围从10到100；设置中间数据与输入数据之间的比率

本实施例使用了有关Google和阿里巴巴中数据中心使用情况的真实的集群运行的数据集来模拟跨区域的数据分析作业。 Google数据集收集以下信息：包含了1.25万台机器的机器的作业、任务和机器运行的信息。机器，作业和任务的事件全部由一个或多个记录描述。每个记录通常包含元信息，例如时间戳，ID，事件类型和资源请求。阿里巴巴数据集由阿里巴巴集团于2018年发布。其中包含有关八天内4千台机器的记录。此数据集包括许多类型的批处理作业负载，其中大多数是DAG作业。

这两个数据集的记录单个数据中心中的作业运行信息。为了模拟跨区域的数据分析作业的运行，本实施例将这些计算机划分为不同的站点。根据机器上每个作业的任务分布，可以获得所有站点上每个作业的输入数据量。

本实施例中将本发明的方法与以下方法进行了比较：

In-Place:默认的Spark方法，根据输入数据的位置在本地运行任务，并在shuffle阶段将任务平均分配给所有站点。

Iridium: 最近的一种方法是通过优化reduce阶段的任务放置来改善广域网数据分析作业的响应时间。

Tetrium: 近年来的最先进方法旨之一在优化输入数据的放置并优化reduce阶段的任务放置，改善作业的响应时间。

实施例1

本实施例通过将SDTP与几种经典的任务放置方法进行比较，以平均响应时间和平均slowdown进行比较，来评估SDTP的性能，主要是通过与各种方法相比平均响应时间减少和平均slowdown降低来得出结论。其中，slowdown定义为与其他方法相比，单个作业的响应时间减少率。例如，使用In-Place的作业A的响应时间为

图9（a）展示了SDTP在不同站点数量下平均作业响应时间的改进。显然，SDTP明显优于其他基准方法。特别是，当站点数量为10时，与In-Place相比，本发明的方法将所有作业类型的平均作业响应时间减少了72％，70％和29％。由此可知，本发明的方法可以有效地减少作业响应时间。当站点数为30时，与In-Place，Iridium和Tetrium相比，本发明的方法将所有作业类型的平均作业响应时间分别减少了61％，60％和19％。在10个站点设置下，平均响应时间的减少比在30个站点设置下的平均响应时间的减少更为显着。这是因为更多的站点导致需要更多的计算资源来处理作业，并且减少了map计算和shuffle阶段的重叠时间。因此，平均响应时间的减少随着站点数量的增加而减少。

图9（b）还显示了当站点数量变化时，与In-Place，Iridium和Tetrium相比slowdown的降低。当站点数量为10时，与In-Place相比，本发明的方法可以将每个作业的平均响应时间减少56％。因此，SDTP可以减少大多数广域网数据分析作业的作业响应时间。同样，随着站点数量的增加，平均slowdown的下降也有所减少。这也是因为随着站点数量的增加，处理作业所需的计算资源的总和增加了，并且map计算和shuffle过程的重叠时间减少了。因此，当站点数量增加时，平均slowdown的减少程度将减小。此外，根据不同的基准，平均响应时间的减少小于平均slowdown的减少。这表明SDTP对于响应时间长的作业更有效。

本实施例还评估了与In-Place，Iridium和Tetrium相比，不同规模作业的平均响应时间的改进。本实施例根据所需的输入数据量将所有作业分类为小规模，中等规模或大规模的作业。如果作业的输入数据量不超过60 GB，则将其视为小型作业。如果作业的输入数据量大于60 GB且不大于600 GB，则将其分类为中等规模的作业。否则，这是一项大规模的作业。在此实验中，站点数设置为10。

图10（a）表明，随着作业规模的增加，平均响应时间的改善更大。也就是说，本发明的方法对于耗时的作业更为有效。这是因为随着作业规模的增加，SDTP可以使用更多的空闲资源来传输数据和处理任务。在shuffle过程，耗时的作业通常会导致跨所有站点的数据传输和映射任务执行的总时间差异更大。因此，SDTP可以使用空闲资源来平衡跨所有站点的数据传输和映射任务执行，从而节省更多时间。在reduce阶段，较大的作业会导致更长的map计算和shuffle传输时间，并且可以通过重叠map计算和shuffle过程来进一步减少作业响应时间。

图10（b）显示了随着作业规模的增加，作业响应时间变小。显然，大规模作业的平均速度下降幅度在37％至75％之间。因此，当作业规模较大时，本发明的方法可以有效地减少作业响应时间。平均slowdown的减少随着作业规模的增加而减少。这是因为，随着输入数据量的增加，作业的响应时间增加，并且SDTP可以优化的时间变长。

本实施例还评估了与In-Place，Iridium和Tetrium相比，平均响应时间对不同组件的影响。图11（a）展示了在不同组件上与其他方法相比平均响应时间的减少。在map阶段仅使用算法1时，与In-Place，Iridium和Tetrium相比，SDTP分别将平均作业响应时间减少了65％，61％和10％。在减少阶段仅使用算法2时，平均作业响应时间的减少大于使用算法1时平均作业响应时间的减少。也就是说，算法2可以减少更多的作业响应时间。同时使用算法1和2时，平均作业响应时间的减少大于仅使用一种算法时平均作业响应时间的减少。也就是说，同时使用算法1和2可以减少作业响应时间。此外，同时使用算法1和2的平均作业响应时间的减少小于分别使用算法1和算法2的平均作业响应时间减少的总和。因此，算法1和2相互影响。

图11（b）显示了与其他方法相比平均slowdown降低的情况。可以观察到，使用算法2时的平均减少slowdown比使用算法1时的平均减少slowdown稍大。这表明算法2在减少作业时间方面更有效。此外，当同时使用算法1和2时，减少的slowdown大于仅使用一种算法时的减少的slowdown。

实施例2

本实施例将量化各种参数对SDTP的影响，其中包括

图12（a）描绘了

图12（b）说明了与In-Place，Iridium和Tetrium相比具有不同

不同数量的实例也会影响作业响应时间。图13（a）表明，平均作业响应时间的减少随着实例数量的增加而减少。在本实验中，当实例的比率为1时，每个站点上的实例数在100到1000之间。当计算实例的比率为0.1时，每个站点上的计算实例数等于当计算实例号的比率为1时的计算实例数乘以0.1时。因此，实例的数目随着实例数目的比率的增加而增加。该图表示了作业在不同比率下的响应时间，其中T是计算实例的比率为1时的响应时间。可以看出，随着计算实例数的增加，作业响应时间减少了。当站点具有更多实例时，它可以处理map并更快地减少任务，因此，减少了map的时间并减少了计算阶段。

与Iridium和Tetrium相比，具有不同计算实例数量的平均响应时间的减少如图13（b）所示。可以观察到，随着计算实例数量的增加，平均响应时间的会减少。这是因为，当站点具有更多计算实例时，shuffle和reduce计算时间会减少，因此SDTP可以减少的时间受到限制，尤其是在reduce传输过程。

实施例3

本实施例考虑了并行性在并行计算中的影响。首先评估了预测方法对不同阶段响应时间的影响。此后，在考虑并行度的情况下评估了计算属性对并行计算中不同方法的影响以及方法平均响应时间的改进。

本实施例使用BigDataBench 测量了在Spark上运行的具有不同数据量和并行度的多个查询的时间。根据结果，本实施例使用多元线性回归算法构建每个阶段计算时间的预测模型。结果表明，R2统计量均大于0.9，其中R为相关系数。 F统计量的值大于根据F分布表的值。与F统计量相对应的概率p均小于0.0001。即，在输入数据量和并行度之间存在很强的相关性，因此预测模型是有效的。

为了量化并行度的影响，本实施例分析了不同方法的绝对百分比误差（APE）。计算出的APE为

因此，如果仅使用shuffle时间并减少任务和计算实例的数量来计算不同阶段的计算时间，则作业响应时间的最终结果将与实际作业响应时间明显不同。此外，由于Tetrium考虑了计算资源异构性在不同站点上的影响，因此Tetrium的APE比其他方法更大。Tetrium中每个站点的计算时间等于

与In-Place，Iridium和Tetrium方法相比，不同作业规模下的平均响应时间减少了，如图14（b）所示。可以看出，所有作业的平均响应时间提高了7％至14％。此外，当作业规模很大时，所有作业的平均响应时间将缩短20％至26％。即，平均响应时间的减少随着数据量的增加而增加。通常，SDTP +的平均响应时间的改进在某种程度上受到限制。这是因为在该实验中，在所有情况下，每个作业在每个站点上的输入数据量均小于100 GB。

实施例4

图15（a）展示了动态WAN链路带宽对作业响应时间的影响。所有站点的更改带宽都是在0.1和2 GB/s之间随机生成的。当WAN带宽在不同的作业规模上变化时，本实施例测量了SDTP++与SDTP+相比，平均响应时间的减少。从图14（a）可以看出，平均响应时间大大减少了。因此，如果在任务放置保持不变的情况下改变WAN带宽，则作业响应时间将变得很长。当作业规模为中等或较大时，与小规模作业相比，平均响应时间的减少非常大。因此，SDTP++对于耗时长的作业更为有效。

图15（b）显示了使用不同WAN带宽时平均响应时间的减少。在该图中，横坐标

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。