层次化计算范式数据中心任务调度方法

胡 荣，马军生

(1.吉利学院 智能科技学院，四川 成都 641402；2.国防科技大学 信息通信学院，湖北 武汉 430000)

0 引 言

近年来，网络带宽不断增长、通信成本不断下降，分布式应用产生的数据量越来越大，这一现象开始得到研究人员的关注[1,2]。在这些应用中，如果源节点将原始数据直接发送给服务器，会给网络基础设施和服务器带来极大压力。为了缓解这一问题，一些研究[3-5]提出，可以在网络中部署中间处理节点(intermediate processing nodes，IPNs)对原始数据做预处理，如压缩、格式转换、去噪等，再由中间处理节点将处理后的数据发送给服务器。在实际的大规模分布式应用中，出于分而治之或负载均衡等方面的考虑，也常常部署一些性能较高的中间处理节点，对源节点产生的原始数据进行预处理。本文将分布式应用的这种分层的处理模式命名为层次化计算范式。

需要注意的是，分布式应用中的一次任务通常包含多个子任务。比如，在层次化计算范式中，每个源节点产生数据并经由IPN中继到目标节点的过程，都可以视为一个子任务。在分布式应用中，这些子任务的预期完成时长和截止时间可能各不相同[6]，也很难保证所有的子任务都可以在截止时间之前完成[7]。与已有的研究保持一致[8]，本文试图通过最小化所有子任务的总延迟来优化分布式应用的响应时间。

如图1所示，在层次化计算范式中，某个子任务的完成时长由3部分组成：子任务从源节点出发，经由IPN到达目标节点引入的路由时延；子任务在IPN上的处理时长；子任务在IPN上等待处理时，引入的排队时长。为了简便，本文将处理时长和排队时长之和称为处置时长。注意到，子任务的处理时长和路由时延依赖于子任务的分配策略，排队时长则依赖于IPN的调度策略。子任务的分配策略和调度策略相互影响，导致路由时延、排队时长和处理时长的联合优化并非易事。

图1 层次化计算范式下的子任务完成时长

大规模IDC在不同维度、不同层面上存在异构性。比如，为了满足不同应用的资源需求，IDC中往往部署有不同配置的主机；同时，IDC往往是增量化建设的，不同批次主机的配置也有不同。虚拟化IDC中的混布技术将资源需求不同的应用(如在线应用和离线应用)部署在一起，因而应用之间也存在异构性。因此层次化计算范式中的中间处理节点往往是异构的，它们的资源总量和处理能力各不相同。这种配置异构性使得层次化计算范式中的总延迟最小化变得更加困难。比如，将子任务分配给处理能力最强的IPN，可以使得预期处理时长最小，但可能引入很大的路由时延；而将子任务分配给路由时延最小的IPN，则可能会引入较长的处理时长；此外，如果子任务在IPN节点之间分配不均，也可能导致高负载IPN上的排队时长过大。

当前，针对路由策略的研究[9,10]和针对调度策略的研究[11]已有很多。广义来说，路由策略研究的是数据(子任务)如何分配给服务节点；在子任务分配过程中，路由策略通常着眼于路由时延优化，而不关注子任务在服务节点上的处置时长。调度策略研究的是服务节点处理数据(执行子任务)的次序；在决定子任务的执行次序时，调度策略通常仅着眼于排队时长优化，而不关注其它。近年来，越来越多的研究开始关注路由策略和调度策略之间的相互关系[12-14]。但是，极少有研究关注层次化计算范式下的路由策略和调度策略的相互影响。

层次化计算范式近年来已经广泛出现在大规模分布式应用中，比如分布式信息检索或智慧城市。层次化计算范式是一个新兴且重要的系统架构，异构层次化计算范式下分布式应用的延迟最小化问题很值得研究。本文试图回答以下问题：如何在异构层次化计算范式下，最小化分布式应用的总延迟?针对层次化计算范式下路由时延和处置时长的联合优化需求，并考虑了大规模应用在线运行时的实际情况，本文设计了一种延迟感知的Power-of-D任务调度算法(tardiness-aware power-of-dalgorithm，TPD)。最后，基于真实系统场景对上述算法进行了性能评估，评估结果肯定了其有效性。

1 初始方案及其启示

本小节给出了层次化计算范式下总延迟最小化的问题定义。表1总结了问题定义中所使用的符号及含义。

表1 本文符号及定义

某个子任务m在源节点产生后，会被中继到一个且仅被中继到一个资源总量可以满足此子任务的IPN节点k上，即Qk≥qm。 子任务到达IPN后，若该IPN的剩余资源充足，则可以并发处理多个子任务；若剩余资源不足，则到达的子任务会在优先级队列中等候处理。这里假设IPN上的优先级队列没有长度限制。此外，本文考虑子任务级别的调度策略，所以假设子任务的执行过程不可被打断。

