0 引言

面对海量数据的存储和计算需求，通常采用分布式模型，这种模型将待处理的数据存储到通过网络连接的若干个地理位置不同的存储节点上，其典型代表是Apache开源的Hadoop^[1]。随着海量数据的不断增长，分布式存储系统^[2]往往通过横向扩展的方式，不断增加新的存储节点，使其规模越来越大；同时为了节省成本，整个集群中的存储节点大多采用可靠性较低的设备，而且新旧节点之间差异明显，这必然导致节点故障越来越频繁^[3]，这也给整个分布式存储集群带来了存储和计算资源的不确定性。上述情况给存储分配和任务调度带来了极大的挑战。因此如何解决分布式存储系统中存储资源的均衡和计算任务的均衡问题，是当前分布式系统的研究的热点之一。

1 相关研究 1.1 负载均衡

负载均衡^[4]是分布式模型中一个比较重要的研究内容，主要研究方向包括存储负载均衡和计算负载均衡，其中存储负载均衡解决的是存储资源的均衡分布问题，而计算负载均衡解决的是计算资源的均衡分布问题。

国内外的相关研究中，对计算负载均衡方面的研究比较多，而存储负载均衡方面的研究比较少。在分布式存储系统中，谈到各存储节点的负载均衡，一般都是以存储空间利用率或其他资源利用率^[5-6]来判断各存储节点的负载均衡程度，在基于资源利用率的负载均衡算法设计过程中，一般是以所有节点的磁盘空间利用率(Disk space Utilization, DU)相等作为整个分布式存储系统的最佳均衡点；而在实际的应用场景中，新加入集群的节点与原节点相比，新节点的磁盘I/O速率和存储可靠性一般都比原节点要高很多，这种差异导致原节点往往会成为整个分布式存储系统数据读写性能的瓶颈。传统的以磁盘空间利用率的方法来判定整个分布式存储系统的负载均衡，实际上是以损失新节点的数据读写效率为代价的。因此本文尝试从保证数据最佳读写效率的角度提出度量分布式存储系统负载均衡的新思路。

1.2 熵

在热力学领域，熵是表征系统内混乱程度的物理量，整个系统中热量总是从高温物体自发地传到低温物体，最终达到热平衡状态，此时系统熵值达到最大值^[7]。在信息学领域，信息熵常用来衡量一个随机信息量的大小，若信息的不确定性越大，则信息量越大，信息熵就越大；信息的不确定越小，则信息量越小，信息熵也越小^[8]。

分布式存储系统中存储资源的负载均衡问题从本质上可以理解为系统内部存储的均衡问题。文献[9]通过分析分布式系统与热力学系统的内在相似性，从熵的角度探讨了分布式系统均衡负载问题与能量的关系；文献[10]利用最大熵和熵增原理构建了熵优化模型，并提出了分布式系统中资源动态加权评估模型。

2 存储熵

本文根据熵和信息熵理论，结合分布式存储系统资源负载均衡问题，提出存储熵(Storage Entropy, SE)的概念和定义，并给出相应的负载均衡算法。

2.1 名词约定

1) 数据总量DN，即系统中所有节点存储的数据量累加数。设分布式系统中有n个节点，第i个节点的存储数据量为DN_i，则该系统中的存储数据总量为：

$ DN = \sum\limits_{i = 1}^n {D{N_i}} $

(1)

2) 磁盘I/O速率DR，即磁盘平均读写速率。第i个节点中磁盘的读写速率为DR_i，则磁盘平均读写速率为：

$ DR = \overline {\sum\limits_{i = 1}^n {D{R_i}} } $

(2)

3) 节点可靠性R_i，即第i个节点中磁盘能够正常运行的概率。

$ {R_i} = 1 - \frac{{{T_\mathit{i}}}}{{2*{T_{{\rm{life}}}}}} $

(3)

磁盘属于电子设备，其失效率符合“浴盆曲线”^[11]，考虑到磁盘的早期失效期时间比较短，为了简化计算，将其与恒定失效期合并，并通过式(3) 的方法近似计算，此时可以理解为磁盘出厂未使用时其可靠性为100%，当达到硬件的使用寿命时，其可靠性为50%，当达到2倍的硬件寿命时，其可靠性为0%。其中，T_life表示磁盘寿命(一般为3万小时)；T_i表示磁盘已经使用时间。

4) 节点读写时间DT_i, 即第i个节点中磁盘可靠的情况下读写数据所需要的时间：

$ D{T_i} = D{N_i}/D{R_i} $

(4)

