一種基于分布式存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)修復(fù)的節(jié)點(diǎn)選擇算法

劉 佩 蔣梓逸 曹 袖

1(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201203) 2 (網(wǎng)絡(luò)信息安全審計(jì)與監(jiān)控教育部工程研究中心(復(fù)旦大學(xué)) 上海 200433) (13210240020@fudan.edu.cn)

隨著云計(jì)算和“互聯(lián)網(wǎng)+”應(yīng)用的普及，分布式存儲(chǔ)系統(tǒng)在各行各業(yè)中得到廣泛的應(yīng)用，用戶訪問不良特征和系統(tǒng)軟硬件的錯(cuò)誤導(dǎo)致節(jié)點(diǎn)的失效非常之多.Kondo等人[1]跟蹤27個(gè)不同規(guī)模系統(tǒng)在一段時(shí)間內(nèi)的節(jié)點(diǎn)失效狀況，并給出了的真實(shí)失效數(shù)據(jù)集FTA(failure trace archive)，如微軟公司的桌面計(jì)算機(jī)系統(tǒng)數(shù)據(jù)集Microsoft99、P2P系統(tǒng)PlanetLab的數(shù)據(jù)集、高性能計(jì)算機(jī)PNNL等.本文通過用Mysql和Matlab對(duì)所得到的數(shù)據(jù)進(jìn)行分析和統(tǒng)計(jì)得到云存儲(chǔ)中節(jié)點(diǎn)的失效情況，經(jīng)過歸一化處理得到平均每個(gè)系統(tǒng)每周內(nèi)的失效率為60.29%.從FTA中可以看出節(jié)點(diǎn)的失效率是非常高的，如何保證系統(tǒng)的可靠性是一項(xiàng)非常重要的課題.

為了提高分布式存儲(chǔ)系統(tǒng)的可靠性，系統(tǒng)通常引入良好的數(shù)據(jù)冗余機(jī)制和數(shù)據(jù)修復(fù)策略.經(jīng)典的冗余方式為副本機(jī)制[2]，例如HDFS[2]系統(tǒng)和Ceph[3]系統(tǒng).在大數(shù)據(jù)時(shí)代，因糾刪碼(erasure coding)比副本機(jī)制具有更低的存儲(chǔ)成本，廣泛應(yīng)用于實(shí)際系統(tǒng)中[4-5].當(dāng)系統(tǒng)發(fā)生節(jié)點(diǎn)失效時(shí)，保證持續(xù)的可靠性，系統(tǒng)需要將失效節(jié)點(diǎn)上的數(shù)據(jù)重新修復(fù)到新的節(jié)點(diǎn)上.修復(fù)時(shí)提供數(shù)據(jù)下載的存活節(jié)點(diǎn)稱為供應(yīng)節(jié)點(diǎn)，修復(fù)時(shí)存儲(chǔ)再生數(shù)據(jù)的新節(jié)點(diǎn)稱為新生節(jié)點(diǎn).傳統(tǒng)糾刪碼方式的失效數(shù)據(jù)修復(fù)需要先將源文件恢復(fù)出來，因此會(huì)引入不必要的修復(fù)帶寬開銷[6].在此基礎(chǔ)之上，Dimakis等人[7]通過研究節(jié)點(diǎn)存儲(chǔ)開銷和修復(fù)帶寬開銷之間的關(guān)系，提出了再生碼，其可以下載比糾刪碼更少的數(shù)據(jù)塊把失效的數(shù)據(jù)再生出來.在擁有相似的存儲(chǔ)效率的情況下，再生碼可以很好地降低數(shù)據(jù)修復(fù)時(shí)的修復(fù)帶寬(數(shù)據(jù)傳輸量)[8].

Fig. 1 The performance of data repair progress with different methods圖1 數(shù)據(jù)修復(fù)過程中不同優(yōu)化方法的性能

存儲(chǔ)系統(tǒng)的修復(fù)過程中默認(rèn)參與修復(fù)的節(jié)點(diǎn)已經(jīng)給定，傳統(tǒng)的算法包括具有隨機(jī)性的BHS(blind helper selection)算法和SHS[10](static helper selection)算法.Gong等人[11]首次提出了單個(gè)節(jié)點(diǎn)失效場(chǎng)景下的最優(yōu)節(jié)點(diǎn)選擇機(jī)制SPSN(select provider select newcomer).其本質(zhì)為貪心算法，對(duì)已有帶寬進(jìn)行排序之后，優(yōu)先選擇帶寬較大的節(jié)點(diǎn)進(jìn)行傳輸數(shù)據(jù)，從而降低了數(shù)據(jù)的修復(fù)時(shí)間.

