文 /郝樹華 安紅心 袁磊

隨著互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的飛速發(fā)展，越來越多的信息需要存儲到計算機網(wǎng)絡(luò)中。例如一個視頻碼率為8Mbit/s的攝像頭一天將產(chǎn)生超過86G的信息，一個智慧城市中的交通和安防攝像頭的數(shù)目至少幾十萬個并且還在增長，它們每天產(chǎn)生的信息都需要存儲在互聯(lián)網(wǎng)中。又如在教育行業(yè)新興的慕課、騰訊課堂以及各種教育資源也需要占用大量的存儲空間。信息量的爆炸式增長帶來了如何高效、低成本、可靠存儲信息的難題。一些重要信息的毀壞或丟失將帶來非常嚴(yán)重的后果，提高存儲信息的可靠性和降低存儲成本是一個極其重要的研究方向。大數(shù)據(jù)時代下，可靠保存和有效管理信息變得尤為重要。大型數(shù)據(jù)中心的規(guī)模有幾千到幾萬臺存儲服務(wù)器，如百度最大的數(shù)據(jù)中心服務(wù)器設(shè)計裝機規(guī)模超過16萬臺，將承擔(dān)80%的流量，眾多的服務(wù)器設(shè)備的升級、維修等耗費巨大，并且不能完全保證用戶存儲的信息不丟失。例如谷歌、亞馬遜等存儲服務(wù)系統(tǒng)都曾出現(xiàn)過問題。一種有效降低成本的辦法是將眾多普通存儲設(shè)備組合起來構(gòu)成一個分布式存儲系統(tǒng)。為了保證信息的高可靠性，常用的方法是副本方式。副本就是對原始文件進行完全復(fù)制，這種做法占用存儲空間大，副本存儲占用空間是原始文件大小的整數(shù)倍，如微軟、亞馬遜等公司都采用過三副本方式存放新創(chuàng)建的數(shù)據(jù)[1]。之后研究人員將具有防止數(shù)據(jù)丟失特性的糾刪碼(Erasure Correcting Codes)引入存儲領(lǐng)域，糾刪編碼技術(shù)相對于副本存儲技術(shù)具有更高的存儲效率[2]。常用的糾刪碼有里德所羅門編碼(RS碼, Reed Solomon Codes)、局部重構(gòu)編碼(LRC碼,Local Reconstruction Codes)。將糾刪碼應(yīng)用于存儲集群的實例如谷歌在其GFS文件系統(tǒng)增加了RS碼支持，它采用了最基本的RS (6,3)編碼，最多可允許包括數(shù)據(jù)塊和校驗塊在內(nèi)的任意3個塊錯誤；Facebook早期在HDFS RAID中采用的編碼方式為RS(10,4)，進階版“HDFS”采用了LRC(10,6,5)[1]。噴泉碼(Fountain Codes)是一類碼率不受限的糾刪碼[3,4]，與普通糾刪碼(如RS碼、LRC碼)相比，噴泉碼更適合于分布式存儲系統(tǒng)，因為它的編譯碼復(fù)雜度低得多，并且它能任意調(diào)整冗余比例[5]。分布式存儲系統(tǒng)引入噴泉碼之后，經(jīng)過編碼可以產(chǎn)生任意大小的編碼文件而不必是原始文件的整數(shù)倍，并且編碼后的文件將建立各個文件塊之間的聯(lián)系，即受到破壞的文件塊可以由其他已恢復(fù)文件進行譯碼恢復(fù)，從而提高了存儲信息的可靠性。

蘭州大學(xué)

國內(nèi)現(xiàn)階段網(wǎng)絡(luò)資源存儲基本都是基于IPv4設(shè)計與實現(xiàn)的。IPv6是用來替代現(xiàn)行版本IPv4的下一代IP協(xié)議。IPv4使用的是32位地址，而IPv6使用128位地址，這表示有340萬億個地址可以使用。并且IPv6使用更小的路由表，提高了路由器轉(zhuǎn)發(fā)數(shù)據(jù)包的速度，減少網(wǎng)絡(luò)傳輸時延；IPv6可以對網(wǎng)絡(luò)層的數(shù)據(jù)進行加密并對IP報文進行校驗，極大地增強了網(wǎng)絡(luò)的安全性。2017年，中共中央辦公廳、國務(wù)院辦公廳印發(fā)了《推進互聯(lián)網(wǎng)協(xié)議第六版(IPv6)規(guī)模部署行動計劃》，該行動計劃旨在加快推進基于互聯(lián)網(wǎng)協(xié)議第六版(IPv6)的下一代互聯(lián)網(wǎng)規(guī)模部署，促進互聯(lián)網(wǎng)演進升級和健康創(chuàng)新發(fā)展[6]。

