隨著半導體和互聯(lián)網等新興技術的出現和發(fā)展，人們已經進入了大數據(Big Data)時代，數據存儲量正在以驚人的速度增加。如果存儲設備的某個存儲單元發(fā)生故障，其中的存儲數據就會丟失，從而造成損失。這一問題在大數據時代顯得尤為突出。因此，目前業(yè)內主流存儲公司(例如微軟、谷歌、百度等)都采用了可靠性增強技術，對存儲數據進行保護。

　　可靠性增強技術的基本方法是對原始數據增加一定冗余(Redundancy)[1]，使得用戶在讀取數據時，如果有存儲單元出現故障，可以盡量利用冗余數據恢復出原始數據。本文淺析了當前業(yè)界存儲系統(tǒng)中使用的兩種可靠性增強技術——數據復制(Replication)和刪除編碼(Erasure Coding)對存儲數據保護的原理。

　　數據復制是一種最簡單也是最常用的增加冗余的方法。圖1給出了這種方法的示意圖。

　　圖1 采用數據復制的存儲過程示意圖

　　在圖1中，每個方框代表一個存儲單元。藍色存儲單元中的數據為原始數據，粉色存儲單元中的數據為原始數據的復制。每個數據復制成為三份相同的數據進行存儲。用戶在數據讀取時，依次對三份數據進行讀取。若三份數據均讀取失敗則原始數據讀取失?。环駝t，將讀取的任意一份數據作為相應的原始數據?？梢钥闯?，只要三份相同數據中有一份可以讀出，就可以得到原始數據。

　　但是，采用上述復制方法，存儲利用率只有1/3。也就是說，僅有1/3的空間用來存儲有效數據，另外2/3的空間存儲的是冗余數據。因此，存儲利用率相對較低。為了克服這一問題，一些新穎的增加冗余的方法應運而生。其中刪除編碼是一種常用的方法。

　　刪除編碼的基本思想是將需要存儲的數據分成每K個一組，通過特定的編碼方式，增加個冗余數據，構成個數據進行存儲。選擇的編碼方式具有如下特征：若在N個數據中可以讀取任意不少于K個數據，就能恢復全部K個原始數據。刪除編碼的數據編碼及其讀取方法均基于多項式(Polynomial)求值進行的。下面以, 為例說明其基本原理。

　　圖2 采用刪除編碼的存儲過程示意圖

　　如圖2所示，假定需要存儲的兩個數據為字符A和B。下面求取增加的一個冗余數據。在ASCII表[2]中查得A和B的ASCII值分別為65和66。假定它們在平面直角坐標系中對應兩個點，坐標分別為A(1,65), B(2,66)，如圖3所示。

　　圖3 刪除編碼求取冗余數據示意圖

　　由平面幾何知識可知，這兩個點唯一確定一條直線。利用點A和點B的坐標可以求得該直線的函數方程為。增加冗余數據的方法是計算該函數在其它某個給定點的函數值。假定冗余數據對應，經計算可知其對應函數值為67，查ASCII表可知對應的字符為C。數據存儲過程見圖2，其中藍色存儲單元中的數據為原始數據，粉色存儲單元中的數據為冗余數據。需要指出的是，對于用戶來說，原始數據和冗余數據對應點的縱坐標是需要讀取或者計算得到的，但是橫坐標是預先知道的。下面分為三種情況討論數據讀取過程。

　　情況一：假定在數據讀取中前兩個存儲單元都沒有發(fā)生故障。根據數據的排列方式，依次取這兩個存儲單元中的字符，就得到了原始數據。需要說明的是，由于第三個存儲單元中存儲的是冗余數據(C)，因此無論其是否故障都不影響原始數據(A和B)的讀取。

　　情況二：假定在數據讀取中第一個存儲單元出現故障，后兩個單元中的數據可以讀取。此時可以得到點B和點C的坐標(2,66)和(3,67)。利用這兩個點的坐標，可以求得通過BC的直線方程。由于第一個存儲單元中的數據的對應點也在這條直線上，且橫坐標。因此，計算該點的函數值并查ASCII表可知對應的字符為A。此時，兩個原始數據都可以成功讀取。

　　情況三：假定在數據讀取中第二個存儲單元出現故障。與情況二完全類似，這時也可以成功讀取兩個原始數據。

　　綜合上面的分析可知，只要可以讀取任意不少于2個數據，就可以保證恢復出全部2個原始數據字符A和B。

　　一般地，若刪除編碼的參數為N和K，則原始數據對應平面的K個不同點。根據代數知識可知，這K個點可以確定一個次數不超過K的多項式函數。求取冗余數據的方法可歸結為計算該函數在其它個給定點的函數值。在數據讀取時，若原始數據有些不能讀取，但能夠讀取的數據數目不少于K，就可以通過求解線性方程組得到(即求出系數)，進而得到原始數據對應的K個點的函數值，恢復出原始數據。

　　需要指出的是，在實際存儲中，上述多項式不是定義在實數集上，而是定義在一種特殊的代數系統(tǒng)——有限域(Finite Field)上。由于篇幅所限，對于有限域的基本知識和相關運算就不加以介紹了，感興趣的讀者請參考文獻[3]。

　　不難看出，上述刪除編碼的存儲利用率為K/N。通過恰當選擇參數N和K(例如，N和K典型的取值為14和10)，可以使得其存儲利用率高于復制方法。但是，從數據讀取來看，刪除編碼比復制方法要復雜。此外，刪除編碼對數據的保護能力比復制方法可能要差一些。

　　在大數據時代，可靠性增強技術在數據存儲系統(tǒng)中發(fā)揮著非常重要的作用。隨著存儲系統(tǒng)的不斷發(fā)展，新穎的可靠性增強技術也在不斷涌現。希望讀者通過本文的介紹對這一技術有初步了解，并能產生興趣，從而進一步探索，發(fā)現更多有意義的結論。

　　參考文獻：

　　[1] 李揮，侯韓旭. 分布式存儲編碼與系統(tǒng)[M]. 北京：科學出版社，2016.

　　[2] 譚浩強. C程序設計(第四版)[M]. 北京：清華大學出版社，2010.

　　[3] 馮克勤，廖群英. 有限域及其應用[M]. 大連：大連理工大學出版社. 2011.