理論研究和實(shí)際系統(tǒng)中，往往存在多個(gè)節(jié)點(diǎn)同時(shí)修復(fù)(也叫延遲修復(fù))的情況.此時(shí)SPSN算法由于具有串行選擇的特征而不再最優(yōu).隨著系統(tǒng)中節(jié)點(diǎn)失效規(guī)模的擴(kuò)大，這將給數(shù)據(jù)修復(fù)帶來很大的時(shí)間開銷和空間開銷.基于這些問題，本文提出了多節(jié)點(diǎn)失效場(chǎng)景下的節(jié)點(diǎn)選擇機(jī)制B-WSJ(bandwidth based weak and strong judgement)，其對(duì)節(jié)點(diǎn)關(guān)系的運(yùn)算進(jìn)行建模，利用此模型并行地進(jìn)行新生節(jié)點(diǎn)的強(qiáng)弱判斷，在很大程度上優(yōu)化了多節(jié)點(diǎn)失效時(shí)的數(shù)據(jù)修復(fù)時(shí)間.實(shí)驗(yàn)結(jié)果表明B-WSJ較SPSN算法有很大的性能提升.

1 相關(guān)工作

Ahmad等人[10]研究在什么條件下，再生碼修復(fù)時(shí)對(duì)節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)選擇優(yōu)于隨機(jī)選擇.本文提出了一個(gè)FR(family repair)模型，并分析得到在某些情況下，應(yīng)用此節(jié)點(diǎn)選擇機(jī)制的數(shù)據(jù)修復(fù)比隨機(jī)選擇能夠獲得更低的存儲(chǔ)開銷和修復(fù)帶寬開銷.Ahmad等人[12]繼續(xù)針對(duì)本地修復(fù)再生碼(locally repairable regenerating codes， LRRC)提出了動(dòng)態(tài)供應(yīng)節(jié)點(diǎn)選擇機(jī)制(dynamic helper selection， DHS)，并分析在特定的編碼狀況下，DHS節(jié)點(diǎn)選擇機(jī)制比SHS算法和BHS算法具有更低的存儲(chǔ)開銷和帶寬開銷.

Gong等人[11]針對(duì)單節(jié)點(diǎn)失效場(chǎng)景提出了最優(yōu)節(jié)點(diǎn)選擇算法SPSN，其特征為優(yōu)先選取帶寬較大的節(jié)點(diǎn)作為供應(yīng)節(jié)點(diǎn)和新生節(jié)點(diǎn)，本文分別探討了在固定的修復(fù)帶寬和彈性修復(fù)帶寬場(chǎng)景下的節(jié)點(diǎn)選擇機(jī)制.研究結(jié)果表明SPSN算法較隨機(jī)選擇算法有很大的性能提升.齊鳳林等人[13]在此基礎(chǔ)上，將節(jié)點(diǎn)的計(jì)算能力考慮進(jìn)來，提出了不同拓?fù)淠Ｐ蜕系墓?yīng)節(jié)點(diǎn)的選擇，結(jié)果表明節(jié)點(diǎn)的選擇機(jī)制對(duì)修復(fù)性能具有較好的性能提升.Jia等人[14]考慮節(jié)點(diǎn)之間的實(shí)際物理鏈路，將同時(shí)選擇供應(yīng)節(jié)點(diǎn)和節(jié)點(diǎn)傳輸數(shù)據(jù)的路由路徑建模成整數(shù)線性規(guī)劃問題，并提出了近似最優(yōu)解.

以上的研究針對(duì)單節(jié)點(diǎn)失效場(chǎng)景，然而理論研究和實(shí)際系統(tǒng)均表明多節(jié)點(diǎn)失效的延遲修復(fù)非常常見.在實(shí)際存儲(chǔ)系統(tǒng)[15]中，由于軟硬件錯(cuò)誤或用戶不良的訪問需求等，節(jié)點(diǎn)的性能相差很大.Shen等人[16]利用Lyapunov方法，根據(jù)失效節(jié)點(diǎn)的等待時(shí)間和網(wǎng)絡(luò)拓?fù)渲械目捎脦?，確定延遲修復(fù)何時(shí)開始.此研究成果表明,與逐個(gè)修復(fù)相比，延遲修復(fù)可以很好地降低系統(tǒng)的再生時(shí)間.在Wuala[17]，Total Recall[18]等實(shí)際系統(tǒng)中，當(dāng)節(jié)點(diǎn)失效的個(gè)數(shù)達(dá)到設(shè)定的閾值時(shí)，失效數(shù)據(jù)才開始再生；因此多節(jié)點(diǎn)失效的延遲修復(fù)是一種非常常見的現(xiàn)象.Hu等人[19]基于單節(jié)點(diǎn)失效時(shí)修復(fù)的性能，首次提出了多節(jié)點(diǎn)失效場(chǎng)景下的合作修復(fù)編碼(mutually cooperative recovery, MCR).理論證明，與單節(jié)點(diǎn)失效時(shí)的MSR碼和MBR碼相比，MCR碼消耗更小的存儲(chǔ)成本和修復(fù)帶寬.為了進(jìn)一步降低修復(fù)帶寬，Shum等人[20]基于合作修復(fù)編碼，應(yīng)用信息流圖的最大流最小割定理得到關(guān)于修復(fù)帶寬和節(jié)點(diǎn)存儲(chǔ)量的權(quán)衡曲線，滿足此曲線上的編碼方式被稱為線性合作再生碼.曲線上2個(gè)極點(diǎn)分別為存儲(chǔ)開銷最低的編碼(minimum-storage cooperative regenerating, MSCR)[21]和修復(fù)帶寬最小的編碼(minimum-bandwidth cooperative regenerating, MBCR).