蘭州大學(xué)作為CERNET、CNGI-CERNET2在甘肅省的中心節(jié)點，在1999年初開始進行關(guān)于IPv6的實驗性研究，是國內(nèi)最早建成的功能齊全的IPv6試驗床，并通過CNGI-CERNET2主干網(wǎng)建設(shè)和駐地網(wǎng)建設(shè)，在學(xué)校全網(wǎng)范圍開通了IPv6/IPv4雙協(xié)議棧接入[6]。目前蘭州大學(xué)校園網(wǎng)IPv6全覆蓋，為IPv6協(xié)議下的實驗奠定了物理基礎(chǔ)。本文設(shè)計實現(xiàn)了IPv6網(wǎng)絡(luò)中基于噴泉碼的分布式存儲原理系統(tǒng)，該系統(tǒng)采用C++語言在Qt開發(fā)框架下完成[7]，實現(xiàn)了文件的噴泉編碼、分布式存儲、譯碼恢復(fù)等功能，實測結(jié)果表明IPv6網(wǎng)絡(luò)中基于噴泉碼的分布式存儲系統(tǒng)具有高效可靠的性能。本文所提方案為蘭州大學(xué)校內(nèi)資源快速、穩(wěn)定、可靠存儲提供了一種新的設(shè)計思路。

噴泉碼介紹

噴泉碼最早起源于通信領(lǐng)域，是針對刪除信道下大規(guī)模數(shù)據(jù)廣播和分發(fā)的需求提出的解決方案[4]。該方案通過對傳輸信息進行編碼傳輸，以解決傳輸過程中信息丟失的問題。由于噴泉碼具有無碼率、編碼后節(jié)點地位相同等特點，將其引入分布式存儲領(lǐng)域代替普通糾刪碼，可以提高存儲可靠性和降低編譯碼復(fù)雜度[5]。

上世紀(jì)90年代Luby等人首次提出噴泉碼的概念，但并未給出實用的設(shè)計方案[4]。其基本思想是將一個原始文件分成一定數(shù)目的文件塊，每個編碼塊都是由任意個文件塊異或得到，接收端只要接收到足夠數(shù)量的編碼塊，即可完成譯碼恢復(fù)原始文件。由于參與編碼的文件塊是隨機選擇的，并且數(shù)目任意，理論上可以產(chǎn)生無限多的編碼塊，故具有無碼率的特點。這個過程像是噴泉源源不斷噴出水滴，故取名為噴泉碼[3,4]。隨后Luby提出第一個實用噴泉碼設(shè)計方案：LT(Luby Transform)碼[8]，之后噴泉碼技術(shù)便推向了具體應(yīng)用[9]，目前，一種系統(tǒng)噴泉碼已被3GPP組織的多媒體廣播多播業(yè)務(wù) (MBMS, Multimedia Broadcast Multicast Service)標(biāo)準(zhǔn)所采用[10]。本文設(shè)計的基于噴泉碼的分布式存儲系統(tǒng)便采用了LT碼。

圖1 LT碼編碼示意圖

LT碼原理

1.LT碼編碼過程

將信源文件劃分為k個輸入文件塊。譯碼開銷(overhead)定義為N/k-1，其中，N是接收端接收的編碼塊的數(shù)目，編碼過程如下，示意圖如圖1所示。

（1）首先由節(jié)點的度分布函數(shù)產(chǎn)生一個度值d；

（2）均勻隨機地從k個輸入文件塊中選取d個文件塊；

（3）將選取的文件塊進行二進制異或運算，得到編碼塊；

（4）重復(fù)上述3個步驟N次，得到N個編碼塊。

2.度分布

