节点实时性能自适应的集群资源分配算法*

胡亚红，吴寅超，朱正东

(1. 浙江工业大学 计算机科学与技术学院(软件学院)， 浙江 杭州 310023； 2. 西安交通大学 计算机科学与技术学院， 陕西 西安 710049)

Apache Spark是高性能的大数据处理框架，能够高效地处理批数据和流式数据[1-3]。但Spark默认的资源分配算法仅匹配作业需求和节点的资源情况，不能够保证为用户作业分配到最优资源。资源分配和作业调度属于NP-hard问题[4]，是当前的研究热点。综合考虑集群资源的异构性、节点负载的实时变化和用户作业不同特点的资源分配算法，能够有效提高集群性能、缩短作业的完成时间。

为了解决Spark在进行资源分配时未结合节点硬件性能的问题，Xu等提出了一个考虑集群资源属性和作业特性的启发式算法，能够为作业分配到合适的资源[5]。

胡亚红等提出的基于节点优先级的Spark动态自适应调度算法[6](Spark dynamic adaptive scheduling algorithm, SDASA)则是为了综合处理集群的异构性和节点的实时性能。该算法中，节点的性能使用优先级来度量，节点的实时优先级根据节点的资源使用情况等工作状态进行动态计算。

为保证所有作业都能够在截止时间内完成，文献[7]介绍了一个考虑作业价值密度和完成时间限制的硬实时调度算法截止时间及价值密度感知(deadline and value density aware, DVDA)算法[7]。但DVDA算法没有考虑集群中节点的实时资源使用状况。

针对电力供应受限的系统，文献[8]分析了常用基于价值的任务调度方法的不足，提出需要在不同的电力供应状态下选择不同的能源分配方案，并在此基础上，提出了基于价值的能耗感知启发式任务调度算法。

为减少存储设备异构的集群中作业的执行时间，文献[9]提出的任务调度策略根据存储类型获得对应存储设备的读取速度，同时考虑数据存储的位置，以完成任务优先级的计算[9]。

充分利用具有较高读写速度的缓存能够缩短数据的读写时间，加快用户作业的完成。文献[10]描述了针对数据密集型任务的并行调度算法。该算法在考虑数据本地性、相关性和负载均衡的条件下，最小化任务的完成时间。此文献对数据密集型负载进行了分析，但没有讨论其他类型负载的情况。

启发式算法是解决调度问题的常用算法，Yu等提出使用野草算法(invasive weed optimization，IWO)完成异构集群中的任务调度，目标是最小化任务的完成时间。其中，IWO用于为每一个子作业分配优先级，最早完成时间 (earliest finish time，EFT)算法则为子作业分配最优的运行节点[11]。

由于资源分配问题的复杂性，越来越多的研究采用了机器学习的方法。文献[12]讨论了包含CPU-GPU的异构集群中多个任务共用GPU的任务调度问题。基于GPU上任务的细粒度划分和任务间的关系，作者提出了基于深度强化学习和神经协同过滤的两阶段任务调度方法，给各任务分配最合适的节点[12]。

Hu 等在研究中发现，为用户作业分配过多的资源不但会增加资源间的通信开销，使得作业的完成时间 (job completion time，JCT) 不降反增，而且还造成其他作业无法获得足够资源[13]。为了解决资源过度分配问题，首先利用深度神经网络(deep neural network，DNN) 寻找每个作业的最优集群配置；在获得作业最优配置后，使用短作业优化算法为作业预分配集群资源；之后使用启发式算法以平衡多个作业之间的资源分配，从而达到批作业完成时间最短的优化目标。

Spark默认资源调度方法没有充分考虑计算资源和网络资源之间的均衡。如果集群用于处理网络密集型作业，则可能需要在节点间传输大量的数据，从而导致集群性能下降。针对该问题，Du等提出了一种任务完成时间感知的作业调度优化方法[14]。该算法首先进行任务完成时间的预测。再利用得到的任务执行时间，从非本地任务调度和网络的传输时间两方面进行优化。

目前常用的集群资源分配算法没有综合考虑节点的实时性能和待运行作业的特点，使得一些节点的性能优势无法完全发挥，而部分作业的执行时间也没有达到最优。下面以WordCount负载分别运行于配置不同的三个节点为例说明上述问题。节点配置如表1所示。

表1 WordCount运行时间对比实验配置

