摘  要： 在分布式存儲系統(tǒng)中，通常需要在節(jié)點失效之后引入新節(jié)點并重建數(shù)據(jù)，以保證系統(tǒng)的可用性。網(wǎng)絡(luò)編碼(Network Coding)存儲技術(shù)通過數(shù)據(jù)在存活節(jié)點內(nèi)部作線性組合，可以大幅度降低數(shù)據(jù)重建時的下載帶寬，因此近網(wǎng)絡(luò)編碼技術(shù)在節(jié)點修復(fù)過程中具有非常重要的地位。但同時其大量的線性組合運算也導(dǎo)致了相當可觀的時間開銷，極大地影響了數(shù)據(jù)重建的效率和用戶的響應(yīng)請求?；诰W(wǎng)絡(luò)編碼文件系統(tǒng)(NCFS)，提出了一種結(jié)合80-20法則的數(shù)據(jù)重建方法，并作出了程序?qū)崿F(xiàn)與仿真驗證。實驗結(jié)果表明,新系統(tǒng)在重建效率、用戶平均響應(yīng)時間及吞吐率方面均有較大提升。
關(guān)鍵詞： 網(wǎng)絡(luò)編碼； NCFS； 數(shù)據(jù)重建； 80-20法則

    在這個大數(shù)據(jù)的年代，數(shù)據(jù)量增長的速度是驚人的。據(jù)IDC報告顯示，預(yù)計到2020年全球數(shù)據(jù)總量將超過40 ZB(相當于4萬億GB)[1],這一數(shù)據(jù)量是2011年的22倍。為了給海量數(shù)據(jù)提供有效的存儲及服務(wù)的能力，誕生了許多大規(guī)模數(shù)據(jù)存儲系統(tǒng)， 比如GFS、Hadoop、OceanStore、Lustre、Gluster等。在這些大型存儲系統(tǒng)中，數(shù)據(jù)分布在一系列的節(jié)點(磁盤等物理介質(zhì))上，為了保證數(shù)據(jù)的可用性，系統(tǒng)必須能夠容忍節(jié)點失效。為了達到這一目的，分布式存儲系統(tǒng)引入了冗余數(shù)據(jù)以提供容錯能力。
    一般的容錯技術(shù)包括副本技術(shù)，糾刪碼技術(shù)和網(wǎng)絡(luò)編碼技術(shù)。副本技術(shù)對一個數(shù)據(jù)對象創(chuàng)建多個副本，并將這些副本分散到不同的節(jié)點上。當一個節(jié)點失效時，可以通過訪問其他節(jié)點的數(shù)據(jù)副本來重建新節(jié)點。比如GFS[1]為每個數(shù)據(jù)塊提供了3個副本。糾刪碼技術(shù)是能夠容忍一個或多個節(jié)點同時失效的編碼技術(shù)，而且比副本技術(shù)有更高的空間存儲效率。常見的糾刪碼有Reed- Solomon碼、LDPC碼等。網(wǎng)絡(luò)編碼技術(shù)通過選擇特殊的編碼系數(shù)來構(gòu)造生成矩陣，在節(jié)點修復(fù)時，把存儲在同一節(jié)點上的若干數(shù)據(jù)塊做線性運算，所以該節(jié)點傳輸一個數(shù)據(jù)塊就等于提供了做運算之前的若干個數(shù)據(jù)塊的信息，從而有效地節(jié)省了帶寬。
    DIMAKIS等人于2007年首先在分布式存儲系統(tǒng)中引入網(wǎng)絡(luò)編碼思想，提出了一種稱為再生碼(regenerating code)[2]的編碼技術(shù)。隨后，Rashmi等人提出了E-MBR(Exact minimum Bandwidth Regenerating)碼[3]，突破了網(wǎng)絡(luò)編碼的理論階段,給出了一個具體的最優(yōu)帶寬再生碼方案。雖然網(wǎng)絡(luò)編碼在數(shù)據(jù)重建時,下載帶寬方面表現(xiàn)優(yōu)越，但是其付出的運算開銷卻不可忽視[2]。據(jù)NCFS[4]研究表明，網(wǎng)絡(luò)編碼在退化模式下的表現(xiàn)明顯不如RAID5和RAID6。Tian Lei等人實現(xiàn)了以訪問頻度優(yōu)先的數(shù)據(jù)重構(gòu)優(yōu)化方法[5]來改善磁盤陣列中數(shù)據(jù)重建緩慢的問題，不過他們只限于對RAID5和RAID10的研究?；诖?，本文提出了一種在網(wǎng)絡(luò)編碼修復(fù)過程中利用80/20法則來加快數(shù)據(jù)重建過程的方法。在NCFS平臺上進行了仿真實現(xiàn)，并對RAID5、RAID6和E-MBR編碼在節(jié)點重建時間、用戶平均響應(yīng)時間和吞吐率方面進行了比較。
