噴泉碼的分布式云存儲教學系統設計

袁 磊，付 饒，沈 鈺，任秀杰

（蘭州大學信息科學與工程學院，蘭州 730030）

0 引言

人工智能、第5 代移動通信和物聯網等技術的進步推動著我國智能化社會的發展，同時其所產生的數據正呈爆炸式增長，如何處理海量規模的數據成為了亟待解決的問題。針對大規模數據存儲領域中傳統存儲技術存在可拓展性差、成本高等問題，分布式云存儲技術憑借高可靠性、高擴展性和高可用性等優勢，成為物聯網中大規模數據存儲的主要方式。近年來，大規模分布式應用關注的焦點逐漸從“計算”向“數據”遷移［1-2］，分布式云存儲的相關理論、技術和系統方面的研究也得到了工業界的廣泛關注與應用，如百度云、華為云、iCloud等分布式云存儲服務。

物聯網課程作為一種融合了嵌入式系統、計算機軟件和網絡通信等多種技術與理論的應用型課程，能有效提高學生的工程實踐能力。在物聯網課程的以往教學中，我校主要以理論講授為主，電子信息類專業學生普遍反映缺乏足夠的實踐機會，使其綜合應用物聯網課程中的各種理論知識。同時相較于計算機類學生，電子信息類學生普遍存在軟件開發能力偏弱的問題，因此，如何通過工程實踐提升學生的綜合素養顯得尤為重要。有鑒于此，以我校電子信息類專業大三下學期開設的“物聯網技術及應用”課程進行改革為契機，基于物聯網領域的學科前沿知識和前期成果“IPv6協議下基于噴泉碼的P2P 文件分發系統設計與實現”（其于2019 年獲得第五屆下一代互聯網技術創新大賽二等獎），開發了一套基于噴泉碼的分布式云存儲實驗教學系統，通過利用Qt（一種C ＋＋圖形用戶界面應用程序開發框架）的跨平臺特性和新型糾刪碼噴泉碼，使學生掌握分布式云存儲系統開發的基本流程和原理。通過實驗，學生可以自主實現多層次糾刪碼編譯碼算法，還可靈活選用傳輸控制協議（Transmission Control Protocol，TCP）、用戶數據報協議（User Datagram Protocol，UDP）等網絡協議進行數據傳輸，以此增強學生的工程實踐能力、綜合應用能力以及創新意識。

1 系統背景

1.1 分布式云存儲和噴泉碼

分布式存儲是一種數據存儲技術，旨在通過將數據分散存儲在多臺獨立的設備上，達到大規模存儲的目的。云存儲是一種網絡在線存儲模式，即把信息存放在第三方托管的虛擬服務器上。分布式云存儲則是結合兩者的優勢，使不同類型的存儲設備集合起來協同工作，共同對外提供數據存儲服務，形成“物理分散，邏輯集中”的高效協同系統，系統架構如圖1 所示。分布式云存儲可以實現存儲資源的有效利用，避免存儲資源浪費，也可以將存儲文件保存在特定位置，提高安全性，是當下主流的存儲應用方式。

現有大型分布式云存儲系統的重要工作之一是數據保護［3］，為了防止節點故障造成的數據丟失，選擇合適的數據冗余保護策略尤為重要。多副本和糾刪碼是目前分布式云存儲系統中常用的兩種數據冗余保護策略。多副本策略中，最常用的是三副本技術，即將原始數據鏡像復制到3 個存儲節點上，文件恢復速度快，但存儲成本非常高［4］。糾刪碼策略是通過糾刪碼算法將原始的數據編碼得到冗余，并將數據和冗余一并存儲起來，以達到容錯的目的。它與傳統的多副本策略相比，具有冗余度低，磁盤利用率高等優點［5］。現有大型分布式云存儲系統，如Swift、Ceph 大多將里德－所羅門（Reed Solomon，RS）碼作為糾刪碼［6］，但諸如RS 碼之類的最大距離可分碼存在編譯碼復雜度高、修復帶寬開銷大的問題。因此，近年來又有學者陸續提出將低密度奇偶校驗（Low Density Parity Check，LDPC）碼、局部修復碼等作為新的糾刪碼應用到分布式云存儲系統中［7］，旨在降低編譯碼復雜度與修復帶寬開銷，但固定碼率的糾刪碼（如LDPC 碼）在多播廣播等傳輸場景下存在效率低下的問題。