基于上述描述，本问题可以定义如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

2 任务调度策略

在线运行阶段，借鉴已有研究经验，假设子任务按照泊松过程动态产生——这也是在线活动建模的常用方法。如算法1所示，在线任务调度是以事件驱动模式进行的。具体而言，定期采集分布式应用的状态，并根据应用状态进行任务调度。对于每个IPN节点k，子任务分发器(dispatcher)定期地采集系统中的传输时延ωik和ωkj(第4行)以及IPN的负载情况(第5行)。如果一个新的子任务m产生，分发器会选择一个IPN节点k(第7行)，并将子任务m分发给k(第8行)。最后，IPN节点k按照一定的优先级对其上的子任务进行处理(第9行)。

算法1:在线任务调度流程

(1)repeat

(2) WaitForEvent(&event);

(3)ifevent isCollectInformationthen

(4) CollectLatency();

(5) CollectWorkload();

(6)elseifevent isSubTaskGenerationthen

(7) Select an IPNkto process the new sub-taskm;

(8) Dispatch sub-taskmto IPNk;

(9) IPNkschedules and processes sub-taskm;

(10)untilnomoresub-tasksaregenerated;

在实际的大规模分布式应用中，系统状态通常是定期收集的，且将子任务从源节点路由到IPN节点也会引入时延。因而，采集到的系统状态数据可能是过时的、近似的，甚至还会有错误存在。在这种情况下，不能假设在线运行过程中所采集到的系统状态数据是实时的、准确的。已有研究人员发现，将任务直接分发给看起来负载最轻的服务器上，可能导致系统性能显著下降。因而，不能仅仅基于采集到的系统状态数据进行任务调度。本节将超市模型(supermarket model)中的Power-of-D范式扩展到异构层次化计算范式中，并设计了延迟感知的Power-of-D算法(tardiness-aware power-of-D，TPD)用于在线任务调度。

2.1 超市模型与Power-of-D范式

超市模型考虑的是这样一个场景：顾客依次到达超市，而后加入到某个服务员前的队列中；顾客的到达模型，是速率为n·λ(0<λ<1) 的泊松流，其中n是服务员的数量;所有服务员的服务速度相同；服务员按照先到先服务(first come first service，FCFS)的原则，依次服务其队列中的顾客。超市模型旨在将顾客分配到最佳的服务员，使得顾客的期望滞留时长(expected sojourn time)最短。若将子任务视为顾客，将IPN视为服务员，子任务调度与超市模型非常类似。

超市模型的一个典型解决方案是Power-of-D范式。在Power-of-D范式中，每个新来的顾客按照均等概率随机选取d个服务员，而后在选取的服务员中选择顾客队列最短的那个。有文献[11]证明，d=2时用户的平均滞留时间比起d=1时有指数级的改进，而d=3时则仅比d=2时有常数级的改进。因此，d通常取值为2，Power-of-D范式也通常被称为Power-of-Two。Power-of-D在实际的大规模系统中成效显著，是因为其在选择服务员时引入了随机性。这启发作者在任务调度中也增加随机因素。

2.2 挑 战

尽管在线任务调度与超市模型相似，两者之间还是有一些关键性的区别。特别的，在层次化计算范式下应用Power-of-D范式面临以下挑战。

第一，是负载不均衡。在超市模型中，所有服务员的服务能力都是相同的，而IPN节点的资源总量和处理速度则各不相同。在异构系统中，Power-of-D的表现比在同构系统中的表现要差。这是因为，经典的Power-of-D总是按照均等概率选择服务员，这会增加弱服务能力的IPN上子任务的排队时长，进而增大异构系统中顾客的滞留时间。此外，Power-of-D在异构系统中对d的取值敏感，d取值不合适会导致顾客(负载)在服务员(服务节点)上分布不均衡，这也会增长顾客的滞留时间。

第二，是最优服务员的选取。经典的Power-of-D范式中，每个顾客选择队列最短的服务员，以最小化该顾客的期望滞留时间(即层次化计算范式场景中的处置时长)。然而在层次化计算范式中，较短的队列并不一定意味着较短的排队时长，因为少量的长子任务可以占用IPN的大量资源和处理能力。此外，层次化计算范式中，不仅关注处置时长还关注路由时延，而超市模型则不关注路由时延(即顾客加入某个服务员的队列所需的开销)。

第三，是子任务的调度策略。Power-of-D只关注如何将顾客分配给合适的服务员，服务员则简单地按照FCFS的规则提供服务。因为FCFS规则中的优先级机制过于简单(先到达的顾客的优先级总是比后到达的顾客要高)，所以在优化层次化计算范式中的子任务延迟时是低效的。比如，即使某个子任务马上就要超过其截止时间了，它还是需要在队列中等待它前面的子任务一一得到处理，这会增加任务的总延迟和分布式应用的响应时间。

