信息知識(shí)庫(kù)中的數(shù)據(jù)可用性恢復(fù)策略*

徐 鵬，孟宇龍,朱 群，侍守創(chuàng)，龔玉婷

(1. 中國(guó)船舶重工集團(tuán)公司第七一六研究所 江蘇杰瑞科技集團(tuán)有限責(zé)任公司， 江蘇 連云港 222002；2. 哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 黑龍江 哈爾濱 150001)

相比于傳統(tǒng)數(shù)據(jù)庫(kù)，信息知識(shí)庫(kù)不僅包含了大量的數(shù)據(jù)，還包含了規(guī)則和過(guò)程性知識(shí)，信息化地從知識(shí)庫(kù)中提取數(shù)據(jù)，能夠有效提高生產(chǎn)效率[1]。由于數(shù)據(jù)的不斷積累及爆發(fā)式的增加，知識(shí)庫(kù)的存儲(chǔ)節(jié)點(diǎn)數(shù)量也隨之不斷膨脹。為控制成本，大規(guī)模的知識(shí)庫(kù)存儲(chǔ)系統(tǒng)的搭建一般選用廉價(jià)的存儲(chǔ)服務(wù)器，當(dāng)設(shè)備離線或故障時(shí)，存儲(chǔ)節(jié)點(diǎn)失效，數(shù)據(jù)丟失[2]，故保證知識(shí)庫(kù)數(shù)據(jù)的可靠性和完整性至關(guān)重要。

現(xiàn)有保證數(shù)據(jù)可靠性及完整性的方式主要包括副本冗余[3]與糾刪碼[4]，副本冗余技術(shù)成本隨

數(shù)據(jù)量的增大而不斷提高，糾刪碼技術(shù)可以在存儲(chǔ)成本低于副本冗余技術(shù)的前提下，獲得相同或更高的數(shù)據(jù)可靠性及完整性[5-6]，但其失效數(shù)據(jù)重構(gòu)過(guò)程的數(shù)據(jù)傳輸會(huì)造成較多的網(wǎng)絡(luò)資源消耗，且重構(gòu)速度有待提高。如何提高糾刪碼的失效數(shù)據(jù)重構(gòu)性能成為研究熱點(diǎn)。傳統(tǒng)糾刪碼數(shù)據(jù)重構(gòu)采用供應(yīng)節(jié)點(diǎn)與新生節(jié)點(diǎn)數(shù)據(jù)直接傳輸?shù)姆绞?，該方式瓶頸取決于供應(yīng)節(jié)點(diǎn)與新生節(jié)點(diǎn)間網(wǎng)絡(luò)狀況最差的一條鏈路，對(duì)整體重構(gòu)性能影響嚴(yán)重。針對(duì)該問(wèn)題，Li等[7-8]以樹形拓?fù)浣Y(jié)構(gòu)代替節(jié)點(diǎn)直連方式，該方式將新生節(jié)點(diǎn)作為重構(gòu)拓?fù)涞母?jié)點(diǎn)，參與重構(gòu)的供應(yīng)節(jié)點(diǎn)作為葉節(jié)點(diǎn)，葉節(jié)點(diǎn)數(shù)據(jù)經(jīng)過(guò)計(jì)算處理后上傳至父節(jié)點(diǎn)。當(dāng)上級(jí)節(jié)點(diǎn)獲取到數(shù)據(jù)后，與本節(jié)點(diǎn)數(shù)據(jù)按照算法進(jìn)行計(jì)算，然后向其父節(jié)點(diǎn)發(fā)送計(jì)算結(jié)果，依照該方法遞歸至根節(jié)點(diǎn)，重構(gòu)過(guò)程結(jié)束。樹形重構(gòu)方法雖然一定程度上降低了傳輸鏈路瓶頸對(duì)重構(gòu)效率的影響，但是數(shù)據(jù)完整性較差。