噴泉碼是一類新穎且碼率不受限的線性糾刪碼，最初是為解決可靠多播廣播問題而提出。盧比變換（Luby Transform，LT）碼和Raptor 碼是目前主要的兩類噴泉碼，其中一種系統Raptor碼已被多個主流標準所采用，如用于多媒體廣播和組播業務的MBMS（Multimedia Broadcast Multicast Service）標準［8］。發送方通過對信息進行噴泉編碼，可以產生任意多的噴泉編碼包。接收方只要接收到略大于信息數目的噴泉編碼包，即可通過譯碼算法以高概率成功恢復原始數據。噴泉碼具有較低的編譯碼復雜度，通過與UDP協議相結合，可實現快速可靠地數據分發，尤為適合可靠多播廣播傳輸場景［9］。目前，噴泉碼除了在通信領域獲得了成功，在分布式云存儲領域中其作為糾刪碼數據保護策略也受到了學術界和工業界的廣泛關注，如文獻［10-11］中研究了基于LT 碼的分布式云存儲系統性能，美國昆騰公司的Lattus 對象存儲系統也采用了噴泉碼作為糾刪碼，文獻［12］中提出利用噴泉碼構造液態云存儲（Liquid Cloud Storage）系統的新概念。

1.2 教學系統創新

基于噴泉碼的分布式云存儲系統結合了噴泉碼優勢，創新構建多元化分層次實驗教學體系，系統創新架構如圖2 所示，其創新點如下：

圖2 系統創新架構

（1）教學內容豐富。遵循RFC5053 標準的系統噴泉碼（即R10 碼）［13］引入分布式存儲教學系統中，增強學生學習實際標準的意識。此外，該系統采用具有跨平臺特性的Qt 框架開發，方便跨平臺移植，學生也可以根據自己的興趣自主進行系統的圖形用戶界面（Graphical User Interface，GUI）設計。通過系統實驗，學生還可以有效學習C ＋＋、網絡編程、數據庫、通信傳輸協議等物聯網課程基礎知識，加深了學生對物聯網課程系統層次結構的理解，增強了學生的實踐能力。

（2）靈活使用傳輸層協議。傳統分布式存儲系統采用TCP協議作為傳輸層協議，其可靠性高，但也存在傳輸時延高、無法適應多播廣播傳輸等問題。2016年，谷歌提出基于UDP 的快速UDP 互聯網連接（Quick UDP Internet Connection，QUIC）協議取代傳統基于TCP 的超文本傳輸協議2.0（Hyper Text Transfer Protocol 2.0），以此提升傳輸效率［14］。UDP 協議具有快速、高效、適合多播廣播場景傳輸等特點，但其無法保證可靠傳輸，因此QUIC 協議采用了糾刪碼技術來保證UDP傳輸的可靠性。噴泉碼作為新近出現的糾刪碼方法，具有傳統糾刪碼所不具備的“無率”和“獨立”特性。有鑒于此，該教學系統靈活選擇兩種傳輸層協議，對傳輸信息量相對較少的控制流信息，使用TCP協議傳輸；對傳輸信息量較大的數據信息，采用UDP協議傳輸，將噴泉碼無碼率和動態生成獨立編碼包的特點與UDP 協議相結合，實現文件的快速可靠分發。

（3）分層次實驗教學。按實驗的難易程度和綜合知識量，建立了一套注重培養學生實際動手能力的分層次實驗教學體系。①在驗證型實驗中，注重系統的“實現＋驗證”，學生以小組為單位通過Qt 開發平臺，自主開發基于傳統三副本＋TCP模式的分布式存儲系統。在單用戶下載文件的場景下，通過模擬存儲節點宕機后文件能否正常恢復，驗證系統的存儲可靠性。②在綜合型實驗中，注重系統的“可靠＋高效”，學生通過實驗熟悉噴泉碼＋UDP 協議在其典型多用戶下載場景下所擁有的傳輸優勢。同時，學生可以自主實現不同難度的噴泉編譯碼算法，將其作為編譯碼模塊加入系統中，從而有效鍛煉自身編程能力。

2 系統設計

基于噴泉碼的分布式云存儲教學系統由噴泉編譯碼模塊、分布式存儲系統模塊兩部分組成。噴泉碼模塊貫穿于整個系統中，負責文件的編譯碼實現。本系統采用了兩種噴泉碼，即LT 碼、R10 碼。分布式云存儲系統模塊則主要負責系統架構與實現，其由客戶端、云服務器和云存儲節點三部分組成，具體模塊設計如下。

2.1 噴泉碼模塊

2.1.1 LT碼

LT碼是第1 個實用噴泉碼設計方案，其編碼過程如圖3 所示，首先將源文件劃分為k個等長輸入符號塊，然后利用度分布函數隨機均勻選取d（d≤k）個不同的符號塊，將這d個符號塊異或得到一個編碼符號塊。重復以上步驟n次，即可得到n個輸出編碼符號塊。

圖3 LT編碼過程

