基于Hopfield神经网络的云存储负载均衡策略

李 强, 刘晓峰

(1.太原理工大学 财经学院，太原 030024; 2.山西省财政税务专科学校 信息学院，太原 030024; 3.太原理工大学 大数据学院，太原 030024)

(*通信作者电子邮箱122824940@qq.com)

基于Hopfield神经网络的云存储负载均衡策略

李 强1,2, 刘晓峰3*

(1.太原理工大学 财经学院，太原 030024; 2.山西省财政税务专科学校 信息学院，太原 030024; 3.太原理工大学 大数据学院，太原 030024)

(*通信作者电子邮箱122824940@qq.com)

针对当前Hadoop存储效率不高，且副本故障后恢复成本较高的问题，提出一种基于Hopfield神经网络(HNN)的存储策略。为了实现系统整体性能的提升，首先分析影响存储效率的资源特征；然后建立资源约束模型，设计Hopfield能量函数, 并化简该能量函数;最后，通过标准用例Wordcount测试，分析8个节点的平均利用率, 并与三个常用算法包括基于资源的动态调用算法、基于能耗的算法和Hadoop默认存储策略进行性能和资源利用方面的比较。实验表明，与对比算法相比，基于HNN的存储策略在效率上分别平均提升15.63%、32.92%和55.92%。因此，该方法在应用中可以更好地实现资源负载平衡，将有助于改善Hadoop的存储能力，并可以加快检索。

云存储；Hadoop；Hadoop分布式文件系统；副本策略；负载均衡

0 引言

云存储作为云计算的一种重要应用，通过对数据资源的统一化管理，能为用户提供高可靠性和可用性的大数据存储方式，受到到商界和学术界的特别重视[1-2]。基于Google云的云存储服务案例告诉我们，云并不一定建立在大规模和高可靠性的专用机器上，如果通过采用策略算法实施于一群普通PC上，就可以实现廉价的大规模存储。而这些硬件基础设施的可靠性并不一定高，一旦发生故障将导致永久性的数据遗失，所以为了提高可靠性，云存储系统往往采用副本技术来实现数据的冗余备份。副本技术将一个文件复制多份，然后采用算法将这些备份分布在不同的存储介质上，一方面可以防止存储设备宕机造成的危害，另一方面可为系统提供负载均衡，减轻单台存储造成的性能瓶颈，实现多台同时访问，以提高系统的整体性能和可靠性。

在Hadoop文件系统中使用ReplicationTargetChooser类实现副本算法，该默认算法设置3个副本：第一个副本存放在客户所在的DataNode上；第二个副本放在与第一个副本不同的机架中，并随机选择该机架中的一个DataNode进行存放；而第三个副本则存放于第一个副本所在的机架但与第一个副本不同的DataNode中。如果有更多副本则随机安放在系统的DataNode中。这种分布策略在一定程度上提高了系统的可靠性和负载能力，但这种策略随机性强，数据均衡性不是很强，所以需要进一步改进副本存放策略以提高系统的负载均衡能力[1]。在默认的副本复制方式下，系统的整体性能并不高，但是在近几年，云存储管理方式才得到一些国内外学者的关注。

2010年，国外学者Bonvin等[2]提出了一种可以自组织、故障忍耐，并可缩放的模型实现云存储。同期间在IEEE的国际会议上，Wei等[3]也提出了一种云存储簇的概念，使用成本效益合算方法实现动态复制管理。缺省的Hadoop副本存放策略基本上采用随机方式存放，并没有考虑各个存储节点的异构性。为了解决该问题，文献[4]中提出了依据节点处理能力计算备份的存储位置，在一定程度上提升了系统的整体存储性能，主要解决了系统中的异构性问题。2012年，周敬利等[5]提出了一种基于历史访问记录和积极删除文件的方法来实现数据的复制，实现了文件访问时间与文件保持一致性之间的代价平衡。文献[6]中通过使用哈希分布算法实现节点数据均匀分布，同时也实现了负载均衡；但是仅从容量的角度来提升性能，无法满足异构式分布系统的需求。文献[7]中依据节点距离和负载能力之间均衡，实现对文献[6]中的方法进一步改进。2013年，张兴[8]提出了一种比较全面的副本存放策略,该方法参考服务器负载均衡的策略，主要从磁盘空间的使用率、磁盘I /O访问率、CPU使用率和内存使用率来评价系统的负载均衡能力；但是该策略没有考虑网络因素和节点的分布方式对系统的影响，所以还有很多发展的空间。2014年，付雄等[9]提出了一种基于分簇思想且采用网络带宽和负载均衡的方法来布置副本的技术，并在实验中得到证实。但该方法是一种静态簇方法，不能支持簇的动态加入。此外，使用临时副本技术也增加了管理上的难度。