已有的延遲修復(fù)過程中，SPSN算法的性能不再最優(yōu).隨著系統(tǒng)中節(jié)點(diǎn)失效規(guī)模的擴(kuò)大，這將給數(shù)據(jù)修復(fù)帶來很大的時(shí)間開銷和空間開銷.

2 問題描述

Fig. 2 Example of node selection algorithm圖2 節(jié)點(diǎn)選擇算法示例

從圖2可知，節(jié)點(diǎn)選擇機(jī)制對(duì)于數(shù)據(jù)的修復(fù)性能具有很大的影響，已有的節(jié)點(diǎn)選擇算法在多節(jié)點(diǎn)修復(fù)場(chǎng)景下具有很大的局限性.首先，SPSN算法僅僅考慮供應(yīng)節(jié)點(diǎn)和新生節(jié)點(diǎn)之間帶寬的選擇，而沒有考慮到新生節(jié)點(diǎn)之間帶寬的選擇.這將使得新生節(jié)點(diǎn)之間的帶寬在后續(xù)多節(jié)點(diǎn)修復(fù)過程中造成性能瓶頸；其次，SPSN算法串行選擇節(jié)點(diǎn)，使得數(shù)據(jù)再生過程中產(chǎn)生很多冗余信息，增加了網(wǎng)絡(luò)的負(fù)擔(dān)；最后，SPSN算法由于其具有串行貪心選擇的特征，隨著系統(tǒng)中節(jié)點(diǎn)失效規(guī)模的擴(kuò)大，這將給數(shù)據(jù)修復(fù)帶來很大的時(shí)間開銷和空間開銷.

基于這些問題，本文提出了多節(jié)點(diǎn)失效場(chǎng)景下的節(jié)點(diǎn)選擇機(jī)制B -WSJ，主要貢獻(xiàn)有4個(gè)方面：1)算法對(duì)帶寬中節(jié)點(diǎn)的關(guān)系進(jìn)行分類，并在操作中將已有算法所忽略的節(jié)點(diǎn)關(guān)系存儲(chǔ)起來；2)算法分為淺度和深度判斷，逐層過濾，去掉冗余信息，淺度判斷中加入了已有算法忽略新生節(jié)點(diǎn)信息；3)算法繼續(xù)對(duì)弱判斷結(jié)果進(jìn)行強(qiáng)判斷操作，找出兩兩相連的r個(gè)節(jié)點(diǎn)，隨著失效節(jié)點(diǎn)規(guī)模增大，這將具有很大的挑戰(zhàn)性；4)算法中加入了大量的預(yù)處理和剪枝思想，從而有效地降低算法的時(shí)空復(fù)雜度.實(shí)驗(yàn)結(jié)果表明，B-WSJ較SPSN算法有很大的性能提升.下面我們對(duì)算法進(jìn)行詳細(xì)的描述，并進(jìn)行多維度的分析和驗(yàn)證.

3 系統(tǒng)模型

3.1 拓?fù)淠Ｐ?/h3>

分布式存儲(chǔ)系統(tǒng)利用一定的通信技術(shù)，將文件分布到物理位置獨(dú)立的服務(wù)器中[4]，最終提供相應(yīng)的接口給用戶端上傳、下載或更新.

定義1. 網(wǎng)絡(luò)拓?fù)?實(shí)際系統(tǒng)中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有星型、樹形、網(wǎng)狀等，基于已有的研究，不失一般性，本文將網(wǎng)絡(luò)拓?fù)涑橄蟪蒾verlay結(jié)構(gòu)，記為G(V，E).其中：

1)V=Vp∪Vf∪Vn.V為所有節(jié)點(diǎn)的集合；Vp為存活節(jié)點(diǎn)的集合；Vf表示失效節(jié)點(diǎn)的集合；Vn表示空閑的節(jié)點(diǎn)集合，此處的空閑是指相對(duì)于目標(biāo)文件空閑.

2)E={C(u,v)|u∈Vp∪Vn,v∈V}.E表示網(wǎng)絡(luò)中所有帶寬.實(shí)際分布式存儲(chǔ)系統(tǒng)中，塊服務(wù)器間歇性的向主節(jié)點(diǎn)發(fā)送信息，數(shù)據(jù)中心的鏈路帶寬可以由主節(jié)點(diǎn)獲取[11，17].根據(jù)文獻(xiàn)[22]可知帶寬滿足C(u，v)～U[0.3，120].

定義2. 鏈路上節(jié)點(diǎn)之間關(guān)系.網(wǎng)絡(luò)中某節(jié)點(diǎn)w，我們對(duì)其鄰居節(jié)點(diǎn)關(guān)系記錄如下：

