E-Aalo: 面向无先验知识Coflow的高效多级队列调度

施凌鹏 卢士达 刘云飞 李 静

1(国网上海市电力公司信息通信公司 上海 200072) 2(南京航空航天大学计算机科学与技术学院 江苏 南京 211106)

0 引 言

目前,为了提高资源利用率和大规模任务处理的效率,往往通过集群技术将大量多余闲置的计算机连接起来形成云数据中心。在云数据中心中,通常采用MapReduce[1]、Spark[2]等分布式并行计算框架来处理大规模的数据。由于采用了分布式计算框架,一个作业往往会被划分成多个子任务然后交给数据中心中的多台计算机来完成,在对子任务进行分发及子任务结果进行合并时,会产生大量的中间通信数据流。如果其中的某条数据流没能及时完成,依赖这条数据流结果的后续子任务将无法继续,最终导致作业的完成时间延长[3]。文献[4]表明这些中间数据通信流传输花费的时间平均占作业总完成时间的33%,最高可达50%。所以优化这些中间数据流的完成时间具有十分重要的意义。

目前的研究中,具有语义相关的一组通信数据流被称为Coflow[5]。Coflow是一组数据流(flow)的集合,以MapReduce并行计算框架为例,Map映射阶段需要对作业的任务进行划分和分发(shuffle),会产生中间通信数据流,Reduce归并阶段需要读取Map阶段处理完成后的中间结果,也会产生中间通信数据流。为了提高云数据中心的性能,提高其中作业的完成时间,需要对Coflow的完成时间(Coflow Completion Time, CCT)进行优化,而不是对单个数据通信流的完成时间(Flow Completion Time, FCT)进行优化。因为对于一个网络,只有当此阶段的所有流都完成,这个阶段的通信才算真正完成,才可以进行下一个阶段的任务。目前的一些研究者在改进降低FCT的同时,忽略了应用程序级别的要求,例如方法PDQ[6]和pFabric[7],往往不能做到网络资源的最优调度。而Coflow抽象则可以通过网络公开应用程序级别的语义进行弥补,文献[8-9]指出这种语义相关的抽象可以提高计算平台的性能。但是目前Coflow调度方法也存在一定的缺陷,目前最优方法Varys[10]由于需要额外的先验知识而导致其实用性较差;Aalo[11]无需先验知识但仍存在可以优化的闲置空间和可利用的端口信息。

对目前Coflow调度的主流方法进行介绍,然后分析目前主流方法存在的实用性不强和Coflow平均完成时间过高的缺陷,并提出一种面向无先验知识Coflow的高效多级队列调度E-Aalo。通过Coflow流量放置策略选择所需传输数据最小且负载最小的接收节点来减小Coflow的发送量,并对现有Aalo方法中的多级队列调度存在的闲置空间通过提前调度低优先级队列中流量进行优化来降低Coflow调度的CCT。最后基于Facebook的MapReduce公开数据集和CoflowSim框架与现有方法进行对比验证。

1 相关工作

为了提高云数据中心应用的性能,对流量进行调度的方法从优化的对象上主要可以分为两类:(1) 面向单个数据流(single flow),优化目标是最小化其FCT,主要的研究工作包括PDQ[6]、pFabric[7]等,这一类方法往往因为是对单一数据流的调度,而无法做到整个网络资源的最优调度[12]。(2) 面向Coflow,优化目标是最小化CCT,主要的研究工作包括Varys[10]、Baraat[9]和Aalo[10]等。Varys[10]基于最小有效瓶颈优先的机制对Coflow进行调度,是目前先验知识已知情况下效果最好的方法。Baraar[9]采用FIFO(First In First Out)和公平共享机制提高带宽的利用率,进而减少平均CCT。Aalo[10]则是基于队列的多级调度器,为不同的Coflow分配不同的优先级来进行调度。目前主要的研究都是围绕面向Coflo优化的第二类问题展开,即最小化平均CCT。

