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个特征参数描述节点状态。

2 基于HNN的存储策略 2.1 约束条件的表达

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

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

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

$ {{C}_{1}}\text{=}\sum\limits_{m\text{=}1}^{M}{\sum\limits_{l\text{=}1}^{N}{\sum\limits_{n\text{=}1}^{S}{\sum\limits_{\begin{smallmatrix} h\text{=}1 \\ h\ne m \end{smallmatrix}}^{M}{{{Z}_{mln}}\cdot }}}}{{Z}_{hln}} $

(1)

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

$ {{C}_{2}}=\sum\limits_{m=1}^{M}{\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{\sum\limits_{\begin{smallmatrix} h=1 \\ h\ne m \end{smallmatrix}}^{N}{\sum\limits_{l=1}^{S}{{{Z}_{mln}}\cdot {{Z}_{mhl}}}}}}} $

(2)

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

$ {{C}_{3}}=\sum\limits_{l=1}^{N}{{{\left( \sum\limits_{n=1}^{S}{\sum\limits_{m=1}^{M}{{{Z}_{mln}}-{{B}_{m}}}} \right)}^{2}}} $

(3)

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

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

$ {{C}_{4}}=\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{{{\left( \sum\limits_{m=1}^{M}{{{Z}_{mln}}-1} \right)}^{2}}}} $

(4)

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

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

$ \begin{array}{l} {C_5} = \sum\limits_{m = 1}^N {\sum\limits_{l = 1}^M {\sum\limits_{n = 1}^S {{Z_{\mathit{mln}}} \cdot J_{\mathit{mln}}^2 \cdot K({\mathit{J}_{\mathit{mln}}})} } } ;\\ \;\;\;\;\;\;\;{J_{\mathit{mln}}} = n - {t_m}, \mathit{K}({\mathit{J}_{\mathit{mln}}}) = \left\{ \begin{array}{l} 0, \;\;\;\;{J_{\mathit{mln}}} > 0\\ 1, \;\;\;\;{J_{\mathit{mln}}} \le 0 \end{array} \right. \end{array} $

(5)

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

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

$ \sum\limits_{m=1}^{M}{\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{\sum\limits_{\begin{smallmatrix} x=1 \\ x\ne m \end{smallmatrix}}^{N}{\sum\limits_{\begin{smallmatrix} y=1 \\ y\ne l \end{smallmatrix}}^{N}{\sum\limits_{z=1}^{L}{\sum\limits_{h=1}^{T}{\sum\limits_{k=1}^{F}{{{Z}_{\mathit{mln}}}\cdot {{R}_{\mathit{mlnhk}}}\cdot {{Z}_{xyn}}}}}}}}}}\cdot {{R}_{xynhk}} $

(6)

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

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

$ \begin{align} & E=\frac{1}{2}\sum\limits_{i=1}^{6}{{{C}_{i}}{{A}_{i}}}= \\ & \ \ \ \ \frac{{{A}_{1}}}{2}\sum\limits_{m=1}^{M}{\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{\sum\limits_{\begin{smallmatrix} h=1 \\ h\ne m \end{smallmatrix}}^{M}{{{Z}_{\mathit{mln}}}\cdot {{Z}_{\mathit{hln}}}}}}}+ \\ & \ \ \ \ \frac{{{A}_{2}}}{2}\sum\limits_{m=1}^{M}{\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{\sum\limits_{\begin{smallmatrix} h=1 \\ h\ne m \end{smallmatrix}}^{N}{\sum\limits_{l=1}^{S}{{{Z}_{\mathit{mln}}}\cdot {{Z}_{\mathit{mhl}}}}}}}}+ \\ & \ \ \ \ \frac{{{A}_{3}}}{2}\sum\limits_{l=1}^{N}{{{\left( \sum\limits_{n=1}^{S}{\sum\limits_{m=1}^{M}{{{Z}_{\mathit{mln}}}-{{B}_{m}}}} \right)}^{2}}}+ \\ & \ \ \ \ \frac{{{A}_{4}}}{2}\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{{{\left( \sum\limits_{m=1}^{M}{{{Z}_{\mathit{mln}}}-1} \right)}^{2}}}}+ \\ & \ \ \ \ \frac{{{A}_{5}}}{2}\sum\limits_{m=1}^{N}{\sum\limits_{l=1}^{M}{\sum\limits_{n=1}^{S}{{{Z}_{\mathit{mln}}}\cdot J_{\mathit{mln}}^{2}\cdot K({{J}_{\mathit{mln}}})}}}+ \\ & \ \ \ \ \frac{{{A}_{6}}}{2}\sum\limits_{m=1}^{M}{\sum\limits_{l=1}^{N}{\sum\limits_{n=1}^{S}{\sum\limits_{\begin{smallmatrix} x=1 \\ x\ne m \end{smallmatrix}}^{N}{\sum\limits_{\begin{smallmatrix} y=1 \\ y\ne l \end{smallmatrix}}^{N}{\sum\limits_{z=1}^{L}{\sum\limits_{h=1}^{T}{\sum\limits_{k=1}^{F}{{{Z}_{\mathit{mln}}}\cdot {{R}_{\mathit{mlnhk}}}\cdot {{Z}_{xyn}}}}}}}}}}\cdot {{R}_{xynhk}} \\ \end{align} $

