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

本發(fā)明屬于計(jì)算機(jī)存儲(chǔ)技術(shù)領(lǐng)域，具體涉及一種基于糾刪碼的數(shù)據(jù)塊重建方法，可減少重建數(shù)據(jù)傳輸。

背景技術(shù)

從RAID(獨(dú)立硬盤(pán)冗余陣列)到分布式存儲(chǔ)系統(tǒng)，糾刪碼廣泛應(yīng)用于存儲(chǔ)系統(tǒng)中，用于防止部分?jǐn)?shù)據(jù)丟失或數(shù)據(jù)服務(wù)器宕機(jī)導(dǎo)致的數(shù)據(jù)不可訪問(wèn)。

糾刪碼是一種數(shù)據(jù)保護(hù)的編碼方法，它首先將原始數(shù)據(jù)分為等大的數(shù)據(jù)塊，然后再將數(shù)據(jù)塊編碼為校驗(yàn)塊。當(dāng)若干個(gè)數(shù)據(jù)塊或校驗(yàn)塊丟失時(shí)，糾刪碼技術(shù)保證原始數(shù)據(jù)仍然可以恢復(fù)。

傳統(tǒng)的編碼方法將原始數(shù)據(jù)等分為k份數(shù)據(jù)塊，編碼生成m份校驗(yàn)塊并將它們存儲(chǔ)在k+m個(gè)不同的存儲(chǔ)節(jié)點(diǎn)。存儲(chǔ)節(jié)點(diǎn)是存儲(chǔ)設(shè)備的邏輯抽象，既可以是一個(gè)磁盤(pán)也可以是一個(gè)存儲(chǔ)服務(wù)器。所有(k+m)塊數(shù)據(jù)塊和校驗(yàn)塊中的任意k塊都可以重建出k個(gè)數(shù)據(jù)塊。但是這類糾刪碼也面臨著一個(gè)修復(fù)帶寬問(wèn)題：重建一個(gè)數(shù)據(jù)塊需要該數(shù)據(jù)塊大小的k倍磁盤(pán)I/O和網(wǎng)絡(luò)流量，占用大量的存儲(chǔ)資源和網(wǎng)絡(luò)資源。

以(n,k)里德-所羅門(mén)編碼為例，n是數(shù)據(jù)塊和校驗(yàn)塊的總個(gè)數(shù)，k是數(shù)據(jù)塊個(gè)數(shù)，m＝n-k是校驗(yàn)塊個(gè)數(shù)。當(dāng)使用(n,k)里德-所羅門(mén)編碼對(duì)數(shù)據(jù)量為M的文件進(jìn)行編碼時(shí)，首先將文件等分為k個(gè)數(shù)據(jù)塊：D₀、D₁、…、D_k-1，每個(gè)數(shù)據(jù)塊大小為M/k，接著計(jì)算生成矩陣和k個(gè)數(shù)據(jù)塊的乘積(計(jì)算基于有限域)，得到m個(gè)校驗(yàn)塊C₀、C₁、…、C_m-1，每個(gè)校驗(yàn)塊大小也是M/k。(n,k)里德-所羅門(mén)編碼的生成矩陣是一個(gè)基于有限域GF(2^w)的m行k列的矩陣，該矩陣可以是變換后的范德?tīng)柮傻戮仃?Vandermonde matrix)，也可以是柯西矩陣(Cauchy matrix)。當(dāng)一個(gè)數(shù)據(jù)塊或校驗(yàn)塊失效時(shí)，需要重建數(shù)據(jù)塊或校驗(yàn)塊以保證可靠性。如果失效的是校驗(yàn)塊，利用k塊數(shù)據(jù)塊可以重新編碼得到；如果失效的是數(shù)據(jù)塊，利用剩余n-1塊數(shù)據(jù)塊和校驗(yàn)塊中的任意k塊可重建該數(shù)據(jù)塊。無(wú)論是失效的是一塊數(shù)據(jù)塊還是一塊校驗(yàn)塊，都需要k塊整塊數(shù)據(jù)塊或校驗(yàn)塊進(jìn)行重建，所需要的數(shù)據(jù)量是M。

現(xiàn)有減少單數(shù)據(jù)節(jié)點(diǎn)失效所需重建數(shù)據(jù)量的編碼方法往往犧牲了最優(yōu)的存儲(chǔ)效率或者最大距離可分(MDS)性質(zhì)。簡(jiǎn)單再生碼(Simple Regenerating Codes，見(jiàn)論文："Simple regenerating codes:Network coding for cloud storage."INFOCOM,2012Proceedings IEEE.IEEE,2012.)在每個(gè)存儲(chǔ)節(jié)點(diǎn)多存儲(chǔ)1/f的數(shù)據(jù)量，f越大，額外的存儲(chǔ)開(kāi)銷越小，但相應(yīng)的修復(fù)帶寬也越大，反之亦然。局部重建碼(Local Reconstruction Codes，見(jiàn)論文："Erasure Coding in Windows Azure Storage."USENIX Annual Technical Conference.2012.)將數(shù)據(jù)塊分組，不僅在組內(nèi)進(jìn)行編碼，并在組間進(jìn)行編碼，這樣可以將大部分單點(diǎn)失效的重建局限在組內(nèi)進(jìn)行，從而減少了重建數(shù)據(jù)量，但局部重建碼需要額外的存儲(chǔ)開(kāi)銷，且不滿足MDS性質(zhì)。功能性最小存儲(chǔ)再生碼(Functional Minimum Storage Regenerating codes，見(jiàn)論文：NCCloud:A Network-Coding-Based Storage System in a Cloud-of-Clouds[J].2013.)雖然存儲(chǔ)和修復(fù)單個(gè)節(jié)點(diǎn)失效所需要的數(shù)據(jù)量都是最優(yōu)的，但存在計(jì)算開(kāi)銷大，且保存的不是原來(lái)的數(shù)據(jù)，因此讀取數(shù)據(jù)時(shí)需要解碼等缺點(diǎn)。

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

本發(fā)明提供一種基于糾刪碼的數(shù)據(jù)塊重建方法，解決現(xiàn)有數(shù)據(jù)塊修復(fù)方法需要傳輸大量數(shù)據(jù)的問(wèn)題，以減少重建數(shù)據(jù)的傳輸量。

本發(fā)明所提供的一種基于糾刪碼的數(shù)據(jù)塊重建方法，包括數(shù)據(jù)分塊步驟、構(gòu)造生成矩陣G步驟、生成校驗(yàn)塊步驟、檢查數(shù)據(jù)塊狀態(tài)步驟、構(gòu)造修復(fù)矩陣步驟和修復(fù)數(shù)據(jù)塊步驟，其特征在于：

(1)數(shù)據(jù)分塊步驟：

將數(shù)據(jù)量為M的原始文件等分為k個(gè)數(shù)據(jù)塊D_j，j＝0、…、k-1，再將k個(gè)數(shù)據(jù)塊分別保存在k個(gè)數(shù)據(jù)節(jié)點(diǎn)上，進(jìn)而將各數(shù)據(jù)節(jié)點(diǎn)上的數(shù)據(jù)塊D_j等分為r個(gè)數(shù)據(jù)片D_j,p，p＝0、…、r-1，r＝m^k-1，k≥2，m≥2；等分過(guò)程中不足部分用0補(bǔ)齊并記錄不足數(shù)據(jù)塊或數(shù)據(jù)片的長(zhǎng)度；