对Coflow进行优化的方法可分为两类:(1) 拥有Coflow大小等先验知识的Coflow调度方法。这方面主要的调度效果最好的有Varys[10],它采用一种最小瓶颈优先(Smallest-Effective-Bottleneck-First,SEBF)机制对瓶颈较小的流优先调度,且控制不同内部流的发送速度,节省了端口的带宽并为其他Coflow腾出空间,可以使所有内部流的完成时间一致。其缺陷在于需要提前获取Coflow的大小等信息,而这一点往往只有在Coflow完成之后才能知晓,因此实用性不强。(2) 在没有Coflow先验信息的情况下对Coflow进行调度。Aalo[10]是目前最具代表性的方法之一,Aalo不需要提前知晓Coflow的流量大小信息,而是根据Coflow当前已经发送的字节数目来判断Coflow的大小,通过设置不同优先级的队列并按照优先级对Coflow进行调度。Aalo为每个队列设置阈值,当Coflow已发送的字节数超过阈值时降低Coflow的优先级。Aalo拥有较强的实用性,但是其缺陷在于只考虑了Coflow当前已发送的字节数目,而没有充分考虑其他有用的信息,如Coflow的宽度信息也是可以利用的,且多级队列也存在可以优化的闲置空间。对于较大一点的Coflow, Aalo由于缺乏先验知识而表现不如Varys。A-SEBF(Approximate Smallest-Effective-Bottleneck-First)[3]是在先验信息未知的情况下的一种近似最小有效瓶颈优先的Coflow调度机制,通过Coflow当前大小和宽度信息决定Coflow的调度信息,其核心思想是在一定程度上提高宽度大的Coflow的优先级,相比于Aalo,能够显著降低CCT,效果接近于利用先验知识的SEBF方法。

针对上面方法中存在的Coflow平均完成时间较高和可用性不强的问题,提出面向无先验知识Coflow的高效多级队列调度E-Aalo,在无先验知识的情况下通过基于计算节点状态的流量放置策略和优化多级队列调度中的闲置空间来降低Coflow的平均完成时间,并保证可用性。

2 研究背景

2.1 数据中心网络抽象模型

数据中心中包含大量的计算节点,为了研究的方便,可以将整个数据中心抽象为一个连接了所有计算机的无阻塞大型交换机。这个大型交换机的入口端口对应于服务器的出口链路,而出口端口则对应于服务器的入口链路[13-14]。通过这种抽象,该模型的优势在于只需要考虑入口端口和出口端口,便于对Coflow流量的调度进行分析,且在简单且全平分带宽拓扑结构下具有很高的实用性,目前已经被大量的研究者采纳。

数据中心抽象模型如图1所示。图1是由n个入口端口和n个出口端口组成的一个大型无阻塞交换机,即数据中心抽象模型,这些入口端口和出口端口是对数据中心中各个主机的流量输入和输出端口的抽象。在这个模型中,每个入口端口都可能会拥有一个或多个Coflow,这些Coflow将会从入口端口对应的服务器中发出,到达交换机,并通过抽象的无阻塞交换机最终被转发到出口端口中,这些出口端口对应接收节点的入口链路。每一个主机在一段时间内将会需要调度多个Coflow,所以图1中入口端口的最左边使用一个虚拟的队列用于存放到达的需要调度的Coflow。

图1 数据中心抽象模型

2.2 Coflow调度目标和相关定义

式中:每个Coflow的完成时间是其所包含的flow中完成时间最长的flow的完成时间。那么Coflow调度的目标如式(2)所示。

(2)

后续叙述中使用的变量定义如表1所示。

表1 相关参数及定义

3 E-Aalo调度

3.1 E-Aalo总体架构

E-Aalo架构如图2所示,主要包括全局协调器和本地守护进程两个部分。

图2 面向无先验知识Coflow的高效多级队列调度整体框架

(1) 全局协调器。全局协调器监测每个作业是否产生Coflow,对产生Coflow的作业利用Coflow流量放置策略,筛选合适的计算节点放置每个Coflow中的流量并生成放置方案,然后通知发送节点将Coflow中的流量发送到接收节点。同时,全局协调器还需接收发送节点发送来的每个Coflow已发送的数据流大小信息,根据这些信息确定不同Coflow的优先级并发送给本地守护进程。再对当前多级队列调度中可能产生的闲置空间进行分析,若当前最高优先级队列中只有一个Coflow且只使用部分发送端口,此时出现端口闲置空间,则提前启动低优先级队列中的Coflow流量调度来降低CCT。