在實(shí)際生產(chǎn)環(huán)境中，當(dāng)有單個(gè)存儲(chǔ)節(jié)點(diǎn)失效時(shí)，系統(tǒng)并不會(huì)立即進(jìn)行數(shù)據(jù)恢復(fù)，而是在達(dá)到指定失效節(jié)點(diǎn)數(shù)量或設(shè)定時(shí)間時(shí)開始重構(gòu)[9-10]，多節(jié)點(diǎn)失效情況下星形及樹形重構(gòu)方式性能下降嚴(yán)重?；诙喙?jié)點(diǎn)失效情形，本文提出鏈路帶寬和路由節(jié)點(diǎn)的重構(gòu)方法 (Reconstruction Method based on Link Bandwidth and Routing Node，RMLBRN)，首先根據(jù)節(jié)點(diǎn)的數(shù)據(jù)處理能力從候選新生節(jié)點(diǎn)中選舉出路由節(jié)點(diǎn)，然后根據(jù)路由節(jié)點(diǎn)與候選供應(yīng)節(jié)點(diǎn)間鏈路帶寬選出供應(yīng)節(jié)點(diǎn)，根據(jù)路由節(jié)點(diǎn)與候選新生節(jié)點(diǎn)間帶寬確定新生節(jié)點(diǎn)，從而構(gòu)成失效數(shù)據(jù)重構(gòu)的網(wǎng)絡(luò)拓?fù)洹Ｔ诼酚晒?jié)點(diǎn)接收供應(yīng)節(jié)點(diǎn)數(shù)據(jù)重構(gòu)出失效數(shù)據(jù)后，發(fā)送至新生節(jié)點(diǎn)，完成數(shù)據(jù)重構(gòu)，從而有效降低重構(gòu)時(shí)間。

1 研究現(xiàn)狀

文獻(xiàn)[11-12]提出了Regenerating Codes，該方法不僅滿足了最大可分離碼的性質(zhì)，而且引入了網(wǎng)絡(luò)編碼來(lái)優(yōu)化重構(gòu)帶寬。在重構(gòu)過(guò)程中，選取盡可能多的節(jié)點(diǎn)參與重構(gòu)，降低了重構(gòu)過(guò)程中帶寬的消耗。但該方法限制每個(gè)供應(yīng)節(jié)點(diǎn)必須向新生節(jié)點(diǎn)傳輸?shù)攘繑?shù)據(jù)，使得新生節(jié)點(diǎn)可選擇使用的鏈路受限，無(wú)法利用其中具有較高帶寬的鏈路資源，從而重構(gòu)時(shí)間較長(zhǎng)。文獻(xiàn)[13]基于樹形重構(gòu)方法對(duì)節(jié)點(diǎn)間帶寬進(jìn)行排序，并優(yōu)先選取可用帶寬較好的節(jié)點(diǎn)參與重構(gòu)過(guò)程，降低了數(shù)據(jù)傳輸對(duì)重構(gòu)性能的影響，但該重構(gòu)方法為貪心策略，時(shí)空復(fù)雜度會(huì)隨存儲(chǔ)系統(tǒng)節(jié)點(diǎn)增多而不斷提高。文獻(xiàn)[14]通過(guò)避免使用上一次重構(gòu)時(shí)帶寬最小的鏈路來(lái)改善重構(gòu)時(shí)間，但該方法性能隨重構(gòu)次數(shù)增加而下降，且在多節(jié)點(diǎn)失效情況下性能下降更加明顯。

針對(duì)存儲(chǔ)系統(tǒng)中存在多個(gè)失效節(jié)點(diǎn)的問(wèn)題，文獻(xiàn)[15]中將糾刪碼參與重構(gòu)節(jié)點(diǎn)的數(shù)據(jù)劃分至不同的塊中，重構(gòu)過(guò)程中各節(jié)點(diǎn)根據(jù)所在塊完成相應(yīng)任務(wù)，相較單節(jié)點(diǎn)重構(gòu)有更高的重構(gòu)速率，但該重構(gòu)策略時(shí)間復(fù)雜度較高；基于星形結(jié)構(gòu)的串行修復(fù)策略[16](Star Structure based serial Repair, SSR)與基于樹形結(jié)構(gòu)的串行修復(fù)策略[17](Tree structure based serial Repair, TSR)采用串行方式重構(gòu)失效數(shù)據(jù)，重構(gòu)時(shí)間較長(zhǎng)且占用網(wǎng)絡(luò)資源較多；文獻(xiàn)[18]針對(duì)現(xiàn)有多節(jié)點(diǎn)重構(gòu)方案未考慮新生節(jié)點(diǎn)間的數(shù)據(jù)傳輸問(wèn)題，提出了基于帶寬的節(jié)點(diǎn)選擇策略(Bandwidth based Weak and Strong Judgement, B-WSJ)，考慮新生節(jié)點(diǎn)間信息傳輸，可以降低重構(gòu)時(shí)間，但仍為串行重構(gòu)，且在判斷新生節(jié)點(diǎn)間數(shù)據(jù)傳輸時(shí)會(huì)增加重構(gòu)時(shí)間；文獻(xiàn)[19]從節(jié)點(diǎn)間網(wǎng)絡(luò)距離角度出發(fā)，通過(guò)統(tǒng)計(jì)各供應(yīng)節(jié)點(diǎn)與新生節(jié)點(diǎn)間的網(wǎng)絡(luò)距離，找出網(wǎng)絡(luò)距離總和最小的鏈路進(jìn)行重構(gòu)，以此降低重構(gòu)時(shí)間，但該方法并未考慮實(shí)時(shí)帶寬及鏈路情況變化。

