[發(fā)明專利]一種基于糾刪碼的失效數(shù)據(jù)線形修復方法

有效

• 申請?zhí)枺?/td>: 201310593541.5
• 申請日: 2013-11-21
• 公開（公告）號: CN103607304A
• 公開（公告）日: 2014-02-26
• 發(fā)明（設(shè)計）人: 王意潔;許方亮;裴曉強;符永銓;孫偉東;程力;李小勇;馬行空;王媛;趙越;林軒;熊澤宇
• 申請（專利權(quán)）人: 中國人民解放軍國防科學技術(shù)大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L29/08
• 代理公司: 國防科技大學專利服務(wù)中心 43202
• 代理人: 郭敏

1.一種基于糾刪碼的失效數(shù)據(jù)線形修復方法，其特征在于包括以下步驟：

第一步，構(gòu)建一個由多個節(jié)點構(gòu)成分布存儲系統(tǒng)，每個節(jié)點都是一臺可獨立運行的計算機，各節(jié)點通過網(wǎng)絡(luò)設(shè)備互連；分布存儲系統(tǒng)中的節(jié)點分為兩類：控制節(jié)點和存儲節(jié)點，控制節(jié)點和存儲節(jié)點上均安裝有操作系統(tǒng)、TCP/IP協(xié)議軟件，配置了網(wǎng)絡(luò)環(huán)境；

分布存儲系統(tǒng)包括一個控制節(jié)點，負責與用戶交互，接收用戶提交的失效數(shù)據(jù)塊修復請求；負責存儲解碼系數(shù)，構(gòu)建線形修復路徑，向各存儲節(jié)點分發(fā)失效數(shù)據(jù)塊修復任務(wù)和接收修復成功信息，向用戶返回修復成功信息；

分布存儲系統(tǒng)包括N個存儲節(jié)點，N為正整數(shù)，它們負責存儲數(shù)據(jù)對象的原始數(shù)據(jù)塊和冗余數(shù)據(jù)塊，執(zhí)行失效數(shù)據(jù)塊修復任務(wù)，并向控制節(jié)點返回修復成功信息；設(shè)數(shù)據(jù)對象DO分割為k個原始數(shù)據(jù)塊，對其進行編碼計算得到m個冗余數(shù)據(jù)塊，這k+m個數(shù)據(jù)塊分別存儲在不同的存儲節(jié)點上，k+m＜N；在分布存儲系統(tǒng)中，每個數(shù)據(jù)塊擁有唯一的數(shù)據(jù)塊編號；

控制節(jié)點上安裝有任務(wù)管理程序和結(jié)果回收程序，任務(wù)管理程序接收用戶提交的失效數(shù)據(jù)塊修復請求，為失效數(shù)據(jù)塊選擇新存儲節(jié)點；從數(shù)據(jù)對象DO的k+m-1個可用數(shù)據(jù)塊中選擇k個可用數(shù)據(jù)塊；根據(jù)存儲節(jié)點之間的網(wǎng)絡(luò)距離構(gòu)建線形修復路徑，向k個可用數(shù)據(jù)塊所在的存儲節(jié)點發(fā)送失效數(shù)據(jù)塊修復請求及修復所需的相關(guān)信息；結(jié)果回收程序負責接收存儲節(jié)點的修復成功信息并返回給用戶；

存儲節(jié)點上安裝有修復程序，修復程序負責接收來自控制節(jié)點的失效數(shù)據(jù)塊修復請求，并對存儲節(jié)點上存儲的可用數(shù)據(jù)塊進行解碼計算，完成修復后向控制節(jié)點發(fā)送修復成功信息；

第二步，控制節(jié)點執(zhí)行任務(wù)管理程序，為待修復的失效數(shù)據(jù)塊D_i選擇新存儲節(jié)點LN；從數(shù)據(jù)對象DO的k+m-1個可用數(shù)據(jù)塊中選擇k個可用數(shù)據(jù)塊；根據(jù)存儲節(jié)點之間的網(wǎng)絡(luò)距離構(gòu)建線形修復路徑，向k個可用數(shù)據(jù)塊所在的存儲節(jié)點發(fā)送失效數(shù)據(jù)塊D_i修復請求、可用數(shù)據(jù)塊編號及其解碼系數(shù)H_ij、線形修復路徑數(shù)組Path、失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN的編號，1≤i≤k，j＝1,2,…,k，具體方法是：

2.1控制節(jié)點的任務(wù)管理程序接收用戶提交的失效數(shù)據(jù)塊D_i修復請求；

2.2控制節(jié)點的任務(wù)管理程序從可用存儲節(jié)點中選擇一個存儲節(jié)點作為失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN，選擇原則是存儲節(jié)點LN未存儲數(shù)據(jù)對象DO的任何數(shù)據(jù)塊；

2.3控制節(jié)點的任務(wù)管理程序從數(shù)據(jù)對象DO的k+m-1個可用數(shù)據(jù)塊中選擇k個可用數(shù)據(jù)塊，k個可用數(shù)據(jù)塊所在的存儲節(jié)點構(gòu)成集合NSet；