LT碼在刪除信道下的譯碼算法主要為置信傳播譯碼算法（Belief Propagation，BP）和及時高斯消元譯碼算法（On the Fly Gaussian Elimination，OFG）［15］兩種。在接收到一定數量的噴泉編碼符號塊后開始執行譯碼算法，如果文件恢復成功，則譯碼結束，否則繼續接收一定量的編碼符號塊，直到譯碼成功為止。BP譯碼的主要過程為首先在每一輪迭代中尋找度值為1 的編碼符號，將該編碼符號的值賦予與其連接的信息符號，再通過異或操作更新對應的編碼符號，重復步驟直到所有文件塊恢復成功。BP譯碼雖然譯碼簡單，但其譯碼性能比最優的極大似然譯碼算法差。OFG 譯碼算法則是一種快速極大似然譯碼算法實現，其通過將矩陣三角化操作分散到了譯碼器每一次接收編碼符號的過程中，有效地降低了譯碼復雜度，將譯碼復雜度控制在O（k2）。表1 給出了LT 碼的BP 和OFG 譯碼算法在不同譯碼開銷下的文件錯誤率（File Error Rate，FER），即源文件譯碼失敗概率，源文件大小k為200，度分布采用了參數c＝0，03，ε ＝0.5 的魯棒孤波度分布（Robust Soliton Degree Distribution）［18］，譯碼開銷定義為n／k－1。

表1 LT碼的BP和OFG的FER比較

2.1.2 R10 碼

相比于LT碼，Raptor碼具有更好的性能，其在LT碼的基礎上級聯了一個線性分組碼作為外碼，先將原始信息進行預編碼再將外碼的碼字作為LT 碼的輸入。

R10 碼是一種二進制的系統Raptor碼。RFC5053標準詳細規定了R10 碼的編譯碼算法，如圖4 所示。R10 碼的編碼過程是由k個源符號編碼產生修復符號的過程，分為兩個階段，第1 個階段由源符號預編碼產生中間符號；第2 個階段由中間符號進行LT 編碼，產生修復符號，其譯碼過程采用失活譯碼高斯消元（Inactivation Decoding Gaussian Elimination）算法。

圖4 R10碼編譯過程

2.2 分布式云存儲系統模塊

2.2.1 主要功能

客戶端是用戶操作及文件恢復的終端，在系統工作過程中的主要功能包括：①與云服務器交互控制信息及文件元數據信息（如文件名、文件大小和文件存儲位置等）；②與云服務器交互存儲文件；③與云存儲節點交互副本及噴泉編碼包；④譯碼恢復源文件。

云服務器是綜合調度整個系統的服務終端，主要功能包括：①與客戶端及云存儲節點交互控制信號，利用Qt支持的結構化查詢語言數據庫功能完成控制信號數據的組織和記錄；②與云存儲節點交互副本及噴泉編碼包。

云存儲節點用來存儲和傳輸副本及噴泉編碼包，其在系統工作過程中的主要功能包括：①存儲副本及噴泉編碼包；②與云服務器及客戶端交互副本及噴泉編碼包。

2.2.2 工作過程

系統工作模式分為傳統三副本＋TCP模式和噴泉碼＋UDP模式兩種，由云服務器選擇工作模式。傳輸層協議采用TCP 與UDP 協議：其中TCP 協議主要用于傳輸文件的控制流，以及在三副本模式下傳輸數據流，保證數據的可靠傳輸；UDP 協議主要用于在噴泉碼模式中傳輸數據流，將其與無須反饋的噴泉碼特性結合，可以實現快速可靠的文件分發，其工作過程如圖5 所示。

圖5 分布式云存儲系統模塊工作流程圖

文件上傳時，客戶端將要存儲的文件上傳到云服務器，其通過TCP 協議傳輸存儲控制信息、文件元數據信息及文件數據信息，其后云服務器采用TCP協議將文件數據信息傳輸到云存儲節點。在三副本模式中，云服務器將3 份文件數據信息存儲在不同的云存儲節點上。在噴泉碼模式中，云服務器將文件數據信息進行噴泉編碼，然后將編碼后的不同編碼包存儲在多個云存儲節點上。

文件下載時，客戶端和云服務器確定下載方式后，由云存儲節點向客戶端提供下載服務。在單用戶下載文件的場景下，三副本模式中n個存儲節點分別與客戶端建立TCP連接，分別傳輸文件的n分之一數據信息，達到并行下載的目的。在多用戶下載相同文件的場景下，噴泉碼模式中的云存儲節點利用UDP協議向客戶端廣播噴泉編碼包，客戶端接收到足夠的編碼包即可進行文件的譯碼恢復，如未譯碼成功，客戶端會繼續接收噴泉編碼包，直到文件恢復，達到可靠多播的目的。

3 分層次實驗實施

3.1 驗證型實驗：傳統三副本＋TCP 模式分布式云存儲系統的實現