节点1和节点2的区别在于磁盘的性能，节点2的I/O性能优于节点1。节点2和节点3的CPU速度不同，节点2的CPU性能更好。众所周知，WordCount负载对于节点的CPU性能较为敏感。对比相同的WordCount负载在3个节点的执行时间，可以清楚地看出节点3的运行时间比节点2的长了72.11%，主要原因就是节点3的CPU性能较差。而WordCount在节点1和2的运行时间仅有2%的差别，也说明了WordCount对节点的I/O性能不敏感。因此为用户作业选择适合其特点的节点非常有必要。

目前考虑节点与作业类型匹配的研究不是很多。文献[15]考虑了节点的任务执行特点，使用作业和节点的匹配差异程度作为资源分配的依据。该文中：作业的类型由用户提供，分为计算密集型和内存密集型。节点的负载由其CPU分量、内存分量和系统其他分量表示。资源分配的基本思想是将CPU利用率低、内存利用率高的节点分配给计算密集型作业；将内存利用率低的节点分配给计算密集型作业。使用该算法时，若是用户对作业不够了解，则其指定的作业类型会不准确。另外，节点负载的影响分量考虑得不是非常全面。它主要考虑的是CPU分量、内存分量，其他如磁盘容量等统一归属于其他分量，因而不能对除了CPU和内存以外的分量进行更为有效的处理。

本文提出的节点实时性能自适应的集群资源分配算法(node real-time performance adaptive cluster resource scheduling algorithm，NPARSA) 旨在综合考虑节点的实时处理性能优先级和用户作业的特点，为作业分配最适合的节点，从而缩短作业运行时间，提升集群的性能。

1 节点性能评价及资源调度算法

NPARSA根据用户作业的类型自适应地进行节点优先级评价指标权值的选择，从而计算出各个节点处理此作业的性能优先级。

1.1 用户作业类型的判定

CPU密集型作业和内存密集型作业是常见类型的用户作业，它们对于集群有着不同的资源需求。作业的类型可以使用运行作业需要的CPU核数和内存数量进行判定，式(1) 给出了作业类型的判定方法。

(1)

作业的类型使用变量J进行判定。Mr是用户要求为作业提供的内存数量，而用户要求提供给作业的CPU核数用变量Cr表示。为了选择合理的J阈值以区分作业类型，本文进行了大量的实验。实验分别使用Spark默认调度算法和NPARSA运行相同的作业，计算出在不同J阈值下NPARSA能够产生的系统性能提升百分比，实验结果见表2。

表2 不同J阈值下集群性能提升效果

对表2进行分析发现，当J阈值为1.1时，NPARSA能够得到最好的效果。因此，将作业类型J的阈值定为1.1。当一个作业的J值大于1.1时，判定该作业为内存密集型，否则判定为CPU密集型作业。NPARSA将根据作业的类型自适应地选择节点优先级计算时需要的权值。

1.2 节点性能优先级的评价

异构集群中的节点性能差别较大，有些节点适合处理CPU密集型作业，有些则适合运行内存密集型作业。因此根据当前作业的类型自适应地分析节点性能很有必要。

节点性能P由其静态性能指标和动态性能指标表示，可以使用式 (2) 计算得到。

P=αS+βD

(2)

式中：S表示节点的静态性能指标；D表示节点的动态性能指标；α和β为对应的权值，且α+β=1。

S=α1Cs+α2Ms+α3Sts+α4Sps

(3)

D=β1Cd+β2Md+β3Spd+β4Std

(4)

其中：节点静态和动态性能各评价指标的权值α1+α2+α3+α4=1，β1+β2+β3+β4=1。

1.3 节点性能优先级影响因素权值的计算

层次分析法 (analytic hierarchy process，AHP) 是将定量分析和定性分析结合的方法，常用于权值计算。使用AHP确定影响节点性能优先级各因素的权值，图1给出了节点性能优先级评价指标体系的层次结构模型。请专家针对CPU密集型和内存密集型作业的特点，分别对各影响因素进行评分。这样，NPARSA就能够根据当前需要处理作业的类型自适应地进行节点实时性能优先级的计算。

图1 节点性能优先级评价指标体系层次结构模型Fig.1 Hierarchical structure model for the node performance evaluation index system

1.3.1 针对CPU密集型作业

经专家打分，静态因素的四个影响因素的判断矩阵是：