1) 其下游的鄰居節(jié)點(diǎn)集合被記作T(w)，集合中的元素個(gè)數(shù)記為count+T(w).即對(duì)于拓?fù)渲腥我夤?jié)點(diǎn)v∈T(w)，存在一條從節(jié)點(diǎn)w到節(jié)點(diǎn)v鏈路帶寬；

2) 其上游的鄰居節(jié)點(diǎn)如果屬于集合Vn，即候選新生節(jié)點(diǎn)集合，我們將這些鄰居節(jié)點(diǎn)的集合記為Hn(w)，集合中的元素個(gè)數(shù)記為count+Hn(w).即對(duì)于拓?fù)渲腥我夤?jié)點(diǎn)v∈Hn(w)，存在一條從節(jié)點(diǎn)v到節(jié)點(diǎn)w鏈路帶寬；

3) 其上游的鄰居節(jié)點(diǎn)如果屬于集合Vp，即候選供應(yīng)節(jié)點(diǎn)集合，我們將這些鄰居節(jié)點(diǎn)的集合記為Hp(w)，集合中的元素個(gè)數(shù)記為count+Hp(w).即對(duì)于拓?fù)渲腥我夤?jié)點(diǎn)v∈Hp(w)，存在一條從節(jié)點(diǎn)v到節(jié)點(diǎn)w鏈路帶寬；

4) 既為其上游鄰居節(jié)點(diǎn)，也為下游鄰居節(jié)點(diǎn)集合記為HT(w),集合中的元素個(gè)數(shù)記為count+HT(w).即對(duì)于拓?fù)渲腥我夤?jié)點(diǎn)v∈HT(w)，既存在一條從節(jié)點(diǎn)v到節(jié)點(diǎn)w鏈路帶寬，也存在一條從節(jié)點(diǎn)w到節(jié)點(diǎn)v鏈路帶寬.

證明.

① 當(dāng)S=1時(shí)，假設(shè)這個(gè)節(jié)點(diǎn)為v1,很明顯1個(gè)節(jié)點(diǎn)兩兩相連，結(jié)論是成立的；

證畢.

文件以(n，k，d)的編碼方式存儲(chǔ)到此拓?fù)渚W(wǎng)絡(luò)中.存儲(chǔ)模型可以描述為源文件從虛擬節(jié)點(diǎn)VS發(fā)出，系統(tǒng)首先將其均勻分成k塊；然后經(jīng)過某種編碼方式將這k個(gè)數(shù)據(jù)塊編成n塊；最后將通過Hash或者其他分布算法將這些數(shù)據(jù)塊放到n個(gè)存儲(chǔ)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù)量為α.我們?cè)O(shè)定源文件的存儲(chǔ)具有MDS性質(zhì)，即目標(biāo)節(jié)點(diǎn)DS可以訪問n個(gè)存儲(chǔ)節(jié)點(diǎn)中任意k個(gè)節(jié)點(diǎn)上的數(shù)據(jù)，經(jīng)過相應(yīng)的解碼操作將源文件還原出來.當(dāng)節(jié)點(diǎn)失效時(shí)，每個(gè)新選擇出的節(jié)點(diǎn)需要從d供應(yīng)節(jié)點(diǎn)下載數(shù)據(jù).

3.2 多節(jié)點(diǎn)失效場(chǎng)景下的修復(fù)模型

在分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)失效的個(gè)數(shù)達(dá)到r(r≤n)時(shí)，我們才對(duì)其進(jìn)行合作修復(fù).時(shí)間被切割成不同的階段，直到此時(shí)間段內(nèi)所有的數(shù)據(jù)修復(fù)完才進(jìn)入到下一個(gè)時(shí)間段[20-21].已有文獻(xiàn)對(duì)分布式存儲(chǔ)系統(tǒng)中帶寬的預(yù)測(cè)方法表明未來帶寬大小的變化與歷史帶寬大小是相關(guān)聯(lián)的[23-24]，在很短時(shí)間內(nèi)帶寬大小變化很小.因此，我們假設(shè)系統(tǒng)中主節(jié)點(diǎn)獲得的帶寬大小在此修復(fù)時(shí)間段內(nèi)保持不變，而且修復(fù)過程中每個(gè)節(jié)點(diǎn)之間傳輸?shù)臄?shù)據(jù)量均為β.

Fig. 3 Cooperative recovery of distributed storage systems from multiple losses圖3 分布式存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)失效時(shí)的合作修復(fù)

定義3. 多節(jié)點(diǎn)修復(fù)模型.首先，系統(tǒng)從空閑節(jié)點(diǎn)集Vn中找出|Vf|個(gè)節(jié)點(diǎn)作為新生節(jié)點(diǎn)(被稱為newcomer)，并且為每個(gè)newcomer從存活節(jié)點(diǎn)集合Vp中選出d個(gè)節(jié)點(diǎn)(n-r≥d≥k)作為供應(yīng)節(jié)點(diǎn)(被稱為provider).其次，每個(gè)newcomer從每個(gè)provider下載相應(yīng)的數(shù)據(jù)量β并存儲(chǔ)到newcomer上，這個(gè)操作記為ψα→ψβ；與此同時(shí)，每個(gè)newcomer需要從其他r-1個(gè)newcomer下載的數(shù)據(jù)，此過程可以記錄為ψd β→ψβ；最后，每個(gè)newcomer通過計(jì)算所得到的數(shù)據(jù)量，恢復(fù)出失效的數(shù)據(jù)，記錄為ψ(d+r-1)β→ψα.

