信息知识库中的数据可用性恢复策略*

徐 鹏，孟宇龙,朱 群，侍守创，龚玉婷

(1. 中国船舶重工集团公司第七一六研究所 江苏杰瑞科技集团有限责任公司， 江苏 连云港 222002；2. 哈尔滨工程大学 计算机科学与技术学院， 黑龙江 哈尔滨 150001)

相比于传统数据库，信息知识库不仅包含了大量的数据，还包含了规则和过程性知识，信息化地从知识库中提取数据，能够有效提高生产效率[1]。由于数据的不断积累及爆发式的增加，知识库的存储节点数量也随之不断膨胀。为控制成本，大规模的知识库存储系统的搭建一般选用廉价的存储服务器，当设备离线或故障时，存储节点失效，数据丢失[2]，故保证知识库数据的可靠性和完整性至关重要。

现有保证数据可靠性及完整性的方式主要包括副本冗余[3]与纠删码[4]，副本冗余技术成本随

数据量的增大而不断提高，纠删码技术可以在存储成本低于副本冗余技术的前提下，获得相同或更高的数据可靠性及完整性[5-6]，但其失效数据重构过程的数据传输会造成较多的网络资源消耗，且重构速度有待提高。如何提高纠删码的失效数据重构性能成为研究热点。传统纠删码数据重构采用供应节点与新生节点数据直接传输的方式，该方式瓶颈取决于供应节点与新生节点间网络状况最差的一条链路，对整体重构性能影响严重。针对该问题，Li等[7-8]以树形拓扑结构代替节点直连方式，该方式将新生节点作为重构拓扑的根节点，参与重构的供应节点作为叶节点，叶节点数据经过计算处理后上传至父节点。当上级节点获取到数据后，与本节点数据按照算法进行计算，然后向其父节点发送计算结果，依照该方法递归至根节点，重构过程结束。树形重构方法虽然一定程度上降低了传输链路瓶颈对重构效率的影响，但是数据完整性较差。

在实际生产环境中，当有单个存储节点失效时，系统并不会立即进行数据恢复，而是在达到指定失效节点数量或设定时间时开始重构[9-10]，多节点失效情况下星形及树形重构方式性能下降严重。基于多节点失效情形，本文提出链路带宽和路由节点的重构方法 (Reconstruction Method based on Link Bandwidth and Routing Node，RMLBRN)，首先根据节点的数据处理能力从候选新生节点中选举出路由节点，然后根据路由节点与候选供应节点间链路带宽选出供应节点，根据路由节点与候选新生节点间带宽确定新生节点，从而构成失效数据重构的网络拓扑。在路由节点接收供应节点数据重构出失效数据后，发送至新生节点，完成数据重构，从而有效降低重构时间。

1 研究现状

文献[11-12]提出了Regenerating Codes，该方法不仅满足了最大可分离码的性质，而且引入了网络编码来优化重构带宽。在重构过程中，选取尽可能多的节点参与重构，降低了重构过程中带宽的消耗。但该方法限制每个供应节点必须向新生节点传输等量数据，使得新生节点可选择使用的链路受限，无法利用其中具有较高带宽的链路资源，从而重构时间较长。文献[13]基于树形重构方法对节点间带宽进行排序，并优先选取可用带宽较好的节点参与重构过程，降低了数据传输对重构性能的影响，但该重构方法为贪心策略，时空复杂度会随存储系统节点增多而不断提高。文献[14]通过避免使用上一次重构时带宽最小的链路来改善重构时间，但该方法性能随重构次数增加而下降，且在多节点失效情况下性能下降更加明显。

针对存储系统中存在多个失效节点的问题，文献[15]中将纠删码参与重构节点的数据划分至不同的块中，重构过程中各节点根据所在块完成相应任务，相较单节点重构有更高的重构速率，但该重构策略时间复杂度较高；基于星形结构的串行修复策略[16](Star Structure based serial Repair, SSR)与基于树形结构的串行修复策略[17](Tree structure based serial Repair, TSR)采用串行方式重构失效数据，重构时间较长且占用网络资源较多；文献[18]针对现有多节点重构方案未考虑新生节点间的数据传输问题，提出了基于带宽的节点选择策略(Bandwidth based Weak and Strong Judgement, B-WSJ)，考虑新生节点间信息传输，可以降低重构时间，但仍为串行重构，且在判断新生节点间数据传输时会增加重构时间；文献[19]从节点间网络距离角度出发，通过统计各供应节点与新生节点间的网络距离，找出网络距离总和最小的链路进行重构，以此降低重构时间，但该方法并未考虑实时带宽及链路情况变化。