应用在作业调度中的典型代表技术有粒子群算法、蚁群算法、BP神经网络、概率神经网络[10]和霍普菲尔德神经网络(Hopfield Neural Network, HNN)等。其中,HNN已经成功应用在Job-Shop[11]和多处理器作业调度方面[12]。HNN算法在文献[11-12]中针对时间约束和资源约束可以很好地结合，并通过实验结果表明可以达到资源的最佳配置。

在Hadoop分布式文件系统(Hadoop Distributed File System，HDFS)集群中，为了达到每个数据存储节点之间的负载平衡，往往需要对副本存储方案进行改进，选择合适的节点作为目标节点实现副本的存储。资源的负载平衡问题，其本质就是一个受限资源的分配问题，对应于数学上的NP问题。本文采用HNN来实现副本存储位置的选择，进一步提高云节点上数据存储和检索的性能。

1 存储节点的特征

为了可以较详细地描述系统中某个节点的使用状况，采用5个指标进行描述，包括CPU平均使用率、内存平均占用率、 I/O平均访问率、 网络平均访问率和磁盘平均利用率。根据经验和参考其他文献，选取如表1所示的9个特征参数描述节点状态。

表1 节点特征参数Tab. 1 Characteristic parameters of nodes

2 基于HNN的存储策略

2.1 约束条件的表达

文献[13]指出HNN实现优化的本质是求解对应能量函数的极值问题。在求解问题的过程中，首先设计一个能量函数,不断地改变对应神经元的变量,最终寻找到该问题的极值，也就是该神经网络达到了稳定的状态。为了设计该对应问题的能量函数，需要创建函数项，包括目标函数和问题的约束条件。

使用变量Zmln表示为编号为m的数据块在第l个存储节点上的第n个磁盘上存放的状态标识。也就是当Zmln=1时，指明数据块m在第l个节点上的第n个磁盘上存放，否则Zmln=0。其中：m=1,2,…,M，M为数据块的最大编号；l=1,2,…,N，N为存储节点的个数；n为磁盘编号，n=1,2,…,S，S为最大磁盘数。

约束条件1 一个数据块的副本只能存放在任意一个存储节点上的一个磁盘中，可以按式(1)表示。

(1)

约束条件2 一个数据块的副本只能放在一个存储节点上，可按式(2)表示。

(2)

约束条件3 数据块m存放需要的磁盘数限制：

(3)

其中：Bm是数据块m需要的最少的磁盘数。如果式(3)中所需要的磁盘数为Bm时，其值为0，即最小值。

约束条件4 存储过程中无空闲存储节点约束：

(4)

该约束项用来保证在存储过程中不会出现所有的存储节点闲置。

约束条件5 每个数据块分配最大磁盘数：

(5)

其中：tm是数据块m需要存放的最大磁盘量；K(Jmln)为单位步长函数，当Zmln=1,n-tm>0并且K(Jmln)>0时,此项大于0，否则此项等于0。

约束条件6 资源共享竞争互斥：

(6)