2.3 应对挑战

(10)

表象处理速度表征了这样一种现象：由于路由时延的存在，IPN节点的处理速度看起来变得比其实际处理速度vk慢；某个IPN节点引入的路由时延越长，子任务经由该IPN处理并转发所需的时间就越长，因而该节点的处理速度看起来就越慢。注意到，网络中的路由时延会不断变化，每个IPN节点的表象处理速度v′k也需要相应的不断更新。

通过定义表象处理速度，IPN节点k的抽样概率可以表达为

(11)

式中：IPN节点k的抽样概率与其表象处理速度v′k成正比。这样，具有较高处理速度和较低路由时延的IPN节点被选中的机会就越大，避免了在低配置IPN节点上发生拥塞。

此外，为了保证负载均衡，还需要仔细计算d值。异构超市模型中可以保证负载均衡的d值的紧下界(tight lower bound)和紧上界(tight upper bound)。其中，d值的下界表达为

dlower=(1-ε)·f(α,β)

(12)

上界表达为

dupper=(1+ε)·f(α,β)

(13)

在上述等式中，ε∈[0,1]

(14)

为了选择最佳的IPN节点，在抽样得到的d个候选IPN中，选择符合如下条件的IPN节点k来服务子任务m

(15)

式中：Queuek表示IPN节点k上的优先级队列中的子任务集合。这样，某个IPN节点负载越轻、处理速度越快、传输时延越短，子任务就越倾向于选择它。通过选择这样的IPN节点，子任务的预期完成时长最短。

至于子任务调度策略，IPN从其队列中优先选择处理符合如下条件的子任务i

(16)

2.4 算法流程

将前面的设计综合起来，设计了延迟感知的Power-of-D算法(tardiness-aware power-of-D，TPD)。该算法的工作流程如算法2所示。

算法2：算法流程

(6) Calculatedaccording to Formula (12) and (13);

(7) Sampledcandidates with probability distribution F;

(8) Routemto the IPNksatisfying Formula (15);

(9) IPNkschedules and processes sub-taskmaccording to Formula (16);

可以看到，算法2是一个线性时间算法，算法的时间复杂度与IPN节点的数量成正比，即O(|K|)。 注意到，在实际系统中，IPN节点的数量通常较小，所以TPD算法可以高效工作。

3 性能评估

前面提到，层次化计算范式已经出现在诸多应用场景中，如分布式检索、智慧城市等。本节在平安校园场景中对设计的方案进行评估。平安校园场景的传输时延相对较小且较稳定，因此子任务的处置时长占据了绝大部分完成时长。

本节在实际场景中对本文提出的解决方案进行评估，并将其与其它3种算法进行了对比。在评估过程中，试图回答以下问题：第一，TPD能否有效优化分布式应用的总延迟？第二，TPD的性能与理论上的最优方案之间的差距有多大？

性能评估的主要结果总结如下。

延迟优化：评估结果表明，TPD可以显著降低不同模式的子任务的平均路由时延、平均处置时长及总延迟。因而，TPD可以有效降低分布式应用的响应时间。

最优性差距：为了明确TPD与理论上的最优性能之间的差距，将其与离线最优结果进行对比，并定义了最优性差距指标。在实际场景下，TPD的最优性差距比其它策略要小。上述结果肯定了TPD在在线调度场景中的有效性。

3.1 实验设定

某平安校园系统部署在某大型校园中，该校园面积超过3 000 000平方米。校园中共部署有超过600个摄像头(源节点)、12个监控点(IPN节点)以及1个指挥中心(目标节点)。如图2所示，校园中共有12个重点部位，如博物馆、图书馆、教学楼等。为了更好监控这些重点部位的情况，每个重点部位都部署有一个监控点。特别的，编号为12的位置为该校主楼，主楼也是指挥中心所在的位置。每个监控点都部署有一台网络视频录像机(network video recorder)。摄像头将视频片段和照片等发送到其中一台网络视频录像机上，网络视频录像机则将这些视频片段和照片进行转码，并转发给指挥中心。在指挥中心，这些视频将被展示在大屏幕上，并被进一步分析(比如火情监控或入侵检测等)。

图2 平安校园系统平面图

