IPv6網絡中基于噴泉碼的分布式存儲系統研究

文 /郝樹華 安紅心 袁磊

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

蘭州大學

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

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

噴泉碼介紹

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

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

圖1 LT碼編碼示意圖

LT碼原理

1.LT碼編碼過程

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

（1）首先由節點的度分布函數產生一個度值d；

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

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

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

2.度分布

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

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

3. LT碼譯碼原理

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

（1）置信傳播譯碼算法

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

圖2 LT碼BP譯碼過程示例

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

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

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

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

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

（2）極大似然譯碼算法

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

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

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

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

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

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

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

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

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

時間復雜度分析

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

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

系統設計

蘭州大學校園已實現IPv6全覆蓋，本文設計的存儲系統依托蘭州大學IPv6網絡環境，存儲節點分別位于本部校區的飛云樓、網絡中心和榆中校區圖書館。這樣就實現了不同教學樓和不同校區之間的分布式存儲，通過異地存儲提高數據的安全性。系統部署方案如圖3所示。

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

圖3 系統部署方案

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

1.基于IPv6環境在蘭州大學本部飛云樓、網絡中心和榆中校區圖書館各放置兩臺存儲PC節點，客戶端和服務器位于蘭州大學本部校區飛云樓內；

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

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

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

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

LT碼編碼模塊

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

設計的LT碼編碼步驟見表5：

表5 LT碼編碼步驟

LT碼譯碼模塊

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

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

表6 LT碼BP譯碼步驟

表7 LT碼OFG譯碼步驟

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

系統主要組成單元功能描述

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

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

客戶端實現

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

圖4 系統客戶端界面

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

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