度分布的設(shè)計是LT碼的關(guān)鍵，為了高效可靠譯碼，Luby首先提出了理想孤波度分布(ISDD, Ideal Soliton Degree Distribution)，表達式如下：

其中，k為原始文件劃分為文件塊的數(shù)目，p(d)為選擇度為d的概率。在ISDD下，編碼塊節(jié)點度平均值約為lnk，這種度分布在實際中工作表現(xiàn)不佳，度為1的節(jié)點概率約為1/k，但在實際譯碼過程中的波動會導(dǎo)致沒有度為1的編碼塊，從而導(dǎo)致譯碼終止。針對這些不足之處，Luby引入了兩個額外的參數(shù)c和δ，構(gòu)成魯棒孤波度分布(RSDD, Robust Soliton Degree Distribution)。首先，定義

3. LT碼譯碼原理

LT碼在刪除信道下的譯碼包括置信傳播 (BP，Belief Propagation) 譯碼算法和極大似然 (ML，Maximum Likelihood) 譯碼算法。

（1）置信傳播譯碼算法

接收端收到N個編碼塊后（N稍大于k），即有可能完成譯碼，恢復(fù)原始文件。假定k個輸入文件塊分別表示為S1，S2，. .. ，Sk，接收的N個編碼塊分別表示為Y1，Y2，. . . ，YN，譯碼過程如下：

圖2 LT碼BP譯碼過程示例

a.首先找到度為1的編碼塊Yi，將其賦值給它連接的輸入文件塊，即St=Yi；

b.找出與輸入文件塊St連接的編碼塊進行異或運算，并將所有與St相連的邊刪除，也就是將G矩陣中相應(yīng)位置零；

c.再次尋找度為1的編碼塊，返回步驟a，直到所有輸入文件塊被恢復(fù)。如果沒有度為1的編碼塊，則譯碼停止。

LT碼的譯碼過程可以用二部圖(Bipartite Graph)表示，下文列舉了一個簡單示例，并稱輸入文件塊為變量節(jié)點，編碼塊為校驗節(jié)點，不失一般性，假定每個塊只包含1比特信息，如圖2所示。圖2(a)中的校驗節(jié)點信息為0110。在第一次迭代中首先找到度為1的校驗節(jié)點：第一個校驗節(jié)點Y1。將Y1賦值給與其相連的變量節(jié)點S1，刪除兩節(jié)點的邊，如圖2(b)。并找到與S1相連的校驗節(jié)點，對其進行異或操作，并刪除所連接的邊，如圖2(c)。重復(fù)步驟1，找到度為1的校驗節(jié)點，并將其賦值給與之相連的變量節(jié)點，如圖2(d)。重復(fù)步驟2，將變量節(jié)點S2的值與其相連的校驗節(jié)點異或，刪除連接的邊。最后，如圖2(e)，重復(fù)步驟1、2將S3恢復(fù)。最終如圖2(f)所示，恢復(fù)出的變量節(jié)點信息為001。

如果在譯碼過程中找不到度為1的校驗節(jié)點則譯碼停止[7,8]，此時如果原始文件仍不能完全恢復(fù)，則需要繼續(xù)接收更多編碼塊進行譯碼，直到譯碼成功為止。實際中，當(dāng)輸入文件塊k約為10000時，LT碼譯碼成功所需譯碼開銷大約在5%[4]，因此，BP譯碼算法適合于大型文件的恢復(fù)。

（2）極大似然譯碼算法

刪除信道下，將線性分組碼進行極大似然譯碼的本質(zhì)是求解線性方程組，求解的過程可以通過高斯消元法 (GE，Gaussian Elimination) 實現(xiàn)。LT 碼的GE譯碼算法性能優(yōu)于BP譯碼算法，但是，GE 譯碼算法復(fù)雜度O(k3)遠高于 BP 譯碼算法復(fù)雜度O(klogk)。因此，當(dāng)輸入塊較少時采用GE譯碼算法是可行的[10]。即時高斯消元 (OFG，On the Fly Gaussian Elimination) 譯碼算法是實現(xiàn) GE 譯碼的一種有效算法，進一步將復(fù)雜度降低為O(k2)[11]。本文設(shè)計的分布式存儲系統(tǒng)在存儲小型文件時采用OFG譯碼算法恢復(fù)原始文件。表1和表2給出了BP和OFG譯碼算法在不同譯碼開銷下的文件錯誤率(FER, File Error Rate)即原始文件譯碼失敗概率，其中，原始文件大小k分別為200和1000，度分布采用了參數(shù)為c=0.03，ε=0.5的RSDD。