5) 节点平均读写时间$ \overline {D{T_i}} $。读写第i个节点的数据时，可能出现读写成功和读写失败两种情况，将该节点的可靠性视为读写成功的概率，则可以计算出第i个节点的平均读写时间，因此综合考虑磁盘可靠和不可靠两种情况定义读写数据所需要的平均时间：

$ \overline {D{T_i}} = D{T_i}*{R_i} + D{T_{{\rm{max}}}}*\left( {1 - {R_i}} \right) $

(5)

其中DT_max表示节点不可靠情况下读写数据所需要的时间。

6) 基于读写效率的节点负载率L_i。将第i个节点的数据平均读写时间在整个集群中的比重定义为基于读写效率的节点负载率L_i。

$ {L_i} = \frac{{\overline {D{T_i}} }}{{\sum\limits_{i = 1}^n {\overline {D{T_i}} } }} = \frac{{D{T_i}*{R_i} + D{T_{{\rm{max}}}}*\left( {1 - {R_i}} \right)}}{{\sum\limits_{i = 1}^n {\left( {D{T_i}*{R_i} + D{T_{{\rm{max}}}} * \left( {1 - {R_i}} \right)} \right)} }} $

(6)

2.2 存储熵定义

分布式存储系统中资源负载均衡的目标是将存储的数据分发到n个存储节点上，如果采用随机分发的方式，那n个节点就会有不同的负载情况，需要寻找一种方法来度量这种具有明显不确定性的负载程度。本文根据熵理论给出存储熵的定义，其目的是通过存储熵来度量分布式存储系统中各个存储节点的负载均衡程度。

定义 1  在分布式集群系统中，如果系统中有n个存储节点，则分布式系统的存储熵H定义为：

$ H = - \sum\limits_{i = 1}^n {\left( {{L_i} * {\rm{lb}}\left( {{L_i}} \right)} \right)} $

(7)

存储熵的概念是熵理论在分布式存储系统中资源均衡领域的一种延展，其具有熵的一切性质，根据熵增原理和最大熵原理^[12]可以证明：存储熵的熵值总是从最不均衡状态的最小值H₀逐渐增加，直到完全均衡状态的最大值H_max。通过计算存储熵的熵值，可以简单高效地度量分布式存储系统整体资源负载的均衡程度。

定理 1  当L₁=L₂=…=L_n=1/n(i=1，2，…，n)时，存储熵H取得最大值，且H_max=lb(n)。

证明  由式(6) 可知：

$ \sum\limits_{\mathit{i} = 1}^n {{L_i} = } 1 $

(8)

此时问题转变成求H的条件极值，因此可以构造拉格朗日函数：

$ L = - \sum\limits_{\mathit{i} = 1}^n {({L_i} * lb({L_i})} ) + \lambda (\sum\limits_{\mathit{i} = 1}^n {{L_i} - } 1) $

(9)

分别对L_i(i=1, 2，…，n)求偏导，可以得到：

$ - lb({L_i}) - \frac{1}{{\ln 2}} + \lambda = 0 $

(10)

由此可以获得拉格朗日函数的驻点L₁=L₂=…=L_n，并将其代入式(8)，可以得到L₁=L₂=…=L_n=1/n，此时H取得最大值，根据式(7) 可以计算出H_max=lb(n)。证毕。

根据定义1和定理1可知，H的取值范围是[0, H_max]，因此可以通过存储熵H的大小来判断分布式存储系统中各存储节点的负载均衡的程度：当系统中负载完全均衡时，存储熵的熵值最大，且最大值H_max=lb(n)；当负载不均衡时，存储熵的熵值会逐渐变小，直到等于0。

存储熵函数曲线是一个n维的图像，无法形象化描述，文中仅给出n=2和n=3两种情况下，存储熵的函数曲线。

当n=2时，L₁+L₂=1，令L₁为横坐标轴，熵值H为纵坐标轴，通过MatLab绘制出存储熵的二维函数曲线如图 1所示。

当n=3时，L₁+L₂+L₃=1，令L₁为x坐标轴，L₂为y坐标轴，熵值H为z坐标轴，通过MatLab绘制出存储熵的三维函数曲线如图 2所示。

通过对图 1和图 2的观察可以发现：不论是二维熵函数还是三维熵函数，当所有分量取值相等时函数取得最大值，以此类推，n维熵函数的最大值应该满足：

$ {L_1}{\rm{ = }}{L_2}{\rm{ = }} \cdot \cdot \cdot = {L_{\rm{n}}}{\rm{ = 1/}}n $

(11)

3 基于存储熵的负载均衡算法