静态因素权值向量W=[0.113，0.641，0.073，0.173]T，计算得到对应的一致性比率(consistency ratio, CR)的取值为 0.017，通过一致性检验。因此各个静态因素的权值如下：CPU核数为0.173、内存大小为0.641、磁盘容量为0.113、CPU速度为0.073。

动态因素的四个影响因素经专家打分，得到的判断矩阵为：

动态因素权值向量W=[0.344，0.422，0.156，0.078]T，计算得到CR为0.008，也通过一致性检验。则各个动态因素的权值如下：CPU剩余率为0.422、内存剩余率为0.344、磁盘读写速度为0.156、磁盘剩余率为0.078。

[5]李俊林：《建立高校高层次人才跟踪服务管理机制的研究》，《河北工业大学学报》（社会科学版）2011年第2期。

式(2)中的静态性能指标和动态性能指标对应的判断矩阵为：

因此α=0.5，β=0.5。

1.3.2 针对内存密集型作业

经专家打分，静态因素的四个影响因素的判断矩阵是：

静态因素权值向量W=[0.138，0.513，0.275，0.074]T， CR为0.003 9，通过一致性检验。各个静态因素的权值如下：CPU核数为0.138、内存大小为0.513、磁盘容量为0.275、CPU速度为0.074。

动态因素的四个影响因素经专家打分，构造出的判断矩阵为：

动态因素权值向量W=[0.110，0.442，0.262，0.186]T，CR值为0.023，通过一致性检验。各个动态因素的权值如下：CPU剩余率为0.110、内存剩余率为0.442、磁盘读写速度为0.262、磁盘剩余率为0.186。

α，β取值与CPU密集型作业的计算方法相同，均为0.5。

当需要处理的用户作业为CPU密集型时，NPARSA使用1.3.1节给出的动静态因素对应的权值；而当需要处理的用户作业为内存密集型时，NPARSA则会自适应地选择1.3.2节给出的动静态因素对应的权值。

1.4 算法描述

NPARSA运行于Spark系统中的Master节点。各个worker节点实时采集自身的状态信息，Master则利用Spark的心跳机制进行信息的收集，完成各节点实时优先级的计算。算法1给出了NPARSA的实现。

算法1 节点性能自适应的资源调度算法

2 虚拟机实验

首先在虚拟机上运行NPARSA，以考察其有效性。

2.1 实验环境和数据集

实验中共使用四个虚拟机节点，分别作为Spark系统中的主节点和从节点，节点配置见表3。

为了构建异构环境，各节点的内存容量、CPU核数或磁盘的读写速度有所不同。其中主节点的内存较大；从节点2的CPU仅有1核。为了使节点的I/O性能有一定的差异，从节点3的存储采用了HDD，而其他节点硬盘为SSD。

本文采用的实验数据来源于BigDataBench[16]，选用了WordCount、Sort、K-means和PageRank四种常用的CPU密集型和内存密集型负载。

2.2 实验结果及分析

2.2.1 单作业实验

本实验的工作负载为WordCount、Sort、K-means和PageRank。其中WordCount、K-means和PageRank要求CPU核数为4，内存为4 GB，属于CPU密集型负载；Sort要求CPU核数为4，内存为8 GB，是内存密集型负载。

WordCount和Sort实验中，Spark的资源调度算法分别使用Spark默认调度算法、SDASA[6]、文献[15]描述的算法(为方便描述，称为Difference算法)和NPARSA。实验结果如图2和图3所示。

图2 WordCount作业完成时间比较Fig.2 Comparison of the completion time of WordCount

图3 Sort作业完成时间比较Fig.3 Comparison of the completion time of Sort

从图2可以看出，与Spark默认调度算法相比，NPARSA将WordCount作业时间平均缩短了8.33%。与NPARSA动态调整节点优先级相同，SDASA也是结合节点的资源状态，实时调整集群中各个节点的优先级，但是SDASA没有考虑用户作业类型。与SDASA相比，NPARSA将系统性能平均提升了3.45%。与Difference算法进行对比，当WordCount数据量为2 GB时，NPARSA性能略低于Difference算法。但随着数据量的增加，NPARSA有着更优的表现，系统性能平均提升0.51%。

从图3可以看出，当运行Sort作业时，NPARSA的表现优于所有的对比算法。与Spark默认算法、SDASA和Difference算法相比，使用NPARSA的作业执行时间平均缩短了9.87%、4.88%和6.22%。