表1 k=200時BP和OFG譯碼性能比較

表2 k=1000時BP和OFG譯碼性能比較

由表1和表2可以看出，隨著原始文件劃分?jǐn)?shù)目k的增加，在相同譯碼開銷下，BP譯碼算法和OFG譯碼算法的性能都得到了改善。但是，當(dāng)原始文件數(shù)目劃分較少時，如k為200或1000時，在相同譯碼開銷下，OFG譯碼算法的FER明顯低于BP譯碼算法，其性能至少相差一個數(shù)量級。

噴泉碼與副本存儲性能比較

將原始文件分為k個文件塊，副本存儲和噴泉碼存儲都采用三倍冗余方式。假定其中任意一個文件塊失效的概率為ε(0＜ε＜1)，對于副本存儲而言，若副本存儲中任意一個文件塊的三份備份全部失效則整個文件無法恢復(fù)，表3給出了k為200和1000時，不同刪除概率(即文件塊失效的概率)下的FER仿真結(jié)果：

由表3可以看出當(dāng)k=200和ε=0.3時，三副本存儲方式的FER接近1。對于噴泉碼方案而言，當(dāng)ε=0.3時，可用于譯碼恢復(fù)原始文件的編碼塊數(shù)目為420，即譯碼開銷為2.1。由表1可知當(dāng)譯碼開銷為0.3時，OFG譯碼算法的FER為0.008，因此，當(dāng)譯碼開銷為2.1時，其FER遠低于10-3。由以上分析可知，噴泉碼存儲可靠性遠優(yōu)于副本存儲。k為200和1000時的仿真結(jié)果表明，隨著k的增加，副本存儲方案的性能變差，如ε=0.2和k=200時，三副本存儲方式的FER為0.788，當(dāng)k增加到1000時，其FER增加到1。對于噴泉碼存儲方案則不同，當(dāng)k越大時，其譯碼性能越好。

表3 三副本方案下不同刪除概率的FER

得到上述結(jié)果的原因是噴泉碼產(chǎn)生的編碼塊地位完全等同，即不存在先后順序的問題，并且編碼塊的重要程度相同。編碼塊建立了參與編碼的文件塊之間的聯(lián)系，取消了各個文件塊的獨立性。將這個特性引入存儲系統(tǒng)之后，即使存儲系統(tǒng)存在一部分編碼塊的損毀，用戶只需要獲取足夠數(shù)量的編碼塊就能通過譯碼恢復(fù)原始文件塊，而不必精確恢復(fù)丟失的編碼塊。在傳統(tǒng)分布式存儲系統(tǒng)中，當(dāng)某一文件塊的全部副本損毀后，由于文件塊不完整則導(dǎo)致整個文件恢復(fù)失敗。因此引入噴泉碼可以提高整個系統(tǒng)的存儲可靠性。

時間復(fù)雜度分析

副本存儲方式是原始文件塊的鏡像復(fù)制，不需要編譯碼過程。噴泉碼編碼一個文件塊的復(fù)雜度為O(logk)，GE 譯碼算法復(fù)雜度O(k3)遠高于 BP 譯碼算法復(fù)雜度O(klogk)。即時高斯消元(OFG，On the Fly Gaussian Elimination) 譯碼算法是實現(xiàn) GE 譯碼的一種有效算法，進一步將復(fù)雜度降低為O(k2)[11]。為了進一步說明譯碼時間復(fù)雜度，分別對BP和OFG譯碼時間進行統(tǒng)計，得到譯碼平均時間見表4，其中，原始文件大小k為 1000，RSDD參數(shù)與2.3.2節(jié)相同，時間單位為秒(s)。

表4 k=1000時BP和OFG譯碼時間比較

系統(tǒng)設(shè)計

