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

毛紅霞

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

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

1.糾刪碼冗余技術的原理

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

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

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

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

（3）將這n個文件塊根據(jù)分布式存儲策略存儲到相應的存儲節(jié)點上。

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

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

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

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

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

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

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

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

4.總結

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

參考文獻

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

[2]余林琛，章 巍，林 強，許杰星，鐘 貝. RS糾刪碼在云存儲中的應用. 微電子學與計算機，2011.8

[3]王寶林.糾刪碼分片驗證技術研究.電腦知識與技術，2010-2.

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