石钊铭

（武汉市江夏区藏龙大道709号 武汉 430205）

1 引言

公共计算环境为全舰业务系统提供计算、存储、显控、信息接入与传输交互等集成保障服务，在对各基础设备监测过程中，会产生大量的历史数据，Hadoop 技术栈能够为公共计算环境基础服务平台提供分布式数据存储功能支撑。

Hadoop 分布式存储通过自身负载均衡程序完成均衡［1］。但该负载均衡算法并没有优先处理负载超重的计算单元，在多节点的计算单元集群中负载均衡的效率有待提高。

2 Hadoop负载均衡算法

针对负载不均的情形，Hadoop 提供一套针对方案，该方案中设计了一种算法，算法定义了一个阈值参数。通过该参数来对比Hadoop 平台各计算单元的实际数据占用率。如果占用率高于该定义值，则说明该处理对象承载的数据量过大，需要被均衡处理；如果占用率低于该自定义值，则说明该处理对象单元已经达到均衡状态。

定义四个链表用于存放计算单元对象，依次分别存放承载数据量过大计算单元、超过平均值且不是承载数据量过大的计算单元、低于平均值且不是非常低的计算单元和非常低的计算单元，通过Hadoop 负责均衡设计思路和实现方法可以逐个将各对象单元的负载达到一个平衡状态［2］。各对象单元负载实现均衡状态后，能够显著提高整个计算单元集群承载能力，在数量相同的情况下，可以承担更多业务的处理能力和数据的存储存储能力。

设计方法如下：

假设把两个数据单元作为处理对象，分别标号为S、T，把S 中的数据b 迁移到T 中，满足以下条件即可：

1）数据块b未迁移；

2）数据块b没有副本；

3）数据块副本所在的计算单元数据保持不变。

具体策略如下：

1）假设S 与T 属于同一计算单元，则可以迁移b。理由是数据块b的位置没有跨计算单元：

2）遍历b 的副本，假设副本的位置与T 在同一计算单元，则继续判断步骤3），否则可以迁移数据块b；

3）遍历数据块b 的副本，假设有副本与S 在同一计算单元内，并且通过分析得出此副本不在S上，则可以迁移数据块b。

通过分析上述负责均衡设计的思路和实现策略，可以得出Hadoop 负载均衡方法流程是直接先行处理计算单元内的均衡，再进行计算单元间的均衡［3～5］，没有优先处理负载超重的计算单元。

设想在一个计算单元M中，包含大多数负载重的数据单元（up 单元），只有很少的空闲数据单元（off 或down 单元），该计算单元的承载数据明显超过均值，在此计算单元中只将up 单元上的负载迁移到off 和down 单元，理论上无法实现较好的均衡效果，必须通过负载迁移来解决该计算单元负载承重过高的情形，针对该种情景，Hadoop 处理的应对方案是第一步在计算单元内部实行均衡算法，循序遍历的去处理每一个待处理的承载过高的对象单元，逐个将这些对象单元实现承载数据平衡，统计分析可以得出，该过程会显著延长计算单元全部实现均衡的时间［6～8］。

3 超负载处理算法

3.1 算法描述

针对计算单元集群内部承载数据量过大的计算单元，首先需要进行资源占用均衡分析，通过分析采用对应的处理方案，实施方法如下。

定义计算单元i的磁盘使用率Pi：Pi=Ui/Ti。其中Ui 是计算单元i 的已使用空间，Ti 是计算单元i的总空间大小。

m 表示每个计算单元的平均空间占有率。定义变量m，计算方法为m=Aui/Ati。该计算公式中，变量Aui表示所有计算单元的总空间中已经使用的占有量，Ati表示全部所有计算单元的用量总空间。

定义阈值变量K：针对每个计算单元负载运行情况，用户可以自定义设定此阈值的值，并优先处理承载高于该阈值的对象单元。

定义on 计算单元：假设计算单元i 满足公式m＜Pi≤m+ts，则这个计算单元为on 计算单元。该计算公式中，ts为自定义阈值。

up 计算单元：假设计算单元i 满足公式Pi＞m+ts，则这个计算单元可设定为up计算单元。

off 计算单元：假设计算单元i 满足公式m-ts ≤Pi＜m，则这个计算单元可设定为off计算单元。

down 计算单元：假设计算单元i 满足公式m-ts＞Pi，则这个计算单元可设定为down 计算单元。

