[發(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
• 代理人: 郭敏

技術(shù)領(lǐng)域

本發(fā)明涉及分布存儲系統(tǒng)的數(shù)據(jù)容錯方法，尤其是基于糾刪碼的失效數(shù)據(jù)修復方法。

背景技術(shù)

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

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

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

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

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

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

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

盡管隨著技術(shù)的進步，各種軟硬件資源的可靠性得到了顯著提高，但是，隨著存儲資源規(guī)模的不斷擴大，資源的失效概率明顯上升。此外，為了有效降低維護成本，失效資源不會逐一及時更新，而是成批維護的。在大規(guī)模分布存儲系統(tǒng)中，資源失效是一種常態(tài)行為。由此可見，在大規(guī)模分布存儲系統(tǒng)中，失效數(shù)據(jù)修復對于保證系統(tǒng)的容錯能力至關(guān)重要。

雖然在擁有相同容錯能力的前提下，基于糾刪碼的容錯技術(shù)在存儲開銷方面具有明顯優(yōu)勢，但是，在數(shù)據(jù)塊失效時，基于糾刪碼的容錯技術(shù)需要多個數(shù)據(jù)塊才能解碼恢復失效的原始數(shù)據(jù)塊，需要占用較多的網(wǎng)絡(luò)帶寬資源，從而影響失效數(shù)據(jù)的修復效率。

現(xiàn)有的數(shù)據(jù)修復方法主要包括星形修復方法和樹形修復方法：

（1）星形修復方法是：為失效數(shù)據(jù)塊選擇的新存儲節(jié)點從若干可用存儲節(jié)點獲取可用數(shù)據(jù)塊，并由失效數(shù)據(jù)塊的新存儲節(jié)點負責解碼計算得到修復數(shù)據(jù)塊。

（2）樹形修復方法是：首先，構(gòu)建以失效數(shù)據(jù)塊的新存儲節(jié)點為根、可用存儲節(jié)點為子節(jié)點的生成樹；然后，從葉節(jié)點逐級向上傳輸數(shù)據(jù)，每級節(jié)點對本地存儲的可用數(shù)據(jù)塊進行解碼計算，與其子節(jié)點上傳的數(shù)據(jù)合并后發(fā)送給其父節(jié)點；根節(jié)點（即，失效數(shù)據(jù)塊的新存儲節(jié)點）負責完成最后的解碼計算得到修復數(shù)據(jù)塊。