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

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

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

　　圖1 采用數(shù)據(jù)復制的存儲過程示意圖

　　在圖1中，每個方框代表一個存儲單元。藍色存儲單元中的數(shù)據(jù)為原始數(shù)據(jù)，粉色存儲單元中的數(shù)據(jù)為原始數(shù)據(jù)的復制。每個數(shù)據(jù)復制成為三份相同的數(shù)據(jù)進行存儲。用戶在數(shù)據(jù)讀取時，依次對三份數(shù)據(jù)進行讀取。若三份數(shù)據(jù)均讀取失敗則原始數(shù)據(jù)讀取失敗；否則，將讀取的任意一份數(shù)據(jù)作為相應的原始數(shù)據(jù)?？梢钥闯觯灰菹嗤瑪?shù)據(jù)中有一份可以讀出，就可以得到原始數(shù)據(jù)。

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

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

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

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

　　圖3 刪除編碼求取冗余數(shù)據(jù)示意圖

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

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

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

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

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

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

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

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

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

　　參考文獻：

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

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

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