下面通過圖3來詳細(xì)說明多節(jié)點(diǎn)修復(fù)模型(合作修復(fù)模型)，源文件被均分為4個(gè)塊A，B，C，D，這些原始文件塊經(jīng)過編碼生成8個(gè)數(shù)據(jù)塊，新數(shù)據(jù)塊中每2塊作為一個(gè)包按照某種布置策略分布到4個(gè)節(jié)點(diǎn)上.那么節(jié)點(diǎn)1將存儲(chǔ)數(shù)據(jù)塊A，B；節(jié)點(diǎn)2存儲(chǔ)數(shù)據(jù)塊C，D；節(jié)點(diǎn)3存儲(chǔ)數(shù)據(jù)塊A+C，2B+D；節(jié)點(diǎn)4存儲(chǔ)數(shù)據(jù)塊2A+C，B+D.此時(shí)文件存儲(chǔ)采用的編碼方式(n，k，d)為(4，2，2)，鑒于文件存儲(chǔ)具有MDS性質(zhì)，即任取拓?fù)渲?個(gè)節(jié)點(diǎn)上的數(shù)據(jù)可以將源文件恢復(fù)出來，因此，所用文件存儲(chǔ)模型可以容忍2個(gè)節(jié)點(diǎn)失效.

在某個(gè)時(shí)間點(diǎn)，節(jié)點(diǎn)2和節(jié)點(diǎn)4上的數(shù)據(jù)失效了，即r=2，此時(shí)系統(tǒng)的數(shù)據(jù)修復(fù)開始.假設(shè)選定的新生節(jié)點(diǎn)為節(jié)點(diǎn)5和節(jié)點(diǎn)6，供應(yīng)節(jié)點(diǎn)為節(jié)點(diǎn)1和節(jié)點(diǎn)3，每一個(gè)所選新節(jié)點(diǎn)需要從2個(gè)供應(yīng)節(jié)點(diǎn)上下載數(shù)據(jù).新生節(jié)點(diǎn)5需要從節(jié)點(diǎn)1下載數(shù)據(jù)塊A，從節(jié)點(diǎn)3下載數(shù)據(jù)塊A+C，計(jì)算出數(shù)據(jù)塊C，并將中間計(jì)算結(jié)果2A+C傳輸給節(jié)點(diǎn)6；與此同時(shí)，從節(jié)點(diǎn)6下載數(shù)據(jù)塊D，此時(shí)節(jié)點(diǎn)2上的失效數(shù)據(jù)被再生出來.新生節(jié)點(diǎn)6從節(jié)點(diǎn)1下載數(shù)據(jù)塊B，從節(jié)點(diǎn)3下載數(shù)據(jù)塊2B+D，計(jì)算出數(shù)據(jù)塊D，并將中間結(jié)算結(jié)果D傳輸給節(jié)點(diǎn)5；與此同時(shí)，從節(jié)點(diǎn)6下載數(shù)據(jù)塊2A+C，此時(shí)節(jié)點(diǎn)4上的失效數(shù)據(jù)被再生出來.通過此種新生節(jié)點(diǎn)之間互相交換信息的合作修復(fù)方式，可以很大程度上降低鏈路上傳輸?shù)臄?shù)據(jù)量.

4 算法及分析

4.1 節(jié)點(diǎn)選擇算法

Fig. 4 Algorithm design idea 圖4 算法設(shè)計(jì)思想

從圖4還可以看出，對(duì)比已有的算法，B-WSJ算法有很多特征:

1) 算法不但存儲(chǔ)節(jié)點(diǎn)的入度，而且存儲(chǔ)了節(jié)點(diǎn)的出度和相鄰節(jié)點(diǎn)信息用于后續(xù)判斷；

2) 算法在弱判斷過程中考慮了對(duì)每個(gè)節(jié)點(diǎn)的出度信息，以初步滿足新生節(jié)點(diǎn)的個(gè)數(shù)；

3) 算法繼續(xù)對(duì)弱判斷選擇出的節(jié)點(diǎn)集合進(jìn)行強(qiáng)判斷操作，確定是否存在r個(gè)節(jié)點(diǎn)兩兩相連，找出滿足合作修復(fù)的新生節(jié)點(diǎn).強(qiáng)判斷的過程具有很大的挑戰(zhàn)性，算法利用定義2以及定理1可以快速找出兩兩相連的r個(gè)新生節(jié)點(diǎn)；

4) 算法中加入了大量的預(yù)處理和剪枝思想，從而有效地降低算法的時(shí)空復(fù)雜度.

算法1. B-WSJ算法.

