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

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

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

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

　　在圖1中，每個(gè)方框代表一個(gè)存儲(chǔ)單元。藍(lán)色存儲(chǔ)單元中的數(shù)據(jù)為原始數(shù)據(jù)，粉色存儲(chǔ)單元中的數(shù)據(jù)為原始數(shù)據(jù)的復(fù)制。每個(gè)數(shù)據(jù)復(fù)制成為三份相同的數(shù)據(jù)進(jìn)行存儲(chǔ)。用戶(hù)在數(shù)據(jù)讀取時(shí)，依次對(duì)三份數(shù)據(jù)進(jìn)行讀取。若三份數(shù)據(jù)均讀取失敗則原始數(shù)據(jù)讀取失敗；否則，將讀取的任意一份數(shù)據(jù)作為相應(yīng)的原始數(shù)據(jù)。可以看出，只要三份相同數(shù)據(jù)中有一份可以讀出，就可以得到原始數(shù)據(jù)。

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

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

　　圖2 采用刪除編碼的存儲(chǔ)過(guò)程示意圖

　　如圖2所示，假定需要存儲(chǔ)的兩個(gè)數(shù)據(jù)為字符A和B。下面求取增加的一個(gè)冗余數(shù)據(jù)。在ASCII表[2]中查得A和B的ASCII值分別為65和66。假定它們?cè)谄矫嬷苯亲鴺?biāo)系中對(duì)應(yīng)兩個(gè)點(diǎn)，坐標(biāo)分別為A(1,65), B(2,66)，如圖3所示。

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

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

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

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

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

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

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

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

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

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

　　參考文獻(xiàn)：

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

　　[2] 譚浩強(qiáng). C程序設(shè)計(jì)(第四版)[M]. 北京：清華大學(xué)出版社，2010.

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