2 問(wèn)題描述

一般以(n,k,d)-糾刪碼代表將數(shù)據(jù)對(duì)象劃分為k個(gè)大小完全一致的數(shù)據(jù)塊，通過(guò)對(duì)該k個(gè)數(shù)據(jù)塊進(jìn)行糾刪碼編碼生成n(n>k)個(gè)大小相同的編碼塊的糾刪碼，當(dāng)有任意d(d≥k)個(gè)編碼塊存活時(shí)，通過(guò)解碼運(yùn)算即可恢復(fù)失效數(shù)據(jù)或原有數(shù)據(jù)。以(6, 3, 3)-糾刪碼為例，首先將數(shù)據(jù)對(duì)象分為3個(gè)數(shù)據(jù)量完全一致的數(shù)據(jù)塊B1、B2、B3,根據(jù)編碼規(guī)則對(duì)3個(gè)數(shù)據(jù)塊進(jìn)行編碼生成C1、C2、C33個(gè)編碼塊，大小與數(shù)據(jù)塊相同。分別將每個(gè)塊存放于不同的節(jié)點(diǎn)，根據(jù)最大可分離性質(zhì)，當(dāng)系統(tǒng)中有少于等于3個(gè)失效塊時(shí)，便可恢復(fù)出失效數(shù)據(jù)。劃分及編碼過(guò)程如圖1所示。

圖1 (6, 3, 3)-糾刪碼Fig.1 (6, 3, 3)-erasure code

假設(shè)系統(tǒng)設(shè)定當(dāng)存在兩個(gè)失效節(jié)點(diǎn)時(shí)，開始重構(gòu)失效數(shù)據(jù)。以SSR方法與TSR方法為例，當(dāng)系統(tǒng)進(jìn)行重構(gòu)時(shí)，會(huì)在存活的空閑節(jié)點(diǎn)中隨機(jī)選取2個(gè)供應(yīng)節(jié)點(diǎn)作為新生節(jié)點(diǎn)，存活的數(shù)據(jù)節(jié)點(diǎn)和編碼節(jié)點(diǎn)向其傳輸該節(jié)點(diǎn)的所有數(shù)據(jù)并進(jìn)行重構(gòu)。傳統(tǒng)重構(gòu)方法在選擇新生節(jié)點(diǎn)時(shí)并未考慮與供應(yīng)節(jié)點(diǎn)間的鏈路帶寬，性能上有較大瓶頸；在重構(gòu)時(shí)每個(gè)節(jié)點(diǎn)傳輸該節(jié)點(diǎn)的所有數(shù)據(jù)，數(shù)據(jù)冗余較大，占用了較多的網(wǎng)絡(luò)資源，資源消耗嚴(yán)重。

針對(duì)多節(jié)點(diǎn)失效情況，本文提出了RMLBRN算法。該方法首先根據(jù)新生節(jié)點(diǎn)的數(shù)據(jù)處理能力，選擇出負(fù)責(zé)接收、計(jì)算并傳輸數(shù)據(jù)的路由節(jié)點(diǎn)；然后選取與路由節(jié)點(diǎn)可用帶寬較大的供應(yīng)節(jié)點(diǎn)及新生節(jié)點(diǎn)參與重構(gòu)過(guò)程，生成最大可用帶寬重構(gòu)拓?fù)?，?lái)提高多節(jié)點(diǎn)失效時(shí)的重構(gòu)效率。

3 算法及分析

3.1 選舉路由節(jié)點(diǎn)

