0 概述

随着大数据技术的发展, 在云数据中心需要处理的数据规模呈指数型增长, 使得并行计算框架(如MapReduce^[1]和Spark^[2])成为云服务中数据处理分析的主流平台。在上述计算框架中, 一个作业包含多个计算阶段, 如MapReduce作业中的map映射阶段和reduce归约阶段。在一个计算阶段(如reduce)开始之前, 需要启动多条流以传输来自前一计算阶段(如map)所产生的中间数据。由于这些中间数据体量大, 因此在网络中的传输对相应的作业性能有较大的影响。文献[3]研究结果表明, 中间数据流的传输时间占整个作业完成时间的比例高达50%。因此, 优化中间数据流的传输对分布式并行计算应用的性能至关重要。

近年来, Coflow^[4]作为一种流量模型, 被广泛地用于并行计算作业通信阶段。Coflow是一个并行计算作业中2个不同计算阶段间的数据流的集合。为提升分布式并行计算应用的性能, 需要优化Coflow的完成时间(Coflow Completion Time, CCT), 而不是单个流的完成时间(Flow Completion Time, FCT)。这主要是因为一个并行计算作业的完成时间依赖于其所有中间网络数据流的完成, 而不是单个流的完成。例如, 在MapReduce^[1]中, 一个计算阶段不可能在它收到前一个计算阶段的所有中间数据流之前完成。文献[4-6]研究表明, 优化Coflow的平均完成时间能够明显提升分布式并行计算应用的性能。

现有针对Coflow平均完成时间的优化工作, 主要通过设计合理的Coflow调度机制来实现, 平均完成时间的优化主要分为两类。一类是先验知识已知的Coflow调度机制^[5-7], 其中先验知识主要指Coflow中流的数据量。在这类工作中, Varys^[5]在平均Coflow完成时间方面的性能最好, 它利用最小有效瓶颈优先的Coflow调度策略, 来近似地模拟最短作业优先启发式算法, 从而优先选择小Coflow。但是Varys依赖于Coflow中流量大小信息, 这种信息在许多实际场景中都是无法事先预知的。另一类工作是先验知识未知的Coflow调度^[8-9]。Aalo^[8]是这类工作的代表, 其根据当前已经发送的数据量来决定Coflow的优先级。由于不需要事先知晓Coflow的流量信息, 因此Aalo的实用性很高。但是其根据Coflow总体发送数据量决定优先级过于粗糙, 且容易错失一些潜在的优化空间。

本文通过分析现有研究的不足并结合实际场景中Coflow的特点, 提出一种近似最小有效瓶颈优先调度机制(A-SEBF)。通过联合Coflow当前已发送数据和Coflow宽度这2个信息决定Coflow的优先级, 并基于Facebook公开的MapReduce/Hive数据集, 与先验知识已知调度器Varys和先验知识未知调度器Aalo进行仿真实验对比。

1 相关工作

数据中心网络流量调度按照调度粒度可分为基于单个流的调度和基于Coflow的调度。基于单个流的工作虽然能够优化流的平均完成时间^[10-11], 但它们不考虑流与流之间的协同依赖关系, 无法适用于Coflow的调度场景中^[12-13]。在基于Coflow的调度研究工作中, 文献[3]提出Orchestra方法以对并行计算应用产生的流进行调度, 并于2012年提出Coflow模型^[4]来描述并行计算应用2个计算阶段间并发流的集合。至此, 基于Coflow的研究开始得到广泛的关注。现有研究工作按照调度目标可分为以性能为导向的Coflow调度^[5-8]和以公平为导向的Coflow调度^[9]。这两类方法又可进一步分为先验知识已知的Coflow调度和先验知识未知的Coflow调度。

1) 以性能为导向的Coflow调度。为提升分布式并行计算作业的性能, 网络操作者应以最快的方式将尽可能多的Coflow传输完成。以性能为导向的Coflow调度研究工作主要以最小化Coflow的平均完成时间为目标。其中, 一部分研究工作适用于先验知识已知的场景^{[5-7, 14-16]}, 另外一部分则适用于先验知识不可知的场景^[8]。在先验知识已知的场景中^[17-18], Varys^[5]采用最小有效瓶颈优先的启发式策略来调度Coflow。此外, Baraat^[6]方法利用先进先出和公平共享的调度策略来减少Coflow的平均完成时间。在先验知识未知的场景中, 为减少平均Coflow完成时间, Aalo^[8]提出D-CLAS(Discretized Coflow Aware Least Attained Service)方法。D-CLAS按照已发送数据大小将Coflow划分到不同的优先级队列中, 并在每个队列中以先进先出(FIFO)的方式对Coflow进行调度。然而, 由于总体数据量小的Coflow不代表其瓶颈流数据量小, 使得它容易忽略一些潜在的优化空间。

