基于糾刪碼冗余技術(shù)中的數(shù)據(jù)可靠性技術(shù)的研究

毛紅霞

摘 要：本文將糾刪碼冗余技術(shù)應(yīng)用于云存儲(chǔ)系統(tǒng)中。采用基于RS糾刪碼的數(shù)據(jù)分片方法，把用戶數(shù)據(jù)分成若干分片分別存儲(chǔ)到不同存儲(chǔ)節(jié)點(diǎn)。在拜占庭故障的情況下，不同的m個(gè)分片的子集可能解碼出不同的數(shù)據(jù)塊，所以使用分片驗(yàn)證技術(shù)來(lái)確保分片來(lái)自于唯一正確的數(shù)據(jù)塊，從而保證數(shù)據(jù)的可靠性。

關(guān)鍵詞：糾刪碼冗余技術(shù)；數(shù)據(jù)分片

1.糾刪碼冗余技術(shù)的原理

一般來(lái)說(shuō)，糾刪碼可以用一個(gè)四元組（n，k，b，k）來(lái)表示，其中，k是編碼前文件塊的個(gè)數(shù)，b是每個(gè)文件塊包含的比特?cái)?shù)，k是一個(gè)不小于k的數(shù)，n是編碼后的文件塊個(gè)數(shù)[1]。

糾刪碼冗余技術(shù)用于存儲(chǔ)系統(tǒng)中的步驟是：

（1）將文件數(shù)據(jù)劃分成k個(gè)文件塊，每個(gè)文件塊的大小都是相等的，包含b bits。

（2）使用糾刪碼函數(shù)E進(jìn)行編碼，得到n個(gè)文件塊，并且每個(gè)文件塊大小相等，并且有唯一的標(biāo)識(shí)。

（3）將這n個(gè)文件塊根據(jù)分布式存儲(chǔ)策略存儲(chǔ)到相應(yīng)的存儲(chǔ)節(jié)點(diǎn)上。

（4）存儲(chǔ)系統(tǒng)中的任意k個(gè)數(shù)據(jù)塊通過(guò)解碼函數(shù)D都可以還原成原始文件。

2.數(shù)據(jù)分片技術(shù)

在將RS糾刪碼應(yīng)用于云存儲(chǔ)系統(tǒng)時(shí)，首先將用戶的數(shù)據(jù)文件分成X+1個(gè)大小相等的數(shù)據(jù)段，對(duì)每一個(gè)數(shù)據(jù)段使用糾刪碼的編碼函數(shù)進(jìn)行編碼，并將數(shù)據(jù)塊Di和校驗(yàn)塊Dj按下標(biāo)分別存放到不同的文件分片中，文件分片流程如圖2所示。

通過(guò)分片之后得到的文件分片都包含數(shù)據(jù)塊和校驗(yàn)塊兩部分。文件分片根據(jù)云存儲(chǔ)的分布式存儲(chǔ)策略存儲(chǔ)在不同的存儲(chǔ)服務(wù)器上，只要有任意k個(gè)分片能夠正常使用，系統(tǒng)就能完全恢復(fù)用戶的原始文件。單個(gè)文件分片的泄漏或存儲(chǔ)服務(wù)器的故障也不會(huì)影響用戶的數(shù)據(jù)信息，從而保障了云存儲(chǔ)中用戶數(shù)據(jù)的可靠性[2]。

3.數(shù)據(jù)分片驗(yàn)證一致性策略

基于糾刪碼冗余技術(shù)的云存儲(chǔ)系統(tǒng)中，每個(gè)存儲(chǔ)節(jié)點(diǎn)上只存儲(chǔ)經(jīng)過(guò)編碼后的某個(gè)文件分片，經(jīng)過(guò)權(quán)限驗(yàn)證后的正確客戶至少要讀取m個(gè)分片才能解碼出原始數(shù)據(jù)。但存在拜占庭故障的情況下，不同的 m 個(gè)分片的子集可能解碼出不同的數(shù)據(jù)塊，所以客戶在寫數(shù)據(jù)分片時(shí)必須要同時(shí)將檢驗(yàn)數(shù)據(jù)同時(shí)寫入，確保文件的分片均來(lái)自于唯一的源數(shù)據(jù)塊。

Krawczyk 提出了分布式指紋的概念，可以用于對(duì)數(shù)據(jù)分片的驗(yàn)證。實(shí)質(zhì)上是一種稱為交叉校驗(yàn)和（crossed checksum，簡(jiǎn)稱 cc）的結(jié)構(gòu)[3]，將每個(gè)文件分片進(jìn)行哈希運(yùn)算，得到相應(yīng)的哈希值，具體數(shù)據(jù)結(jié)構(gòu)如圖3所示。

一般情況下，客戶讀操作時(shí)先從讀取到的分片中恢復(fù)出數(shù)據(jù)塊 B，然后用糾刪碼將 B編碼生成n個(gè)分片，再分別哈希每一個(gè)分片，與交叉檢驗(yàn)碼中的對(duì)應(yīng)部分相比較，如果全部都一致，那么數(shù)據(jù)驗(yàn)證成功，即重構(gòu)的源數(shù)據(jù)是正確的，編碼前的數(shù)據(jù)是相等的，代碼如下，驗(yàn)證過(guò)程如圖4所示[4]。

4.總結(jié)

為了解決云中數(shù)據(jù)丟失或失效的問(wèn)題，采用基于RS糾刪碼的數(shù)據(jù)分片機(jī)制，把用戶數(shù)據(jù)分成若干分片分別存儲(chǔ)到不同存儲(chǔ)節(jié)點(diǎn)。數(shù)據(jù)分片的驗(yàn)證技術(shù)可以確保用戶數(shù)據(jù)的可靠性與完整性。

參考文獻(xiàn)

[1]何潤(rùn)潤(rùn).基于糾刪碼的數(shù)據(jù)冗余策略研究.機(jī)電技術(shù)，2010 . 5

[2]余林琛，章 巍，林 強(qiáng)，許杰星，鐘 貝. RS糾刪碼在云存儲(chǔ)中的應(yīng)用. 微電子學(xué)與計(jì)算機(jī)，2011.8

[3]王寶林.糾刪碼分片驗(yàn)證技術(shù)研究.電腦知識(shí)與技術(shù)，2010-2.

[4]蔡鸞佳.拜占庭容錯(cuò)糾刪碼分布式存儲(chǔ)協(xié)議.計(jì)算機(jī)系統(tǒng)應(yīng)用，2012-21-2