2 问题描述

一般以(n,k,d)-纠删码代表将数据对象划分为k个大小完全一致的数据块，通过对该k个数据块进行纠删码编码生成n(n>k)个大小相同的编码块的纠删码，当有任意d(d≥k)个编码块存活时，通过解码运算即可恢复失效数据或原有数据。以(6, 3, 3)-纠删码为例，首先将数据对象分为3个数据量完全一致的数据块B1、B2、B3,根据编码规则对3个数据块进行编码生成C1、C2、C33个编码块，大小与数据块相同。分别将每个块存放于不同的节点，根据最大可分离性质，当系统中有少于等于3个失效块时，便可恢复出失效数据。划分及编码过程如图1所示。

图1 (6, 3, 3)-纠删码Fig.1 (6, 3, 3)-erasure code

假设系统设定当存在两个失效节点时，开始重构失效数据。以SSR方法与TSR方法为例，当系统进行重构时，会在存活的空闲节点中随机选取2个供应节点作为新生节点，存活的数据节点和编码节点向其传输该节点的所有数据并进行重构。传统重构方法在选择新生节点时并未考虑与供应节点间的链路带宽，性能上有较大瓶颈；在重构时每个节点传输该节点的所有数据，数据冗余较大，占用了较多的网络资源，资源消耗严重。

针对多节点失效情况，本文提出了RMLBRN算法。该方法首先根据新生节点的数据处理能力，选择出负责接收、计算并传输数据的路由节点；然后选取与路由节点可用带宽较大的供应节点及新生节点参与重构过程，生成最大可用带宽重构拓扑，来提高多节点失效时的重构效率。

3 算法及分析

3.1 选举路由节点

由于系统中各节点性能存在差异，磁盘的I/O、内核数目、内存型号、芯片型号、硬盘的缓存和转速以及CPU 的主频等都有可能是导致节点能力异构的因素。所有节点不可能一成不变，在经过一段时间的使用之后，节点的一些性能也会随时间而改变，需通过及时更新节点数据处理能力来保证实验参数的准确性。在分析过后，本节以以下衡量标准定义节点的数据处理能力：首先根据节点的主要决定因素初始化节点的数据处理能力，然后根据每次系统的设定改变，或者以一次完整重构时间为基数，经加权计算后更新该节点性能。

以(n,k,d)-纠删码为例，当系统存在r(r≤n-d)个失效节点时，开始重构失效数据。假设该系统共包含N个存储节点，其中n-r个供应节点需进行数据读取、编码及上报，节点压力较大，故在剩余N-n个节点中选择r个空闲节点作为新生节点。

首先选取磁盘I/O、CPU核数、主频、内存大小等作为衡量节点数据处理能力的标准。分别用α表示节点的磁盘I/O，β表示CPU核数，γ表示节点主频，θ表示节点内存，同时以cα、cβ、cγ、cθ表示四项标准的加权参数，并满足cα+cβ+cγ+cθ=1，则节点i的数据处理能力可表示为：

Si=cαα+cββ+cγγ+cθθ

(1)

假设节点i在重构过程中参与的数据读取、编码等操作的总计算量为Pi，则节点i参与重构的总时间为：

t=T(Pi/Si)

(2)

其中函数T(·)将计算结果转换为时间单位(s)，以便后续处理，其转换结果与节点数据处理能力成反比。

针对节点状态的变化对数据处理能力的影响，在式(2)初始化节点的数据处理能力后，当达到设定的时间阈值或数据重构后，更新节点的数据处理能力。以ni,t表示节点i本次参与重构消耗的时间，li,t表示节点i上一次参与重构消耗的时间，单位均为s，则更新节点i的参与重构时间为：

ti=ali,t+(1-a)ni,t

(3)

式中，a(0≤a≤1)为上次参与重构时间的权重。通过式(3)，节点i的数据处理能力与重构时间建立关系，并成反比。当路由节点数据处理能力越强时，系统重构效率越高。

3.2 选择参与重构的节点

在选择参与重构的供应节点时，首先需要获取存活节点与新生节点间的可用带宽大小，然后按照最大生成树原理，依次选取与新生节点有最大可用带宽的存活节点作为供应节点，直到供应节点数量满足所选纠删码策略的重构要求为止。