2) 以公平为导向的Coflow调度。较多研究人员认为同等地对待所有Coflow对部分有着特殊需求的Coflow会不公平。在先验知识已知的场景中^[19-21], 文献[19]针对Coflow延迟敏感度进行效益函数建模, 并建立一个字典序最大化问题以优化Coflow的效益总和, 但是他们的方法不能提供性能隔离。为此, 文献[20]提出Coflex以兼顾Coflow平均完成时间和Coflow间的性能隔离。此外, HUG^[22]也能实现这种性能隔离保障。但是当Coflow流量信息未知时, 这些方法将不再适用。为此, wenian^[9]提出NC-DRF调度器, 以在先验知识不可知场景下实现Coflow间的隔离保障。以上方法虽然能提供公平或性能隔离保障, 但它们在减少Coflow平均完成时间方面的性能欠佳。

总体来看, 现有研究在最小化Coflow平均完成时间的性能方面欠佳, 尤其是在Coflow流量信息无法预知的场景下, 还有较大的提升空间。

2 研究背景

本节介绍Coflow及数据中心网络抽象模型, 并结合实例来详细论述本文的研究动机。

2.1 Coflow抽象模型

一个Coflow是指一个分布式并行计算作业的2个不同计算阶段间数据流的集合^[4]。Coflow中的流仅包含中间传输的数据流, 而不涉及通信过程中产生的控制流。Coflow抽象模型允许并行计算应用明确地表述其网络需求, 例如最小化Coflow完成时间或确保Coflow内所有流在截止时间前完成。在数据中心中, 许多并行计算作业会同时运行。因此, 大量Coflow会共存于数据中心, 并相互争用网络资源。Coflow调度机制的目标是最小化Coflow的平均完成时间, 以提高应用层作业的性能。

由于Coflow包含多个流, 因此不能仅用数据大小来刻画它。Coflow包含很多特征, 如长度、宽度、大小等^[5]。长度指Coflow中数据量最大的流的大小; 宽度指Coflow中并发流的数目; 大小指Coflow中所有流大小的总和。在很多实际场景中, Coflow的大小不能预先知晓, 这主要是由流水线作业^[23]、多波任务执行^[24]以及任务失败^{[1, 25]}等原因所导致。例如, 在流水线多阶段作业中(如MapReduce Online^[23]), 数据一经产生就直接被传送到目的地, 且仅当所有数据传输完毕, 才能知道流的大小。为此, 本文重点关注Coflow大小不可知的场景。

2.2 数据中心网络抽象模型

本文考虑将整个数据中心网络抽象为一个无阻塞的连接所有服务器的大交换机^[26], 并且只关注其出入端口。这种网络抽象模型在全平分带宽拓扑^[27]下是合理的, 并且大量地被现有研究工作所采纳^{[5-9, 19-21]}。在这种大交换机模型中, 每个入端口对应所连接服务器的外向链路, 而每个出端口对应所连接服务器的入链路。

如图 1所示, 一个包含3台服务器的数据中心网络被抽象为一个无阻塞的大交换机。在图 1中, 有3个Coflow, 分别用灰色(C1)、黑色(C2)和白色(C3)表示。C1有2条流, 数据大小均为2。C2和C3均只有1条流, 数据大小分别为4和3。需要注意的是, 图 1中入端口的虚拟队列是用来表述流的源端点和目的端点的。例如, 在服务器1中, C1的其中一条流需要传送2个单位的数据给服务器2, C2的流需要传输4个单位的数据到服务器2;在服务器2中, C1和C3分别需要传输2个单位和3个单位的数据给服务器3。

2.3 研究动机

在先验知识未知的场景下, 当前最先进的调度方法是Aalo^[8]。Aalo采用一个集中控制器来统计每个Coflow的进度。进度是指截止到目前, 一个Coflow在所有端口已经发送的数据总和。具体到每个端口中, Aalo实现了一个本地调度器, 并结合多级队列机制以近似模拟最小Coflow优先的调度策略。Aalo会根据Coflow的进度将其放置在不同的优先级队列中。在队列间采用加权公平队列调度方法, 而在队列内部则使用先进先出的机制来决定流的发送顺序。从本质上来讲, Aalo对最小Coflow优先做了粗略的模仿, 但与此同时, 忽略了Coflow宽度信息, 使得它容易错失一些优化机会。