针对共享资源竞争的问题,即两个数据块存放的相同扇区不能同时使用同样的资源,如网络、CPU和具体存储单元等。在式(6)中，F代表磁盘扇区的总量，t表示存储时间片，Rmlnhk和Rxynhk分别代表了数据块m和数据块x的资源需求矩阵的元素。若Rmlnhk=1，表示在h存储时间时数据块m需要资源k，Rxlnhk的作用等同于Rmlnhk。该约束项的作用是保证这两个不同磁盘的数据不能同时使用资源k。

当满足以上任意一个条件约束时,该约束对应的约束条件项值为0。联合以上所有的约束条件表达项,可以按式(7)统一表达所有约束:

(7)

其中:Ai是各个项的权重因数,并且保证Ai>0。

经过约束条件的组合设置，并设计能量函数，就可以实现优化目标，解决满足资源要求的分配问题[11]。

2.2 能量函数的设计

HNN具有高度的并行执行能力，可以被用来解决资源的优化组合配置问题。通过将上述约束条件联合成能量函数，可以满足李雅普诺夫函数条件，该系统存在稳定的控制状态，即该能量函数有解[13]。整理式(7)可以得到式(8)。

(8)

其中：

(9)

其中：两个神经元突触之间的连接强度用ψijkxyzhp表示,神经元阈值用变量ζxyz表示。该问题可由二值状态的离散型神经元表示，该变量的变化可由式(10)推导得出。

(10)

3 实验与分析

3.1 实验方法

为了观察该基于HNN的存储策略的性能，采用Hadoop三个标准的用例进行测试，包括WordCount、TaraSort和MRBench，并且与基于资源的动态调用算法、基于能耗的算法和Hadoop默认存储策略进行对比。本文采用的是预先周期节点情况采样策略，定期更新HNN的输入参数，采样周期为20 s，该方法可以避免动态方法访问频率过高，同时也可以减少不必要的I/O开销。

该系统配置为8个节点，其中一个节点为管理节点，其余7个为存储节点。网络参数Ai设置如下:A1=4.1,A2=4.1,A3=1.1,A4=2.3,A5=2.3,A6=4.1；并设置网络按串行方式迭代200步。

3.2 实验分析

对比测试结果如表2所示，可以看出与基于资源的动态调用算法、基于能耗的算法和Hadoop默认存储策略相比，基于HNN的存储策略在Wordcount用例上分别快178 ms、236 ms和226 ms；在Terasort用例上分别快138 ms、353 ms和523 ms;在MRBench用例上分别快118 ms、324 ms和568 ms。此外，基于HNN的存储策略、基于资源的动态调用算法和基于能耗的算法在执行效率上比Hadoop默认存储策略分别可提升55.92%、40.29%和23.04%；与基于资源的动态调用算法、基于能耗的算法和Hadoop默认存储策略相比,本文推荐的存储策略在执行效率上分别平均可以提升15.63%、32.92%和55.92%。分析其比较效果是因为基于HNN的存储策略独立运行在管理节点上，并不参与存储，在存储节点上没有消耗，所以没有明显地增加系统开销和时间。基于资源的动态调用算法侧重于等待时间而轻资源消耗，而基于能耗的算法偏重于资源利用而轻时间消耗，这两种算法均未能均衡对待时间和资源，导致系统整体开销增加，时间消耗增大。如某些节点资源处理能力弱却因等待时间长而被动态算法选择，事实上处理能力强的节点更加合适，所以会增加整体系统消耗时间；又如异构系统中节点资源不均等，资源多且能耗也大，但是能耗算法将选择其他资源小且能耗也小的节点，产生非能力分配等情况，反而系统的整体消耗将会增加。所以从总体消耗来观察，HNN具有显著优势。

如表3所示，节点1中的CPU利用率、内存利用率、I/O利用率和网路利用率相对其他节点较高，而磁盘利用率较低，分析其原因为该节点是管理节点，主要维护数据的索引，并不真实存储数据。同时，可以计算得到7个计算节点的CPU利用率、内存利用率、I/O利用率、网路利用率和磁盘利用率分别平均分布在72.625%、73.12%、66.5%、53.55%和46.5%，且可观察到该5个指标分布相对均衡。

