基于负载预测的HDFS动态负载均衡改进算法

邵必林，王莎莎

(西安建筑科技大学管理学院，陕西 西安 710055)

0 引言

HDFS[1-3]是Hadoop平台中的分布式文件系统，采用分布式布局模型[4]，在大数据处理尤其是存储方面具有非常高的可靠性、时效性。HDFS中有一个Balancer程序，是以存储空间利用率来评估节点负载量，程序初始运行时，由用户输入一个阈值(threshold，范围为0～100)，一般系统默认值为10，当数据节点中的负载值与平均负载最大差值小于阈值时，Balancer认为集群处于均衡状态，否则就会通过迁移操作来使集群到达负载均衡[5]。

虽然HDFS以诸多优势而被广泛应用，但其在负载均衡过程中，只采用存储空间利用率这单一指标来对集群做出均衡决策，并且采用设定静态threshold的迁移判断方法，对节点进行数据迁移和任务调度，很大程度影响了HDFS的存储效率。文献[6]在其默认均衡基础上，定义了一个多指标负载衡量函数，但其参与计算的指标过多，容易带来计算浪费和等待延迟问题。文献[7]对Hadoop异构集群中各节点的性能差异给集群均衡带来的影响进行综合考虑，但却忽略了集群整体状态对负载均衡效果的影响。文献[8]提出一种以存储熵作为集群均衡判断的新思路，有效提高了系统整体读写效率，但存储熵的计算具有明显的滞后性。

现有的HDFS负载均衡改进算法在解决负载状态衡量的片面性、滞后性，以及阈值设定的静态性问题等方面存在不足，本文针对此问题，提出了一种基于负载预测的HDFS动态负载均衡改进算法。

1 负载预测模型

1.1 节点负载计算函数

在分布式存储系统研究中，研究者往往是以存储空间使用情况来对集群中数据节点的负载进行评估，但实际上，单一指标并无法准确衡量每个节点所承受的真实负载，节点的繁忙程度对其负载状态的影响也是至关重要的[9-10]。分析存储节点的繁忙程度特征可知，在其运行过程中，CPU占用较少，主要存在大量的数据I/O操作，且数据的I/O快慢很大程度上取决于网络带宽的使用情况。

为了避免单一指标对负载状态衡量的片面性，和对所有负载特征同时采集可能造成的资源浪费和响应延迟问题。本文选取存储空间利用率Lstoragei、网络带宽占用率Lneti和I/O占用率LI/Oi三个重要指标来建立存储节点负载计算函数，其相对于HDFS中的节点负载衡量更加全面，且契合存储节点。设分布式存储集群中S={S1,S2,…,Sn}，其中Si表示集群中第i个存储节点，则存储节点i的综合负载值计算函数如下：

Li=ω1Lstoragei+ω2Lneti+ω3LI/Oi

(1)

式(1)中，ωi为各负载特征对存储效率影响大小的权重系数，ω1+ω2+ω3=1且ωi>0。

1.2 二次指数平滑预测模型

分析大量的负载历史值可知，负载变化存在短期上升或下降的线性波动。在对呈线性变化趋势的负载时间序列采用一次指数平滑，结果会产生明显偏差和滞后，二次指数平滑可以在此基础上对其再做一次指数平滑来对其结果进行修正，使预测效果最佳。此外，由于三次指数平滑的时间复杂度过高，不适用于进行频繁的负载预测[11-13]。所以本文的负载预测模型是建立在二次指数平滑算法的基础上进行优化研究。假设t时刻的负载时间序列{Lt}(t=1,2,…)，则其二次指数平滑模型定义为：

(2)

其二次指数预测模型为：

(3)

1.3 二次指数平滑预测模型优化

对式(2)进行逐次展开得：

(4)

综上所述可知，α需要随着时间推进和数据更新进行不断的动态调整，同时要舍弃掉距离当前t时刻较远的负载历史序列，才能使预测模型始终处于预测效果优化状态且保持算法复杂度最低。

将式(4)中两个公式各项系数之和进行归一化处理，得到：

(5)

基于此，提出优化后的动态二次指数平滑新模型为：

(6)

式(6)中，vt作为相应的动态平滑参数；t0为保留的负载时间序列的{Lt}长度。

优化后的动态二次指数预测公式为：

(7)

考虑到初始值对负载预测效果影响非常小，为了将算法的复杂度降至最低，对其使用静态值。

(8)

本文采用预测误差平方和SSE最小为目标作为评价优化模型，即：