为了更好地说明Aalo的不足, 本文针对图 1中的Coflow来分析不同调度机制得到的不同调度结果。假设图 1中Coflow的数据大小信息能够预知, 那么最优的调度就是采用Varys的最小有效瓶颈优先方法。如图 2所示, 在最优调度机制下, C1首先被调度, 其次是C3和C2。假设每个端口单位时间内只能传输1个单位的数据, 那么在最优调度下, Coflow的平均完成时间为(2+5+6)/3=4.33。

图 3给了出在Coflow大小信息不能事先知晓的情况下采用Aalo调度器所得到的调度结果。假设在Aalo调度器中, 队列的阈值为1, 2, 4, 8, …, 那么Aalo所能实现的Coflow平均完成时间就是(4.5+5+6)/3=5.17。在这个例子中, Aalo具体工作流程如下:一旦Coflow的流到达, 它们进入最高优先级队列, 然后随着Coflow发送数据总量的增加, 逐步下移到低优先级队列。优先级移动的基本原则是一旦Coflow发送数据总量超过当前队列的预先设定的阈值, 那么该Coflow就会被移动到下一个低优先级队列中。

在Aalo的设计中, 队列的阈值是基于已经发送的总体数据量来制定, 并且单个队列的阈值对所有的Coflow都一样。当一个宽度较大的Coflow得到调度时, 它能迅速地到达队列阈值, 因为相比于瘦的Coflow, 胖的Coflow能够在更多的端口上传输数据。然而, 一旦它到达阈值并移动到低优先级队列后, 则需要等待高优先级的所有其他Coflow。在这种情况下, 原本应该优先被调度的胖而短的Coflow却需要等待瘦长的Coflow。这也是为何Aalo所实现的平均Coflow完成时间与Varys所实现的最优值相差甚远。

如果在调度时能够将宽度考虑进来, 那么Coflow的平均完成时间将能够得到进一步的优化。如图 4所示, 每个队列的阈值依然为1, 2, 4, 8, …。但是Coflow优先级队列移动的原则不再是基于已经发送的总体数据量, 而是基于平均每条流已经发送的数据量。例如, 当C1在优先级队列q₀中平均每条流发送的数据达到1时, C1就被移动到低优先级队列q₂中。可以看出, 在这种调度机制下, Coflow的平均完成时间是(3+5+6)/3=4.67。

实际上, 不同Coflow的宽度存在着很大的差异。图 5和图 6分别展示了Coflow宽度与Coflow数据量大小的关系, 其中的数据是来自于Facebook数据中心的MapReduce/Hive数据集^{[5, 7-8]}。可以看出, 无论是发送端口还是接收端口, 都存在端口数目少但数据量大的Coflow。若在调度中, 这些Coflow很有可能被认为是小Coflow并因此具有高优先级, 这显然与最优的Coflow调度思想相违背。为此, 本文后续部分将通过设计近似最小有效瓶颈优先调度机制来解决这类问题。

3 A-SEBF设计 3.1 整体工作流程

本节首先介绍A-SEBF的整体工作流程。A-SEBF调度机制如图 7所示。

A-SEBF流程与Aalo^[8]类似, 且涉及2个部分:全局控制器和本地进程。其中每台服务器主机运行一个本地进程。全局控制器定期地收集每台服务器主机中所有流截止到当前已经发送的数据量。全局控制器根据收集的结果, 得到所有Coflow当前已经成功发送的数据量大小, 并结合Coflow的宽度信息计算瓶颈因子。然后通过比较瓶颈因子与不同优先级队列的阈值来决定每个Coflow应该放在哪个优先队列。每台服务器主机根据接收到的优先级信息, 将Coflow移动到对应的优先级队列。同一优先级队列采用先进先出调度, 不同优先级队列间采用按权公平队列调度策略。与Aalo类似, 本文使用阈值以10为底的指数型增长的优先级队列, 也即第h+1个队列的阈值是第h个的10倍。

表 1给出本文内容所涉及的变量和定义说明。

3.2 A-SEBF调度机制

本节首先介绍最小有效瓶颈优先(Smallest-Effective-Bottleneck-First, SEBF)调度机制。SEBF是Varys针对Coflow设计的调度机制, 并且是公认的在先验知识已知场景中的最优调度机制。SEBF的核心思想是找出每个Coflow的瓶颈所在, 并据此决定Coflow的优先级。具体来讲, 假设有一个Coflow k, 其需要从主机i传输d_{i, j}^k的数据量到主机j。假设主机i的出口带宽为b_i^out, 主机j的入口带宽为b_jⁱⁿ, 那么该Coflow的完成时间至少为T_k:

$ {T_k} = \max \left( {{{\max }_i}\frac{{\sum\limits_j {d_{i, j}^k} }}{{b_i^{{\rm{out}}}}}, {{\max }_j}\frac{{\sum\limits_j {d_{i, j}^k} }}{{b_j^{{\rm{in}}}}}} \right) $

在Varys的SEBF方法中, T_k被认为是Coflow k的瓶颈因子。因为它是假设在得到所有带宽前提下, 一个Coflow中瓶颈流所需的完成时间。基于此, SEBF就是让T_k越小的Coflow优先级越高。Varys的实验结果表明, 相比于Coflow长度最短优先、Coflow宽度最窄优先以及Coflow数据总量最小优先等调度方法, SEBF能够明显减少Coflow的平均完成时间。SEBF虽然能表现出较好的性能, 但是其依赖于每个Coflow的数据大小信息, 例如d_{i, j}^k。而在很多实际场景中, 如2.1节所述, 这种信息是无法事先预知的。为此, 本文提出近似最小有效瓶颈优先调度机制, 称为A-SEBF。

A-SEBF主要基于2个信息对Coflow进行优先级排序。第1个信息是Coflow的当前大小, 也即截止到目前, 一个Coflow通过整个数据中心网络已经发送的数据量。由于Coflow大小通常呈现重尾分布趋势^[5], 因此Coflow当前大小能够很好地代表Coflow的实际大小, 并且在实际场景中也能很容易地被获取到^[28]。第2个信息是Coflow的宽度, 宽度是指Coflow中并发流的个数。如2.1节所述, 准确的流的数目很难知晓, 但是能够知道一个Coflow通过多少个端口来发送或接收数据。由于在许多实际的场景中, 相比于发送端, 接收端更容易造成拥堵^[29], 因此, 本文采用接收端口的数目来表示一个Coflow的宽度信息。

A-SEBF的核心就是基于Coflow当前大小以及Coflow宽度信息来评估该Coflow的瓶颈因子, 并根据瓶颈因子大小来决定不同Coflow的优先级。假设Coflow k的当前大小和接收端口数分别为S_k和W_k, 那么该Coflow的瓶颈因子λ_k被定义为:

$\lambda_{k}=\frac{S_{k}}{W_{k}}$

在A-SEBF中, 瓶颈因子λ_k越小的Coflow, 优先级越高。值得注意的是, A-SEBF与Aalo中的D-CLAS调度机制不同。D-CLAS本质上模拟的是Coflow大小最小优先调度机制, 即当前发送数据量S_k来判断Coflow优先级, 容易错失一些潜在的优化机会。假如, 有2个Coflow k₁和k₂, k₁的宽度大于k₂, 但其长度小于k₁。在某个特定时刻t, k₁当前大小S_k1大于k₂的当前大小S_k2, 那么根据Aalo的D-CLAS调度机制, k₂会优于k₁被调度。然而, 根据最优的最小瓶颈优先SEBF策略, k₁应该优先于k₂被调度。如果将Coflow的宽度信息兼顾起来, 若利用瓶颈因子λ_k决定Coflow调度顺序, 则能够在一定程度上消除这种现象。尤其是当Coflow当前大小差距不大, 而宽度差异明显时, 基于瓶颈因子λ_k的调度就越能体现出其在优化Coflow平均完成时间的优势。

4 实验评估

本节基于Facebook真实数据集对所提出的最小有效瓶颈优先调度机制进行性能测试, 并通过对比现有先验知识已知和先验知识未知场景下的调度机制来验证本文提出的调度机制的有效性。

4.1 实验设置

实验是在单机模拟环境下进行的, 具体包括一个Dual-Core Intel(R)Core(TM)i7-5500U 2.40 GHz CPU和8 GB内存。此外, 采用Java语言在CoflowSim^[30]开源框架的基础上实现了本文所提出的A-SEBF调度算法。CoflowSim是一个专用于Coflow调度的模拟器, 目前在Coflow的相关研究^{[5, 8, 17]}中得到了广泛应用。

本文采用由Facebook提供的MapReduce/Hive数据集^{[5, 7-8]}, 该数据集是从一个包含3 000台服务器和150个机架的集群中收集起来的, 该数据集一共包含526个在不同时间到达的Coflow。数据集中每个记录行包括以下信息:Coflow ID, 到达时间, mapper数量, mapper-m的位置, reducer的数量和reducer-r的位置, 以及该reducer需要读取的数据量。需要注意的是, 原始数据被压缩到了机架级别, 因此, mapper和reducer位置的取值范围是0~149。