定义变量Ei，Ei 表示第i 个计算单元在承载过大情形下的数据存储总量值。

依次顺序排列第j 个计算单元，假设该对象单元承载过大情形下的均衡值为SSj：SSj=L/Gj。

若SSj ≤1，则可以在计算单元内能够实现均衡；若SSj＞1，则无法通过在计算单元内自行实现数据承载平衡：若SSj＞K，则表明此计算单元数据承载量超过均衡阈值，在一定程度上影响了计算单元集群的数据处理性能，待处理的优先级较高，急需作为处理对象进行承载数据均衡。

定义变量Osj，该变量表示第j个计算单元在承载数据量过大情形下的均衡能力。OSj=Ej/Gj。

创建三个队列，分别按照如下对应关系命名：PriorBalanceList（P 队列），ForBalanceList（F 队列），NextForBalanceList（N队列）。

把SSi＜1 的计算单元存放在队列F 中；把SSi＞1且OSi＜1 的计算单元存放在队列N 中；把SSi＞K 的计算单元存放在队列P中。

所有分部在P 这个队列中的计算单元，根据上述定义分析，都归结为承载数据量过大计算单元，根据计算得出这些计算单元的内部承载数据量偏大，按照设计思路该对象单元应该需要设定为优先处理的单元进行均衡，均衡方法中按照公式计算SSi，并且按照SSi的降序排列［9～11］。

3.2 策略设计

设定一阈值K，该值可以按照用户需要自定义设定，用于分析并确定给出的计算单元的运行情况，判定是否为承载过大计算单元。

针对每一个计算单元，定义变量SSi。该变量表示计算单元在内部机制下的平衡能力，计算公式为SSi=Li/Gi。

为使计算单元i在均衡进程中达到一定的时间要求，设定被均衡的对象单元迁移的数据总量为Li，Gi是对象计算单元i能承载的的总数据量［12～14］。

若SSi ≤1，表示在均衡过程中，被均衡的计算单元内部需要迁移出的数据总量小于它所能承载的量。即说明此计算单元能够自行完成自适应承载平衡。

若SSi＞1，表示在均衡过程中，被均衡的计算单元内部需要迁移出的数据量大于它可承载的量，即说明该对象单元内不能够自行实现并完成均衡进程，必须把部分数据迁移到其它对象计算单元中去。

若SSi＞K，表示均衡过程中被均衡的对象计算单元内能够承载的量大幅低于需要处理的数据总量，即说明该对象计算单元承载数据量偏大，需要设定处理优先级来完成承载量均衡，按照均衡方法立即处理。

定义变量Osi，该变量表示计算单元i的负载自平衡能力。计算公式为OSi=Ei/Gi。

假设此值低于1，表示此计算单元中承载的数据总量少于能够承载的容量，能够提供使得该计算单元中的up 计算单元达到均衡的空余条件，可以作为均衡时承载数据的对象单元。

P 中存放需要首先均衡的承载量过大计算单元（SSi＞K的计算单元）。

F 中存放自身能够完成承载平衡并且还能承载其他数据的对象计算单元（SSi＜1）。

N 中存放承载过大并且能在该对象计算单元内完成均衡的计算单元（OSi＜1）。

处理逻辑是P 队列降序排列，将该队列中负载最大的计算单元第一时间做均衡处理。

计算单元i 选自P 队列，在F 队列中选取一个计算单元设为j，把i均衡后还需迁移的数据迁移到j。并分别在迁移策略算法中计算Ei及SSj的值。

通过上述计算方法，如果得出Ei 等于0，就表明已完成对计算单元i的处理，同时触发任务，停止i与j之间的均衡进程。

假设计算得出SSj 的值≥1，就表明该计算单元j不能再承载其他均衡数据，该进程需要干预，否则计算单元j 便会出现数据承载过大的情况，应当选择其它计算单元继续承载迁移数据。

假设P 中没有待处理的对象元素，则表明均衡进程已经完成。其余计算单元均衡按照原算法的实现思路完成均衡流程即可。

假设F 中没有待处理的对象元素，则表明进程继续从N中处理其他计算单元来承载均衡数据。

基于Hadoop 的设计算法，本文的设计算法着重于首先处理数据量承载过大的计算单元，升级了Hadoop 算法的策略，把随机选取的模式改为优先选择承载过大计算单元作为被均衡的对象单元来进行处理［15］。

3.3 算法流程