輸入：網(wǎng)絡(luò)拓?fù)銰(V,E)、帶寬E={C(u,v)|u∈Vp∪Vn,v∈Vn}；

④ if (count+Hp(v)≥d+r-1 &&

count+T(v)≥r-1) then

⑤CANDI←v；

⑥ if (CANDI.size≥r) then

⑦DCGS←∪sHT(vi),vi∈CANDI；

⑧ if (s≥r) then

⑨vn←DCGS；

⑩ returnvn及相應(yīng)Hp的前d個(gè)元素；

關(guān)于算法1中實(shí)現(xiàn)弱判斷的步驟④，T(v)是通過計(jì)算所有選取帶寬中上游節(jié)點(diǎn)的出度來實(shí)現(xiàn)的.Hp和Hn是通過計(jì)算所有選取帶寬中下游節(jié)點(diǎn)的入度來實(shí)現(xiàn)的.并把候選新生節(jié)點(diǎn)鄰接供應(yīng)節(jié)點(diǎn)存儲(chǔ)進(jìn)集合Hp，鄰接新生節(jié)點(diǎn)存儲(chǔ)進(jìn)對(duì)應(yīng)的Hn和T.

算法2. 弱判斷中count+Hp(v)和count+T(v)的實(shí)現(xiàn).

② if (v∈Vn)

③ if (u∈Vn) then

④T(u)←v；

⑤count+T(u)++；

⑥Hn(v)←u；

⑦count+Hn(v)++；

⑧ else if (u∈Vp) then

⑨Hp(v)←u；

⑩count+HP(v)++；

算法1中實(shí)現(xiàn)強(qiáng)判斷的步驟⑧是通過判斷2節(jié)點(diǎn)是否均在彼此的鄰接新生節(jié)點(diǎn)集合Hn中得到的，直到最后得到r個(gè)相互連接的節(jié)點(diǎn).

算法3. 強(qiáng)判斷中DCGS的實(shí)現(xiàn).

① for eachiinCANDIdo

② if (HP(i).size≥d&&Hn(i).size≥r-1) then

③ for eachjin hashsetvndo

④ if (vn.size=0)

⑤vn.add(i)；

⑥ break;

⑦ else if (j=i‖!(j∈Hn(i))‖!(i∈Hn(j)))

⑧ continue；

⑨ else

⑩vn.add(i)；

下面列舉一個(gè)實(shí)例來對(duì)強(qiáng)判斷進(jìn)行說明.假設(shè)弱判斷選擇出的節(jié)點(diǎn)如圖5所示，圖5(a)表示弱判斷選擇出的集合CANDI包含元素為{Node2，Node1，Node4，Node3}，它們是滿足供應(yīng)節(jié)點(diǎn)和新生節(jié)點(diǎn)個(gè)數(shù)條件的候選新生節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)i的Hn集合里的元素為圖5(a)所示.假設(shè)失效節(jié)點(diǎn)個(gè)數(shù)為3，我們進(jìn)行4項(xiàng)強(qiáng)判斷:①取集合CANDI中第1個(gè)元素Node2，由于此時(shí)集合為空，Node2將被放入集合中vn；②取CANDI中下一個(gè)元素Node1，由于Node2∈Hn(Node1)，并且Node1∈Hn(Node2)，因此將Node1加入集合.由于vn的長(zhǎng)度未到達(dá)2，算法繼續(xù)進(jìn)行；③取元素Node4，由于Node4∈Hn(Node2)，而Node2?Hn(Node4)，故忽略Node4；④取最后一個(gè)元素Node3，由于Node3∈Hn(Node1)，并且Node1∈Hn(Node3)，Node3∈Hn(Node2)，并且Node2∈Hn(Node3)，因此將Node3加入集合如圖5(b)所示.此時(shí)集合中元素的個(gè)數(shù)滿足條件，算法終止，并輸出最后集合vn及相應(yīng)Hn的前d個(gè)元素.

Fig. 5 An example of strong judgement圖5 強(qiáng)判斷的實(shí)例

4.2 算法分析

本算法由Gong等人[11]所作研究的思想拓展而成，其核心想法是優(yōu)先選取最大的帶寬傳輸數(shù)據(jù)，下面對(duì)算法的性能進(jìn)行分析.首先對(duì)B -WSJ算法的最優(yōu)性進(jìn)行證明；然后對(duì)其時(shí)間復(fù)雜度進(jìn)行分析；最后我們考慮算法對(duì)不同編碼方式的影響.

1) 證明算法的最優(yōu)性

定理2. 分布式存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)失效場(chǎng)景下，對(duì)于已有的修復(fù)模型，節(jié)點(diǎn)選擇算法B -WSJ為最優(yōu).

證畢.

2) 算法時(shí)間復(fù)雜度的分析

實(shí)際分布式存儲(chǔ)系統(tǒng)中，鏈路帶寬可以通過數(shù)據(jù)中心的主節(jié)點(diǎn)獲取[17]，帶寬包括集合Vp中節(jié)點(diǎn)到集合Vn中節(jié)點(diǎn)的帶寬，集合Vn中兩兩節(jié)點(diǎn)的帶寬.相關(guān)研究測(cè)量得出獲取帶寬的時(shí)間很短[22]，只需2～4個(gè)往返時(shí)延(round-trip time, RTT)，因此獲取帶寬的時(shí)間對(duì)于再生修復(fù)時(shí)間來說可以忽略不計(jì).