为不对数据集做任何修改, 本文模拟一个包含150台服务器主机的数据中心网络, 其中每台服务器的出口和入口带宽容量均设置为1 Gb/s。

本文主要对比以下2个方法:

1) Aalo。该方法在Coflow信息不知晓的前提下, 利用D-CLAS策略来调度Coflow。

2) Varys。该方法在Coflow信息知晓的场景中, 利用SEBF策略对Coflow做最优的调度。

本文通过定义$ \frac{A u g C C T_{2}-A u g C C T_{1}}{A u g C C T_{2}}$性能指标, 来表示方法1在方法2的基础上Coflow平均完成时间降低的百分比, 其中, AugCCT₁和AugCCT₂分别是方法1和方法2所能实现的Coflow的平均完成时间。

4.2 结果分析

图 8给出了在不同调度方法下所有Coflow的平均完成时间, 其中, 横轴为不同的调度方法, 纵轴为完成时间度量。从图 8中可以看到, A-SEBF实现的平均完成时间明显少于Aalo, 且与Varys十分相近。更具体地讲, Aalo、A-SEBF和Varys这3种方法实现的平均Coflow完成时间分别是46 098 ms、30 800 ms以及28 528 ms。相比于Aalo方法, A-SEBF能够将平均Coflow完成时间降低(46 098-30 800)/46 098=33.2%。造成性能提升的主要原因是Aalo在调度中仅考虑当前已发送数据量, 没有考虑Coflow宽度的影响, 使得它容易错过一些潜在的优化机会。相比于Varys方法, A-SEBF仅有(30 800-28 528)/28 528=7.3%的差距。但是Varys假设先验知识已知, 在实际场景中得不到很好的应用, 而本文重点关注如何在先验知识未知的场景。上述结果表明, 本文提出的A-SEBF是一种先验知识未知场景下的高效调度器, 且它能够实现接近于先验知识已知场景下的最优平均Coflow完成时间。

为进一步理解不同方法的Coflow完成时间, 图 9给出了不同调度方法实现的Coflow完成时间的累积分布函数曲线。其中, 横轴表示完成时间并以对数刻度呈现, 纵轴表示累积分布函数(Cumulative Distribution Function, CDF)值。图 9能够表示出完成时间小于任何一个数值的Coflow数目占Coflow总数的比例, 可以看出, 在3×10⁵ ms之前, Aalo与A-SEBF这2条曲线走势差别不大或基本吻合; 但在3×10⁵ ms后, A-SEBF曲线明显高于Aalo, 部分时候甚至高于Varys曲线。具体来看, 在Aalo方法下, 97.91%的Coflow的完成时间小于10⁶ ms; 而在A-SEBF方法下, 有99.24%的Coflow的完成时间小于10⁶ ms。结合Coflow大小的重尾分布特性, 不难得出A-SEBF在平均Coflow完成时间方面优于Aalo。

由于Coflow的完成时间实际上取决于其瓶颈流的完成时间, 不同的方法只是在不同场景下利用不同的策略来找出这种瓶颈流。为说明瓶颈流的完成快慢情况, 图 10给出了不同方法下Coflow中瓶颈流量大小与Coflow完成时间的散点图。其中, 横轴是瓶颈流的大小, 纵轴是Coflow的完成时间, 横纵轴都以对数刻度形式呈现。需要说明的是, 因为本文在对A-SEBF和Aalo方法进行测验时是假设Coflow大小信息不可知的, 图 10的结果不违背本文的先验知识不可知的场景。在测验结束后, 会记录每个Coflow的完成时间、总体数据量大小以及最长流的大小等信息。从以上结果可以看出, A-SEBF能够将Coflow中瓶颈流的完成时间置于Aalo和Varys之间。这证明了本文所提的A-SEBF调度机制具有较好的性能。

5 结束语

本文在先验知识未知的场景下, 提出一种近似最小有效瓶颈优先的Coflow调度机制A-SEBF。A-SEBF在决定各个Coflow优先级时兼顾Coflow大小和宽度2个因素, 从而加大Coflow调度优化的空间。通过Facebook公开的Coflow数据集, 对A-SEBF调度机制进行仿真分析。实验结果表明, 相较于当前先进的先验知识未知的Aalo调度器, A-SEBF调度机制在“最小化平均Coflow完成时间”方面有33.2%的性能提升; 相较于先验知识已知的Varys调度器, 仅有7.3%的性能损失。下一步将在真实集群环境下对本文提出的A-SEBF调度机制进行分布式优化与实现。