蘭州大學(xué)校園已實現(xiàn)IPv6全覆蓋，本文設(shè)計的存儲系統(tǒng)依托蘭州大學(xué)IPv6網(wǎng)絡(luò)環(huán)境，存儲節(jié)點分別位于本部校區(qū)的飛云樓、網(wǎng)絡(luò)中心和榆中校區(qū)圖書館。這樣就實現(xiàn)了不同教學(xué)樓和不同校區(qū)之間的分布式存儲，通過異地存儲提高數(shù)據(jù)的安全性。系統(tǒng)部署方案如圖3所示。

本實驗平臺為基于噴泉碼的分布式存儲系統(tǒng)，該系統(tǒng)由6臺PC級存儲節(jié)點、一臺客戶端節(jié)點和一臺服務(wù)器節(jié)點組成。每個存儲節(jié)點的配置為：英特爾Core i5-8400 @ 2.80GHz 六核CPU，鎂光8GB DDR3內(nèi)存，希捷ST2000DM006-2DM164 4TB硬盤，主板集成的千兆以太網(wǎng)網(wǎng)卡，Windows 7 64位操作系統(tǒng)。服務(wù)器端配置為：英特爾 Core i7-8700k @ 3.70GHz六核CPU，金泰克16GB DDR4內(nèi)存，希捷ST2000DM006-2DM164 2TB硬盤，主板集成的千兆以太網(wǎng)網(wǎng)卡，Windows 7 64位操作系統(tǒng)?？蛻舳伺渲脼椋篈MD Ryzen 7 1700 Eight-Core Processor 八核CPU，金泰克16GB DDR4內(nèi)存，主板集成的千兆以太網(wǎng)網(wǎng)卡，Windows 7 64位操作系統(tǒng)。

圖3 系統(tǒng)部署方案

整個系統(tǒng)測試的基本流程可分為以下幾個步驟：

1.基于IPv6環(huán)境在蘭州大學(xué)本部飛云樓、網(wǎng)絡(luò)中心和榆中校區(qū)圖書館各放置兩臺存儲PC節(jié)點，客戶端和服務(wù)器位于蘭州大學(xué)本部校區(qū)飛云樓內(nèi)；

2.選擇125MB大小的MKV格式的視頻文件（其代表一個小型文件）和 1.5GB大小的Zip壓縮格式文件（其代表一個大型文件）分別進行3倍冗余LT編碼；

3.客戶端向服務(wù)器請求文件存儲，服務(wù)器選擇合適的存儲節(jié)點并通知客戶端向存儲節(jié)點存放合適大小的編碼塊文件；

4.客戶端向服務(wù)器請求下載編碼塊文件，服務(wù)器依據(jù)一定的路由選擇算法從離客戶端由近及遠的存儲節(jié)點進行下載；

5.客戶端下載一定數(shù)量的編碼塊后，根據(jù)文件大小采用合適的譯碼算法恢復(fù)原始文件，若譯碼失敗則繼續(xù)下載額外的編碼塊再次進行譯碼，直到譯碼成功為止。

LT碼編碼模塊

存儲的LT碼編碼數(shù)據(jù)相比于編碼塊多了4個字節(jié)的種子(Seed)信息，偽隨機數(shù)生成算法利用種子來產(chǎn)生編譯碼所需要的度和編碼塊的生成向量。種子信息和編碼塊存放在不同文件中。其中每個種子信息占4B，每個編碼塊數(shù)據(jù)占128KB。由于噴泉編碼只進行異或操作，所以編碼塊與原始文件塊大小相同。度分布函數(shù)采用RSDD，其參數(shù)為c=0.03，ε =0.5。

設(shè)計的LT碼編碼步驟見表5：

表5 LT碼編碼步驟

LT碼譯碼模塊

本文設(shè)計的系統(tǒng)涉及到BP譯碼模塊和OFG譯碼模塊，分別描述見表6、7。

本系統(tǒng)的譯碼過程具體設(shè)計為：首次譯碼時，先下載1.05×k個編碼塊完成譯碼，如果無法成功譯碼，則再每次下載0.05×k個編碼塊再次譯碼，直到恢復(fù)原始文件為止。

表6 LT碼BP譯碼步驟

表7 LT碼OFG譯碼步驟