根据上述存储熵的定义，要计算其熵值H，需要求出所有节点负载率L_i，而在节点已知的情况下，需要求出该节点的数据读写时间DT_i和DT_max以及节点可靠性R_i。其中，DT_i可以通过节点存储的数据量DN_i和磁盘I/O速率DR_i来计算；DT_max可以通过人工设定的方式确定，比如令DT_max=3DT_i；R_i可以根据磁盘已使用时间和磁盘的使用寿命来计算。因此，在存储熵的计算公式中，需要采集的数据包括每个节点存储的数据量DN_i和磁盘的已使用时间T_i，其他数据都可以通过设备参数(如DR_i和T_life)或人工设定(如DT_max)来确定。

本文提出的基于存储熵的负载均衡算法就是根据存储熵的熵值判断分布式存储系统中存储负载的均衡程度，当该熵值小于一定的阈值，则进行负载迁移。该算法包括三个组成部分：判断系统存储负载均衡程度，判断单节点存储负载均衡程度，执行存储负载迁移操作。

3.1 系统存储负载判定

系统存储负载是否均衡的判定是本文算法的关键环节，如果系统存储负载判定是均衡的，则无需进行后续的单点存储负载判定和存储负载迁移工作。由于执行一次存储负载迁移需要占用一定的计算资源和存储资源，并且系统开销比较大，为了避免频繁地进行存储负载迁移操作，所以算法中设置了一个均衡阈值，只有当存储熵的熵值H小于该阈值时，表明整个分布式存储系统中存储负载不均衡情况达到了相对严重的程度，需要进行存储负载迁移。

系统存储负载情况判定的过程包括：

1) 设定均衡因子α(0 < α < 1)，可以据此得到均衡阈值H_α=αH_max。

2) 收集每个节点存储的数据量DN_i和磁盘已经使用时间T_i，并根据式(6) 计算出每个存储节点的负载率L_i。

3) 根据式(7) 计算出整个分布式存储系统的实际存储熵值H。

4) 判定系统负载是否均衡。如果H≥H_α，说明整个系统负载均衡程度在可以忍受的范围内，不需要作任何调整；如果H < H_α，说明整个系统负载失衡比较严重，需要进行负载迁移。

3.2 单节点存储负载判定

如果整个分布式存储系统中存储资源的负载均衡情况不理想，需要进行存储负载迁移操作，那就需要计算出哪些存储节点是超负载，哪些存储节点是空负载，并按照其存储负载程度构建超载节点有序队列和空载节点有序队列。

单节点负载判定的过程包括：

1) 计算每个节点的负载率L_i。

2) 计算系统平均负载L_avg。

$ {L_{{\rm{avg}}}} = \frac{1}{n}\sum\limits_{i = 1}^n {{L_i}} $

(12)

3) 创建超载节点有序队列和空载节点有序队列。如果L_i > L_avg，说明该存储节点超载，就将该存储节点按大根堆序插入到超载节点队列中；如果L_i < L_avg，说明该存储节点空载，就将该存储节点按小根堆序插入到空载节点队列中。

3.3 存储负载迁移

存储负载迁移的目的是将负载较多的存储节点上的数据迁移到负载较少的存储节点上，使整个分布式存储系统整体达到资源的负载均衡。

存储负载迁移的具体过程包括：

1) 计算每一个超载存储节点需要迁移出的数据量：

$ \begin{array}{l} \Delta D{N_i} = \left\{ {\left[{\left( {{L_i}-{L_{{\rm{avg}}}}} \right)} \right.} \right. * \sum\limits_{i = 1}^n {\left( {D{T_i} * {R_i} + D{T_{\max }}} \right.} * \\ \;\;\;\left. {\left( {1-{R_i}} \right)} \right)-D{T_{{\rm{max}}}} * \left. {\left( {1 - {R_i}} \right)} \right] * \left. {D{R_i}} \right\}/{R_i} \end{array} $

(13)

2)计算每一个空载存储节点需要迁移进的数据量：

$ \begin{array}{l} \Delta D{N_i}^\prime = \left\{ {\left[{\left( {{L_{{\rm{avg}}}}-{L_i}} \right)} \right.} \right. * \sum\limits_{i = 1}^n {\left( {D{T_i} * {R_i} + D{T_{\max }}} \right.} * \\ \;\;\;\left. {\left( {1-{R_i}} \right)} \right)-D{T_{{\rm{max}}}} * \left. {\left( {1 - {R_i}} \right)} \right] * \left. {D{R_i}} \right\}/{R_i} \end{array} $

(14)

3) 根据存储节点需要迁移的数据量，按序循环迁移数据，具体算法流程如图 3所示。

