[發(fā)明專利]一種多數(shù)據(jù)中心背景下基于遺傳算法的RS碼節(jié)點修復方法

在審

• 申請?zhí)枺?/td>: 202110482403.4
• 申請日: 2021-04-30
• 公開（公告）號: CN113285985A
• 公開（公告）日: 2021-08-20
• 發(fā)明（設計）人: 王勇;鎖欣;葉苗;蔡月
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L1/00;G06N3/12
• 代理公司: 鹽城創(chuàng)佳智科專利代理事務所(普通合伙) 32476
• 代理人: 卜祥奎

本發(fā)明公開了一種多數(shù)據(jù)中心背景下基于遺傳算法的RS碼節(jié)點修復方法。本發(fā)明的目的是針對傳統(tǒng)數(shù)據(jù)修復方式在多數(shù)據(jù)中心背景下無法取得全局最優(yōu)瓶頸帶寬修復方案的問題，提出了一種基于遺傳算法的最優(yōu)瓶頸帶寬路徑選擇方法，根據(jù)節(jié)點的計算能力及節(jié)點間的帶寬，生成瓶頸帶寬最大的修復樹，有效降低了節(jié)點修復時所產(chǎn)生的網(wǎng)絡帶寬消耗和修復時間。本發(fā)明所述的一種多數(shù)據(jù)中心背景下基于遺傳算法的RS碼節(jié)點修復方法，克服了傳統(tǒng)星型修復方案及流水線修復方案的修復時延較大的問題和傳統(tǒng)樹型修復方案帶寬消耗較大的問題，減少冗余數(shù)據(jù)傳輸，提高修復效率，降低修復時間。

技術領域

本發(fā)明屬于分布式糾刪碼存儲系統(tǒng)領域，具體涉及一種多數(shù)據(jù)中心背景下基于遺傳算法的RS碼節(jié)點修復方法。

背景技術

分布式存儲系統(tǒng)憑借其優(yōu)秀的性能和低廉的構造成本成為了當前大規(guī)模數(shù)據(jù)存儲領域的主流存儲系統(tǒng)，但由于分布式存儲系統(tǒng)的底層設備普遍采用廉價商用硬件，因此節(jié)點失效已成為一種常態(tài)。

為了防止由節(jié)點故障導致的數(shù)據(jù)失效所引起的業(yè)務損失，分布式存儲系統(tǒng)常采用糾刪碼和多副本冗余數(shù)據(jù)來保證數(shù)據(jù)的完整性與可靠性，其中糾刪碼因為額外存儲開銷較小受到廣泛應用，但當部分節(jié)點發(fā)生故障導致數(shù)據(jù)失效時，糾刪碼則需要讀取其他數(shù)據(jù)塊并進行編碼解碼來恢復失效數(shù)據(jù)，這一過程會產(chǎn)生大量的修復流量開銷，且修復速度較慢。

發(fā)明內(nèi)容

為了克服上述現(xiàn)有技術的不足，本發(fā)明提供了一種多數(shù)據(jù)中心背景下基于遺傳算法的RS碼節(jié)點修復方法，減小修復流量開銷并加速修復效率。

以(n,k)RS碼為例，將這組碼的n個數(shù)據(jù)塊分別存儲于2個數(shù)據(jù)中心內(nèi)，兩個數(shù)據(jù)中心的網(wǎng)絡拓撲可以表示為G＝(V,E,W),V＝{1，2,…,n₁,n₁+1,…,n}表示一組(n,k)碼存儲于集群中的n個節(jié)點，其中云1包含n1個修復節(jié)點，云2中包含n2個修復節(jié)點，n₁+n₂＝n；E＝{e₁₁,e₁₂,…,e_ij}表示集群內(nèi)部的鏈路連接，e_ij表示節(jié)點之間的最優(yōu)鏈路；W_ij表示節(jié)點之間的可用帶寬，當i＝j時，表示節(jié)點的處理能力。當一個云中心內(nèi)的發(fā)生節(jié)點失效時，云中心C1和云中心C2分別提供k1、k2個數(shù)據(jù)塊作為provider節(jié)點對失效節(jié)點進行修復，k₁+k₂＝k。

糾刪碼數(shù)據(jù)修復時，所有provider節(jié)點所傳輸?shù)臄?shù)據(jù)塊都到達修復節(jié)點后才能恢復失效數(shù)據(jù)塊，此時樹形修復拓撲中帶寬最小鏈路將直接影響整個數(shù)據(jù)傳遞過程的效率，該鏈路被稱為瓶頸鏈路，其可用帶寬被稱為瓶頸帶寬，修復樹的瓶頸帶寬越大，代表該修復樹傳遞修復數(shù)據(jù)的效率越高。因此構建修復樹的問題可歸納為在圖G中尋找一棵以重構點為根，且在C₁、C₂內(nèi)分別包含k₁、k₂個provider節(jié)點的修復樹，使其瓶頸帶寬最大，可表達為下列公式，w(i,j)為當前鏈路可用帶寬，D是鏈路上所傳輸?shù)臄?shù)據(jù)塊，二者的商為傳輸時延：

T＝min(max{D/w(i,j)})

同時，由于樹形拓撲本身比其他拓撲有額外的流量要進行傳輸，因此，修復樹中的每個節(jié)點都對其子節(jié)點及本身的編碼塊做合并運算，從而節(jié)省傳輸流量開銷，盡可能的減小網(wǎng)絡負載，使修復過程對網(wǎng)絡本身不造成較大影響。所以鏈路兩端的計算時延可表示為下列公式，其中process_i表示節(jié)點i的計算能力：

t(v_i,v_j)＝D_i/process_i+D_j/process_j

當傳統(tǒng)修復樹加入節(jié)點處理能力這一條件后，本章的目標函數(shù)可表示為下列公式：