通过3个用例对四个算法进行相同的测试，如表4所示，基于HNN的存储策略的I/O平均利用率、网路平均利用率和磁盘平均利用率相对其他算法较低，究其原因为负载均衡后，减少了不必要的I/O和网络开销，也就是由于基于HNN的存储策略针对磁盘参数、I/O参数和网络参数可以均衡地表达在约束条件中。而基于能耗的算法中CPU平均利用率、内存平均利用率显著较高，而I/O平均利用率、网路平均利用率和磁盘平均利用率较低，其原因为把大量的运算布置在本地，过度降低I/O的能耗而导致CPU和内存的代价增高。基于资源的动态调用算法的CPU平均利用率、内存平均利用率和磁盘平均利用率相对于其平均利用率和网络平均利用率较低,其原因是为了实现资源的动态平衡,而在不同节点之间进行数据交换,增大了I/O和网络的开销。Hadoop默认存储策略由于在数据负载平衡之间没有较准确地按需调配,导致系统的总的开销都比较大。

表2 几种算法执行时间对比Tab. 2 Execution time comparison of several algorithms

表3 8个节点的平均资源利用率Tab. 3 Average resource utilization rate of 8 nodes

表4 用例的性能比较 %Tab. 4 Performance comparison of use cases %

4 结语

本文首先分析了Hadoop默认存储策略存在的问题,该问题最终会导致系统负载不均,以及系统恢复数据高成本的缺陷；然后,分析系统各个资源对存放数据的影响，建立一套综合资源利用模型；最后，使用人工智能HNN技术实现数据存放策略的改进，并通过实验验证了该方法可以实现存储负载均衡，显著地提升系统的存储性能和检索效率。

高弹性的系统能力是云计算的显著特征，但是在系统规模增大或作业数显著增加时，现有的云作业调度算法的性能容易达到峰值。如何改进作业调度策略，提升系统的整体作业吞载率，实现作业调度算法的优化，将是我们下一步研究的重点。

References)

[1] BORTHAKUR D. Hadoop [EB/OL]. [2011- 06- 15]. http://lucene.apache.org/hadoop.

[2] BONVIN N, PAPAIOANNOU T G, ABERER K. A self-organized, fault-tolerant and scalable replication scheme for cloud storage [C]// SoCC ’10: Proceedings of the 1st ACM Symposium on Cloud Computing. New York: ACM, 2010: 205-216.

[3] WEI Q, VEERAVALLI B, GONG B, et al. CDRM: a cost-effective dynamic replication management scheme for cloud storage cluster [C]// CLUSTER ’10: Proceedings of the 2010 IEEE International Conference on Cluster Computing. Washington, DC: IEEE Computer Society, 2010: 188-196.

[4] RUAN X, XIE J, DING Z, et al. Improving MapReduce performance through data placement in heterogeneous Hadoop clusters [C]// Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum. Washington, DC: IEEE Computer Society, 2010: 1-9.

[5] WANG Z, LI T, XIONG N, et al. A novel dynamic network data replication scheme based on historical access record and proactive deletion [J]. The Journal of Supercomputing, 2012, 62(1): 227-250.

[6] 周敬利,周正达.改进的云存储系统数据分布策略[J].计算机应用,2012,32(2):309-312. (ZHOU J L, ZHOU Z D. Improved data distribution strategy for cloud storage system [J]. Journal of Computer Applications, 2012, 32(2): 309-312.)

[7] 林伟伟．一种改进的Hadoop数据放置策略[J].华南理工大学学报(自然科学版)，2012,40(1):152-153. (LIN W W. An improved data placement strategy for Hadoop [J]. Journal of South China University of Technology (Natural Science Edition), 2012, 40(1): 153-158.)

[8] 张兴.基于Hadoop的云存储平台的研究与实现[D].成都：电子科技大学,2013:22-38. (ZHANG X. Research and Implementation of cloud storage plateform based on Hadoop [D]. Chengdu: University of Electronic Science and Technology of China, 2013: 22-38.)