基于存储熵的负载均衡算法按照系统存储负载判定、单节点存储负载判定和存储负载迁移三个步骤调整分布式存储系统中各个存储节点间存储的数据量，以达到均衡存储负载的目的。这种追求全局均衡的机制可以有效控制各节点间的资源均衡程度，能够最大化地提高整个分布式存储系统的数据读写效率。

4 实验与分析 4.1 实验环境

为了验证算法的正确性和优越性，利用虚拟机搭建一个由双硬盘共20个节点构成的Hadoop集群进行测试。整个Hadoop集群由2个NameNode节点和18个DataNode节点组成，其中8个DataNode节点位于硬盘A上，其他节点位于硬盘B上，每个节点均为内存512 MB，硬盘8 GB，操作系统为CentOS 6.5，Hadoop版本为2.6.0。

硬盘A与硬盘B分别通过鲁大师硬件检测工具进行测试，测试结果显示硬盘A与硬盘B的数据传输率分别是482 MB/s和574 MB/s，可靠性分别是78.12%和93.03%。

4.2 实验设计与分析

实验中设置Hadoop集群的副本数量为1，依次上传5个测试文件，每个测试文件的大小分别是5.75、11.5、17.25、23和28.75 GB，根据下面提出的两种不同的实验方案，分别使用Hadoop自带的基准测试软件包测试其文件读操作所耗时间。

方案1  基于磁盘空间利用率的负载均衡算法(简记为DUA)^[13]。

将整个测试文件分成的Block平均分配到18个DataNode中，无法平均的Block按照随机顺序存储到对应的DataNode中，测试读取整个文件所用时间。

方案2  基于存储熵的负载均衡算法(简记为SEA)。

按照基于存储熵的负载均衡算法将测试文件存储到硬盘A和硬盘B对应的DataNode中，测试读取整个文件所用时间。

方案1、2文件读取时间的对比结果如表 2所示。

表 2中两种算法读取文件的时间开销均是经过多次重复实验所获得的测试数据均值，实验过程中，基于磁盘利用率的负载均衡算法采用Hadoop系统默认的数据均衡阈值(10%)，基于存储熵的负载均衡算法也设置数据均衡阈值为10%，该测试数据中包括了数据均衡和数据迁移所需要的时间开销。

上述两种算法各存储节点存储量和各存储节点存储空间利用率对比结果分别如图 4和图 5所示。

对比方案1、2的实验结果可以明显看出：基于存储熵的负载均衡算法在各存储节点磁盘I/O速率差异较大的分布式存储系统中，其数据读取效率比基于磁盘空间利用率的负载均衡算法高很多。在磁盘空间利用率方面，基于存储熵的负载均衡算法不如基于磁盘空间利用率的负载均衡算法，但实际上，这是因为上述实验中每个DataNode节点的硬盘空间都被固定地分配了8 GB，如果将硬盘B所对应的硬盘空间调整为12 GB，则两种算法磁盘空间利用率对比如图 6所示。

通过图 5和图 6的对比可以看出：调整硬盘B所对应的存储节点的磁盘空间大小后，不但使得整个存储系统读取文件的效率达到最优，而且也能保证整个存储系统磁盘空间利用率最优。

在实际应用场景中，随着海量数据的不断增长，分布式存储系统往往需要通过横向扩展的方式不断增加新的存储节点，这些新加入节点的磁盘I/O速率和可靠性一般都比原有存储节点高，如果盲目地增加新节点，有可能造成资源浪费。本文提出的基于存储熵的负载均衡算法追求数据读写效率最优，当存储熵达到最大值时，集群中所有存储节点的数据读写时间应该是一致的，因此可以根据节点负载率计算公式来推导和计算新加入节点最合适的存储容量，使之与原有存储节点匹配，从而保证整个存储系统达到配置最合理。

5 结语

针对分布式存储系统中的存储均衡问题，本文从数据读写效率的角度提出了基于存储熵的负载均衡算法，并将该算法与基于磁盘空间利用率的负载均衡算法进行了对比实验，验证了本文算法可以有效地提高整个分布式存储系统的读写性能。事实上，如果考虑到磁盘空间利用率的问题，可以根据磁盘I/O速率和可靠性，利用节点负载率计算公式计算并调整新节点的磁盘容量，这样既可以保证整个分布式存储系统的读写效率，也能够充分利用磁盘空间资源，该方法可以在集群规模扩展的过程中，解决新加入节点和原有节点配置差异大的问题。不过，本文提出的基于存储熵的负载均衡算法主要讨论和解决分布式存储系统整体的存储均衡问题，目的是实现分布式存储系统整体的读写效率最优，并不能实现单个文件的读写效率最优。