(2) 本地守护进程。本地守护进程主要负责接收全局协调器发送来的Coflow优先级信息,然后在本地的多级队列中对Coflow进行调度。多级队列内部使用FIFO方式进行调度,不同队列之间使用加权公平队列调度方式。此外,本地的守护进程还需要将本计算节点中每个Coflow已发送的数据量信息发送给全局协调器,以便全局协调器可以及时调整Coflow的优先级。

全局协调器负责分析Coflow的发送位置和Coflow的调度优先级,本地守护进程负责进行Coflow流量的发送并将已经发送的Coflow信息通知全局协调器,帮助全局协调器进行优先级的分析。全局协调器和本地守护进程相互合作完成Coflow的调度。

3.2 基于计算节点状态的流量放置策略

目前A-SEBF、Aalo等方法只考虑利用Coflow到达之后的优化调度来降低CCT,但忽略了Coflow中流量的放置问题。而云数据中心中的作业往往被划分成多个子任务进行处理,每个子任务将被分派放置到不同的主机上执行,相应的数据也被传输到执行任务的主机节点上,带来更多的数据流量传输,也导致更大的开销[15-16]。若该主机上原本就存在相应的数据(云数据中心的HDFS文件系统一般都具有冗余备份,即文件的数据块可能存在于多台不同的主机上),就可避免额外的数据传输开销。因此,对Coflow中的流量进行不同的放置可对子任务在不同的主机上进行分配,而合理的分配也将会减少数据的传输量,降低时间开销,提高云数据中心的性能[17-18]。

Coflow中流量放置策略即是对一道作业在云数据中心选择不同的计算主机来执行其子任务,选择时需要考虑该计算节点的状态:是否已经拥有执行任务所需要的数据和该计算节点的网络负载情况。

Coflow的放置策略如式(3)所示。

(4)

算法1Coflow流量放置选择

输入:集合Q1,Q2,…,Qk对应Cn的k个数据流。

输出:Cn的放置方案M1,M2,…,Mk对应的k个数据量的放置方案。

1. for allifrom 1 tokdo

2. for alljfrom 1 tomdo

4.Qi.push(j)

//将合适的节点j放入数据流i对应的集合中

5. end

6. end

7. end

8. for allifrom 1 tokdo

9. for alljinQido

11. end

12. end

13. returnM1,M2,…,Mk

流量放置策略是在Coflow流量进行发送之前的一个优化操作,之前的方法[10-11]没有在Coflow流量发送并进行调度之前对流量的目标节点进行筛选,而是选择直接将流量发送到随机的节点上,很容易造成节点的堵塞,导致Coflow调度的平均CCT时间加长。而通过判断目标节点上是否存在Coflow流量的数据以及目标节点的当前网络负载情况,可以为Coflow中流量的调度选择出最合适的目标节点。如果此时目标节点已经拥有Coflow将要传输的流量数据,可以避免额外数据的传输,将网络资源空出给其他流量进行传输。目标节点在处理完计算任务之后需要将数据回传,如果此时目标节点的网络负载较小,那么也会加快回传完成的速度,所以通过计算节点状态来选择合适的目标节点可以相比之前的方法进一步降低Coflow调度的平均CCT。

3.3 优化闲置空间的多级队列调度

除了流量放置外,Coflow的流量调度也是影响CCT的重要环节。Coflow的放置策略可以选择合适的计算节点,这些节点在执行任务时,往往要处理来自多个Coflow的流量,这些流量可能同时到达,也可能先后到达,如何对这些Coflow流量进行调度同样会对CCT造成重要影响。其中,Varys方法对瓶颈因子最小的Coflow流量进行优先调度,本质上是对CCT最小的Coflow进行优先调度来降低CCT;Aalo方法在先验未知的情况下通过设置多个优先级队列,并根据Coflow已发送的数据量大小来决定Coflow的优先级进行调度;而A-SEBF方法对Varys中的瓶颈因子和Coflow宽度信息进行改进。A-SEBF和Aalo方法中都使用了优先级队列,但是其中的考虑相对简单,在复杂情况下仍然存在一定的改进空间,因此提出一种改进的高效多级队列调度方法。