由于系統(tǒng)中各節(jié)點(diǎn)性能存在差異，磁盤的I/O、內(nèi)核數(shù)目、內(nèi)存型號(hào)、芯片型號(hào)、硬盤的緩存和轉(zhuǎn)速以及CPU 的主頻等都有可能是導(dǎo)致節(jié)點(diǎn)能力異構(gòu)的因素。所有節(jié)點(diǎn)不可能一成不變，在經(jīng)過(guò)一段時(shí)間的使用之后，節(jié)點(diǎn)的一些性能也會(huì)隨時(shí)間而改變，需通過(guò)及時(shí)更新節(jié)點(diǎn)數(shù)據(jù)處理能力來(lái)保證實(shí)驗(yàn)參數(shù)的準(zhǔn)確性。在分析過(guò)后，本節(jié)以以下衡量標(biāo)準(zhǔn)定義節(jié)點(diǎn)的數(shù)據(jù)處理能力：首先根據(jù)節(jié)點(diǎn)的主要決定因素初始化節(jié)點(diǎn)的數(shù)據(jù)處理能力，然后根據(jù)每次系統(tǒng)的設(shè)定改變，或者以一次完整重構(gòu)時(shí)間為基數(shù)，經(jīng)加權(quán)計(jì)算后更新該節(jié)點(diǎn)性能。

以(n,k,d)-糾刪碼為例，當(dāng)系統(tǒng)存在r(r≤n-d)個(gè)失效節(jié)點(diǎn)時(shí)，開始重構(gòu)失效數(shù)據(jù)。假設(shè)該系統(tǒng)共包含N個(gè)存儲(chǔ)節(jié)點(diǎn)，其中n-r個(gè)供應(yīng)節(jié)點(diǎn)需進(jìn)行數(shù)據(jù)讀取、編碼及上報(bào)，節(jié)點(diǎn)壓力較大，故在剩余N-n個(gè)節(jié)點(diǎn)中選擇r個(gè)空閑節(jié)點(diǎn)作為新生節(jié)點(diǎn)。

首先選取磁盤I/O、CPU核數(shù)、主頻、內(nèi)存大小等作為衡量節(jié)點(diǎn)數(shù)據(jù)處理能力的標(biāo)準(zhǔn)。分別用α表示節(jié)點(diǎn)的磁盤I/O，β表示CPU核數(shù)，γ表示節(jié)點(diǎn)主頻，θ表示節(jié)點(diǎn)內(nèi)存，同時(shí)以cα、cβ、cγ、cθ表示四項(xiàng)標(biāo)準(zhǔn)的加權(quán)參數(shù)，并滿足cα+cβ+cγ+cθ=1，則節(jié)點(diǎn)i的數(shù)據(jù)處理能力可表示為：

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

(1)

假設(shè)節(jié)點(diǎn)i在重構(gòu)過(guò)程中參與的數(shù)據(jù)讀取、編碼等操作的總計(jì)算量為Pi，則節(jié)點(diǎn)i參與重構(gòu)的總時(shí)間為：

t=T(Pi/Si)

(2)

其中函數(shù)T(·)將計(jì)算結(jié)果轉(zhuǎn)換為時(shí)間單位(s)，以便后續(xù)處理，其轉(zhuǎn)換結(jié)果與節(jié)點(diǎn)數(shù)據(jù)處理能力成反比。

針對(duì)節(jié)點(diǎn)狀態(tài)的變化對(duì)數(shù)據(jù)處理能力的影響，在式(2)初始化節(jié)點(diǎn)的數(shù)據(jù)處理能力后，當(dāng)達(dá)到設(shè)定的時(shí)間閾值或數(shù)據(jù)重構(gòu)后，更新節(jié)點(diǎn)的數(shù)據(jù)處理能力。以ni,t表示節(jié)點(diǎn)i本次參與重構(gòu)消耗的時(shí)間，li,t表示節(jié)點(diǎn)i上一次參與重構(gòu)消耗的時(shí)間，單位均為s，則更新節(jié)點(diǎn)i的參與重構(gòu)時(shí)間為：

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

(3)

式中，a(0≤a≤1)為上次參與重構(gòu)時(shí)間的權(quán)重。通過(guò)式(3)，節(jié)點(diǎn)i的數(shù)據(jù)處理能力與重構(gòu)時(shí)間建立關(guān)系，并成反比。當(dāng)路由節(jié)點(diǎn)數(shù)據(jù)處理能力越強(qiáng)時(shí)，系統(tǒng)重構(gòu)效率越高。

3.2 選擇參與重構(gòu)的節(jié)點(diǎn)