算法输入：各个计算单元的磁盘使用率

算法输出：无

算法伪语言描述：

1）按照上述设计的计算公式和分析策略，分别得出计算单元i的Li、Gi、SSi、Ei及Osi的值。

2）把满足SSi＞K 的计算单元加入到队列P，将优先需要处理的对象元素存放在该队列中。

3）把满足SSi＜1 的计算单元加入到队列F，该队列一方面能够完成计算单元内部的自适应均衡，另一方面还能够将承载迁移数据的计算单元按升序在队列中排序。

4）分别从P 队列和F 队列各取一个计算单元，假设为j和k。对于计算单元j，首先分析该计算单元内部的均衡情况，完成内部的自适应均衡，然后分析计算单元j 和k 间的总数据量承载情况，完成单元间的承载平衡，循环执行进程，直到进程结果计算得出Ej=0或着计算得出SSk ≥1。

5）分别按照上述方法计算自定义变量Ej、自定义变量SSk和OSk的值，

（1）若Ej=0，在P中删除计算单元j；

（2）若SSk ≥l，在F 中删除计算单元k，若OSk＜l，把k 加入到N队列中，升序排列此队列；

（3）若P不含对象元素，执行第9）步；

（4）若F 不含对象元素，执行第6）步；如果含有对象元素则跳转到第4）步。

6）分别从P 和N 中取一个计算单元，假设为j 和k。对于计算单元j，第一步分析计算单元内部的均衡情况，完成单元内部的均衡，第二步在计算单元j 和k 之间进行承载平衡，循环执行进程直到计算得出Ej=0 或着计算得出OSk ≥10。

7）计算新的定义值Ej和Osk。

（1）若Ej=0，从P中删除对象计算单元j；

（2）若OSk ≥1，从F中删除对象计算单元k；

（3）若P中不含对象元素，执行第9）步：

（4）若F 中不含对象元素，则跳转到执行第8）步；否则执行第6）步。

8）通过计算得出承载数据量过大的计算单元数目过多，则自定义设置阈值K。

9）完成上述分析和实现过程后，剩下的均衡情形和处理对象，其均衡过程基于Hadoop 的实现流程处理便可完成。

图1 算法流程图

4 实验分析

测试环境如图2所示，包括计算单元A、计算单元B、计算单元C三个计算单元：计算单元A中配置三个数据单元A1、A2、A3，计算单元B 配置B1、B2、B3三个数据单元，计算单元C配置C1、C2两个数据单元。

图2 优先处理超负载计算单元实验拓扑图

自定义每个HDFS 数据件块在单元内部存储系统中的大小为10M。实验中各计算单元的本地配置如：操作系统、cpu 和内存均保持一致，保证实验过程中非影响元素的统一性。

通过实验结果可以看出本文两种算法进行比较。具体比较参数包括：总空间及使用率和已占用大小。

整个处理对象单元的承载均衡进程实验分析以及处理结果如图3、图4所示。图中所示的横坐标即代表对象编号，纵坐标代表使用率。K值均为5。

表1 计算单元的初始数据存储率

图3 threshold为10%的空间使用率

图4 threshold为15%的空间使用率

计算单元A 中包含三个承载过大数据单元，分别定义为A1、A2、A3。计算单元B 中的数据单元B3以及计算单元C的全部数据单元均为低负载对象。

图3 中本文算法数据分布更均衡。用时6.89min。Hadoop算法整个数据量承载均衡进程执行完成，计算出用时大约为7.46min。在A1 对象计算单元完成数据量承载均衡时，本文算法耗时大约为2.43min。

图4 中，Hadoop 算法在5.89min 完成数据量承载平衡，本文算法用时略多，但能够更快地实现计算单元A1 中各数据单元之间的均衡，提高各数据单元的数据量承载均衡效率。

5 结语

计算单元存储负载均衡是公共计算领域的一个重要研究课题。Hadoop 平台能够在较多计算单元集群的应用场景中，高效地处理和存储海量数据。该平台自身负载均衡算法在面对有承载过大计算单元的情形时，实现跨计算单元的快速均衡的效率有待提升，针对该情形，本文设计并提出了一种改进的数据量承载平衡思路，该设计以Hadoop本身平衡策略为基础，加以改进和优化。验证了该优化策略能够更快地处理数据量承载过大的计算单元，缩短了承载过大计算单元负载均衡时间，提高了全系统负载均衡效率。