由于测量各节点间链路带宽仅需2～4个往返时延[20]，相对重构过程影响可忽略，且短时间内带宽波动较小，因此在数据重构期间可将带宽设置为固定值[21-22]。假设各参与重构节点的数据传输量均为d。具体供应节点选择步骤如下。

以(n,k,d)-纠删码为例，重构阈值为r(r≤n-d)，引入供应节点集合Cc及新生节点集合Cn，用以存放参与失效数据重构的供应节点及新生节点。首先从空闲新生节点中根据节点的数据处理性能选择路由节点Nc，放入集合Cn。

引入边集Ec={e0,e1,…,en-r-1}表示路由节点与候选供应节点间的链路，其值代表数据传输的网络带宽，值为0表示节点间无链路连接。算法根据路由节点与候选供应节点的边集Ec依次选择具有链路带宽的节点，确定为供应节点，将该点存入集合Cc中并从边集中删去该链路，根据此方法选出共d个供应节点截止。

供应节点确定后，需在空闲节点中选择剩余r-1个新生节点。引入边集En={e0,e1,…,eN-n-2}表示路由节点与候选新生节点间的链路，其值代表数据传输的网络带宽，值为0表示节点间无链路连接。算法根据路由节点与候选节点的边集En依次选择具有链路带宽的节点，确定为新生节点，将该点存入集合Cn中并从边集中删去该链路，根据此方法选出共r-1个新生节点截止，从而构成以路由节点为中心的数据重构网络拓扑。参与重构的节点选择算法如算法1所示。

以(6,3,3)-纠删码为例，重构阈值为2，介绍RMLBRN方法的具体过程。节点间网络链路及带宽如图2所示，节点1～4为存活节点，节点5～6为失效节点，节点7～10为空闲节点。当系统中存在2个失效节点时，开始数据重构过程。

算法1 参与重构节点选择算法

图2 (6,3,3)-纠删码节点连接图Fig.2 Connection graph of the nodes of (6,3,3)- erasure code

首先根据节点的数据处理能力在空闲节点中选出节点9作为路由节点；然后根据路由节点与候选供应节点间的网络带宽，依次选出节点3、节点4、节点1作为供应节点；最后根据路由节点与候选新生节点间的网络带宽，选择出节点8作为新生节点，从而构成数据重构的网络拓扑，如图3所示。

图3 (6,3,3)-纠删码数据重构网络拓扑Fig.3 Data reconstruct network topology of (6,3,3)-erasure code

4 实验验证及分析

本节进行不同带宽及不同失效节点个数下，RMLBRN、TSR和B-WSJ重构方法的性能对比实验。

4.1 实验目的和指标

实验将RMLBRN与现有存储系统中常用的TSR和B-WSJ失效重构方法对比，通过数据重构时间、失效节点变化对重构时间的影响及重构成功率实验观察不同方法的性能，三种方法均采用块存储方式。数据重构时间，指重构过程开始到所有失效节点全部重构完成所经历的时间长度，是验证性能的最直接和最主要的指标；重构成功率，指在重构过程开始到重构结束时，失效块被成功完成重构的概率。在重构过程中，可能会出现供应节点或新生节点失效的情况，导致重构失败，所以重构成功率一般由成功重构的失效块数量除以所有失效块的数量。

4.2 实验环境

实验基于HDFS-RAID平台，该平台被Facebook用于解决HDFS使用多副本策略导致存储成本较大的问题，实验采用了纠删码策略。实验设置10个DataNode、1个RaidNode及1个NameNode，其中DataNode用于存放数据，RaidNode用于对数据块的编码及失效数据的重构，NameNode用于管理系统中存放的数据。实验模拟生成64 G数据，并划分为64 MB的数据块，通过编码后存放于各节点中。各节点间通过10 GB/s的万兆网交换机连接。节点失效或离线通过随机断开节点的方式进行模拟。

实验选取节点的I/O、CPU核数、主频、内存等作为衡量节点的数据处理能力，并模拟不同数值及相应权重。磁盘I/O由于占用时间较多，故分配权重为0.4；CPU核数取值范围为1～2个，占比0.3；主频取值范围为0.5～2.3 GHz，占比0.1；内存取值范围为1×32 GB～8×32 GB，占比0.2。

4.3 带宽对重构时间的影响

首先探究网络带宽的变化对RMLBRN、TSR和B-WSJ方法重构时间的影响。其中TSR方法为串行重构方法，所有参与重构的供应节点将数据按树形拓扑结构传输给新生节点进行数据重构；B-WSJ算法则在多节点失效情况下考虑节点间的最大可用带宽进行串行重构。以RS(10,5)编码策略为例，系统存在4个失效节点时开始重构。试验带宽服从均匀分布，范围为1～100 Mbit/s，实验结果采用50次实验数据的平均值。实验通过设置不同的网络条件来进行对比，实验结果如图4所示。