在選擇參與重構(gòu)的供應(yīng)節(jié)點(diǎn)時(shí)，首先需要獲取存活節(jié)點(diǎn)與新生節(jié)點(diǎn)間的可用帶寬大小，然后按照最大生成樹原理，依次選取與新生節(jié)點(diǎn)有最大可用帶寬的存活節(jié)點(diǎn)作為供應(yīng)節(jié)點(diǎn)，直到供應(yīng)節(jié)點(diǎn)數(shù)量滿足所選糾刪碼策略的重構(gòu)要求為止。

由于測(cè)量各節(jié)點(diǎn)間鏈路帶寬僅需2～4個(gè)往返時(shí)延[20]，相對(duì)重構(gòu)過(guò)程影響可忽略，且短時(shí)間內(nèi)帶寬波動(dòng)較小，因此在數(shù)據(jù)重構(gòu)期間可將帶寬設(shè)置為固定值[21-22]。假設(shè)各參與重構(gòu)節(jié)點(diǎn)的數(shù)據(jù)傳輸量均為d。具體供應(yīng)節(jié)點(diǎn)選擇步驟如下。

以(n,k,d)-糾刪碼為例，重構(gòu)閾值為r(r≤n-d)，引入供應(yīng)節(jié)點(diǎn)集合Cc及新生節(jié)點(diǎn)集合Cn，用以存放參與失效數(shù)據(jù)重構(gòu)的供應(yīng)節(jié)點(diǎn)及新生節(jié)點(diǎn)。首先從空閑新生節(jié)點(diǎn)中根據(jù)節(jié)點(diǎn)的數(shù)據(jù)處理性能選擇路由節(jié)點(diǎn)Nc，放入集合Cn。

引入邊集Ec={e0,e1,…,en-r-1}表示路由節(jié)點(diǎn)與候選供應(yīng)節(jié)點(diǎn)間的鏈路，其值代表數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)帶寬，值為0表示節(jié)點(diǎn)間無(wú)鏈路連接。算法根據(jù)路由節(jié)點(diǎn)與候選供應(yīng)節(jié)點(diǎn)的邊集Ec依次選擇具有鏈路帶寬的節(jié)點(diǎn)，確定為供應(yīng)節(jié)點(diǎn)，將該點(diǎn)存入集合Cc中并從邊集中刪去該鏈路，根據(jù)此方法選出共d個(gè)供應(yīng)節(jié)點(diǎn)截止。

供應(yīng)節(jié)點(diǎn)確定后，需在空閑節(jié)點(diǎn)中選擇剩余r-1個(gè)新生節(jié)點(diǎn)。引入邊集En={e0,e1,…,eN-n-2}表示路由節(jié)點(diǎn)與候選新生節(jié)點(diǎn)間的鏈路，其值代表數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)帶寬，值為0表示節(jié)點(diǎn)間無(wú)鏈路連接。算法根據(jù)路由節(jié)點(diǎn)與候選節(jié)點(diǎn)的邊集En依次選擇具有鏈路帶寬的節(jié)點(diǎn)，確定為新生節(jié)點(diǎn)，將該點(diǎn)存入集合Cn中并從邊集中刪去該鏈路，根據(jù)此方法選出共r-1個(gè)新生節(jié)點(diǎn)截止，從而構(gòu)成以路由節(jié)點(diǎn)為中心的數(shù)據(jù)重構(gòu)網(wǎng)絡(luò)拓?fù)?。參與重構(gòu)的節(jié)點(diǎn)選擇算法如算法1所示。

以(6,3,3)-糾刪碼為例，重構(gòu)閾值為2，介紹RMLBRN方法的具體過(guò)程。節(jié)點(diǎn)間網(wǎng)絡(luò)鏈路及帶寬如圖2所示，節(jié)點(diǎn)1～4為存活節(jié)點(diǎn)，節(jié)點(diǎn)5～6為失效節(jié)點(diǎn)，節(jié)點(diǎn)7～10為空閑節(jié)點(diǎn)。當(dāng)系統(tǒng)中存在2個(gè)失效節(jié)點(diǎn)時(shí)，開始數(shù)據(jù)重構(gòu)過(guò)程。

算法1 參與重構(gòu)節(jié)點(diǎn)選擇算法

圖2 (6,3,3)-糾刪碼節(jié)點(diǎn)連接圖Fig.2 Connection graph of the nodes of (6,3,3)- erasure code

