[發明專利]一種基于改進型糾刪碼的失效數據修復方法

有效

• 申請號: 201410019879.4
• 申請日: 2014-01-16
• 公開（公告）號: CN103729151A
• 公開（公告）日: 2014-04-16
• 發明（設計）人: 王意潔;孫偉東;裴曉強;許方亮;符永銓;程力;李小勇;馬行空;王媛;趙越;林軒;熊澤宇
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F3/06
• 分類號: G06F3/06;H04L29/08
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

1.一種基于改進型糾刪碼的失效數據修復方法，其特征在于包括以下步驟：

第一步，構建一個分布存儲系統，它由多個節點構成，每個節點都是一臺可獨立運行的計算機，各節點通過網絡設備互連；

分布存儲系統中的節點分為兩類：控制節點和存儲節點，控制節點和存儲節點上均安裝有操作系統、TCP/IP協議軟件，配置了網絡環境；

分布存儲系統包括一個控制節點，負責與用戶交互，控制節點上安裝有數據寫入管理程序和數據修復程序；數據寫入管理程序接收用戶提交的數據對象寫入請求，負責存儲編碼系數，對數據對象進行分塊和編碼計算，向各存儲節點分發數據塊寫入請求；數據修復程序接收用戶提交的失效數據子塊修復請求，負責存儲解碼系數，從各存儲節點獲取可用數據子塊，進行解碼計算，完成修復后向用戶發送修復成功的數據子塊；

分布存儲系統包括N個存儲節點，N為正整數，它們負責存儲數據對象的原始數據塊和冗余數據塊，執行數據塊寫入任務和可用數據子塊讀取任務，所述原始數據塊由多個原始數據子塊組成，冗余數據塊由多個冗余數據子塊組成；

存儲節點上安裝有數據寫入程序和數據讀取程序，數據寫入程序負責接收來自控制節點的數據塊寫入請求，完成數據塊寫入任務，數據讀取程序負責接收來自控制節點的可用數據子塊讀取請求，讀取可用數據子塊，并發送給控制節點；

第二步，控制節點執行數據寫入管理程序，接收用戶提交的數據對象NDO，對數據對象NDO進行分塊和編碼計算，得到原始數據塊和冗余數據塊，將原始數據塊和冗余數據塊寫入存儲節點，具體步驟如下：

2.1控制節點的數據寫入管理程序接收用戶提交的數據對象NDO寫入請求；

2.2控制節點的數據寫入管理程序將數據對象NDO分割為k個原始數據塊，并將每個原始數據塊分割為f個原始數據子塊，記這k個原始數據塊為TD₁～TD_k，記原始數據塊TD_x分割的第y個原始數據子塊為td_xy，1≤x≤k，1≤y≤f；

2.3控制節點的數據寫入管理程序重新構建k個原始數據塊，記這k個原始數據塊為D₁～D_k，D_i包括f個原始數據子塊，D_i的第l個原始數據子塊記為d_il，i＝1,2,…,k，l＝1,2,…,f；

2.4控制節點的數據寫入管理程序利用存儲的編碼系數對k個原始數據塊即D₁～D_k的原始數據子塊進行編碼計算，得到m個冗余數據塊即C₁～C_m的冗余數據子塊，記D_i的第l個原始數據子塊為d_il，記C_j的第l個冗余數據子塊為c_jl，1≤i≤k，1≤j≤m，1≤l≤f，具體步驟如下：

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

2.4.1.1令冗余數據塊C_j的序號j＝1；

2.4.1.2令冗余數據子塊c_jl的序號l＝1；

2.4.1.3令原始數據塊D_i的序號i＝1；

2.4.2控制節點的數據寫入管理程序進行編碼計算，將編碼系數G_ji與原始數據子塊d_il進行逐位相乘，即，t_jil＝G_ji×d_il，得到新數據子塊t_jil；

2.4.3如果i=1，令c_jl＝t_jil，轉第2.4.4步；否則，將t_jil與c_jl進行逐位相加，即，c_jl＝c_jl+t_jil，轉第2.4.4步；

2.4.4更新原始數據塊D_i的序號，i＝i+1；

2.4.5如果i＞k，則令i＝1，l＝l+1；

2.4.6如果l＞f，則令l＝1，j＝j+1；

2.4.7如果j＞m，則轉第2.5步；否則，轉第2.4.2步；

2.5控制節點的數據寫入管理程序將D₁～D_k和C₁～C_m分別寫入不同的存儲節點，寫入存儲節點的數據對象記為DO；

第三步，控制節點執行數據修復程序，接收用戶提交的數據對象DO的失效數據子塊d_il修復請求；從數據對象DO的k+m-1個可用數據塊中任意選擇k個可用數據塊，采用存儲節點數組SNArray存儲這k個可用數據塊所在的存儲節點，SNArray[j]表示第j個可用數據塊所在的存儲節點，1≤j≤k；向k個可用數據塊所在的存儲節點發送可用數據子塊讀取請求、可用數據塊編號和待修復的失效數據子塊序號l；

第四步，k個可用數據塊所在的存儲節點即SNArray[1]～SNArray[k]同時執行數據讀取程序，接收來自控制節點的可用數據子塊讀取請求、可用數據塊編號和待修復的失效數據子塊序號l；根據可用數據塊編號獲取本地存儲的可用數據塊，記為E_j；根據待修復的失效數據子塊序號l讀取可用數據塊E_j中的數據子塊e_jl，將可用數據子塊e_jl發送給控制節點；

第五步，控制節點執行數據修復程序，接收來自SNArray[1]～SNArray[k]的可用數據子塊e_1l～e_kl，利用存儲的解碼系數H_i1～H_ik進行解碼計算，得到修復成功的數據子塊d_il，并向用戶發送數據子塊d_il，具體步驟如下：

5.1初始化信息，令存儲節點數組的節點序號j＝1；

5.2控制節點的數據修復程序接收來自存儲節點SNArray[j]的可用數據子塊e_jl；

5.3控制節點的數據修復程序進行解碼計算，將解碼系數H_ij與可用數據子塊e_jl進行逐位相乘，即，s_ijl＝H_ij×e_jl，得到新數據子塊s_ijl；

5.4如果j=1，那么，令d_il＝s_ijl，轉第5.5步；否則，將s_ijl與d_il進行逐位相加，即，d_il＝d_il+s_ijl，轉第5.5步；

5.5更新存儲節點數組的節點序號，j＝j+1；

5.6如果j＞k，轉第5.7步；否則，轉第5.2步；

5.7控制節點的數據修復程序向用戶發送修復的數據子塊d_il。