3.3.1调度过程中的闲置空间分析

以图3为例,图3中一共包含了3个Coflow,分别为C1(灰色)、C2(白色)、C3(黑色),C1的大小为2,只包含一条数据流;C2大小为7,包含2条数据流;C3大小为3,包含一条数据流;C2和C3同时到达,C1在C2之后到达。这里假设只存在3个端口,每个入口端口的左边存在三个队列,分别对应发送目的端口,例如:入口端口1中的C3在第一个队列中,表示它将发送3个单位的数据到出口端口1中;C2在第三个队列中,表示要发送3个单位的数据到出口端口3中。

图3 数据中心流量

在Varys方法中,采用的是最小瓶颈优先,采用Varys的调度情况如图4所示,C3的完成时间为3,C2的完成时间为6,C1的完成时间为2,此时的平均CCT为(3+2+6)/3≈3.66,这是理想状态下Coflow调度的最优调度结果。

图4 Varys方法的调度情况

在Aalo方法中,根据Coflow已发送数据量大小设置Coflow的优先级,由于例子中的Coflow大小比较小,所以这里假设多级队列的阈值分别为1、2、4、8等。采用Aalo的调度情况如图5所示,在Aalo中按照优先级队列对Coflow进行调度,优先级高的队列将会被优先调度,队列内部采取FIFO策略,因此当高优先级队列中的Coflow的发送量达到阈值时将会被下放到低优先级队列中,只有高优先级队列中的Coflow调度完之后才会调度低优先级队列中的Coflow。从图5中可以看出这样会导致端口发送的时间段内存在一些闲置空间的情况,这些情况会导致CCT变大。此时的CCT为(8+4+4)/3≈5.33。

图5 Aalo方法调度情况

3.3.2优化调度过程中的闲置空间

Aalo的多级队列调度方法根据Coflow已发送的数据量来决定Coflow的调度优先级,当高优先级队列中的Coflow的发送量达到阈值时将会被下放到低优先级队列中,只有高优先级队列中的Coflow调度完之后才会调度低优先级队列中的Coflow。通过分析发现,Aalo会在调度过程中存在一些闲置空间,即为了等待高优先级队列中一些Coflow流量传输的完成,会导致将要调度发送低优先级队列中的Coflow流量的端口处于停滞状态,必须要等待高优先级度列中的Coflow发送都超过队列的阈值时才会进一步调度低优先级队列中的Coflow流量,这种闲置空间无疑会导致Coflow的平均CCT增大。通过在这些停滞的端口上提前对低优先级队列中的Coflow流量进行调度,设置当端口发生闲置时主动去低优先级队列中提前调度Coflow,可以充分利用每个端口的网络资源,从而有效降低多级队列调度方法中Coflow的平均CCT。

对这种闲置空间进行改进,允许在依据优先级队列进行调度的过程中产生闲置空间时,提前启动低优先级队列中Coflow的调度,以此来充分利用闲置空间,降低Coflow的CCT,提高效率。提前开启低优先级队列中Coflow调度后,调度的情况如图6所示。

图6 E-Aalo调度情况

可以看出,产生闲置空间被用于调度C2,图6中星号标记的即为提前调度的Coflow流量,这种方法下,最终的CCT为(6+4+4)/3≈4.66,比Aalo降低了0.67。提前调度方式如图7所示。

图7 E-Aalo调度方式

图7中,C2和C3是同时到达的且在不同的端口,所以它们相当于在队列中并列。当第一个时间过去后,端口1和端口3都发送1个单位的流量,C2和C3由于不在同一端口,所以依然可以并列看待。当C1到达时,端口1开始调度C1,但是端口3此时并不需要调度C1的流量,此时如果按照Aalo和A-SEBF中的方法,端口3此时将被闲置,将会导致端口3中C2和C3的CCT变大,而此时如果在端口3提前调度较低一级队列中的C2,就可以显著减小CCT。具体来说,E-Aalo高效多级队列调度算法调度步骤如下:

(1) 全局协调器根据流量放置方案选择Coflow的合适的接收节点,通知Coflow的发送端,然后发送端会先将这些流量排入高优先级队列中,在同一级队列中通过FIFO方式调度。