1 背景知識
1.1  帕雷托法則(Pareto principle)
    帕雷托法則又稱80-20法則，在計算機科學(xué)里，80-20法則代表80%的資源只被20%的操作所使用。具體到文件系統(tǒng)的訪問行為，是指80%的請求往往集中在20%的文件上，從而導(dǎo)致某一部分數(shù)據(jù)被頻繁重復(fù)地訪問，而其他數(shù)據(jù)則相對訪問頻度較低。比如視頻網(wǎng)站約20%的視頻文件由于經(jīng)常被觀看而必須保存在內(nèi)存中，以提供快速及時的響應(yīng)；而剩余的80%視頻文件則觀看次數(shù)較少，可把這些數(shù)據(jù)置于存儲后端，需要訪問時再從后端提取。
　80-20法則對數(shù)據(jù)重建具有非常重要的借鑒意義。因為一旦節(jié)點失效，系統(tǒng)就處于退化模式，處于退化模式下的文件系統(tǒng)同時兼顧重建節(jié)點和響應(yīng)用戶請求的工作。此時對失效節(jié)點的寫請求可能被拒絕，讀請求轉(zhuǎn)化為對若干存活數(shù)據(jù)節(jié)點的讀請求再對讀出來的數(shù)據(jù)作編碼運算。若20%的熱點數(shù)據(jù)遲遲沒有重建完成，則會累積大量退化讀寫請求。此時不但額外增加了讀操作和運算，而且磁盤重建數(shù)據(jù)流和用戶請求數(shù)據(jù)流對不同區(qū)域的讀寫操作會導(dǎo)致磁盤來回長尋道，因而嚴重降低了系統(tǒng)的I/O性能和系統(tǒng)的響應(yīng)能力。若優(yōu)先重建熱點數(shù)據(jù)，則能明顯縮短退化模式的持續(xù)時間，改善系統(tǒng)的I/O效率和系統(tǒng)響應(yīng)能力。
1.2 E-MBR編碼(Exact Minimum Bandwidth Regenerating Code)
　    一般再生碼分為最小帶寬再生碼(MBR)和最小存儲再生碼(MSR)。相比MSR，MBR以略增加節(jié)點的存儲量為代價，換取降低數(shù)據(jù)重建的帶寬開銷。通常用一個元組(n,k.,m,d)來描述一個MBR編碼系統(tǒng)。數(shù)據(jù)編碼后分布存儲在n個節(jié)點上,用戶連接其中任意k個節(jié)點可以還原出原始文件。節(jié)點修復(fù)時，新節(jié)點連接d個節(jié)點來完成修復(fù)。m=n-d，即當失效的節(jié)點多于m個時，就必須要通過還原整個原始文件來完成節(jié)點修復(fù)，這將帶來相比常規(guī)節(jié)點修復(fù)過程高得多的帶寬和計算開銷。一般最基本的編碼方式是d=n-1。E-MBR編碼[3]是Rashmi等人提出來的一種準確性修復(fù)MBR編碼。
2 實驗設(shè)計
2.1 NCFS系統(tǒng)架構(gòu)
    NCFS是基于FUSE[6]，實現(xiàn)在用戶空間的網(wǎng)絡(luò)編碼文件系統(tǒng)。通過把物理節(jié)點掛載到當前的文件系統(tǒng)下面(如/mnt/ncfs)即可以像訪問邏輯節(jié)點一樣訪問節(jié)點中的數(shù)據(jù)。NCFS主要由文件系統(tǒng)層、編碼層、存儲層組成。文件系統(tǒng)層負責文件系統(tǒng)的操作，比如文件讀、寫、刪除等；編碼層提供了RAID5、RAID6、E-MBR的存儲編碼方式；存儲層提供訪問具體物理設(shè)備的接口。在實驗中，用Linux操作系統(tǒng)的偽塊設(shè)備/dev/loop來模擬物理磁盤的存儲行為，用戶的讀、寫請求都是針對/dev/loop1, /dev/loop2等塊設(shè)備的讀寫。其系統(tǒng)架構(gòu)如圖1所示。