[9] 付雄,贡晓杰,王汝传.云存储系统中基于分簇的数据复制策略[J].计算机工程与科学,2014,36(12):2296-2304. (FU X G, GONG X J, WANG R C. A cluster based data replication strategy in cloud storage systems [J]. Computer Engineering & Science, 2014, 36(12): 2296-2304.)

[10] 李强,刘晓峰,贺静.基于语音特征的情感分类[J].小型微型计算机系统,2016,37(2):385-388. (LI Q, LIU X F, HE J. Sentiment classification based on voice features [J]. Journal of Chinese Computer Systems, 2016, 37(2): 385-388.)

[11] 王万良,吴启迪,徐新黎.基于Hopfield神经网络的作业车间生产调度方法[J].自动化学报,2002,28(5):838-844. (WANG W L, WU Q D, XU X L. Hopfield neural network approach for job-shop scheduling problems [J]. Acta Automatica Sinica, 2002, 28(5): 838-844.)

[12] 王秀利,吴惕华.一种求解多处理器作业调度的Hopfield神经网络方法[J].系统工程与电子技术,2002,24(8):13-16. (WANG X L, WU T H. Scheduling multiprocessor job using Hopfield neural network [J]. Systems Engineering and Electronics, 2002, 24(8): 13-16.)

[13] HOPFIELD J J, TANK D W. Neural computation of decision in optimization problems [J]. Biological Cybernetics, 1985, 52(3): 141-152.

This work is partially supported by the National Natural Science Foundation of China (61502330), the Scientific and Technological Innovation Programs of Higher Education Institutions in Shanxi (20161131), the Project of Soft Science Plan of Shanxi Province (2016041008- 5).

LIQiang, born in 1980, M. S., associate professor, senior engineer. His research interests include Hopfield neural network.

LIUXiaofeng, born in 1979, Ph. D., lecturer. His research interests include Hopfield neural network.

LoadbalancingstrategyofcloudstoragebasedonHopfieldneuralnetwork

LI Qiang1，2, LIU Xiaofeng3*

(1.CollegeofFinanceandEconomics,TaiyuanUniversityofTechnology,TaiyuanShanxi030024,China；2.CollegeofInformation,ShanxiFinanceandTaxationCollege,TaiyuanShanxi030024,China；3.CollegeofDataScience,TaiyuanUniversityofTechnology,TaiyuanShanxi030024,China)

Focusing on the shortcoming of low storage efficiency and high recovery cost after copy failure of the current Hadoop, Hopfield Neural Network (HNN) was used to improve the overall performance. Firstly, the resource characteristics that affect the storage efficiency were analyzed. Secondly, the resource constraint model was established, the Hopfield energy function was designed and simplified. Finally, the average utilization rate of 8 nodes was analyzed by using the standard test case Wordcount, and the performance and resource utilization of the proposed strategy were compared with three typical algorithms including dynamic resource allocation algorithm, energy-efficient algorithm and Hadoop default storage strategy, and the comparison results showed that the average efficiency of the storage strategy based on HNN was promoted by 15.63%, 32.92% and 55.92% respectively. The results indicate that the proposed algorithm can realize the resource load balancing, help to improve the storage capacity of Hadoop, and speed up the retrieval.

cloud storage; Hadoop; Hadoop Distributed File System (HDFS); replica strategy; load balancing

TP393.027

A

2017- 01- 18;

2017- 03- 10。

国家自然科学基金资助项目(61502330)；山西省高等学校科技创新项目(20161131)；山西省软科学计划研究项目(2016041008- 5)。

李强(1980—)，男，山西太原人, 副教授，高级工程师，硕士，CCF会员，主要研究方向：Hopfield神经网络； 刘晓峰(1979—)，男，山西怀仁人，讲师，博士，主要研究方向：Hopfield神经网络。

1001- 9081(2017)08- 2214- 04

10.11772/j.issn.1001- 9081.2017.08.2214