针对K-means和PageRank负载，实验分别在使用Spark默认调度算法、SDASA和NPARSA的Spark集群中运行。K-means负载的实验结果如图4所示。

图4 K-means作业完成时间比较Fig.4 Comparison of the completion time of K-means

从图4可以看出，执行K-means作业时，与Spark默认算法相比，NPARSA将作业的执行效率平均提升13.95%；和SDASA相比，平均提升7.85%。

图5给出了对PageRank负载进行的实验结果。实验中数据集的Page数目分别为260、270、280、290和2100。实验结果表明，相对于Spark默认算法和SDASA，NPARSA完成作业的时间平均缩短了17.46%和6.75%。

图5 PageRank作业完成时间比较Fig.5 Comparison of the completion time of PageRank

从图2～5不难看出，无论是运行WordCount、K-means、PageRank这样的CPU密集型作业，还是Sort这类内存密集型作业，NPARSA的表现都较为优秀。并且随着作业数据量的增大，使用NPARSA能够更加有效地缩短作业的执行时间，提升集群效率。

2.2.2 多作业并行实验

为考察当多个作业并行运算时NPARSA的性能，进行了WordCount和Sort两类任务的并行运行实验，图6给出了实验结果。

图6 并行运行的作业执行时间对比Fig.6 Completion time comparison for parallel jobs

可以看到，当多个负载并行执行时，与Spark默认调度算法相比，NPARSA将作业的平均执行时间缩短了10.84%；与Difference算法相比，作业平均执行时间也减少了1.74%。

从上述实验结果可以看出，因为节点的实时性能是根据所要处理作业的类型计算的，NPARSA能够给每个作业分配合适的集群资源，从而提高了集群的性能，缩短了作业的完成时间。

2.2.3 不同节点数目实验

为了测试集群中节点的数目对于NPARSA性能的影响，本节修改了虚拟机实验中的节点数目，删除了原四节点集群中的Slave1，构建的新集群中仅包含三个节点。在此三节点集群上使用2.2.1节描述的方式运行PageRank，得到的实验结果如图7所示。

图7 三节点集群中PageRank作业完成时间比较Fig.7 Comparison of the completion time of PageRank in the cluster with 3 nodes

通过分析计算，在三节点集群中，NPARSA完成PageRank作业的时间比Spark默认算法和SDASA平均缩短11.71%和4.28%。在四节点集群中，完成同样数量的PageRank作业，NPARSA完成作业的时间比Spark默认算法和SDASA平均缩短17.46%和6.75%。因此可以看出，随着集群中节点数目的增加，NPARSA的优势可以得到更好的体现。

3 小规模物理集群实验

为了避免虚拟机实验的偏差，进一步验证NPARSA的有效性，搭建了一个小规模的物理集群，完成了PageRank负载的对比实验。集群中有三个节点，其中一个是主节点，两个从节点，节点的配置如表4所示。为了使集群具有异构性，三个节点在CPU速度、核数、内存大小和磁盘读写速度上配置不同。

表4 物理集群实验节点配置

实验中PageRank的Page数目分别为260、270、280、290、2100和2110。实验运行7次，取各次运行结果的平均值作为实验结果，如图8所示。从图8中可以看出，在物理集群实验中，NPARSA仍能比Spark默认调度算法和SDASA有更为良好的表现，其完成PageRank作业的平均时间比Spark默认算法减少了37.39%，比SDASA减少了11.93%。

图8 物理集群中PageRank作业完成时间比较Fig.8 Comparison of the completion time of PageRank running in a physical cluster

4 结论

为了给每一个用户作业分配最适合其特点的节点，本文提出了NPARSA。NPARSA在计算节点的实时优先级时，会根据当前作业的类型自适应地选择节点优先级评价体系中各指标的权值。虚拟机实验和小规模的物理集群实验结果均表明，与Spark默认调度算法、SDASA和Difference算法相比，NPARSA能够减少用户作业的执行时间。

为了进一步优化NPARSA并验证其有效性，后续的研究内容包括：

1) 采用深度学习的方法对更多种用户作业的类型，如I/O密集型、网络密集型等进行准确判断，从而使算法可以更好地为更多类型的作业进行有效的资源分配。

2)增加节点静态和动态资源影响因素，如CPU的最大频率、内存的带宽等，以便更加全面准确地衡量节点的实时性能。

3) 在大规模的物理集群上进行实验，进一步验证算法的可扩展性。