(2) 每个发送端口先将高优先级队列中的Coflow进行调度,每个发送端口还需要将当前Coflow已经调度的流量信息发送到全局协调器,全局协调器对每个Coflow已经发送的数据量进行统计,如果Coflow的已发送数据量超过了当前优先级队列的阈值,则将Coflow下调到低一级优先级队列中,即降低该Coflow的优先级。

(3) 发送端口在选择队列中下一个Coflow进行调度时,如果其他的端口中的Coflow都已经被放置到下一级优先级队列中且其他发送端口存在闲置空间时,对下一个Coflow进行调度的同时,提前开启闲置端口的低一级优先级队列中的Coflow进行调度,充分利用闲置空间;其他端口中的低优先级队列中的Coflow调度方式和(2)中一样。

(4) 提前开启闲置端口的低一级优先级队列时,同样在同一级队列中使用FIFO方式进行调度,直到所有的Coflow调度完。

4 实验评估

为了评估提出的基于多级队列的Coflow调度机制的有效性,使用公开的Facebook数据集,通过和现有的先验已知Coflow调度方法Varys、先验未知Coflow调度方法Aalo、传统的FAIR方法进行对比,验证方法的有效性。所给调度方法目前是在Java语言实现的CoflowSim调度模拟器进行实验和评估,还未在真实的分布式集群环境对所给方法进行实现和实验评估,在真实的分布式集群环境对所给方法进行实现和实验评估是下一步的目标。

4.1 实验配置

CoflowSim是目前专门用于流级别的模拟器,用于实现和比较各种Coflow调度机制,且已经实现了多种先验知识和无先验知识情况下的Coflow调度方法,比如Varys、Aalo等,所以选择CoflowSim模拟工具进行实验验证。

CoflowSim调度模拟器上进行实验的部署环境为:Intel Xeon W-2102 CPU、32 GB内存,Ubuntu16.04操作系统和Java 1.8.0_181环境。在Eclipse中通过maven工具导入CoflowSim框架,由于CoflowSim模拟器内部已经对数据中心的抽象模型进行了建模和实现,同时实现了Aalo和Varys等CoflowSim调度算法,所以只需要使用Java语言实现所给调度方法并进行实验验证。

使用的数据集为Facebook提供的从现实世界中数据密集型应用程序合成的实际工作负载。原始的数据来自Facebook上3 000台150机架的MapReduce集群,合成后的数据包含526个Coflow,这些Coflow是在不同时刻到达。该数据集中的数据格式如图8所示。其中数据被压缩到了机架级别,Mapper的位置和Reducer的位置都是机架级别的,而机架的范围是0～149,即150台服务器。同一机架中的Mapper被组合成一个机架级别的Mapper,同一机架中的Reducer被组合成一个机架级别的Reducer。图8给出了一个Coflow实例,表明该Coflow ID为3,到达时间为13 122,一共有两个Mapper,位置分别是机架中的66和138号机架,一共1个Reducer,Reducer的位置在38号机架且需要接收的数据为4.0 MB。在本实验中,CoflowSim中模拟的每台服务器的端口的初始带宽为1 Gbit/s。

图8 数据集格式

在之前使用Facebook提供的数据集的研究中[19],可以发现其中大部分的Coflow的完成时间都在60 s之内,比例约占90%左右,所以数据集中大部分都是小型Coflow(能在60 s内完成),只有少量的大型Coflow,但是这些大型Coflow的传输数据量占总量的90%以上。

4.2 对比实验

E-Aalo调度主要包括Coflow流量放置和在端口闲置时提前调度低优先级队列流量,所以设置的实验主要包括:(1) E-Aalo方法和其他Coflow调度方法的CCT对比;(2) 使用Coflow流量放置策略和提前调度低优先级队列流量前后的效果对比。

设置的对比方法涉及Aalo[11]、Varys[12]和FS。Varys是在先验知识已知情况下的基于最小瓶颈优先(SEBF)的Coflow调度方法;Aalo是在先验未知情况下利用多级队列来调度Coflow的方法;FS(Fair Sharing)是根据流量数量对网络带宽进行平均分配的策略。比较的指标主要是Coflow的平均完成时间(Average CCT)。

4.2.1E-Aalo和其他方法的对比

