基于糾刪碼冗余技術中的數據可靠性技術的研究

毛紅霞

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

關鍵詞：糾刪碼冗余技術；數據分片

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

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

糾刪碼冗余技術用于存儲系統中的步驟是：

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

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

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

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

2.數據分片技術

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

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

3.數據分片驗證一致性策略

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

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

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

4.總結

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

參考文獻

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

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

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

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