(9)

对上式非线性优化模型进行求解即可得到最优的平滑参数α，进而计算出相应的动态平滑参数使预测结果更准确。本文采用执行速度快，计算复杂度低的最速下降算法来求解最优的α值。过程如下：

1)分别给定初值α0和允许误差X>0。

2)计算SSE′(α0)，如果‖SSE′(α0)‖≤X，则α0就是最优平滑参数，否则进行一维搜索，利用黄金分割法来计算最优步长λk-1，计算αk=αk-1-λk-1SSE′(αk-1)，(k≥1)，直至满足近似最优解条件。

3)最后将αk代入式(5)求得动态平滑参数vt，使用改进后的指数平滑预测模型进行负载预测。

根据以往研究经验，负载序列长期趋势变化不大但存在上下波动，静态算法中的α取值一般在0.3～0.5之间。优化模型中，为了使算法计算简单且结果精确度高，在进行多次实验后，最终确定了本文t0的最佳取值。图1为二次指数平滑的静态算法和本文优化后的动态算法与实际负载的预测结果对比，其中α=0.4，t0=6。分析可知静态算法中由于α取值固定，预测过程中难以实现在复杂的集群环境中对负载的变化做出自适应的改变，预测结果偏差较大。本文优化后的动态算法中α是通过反复迭代寻求SSE的最优解得到，整体预测结果很大程度优于静态算法，更适合建立负载预测模型来作为数据调度策略的一个重要依据。

图1 预测结果对比分析Fig.1 Comparative analysis of prediction results

2 动态负载均衡改进算法

在异构分布式存储系统中，各节点的资源和性能各不相同，负载均衡算法是将存储资源合理的分配调度至各节点，使集群保持均衡的状态[14-16]。HDFS中默认的负载均衡思路非常简单，由用户设置静态阈值，将数据节点划分为不同负载状态的集合，最后将高负载状态集合中的数据向低负载状态集合中的节点进行迁移，直至所有节点负载与平均负载的差值小于设定的阈值，才会认为集群处于正常均衡状态。其中阈值的设置是HDFS集群中负载均衡的关键，决定了系统达到平衡时所需要迁移的数据量和均衡效率。HDFS中阈值是人为设置的静态参数，没有考虑集群的整体状态，也不能随着集群环境的改变而动态的做出调整，具有较强的主观性和静态性。

2.1 动态阈值计算模型

基于以上分析可知，阈值的设定需要充分考虑集群的整体状态和环境变化，时刻做出动态调整，才能使整体集群随时处于最佳的均衡效果，且不会因为不必要的负载迁移而带来的资源浪费，因此，本文提出一种动态阈值的获取方式。动态阈值是根据节点的负载预测值和性能对集群的整体状态进行综合评估，其中包括集群的繁忙程度、响应效率、均衡程度等信息来动态计算阈值，其计算模型具体如下：

threshold=u1α+u2β+u3γ

(10)

式(10)中，μi>0且u1+u2+u3=1，α为集群的繁忙程度，β为集群的响应效率，γ为集群的均衡程度。由于threshold只能属于在0～100间的值，所以当计算得到的动态threshold<0时，自动替换为默认值10，当threshold>100时，自动替换为100。

2.1.1 集群繁忙程度计算

集群的繁忙程度可以使用集群中所有节点的平均负载Lavg来表示，在进行Lavg的计算时，为了减少集群繁忙程度衡量的滞后性，采用集群中所有节点的负载预测值来对其平均负载Lavg进行计算。具体如下：

(11)

2.1.2 集群响应效率计算

集群中节点的读写时间直接影响系统整体的响应时间，节点的读写时间又与节点的存储量和性能密切相关，节点i的平均读写时间可由下式计算：

(12)

式(12)中，SNi为第i个节点存储的数据量；SRi为第i个节点中磁盘的I/O速率。

将数据节点i在集群中数据读写时间占整个集群中所有节点的读写时间比重定义为节点的响应效率：

(13)

每个节点的响应效率为βi，则集群整体的响应效率为：

(14)

2.1.3 集群均衡程度计算

采用集群中各存储节点的均方差ε来衡量集群内部负载均衡程度，ε越大，说明集群内部状态越不均衡，ε越小，说明集群内部状态越均衡， 计算公式如下：

(15)

2.2 改进算法具体步骤和流程