(7)

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

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

2.2 能量函数的设计

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

$ \begin{align} & E=-\frac{1}{2}\sum\limits_{i}{\sum\limits_{j}{\sum\limits_{k}{\sum\limits_{x}{\sum\limits_{y}{\sum\limits_{z}{{{Z}_{ijk}}\cdot {{\mathit{\Psi }}_{ijkxyzhp}}\cdot {{Z}_{\mathit{xyz}}}}}}}+}} \\ & \ \ \ \ \ \ \ \ \ \sum\limits_{x}{\sum\limits_{y}{\sum\limits_{z}{{{\zeta }_{xyz}}\cdot {{Z}_{\mathit{xyz}}}}}} \\ \end{align} $

(8)

其中：

$ \left\{ \begin{array}{l} {\psi _{ijkxyzhp}} = - {A_1}(1 - \mathit{\sigma }(\mathit{i}, \mathit{x}))\mathit{\sigma }(\mathit{j}, \mathit{y})\mathit{\sigma }(\mathit{k}, \mathit{z}) - \\ \;\;{A_2}\mathit{\sigma }(i, \mathit{x})(1 - \mathit{\sigma }(\mathit{j}, \mathit{y}) - {A_3}\mathit{\sigma }(i, \mathit{x}) - {A_4}\mathit{\sigma }(j, \mathit{x}) - \\ \;\;{A_6}(1 - \mathit{\sigma }(i, \mathit{x})(1 - \mathit{\sigma }(\mathit{j}, \mathit{x}))\mathit{\sigma }(\mathit{k}, \mathit{z})\sum\limits_h {\sum\limits_p {{R_{ijkhp}}{R_{xyzhp}}} } \\ {\zeta _{xyz}} = - {A_3}{F_m} - {A_4} + {A_5}J_{xyz}^2\mathit{K}({\mathit{J}_{xyz}})\\ \mathit{\sigma }(\mathit{u}, \mathit{v}) = \left\{ \begin{array}{l} 0, \;\;\;\;u \ne v\\ 1, \;\;\;\;u = v \end{array} \right. \end{array} \right. $

(9)

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

$ \begin{array}{l} Z_{_{xyz}}^{t + 1} = \left\{ \begin{array}{l} 0, \;\;\;\;\;\;{Q_{xyz}} < 0\\ 1, \;\;\;\;\;\;{Q_{xyz}} > 0\\ Z_{xyz}^t, \;\;{Q_{xyz}} = 0 \end{array} \right.;\\ \;\;\;\;\;\;\;\;\;\;\;\;{Q_{xyz}} = \sum\limits_x {\sum\limits_y {\sum\limits_z {{\psi _{ijkxyz}}} } \cdot {Z_{ijk}} - {\zeta _{xyz}}} \end{array} $

(10)

3 实验与分析 3.1 实验方法

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

该系统配置为8个节点，其中一个节点为管理节点，其余7个为存储节点。网络参数A_i设置如下: A₁=4.1, A₂=4.1, A₃=1.1, A₄=2.3, A₅=2.3, A₆=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默认存储策略由于在数据负载平衡之间没有较准确地按需调配, 导致系统的总的开销都比较大。

4 结语

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

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