綜上分析可知，B-WSJ算法加入各種機(jī)制降低了節(jié)點(diǎn)選擇的時(shí)間復(fù)雜度.一方面，分布式存儲(chǔ)系統(tǒng)中，單個(gè)文件的存儲(chǔ)節(jié)點(diǎn)是有限的，例如Google文件系統(tǒng)編碼方式為(6，3，3)，此時(shí)，失效節(jié)點(diǎn)個(gè)數(shù)r滿足條件:r≤3，r?N；因此，失效節(jié)點(diǎn)的個(gè)數(shù)相對(duì)系統(tǒng)節(jié)點(diǎn)來說是一個(gè)很小的值.另一方面，算法中設(shè)計(jì)的預(yù)處理機(jī)制和剪枝策略，涉及了節(jié)點(diǎn)出入度和連接關(guān)系，刪除了大量隨機(jī)孤立或連接稀疏的節(jié)點(diǎn)，從而大批量地縮小了算法的選擇范圍.分布式存儲(chǔ)系統(tǒng)中，等待節(jié)點(diǎn)失效個(gè)數(shù)達(dá)到r時(shí)進(jìn)行修復(fù).Garraghan等人在文獻(xiàn)[25]中指出系統(tǒng)的節(jié)點(diǎn)修復(fù)時(shí)間以小時(shí)(h)為單位，大部分節(jié)點(diǎn)失效可以通過重啟服務(wù)器或者其他方式來進(jìn)行修復(fù)，因此其修復(fù)時(shí)間可以少于30 min；而有些不能通過重啟服務(wù)器進(jìn)行修復(fù)的失效則需要幾天時(shí)間.基于此，算法的復(fù)雜度是可以接受的.

3) 編碼性質(zhì)的影響

當(dāng)失效節(jié)點(diǎn)的個(gè)數(shù)達(dá)到閾值r時(shí)，這些失效的數(shù)據(jù)將被再生到新的空節(jié)點(diǎn)上.根據(jù)定義5可知多節(jié)點(diǎn)失效時(shí)的合作修復(fù)模型.我們將此修復(fù)過程建模成信息流圖，即最大流等于最小割.使用B-WSJ算法選擇新生節(jié)點(diǎn)集合vn和相應(yīng)Hp之后，系統(tǒng)繼續(xù)開始修復(fù)數(shù)據(jù).修復(fù)過程中修復(fù)帶寬最小割的大小至少為文件的大小，修復(fù)過程中的數(shù)據(jù)傳輸量可以保證源文件被恢復(fù).因此B -WSJ算法選擇出的節(jié)點(diǎn)與文件的MDS性質(zhì)是獨(dú)立的.

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

在實(shí)驗(yàn)1中，主要變化網(wǎng)絡(luò)拓?fù)渲袔挿植?，以探索多?jié)點(diǎn)失效場(chǎng)景下，B-WSJ算法與已有的算法的性能變化.設(shè)定節(jié)點(diǎn)的失效閾值為2，每個(gè)供應(yīng)節(jié)點(diǎn)需要從4新生節(jié)點(diǎn)中下載數(shù)據(jù)，即d=4.實(shí)驗(yàn)分別在網(wǎng)絡(luò)拓?fù)渲袔捑鶆蚍植挤秶鸀閇0.3，120]，[1，120]，[10，120]，[30，120]，[50，120]，[70，120]，[90，120]的情況下進(jìn)行.如圖6所示:

Fig. 6 Performance of different node selection algorithm with different network topologies 圖6 不同帶寬分布情況下不同節(jié)點(diǎn)選擇算法的性能

在帶寬異構(gòu)明顯的情況下，已有的節(jié)點(diǎn)選擇機(jī)制性能相差越來越大.當(dāng)帶寬分布為[90，120]時(shí)，即帶寬變化不明顯時(shí)，B -WSJ算法比SPSN算法性能提高了5.27%，比BHS算法性能提高了21.73%.當(dāng)帶寬分布為[0.3，120]時(shí)，B -WSJ算法比SPSN算法性能提高了45.93%，比BHS算法性能提高了78.95%.結(jié)果證明節(jié)點(diǎn)的選擇機(jī)制對(duì)于數(shù)據(jù)的再生時(shí)間具有很大的影響.從圖6中還可以看出，B -WSJ算法在帶寬異構(gòu)明顯時(shí)的性能要好于帶寬異構(gòu)不明顯時(shí)的性能，這是由B -WSJ算法的對(duì)帶寬進(jìn)行貪心擇優(yōu)的特征決定的.