首先根據(jù)節(jié)點(diǎn)的數(shù)據(jù)處理能力在空閑節(jié)點(diǎn)中選出節(jié)點(diǎn)9作為路由節(jié)點(diǎn)；然后根據(jù)路由節(jié)點(diǎn)與候選供應(yīng)節(jié)點(diǎn)間的網(wǎng)絡(luò)帶寬，依次選出節(jié)點(diǎn)3、節(jié)點(diǎn)4、節(jié)點(diǎn)1作為供應(yīng)節(jié)點(diǎn)；最后根據(jù)路由節(jié)點(diǎn)與候選新生節(jié)點(diǎn)間的網(wǎng)絡(luò)帶寬，選擇出節(jié)點(diǎn)8作為新生節(jié)點(diǎn)，從而構(gòu)成數(shù)據(jù)重構(gòu)的網(wǎng)絡(luò)拓?fù)?，如圖3所示。

圖3 (6,3,3)-糾刪碼數(shù)據(jù)重構(gòu)網(wǎng)絡(luò)拓?fù)銯ig.3 Data reconstruct network topology of (6,3,3)-erasure code

4 實(shí)驗(yàn)驗(yàn)證及分析

本節(jié)進(jìn)行不同帶寬及不同失效節(jié)點(diǎn)個(gè)數(shù)下，RMLBRN、TSR和B-WSJ重構(gòu)方法的性能對(duì)比實(shí)驗(yàn)。

4.1 實(shí)驗(yàn)?zāi)康暮椭笜?biāo)

實(shí)驗(yàn)將RMLBRN與現(xiàn)有存儲(chǔ)系統(tǒng)中常用的TSR和B-WSJ失效重構(gòu)方法對(duì)比，通過(guò)數(shù)據(jù)重構(gòu)時(shí)間、失效節(jié)點(diǎn)變化對(duì)重構(gòu)時(shí)間的影響及重構(gòu)成功率實(shí)驗(yàn)觀察不同方法的性能，三種方法均采用塊存儲(chǔ)方式。數(shù)據(jù)重構(gòu)時(shí)間，指重構(gòu)過(guò)程開始到所有失效節(jié)點(diǎn)全部重構(gòu)完成所經(jīng)歷的時(shí)間長(zhǎng)度，是驗(yàn)證性能的最直接和最主要的指標(biāo)；重構(gòu)成功率，指在重構(gòu)過(guò)程開始到重構(gòu)結(jié)束時(shí)，失效塊被成功完成重構(gòu)的概率。在重構(gòu)過(guò)程中，可能會(huì)出現(xiàn)供應(yīng)節(jié)點(diǎn)或新生節(jié)點(diǎn)失效的情況，導(dǎo)致重構(gòu)失敗，所以重構(gòu)成功率一般由成功重構(gòu)的失效塊數(shù)量除以所有失效塊的數(shù)量。

4.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)基于HDFS-RAID平臺(tái)，該平臺(tái)被Facebook用于解決HDFS使用多副本策略導(dǎo)致存儲(chǔ)成本較大的問(wèn)題，實(shí)驗(yàn)采用了糾刪碼策略。實(shí)驗(yàn)設(shè)置10個(gè)DataNode、1個(gè)RaidNode及1個(gè)NameNode，其中DataNode用于存放數(shù)據(jù)，RaidNode用于對(duì)數(shù)據(jù)塊的編碼及失效數(shù)據(jù)的重構(gòu)，NameNode用于管理系統(tǒng)中存放的數(shù)據(jù)。實(shí)驗(yàn)?zāi)M生成64 G數(shù)據(jù)，并劃分為64 MB的數(shù)據(jù)塊，通過(guò)編碼后存放于各節(jié)點(diǎn)中。各節(jié)點(diǎn)間通過(guò)10 GB/s的萬(wàn)兆網(wǎng)交換機(jī)連接。節(jié)點(diǎn)失效或離線通過(guò)隨機(jī)斷開節(jié)點(diǎn)的方式進(jìn)行模擬。

實(shí)驗(yàn)選取節(jié)點(diǎn)的I/O、CPU核數(shù)、主頻、內(nèi)存等作為衡量節(jié)點(diǎn)的數(shù)據(jù)處理能力，并模擬不同數(shù)值及相應(yīng)權(quán)重。磁盤I/O由于占用時(shí)間較多，故分配權(quán)重為0.4；CPU核數(shù)取值范圍為1～2個(gè)，占比0.3；主頻取值范圍為0.5～2.3 GHz，占比0.1；內(nèi)存取值范圍為1×32 GB～8×32 GB，占比0.2。