图4 带宽分布对重构时间的影响Fig.4 Influence of bandwidth distribution on reconstruction time

实验结果表明，当带宽波动较大时，各方法的性能均有大幅下滑。当带宽较高而且平稳时，RMLBRN重构算法的性能比B-WSJ重构算法提高了12.44%，比TSR重构算法性能提高了17.36%。当带宽分布为[1,100]时，RMLBRN重构方法较B-WSJ和TSR重构方法性能分别提高36.01%和46.67%。

4.4 失效节点数对重构时间的影响

实验在RS(10,5)编码策略下，以随机断开节点的方式模拟不同数量的失效节点。为降低带宽对重构时间的影响，固定带宽范围为90～100 Mbit/s；并根据编码的重构阈值，设定失效节点数为1～4。实验结果如图5所示。

图5 失效节点数对重构时间的影响Fig.5 Influence of the number of failed nodes on reconstruction time

从图5可知，当失效节点数由1增加到4时，B-WSJ和TSR方法的性能下降较为明显，RMLBRN方法性能较为稳定。由于TSR为串行重构，虽然简单易实现，但是针对多节点失效情况串行效率较低；B-WSJ方法虽然重构过程考虑了节点间的可用带宽，但该方法基于贪心策略，当失效节点增多时性能会随之下降。而RMLBRN算法通过选取数据处理能力最强的新生节点作为路由节点，能够提高计算的处理能力，而且选取与新生节点有最大可用带宽的存活节点作为供应节点来生成最大重构树，进行数据重构，相比TSR方法降低了串行重构的资源消耗，进一步提高了重构效率。

4.5 失效节点数对重构成功率的影响

最后验证不同失效节点数对各重构方法重构成功率的影响。为验证普遍，分别以RS(10,5)和RS(12,6)编码策略为例进行实验(也可根据具体环境选择其他RS码)，固定带宽分布为90～100 Mbit/s，降低带宽因素对重构成功率的影响，并设定失效节点数为1～4，实验结果如图6所示。

(a) RS(10,5)编码策略下失效节点数 对重构成功率的影响(a) Influence of the number of failed nodes on the success rate of reconstruction under the RS(10,5)

(b) RS(12,6)编码策略下失效节点数 对重构成功率的影响(b) Influence of the number of failed nodes on the success rate of reconstruction under the RS(12,6)图6 失效节点数对重构成功率的影响Fig.6 Influence of the number of failed nodes on the success rate of reconstruction

从图6可以看出，当失效节点数量上升时，各方法的重构成功率都出现不同程度的下降。但因为在相同失效节点数的情况下，RMLBRN方法根据路由节点与供应节点、新生节点间的最大链路带宽建立数据重构拓扑，降低了失效数据重构时间，使得节点失效概率下降，从而提高了失效节点的重构成功率。同时可以看出，B-WSJ和TSR方法重构成功率下滑程度较大，RMLBRN方法下滑幅度相对较小且一直高于B-WSJ和TSR方法。与RS(10,5)编码策略相似，RS(12,6)编码策略下三种重构方法的重构成功率也均有所下滑。但因为RMLBRN方法通过树形传输方式，规避了带宽较小的链路，提高了重构速度，因此成功率下滑较小。而且，针对数据分块较多的纠删码策略，RMLBRN方法的属性传输策略能够较为有效地提高重构效率，能够降低重构时参与重构的数据块失效的影响，提高重构成功率。

5 结论

随着数据量的急速膨胀，信息知识库存储节点失效时有发生，利用纠删码技术，能够在降低存储成本的同时，达到与副本冗余技术相同甚至更高的数据可用性及可靠性。但传统纠删码技术多为单点重构，而实际生产环境中多节点失效情况更为普遍。本文针对多节点失效情境，提出了一种RMLBRN重构方法，通过存储节点的数据处理能力选举出路由节点，并根据路由节点与其他节点间链路带宽选择出供应节点及新生节点，从而形成数据重构拓扑，在很大程度上降低了多节点失效的重构时间，且具有较高的重构成功率。实验表明，RMLBRN方法重构性能较优。本文提出的RMLBRN方法可能会构造出多个不同的数据重构拓扑，如何使网络拓扑的重构时间最短是后续研究的方向。