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

有效

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

技術領域

本發明涉及分布存儲系統的數據容錯方法，尤其是基于糾刪碼的失效數據修復方法。

背景技術

數據容錯是海量數據分布存儲的關鍵技術之一，數據容錯對于提高系統的可用性和可靠性至關重要。目前，數據容錯技術主要包括基于復制的容錯技術和基于糾刪碼的容錯技術。

基于復制的容錯技術簡單直觀，易于實現和部署，需要為每個數據對象創建若干同樣大小的副本，存儲空間開銷較大?；诩m刪碼的容錯技術通過將數據對象分割為多個數據塊，通過利用糾刪碼算法對原始的數據塊進行編碼得到冗余的數據塊，把多個數據塊的信息融合到較少的冗余信息中，有效節省存儲空間。與基于復制的容錯技術相比，基于糾刪碼的容錯技術具有冗余度低、存儲空間利用率高等優點，已經逐步成為大數據時代數據容錯的主流技術。

基于糾刪碼的容錯技術的基本思想是對k個原始數據塊進行編碼計算得到m個冗余數據塊；只需k+m個數據塊中的任意k個數據塊，就可通過解碼計算恢復得到原始的k個數據塊。

具體而言，每個冗余數據塊C_j（j＝1,2,…,m）都是k個原始數據塊D_i（i＝1,2,…,k）的線性組合，編碼計算可表示為公式（1），其中，G_ji（j＝1,2,…,m，i＝1,2,…,k）是數據塊編碼系數。也就是說，對于冗余數據塊C_j（j＝1,2,…,m）而言，首先，編碼系數G_ji（i＝1,2,…,k）與數據塊D_i（i＝1,2,…,k）進行逐位相乘，得到k個新數據塊T_ji＝G_ji×D_i（i＝1,2,…,k）；然后，k個新數據塊T_ji（i＝1,2,…,k）進行逐位相加，得到冗余數據塊

G_j1×D₁+…+G_ji×D_i+…+G_jk×D_k=C_j???（1）

每個原始數據塊D_i（i＝1,2,…,k）都是其它任意k個可用數據塊E_j（j＝1,2,…,k）（原始數據塊或者冗余數據塊）的線性組合，解碼計算可表示為公式（2），其中，H_ij（i＝1,2,…,k，j＝1,2,…,k）是數據塊解碼系數。也就是說，對于原始數據塊D_i（i＝1,2,…,k）而言，首先，解碼系數H_ij（j＝1,2,…,k）與可用數據塊E_j（j＝1,2,…,k）進行逐位相乘，得到k個新數據塊S_ij＝H_ij×E_j（j＝1,2,…,k）；然后，k個新數據塊S_ij（j＝1,2,…,k）進行逐位相加，得到原始數據塊

H_i1×E₁+…+H_ij×E_j+…+H_ik×E_k=D_i???（2）

糾刪碼的編解碼計算對內存空間的需求取決于數據塊的大小。隨著海量數據規模的不斷增大，數據對象的大小和數據對象的數目都呈現出逐漸增長的趨勢。數據對象越來越大直接導致數據塊大小不斷變大，從而使得糾刪碼的編解碼計算對內存空間的需求越來越大，甚至超出服務器的內存容量。

為了有效實現糾刪碼的編解碼計算，一個原始數據塊（冗余數據塊）可以進一步劃分為f個原始數據子塊（冗余數據子塊），即，原始數據塊D_i（i＝1,2,…,k）劃分為f個原始數據子塊d_il（l＝1,2,…,f），冗余數據塊C_j（j＝1,2,…,m）劃分為f個冗余數據子塊c_jl（l＝1,2,…,f）。糾刪碼的編解碼計算可以在原始數據子塊和冗余數據子塊之間進行，從而降低編解碼計算對內存空間的需求。