關(guān)于本系統(tǒng)大小文件的劃分：原始文件劃分塊數(shù)k小于5000(即625M)視為小型文件，采用OFG譯碼算法，否則視其為大型文件，采用BP譯碼算法。根據(jù)4.1節(jié)提到的編碼塊大小為128KB，則125MB大小的mkv文件劃分為1000個文件塊，視為小型文件，采用OFG譯碼算法。1.5GB的zip文件大約可分為12288塊，可視為大型文件，采用BP譯碼算法。

系統(tǒng)主要組成單元功能描述

服務(wù)器的功能包括：1.利用數(shù)據(jù)庫完成文件信息的組織和記錄，本系統(tǒng)采用的數(shù)據(jù)庫模塊為Qt支持的SQLite數(shù)據(jù)庫，其生成的db文件可以保存文件信息，如文件名、類型和大小等；2.根據(jù)最短路徑優(yōu)先準(zhǔn)則選擇合適的存儲節(jié)點并通知客戶端；3.負(fù)責(zé)記錄編碼塊文件的種子信息文件。

當(dāng)客戶端需要存儲文件時，首先選擇文件并進行LT編碼，然后，通過TCP協(xié)議將適量的編碼塊文件傳輸?shù)椒?wù)器選擇的存儲節(jié)點，并將相應(yīng)的種子信息文件保存到服務(wù)器。當(dāng)客戶端需要下載文件時，首先從服務(wù)器獲知存儲節(jié)點的IPv6地址，并下載相應(yīng)種子文件信息，其次，通過TCP協(xié)議將適量的編碼塊文件下載到客戶端，最后依據(jù)原始文件大小選擇相應(yīng)譯碼算法并恢復(fù)原始文件。

客戶端實現(xiàn)

Qt是一個跨平臺應(yīng)用程序和UI開發(fā)框架。本系統(tǒng)基于Qt開發(fā)的客戶端界面主要包括打開文件按鈕、噴泉編碼按鈕、存儲按鈕、刪除按鈕、下載按鈕、譯碼按鈕和文件信息列表，如圖4所示。完成的功能有對文件進行LT編碼、存儲、下載、譯碼恢復(fù)和刪除操作?？蛻舳薎Pv6地址為2001:da8:c000:2021:3925:cfa4:bdbb:18da。

圖4 系統(tǒng)客戶端界面

程序啟動后客戶端首先與服務(wù)器交互信息，獲得服務(wù)器上存儲的文件信息列表，并將其顯示在客戶端文件信息列表中。當(dāng)客戶端需要存儲文件時，首先選擇文件進行LT編碼。其次，點擊存儲按鈕與服務(wù)器通信，將種子信息文件保存在服務(wù)器，編碼塊文件則保存在服務(wù)器選擇的存儲節(jié)點中。當(dāng)文件存儲完成后，其信息會顯示在文件信息列表。當(dāng)客戶端有不需要的文件時可以將其刪除，但是，只能刪除自身上傳的文件。當(dāng)文件譯碼成功或被刪除時，其信息也將從信息列表刪除。當(dāng)客戶端需要下載文件時，首先從文件信息列表選擇文件，點擊下載按鈕，服務(wù)器返回存儲節(jié)點的IPv6地址和相應(yīng)的種子文件信息，客戶端從存儲節(jié)點下載編碼塊文件?？蛻舳藫碛芯幋a文件后即可進行譯碼恢復(fù)原始文件。當(dāng)譯碼失敗時，繼續(xù)請求服務(wù)器下載種子信息文件和編碼塊文件，再次進行譯碼，直到譯碼成功為止。每次完成存儲、刪除和譯碼操作后，服務(wù)器向客戶端發(fā)送XML文件用以更新文件信息列表。

本文在IPv6網(wǎng)絡(luò)中設(shè)計實現(xiàn)了基于噴泉碼的分布式存儲系統(tǒng)，該系統(tǒng)在相同存儲開銷下，相比于副本存儲的系統(tǒng)進一步提高了信息存儲的可靠性，在相同可靠性下降低了存儲空間的使用，提高了空間利用率，但是也相應(yīng)地增加了編譯碼的時間開銷。進一步的研究方向為：可以對一些訪問頻度高的熱數(shù)據(jù)采用副本存儲的方式，對一些訪問頻度低的冷數(shù)據(jù)采用噴泉碼存儲方式。