4.3 帶寬對(duì)重構(gòu)時(shí)間的影響

首先探究網(wǎng)絡(luò)帶寬的變化對(duì)RMLBRN、TSR和B-WSJ方法重構(gòu)時(shí)間的影響。其中TSR方法為串行重構(gòu)方法，所有參與重構(gòu)的供應(yīng)節(jié)點(diǎn)將數(shù)據(jù)按樹形拓?fù)浣Y(jié)構(gòu)傳輸給新生節(jié)點(diǎn)進(jìn)行數(shù)據(jù)重構(gòu)；B-WSJ算法則在多節(jié)點(diǎn)失效情況下考慮節(jié)點(diǎn)間的最大可用帶寬進(jìn)行串行重構(gòu)。以RS(10,5)編碼策略為例，系統(tǒng)存在4個(gè)失效節(jié)點(diǎn)時(shí)開始重構(gòu)。試驗(yàn)帶寬服從均勻分布，范圍為1～100 Mbit/s，實(shí)驗(yàn)結(jié)果采用50次實(shí)驗(yàn)數(shù)據(jù)的平均值。實(shí)驗(yàn)通過(guò)設(shè)置不同的網(wǎng)絡(luò)條件來(lái)進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 帶寬分布對(duì)重構(gòu)時(shí)間的影響Fig.4 Influence of bandwidth distribution on reconstruction time

實(shí)驗(yàn)結(jié)果表明，當(dāng)帶寬波動(dòng)較大時(shí)，各方法的性能均有大幅下滑。當(dāng)帶寬較高而且平穩(wěn)時(shí)，RMLBRN重構(gòu)算法的性能比B-WSJ重構(gòu)算法提高了12.44%，比TSR重構(gòu)算法性能提高了17.36%。當(dāng)帶寬分布為[1,100]時(shí)，RMLBRN重構(gòu)方法較B-WSJ和TSR重構(gòu)方法性能分別提高36.01%和46.67%。

4.4 失效節(jié)點(diǎn)數(shù)對(duì)重構(gòu)時(shí)間的影響

實(shí)驗(yàn)在RS(10,5)編碼策略下，以隨機(jī)斷開節(jié)點(diǎn)的方式模擬不同數(shù)量的失效節(jié)點(diǎn)。為降低帶寬對(duì)重構(gòu)時(shí)間的影響，固定帶寬范圍為90～100 Mbit/s；并根據(jù)編碼的重構(gòu)閾值，設(shè)定失效節(jié)點(diǎn)數(shù)為1～4。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 失效節(jié)點(diǎn)數(shù)對(duì)重構(gòu)時(shí)間的影響Fig.5 Influence of the number of failed nodes on reconstruction time

從圖5可知，當(dāng)失效節(jié)點(diǎn)數(shù)由1增加到4時(shí)，B-WSJ和TSR方法的性能下降較為明顯，RMLBRN方法性能較為穩(wěn)定。由于TSR為串行重構(gòu)，雖然簡(jiǎn)單易實(shí)現(xiàn)，但是針對(duì)多節(jié)點(diǎn)失效情況串行效率較低；B-WSJ方法雖然重構(gòu)過(guò)程考慮了節(jié)點(diǎn)間的可用帶寬，但該方法基于貪心策略，當(dāng)失效節(jié)點(diǎn)增多時(shí)性能會(huì)隨之下降。而RMLBRN算法通過(guò)選取數(shù)據(jù)處理能力最強(qiáng)的新生節(jié)點(diǎn)作為路由節(jié)點(diǎn)，能夠提高計(jì)算的處理能力，而且選取與新生節(jié)點(diǎn)有最大可用帶寬的存活節(jié)點(diǎn)作為供應(yīng)節(jié)點(diǎn)來(lái)生成最大重構(gòu)樹，進(jìn)行數(shù)據(jù)重構(gòu)，相比TSR方法降低了串行重構(gòu)的資源消耗，進(jìn)一步提高了重構(gòu)效率。

4.5 失效節(jié)點(diǎn)數(shù)對(duì)重構(gòu)成功率的影響