傳統三副本分布式存儲通過跨節點的副本保護，可有效防止存儲節點宕機或磁盤損壞對數據恢復的影響。在單用戶下載文件的場景下，基于三副本機制的分布式云存儲系統可以有效保證文件數據恢復的可靠性。實驗在此基礎上設計而成，由以下三步組成。

（1）系統初步搭建。教師在課堂上給學生講解該系統的設計流程、工作原理，搭建流程后。學生以小組（4 或5 人）的形式，合理分配客戶端、云服務器、云存儲節點個數，安裝Qt開發環境，自主進行GUI設計，結合給定的參考偽代碼，初步搭建三副本分布式云存儲系統。

（2）系統功能開發。學生開發系統的主要功能，并通過文件的上傳和下載進行功能驗證。以5 人小組為例，分配1 個客戶端，1 個云服務器，3 個云存儲節點。客戶端將文件上傳后，云服務器與3 個云存儲節點建立TCP連接，將文件的副本分別存儲在3 個云存儲節點。下載時，3 個云存儲節點與客戶端建立TCP連接，并行傳輸文件的1／3 數據信息，在客戶端進行文件恢復，實現并行下載功能。

（3）模擬節點宕機。以5 人小組為例，學生在存儲文件后，使其中一個云存儲節點宕機，模擬存儲數據丟失情景。學生小組開發功能，使剩余的兩個云存儲節點通過TCP 連接向客戶端傳輸文件的1／2 數據信息，如文件可以正常恢復，則三副本分布式云存儲系統搭建成功。

在驗證型實驗中，通過利用三副本機制的分布式云存儲系統輔助教學，學生在搭建和使用的過程中可以形象、直觀地學習系統工作流程及存儲領域的前沿知識，同時提高學生的編程能力，極大地調動了學生的學習積極性。

3.2 綜合型實驗：噴泉碼＋UDP 模式分布式云存儲系統的實現

多用戶下載場景為噴泉碼＋UDP 協議的典型優勢應用場景。以5 客戶端下載為例，傳統三副本＋TCP方式中的3 個云存儲節點需要分別建立5 個TCP連接，為用戶發送副本信息，存在傳輸效率低下的問題。基于噴泉碼的分布式云存儲系統通過利用噴泉碼＋UDP廣播的優勢，只需要3 個云存儲節點分別建立1 個UDP連接向5 個客戶端廣播足夠的編碼包，多個用戶即可恢復源文件。學生小組配合進行實驗，實現該場景下基于噴泉碼的分布式云存儲系統，實驗由以下步驟組成。

（1）噴泉編譯碼算法實現。供學生選擇實現的編譯碼算法分為兩類：①LT 碼編碼＋BP 譯碼／OFG 譯碼；②遵循RFC5053 標準的R10 噴泉編譯碼，學生小組可根據能力自主選擇不同難度的兩種編譯碼算法。教師講解兩種編譯碼方案原理，提供設計文檔，教師在一段時間后提供文件編譯碼算法的偽代碼，學生小組通過Qt開發框架用C ＋＋語言實現文件的編譯碼。

（2）系統功能開發。學生將多臺客戶端加入系統，建立廣播組。同時在實驗1 實現系統的基礎上，開發云存儲節點的UDP廣播功能，通過文件能否正常恢復測試噴泉編譯碼模塊開發是否成功。文件上傳后，云服務器通過步驟1 實現的噴泉編譯碼模塊進行編碼，隨后將噴泉編碼包存儲在云存儲節點。文件下載時，多個客戶端接收云存儲節點UDP 廣播的編碼包，測試接收足夠多的編碼包后能否譯碼成功，如果譯碼成功，則噴泉碼＋UDP 廣播功能開發成功，完整系統如圖6 所示。

圖6 基于噴泉碼的分布式云存儲系統

通過綜合型實驗，學生不僅可以通過噴泉編譯碼算法的實現鍛煉編程能力和理解糾刪碼知識，還可以在理解網絡傳輸協議的基礎上，鍛煉知識遷移能力和工程實踐能力。

4 結語

本文設計的基于噴泉碼的分布式云存儲系統及教學實驗對標我校實踐教學的人才培養目標，具有極大的研究意義與價值。通過讓學生將理論學習與實際應用相結合，激發學生的學習興趣，充分發揮了學生的主觀能動性。該系統專業綜合程度高，知識覆蓋面廣，能夠有效培養電子信息類學生軟件開發的思維能力，鍛煉學生的編程能力，經過實踐取到了較好的教學效果，為理論學習與工程案例應用相結合提供了新的思路。在以后的研究中，可以嘗試把噴泉編譯碼算法換成性能更為優秀的RaptorQ 碼，譯碼程序中運算量較大的部分可以考慮放在圖形處理器上并行實現，從而提高編譯碼的性能，同時考慮將存儲節點從云端轉到邊緣，用以提高數據傳輸性能及降低網絡帶寬。