為了驗(yàn)證環(huán)境參數(shù)對(duì)算法性能的影響，我們對(duì)不同供應(yīng)節(jié)點(diǎn)個(gè)數(shù)進(jìn)行變化.文獻(xiàn)相關(guān)參考文獻(xiàn)網(wǎng)絡(luò)拓?fù)渲袔挿木鶆蚍植糢[0.3，120] .實(shí)驗(yàn)依次變換d的取值，即d分別取值為4，5，6，7，8，結(jié)果如圖7所示:

Fig. 7 Performance of different node selectionalgorithm with different providers圖7 不同供應(yīng)節(jié)點(diǎn)個(gè)數(shù)時(shí)不同節(jié)點(diǎn)選擇算法的性能

從圖7中可以看出隨著供應(yīng)節(jié)點(diǎn)個(gè)數(shù)的增加，算法的再生時(shí)間均增加，這是由于算法不但選擇新生節(jié)點(diǎn)而且同時(shí)選擇供應(yīng)節(jié)點(diǎn)的個(gè)數(shù)決定的；從圖7中可以清晰看出，B-WSJ算法所選結(jié)果的再生時(shí)間比SPSN算法增長(zhǎng)幅度較慢，這是符合算法的特征的；BHS算法的結(jié)果沒有特別明顯的增長(zhǎng)趨勢(shì).

Fig. 8 Performance of different node selection algorithmwith different numbers of failure nodes圖8 不同失效節(jié)點(diǎn)個(gè)數(shù)時(shí)不同節(jié)點(diǎn)選擇算法的性能

為了繼續(xù)驗(yàn)證環(huán)境參數(shù)中節(jié)點(diǎn)失效個(gè)數(shù)對(duì)B -WSJ算法性能的影響，我們?cè)谑Р煌?jié)點(diǎn)個(gè)數(shù)的場(chǎng)景進(jìn)行了實(shí)驗(yàn).設(shè)定d=4，帶寬服從均勻分布U[0.3，120].由于單個(gè)文件需要能夠被恢復(fù)出來，因此不能超過6個(gè)節(jié)點(diǎn)同時(shí)失效，故實(shí)驗(yàn)中閾值r分別取值為1，2，3，4，5，6.圖8表明：隨著節(jié)點(diǎn)失效個(gè)數(shù)的增加，已有節(jié)點(diǎn)選擇算法的性能越來越差.從圖8中可看出B-WSJ算法性能最優(yōu)，而SPSN算法性能較差.當(dāng)r=1時(shí)，SPSN算法和B-WSJ算法性能相同，這是由于SPSN算法為B-WSJ算法在失效一個(gè)節(jié)點(diǎn)情況下的特例.隨著失效個(gè)數(shù)越多，由于SPSN算法為逐個(gè)失效節(jié)點(diǎn)的修復(fù)，其選擇到的節(jié)點(diǎn)性能越來越差，因此其再生時(shí)間越來越長(zhǎng)，而B-WSJ算法具有全局并行性的特征而性能相對(duì)較優(yōu).BHS算法為隨機(jī)選擇算法，性能不穩(wěn)定，因此平均性能最差.

6 結(jié) 論

在大數(shù)據(jù)環(huán)境下，分布式存儲(chǔ)系統(tǒng)通常引進(jìn)冗余來提高可靠性.在多節(jié)點(diǎn)失效場(chǎng)景下，當(dāng)失效節(jié)點(diǎn)個(gè)數(shù)達(dá)到一個(gè)閾值時(shí)，系統(tǒng)才進(jìn)行修復(fù).為了優(yōu)化修復(fù)時(shí)間，相關(guān)研究驗(yàn)證了單節(jié)點(diǎn)失效場(chǎng)景中節(jié)點(diǎn)選擇機(jī)制對(duì)修復(fù)時(shí)間的影響.然而已有的算法不適用于多節(jié)點(diǎn)失效的場(chǎng)景，其串行性特征會(huì)使得數(shù)據(jù)的修復(fù)性能不再最優(yōu).基于此問題，本文繼續(xù)探索了多節(jié)點(diǎn)失效場(chǎng)景下，節(jié)點(diǎn)選擇機(jī)制對(duì)數(shù)據(jù)修復(fù)性能的影響.在分析多節(jié)點(diǎn)失效的延遲修復(fù)模型之后，本文提出了B-WSJ算法，并對(duì)算法性能進(jìn)行多維度的分析和最優(yōu)性證明.最后通過在不同的參數(shù)環(huán)境下對(duì)比已有算法，結(jié)果證明節(jié)點(diǎn)選擇機(jī)制對(duì)于數(shù)據(jù)的修復(fù)性能具有很大的影響；通過對(duì)不同的實(shí)際文件存儲(chǔ)方式和失效模型進(jìn)行實(shí)驗(yàn)，結(jié)果表明:算法在失效個(gè)數(shù)比較多或帶寬異構(gòu)明顯的情況下，B-WSJ算法比已有算法的性能更優(yōu).本文的研究模型比較理想，后續(xù)我們將繼續(xù)擴(kuò)展環(huán)境，考慮傳輸不同數(shù)據(jù)量場(chǎng)景下的節(jié)點(diǎn)選擇機(jī)制.