最后驗(yàn)證不同失效節(jié)點(diǎn)數(shù)對(duì)各重構(gòu)方法重構(gòu)成功率的影響。為驗(yàn)證普遍，分別以RS(10,5)和RS(12,6)編碼策略為例進(jìn)行實(shí)驗(yàn)(也可根據(jù)具體環(huán)境選擇其他RS碼)，固定帶寬分布為90～100 Mbit/s，降低帶寬因素對(duì)重構(gòu)成功率的影響，并設(shè)定失效節(jié)點(diǎn)數(shù)為1～4，實(shí)驗(yàn)結(jié)果如圖6所示。

(a) RS(10,5)編碼策略下失效節(jié)點(diǎn)數(shù) 對(duì)重構(gòu)成功率的影響(a) Influence of the number of failed nodes on the success rate of reconstruction under the RS(10,5)

(b) RS(12,6)編碼策略下失效節(jié)點(diǎn)數(shù) 對(duì)重構(gòu)成功率的影響(b) Influence of the number of failed nodes on the success rate of reconstruction under the RS(12,6)圖6 失效節(jié)點(diǎn)數(shù)對(duì)重構(gòu)成功率的影響Fig.6 Influence of the number of failed nodes on the success rate of reconstruction

從圖6可以看出，當(dāng)失效節(jié)點(diǎn)數(shù)量上升時(shí)，各方法的重構(gòu)成功率都出現(xiàn)不同程度的下降。但因?yàn)樵谙嗤Ч?jié)點(diǎn)數(shù)的情況下，RMLBRN方法根據(jù)路由節(jié)點(diǎn)與供應(yīng)節(jié)點(diǎn)、新生節(jié)點(diǎn)間的最大鏈路帶寬建立數(shù)據(jù)重構(gòu)拓?fù)?，降低了失效?shù)據(jù)重構(gòu)時(shí)間，使得節(jié)點(diǎn)失效概率下降，從而提高了失效節(jié)點(diǎn)的重構(gòu)成功率。同時(shí)可以看出，B-WSJ和TSR方法重構(gòu)成功率下滑程度較大，RMLBRN方法下滑幅度相對(duì)較小且一直高于B-WSJ和TSR方法。與RS(10,5)編碼策略相似，RS(12,6)編碼策略下三種重構(gòu)方法的重構(gòu)成功率也均有所下滑。但因?yàn)镽MLBRN方法通過(guò)樹形傳輸方式，規(guī)避了帶寬較小的鏈路，提高了重構(gòu)速度，因此成功率下滑較小。而且，針對(duì)數(shù)據(jù)分塊較多的糾刪碼策略，RMLBRN方法的屬性傳輸策略能夠較為有效地提高重構(gòu)效率，能夠降低重構(gòu)時(shí)參與重構(gòu)的數(shù)據(jù)塊失效的影響，提高重構(gòu)成功率。

5 結(jié)論

隨著數(shù)據(jù)量的急速膨脹，信息知識(shí)庫(kù)存儲(chǔ)節(jié)點(diǎn)失效時(shí)有發(fā)生，利用糾刪碼技術(shù)，能夠在降低存儲(chǔ)成本的同時(shí)，達(dá)到與副本冗余技術(shù)相同甚至更高的數(shù)據(jù)可用性及可靠性。但傳統(tǒng)糾刪碼技術(shù)多為單點(diǎn)重構(gòu)，而實(shí)際生產(chǎn)環(huán)境中多節(jié)點(diǎn)失效情況更為普遍。本文針對(duì)多節(jié)點(diǎn)失效情境，提出了一種RMLBRN重構(gòu)方法，通過(guò)存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)處理能力選舉出路由節(jié)點(diǎn)，并根據(jù)路由節(jié)點(diǎn)與其他節(jié)點(diǎn)間鏈路帶寬選擇出供應(yīng)節(jié)點(diǎn)及新生節(jié)點(diǎn)，從而形成數(shù)據(jù)重構(gòu)拓?fù)洌诤艽蟪潭壬辖档土硕喙?jié)點(diǎn)失效的重構(gòu)時(shí)間，且具有較高的重構(gòu)成功率。實(shí)驗(yàn)表明，RMLBRN方法重構(gòu)性能較優(yōu)。本文提出的RMLBRN方法可能會(huì)構(gòu)造出多個(gè)不同的數(shù)據(jù)重構(gòu)拓?fù)?，如何使網(wǎng)絡(luò)拓?fù)涞闹貥?gòu)時(shí)間最短是后續(xù)研究的方向。