2.4控制節(jié)點的任務(wù)管理程序根據(jù)存儲節(jié)點之間的網(wǎng)絡(luò)距離構(gòu)建線形修復路徑，采用線形修復路徑數(shù)組Path存儲線形修復路徑中的存儲節(jié)點，Path[j]表示線形修復路徑的第j個存儲節(jié)點，1≤j≤k，線形修復路徑長度也為k，具體步驟如下：

2.4.1初始化信息，具體包括：

2.4.1.1目標存儲節(jié)點TN=LN；

2.4.1.2線形修復路徑節(jié)點序號j＝k；

2.4.2根據(jù)集合NSet中的所有存儲節(jié)點與目標存儲節(jié)點TN之間的網(wǎng)絡(luò)距離，確定與目標存儲節(jié)點TN距離最近的存儲節(jié)點NN，Path[j]=NN；

2.4.3將存儲節(jié)點NN從NSet中刪除，即，NSet=NSet-{NN}；

2.4.4更新目標存儲節(jié)點，TN=NN；

2.4.5更新線形修復路徑節(jié)點序號，j＝j(luò)-1；

2.4.6如果j＝0，轉(zhuǎn)第2.5步；否則，轉(zhuǎn)到第2.4.2步；

2.5控制節(jié)點的任務(wù)管理程序向k個可用數(shù)據(jù)塊所在的存儲節(jié)點發(fā)送失效數(shù)據(jù)塊D_i修復請求、可用數(shù)據(jù)塊編號及其解碼系數(shù)H_ij、線形修復路徑數(shù)組Path、失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN的編號；解碼系數(shù)H_ij是指糾刪碼解碼計算H_i1×E₁+…+H_ij×E_j+…+H_ik×E_k=D_i中的解碼系數(shù)，E_j是可用數(shù)據(jù)塊，“×”表示H_ij與可用數(shù)據(jù)塊E_j進行逐位相乘；

第三步，線形修復路徑中的各存儲節(jié)點執(zhí)行修復程序，接收來自控制節(jié)點的失效數(shù)據(jù)塊D_i修復請求、可用數(shù)據(jù)塊編號及其解碼系數(shù)H_ij、線形修復路徑數(shù)組Path、失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN的編號；基于可用數(shù)據(jù)塊及其解碼系數(shù)H_ij進行解碼計算，并將解碼計算結(jié)果沿著線形修復路徑進行傳送和合并，并將合并后的最終解碼結(jié)果發(fā)送給失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN：

3.1初始化信息，線形修復路徑節(jié)點序號j＝1；

3.2存儲節(jié)點Path[j]的修復程序接收來自控制節(jié)點的失效數(shù)據(jù)塊D_i修復請求、可用數(shù)據(jù)塊編號及其解碼系數(shù)H_ij、線形修復路徑數(shù)組Path、失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN的編號；

3.3存儲節(jié)點Path[j]的修復程序根據(jù)可用數(shù)據(jù)塊編號獲取本地存儲的可用數(shù)據(jù)塊E_j，進行本地解碼計算，將解碼系數(shù)H_ij與可用數(shù)據(jù)塊E_j進行逐位相乘，即，S_ij＝H_ij×E_j，解碼計算結(jié)果得到新數(shù)據(jù)塊S_ij；

3.4如果j＞1，存儲節(jié)點Path[j]的修復程序接收存儲節(jié)點Path[j]在線形修復路徑中的前繼存儲節(jié)點Path[j-1]發(fā)送來的解碼計算結(jié)果數(shù)據(jù)塊S_i(j-1），并將S_i(j-1）與本地解碼計算結(jié)果數(shù)據(jù)塊S_ij進行合并，即，S_ij＝S_ij+S_i(j-1)，將數(shù)據(jù)塊S_ij和S_i(j-1）進行逐位相加，轉(zhuǎn)第3.5步；否則，轉(zhuǎn)第3.5步；

3.5如果j＜k，存儲節(jié)點Path[j]的修復程序?qū)⒔獯a計算結(jié)果數(shù)據(jù)塊S_ij發(fā)送給存儲節(jié)點Path[j]在線形修復路徑中的后繼存儲節(jié)點Path[j+1]，轉(zhuǎn)第3.6步；否則，存儲節(jié)點Path[j]的修復程序?qū)⒔獯a計算結(jié)果數(shù)據(jù)塊S_ij發(fā)送給失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN，轉(zhuǎn)第四步；

3.6更新線形修復路徑節(jié)點序號，j＝j(luò)+1，轉(zhuǎn)第3.2步；

第四步，失效數(shù)據(jù)塊D_i的新存儲節(jié)點LN的修復程序接收來自線形修復路徑的最后一個存儲節(jié)點的最終解碼計算結(jié)果，向控制節(jié)點發(fā)送修復成功信息；

第五步，控制節(jié)點的結(jié)果回收程序接收來自存儲節(jié)點LN的修復成功信息，并向用戶返回修復成功信息。