2.3 數(shù)據(jù)重建算法
　　(1)把記錄訪問頻度的數(shù)組access_rec[n]排序，得出從大到小記錄區(qū)域號的數(shù)組blk_seq[n]；
　   (2)從blk_seq[n]中取出一個區(qū)域號，進行該區(qū)域的數(shù)據(jù)重建；

　   (3)重復(fù)步驟(2)，直到節(jié)點數(shù)據(jù)重建完成。
3 實驗評估與分析
　　對新系統(tǒng)和原系統(tǒng)的平均重建時間、平均響應(yīng)時間和吞吐率3個性能指標進行了實驗數(shù)據(jù)收集，并進行了比對。

    實驗數(shù)據(jù)結(jié)果如圖5所示。

    實驗分析：實驗數(shù)據(jù)顯示，E-MBR在平均重建時間、平均響應(yīng)時間和吞吐率3個性能指標的表現(xiàn)都劣于RAID5和RAID6，這是因為網(wǎng)絡(luò)編碼的優(yōu)勢主要在于節(jié)省重建帶寬，而為此付出了額外的時間開銷，導(dǎo)致重建過程較緩慢。
     不過從圖表中可以看出，經(jīng)過改進后的新系統(tǒng)在各性能的表現(xiàn)都比原系統(tǒng)好。其中平均重建時間從1.33 s/MB降低到0.75 s/MB，有43.6%的改善；平均響應(yīng)時間從4.98 ms到改進后的0.71 ms，整整提高了7倍；吞吐率也有了3.23倍的提升。
　　系統(tǒng)在退化模式下的性能提升關(guān)鍵在于讓訪問頻度最高的數(shù)據(jù)在最短的時間里重建完成并投入服務(wù)，使對這部分數(shù)據(jù)的大量訪問請求能夠得到及時的響應(yīng)，從而減輕了CPU的壓力。另外，優(yōu)先重建訪問頻度高的數(shù)據(jù)能夠讓重建數(shù)據(jù)流和用戶請求數(shù)據(jù)流盡可能地重疊，以減少大量的磁頭長尋道，從而得到更高的I/O 效率。
    本文基于網(wǎng)絡(luò)編碼文件系統(tǒng)(NCFS)，利用80-20法則對原系統(tǒng)的數(shù)據(jù)重建過程進行了優(yōu)化，結(jié)果顯示新系統(tǒng)在平均重建時間、平均響應(yīng)時間和吞吐率各方面均有比較大的提升。實驗過程中用到了偽塊設(shè)備來模擬磁盤的存儲行為，所有節(jié)點都在同一臺計算機上。這與真實的分布式網(wǎng)絡(luò)有一定的差別。
參考文獻
[1] GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google  file system[C]. Proc. of the 19th ACM Symp. on operating  Systems Principles. December, 2003:29-43.
[2] DIMAKIS A G,GODFREY P B,WAINWRIGHT M J,et al.  Network coding for distributed storage systems[C]. IEEE  Proc. INFOCOM, May 2007:2000-2008.
[3] RASHMI K V, SHAH N B, KUMAR P V, et al. Explicit construction of optimal exact regenerating codes for distributed storage[C]. In Proc. of Allerton Conference, 2009:1243-1249.
[4] Hu Yuchong, Yu Chiuman, Yan Kit Li, et al. NCFS: on  the practicality and extensibility of a network-coding-based  distributed file system[C]. Proceedings of the 2011 International Symposium on Network Coding(NETCOD), 2011.
[5] Tian Lei,Feng Dan,Jiang Hong, et al. PRO: a popularity based multi-threaded reconstruction optimization for RAID-Structured Storage Systems[C]. In FAST′ 07, San Jose, CA, 2007:227-290.
[6] FUSE[OL]. http://fuse.sourceforge.net/, 2013.