基于二分K-means的云计算集群资源分配算法
2022-11-08魏华栋肖心园江冰周志恒
魏华栋， 肖心园， 江冰， 周志恒
(1.山东电力工程咨询院有限公司，山东 济南 250013； 2.河海大学 物联网工程学院，江苏 常州 213022 )
0 引 言
云计算是一种在超大规模分布式环境中整合各类云资源的计算模式。用户对资源的请求是实时变化的。在多资源环境中，资源分配算法对系统资源利用率、用户满意度和总体工作效率等有极大影响。
喻德旷等[1]提出一种动态随机扰动的粒子群优化算法(particle swarm optimization, PSO)策略实现多资源分配，为限制计算过程中的收敛速度，将惯性权重常数设作变量，逐次减小迭代时的搜索范围，为使候选解更加多样，加入随机扰动，仿真证明可以有效提高计算效率和资源利用率。吕腾飞等[2]结合多目标遗传算法的全局搜索特性与蚂蚁算法的信息交流和正反馈机制，有效缩短任务用时，减小任务执行成本，提高资源利用率。郑迎凤等[3]提出一种在满足多QoS(quality of service)条件的基础上注重公平性的CTS_QFC(cloud tasks scheduling QoS algorithm meeting fairness constraint)算法，有效提高了任务的执行效率，并保障资源公平分配和任务合理调度。刘梓璇等[4]先根据资源利用率对云计算集群中各计算节点进行K-means聚类分析，再进行主导资源公平DRF(dominant resource fairness)分配算法，仿真证明该方法能达到更好的负载均衡。王松云等[5]利用时间-效用函数表示任务完成时间和收益之间的关联，提出一种优先关系调度机制达到分配系统资源的目的，实现了系统效用的最大化。潘佳艺等[6]提出了一种负载自适应的资源分配方式，监测云计算集群的计算节点与完成任务的状态，对其建模并量化各计算节点的性能，实现了基于相似度评估的资源调度方式，有效提升了集群并发度、资源利用率与集群性能。Bakalla等[7]提出了一种针对云数据中心的资源分配算法，该算法在满足QoS的基础上可以减少违反SLA(service-level agreement)的行为并管理能源消耗，与其他算法相比达到违反SLA行为最小化，同时维持云数据中心的能源消耗在可接受范围内。Vahidi等[8]提出改进的GOA(grasshopper optimization algorithm)算法，可以查看问题响应的空间从而优化云计算系统的响应，仿真证明了算法处理云计算资源分配问题的能力。Mishra等[9]提出一种基于任务分配的算法，从可用的云资源中为不同的应用选择最佳的资源，优化能耗、最大完工时间和吞吐量等各种参数，实现云系统效率和资源利用率的最大化，并在异构环境下由CloudSim进行仿真，试验证明该算法的性能更好。Jena等[10]提出了基于遗传算法的客户意识资源分配和任务调度算法，将任务映射到云中心的虚拟机，以获得最小的完工时间和最高的客户满意度，仿真结果表明，该算法在相关指标方面表现优越。在多资源的云计算环境里，由于用户发出的请求涉及的资源种类繁多，系统难以合理分配有限的资源，为避免此类问题的产生，在云计算环境中使用合理有效的资源分配方式尤为重要。Hadoop 2.0的资源管理系统YARN有三类基本的资源调度器：FIFO Scheduler、Capacity Scheduler和Fair Scheduler。本文提出RABBKC算法，该算法的实现基于Fair Scheduler。利用YARN资源调度器可插拔的特性，只需在YARN配置文件中修改Fair Scheduler类，并按本文算法思路修改相关源码，覆盖后重启集群即可更新资源分配方式。仿真结果表明本算法可以有效实现集群中各节点的负载均衡，提高了集群整体的稳定性。
1 主导资源公平分配算法
主导资源公平分配算法适用于多资源的云计算场景。这样场景中的云计算平台拥有不同种类的资源，用户发出的请求涉及多种类型资源，同时请求的资源有主次之分，例如I/O密集类型的请求更注重内存资源，计算密集类型的请求更注重CPU资源。对于不同用户与不同类型的请求而言，最为注意的资源类型也不一致。主导资源公平分配算法的原理为：首先以需求向量的形式定义不同用户对请求的资源需求程度，再统计所有用户发出请求中各类资源所占比例，然后根据统计结果将占比最大的资源类型视为主导资源，即为用户所需的最主要资源类型，最后优先对主要资源需求量最小的用户分配资源。
根据上述原理，主导资源公平的资源分配算法具体计算步骤如下所述。
将资源种类设为R1、R2、…、Rn，将系统拥有的资源总量设为向量TotalResource(TR1，TR2，…,TRn)，将请求需要的资源设为向量NeedJi(JiR1,JiR2,…,JiRn)。在已知用户请求Ji所需的资源为NeedJi，系统拥有的资源总量为TotalResource，可以计算出用户请求Ji的主导资源占比为：
(1)
(2)
(3)
图1 主导资源公平分配算法计算流程图
2 RABBKC算法
本文提出RABBKC算法对云计算资源进行分配。首先统计Hadoop集群内各slave节点对内存资源与处理器资源的使用率。由于K-means聚类在开始分簇时需随机指定若干数目的节点为质心，对质心分布不均导致聚类效果差的缺点，采用二分K-means算法进行分簇。本文根据内存资源与处理器资源的使用率统计结果对节点进行二分K-means聚类分析，找出各簇的聚类中心，将其中资源占用率最小的节点代表资源推荐至待分配的用户请求，根据该节点资源总量算出能够分配的最大用户请求数目，再结合主导资源公平的分配算法进行资源调度。
根据上述思想，本文算法的具体计算步骤如下。
将所有节点构成的数据集设为X，X={x1,x2,…,xn}。式中：n为节点数目；xi为数据集X中的第i个实例。xi=(xi1,xi2)为一个向量。式中：xi1为数据的第一个属性即对内存资源的使用率，xi2为数据的第二个属性即对处理器资源的使用率。将整个初始数据集视作一个簇。将簇定义为C=(C1,C2,…,Ck)。式中：k为划分簇的个数。每个簇都有一个质心M，M=(m1,m2,…,mk)。计算簇Ck的质心mk为：
(4)
式中：xik为簇Ck的第i个实例。根据式(4)计算初始簇的质心，当簇总数小于给定的数量时，对每个簇进行k取值为2的K-means聚类，计算簇聚类后的簇内误差平方和SSE(within-cluster sum of squared errors)，选择SSE最小的簇执行划分，直至簇总数达到指定条件。
衡量第h簇划分质量的SSEh包括两个部分：当前簇的簇内误差平方和SSE1与剩余其他簇的簇内误差平方和SSE2。假设目前数据集X包含n个簇，n (5) 式中：h0与h1为簇号。剩余其他簇的簇内误差平方和为： (6) 式中：U={1,2,…,h-1}∪{h+1,…,n}。联立式(5)、式(6)即可求出第h簇的簇内误差平方和。根据上述步骤，最后得到k个簇，并可结合式(4)求出各簇的质心。 使用sysbench和ubench工具测试本云计算集群环境的内存资源使用率与处理器资源使用率，可以得出本文环境中内存资源的最佳使用率为50%，处理器资源的最佳使用率为70%。当资源使用率比上述数据高时会使slave节点的性能降低，于是设得到质心为Cr，其坐标为(Cr,Mr)。定义系统资源利用率评估值为： (7) 代入各簇质心计算，求出的值越小则节点资源的使用率越低，设当质心为Ct时系统资源利用率评估值最小，便优先为其分配用户请求。在资源调度时，通过主导资源公平分配算法求出主导资源所占使用率最低的任务Jlow，将Ct簇内节点上的资源优先为Jlow分配。这样可以保证每次资源调度都是把相对空闲节点的资源分配给任务，从而有利于整体集群的负载均衡。RABBKC算法流程如图2所示。 图2 RABBKC算法计算流程图 由RABBKC算法的具体计算步骤可以看出，本算法有以下优点： (1) 利用主导资源公平分配算法动态计算各用户请求的主导资源占比状态，为主导资源占比低的用户请求分配资源，确保资源平均分配，鼓励各用户对资源的共享。 (2) 利用主导资源公平分配算法动态监测用户需求，具有策略防范意义，用户无法谎报资源需求从而获得更多资源。 (3) 利用主导资源公平分配算法实现用户无嫉妒的资源分配，因为各资源价值与占比均由调度器统一计算，不会有用户认为其他用户获得更多或者更有价值的资源，有利于用户使用体验感的提升。 (4) 动态评估各计算节点的资源利用率，研发人员可根据评估结果动态调整云计算集群中计算节点数目，避免部署节点数目不足难以处理多用户请求而宕机，或是部署过多计算节点浪费资源。 (5) 确保节点资源使用均匀，减少部分节点负载过大导致宕机的可能性，提高了云计算集群整体的稳定性。 (6) 优先使用资源利用率低的节点处理用户请求，不会出现计算节点空闲却不响应用户请求的情况，有利于云计算集群整体任务执行效率的提高。 本文利用Hadoop YARN中资源调度器为可插拔这一特性，修改yarn-site.xml配置文件的yarn.resourcemanager.scheduler.class，修改Fair Scheduler配置文件，按本文算法思路修改并编译相关源码，重启Hadoop即可完成修改。 本文在CloudSim 4.0平台进行仿真，重写了调度算法并修改相关功能函数，建立了一个数据中心，配置了10个物理机和20个虚拟机。设定两类用户请求如表1所示。 表1 用户请求配置 分别新建100个请求任务(含60个请求1与40个请求2)与传统的主导资源公平分配算法进行对比。分别新建50、100、500个请求任务(请求1与请求2数目各一半)与传统的主导资源公平分配算法进行对比，试验结果如图3～图8所示。 图3 任务数为50时内存资源利用率对比图 图4 任务数为50时处理器资源利用率对比图 图5 任务数为100时内存资源利用率对比图 图6 任务数为100时处理器资源利用率对比图 图7 任务数为500时内存资源利用率对比图 图8 任务数为500时处理器资源利用率对比图 由图3至图8可知：使用RABBKC算法调度任务时各虚拟机的资源利用率较为均衡，而使用主导资源公平分配算法时各虚拟机的资源利用率差值较大，说明前者能够有效平衡各节点资源利用率，避免部分虚拟机忙碌而其他节点空闲的情况出现，有利于集群负载均衡； 当任务总数为50时，使用RABBKC算法与使用主导资源公平分配算法的效果差距不大；但是随着任务数增加至100时，各资源利用率的均衡差距急剧加大，说明前者在待处理请求数目较多的场景中更能发挥其负载均衡的作用；当任务总数达到500时，使用主导资源公平分配算法调度任务时部分虚拟机的处理器资源几乎用尽，易发生宕机现象，说明使用RABBKC算法更有利于云计算集群环境的稳定运作。 本文针对云计算集群环境下节点资源难以公平分配的问题，采用RABBKC算法，并通过CloudSim仿真与传统主导资源公平分配方法进行对比分析，验证了本文方法能够有效达到集群负载均衡，从而使集群整体稳定性得到提升，有利于提升云计算集群环境部署算法执行的效率与稳定性。 随着科技不断发展，数据以海量方式增长，为应对海量数据处理云计算应运而生。为了高效处理多用户在云计算场景下提出的多个任务，高效的资源分配算法必不可少。优秀的资源分配算法可以为多用户在同等资源条件下更快地处理计算任务，提供良好的使用体验，具有较高的经济价值。本文提出的算法能够有效达到集群负载均衡，即可实现提升发电预测算法执行的效率和提高系统工作的稳定性。 本文采用的云资源分配方式更适合于计算节点较多的集群环境，当节点数目较少时聚类效果变差，分配云资源的合理性降低，应做出改进，以适用于集群节点不多的场景。
3 仿真试验
4 结束语
