袁 磊,付 饒,沈 鈺,任秀杰
(蘭州大學(xué)信息科學(xué)與工程學(xué)院,蘭州 730030)
人工智能、第5 代移動通信和物聯(lián)網(wǎng)等技術(shù)的進步推動著我國智能化社會的發(fā)展,同時其所產(chǎn)生的數(shù)據(jù)正呈爆炸式增長,如何處理海量規(guī)模的數(shù)據(jù)成為了亟待解決的問題。針對大規(guī)模數(shù)據(jù)存儲領(lǐng)域中傳統(tǒng)存儲技術(shù)存在可拓展性差、成本高等問題,分布式云存儲技術(shù)憑借高可靠性、高擴展性和高可用性等優(yōu)勢,成為物聯(lián)網(wǎng)中大規(guī)模數(shù)據(jù)存儲的主要方式。近年來,大規(guī)模分布式應(yīng)用關(guān)注的焦點逐漸從“計算”向“數(shù)據(jù)”遷移[1-2],分布式云存儲的相關(guān)理論、技術(shù)和系統(tǒng)方面的研究也得到了工業(yè)界的廣泛關(guān)注與應(yīng)用,如百度云、華為云、iCloud等分布式云存儲服務(wù)。
物聯(lián)網(wǎng)課程作為一種融合了嵌入式系統(tǒng)、計算機軟件和網(wǎng)絡(luò)通信等多種技術(shù)與理論的應(yīng)用型課程,能有效提高學(xué)生的工程實踐能力。在物聯(lián)網(wǎng)課程的以往教學(xué)中,我校主要以理論講授為主,電子信息類專業(yè)學(xué)生普遍反映缺乏足夠的實踐機會,使其綜合應(yīng)用物聯(lián)網(wǎng)課程中的各種理論知識。同時相較于計算機類學(xué)生,電子信息類學(xué)生普遍存在軟件開發(fā)能力偏弱的問題,因此,如何通過工程實踐提升學(xué)生的綜合素養(yǎng)顯得尤為重要。有鑒于此,以我校電子信息類專業(yè)大三下學(xué)期開設(shè)的“物聯(lián)網(wǎng)技術(shù)及應(yīng)用”課程進行改革為契機,基于物聯(lián)網(wǎng)領(lǐng)域的學(xué)科前沿知識和前期成果“IPv6協(xié)議下基于噴泉碼的P2P 文件分發(fā)系統(tǒng)設(shè)計與實現(xiàn)”(其于2019 年獲得第五屆下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新大賽二等獎),開發(fā)了一套基于噴泉碼的分布式云存儲實驗教學(xué)系統(tǒng),通過利用Qt(一種C ++圖形用戶界面應(yīng)用程序開發(fā)框架)的跨平臺特性和新型糾刪碼噴泉碼,使學(xué)生掌握分布式云存儲系統(tǒng)開發(fā)的基本流程和原理。通過實驗,學(xué)生可以自主實現(xiàn)多層次糾刪碼編譯碼算法,還可靈活選用傳輸控制協(xié)議(Transmission Control Protocol,TCP)、用戶數(shù)據(jù)報協(xié)議(User Datagram Protocol,UDP)等網(wǎng)絡(luò)協(xié)議進行數(shù)據(jù)傳輸,以此增強學(xué)生的工程實踐能力、綜合應(yīng)用能力以及創(chuàng)新意識。
分布式存儲是一種數(shù)據(jù)存儲技術(shù),旨在通過將數(shù)據(jù)分散存儲在多臺獨立的設(shè)備上,達到大規(guī)模存儲的目的。云存儲是一種網(wǎng)絡(luò)在線存儲模式,即把信息存放在第三方托管的虛擬服務(wù)器上。分布式云存儲則是結(jié)合兩者的優(yōu)勢,使不同類型的存儲設(shè)備集合起來協(xié)同工作,共同對外提供數(shù)據(jù)存儲服務(wù),形成“物理分散,邏輯集中”的高效協(xié)同系統(tǒng),系統(tǒng)架構(gòu)如圖1 所示。分布式云存儲可以實現(xiàn)存儲資源的有效利用,避免存儲資源浪費,也可以將存儲文件保存在特定位置,提高安全性,是當(dāng)下主流的存儲應(yīng)用方式。
現(xiàn)有大型分布式云存儲系統(tǒng)的重要工作之一是數(shù)據(jù)保護[3],為了防止節(jié)點故障造成的數(shù)據(jù)丟失,選擇合適的數(shù)據(jù)冗余保護策略尤為重要。多副本和糾刪碼是目前分布式云存儲系統(tǒng)中常用的兩種數(shù)據(jù)冗余保護策略。多副本策略中,最常用的是三副本技術(shù),即將原始數(shù)據(jù)鏡像復(fù)制到3 個存儲節(jié)點上,文件恢復(fù)速度快,但存儲成本非常高[4]。糾刪碼策略是通過糾刪碼算法將原始的數(shù)據(jù)編碼得到冗余,并將數(shù)據(jù)和冗余一并存儲起來,以達到容錯的目的。它與傳統(tǒng)的多副本策略相比,具有冗余度低,磁盤利用率高等優(yōu)點[5]?,F(xiàn)有大型分布式云存儲系統(tǒng),如Swift、Ceph 大多將里德-所羅門(Reed Solomon,RS)碼作為糾刪碼[6],但諸如RS 碼之類的最大距離可分碼存在編譯碼復(fù)雜度高、修復(fù)帶寬開銷大的問題。因此,近年來又有學(xué)者陸續(xù)提出將低密度奇偶校驗(Low Density Parity Check,LDPC)碼、局部修復(fù)碼等作為新的糾刪碼應(yīng)用到分布式云存儲系統(tǒng)中[7],旨在降低編譯碼復(fù)雜度與修復(fù)帶寬開銷,但固定碼率的糾刪碼(如LDPC 碼)在多播廣播等傳輸場景下存在效率低下的問題。
噴泉碼是一類新穎且碼率不受限的線性糾刪碼,最初是為解決可靠多播廣播問題而提出。盧比變換(Luby Transform,LT)碼和Raptor 碼是目前主要的兩類噴泉碼,其中一種系統(tǒng)Raptor碼已被多個主流標(biāo)準(zhǔn)所采用,如用于多媒體廣播和組播業(yè)務(wù)的MBMS(Multimedia Broadcast Multicast Service)標(biāo)準(zhǔn)[8]。發(fā)送方通過對信息進行噴泉編碼,可以產(chǎn)生任意多的噴泉編碼包。接收方只要接收到略大于信息數(shù)目的噴泉編碼包,即可通過譯碼算法以高概率成功恢復(fù)原始數(shù)據(jù)。噴泉碼具有較低的編譯碼復(fù)雜度,通過與UDP協(xié)議相結(jié)合,可實現(xiàn)快速可靠地數(shù)據(jù)分發(fā),尤為適合可靠多播廣播傳輸場景[9]。目前,噴泉碼除了在通信領(lǐng)域獲得了成功,在分布式云存儲領(lǐng)域中其作為糾刪碼數(shù)據(jù)保護策略也受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注,如文獻[10-11]中研究了基于LT 碼的分布式云存儲系統(tǒng)性能,美國昆騰公司的Lattus 對象存儲系統(tǒng)也采用了噴泉碼作為糾刪碼,文獻[12]中提出利用噴泉碼構(gòu)造液態(tài)云存儲(Liquid Cloud Storage)系統(tǒng)的新概念。
基于噴泉碼的分布式云存儲系統(tǒng)結(jié)合了噴泉碼優(yōu)勢,創(chuàng)新構(gòu)建多元化分層次實驗教學(xué)體系,系統(tǒng)創(chuàng)新架構(gòu)如圖2 所示,其創(chuàng)新點如下:
圖2 系統(tǒng)創(chuàng)新架構(gòu)
(1)教學(xué)內(nèi)容豐富。遵循RFC5053 標(biāo)準(zhǔn)的系統(tǒng)噴泉碼(即R10 碼)[13]引入分布式存儲教學(xué)系統(tǒng)中,增強學(xué)生學(xué)習(xí)實際標(biāo)準(zhǔn)的意識。此外,該系統(tǒng)采用具有跨平臺特性的Qt 框架開發(fā),方便跨平臺移植,學(xué)生也可以根據(jù)自己的興趣自主進行系統(tǒng)的圖形用戶界面(Graphical User Interface,GUI)設(shè)計。通過系統(tǒng)實驗,學(xué)生還可以有效學(xué)習(xí)C ++、網(wǎng)絡(luò)編程、數(shù)據(jù)庫、通信傳輸協(xié)議等物聯(lián)網(wǎng)課程基礎(chǔ)知識,加深了學(xué)生對物聯(lián)網(wǎng)課程系統(tǒng)層次結(jié)構(gòu)的理解,增強了學(xué)生的實踐能力。
(2)靈活使用傳輸層協(xié)議。傳統(tǒng)分布式存儲系統(tǒng)采用TCP協(xié)議作為傳輸層協(xié)議,其可靠性高,但也存在傳輸時延高、無法適應(yīng)多播廣播傳輸?shù)葐栴}。2016年,谷歌提出基于UDP 的快速UDP 互聯(lián)網(wǎng)連接(Quick UDP Internet Connection,QUIC)協(xié)議取代傳統(tǒng)基于TCP 的超文本傳輸協(xié)議2.0(Hyper Text Transfer Protocol 2.0),以此提升傳輸效率[14]。UDP 協(xié)議具有快速、高效、適合多播廣播場景傳輸?shù)忍攸c,但其無法保證可靠傳輸,因此QUIC 協(xié)議采用了糾刪碼技術(shù)來保證UDP傳輸?shù)目煽啃浴娙a作為新近出現(xiàn)的糾刪碼方法,具有傳統(tǒng)糾刪碼所不具備的“無率”和“獨立”特性。有鑒于此,該教學(xué)系統(tǒng)靈活選擇兩種傳輸層協(xié)議,對傳輸信息量相對較少的控制流信息,使用TCP協(xié)議傳輸;對傳輸信息量較大的數(shù)據(jù)信息,采用UDP協(xié)議傳輸,將噴泉碼無碼率和動態(tài)生成獨立編碼包的特點與UDP 協(xié)議相結(jié)合,實現(xiàn)文件的快速可靠分發(fā)。
(3)分層次實驗教學(xué)。按實驗的難易程度和綜合知識量,建立了一套注重培養(yǎng)學(xué)生實際動手能力的分層次實驗教學(xué)體系。①在驗證型實驗中,注重系統(tǒng)的“實現(xiàn)+驗證”,學(xué)生以小組為單位通過Qt 開發(fā)平臺,自主開發(fā)基于傳統(tǒng)三副本+TCP模式的分布式存儲系統(tǒng)。在單用戶下載文件的場景下,通過模擬存儲節(jié)點宕機后文件能否正?;謴?fù),驗證系統(tǒng)的存儲可靠性。②在綜合型實驗中,注重系統(tǒng)的“可靠+高效”,學(xué)生通過實驗熟悉噴泉碼+UDP 協(xié)議在其典型多用戶下載場景下所擁有的傳輸優(yōu)勢。同時,學(xué)生可以自主實現(xiàn)不同難度的噴泉編譯碼算法,將其作為編譯碼模塊加入系統(tǒng)中,從而有效鍛煉自身編程能力。
基于噴泉碼的分布式云存儲教學(xué)系統(tǒng)由噴泉編譯碼模塊、分布式存儲系統(tǒng)模塊兩部分組成。噴泉碼模塊貫穿于整個系統(tǒng)中,負責(zé)文件的編譯碼實現(xiàn)。本系統(tǒng)采用了兩種噴泉碼,即LT 碼、R10 碼。分布式云存儲系統(tǒng)模塊則主要負責(zé)系統(tǒng)架構(gòu)與實現(xiàn),其由客戶端、云服務(wù)器和云存儲節(jié)點三部分組成,具體模塊設(shè)計如下。
2.1.1 LT碼
LT碼是第1 個實用噴泉碼設(shè)計方案,其編碼過程如圖3 所示,首先將源文件劃分為k個等長輸入符號塊,然后利用度分布函數(shù)隨機均勻選取d(d≤k)個不同的符號塊,將這d個符號塊異或得到一個編碼符號塊。重復(fù)以上步驟n次,即可得到n個輸出編碼符號塊。
圖3 LT編碼過程
LT碼在刪除信道下的譯碼算法主要為置信傳播譯碼算法(Belief Propagation,BP)和及時高斯消元譯碼算法(On the Fly Gaussian Elimination,OFG)[15]兩種。在接收到一定數(shù)量的噴泉編碼符號塊后開始執(zhí)行譯碼算法,如果文件恢復(fù)成功,則譯碼結(jié)束,否則繼續(xù)接收一定量的編碼符號塊,直到譯碼成功為止。BP譯碼的主要過程為首先在每一輪迭代中尋找度值為1 的編碼符號,將該編碼符號的值賦予與其連接的信息符號,再通過異或操作更新對應(yīng)的編碼符號,重復(fù)步驟直到所有文件塊恢復(fù)成功。BP譯碼雖然譯碼簡單,但其譯碼性能比最優(yōu)的極大似然譯碼算法差。OFG 譯碼算法則是一種快速極大似然譯碼算法實現(xiàn),其通過將矩陣三角化操作分散到了譯碼器每一次接收編碼符號的過程中,有效地降低了譯碼復(fù)雜度,將譯碼復(fù)雜度控制在O(k2)。表1 給出了LT 碼的BP 和OFG 譯碼算法在不同譯碼開銷下的文件錯誤率(File Error Rate,F(xiàn)ER),即源文件譯碼失敗概率,源文件大小k為200,度分布采用了參數(shù)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碼的基礎(chǔ)上級聯(lián)了一個線性分組碼作為外碼,先將原始信息進行預(yù)編碼再將外碼的碼字作為LT 碼的輸入。
R10 碼是一種二進制的系統(tǒng)Raptor碼。RFC5053標(biāo)準(zhǔn)詳細規(guī)定了R10 碼的編譯碼算法,如圖4 所示。R10 碼的編碼過程是由k個源符號編碼產(chǎn)生修復(fù)符號的過程,分為兩個階段,第1 個階段由源符號預(yù)編碼產(chǎn)生中間符號;第2 個階段由中間符號進行LT 編碼,產(chǎn)生修復(fù)符號,其譯碼過程采用失活譯碼高斯消元(Inactivation Decoding Gaussian Elimination)算法。
圖4 R10碼編譯過程
2.2.1 主要功能
客戶端是用戶操作及文件恢復(fù)的終端,在系統(tǒng)工作過程中的主要功能包括:①與云服務(wù)器交互控制信息及文件元數(shù)據(jù)信息(如文件名、文件大小和文件存儲位置等);②與云服務(wù)器交互存儲文件;③與云存儲節(jié)點交互副本及噴泉編碼包;④譯碼恢復(fù)源文件。
云服務(wù)器是綜合調(diào)度整個系統(tǒng)的服務(wù)終端,主要功能包括:①與客戶端及云存儲節(jié)點交互控制信號,利用Qt支持的結(jié)構(gòu)化查詢語言數(shù)據(jù)庫功能完成控制信號數(shù)據(jù)的組織和記錄;②與云存儲節(jié)點交互副本及噴泉編碼包。
云存儲節(jié)點用來存儲和傳輸副本及噴泉編碼包,其在系統(tǒng)工作過程中的主要功能包括:①存儲副本及噴泉編碼包;②與云服務(wù)器及客戶端交互副本及噴泉編碼包。
2.2.2 工作過程
系統(tǒng)工作模式分為傳統(tǒng)三副本+TCP模式和噴泉碼+UDP模式兩種,由云服務(wù)器選擇工作模式。傳輸層協(xié)議采用TCP 與UDP 協(xié)議:其中TCP 協(xié)議主要用于傳輸文件的控制流,以及在三副本模式下傳輸數(shù)據(jù)流,保證數(shù)據(jù)的可靠傳輸;UDP 協(xié)議主要用于在噴泉碼模式中傳輸數(shù)據(jù)流,將其與無須反饋的噴泉碼特性結(jié)合,可以實現(xiàn)快速可靠的文件分發(fā),其工作過程如圖5 所示。
圖5 分布式云存儲系統(tǒng)模塊工作流程圖
文件上傳時,客戶端將要存儲的文件上傳到云服務(wù)器,其通過TCP 協(xié)議傳輸存儲控制信息、文件元數(shù)據(jù)信息及文件數(shù)據(jù)信息,其后云服務(wù)器采用TCP協(xié)議將文件數(shù)據(jù)信息傳輸?shù)皆拼鎯?jié)點。在三副本模式中,云服務(wù)器將3 份文件數(shù)據(jù)信息存儲在不同的云存儲節(jié)點上。在噴泉碼模式中,云服務(wù)器將文件數(shù)據(jù)信息進行噴泉編碼,然后將編碼后的不同編碼包存儲在多個云存儲節(jié)點上。
文件下載時,客戶端和云服務(wù)器確定下載方式后,由云存儲節(jié)點向客戶端提供下載服務(wù)。在單用戶下載文件的場景下,三副本模式中n個存儲節(jié)點分別與客戶端建立TCP連接,分別傳輸文件的n分之一數(shù)據(jù)信息,達到并行下載的目的。在多用戶下載相同文件的場景下,噴泉碼模式中的云存儲節(jié)點利用UDP協(xié)議向客戶端廣播噴泉編碼包,客戶端接收到足夠的編碼包即可進行文件的譯碼恢復(fù),如未譯碼成功,客戶端會繼續(xù)接收噴泉編碼包,直到文件恢復(fù),達到可靠多播的目的。
傳統(tǒng)三副本分布式存儲通過跨節(jié)點的副本保護,可有效防止存儲節(jié)點宕機或磁盤損壞對數(shù)據(jù)恢復(fù)的影響。在單用戶下載文件的場景下,基于三副本機制的分布式云存儲系統(tǒng)可以有效保證文件數(shù)據(jù)恢復(fù)的可靠性。實驗在此基礎(chǔ)上設(shè)計而成,由以下三步組成。
(1)系統(tǒng)初步搭建。教師在課堂上給學(xué)生講解該系統(tǒng)的設(shè)計流程、工作原理,搭建流程后。學(xué)生以小組(4 或5 人)的形式,合理分配客戶端、云服務(wù)器、云存儲節(jié)點個數(shù),安裝Qt開發(fā)環(huán)境,自主進行GUI設(shè)計,結(jié)合給定的參考偽代碼,初步搭建三副本分布式云存儲系統(tǒng)。
(2)系統(tǒng)功能開發(fā)。學(xué)生開發(fā)系統(tǒng)的主要功能,并通過文件的上傳和下載進行功能驗證。以5 人小組為例,分配1 個客戶端,1 個云服務(wù)器,3 個云存儲節(jié)點??蛻舳藢⑽募蟼骱?,云服務(wù)器與3 個云存儲節(jié)點建立TCP連接,將文件的副本分別存儲在3 個云存儲節(jié)點。下載時,3 個云存儲節(jié)點與客戶端建立TCP連接,并行傳輸文件的1/3 數(shù)據(jù)信息,在客戶端進行文件恢復(fù),實現(xiàn)并行下載功能。
(3)模擬節(jié)點宕機。以5 人小組為例,學(xué)生在存儲文件后,使其中一個云存儲節(jié)點宕機,模擬存儲數(shù)據(jù)丟失情景。學(xué)生小組開發(fā)功能,使剩余的兩個云存儲節(jié)點通過TCP 連接向客戶端傳輸文件的1/2 數(shù)據(jù)信息,如文件可以正?;謴?fù),則三副本分布式云存儲系統(tǒng)搭建成功。
在驗證型實驗中,通過利用三副本機制的分布式云存儲系統(tǒng)輔助教學(xué),學(xué)生在搭建和使用的過程中可以形象、直觀地學(xué)習(xí)系統(tǒng)工作流程及存儲領(lǐng)域的前沿知識,同時提高學(xué)生的編程能力,極大地調(diào)動了學(xué)生的學(xué)習(xí)積極性。
多用戶下載場景為噴泉碼+UDP 協(xié)議的典型優(yōu)勢應(yīng)用場景。以5 客戶端下載為例,傳統(tǒng)三副本+TCP方式中的3 個云存儲節(jié)點需要分別建立5 個TCP連接,為用戶發(fā)送副本信息,存在傳輸效率低下的問題?;趪娙a的分布式云存儲系統(tǒng)通過利用噴泉碼+UDP廣播的優(yōu)勢,只需要3 個云存儲節(jié)點分別建立1 個UDP連接向5 個客戶端廣播足夠的編碼包,多個用戶即可恢復(fù)源文件。學(xué)生小組配合進行實驗,實現(xiàn)該場景下基于噴泉碼的分布式云存儲系統(tǒng),實驗由以下步驟組成。
(1)噴泉編譯碼算法實現(xiàn)。供學(xué)生選擇實現(xiàn)的編譯碼算法分為兩類:①LT 碼編碼+BP 譯碼/OFG 譯碼;②遵循RFC5053 標(biāo)準(zhǔn)的R10 噴泉編譯碼,學(xué)生小組可根據(jù)能力自主選擇不同難度的兩種編譯碼算法。教師講解兩種編譯碼方案原理,提供設(shè)計文檔,教師在一段時間后提供文件編譯碼算法的偽代碼,學(xué)生小組通過Qt開發(fā)框架用C ++語言實現(xiàn)文件的編譯碼。
(2)系統(tǒng)功能開發(fā)。學(xué)生將多臺客戶端加入系統(tǒng),建立廣播組。同時在實驗1 實現(xiàn)系統(tǒng)的基礎(chǔ)上,開發(fā)云存儲節(jié)點的UDP廣播功能,通過文件能否正常恢復(fù)測試噴泉編譯碼模塊開發(fā)是否成功。文件上傳后,云服務(wù)器通過步驟1 實現(xiàn)的噴泉編譯碼模塊進行編碼,隨后將噴泉編碼包存儲在云存儲節(jié)點。文件下載時,多個客戶端接收云存儲節(jié)點UDP 廣播的編碼包,測試接收足夠多的編碼包后能否譯碼成功,如果譯碼成功,則噴泉碼+UDP 廣播功能開發(fā)成功,完整系統(tǒng)如圖6 所示。
圖6 基于噴泉碼的分布式云存儲系統(tǒng)
通過綜合型實驗,學(xué)生不僅可以通過噴泉編譯碼算法的實現(xiàn)鍛煉編程能力和理解糾刪碼知識,還可以在理解網(wǎng)絡(luò)傳輸協(xié)議的基礎(chǔ)上,鍛煉知識遷移能力和工程實踐能力。
本文設(shè)計的基于噴泉碼的分布式云存儲系統(tǒng)及教學(xué)實驗對標(biāo)我校實踐教學(xué)的人才培養(yǎng)目標(biāo),具有極大的研究意義與價值。通過讓學(xué)生將理論學(xué)習(xí)與實際應(yīng)用相結(jié)合,激發(fā)學(xué)生的學(xué)習(xí)興趣,充分發(fā)揮了學(xué)生的主觀能動性。該系統(tǒng)專業(yè)綜合程度高,知識覆蓋面廣,能夠有效培養(yǎng)電子信息類學(xué)生軟件開發(fā)的思維能力,鍛煉學(xué)生的編程能力,經(jīng)過實踐取到了較好的教學(xué)效果,為理論學(xué)習(xí)與工程案例應(yīng)用相結(jié)合提供了新的思路。在以后的研究中,可以嘗試把噴泉編譯碼算法換成性能更為優(yōu)秀的RaptorQ 碼,譯碼程序中運算量較大的部分可以考慮放在圖形處理器上并行實現(xiàn),從而提高編譯碼的性能,同時考慮將存儲節(jié)點從云端轉(zhuǎn)到邊緣,用以提高數(shù)據(jù)傳輸性能及降低網(wǎng)絡(luò)帶寬。