在该平安校园系统中，具体考虑一个入侵检测应用。摄像头会自动检测并拍摄移动物体，拍摄的视频帧率为30 fps。根据大型的视频分析数据集可知，时长为5 s到15 s之间的视频片段足以检测入侵。因此，在实验中，假设视频片段的长度为5 s到15 s之间(即150帧到450帧之间)。由于增量化部署策略，平安校园系统中的网络视频录像机共有两代，其中有8台为高性能网络视频录像机，4台为低性能网络视频录像机。高性能网络视频录像机可以最多并行转码64路视频片段，每路的平均转码速率为1200 fps；低性能网络视频录像机可以最多并行转码32路视频片段，每路的平均转码速率为600 fps。经过实地测量，该平安校园中，任意两个地点之间的路由时延在0.005 s到0.015 s之间。因此，在实验中，将路由时延设定为lmk∈[0.005,0.03] s， 并假设路由时延与转发路径的长度成正比。

3.2 算法性能

接下来验证TPD方法的有效性。

在平安校园场景中，考虑两种子任务产生模式：稳定模式和突发模式。稳定模式描述了子任务产生的通常状态，即子任务以稳定地低速率产生。突发模式则描述了一些突发的子任务，即子任务的产生速率突然增大，但仅持续了较短时间。在稳定模式下，设定：子任务数M=10000，子任务产生速率λ=0.7。在突发模式下，设定：子任务数M=600，子任务产生速率λ=5。每种子任务产生模式均运行100次。

性能评估中，参与比较的算法如下所列。特别的，PoD、CRO和RND这3种算法中，IPN按照EDD(earliest due date first)策略调度其上的子任务。为了充分验证算法性能，性能评估中，每种算法分别模拟运行100次。

TPD：第3节设计的延迟感知的Power-of-D算法。

仅考虑处置时间优化(Power-of-D，PoD)：经典的Power-of-Two策略，即以均等概率随机选取两个IPN，而后将新的子任务分配给队列较短的IPN上。Power-of-Two是一个典型的以最小化处置时间为目标的策略。

仅考虑路由时延优化(consider routing only，CRO)：一个在线版本的仅考虑路由时延优化策略，先以均等概率随机选取两个IPN节点，而后将新子任务分发到具有较短路由时延的IPN上。

随机(Random，RND)：每次将新子任务分发到一个随机的IPN。

首先比较了处置时长。平安校园场景下，图3和图4分别比较了不同算法在入侵检测应用中，稳定模式和突发模式下的子任务的平均处置时长。可以看到，TPD明显优于其它算法，因为TPD在任务调度中考虑了处置时长优化。然而，PoD尽管也考虑了处置时长的因素，但是其表现与CRO相差无几。这肯定了第2.2节的讨论，Power-of-D范式在异构系统中是低效的。

图3 稳定模式下的平均处置时长

图4 突发模式下的平均处置时长

其次比较了路由时延。图5及图6分别展示了平安校园场景中不同模式下的子任务的平均路由时延。可以看到，TPD和CRO在两种子任务模式下均优于其它方案。这是因为在选择最优的IPN时，由于方程式(12)和方程式(13)，TPD通常会抽样到多于2个备选IPN。因而，TPD比CRO更有可能找到更短的路由路径，进而产生更短的路由时延。

图5 稳定模式下的平均路由时延

图6 突发模式下的平均路由时延

最后比较了总延迟及与最优性差距。如图7和图8所示，TPD下子任务的总延迟最小。这说明TPD擅长调度不同模式的子任务。特别的，为了验证TPD算法能否有效优化分布式应用的总延迟，还定义了最优性差距Gap来量化算法的最优性

(17)

式中：T是使用上述算法进行任务调度时的总延迟，TLB是总延迟的下界。在线场景中，对于产生的每个子任务，都遍历所有的IPN以确定全局最优的IPN和全局最优的子任务处理顺序，进而得到总延迟的下界TLB。如图9和图10所示，TPD的最优性差距在任何情况下都比其它策略要小。上述结果肯定了TPD在在线调度场景中的有效性。

图7 稳定模式下的总延迟

图8 突发模式下的总延迟

图9 稳定模式下的最优性差距

图10 突发模式下的最优性差距

4 结束语

本文研究了分布式应用中的任务调度问题。近年来，互联网、移动互联网、物联网飞速发展，分布式应用产生的数据体量越来越大、异构性越来越强。所以，原始数据从源节点发出后，需要在中间处理节点上进行预处理，再由中间处理节点将整合处理后的数据转发给目标节点。在这种层次化计算范式下，任务完成时间受到网络资源(路由时延)和计算资源(中间节点的计算能力、处理能力)的双重约束，受到子任务的分配策略和调度策略的双重影响。

本文致力于在异构层次化计算范式下，优化分布式应用的总延迟。具体地，设计了延迟感知的Power-of-D算法用于子任务的在线分发及调度，该算法将经典的Power-of-D范式扩展到了层次化计算范式中，可以实现任务路由时延、处理时长和排队时长的联合优化。最后，基于真实系统场景，对本文提出的解决方案进行了评估，评估结果肯定了本方案的有效性。