信息知識庫中的數據可用性恢復策略*

徐 鵬，孟宇龍,朱 群，侍守創，龔玉婷

(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方法可能會構造出多個不同的數據重構拓撲，如何使網絡拓撲的重構時間最短是后續研究的方向。