• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      網(wǎng)絡(luò)編碼系統(tǒng)中基于訪問(wèn)頻度的數(shù)據(jù)重建方法*

      2014-07-25 07:45:02李凱
      關(guān)鍵詞:副本頻度編碼

      李凱

      (暨南大學(xué) 計(jì)算機(jī)科學(xué)系,廣東 廣州510632)

      在這個(gè)大數(shù)據(jù)的年代,數(shù)據(jù)量增長(zhǎng)的速度是驚人的。據(jù)IDC報(bào)告顯示,預(yù)計(jì)到2020年全球數(shù)據(jù)總量將超過(guò) 40 ZB(相當(dāng)于4萬(wàn)億 GB)[1],這一數(shù)據(jù)量是 2011年的22倍。為了給海量數(shù)據(jù)提供有效的存儲(chǔ)及服務(wù)的能力,誕生了許多大規(guī)模數(shù)據(jù)存儲(chǔ)系統(tǒng),比如GFS、Hadoop、OceanStore、Lustre、Gluster等。在這些大型存儲(chǔ)系統(tǒng)中,數(shù)據(jù)分布在一系列的節(jié)點(diǎn)(磁盤(pán)等物理介質(zhì))上,為了保證數(shù)據(jù)的可用性,系統(tǒng)必須能夠容忍節(jié)點(diǎn)失效。為了達(dá)到這一目的,分布式存儲(chǔ)系統(tǒng)引入了冗余數(shù)據(jù)以提供容錯(cuò)能力。

      一般的容錯(cuò)技術(shù)包括副本技術(shù),糾刪碼技術(shù)和網(wǎng)絡(luò)編碼技術(shù)。副本技術(shù)對(duì)一個(gè)數(shù)據(jù)對(duì)象創(chuàng)建多個(gè)副本,并將這些副本分散到不同的節(jié)點(diǎn)上。當(dāng)一個(gè)節(jié)點(diǎn)失效時(shí),可以通過(guò)訪問(wèn)其他節(jié)點(diǎn)的數(shù)據(jù)副本來(lái)重建新節(jié)點(diǎn)。比如GFS[1]為每個(gè)數(shù)據(jù)塊提供了3個(gè)副本。糾刪碼技術(shù)是能夠容忍一個(gè)或多個(gè)節(jié)點(diǎn)同時(shí)失效的編碼技術(shù),而且比副本技術(shù)有更高的空間存儲(chǔ)效率。常見(jiàn)的糾刪碼有Reed-Solomon碼、LDPC碼等。網(wǎng)絡(luò)編碼技術(shù)通過(guò)選擇特殊的編碼系數(shù)來(lái)構(gòu)造生成矩陣,在節(jié)點(diǎn)修復(fù)時(shí),把存儲(chǔ)在同一節(jié)點(diǎn)上的若干數(shù)據(jù)塊做線性運(yùn)算,所以該節(jié)點(diǎn)傳輸一個(gè)數(shù)據(jù)塊就等于提供了做運(yùn)算之前的若干個(gè)數(shù)據(jù)塊的信息,從而有效地節(jié)省了帶寬。

      DIMAKIS等人于2007年首先在分布式存儲(chǔ)系統(tǒng)中引入網(wǎng)絡(luò)編碼思想,提出了一種稱(chēng)為再生碼(regenerating code)[2]的編碼技術(shù)。隨后,Rashmi等人提出了 E-MBR(Exact minimum Bandwidth Regenerating)碼[3],突破了網(wǎng)絡(luò)編碼的理論階段,給出了一個(gè)具體的最優(yōu)帶寬再生碼方案。雖然網(wǎng)絡(luò)編碼在數(shù)據(jù)重建時(shí),下載帶寬方面表現(xiàn)優(yōu)越,但是其付出的運(yùn)算開(kāi)銷(xiāo)卻不可忽視[2]。據(jù)NCFS[4]研究表明,網(wǎng)絡(luò)編碼在退化模式下的表現(xiàn)明顯不如RAID5和RAID6。Tian Lei等人實(shí)現(xiàn)了以訪問(wèn)頻度優(yōu)先的數(shù)據(jù)重構(gòu)優(yōu)化方法[5]來(lái)改善磁盤(pán)陣列中數(shù)據(jù)重建緩慢的問(wèn)題,不過(guò)他們只限于對(duì)RAID5和RAID10的研究?;诖耍疚奶岢隽艘环N在網(wǎng)絡(luò)編碼修復(fù)過(guò)程中利用80/20法則來(lái)加快數(shù)據(jù)重建過(guò)程的方法。在NCFS平臺(tái)上進(jìn)行了仿真實(shí)現(xiàn),并對(duì)RAID5、RAID6和E-MBR編碼在節(jié)點(diǎn)重建時(shí)間、用戶(hù)平均響應(yīng)時(shí)間和吞吐率方面進(jìn)行了比較。

      1 背景知識(shí)

      1.1 帕雷托法則(Pareto principle)

      帕雷托法則又稱(chēng)80-20法則,在計(jì)算機(jī)科學(xué)里,80-20法則代表80%的資源只被20%的操作所使用。具體到文件系統(tǒng)的訪問(wèn)行為,是指80%的請(qǐng)求往往集中在20%的文件上,從而導(dǎo)致某一部分?jǐn)?shù)據(jù)被頻繁重復(fù)地訪問(wèn),而其他數(shù)據(jù)則相對(duì)訪問(wèn)頻度較低。比如視頻網(wǎng)站約20%的視頻文件由于經(jīng)常被觀看而必須保存在內(nèi)存中,以提供快速及時(shí)的響應(yīng);而剩余的80%視頻文件則觀看次數(shù)較少,可把這些數(shù)據(jù)置于存儲(chǔ)后端,需要訪問(wèn)時(shí)再?gòu)暮蠖颂崛 ?/p>

      80-20法則對(duì)數(shù)據(jù)重建具有非常重要的借鑒意義。因?yàn)橐坏┕?jié)點(diǎn)失效,系統(tǒng)就處于退化模式,處于退化模式下的文件系統(tǒng)同時(shí)兼顧重建節(jié)點(diǎn)和響應(yīng)用戶(hù)請(qǐng)求的工作。此時(shí)對(duì)失效節(jié)點(diǎn)的寫(xiě)請(qǐng)求可能被拒絕,讀請(qǐng)求轉(zhuǎn)化為對(duì)若干存活數(shù)據(jù)節(jié)點(diǎn)的讀請(qǐng)求再對(duì)讀出來(lái)的數(shù)據(jù)作編碼運(yùn)算。若20%的熱點(diǎn)數(shù)據(jù)遲遲沒(méi)有重建完成,則會(huì)累積大量退化讀寫(xiě)請(qǐng)求。此時(shí)不但額外增加了讀操作和運(yùn)算,而且磁盤(pán)重建數(shù)據(jù)流和用戶(hù)請(qǐng)求數(shù)據(jù)流對(duì)不同區(qū)域的讀寫(xiě)操作會(huì)導(dǎo)致磁盤(pán)來(lái)回長(zhǎng)尋道,因而嚴(yán)重降低了系統(tǒng)的I/O性能和系統(tǒng)的響應(yīng)能力。若優(yōu)先重建熱點(diǎn)數(shù)據(jù),則能明顯縮短退化模式的持續(xù)時(shí)間,改善系統(tǒng)的I/O效率和系統(tǒng)響應(yīng)能力。

      1.2 E-MBR編碼(Exact Minimum Bandwidth Regenerating Code)

      一般再生碼分為最小帶寬再生碼(MBR)和最小存儲(chǔ)再生碼(MSR)。相比MSR,MBR以略增加節(jié)點(diǎn)的存儲(chǔ)量為代價(jià),換取降低數(shù)據(jù)重建的帶寬開(kāi)銷(xiāo)。通常用一個(gè)元組(n,k.,m,d)來(lái)描述一個(gè)MBR編碼系統(tǒng)。數(shù)據(jù)編碼后分布存儲(chǔ)在n個(gè)節(jié)點(diǎn)上,用戶(hù)連接其中任意k個(gè)節(jié)點(diǎn)可以還原出原始文件。節(jié)點(diǎn)修復(fù)時(shí),新節(jié)點(diǎn)連接d個(gè)節(jié)點(diǎn)來(lái)完成修復(fù)。m=n-d,即當(dāng)失效的節(jié)點(diǎn)多于m個(gè)時(shí),就必須要通過(guò)還原整個(gè)原始文件來(lái)完成節(jié)點(diǎn)修復(fù),這將帶來(lái)相比常規(guī)節(jié)點(diǎn)修復(fù)過(guò)程高得多的帶寬和計(jì)算開(kāi)銷(xiāo)。一般最基本的編碼方式是d=n-1。E-MBR編碼[3]是Rashmi等人提出來(lái)的一種準(zhǔn)確性修復(fù)MBR編碼。

      2 實(shí)驗(yàn)設(shè)計(jì)

      2.1 NCFS系統(tǒng)架構(gòu)

      NCFS是基于FUSE[6],實(shí)現(xiàn)在用戶(hù)空間的網(wǎng)絡(luò)編碼文件系統(tǒng)。通過(guò)把物理節(jié)點(diǎn)掛載到當(dāng)前的文件系統(tǒng)下面(如/mnt/ncfs)即可以像訪問(wèn)邏輯節(jié)點(diǎn)一樣訪問(wèn)節(jié)點(diǎn)中的數(shù)據(jù)。NCFS主要由文件系統(tǒng)層、編碼層、存儲(chǔ)層組成。文件系統(tǒng)層負(fù)責(zé)文件系統(tǒng)的操作,比如文件讀、寫(xiě)、刪除等;編碼層提供了RAID5、RAID6、E-MBR的存儲(chǔ)編碼方式;存儲(chǔ)層提供訪問(wèn)具體物理設(shè)備的接口。在實(shí)驗(yàn)中,用Linux操作系統(tǒng)的偽塊設(shè)備/dev/loop來(lái)模擬物理磁盤(pán)的存儲(chǔ)行為,用戶(hù)的讀、寫(xiě)請(qǐng)求都是針對(duì)/dev/loop1,/dev/loop2等塊設(shè)備的讀寫(xiě)。其系統(tǒng)架構(gòu)如圖1所示。

      圖1 NCFS系統(tǒng)架構(gòu)圖

      2.2 以Zipf-like分布訪問(wèn)塊設(shè)備

      用Zipf-like分布模擬用戶(hù)訪問(wèn)行為,由此產(chǎn)生的訪問(wèn)請(qǐng)求具有80-20特征。把塊設(shè)備節(jié)點(diǎn)平均分成n個(gè)區(qū)域,用數(shù)組access_rec[n]記錄每個(gè)區(qū)域的訪問(wèn)頻度,通過(guò)齊夫定律公式產(chǎn)生訪問(wèn)的塊號(hào)去訪問(wèn)該塊,訪問(wèn)請(qǐng)求完成之后修改該塊號(hào)所在區(qū)域的訪問(wèn)頻度。根據(jù)Zipf-like分布,可知第i塊的訪問(wèn)概率為:

      其中,α為一個(gè)常數(shù),其取值范圍是 0<α≤1;N為塊總數(shù),因此 Ω也是一個(gè)常量。實(shí)驗(yàn)中通過(guò)齊夫定律公式產(chǎn)生的訪問(wèn)行為如表1所示 (總訪問(wèn)次數(shù)為1 000 000次,總區(qū)域數(shù)n=10)。

      各區(qū)域按訪問(wèn)頻度排序如圖2所示。

      表1 訪問(wèn)頻度分布

      圖2 各區(qū)域排序

      2.3 數(shù)據(jù)重建算法

      (1)把記錄訪問(wèn)頻度的數(shù)組 access_rec[n]排序,得出從大到小記錄區(qū)域號(hào)的數(shù)組blk_seq[n];

      (2)從blk_seq[n]中取出一個(gè)區(qū)域號(hào),進(jìn)行該區(qū)域的數(shù)據(jù)重建;

      (3)重復(fù)步驟(2),直到節(jié)點(diǎn)數(shù)據(jù)重建完成。

      3 實(shí)驗(yàn)評(píng)估與分析

      對(duì)新系統(tǒng)和原系統(tǒng)的平均重建時(shí)間、平均響應(yīng)時(shí)間和吞吐率3個(gè)性能指標(biāo)進(jìn)行了實(shí)驗(yàn)數(shù)據(jù)收集,并進(jìn)行了比對(duì)。

      3.1 平均重建時(shí)間

      平均重建時(shí)間代表了系統(tǒng)的重建效率,其計(jì)算公式如下:

      其中總重建時(shí)間的單位為s,節(jié)點(diǎn)數(shù)據(jù)量的單位為MB,平均重建時(shí)間的單位為s/MB。實(shí)驗(yàn)數(shù)據(jù)結(jié)果如圖3所示。

      圖3 平均重建時(shí)間對(duì)比

      3.2 平均響應(yīng)時(shí)間

      平均響應(yīng)時(shí)間是指在重建過(guò)程中,系統(tǒng)每響應(yīng)一個(gè)用戶(hù)請(qǐng)求所用的時(shí)間。其計(jì)算公式如下:

      實(shí)驗(yàn)數(shù)據(jù)結(jié)果如圖4所示。

      圖4 平均響應(yīng)時(shí)間對(duì)比

      3.3 吞吐率

      吞吐率是指節(jié)點(diǎn)修復(fù)過(guò)程中重建數(shù)據(jù)流的每秒處理的數(shù)據(jù)量,其計(jì)算公式為:

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

      實(shí)驗(yàn)分析:實(shí)驗(yàn)數(shù)據(jù)顯示,E-MBR在平均重建時(shí)間、平均響應(yīng)時(shí)間和吞吐率3個(gè)性能指標(biāo)的表現(xiàn)都劣于RAID5和RAID6,這是因?yàn)榫W(wǎng)絡(luò)編碼的優(yōu)勢(shì)主要在于節(jié)省重建帶寬,而為此付出了額外的時(shí)間開(kāi)銷(xiāo),導(dǎo)致重建過(guò)程較緩慢。

      不過(guò)從圖表中可以看出,經(jīng)過(guò)改進(jìn)后的新系統(tǒng)在各性能的表現(xiàn)都比原系統(tǒng)好。其中平均重建時(shí)間從1.33 s/MB降低到0.75 s/MB,有43.6%的改善;平均響應(yīng)時(shí)間從4.98 ms到改進(jìn)后的0.71 ms,整整提高了7倍;吞吐率也有了3.23倍的提升。

      圖5 吞吐率對(duì)比

      系統(tǒng)在退化模式下的性能提升關(guān)鍵在于讓訪問(wèn)頻度最高的數(shù)據(jù)在最短的時(shí)間里重建完成并投入服務(wù),使對(duì)這部分?jǐn)?shù)據(jù)的大量訪問(wèn)請(qǐng)求能夠得到及時(shí)的響應(yīng),從而減輕了CPU的壓力。另外,優(yōu)先重建訪問(wèn)頻度高的數(shù)據(jù)能夠讓重建數(shù)據(jù)流和用戶(hù)請(qǐng)求數(shù)據(jù)流盡可能地重疊,以減少大量的磁頭長(zhǎng)尋道,從而得到更高的I/O效率。

      本文基于網(wǎng)絡(luò)編碼文件系統(tǒng)(NCFS),利用80-20法則對(duì)原系統(tǒng)的數(shù)據(jù)重建過(guò)程進(jìn)行了優(yōu)化,結(jié)果顯示新系統(tǒng)在平均重建時(shí)間、平均響應(yīng)時(shí)間和吞吐率各方面均有比較大的提升。實(shí)驗(yàn)過(guò)程中用到了偽塊設(shè)備來(lái)模擬磁盤(pán)的存儲(chǔ)行為,所有節(jié)點(diǎn)都在同一臺(tái)計(jì)算機(jī)上。這與真實(shí)的分布式網(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 RAIDStructured Storage Systems[C].In FAST′07,San Jose,CA,2007:227-290.

      [6]FUSE[OL].http://fuse.sourceforge.net/,2013.

      猜你喜歡
      副本頻度編碼
      基于SAR-SIFT和快速稀疏編碼的合成孔徑雷達(dá)圖像配準(zhǔn)
      《全元詩(shī)》未編碼疑難字考辨十五則
      子帶編碼在圖像壓縮編碼中的應(yīng)用
      電子制作(2019年22期)2020-01-14 03:16:24
      面向流媒體基于蟻群的副本選擇算法①
      Genome and healthcare
      眨眼頻度可判斷煙癮大小
      婦女之友(2017年3期)2017-04-20 09:20:00
      副本放置中的更新策略及算法*
      銅綠假單胞菌MIC分布敏感百分?jǐn)?shù)與抗菌藥物使用頻度相關(guān)性研究
      樹(shù)形網(wǎng)絡(luò)中的副本更新策略及算法*
      頻度副詞問(wèn)與答
      蕲春县| 天全县| 茌平县| 蓬安县| 安阳县| 天等县| 徐闻县| 潞西市| 襄樊市| 沙坪坝区| 土默特右旗| 开鲁县| 合川市| 大埔区| 洞口县| 桂东县| 当阳市| 平罗县| 大宁县| 乌拉特后旗| 郓城县| 巴林右旗| 红原县| 普格县| 山阳县| 紫云| 伊通| 怀来县| 庆安县| 腾冲县| 虞城县| 城步| 沿河| 玛纳斯县| 阳曲县| 泉州市| 盐城市| 陈巴尔虎旗| 南皮县| 丹凤县| 怀来县|