[發(fā)明專利]用于編碼數(shù)據(jù)的方法和裝置

有效

• 申請?zhí)枺?/td>: 201580083722.0
• 申請日: 2015-10-09
• 公開（公告）號: CN108156838B
• 公開（公告）日: 2021-02-12
• 發(fā)明（設(shè)計）人: 彼得·弗拉基米羅維奇·特里福;王元鋼;陳晨
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: H03M13/03
• 分類號: H03M13/03;H03M13/29;H03M13/37;G06F11/10;H03M13/15
• 代理公司: 廣州三環(huán)專利商標(biāo)代理有限公司 44202
• 代理人: 熊永強;李稷芳

本發(fā)明涉及對數(shù)據(jù)進(jìn)行編碼以存儲在n個存儲節(jié)點的存儲設(shè)備中，使得所述數(shù)據(jù)在多達(dá)r個存儲節(jié)點發(fā)生故障和多達(dá)s個存儲設(shè)備發(fā)生故障之后可恢復(fù)，其中，所述方法基于廣義級聯(lián)碼(generalized concatenated code，簡稱GCC)的構(gòu)建，其中，內(nèi)碼是捎帶碼。GCC構(gòu)造使人們能夠防止節(jié)點和設(shè)備故障的發(fā)生，而內(nèi)捎帶碼則可以減少節(jié)點重建階段通過網(wǎng)絡(luò)進(jìn)行傳輸?shù)臄?shù)據(jù)量。本發(fā)明的另一方面涉及對部分糾刪的編碼數(shù)據(jù)進(jìn)行恢復(fù)，其中，利用采用內(nèi)捎帶碼的所謂GCC構(gòu)造對編碼數(shù)據(jù)進(jìn)行編碼。

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

本發(fā)明涉及一種用于在n個存儲節(jié)點的存儲設(shè)備上對數(shù)據(jù)進(jìn)行編碼的裝置和方法，使得數(shù)據(jù)在多達(dá)r個存儲節(jié)點發(fā)生故障和多達(dá)s個存儲設(shè)備發(fā)生故障之后可恢復(fù)。本發(fā)明還涉及用于從部分糾刪的編碼數(shù)據(jù)對數(shù)據(jù)進(jìn)行恢復(fù)的方法和裝置。

本發(fā)明還涉及一種存儲程序代碼的計算機(jī)可讀存儲介質(zhì)，所述程序代碼包括指令，用于執(zhí)行一種用于對數(shù)據(jù)進(jìn)行編碼或從部分糾刪的編碼數(shù)據(jù)對數(shù)據(jù)進(jìn)行恢復(fù)的方法。

背景技術(shù)

考慮一個由n個服務(wù)器(節(jié)點)組成的存儲系統(tǒng)，其中，每個服務(wù)器包含ν個存儲設(shè)備。服務(wù)器和設(shè)備都可能會發(fā)生故障。糾刪編碼技術(shù)通常用于保護(hù)數(shù)據(jù)免受此類故障的影響。為了在故障后對數(shù)據(jù)進(jìn)行恢復(fù)，執(zhí)行糾刪解碼，其涉及從操作設(shè)備讀取數(shù)據(jù)以及對它的一些線性組合進(jìn)行計算。這涉及通過網(wǎng)絡(luò)進(jìn)行的數(shù)據(jù)傳輸。網(wǎng)絡(luò)數(shù)據(jù)傳輸是這種系統(tǒng)中最昂貴的操作。

最小存儲再生代碼為給定數(shù)量的可恢復(fù)服務(wù)器(節(jié)點)故障實現(xiàn)盡可能最低的冗余，并最大限度地減少重建階段期間通過網(wǎng)絡(luò)進(jìn)行傳輸?shù)臄?shù)據(jù)量。但是，這些代碼不能防止設(shè)備故障。

K.V.Rashmi、N.B.Shah和K.Ramchandran于2013年在電氣與電子工程師協(xié)會國際信息理論研討會上發(fā)布了《用于讀取和下載高效的分布式存儲代碼的捎帶設(shè)計框架》，以及K.V.Rashmi、N.B.Shah、D.Gu、H.Kuang、D.Borthakur和K.Ramchandran于2014年8月在《糾刪編碼數(shù)據(jù)中心中快速有效的數(shù)據(jù)重建指南》中介紹了一個所謂的捎帶框架。相應(yīng)地，取系統(tǒng)最大距離可分碼的多個碼字進(jìn)行組合，使得子分條i存儲其子分條1、2、……、i-1中數(shù)據(jù)的碼字和一些線性函數(shù)g_ij的和。子分條內(nèi)的校驗符號取決于相應(yīng)子分條內(nèi)的所有信息符號以及其他分條中的多個信息符號，這樣一來，對這些線性組合進(jìn)行選擇。

無論是捎帶代碼還是用于防止節(jié)點(服務(wù)器)故障的最小存儲再生代碼的現(xiàn)有構(gòu)造，都不會對設(shè)備故障提供保護(hù)。

此外，一些現(xiàn)有技術(shù)方法涉及修復(fù)操作期間通過網(wǎng)絡(luò)進(jìn)行傳輸?shù)拇罅繑?shù)據(jù)。

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

本發(fā)明的目的在于提供一種用于對數(shù)據(jù)進(jìn)行編碼以存儲在存儲設(shè)備中的裝置和方法，其中，該裝置和方法克服了現(xiàn)有技術(shù)中一個或多個上述問題。

根據(jù)本發(fā)明的第一方面，提供了一種用于對數(shù)據(jù)進(jìn)行編碼以存儲在n個存儲節(jié)點的存儲設(shè)備中的方法，使得所述數(shù)據(jù)在多達(dá)r個存儲節(jié)點發(fā)生故障和多達(dá)s個存儲設(shè)備發(fā)生故障之后可恢復(fù)，其中，所述方法包括：

-用一個或多個外碼對所述數(shù)據(jù)進(jìn)行外編碼以獲得外編碼數(shù)據(jù)；

-用一個或多個捎帶內(nèi)碼對所述外編碼數(shù)據(jù)進(jìn)行編碼以獲得編碼數(shù)據(jù)。

所提出的方法基于廣義級聯(lián)碼(generalized concatenated code，簡稱GCC)的構(gòu)建，其中，內(nèi)碼是捎帶碼。可以選擇內(nèi)碼和外碼的參數(shù)，從而達(dá)到所需的保護(hù)等級。GCC構(gòu)造使人們能夠防止節(jié)點和設(shè)備故障的發(fā)生，而內(nèi)捎帶碼則可以減少節(jié)點重建階段通過網(wǎng)絡(luò)進(jìn)行傳輸?shù)臄?shù)據(jù)量。

通過取長度為n的基碼的m個碼字以及在基碼的第i個碼字中添加基碼碼字0、……、i-1的信息符號的一些線性組合，獲得GF(q)^m上長度為n的捎帶碼的碼字。以這種方式選擇特定的系數(shù)，使得在節(jié)點修復(fù)的情況下，要通過網(wǎng)絡(luò)進(jìn)行傳輸?shù)臄?shù)據(jù)量最小化。