图9给出了使用不同的Coflow调度方法得到的平均完成时间对比图。Varys调度完数据集中526个Coflows之后,平均完成时间CCT为28 528.46 ms,是所有对比方法中最好的,因为它可以根据已知的先验知识来进行最小瓶颈优先调度从而达到最优的结果;Aalo调度完526个Coflow之后的CCT为46 097.70 ms,Aalo根据目前已经发送的数据量来设置不同Coflow的优先级,而不是其中flow的优先级,导致多级队列在调度的时候存在一些可以进一步优化利用的闲置空间,所以其CCT相比Varys增加了61.58%;FS调度完526个Coflow之后的CCT为70 592.82 ms,它的效果是4种方法中最差的,CCT最高。E-Aalo方法调度完526个Coflow之后的CCT为40 437.61 ms,比Aalo降低了12.28%,因为E-Aalo方法对Coflow流量放置策略进行了优化,并将Aalo中多级队列调度中的闲置空间加以利用,从而降低CCT。

图9 4种调度方法的CCT

图10给出了4种不同方法每个Coflow的大小及其完成时间的散点图。可以看出,Varys方法调度的大部分的Coflow都出现在图中的左下方,大部分较小的Coflow的完成时间也较小,保证了Coflow调度的效率。FAIR中则出现了许多大小较小但是完成时间较大的点,所以FAIR方法的CCT通常并不理想,会高于其他方法。在Aalo方法中,通过多级队列调度方法可以保证基本不会出现FAIR中较小Coflow被延误而导致完成时间过大的情况,但是一些较大的Coflow的完成时间却会相应提高。在E-Aalo中,通过对多级队列调度过程中的闲置空间进行优化,可以降低部分较大Coflow的完成时间,且也可以加速一些较小Coflow的调度来降低整体的CCT。

图10 Coflow完成时间和Coflow大小的关系

图11给出了4种不同方法Coflow完成时间的累计分布函数曲线图。可以看出,FAIR方法的效果最差,在同一时间间隔内,其Coflow的完成率最低。Varys是先验知识下的最小瓶颈优先方法,效果最好,同一时间内的Coflow完成率最高。Aalo与E-Aalo接近,但E-Aalo对其进行了优化,故同一时间E-Aalo完成的Coflow率略高于Aalo,与Varys方法最接近。因此,方法E-Aalo的Coflow调度效果优于Aalo方法。

图11 Coflow完成时间的累计分布函数曲线

4.2.2E-Aalo自身的对比

图12给出了使用Coflow流量放置策略和提前调度低优先级队列流量前后的效果对比。E-Aalo方法其实是对Aalo多级队列的改进,通过加入流量放置策略和提前调度低优先级队列流量来优化CCT。可以看出,Aalo在数据集上的CCT为46 097.70 ms,使用上流量放置策略后CCT下降到44 046.3 ms,降低了4.45%;E-Aalo使用流量放置策略加上改进的多级队列调度后,CCT下降为40 437.61 ms,比使用流量放置的Aalo方法下降了8.19%。

所给调度方法主要适用于集群中存在大量分布式计算任务且先验知识未知情况下的Coflow调度。所给方法是针对无先验知识下Coflow调度方法Aalo进行的改进。但是暂时只是在Java语言的CoflowSim框架下进行了模拟实验。然后基于Facebook的Coflow公开数据集对所给方法的有效性进行实验验证。

5 结 语

由于Varys方法只能应用于先验知识已知的情况导致实用性较差,且Aalo方法存在一些可以改进的缺陷,提出一种面向无先验知识Coflow的高效多级队列调度E-Aalo。首先,基于计算节点的状态信息选择合适的节点对流量进行放置来减少部分数据的传输,进而降低Coflow的CCT。然后,通过对Aalo方法中的多级队列调度的闲置空间进行改进利用,在闲置时提前调度低优先级的流量来优化Coflow的CCT。最后,利用Facebook的公开数据集和CoflowSim框架进行对比验证。E-Aalo在CCT上比Aalo方法下降了12.28%,优于Aalo方法。由于CoflowSim平台功能比较简单,接下来的工作将考虑在仿真模型功能更强的CloudSim平台或真实环境中实现提出的E-Aalo调度。