1)系统初始化，设置采集节点信息的周期值T(10～15 s)，数据节点主动且周期性的对自身负载信息进行获取，包括存储空间利用率Lstoragei、网络带宽占用率Lneti、I/O占用率LI/Oi、已存储的数据量SNi、磁盘的I/O速率SRi。代入式(1)中计算节点的负载值Li，并将Li、SNi、SRi等信息反馈给控制节点。

3)根据2)中得到的预测结果和1)中的反馈信息分别计算α，β，γ，最后由式(10)计算出动态threshold并做均衡判断。当集群中所有节点的负载与平均负载的差值都小于threshold时，则认为集群处于正常范围，不需要进行迁移调度；反之，需要对其进行数据迁移和任务调度，直至集群处于正常范围。

具体算法流程如图2所示。

图2 改进的算法负载均衡流程图Fig.2 Improved algorithm load balancing flow chart

3 实验结果及分析

为验证上述算法的高效性和优越性，采用VMware Workstation组建包含13个节点的Hadoop集群环境，其中7个节点分布于A硬盘上， I/O速率为480 MB/s，剩余节点分布于B硬盘上，I/O速率为510 MB/s。集群中有1个负责监控和任务调度的控制节点(NameNode)和12个执行任务的数据节点(DataNode)，其配置均为：CPU: Intel Core i5-4200M 2.50 GHz；内存：4 GB；硬盘：8 GB；操作系统：CentOS 6.7；编程语言：Java 1.7.0；Hadoop版本：2.5.2。在实验中，采集节点信息的周期为15 s，其中本文算法中负载衡量函数和阈值计算函数中的权系数参数通过层次分析法，在算法实现过程中计算得到。

1)负载均衡效果对比。图3显示了启用负载均衡器后的1 h集群均衡程度随着时间推移的变化情况。图4为上传不同大小的数据文件，直至调度结束后，集群均衡程度的对比结果。图中数据均为进行3组实验后取得的平均值。如图3所示，采用HDFS算法的集群均衡程度1 h内基本没有变化，而采用本文算法在启用负载均衡器后的18 min内就明显的减少了负载均衡度值，最终均衡效果要优于HDFS算法。其原因是HDFS算法中采用默认静态阈值10，也就是当集群负载均衡度小于10%时，会认为系统处于均衡状态，不会对其进行负载迁移操作。而本文的阈值是通过实时评估系统的整体状态动态得到的，从而可以使系统达到更好的均衡效果。图4结果说明，采用HDFS算法时，集群的均衡程度受上传数据大小的影响比较大，随着文件大小增加，其均衡效果会减弱，而本文算法中的均衡程度则受影响较小，始终保持在0.01～0.02之间。其很大部分是因为本文算法引入了负载预测模型，所以随着集群环境的改变其稳定性和适应性更好。

图3 随时间推移的集群均衡程度变化Fig.3 The loading balance degree changing chart over time

图4 基于数据上传的负载均衡度对比Fig.4 Load balancing comparison based on data upload

2)任务执行效率对比。为了更好观察本文算法的执行效率，将本文算法、HDFS算法和文献[8]中的算法进行实验对比。图5为系统对不同并发任务数的作业完成时间对比结果。如图所示，任务完成时间与并发任务数大小成正比，随着并发任务数增加，完成时间也相应增加。但文本算法与HDFS算法和文献[8]中的算法相比较，所用的时间最少。当并发任务数为300时，HDFS算法用时为460 s，文献[8]算法用时443 s，本文算法用时355 s，本文算法执行效率相比于HDFS算法和文献[8]中的算法可分别提升26%和20%。其是由于本文算法中的节点信息获取由数据节点进行，减少了控制节点的存储负担和计算开销，且本文在进行算法设计时，尽可能地以降低算法时间复杂度为目标，因此大大减少了整体系统的作业执行时间。

图5 任务完成时间对比Fig.5 Task completion time comparison

4 结论

本文提出了一种基于负载预测的HDFS动态负载均衡改进算法。该算法通过建立存储节点负载值的多指标计算函数，并使用优化后的二次指数平滑预测模型对其负载值进行动态预测，最后根据预测结果和节点性能对集群的实时整体状态进行评估，建立动态阈值计算模型，进而对集群做出均衡判断和决策，有效弥补了HDFS中负载状态衡量的片面性、滞后性以及阈值的静态性等缺陷。理论分析和实验结果表明，本文改进算法对存储系统中的负载均衡调度具有高效性，不仅达到了更好的均衡效果，也缩短了作业的完成时间，提高了系统的整体响应效率。