基于糾刪碼的細(xì)粒度云存儲調(diào)度方案

廖 輝，薛廣濤，錢詩友，李明祿

(上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240) (*通信作者電子郵箱gt_xue@sjtu.edu.cn)

基于糾刪碼的細(xì)粒度云存儲調(diào)度方案

廖 輝，薛廣濤*，錢詩友，李明祿

(上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240) (*通信作者電子郵箱gt_xue@sjtu.edu.cn)

針對云存儲系統(tǒng)中數(shù)據(jù)獲取時(shí)延長以及數(shù)據(jù)下載不穩(wěn)定的問題，提出了一種基于存儲節(jié)點(diǎn)負(fù)載信息和糾刪碼技術(shù)的調(diào)度方案。首先，利用糾刪碼對文件進(jìn)行編碼存儲以降低每份數(shù)據(jù)拷貝的大小，同時(shí)利用多個(gè)線程并發(fā)下載以提高數(shù)據(jù)獲取的速度；其次，通過分析大量存儲節(jié)點(diǎn)的負(fù)載信息確定影響時(shí)延的性能指標(biāo)并對現(xiàn)有的云存儲系統(tǒng)架構(gòu)進(jìn)行優(yōu)化，設(shè)計(jì)了一種基于負(fù)載信息的云存儲調(diào)度算法LOAD-ALGORITHM；最后，利用開源項(xiàng)目OpenStack搭建了一個(gè)云計(jì)算平臺，根據(jù)真實(shí)的用戶請求數(shù)據(jù)在云平臺上進(jìn)行部署和測試。實(shí)驗(yàn)結(jié)果表明，相比于現(xiàn)有的工作，調(diào)度算法在數(shù)據(jù)獲取時(shí)延方面最高能減少15%的平均時(shí)延，在數(shù)據(jù)下載穩(wěn)定性方面最高能降低40%的時(shí)延波動(dòng)。該調(diào)度方案在真實(shí)的云平臺環(huán)境下能有效地提高數(shù)據(jù)獲取速度和穩(wěn)定性，降低數(shù)據(jù)獲取時(shí)延，達(dá)到更好的用戶體驗(yàn)。

云存儲系統(tǒng)；糾刪碼；調(diào)度算法；平均時(shí)延；穩(wěn)定性

0 引言

隨著云計(jì)算技術(shù)的發(fā)展，云存儲服務(wù)也受到越來越多行業(yè)的關(guān)注和使用。云存儲[1]是一個(gè)數(shù)據(jù)存儲模型，數(shù)據(jù)被存儲在一個(gè)邏輯存儲池中，實(shí)際的物理存儲則由多臺物理服務(wù)器組成，通常情況下，這些物理環(huán)境由企業(yè)或公司進(jìn)行管理。云存儲系統(tǒng)擁有靈活、易維護(hù)、可擴(kuò)展等特性，并提供數(shù)據(jù)存儲的可靠性保證。用戶可以在任何地點(diǎn)通過網(wǎng)絡(luò)非常方便地訪問云存儲服務(wù)，完成數(shù)據(jù)存儲和獲取等操作。而且，相對于傳統(tǒng)的存儲服務(wù)，它具有成本低、便捷性好的優(yōu)點(diǎn)。毫無疑問，云存儲已經(jīng)成為了當(dāng)前最流行的在線數(shù)據(jù)存儲方案。目前，國外最流行的云存儲服務(wù)包括Dropbox、Google Driver、Microsoft One Driver、Apple iCloud，國內(nèi)的有百度云盤、騰訊微云、華為云盤、360網(wǎng)盤等。

同樣，大數(shù)據(jù)這個(gè)概念近年來也在越來越多的場合被越來越多的人提及，并且經(jīng)常是和云計(jì)算聯(lián)系在一起。大數(shù)據(jù)無疑將給人類社會帶來巨大的價(jià)值，科研機(jī)構(gòu)可以通過大數(shù)據(jù)業(yè)務(wù)協(xié)助進(jìn)行研究探索，如環(huán)境、資源、能源、氣象、航天、生命等領(lǐng)域的探索，那么云計(jì)算和大數(shù)據(jù)之間到底是什么關(guān)系呢？概括而言，沒有互聯(lián)網(wǎng)就沒有云計(jì)算模式，沒有云計(jì)算模式就沒有大數(shù)據(jù)處理技術(shù)。然而，云計(jì)算同樣對大數(shù)據(jù)處理技術(shù)提出了新的挑戰(zhàn)，這主要反映在傳統(tǒng)的關(guān)系數(shù)據(jù)庫不能滿足大數(shù)據(jù)處理的要求，比如海量用戶的高并發(fā)讀寫、海量數(shù)據(jù)的高效存儲和訪問、系統(tǒng)的高可用性和高擴(kuò)展性等。為此，業(yè)界一些廠商先后研發(fā)了一批包含分布式數(shù)據(jù)緩存、分布式文件系統(tǒng)、非關(guān)系型數(shù)據(jù)庫和新關(guān)系型數(shù)據(jù)庫等新技術(shù)來解決上述問題。同樣，由于海量數(shù)據(jù)的大數(shù)據(jù)量和分布性的特點(diǎn)，使得傳統(tǒng)的數(shù)據(jù)處理技術(shù)不適合于處理海量數(shù)據(jù)。這對海量數(shù)據(jù)的分布式并行處理技術(shù)提出了新的挑戰(zhàn)，開始出現(xiàn)以MapReduce為代表的一系列新處理技術(shù)，像數(shù)據(jù)并行處理技術(shù)、增量處理技術(shù)、流式計(jì)算技術(shù)等。云計(jì)算時(shí)代會有更多的數(shù)據(jù)存儲于計(jì)算中心。數(shù)據(jù)是資產(chǎn)，云是數(shù)據(jù)資產(chǎn)保管的場所和訪問的渠道。大數(shù)據(jù)的處理和分析必須依靠云計(jì)算提供計(jì)算環(huán)境和能力，挖掘出適合于特定場景和主題的有效數(shù)據(jù)集。比如，《紐約時(shí)報(bào)》用云計(jì)算轉(zhuǎn)換了1851年到1922年超過40萬張掃描的圖片，通過把任務(wù)分配給幾百臺電腦，這項(xiàng)工作在36 h內(nèi)就完成了；信用卡公司Visa計(jì)算兩年的紀(jì)錄，包括730億筆交易、高達(dá)36 TB的數(shù)據(jù)，處理時(shí)間用傳統(tǒng)方法需要1個(gè)月，而采用基于Hadoop的處理技術(shù)只要13 min[2]。所以說，大數(shù)據(jù)和云計(jì)算其實(shí)是相輔相成的，而大數(shù)據(jù)也將在云計(jì)算技術(shù)等的支撐下被發(fā)掘出更多的價(jià)值。

在云存儲系統(tǒng)中，通常使用兩種方式來提高數(shù)據(jù)容錯(cuò)和防災(zāi)備份能力，以及保證數(shù)據(jù)的可用性。一是通過簡單的冗余備份技術(shù)[3-4]，對原始數(shù)據(jù)進(jìn)行多份拷貝并分別保存在多個(gè)不同的存儲節(jié)點(diǎn)中。二是通過糾刪碼(Erasure Code, EC)技術(shù)[5-7]，將原始數(shù)據(jù)經(jīng)過一定編碼分成若干較小的數(shù)據(jù)塊并保存在多個(gè)不同的存儲節(jié)點(diǎn)中。對于一個(gè)(n,k)糾刪碼(n>k)，原始數(shù)據(jù)先被等分成k個(gè)大小相同的數(shù)據(jù)塊，再將k個(gè)數(shù)據(jù)塊經(jīng)過一定編碼生成n個(gè)數(shù)據(jù)塊，并保存在n個(gè)不同的存儲節(jié)點(diǎn)中，每次只需從n個(gè)數(shù)據(jù)塊中任意獲取k個(gè)數(shù)據(jù)塊并進(jìn)行解碼即可恢復(fù)原始數(shù)據(jù)。對于任意(ni,ki)糾刪碼(i=1,2,…)，只需滿足最大距離可分碼(MaximumDistanceSeparablecode,MDS)[8]，即可使用糾刪碼對文件進(jìn)行編碼存儲。目前，存儲云基本都使用多種不同糾刪碼對文件進(jìn)行編碼存儲，從而來保證數(shù)據(jù)的可靠性。如，F(xiàn)acebook數(shù)據(jù)倉庫集群[9]對頻繁訪問的數(shù)據(jù)簡單地使用3份拷貝進(jìn)行存儲，而對一些較少訪問的數(shù)據(jù)利用(14,10)糾刪碼進(jìn)行保存。一些主流的開源云存儲平臺也開始支持糾刪碼技術(shù)并利用多種不同的糾刪碼進(jìn)行數(shù)據(jù)存儲，如OpenStack的Swift服務(wù)[10]和HDFS-RAID[11]。

相比于簡單的對原始數(shù)據(jù)進(jìn)行冗余備份，利用糾刪碼對數(shù)據(jù)進(jìn)行編碼存儲能夠更高效地利用存儲空間，并能降低數(shù)據(jù)獲取時(shí)延。對云存儲系統(tǒng)而言，一個(gè)重要設(shè)計(jì)準(zhǔn)則就是實(shí)現(xiàn)數(shù)據(jù)的快速獲取。據(jù)Amazon、Microsoft和Google等企業(yè)的相關(guān)報(bào)道，即使輕微的時(shí)延增加也會導(dǎo)致企業(yè)出現(xiàn)實(shí)質(zhì)性的收益降低。由于糾刪碼技術(shù)能比較有效地降低時(shí)延，所以目前被廣泛地運(yùn)用在企業(yè)或一些開源的云平臺中。對于使用(n,k)糾刪碼進(jìn)行存儲的文件，通常利用L個(gè)線程并行下載k個(gè)已編碼的數(shù)據(jù)塊(k≤L≤n)，只要任意k個(gè)數(shù)據(jù)塊下載結(jié)束，通過對該k個(gè)數(shù)據(jù)塊進(jìn)行解碼即可恢復(fù)原始數(shù)據(jù)。相對于下載整個(gè)原始數(shù)據(jù)，由于每個(gè)數(shù)據(jù)塊小于原始數(shù)據(jù)，因此大幅度降低了數(shù)據(jù)獲取時(shí)延。然而，線程調(diào)度策略會對數(shù)據(jù)獲取時(shí)延產(chǎn)生影響，因此，目前最關(guān)鍵的問題是如何優(yōu)化線程調(diào)度以降低數(shù)據(jù)獲取時(shí)延？

本文基于存儲節(jié)點(diǎn)的負(fù)載信息提出了一種新的調(diào)度策略和調(diào)度算法。通過對大量存儲節(jié)點(diǎn)的負(fù)載信息進(jìn)行分析，包括內(nèi)存利用率、磁盤利用率、CPU利用率、硬盤讀寫次數(shù)和收發(fā)的數(shù)據(jù)包等，找出可能影響時(shí)延的性能指標(biāo)，根據(jù)這些指標(biāo)設(shè)計(jì)更細(xì)粒度的調(diào)度策略，并實(shí)現(xiàn)對應(yīng)的調(diào)度算法。本文利用多種不同的糾刪碼對大量文件進(jìn)行編碼存儲，在用戶請求到達(dá)滿足不同分布的情況下進(jìn)行測試，包括真實(shí)的用戶請求數(shù)據(jù)[12]和用戶請求到達(dá)滿足韋伯分布[13]兩種情況。最后，利用開源項(xiàng)目OpenStack[14]搭建了一個(gè)真實(shí)的云計(jì)算平臺進(jìn)行測試，通過大量的實(shí)驗(yàn)結(jié)果證明，本文設(shè)計(jì)的調(diào)度策略和算法不僅能夠有效地降低數(shù)據(jù)獲取時(shí)延，還能保證不同用戶的數(shù)據(jù)下載時(shí)延趨于一致。本文創(chuàng)新點(diǎn)在于根據(jù)存儲節(jié)點(diǎn)的負(fù)載信息實(shí)現(xiàn)反向指導(dǎo)代理節(jié)點(diǎn)進(jìn)行線程調(diào)度，利用最小生成樹中的普里姆算法[15]思想解決調(diào)度過程中出現(xiàn)的問題，并基于真實(shí)云計(jì)算平臺和用戶數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。本文的主要工作包括：

1)對大量存儲節(jié)點(diǎn)的負(fù)載信息進(jìn)行分析，確定影響數(shù)據(jù)獲取時(shí)延的性能指標(biāo)。

2)優(yōu)化云存儲系統(tǒng)現(xiàn)有調(diào)度策略，根據(jù)存儲節(jié)點(diǎn)的負(fù)載信息反向指導(dǎo)代理節(jié)點(diǎn)進(jìn)行線程調(diào)度，并基于負(fù)載信息設(shè)計(jì)一種新的調(diào)度算法。

3)利用OpenStack搭建真實(shí)的云計(jì)算平臺，并通過多種不同的糾刪碼對大量文件進(jìn)行編碼存儲，基于真實(shí)的云存儲平臺和用戶請求到達(dá)數(shù)據(jù)驗(yàn)證調(diào)度算法的有效性和性能。

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

一般而言，云存儲系統(tǒng)包含一個(gè)代理節(jié)點(diǎn)和多個(gè)存儲節(jié)點(diǎn)。用戶通過API或用戶接口與代理節(jié)點(diǎn)進(jìn)行交互，用戶請求可能包含get、put、delete等操作，在本文中只關(guān)注get操作，即文件獲取操作。代理節(jié)點(diǎn)將每個(gè)用戶請求轉(zhuǎn)化成k(k≥1)個(gè)數(shù)據(jù)塊下載任務(wù)，每個(gè)任務(wù)利用一個(gè)線程與存儲節(jié)點(diǎn)建立TCP連接進(jìn)行數(shù)據(jù)下載。當(dāng)k個(gè)任務(wù)都完成后，代理節(jié)點(diǎn)進(jìn)行解碼并恢復(fù)用戶所請求的文件，最后將成功獲取的文件返回用戶。代理節(jié)點(diǎn)一般擁有固定大小的線程池用于維持與存儲節(jié)點(diǎn)的TCP連接，每個(gè)任務(wù)需要消耗一個(gè)線程，當(dāng)線程池中無空閑線程時(shí)，剩余任務(wù)需要等待直到有任務(wù)完成并出現(xiàn)新的空閑線程，代理節(jié)點(diǎn)對等待隊(duì)列中的任務(wù)進(jìn)行調(diào)度后，新的任務(wù)才開始工作。

在本文中，云存儲系統(tǒng)同樣采用了以上所描述的體系架構(gòu)，同時(shí)，在此基礎(chǔ)上新增了一個(gè)性能監(jiān)測節(jié)點(diǎn)用于保存每個(gè)存儲節(jié)點(diǎn)的性能負(fù)載信息，為代理節(jié)點(diǎn)提供調(diào)度依據(jù)，如圖1所示。

圖1 云存儲系統(tǒng)架構(gòu)

2 存儲節(jié)點(diǎn)負(fù)載信息分析

本文中從存儲節(jié)點(diǎn)的負(fù)載信息出發(fā)，分析并確定存儲節(jié)點(diǎn)中可能會對調(diào)度產(chǎn)生影響的性能指標(biāo)。在之前的系統(tǒng)架構(gòu)中提到，這些負(fù)載信息被保存到性能監(jiān)測節(jié)點(diǎn)，文中保存了一些具有代表性的性能指標(biāo)，具體字段如表1所示。本文最初的設(shè)計(jì)將負(fù)載信息保存在代理節(jié)點(diǎn)，為了實(shí)時(shí)跟蹤各個(gè)存儲節(jié)點(diǎn)的負(fù)載變化，本文將數(shù)據(jù)采集的時(shí)間間隔設(shè)置在5s以內(nèi)，但考慮到較高的負(fù)載信息采集頻率對代理節(jié)點(diǎn)調(diào)度產(chǎn)生影響，這里單獨(dú)設(shè)置一個(gè)性能監(jiān)測節(jié)點(diǎn)來保存云存儲系統(tǒng)中各個(gè)存儲節(jié)點(diǎn)的負(fù)載信息。由于云存儲內(nèi)部網(wǎng)絡(luò)屬于高速網(wǎng)絡(luò)，而且代理節(jié)點(diǎn)和存儲節(jié)點(diǎn)處于同一局域網(wǎng)，所以本文有理由相信，當(dāng)進(jìn)行線程調(diào)度時(shí)，代理節(jié)點(diǎn)從性能監(jiān)測節(jié)點(diǎn)獲取負(fù)載信息的通信開銷遠(yuǎn)低于將負(fù)載信息保存在代理節(jié)點(diǎn)中頻繁通信帶來的開銷，從而減少其他因素對代理節(jié)點(diǎn)調(diào)度產(chǎn)生的干擾，降低對文件獲取時(shí)延產(chǎn)生的影響。

表1 負(fù)載信息采集表

通過對多個(gè)存儲節(jié)點(diǎn)的大量負(fù)載信息進(jìn)行分析，本文發(fā)現(xiàn)有些性能指標(biāo)對文件獲取時(shí)延可能存在一定影響。從圖2(a)可以看出，無論時(shí)延曲線如何波動(dòng)，CPU利用率、內(nèi)存利用率、磁盤利用率等曲線基本保持平穩(wěn)狀態(tài)，對于throughput_recv、disk_percent、disk_write等指標(biāo)也得出相似的結(jié)果，曲線之間基本沒有關(guān)聯(lián)性，所以本文初步確定文件獲取的平均時(shí)延基本不受這幾個(gè)指標(biāo)的影響。為了進(jìn)一步驗(yàn)證該設(shè)想，本文在存儲節(jié)點(diǎn)中單獨(dú)部署了兩個(gè)應(yīng)用，分別用于提高存儲節(jié)點(diǎn)的CPU利用率和內(nèi)存利用率，發(fā)現(xiàn)隨著內(nèi)存利用率或CPU利用率的提高，文件平均下載時(shí)延并不隨之變化，而是保持平穩(wěn)狀態(tài)，所以本文有理由認(rèn)為以上幾個(gè)性能指標(biāo)基本不會對文件獲取時(shí)延產(chǎn)生影響。

從圖2(b)可以發(fā)現(xiàn)，throughput_send曲線與時(shí)延曲線可能存在一定程度上的關(guān)聯(lián)性，初步確定文件獲取時(shí)延可能受到每個(gè)存儲節(jié)點(diǎn)吞吐量的影響。因?yàn)椋瑪?shù)據(jù)傳輸時(shí)延=發(fā)送時(shí)延+傳播時(shí)延+等待時(shí)延，當(dāng)吞吐量增高時(shí)，一方面意味著更多數(shù)據(jù)需要傳輸，從而造成數(shù)據(jù)在等待隊(duì)列中的排隊(duì)時(shí)間更長，導(dǎo)致等待時(shí)延的增加；另一方面高吞吐量會造成丟包率的升高，從而導(dǎo)致更多的數(shù)據(jù)包需要進(jìn)行超時(shí)重傳。所以本文認(rèn)為存儲節(jié)點(diǎn)的吞吐量是影響文件獲取時(shí)延的一個(gè)重要因素，在之后的章節(jié)中也會通過大量的實(shí)驗(yàn)結(jié)果來驗(yàn)證。

圖2 存儲節(jié)點(diǎn)性能指標(biāo)分析

由于文件下載需要從存儲節(jié)點(diǎn)的磁盤讀取數(shù)據(jù)塊并發(fā)送給代理節(jié)點(diǎn)，假設(shè)每次磁盤讀操作讀取的數(shù)據(jù)大小相同，為d字節(jié)，那么在理想情況下，只要發(fā)送速度足夠快，throughput_send=disk_read*d，可以看出每秒發(fā)送的字節(jié)數(shù)和每秒讀取次數(shù)存在線性關(guān)系，所以本文使用吞吐量作為調(diào)度依據(jù)而不使用每秒磁盤讀操作。

當(dāng)存儲節(jié)點(diǎn)吞吐量升高，說明代理節(jié)點(diǎn)中有更多的線程用于與該存儲節(jié)點(diǎn)建立連接并進(jìn)行數(shù)據(jù)傳輸，當(dāng)多個(gè)文件下載請求同時(shí)到達(dá)時(shí)，代理節(jié)點(diǎn)可能將過多任務(wù)的調(diào)度到某個(gè)存儲節(jié)點(diǎn)，從而導(dǎo)致該節(jié)點(diǎn)負(fù)載過高。文中之前提到過高負(fù)載可能造成高時(shí)延，以及不同用戶獲取數(shù)據(jù)時(shí)延的不穩(wěn)定，為了避免這種情況產(chǎn)生的負(fù)面影響，在本文之后的內(nèi)容中，通過優(yōu)化現(xiàn)有調(diào)度策略，即基于存儲節(jié)點(diǎn)吞吐量的負(fù)載情況進(jìn)行調(diào)度，設(shè)計(jì)了一種新的調(diào)度算法

3 云存儲調(diào)度算法

根據(jù)以上分析，本文使用單位時(shí)間內(nèi)發(fā)送的數(shù)據(jù)(為了書寫方便，本文之后都使用表1中throughput_send表示)作為調(diào)度依據(jù)，并以此設(shè)計(jì)調(diào)度算法。算法優(yōu)化的目標(biāo)是盡量使各存儲節(jié)點(diǎn)的throughput_send負(fù)載程度相同，從而避免單個(gè)存儲節(jié)點(diǎn)負(fù)載過高影響文件獲取速度。本文針對兩種用戶請求的情況進(jìn)行分析，第一種是每次單個(gè)請求到達(dá)的情況，第二種是每次有多個(gè)請求到達(dá)的情況。

問題1描述 有1個(gè)用戶請求到達(dá)，獲取文件j(j=1, 2,…)，這里用filej表示，該文件采用(nj,kj) 糾刪碼。假設(shè)經(jīng)過編碼后的數(shù)據(jù)塊映射到nj個(gè)存儲節(jié)點(diǎn)中，storage[1, 2, …,nj]表示每個(gè)存儲節(jié)點(diǎn)的信息，chunk[j]表示filej對應(yīng)的數(shù)據(jù)塊信息。需要解決的問題是：如何從nj個(gè)存儲節(jié)點(diǎn)中選出kj個(gè)進(jìn)行數(shù)據(jù)塊下載，使storage[1, 2, …,nj]每個(gè)存儲節(jié)點(diǎn)的負(fù)載程度基本相同？

思路 當(dāng)每次有用戶請求到達(dá)時(shí)，選擇負(fù)載最小的一些存儲節(jié)點(diǎn)進(jìn)行下載。假設(shè)用戶請求文件filej，該文件使用(nj,kj) 糾刪碼，且已編碼的數(shù)據(jù)塊保存在nj個(gè)存儲節(jié)點(diǎn)，那么只需利用簡單的貪心算法，將各存儲節(jié)點(diǎn)按throughput_send從小到大進(jìn)行排序，并從對應(yīng)的nj存儲節(jié)點(diǎn)選擇較小的前kj個(gè)節(jié)點(diǎn)，建立TCP連接進(jìn)行數(shù)據(jù)塊下載任務(wù)，具體如算法1所示。

算法1 單用戶請求調(diào)度算法。

輸入：用戶文件請求filej。

輸出：數(shù)據(jù)塊下載任務(wù)隊(duì)列chunk_task[1-kj]。

1)

storage[1 tonj].throughput_send← 從負(fù)性能監(jiān)測節(jié)點(diǎn)中獲取當(dāng)前每個(gè)存儲節(jié)點(diǎn)的吞吐量并初始化storage數(shù)組

2)

storage[1 tonj].ip← 當(dāng)前存儲節(jié)點(diǎn)的ip

3)

根據(jù)filej使用的(nj,kj)糾刪碼，將文件請求映射到數(shù)據(jù)塊的下載，并初始化chunk數(shù)組

4)

chunk[j].n←nj，文件j包含的數(shù)據(jù)塊個(gè)數(shù)

5)

chunk[j].k←kj，恢復(fù)文件j需要的數(shù)據(jù)塊個(gè)數(shù)

6)

fori← 1 tonj

7)

chunk[j].ips[i] ← 保存所有數(shù)據(jù)塊的存儲節(jié)點(diǎn)，利用storage[i]進(jìn)行初始化

8)

endfor

9)

對chunk[j].ip[1 tonj])按throughput_send信息從小到大進(jìn)行排列

10)

fori← 1 toki

11)

chunk_task.push(chunk[j].ips[i])

12)

endfor

對于算法1，1)～2)行初始化數(shù)組storage，保存每個(gè)存儲節(jié)點(diǎn)當(dāng)前吞吐量以及IP地址。3)行根據(jù)請求文件使用的(nj,kj)糾刪碼，將文件請求任務(wù)映射到對應(yīng)的已編碼數(shù)據(jù)塊下載任務(wù)。4)～8)行，保存數(shù)據(jù)塊信息，包括nj、kj以及數(shù)據(jù)塊所在存儲節(jié)點(diǎn)的信息。9)行根據(jù)throughput_send對storage從小到大進(jìn)行排序。10)～12)行選取throughput_send最小的前kj個(gè)存儲節(jié)點(diǎn)進(jìn)行任務(wù)調(diào)度，并返回這些存儲節(jié)點(diǎn)信息。因?yàn)槊看味歼x擇吞吐量最低的幾個(gè)節(jié)點(diǎn)進(jìn)行調(diào)度，所以負(fù)載較為平均地分?jǐn)偟礁鱾€(gè)存儲節(jié)點(diǎn)，不會造成某些節(jié)點(diǎn)負(fù)載過高。可以得出結(jié)論，當(dāng)每次只有一個(gè)請求時(shí)，使用貪心策略，該算法接近最優(yōu)。

實(shí)際上，在云存儲系統(tǒng)中，每秒往往有多個(gè)用戶請求到達(dá)。當(dāng)同時(shí)有多個(gè)請求到達(dá)時(shí)，由于算法1總是選擇負(fù)載最低的幾個(gè)存儲節(jié)點(diǎn)進(jìn)行調(diào)度，可能導(dǎo)致與代理節(jié)點(diǎn)建立的數(shù)據(jù)連接都集中在一部分存儲節(jié)點(diǎn)，從而造成這些節(jié)點(diǎn)吞吐量負(fù)載增高，影響文件獲取速度。考慮同時(shí)有多個(gè)請求到達(dá)的情況，如果對請求一個(gè)一個(gè)進(jìn)行調(diào)度，前一個(gè)請求的調(diào)度結(jié)果會改變某些存儲節(jié)點(diǎn)的吞吐量，從而對下一個(gè)請求的調(diào)度產(chǎn)生影響，所以在這種情況下算法1不能達(dá)到最優(yōu)，它未考慮到請求之間的關(guān)聯(lián)性。現(xiàn)在的問題是，當(dāng)有多個(gè)請求同時(shí)到達(dá)時(shí)，如何進(jìn)行調(diào)度才能使每個(gè)存儲節(jié)點(diǎn)的負(fù)載基本相同？

思路 傳輸一個(gè)數(shù)據(jù)塊chunk[i]，需要發(fā)送chunk[i].size字節(jié)的數(shù)據(jù)，即造成throughput_send提高chunk[i].size。本文假設(shè)需要下載所有文件的所有數(shù)據(jù)塊n1,n2,…,np，則需要發(fā)送chunk[1].size+chunk[2].size+,…,+chunk[p].size字節(jié)的數(shù)據(jù)。本文將下載這些數(shù)據(jù)塊導(dǎo)致負(fù)載提高的信息更新到現(xiàn)有的存儲節(jié)點(diǎn)storage[1,2,…,p]中。文中使用類似于最小生成樹中的普里姆算法思想，對所有存儲節(jié)點(diǎn)按throughput_send信息進(jìn)行排序，然后每次從throughput_send最高的存儲節(jié)點(diǎn)中刪除一個(gè)數(shù)據(jù)塊，由于小數(shù)據(jù)塊對于吞吐量影響不大，在這里每次刪除最大的數(shù)據(jù)塊并更新當(dāng)前節(jié)點(diǎn)的throughput_send，重復(fù)操作，直到所有文件的數(shù)據(jù)塊數(shù)目分別等于k1,k2,…,kp，具體如算法2所示。

算法2 多用戶請求調(diào)度算法：LOAD-ALGORITHM。

輸入：用戶文件請求隊(duì)列file_list[1,2,…,p]。

1)

storage[1 toq].disk_read← 利用性能監(jiān)測節(jié)點(diǎn)中記錄的負(fù)載信息，初始化storage數(shù)組

2)

storage[1 toq].ip← 當(dāng)前存儲節(jié)點(diǎn)的ip

3)

fori← 1 top:

4)

根據(jù)file_list[i]使用的(ni,ki)糾刪碼，將文件請求映射到數(shù)據(jù)塊下載任務(wù)，初始化chunk數(shù)組

5)

chunk[i].size← 文件塊的大小

6)

chunk[i].k←ki,恢復(fù)文件i需要的數(shù)據(jù)塊個(gè)數(shù)

7)

chunk[i].n←ni,文件i包含的所有數(shù)據(jù)塊個(gè)數(shù)

8)

chunk[i].ips[1 toni] ← 保存文件i對應(yīng)的所有數(shù)據(jù)塊的所在存儲節(jié)點(diǎn)信息，這里用storage[i]進(jìn)行初始化

9)

endfor

10)

fori← 1 toni

11)

更新storage[1-q]信息。假設(shè)需要下載文件的所有數(shù)據(jù)塊，利用chunk[i]信息更新所在存儲節(jié)點(diǎn)的throughput_send

12)

endfor

13)

while !(chunk[i].k==chunk[i].n)(i=1,2,…,p)

14)

對storage[1,2,…,q]按throughput_send從大到小排序

15)

從throughput_send最大的存儲節(jié)點(diǎn)，即storage[1]，找出最大的數(shù)據(jù)塊chunk[j]，并從存儲節(jié)點(diǎn)中刪除該數(shù)據(jù)塊并更新storage[1],storage[1].throughput_send←storage[1].throughput_send-chunk[j].size

16)

將該存儲節(jié)點(diǎn)從chunk[i].ips中刪除

17)

chunk[i].n←chunk[i].n-1

18)

end while

19)

fori← 1 top

20)

chunk_task.push(chunk.ips[1-ki])

21)

endfor

算法2中1)～2)行利用性能監(jiān)測節(jié)點(diǎn)中保存的存儲節(jié)點(diǎn)負(fù)載信息初始化storage數(shù)組。3)～9)行將文件i請求根據(jù)使用的(ni,ki)糾刪碼映射到對數(shù)據(jù)塊的下載任務(wù)，利用ni、ki以及數(shù)據(jù)塊所在的存儲節(jié)點(diǎn)信息初始化chunk數(shù)組。10)～12)行，假設(shè)需要下載所有數(shù)據(jù)塊(n1+n2+…+np)，則將下載這些數(shù)據(jù)塊影響的吞吐量負(fù)載信息更新到storage數(shù)組。13)～18)行，每次從storage數(shù)組中選出throughput_send最大的節(jié)點(diǎn)并從中刪除最大的數(shù)據(jù)塊，直到所有文件剩余的數(shù)據(jù)塊數(shù)目分別等于k1,k2,…,kp。19)～21)利用剩余的數(shù)據(jù)塊以及對應(yīng)的存儲節(jié)點(diǎn)信息初始化任務(wù)隊(duì)列chunk_task，進(jìn)行數(shù)據(jù)塊下載任務(wù)。該算法借鑒了普里姆算法的思路，使負(fù)載信息較為平均地分?jǐn)偟礁鱾€(gè)存儲節(jié)點(diǎn)，可以看出，當(dāng)同時(shí)有多個(gè)請求到達(dá)時(shí)，該算法接近最優(yōu)。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)基于真實(shí)的云計(jì)算平臺和用戶請求數(shù)據(jù)，進(jìn)行大量的測試來驗(yàn)證文中所提出的調(diào)度算法，從實(shí)踐的角度證明算法的可行性和有效性，并將實(shí)驗(yàn)結(jié)果與相關(guān)文獻(xiàn)的工作進(jìn)行對比。

4.1 實(shí)驗(yàn)環(huán)境

首先，本文利用開源項(xiàng)目OpenStack搭建了一個(gè)多節(jié)點(diǎn)的云計(jì)算平臺，每個(gè)節(jié)點(diǎn)配置一個(gè)千兆網(wǎng)卡，代理節(jié)點(diǎn)和所有存儲節(jié)點(diǎn)都處于同一個(gè)局域網(wǎng)。為了進(jìn)行測試，在云平臺中申請了12臺虛擬機(jī)用于模擬文件的下載，10臺用于普通的存儲節(jié)點(diǎn)，1臺用于性能監(jiān)測節(jié)點(diǎn)，1臺用于代理節(jié)點(diǎn)。在存儲節(jié)點(diǎn)中本文保存了大量的文件數(shù)據(jù)，每個(gè)文件都通過糾刪碼進(jìn)行編碼。

其次，根據(jù)文獻(xiàn)[16]的相關(guān)研究，在一個(gè)云存儲系統(tǒng)中，大部分文件都相對比較小，而這些小文件通常只占用很小一部分存儲空間。根據(jù)統(tǒng)計(jì)結(jié)果，大概90%的文件小于4MB，99%的文件小于16MB，而小于4MB的文件大概占用10%的存儲空間，小于16MB的文件大概占用20%的存儲空間。本文按照文獻(xiàn)[16]中給出的結(jié)論對存儲節(jié)點(diǎn)進(jìn)行部署，在系統(tǒng)中保存大量的數(shù)據(jù)文件。

本文采取了多種不同的糾刪碼進(jìn)行對文件進(jìn)行編碼。這里利用四種不同糾刪碼對文件進(jìn)行編碼，分別為：1)(2,1)糾刪碼;2)(4,2)糾刪碼;3)(6,3)糾刪碼;4)(10,4)糾刪碼。

對于性能監(jiān)測節(jié)點(diǎn)，它會定時(shí)采集各個(gè)存儲節(jié)點(diǎn)的負(fù)載信息。本文將監(jiān)測節(jié)點(diǎn)與存儲節(jié)點(diǎn)的之間的交互頻率定義為一秒一次，因?yàn)樨?fù)載信息的數(shù)據(jù)量非常小，可以認(rèn)為，這些數(shù)據(jù)的傳輸基本不會對存儲節(jié)點(diǎn)的性能產(chǎn)生影響，也就是說對實(shí)驗(yàn)結(jié)果不會產(chǎn)生干擾。

代理節(jié)點(diǎn)用于部署調(diào)度算法，同時(shí)擁有L=20大小的線程池。在用戶請求分別符合兩種到達(dá)的情況下，測試調(diào)度算法的性能。第一種情況是用戶請求到達(dá)滿足韋伯分布[13]，第二種情況用戶請求基于真實(shí)的用戶請求到達(dá)數(shù)據(jù)[12]。

最后，在相同的實(shí)驗(yàn)情況下，將本文的算法LOAD-ALGORITHM與SERPT-R算法[17]和FCFS-R算法[18](算法細(xì)節(jié)如第5章所述)進(jìn)行對比，得出相關(guān)的結(jié)論。

4.2 算法性能

圖3為用戶請求到達(dá)滿足韋伯分布得出的結(jié)果。橫坐標(biāo)表示用戶請求的總次數(shù)，本文測試了10，20，50，100，200，500幾組數(shù)據(jù)，縱坐標(biāo)表示完成所有請求所需的時(shí)延。文中使用4種不同的糾刪碼對文件進(jìn)行編碼，如圖3所示。從圖3可以看出，相比之前的工作，在請求量比較少的情況，存儲節(jié)點(diǎn)負(fù)載相對比較低，所以平均時(shí)延大致相同。而當(dāng)請求比較多時(shí)，可能會出現(xiàn)單個(gè)節(jié)點(diǎn)負(fù)載較高從而影響文件獲取的情況，本文設(shè)計(jì)的算法可以很好地避免這一點(diǎn)；即使文件使用不同編碼，在一定程度上都能降低文件獲取的總時(shí)延。從圖3可以看出，本文提出的LOAD-ALGORITHM算法比SERPT-R算法降低10%～15%數(shù)據(jù)獲取的平均時(shí)延，相比FCFS-R算法降低20%～30%的平均時(shí)延。

圖4為用戶請求到達(dá)滿足真實(shí)用戶請求數(shù)據(jù)下得出的結(jié)果。橫坐標(biāo)表示用戶請求的總次數(shù)，縱坐標(biāo)表示所有請求完成所需的時(shí)延。同樣，這里使用了與圖3相同的幾組數(shù)據(jù)進(jìn)行測試以及相同的四種糾刪碼對文件進(jìn)行編碼。可以看出，本文提出的LOAD-ALGORITHM算法比SERPT-R算法完成所有請求所需的時(shí)間更短，降低10%～15%數(shù)據(jù)獲取的平均時(shí)延，相比FCFS-R算法降低20%～30%的平均時(shí)延。

圖3 用戶請求到達(dá)服從韋伯分布時(shí)平均時(shí)延

圖4 用戶請求到達(dá)服從真實(shí)的用戶請求時(shí)平均時(shí)延

在云存儲系統(tǒng)中，數(shù)據(jù)獲取時(shí)延的穩(wěn)定性也是決定用戶體驗(yàn)的重要因素。為了進(jìn)一步驗(yàn)證算法的性能，本文分析了算法對時(shí)延波動(dòng)的影響。文中利用方差來體現(xiàn)數(shù)據(jù)獲取時(shí)延的離散程度，D(X) =E{[X-E(X)]2}。根據(jù)概率論相關(guān)知識，方差越大，表示數(shù)據(jù)離散程度越高，穩(wěn)定性越差。穩(wěn)定性驗(yàn)證的實(shí)驗(yàn)中同樣使用了糾刪碼 (4, 2)、(6, 3)、(10,4)對文件進(jìn)行存儲，并在用戶請求服從韋伯分布和真實(shí)用戶請求數(shù)據(jù)情況下，與SEPRT-R算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖5所示，橫坐標(biāo)表示不同的糾刪碼，縱坐標(biāo)表示時(shí)延方差。從圖5中可以明顯看出，本文提出的算法在兩種用戶請求到達(dá)情況下對數(shù)據(jù)獲取時(shí)延的方差都有著比較明顯的改善，相比于SEPRT-R算法，降低30%～40%的時(shí)延方差。也就是說，在長時(shí)間內(nèi)，數(shù)據(jù)獲取時(shí)延更加穩(wěn)定，不會出現(xiàn)劇烈波動(dòng)即時(shí)延過高或過低的情況，從而影響用戶體驗(yàn)。根據(jù)實(shí)驗(yàn)結(jié)果可得出結(jié)論，本文提出的調(diào)度算法對數(shù)據(jù)獲取時(shí)延的穩(wěn)定性也有著明顯的改善。

圖5 調(diào)度算法對穩(wěn)定性的影響

5 國內(nèi)外相關(guān)研究

目前，國內(nèi)外已經(jīng)有很多關(guān)于云存儲方向的相關(guān)研究。文獻(xiàn)[3,19]主要介紹分布式存儲系統(tǒng)中的存儲方案，對原始文件數(shù)據(jù)進(jìn)行簡單的冗余備份，將一份文件的多個(gè)拷貝保存在不同的存儲節(jié)點(diǎn)中。文獻(xiàn)[5]介紹了云存儲系統(tǒng)中的存儲方案，使用糾刪碼技術(shù)對原始文件進(jìn)行編碼，將文件編碼成等長的幾個(gè)數(shù)據(jù)塊進(jìn)行存儲，由于編碼后的數(shù)據(jù)塊小于原始文件，所以相對于對原始文件進(jìn)行冗余備份，糾刪碼技術(shù)在文件獲取過程中能夠比較好地降低時(shí)延。文獻(xiàn)[9-10,20]介紹了當(dāng)前一些主流的企業(yè)和云存儲平臺，包括如Facebook、Microsoft、OpenStack中的Swift存儲服務(wù)，它們都使用了基于糾刪碼進(jìn)行文件存儲的方案。文獻(xiàn)[17]介紹了代理節(jié)點(diǎn)中的調(diào)度問題，對于使用(n,k)糾刪碼，只使用k個(gè)線程對文件對應(yīng)的k個(gè)數(shù)據(jù)塊進(jìn)行下載，而不使用n個(gè)冗余線程下載所有數(shù)據(jù)塊，同時(shí)利用剩余的線程進(jìn)行其他文件下載任務(wù)，每個(gè)文件占用與其編碼k相同大小的線程數(shù)，直至所有的可用線程都使用完，文章從理論上證明調(diào)度方案的優(yōu)越性。文獻(xiàn)[18]介紹了云存儲系統(tǒng)中代理節(jié)的任務(wù)調(diào)度問題，利用先到先服務(wù)(FirstComeFirstServed,FCFS)策略，對于每個(gè)到達(dá)的請求，利用冗余線程來進(jìn)行文件下載任務(wù)。文獻(xiàn)[21]介紹了代理節(jié)點(diǎn)中新的排隊(duì)模型，并論證了系統(tǒng)只包含單個(gè)存儲節(jié)點(diǎn)和下載時(shí)間滿足指數(shù)分布的前提下，利用冗余線程進(jìn)行任務(wù)下載能夠很好地降低時(shí)延。文獻(xiàn)[22]提出了一種動(dòng)態(tài)調(diào)整糾刪碼的方案，通過監(jiān)控等待隊(duì)列和線程使用情況來判斷當(dāng)前系統(tǒng)負(fù)載，在低負(fù)載情況下編碼成較小數(shù)據(jù)塊對進(jìn)行文件保存，高負(fù)載情況下編碼成較大數(shù)據(jù)塊對進(jìn)行文件保存。文獻(xiàn)[23]對比和分析了現(xiàn)有的糾刪碼技術(shù)，給出了不同糾刪碼在容錯(cuò)能力與磁盤要求、空間利用率、編碼效率、更新效率、重構(gòu)效率等方面的不足和可能的改進(jìn)見解。文獻(xiàn)[24]針對云存儲系統(tǒng)的擴(kuò)展性和數(shù)據(jù)容錯(cuò)問題，給出了一種可容3列隨機(jī)刪除錯(cuò)數(shù)據(jù)的布局方法；利用校驗(yàn)數(shù)據(jù)位與信息數(shù)據(jù)位之間的對應(yīng)關(guān)系找到一種具有低計(jì)算復(fù)雜度的數(shù)據(jù)重構(gòu)算法。文獻(xiàn)[25]針對Hadoop分布式文件系統(tǒng)(HadoopDistributedFileSystem,HDFS)的多副本存儲技術(shù)提出了改進(jìn)，引入編碼和編譯模塊，對系統(tǒng)中的block進(jìn)行編碼分解，生成更多數(shù)量的數(shù)據(jù)分片，并隨機(jī)分散保存到集群當(dāng)中，替代原有系統(tǒng)的多副本容災(zāi)策略，在容災(zāi)效率、負(fù)載均衡、存儲成本以及安全性上對HDFS作了相應(yīng)的優(yōu)化。文獻(xiàn)[26]針對單服務(wù)器的糾刪碼算法在用戶量大的訪問情況下容易導(dǎo)致效率低下的問題，提出了一種基于分散式服務(wù)器的算法，并通過對原數(shù)據(jù)進(jìn)行分割編碼來實(shí)現(xiàn)數(shù)據(jù)塊的冗余存儲。文獻(xiàn)[27]研究了糾刪碼技術(shù)在云文件系統(tǒng)中的應(yīng)用，并從編碼類型、編碼對象、編碼時(shí)機(jī)、數(shù)據(jù)更改、數(shù)據(jù)訪問方式和數(shù)據(jù)訪問性能等6個(gè)方面對云文件系統(tǒng)中糾刪碼的設(shè)計(jì)進(jìn)行了探究，證明了糾刪碼能有效地保障云文件系統(tǒng)的數(shù)據(jù)可用性，并且節(jié)省存儲空間。基于以上的研究，本文利用糾刪碼進(jìn)行文件保存，并根據(jù)存儲節(jié)點(diǎn)的負(fù)載信息，從更細(xì)粒度層面進(jìn)行任務(wù)調(diào)度，優(yōu)化現(xiàn)有的調(diào)度方案。

6 結(jié)語

在云存儲系統(tǒng)中，本文基于糾刪碼技術(shù)，根據(jù)存儲節(jié)點(diǎn)的負(fù)載信息反向指導(dǎo)代理節(jié)點(diǎn)，從更細(xì)粒度層面進(jìn)行數(shù)據(jù)下載任務(wù)的調(diào)度。本文通過分析大量存儲節(jié)點(diǎn)的負(fù)載信息，找出影響文件獲取速度的性能指標(biāo)，并基于該指標(biāo)設(shè)計(jì)了新的調(diào)度算法。為了驗(yàn)證算法的性能，利用開源項(xiàng)目OpenStack搭建了一個(gè)真實(shí)的云計(jì)算實(shí)驗(yàn)平臺，通過多種糾刪碼方案對大量文件進(jìn)行編碼存儲，在真實(shí)的云存儲環(huán)境下模擬不同用戶請求到達(dá)的情況，進(jìn)行大量的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，在云存儲系統(tǒng)中，本文提出的調(diào)度算法不僅能夠有效地降低數(shù)據(jù)獲取時(shí)延，還能保證不同用戶的數(shù)據(jù)下載時(shí)延趨于一致，提高數(shù)據(jù)獲取的穩(wěn)定性，從而提供更好的用戶體驗(yàn)，在一定程度上優(yōu)化現(xiàn)有的調(diào)度策略。

)

[1]Wikipedia.Cloudstorage[EB/OL]. [2016- 06- 10].https://en.wikipedia.org/wiki/Cloudstorage.

[2] 華為.大數(shù)據(jù)和云計(jì)算[EB/OL]. [2016- 07- 19].http://e.huawei.com/zh/publications/cn/ict_insights/hw_366755/horizons/HW_366714. (Huawei.Bigdataandcloudcomputing[EB/OL]. [2016- 07- 19].http://e.huawei.com/zh/publications/cn/ict_insights/hw_366755/horizons/HW_366714.)

[3]GHEMAWATS,GOBIOFFH,LEUNGST.Thegooglefilesystem[C]//Proceedingsofthe19thACMSymposiumonOperatingSystemsPrinciples.NewYork:ACM, 2003: 29-43.

[4]SHVACHKOK,KUANGH,RADIAS,etal.TheHadoopdistributedfilesystem[C]//Proceedingsofthe2010IEEE26thSymposiumonMassStorageSystemsandTechnologies.Washington,DC:IEEEComputerSociety, 2010: 1-10.

[5]HUANGL,PAWARS,ZHANGH,etal.Codescanreducequeueingdelayindatacenters[C]//Proceedingsofthe2012IEEEInternationalSymposiumonInformationTheory.Piscataway,NJ:IEEE, 2012: 2766-2770.

[6]LIANGG,KOZATUC.Fastcloud:pushingtheenvelopeondelayperformanceofcloudstoragewithcoding[J].IEEE/ACMTransactionsonNetworking, 2014, 22(6): 2012-2025.

[7]SHAHNB,LEEK,RAMCHANDRANK.TheMDSqueue:analysinglatencyperformanceofcodesandredundantrequests[EB/OL]. [2016- 01- 07].http://people.eecs.berkeley.edu/～nihar/publications/The_MDS_Queue.pdf.

[8]ROSENTHALJ,SMARANDACHER.Maximumdistanceseparableconvolutionalcodes[J].ApplicableAlgebrainEngineering,CommunicationandComputing, 1999, 10(1): 15-32.

[9]RASHMIK,SHAHNB,GUD,etal.Asolutiontothenetworkchallengesofdatarecoveryinerasure-codeddistributedstoragesystems:astudyonthefacebookwarehousecluster[C]//Proceedingsofthe5thUSENIXConferenceonHotTopicsinStorageandFileSystems.Berkeley,CA:USENIXAssociation, 2013: 8.

[10]Openstack.Swiftservice[EB/OL]. [2016- 06- 10].https://wiki.openstack.org/wiki/Swift/.

[11]HadoopWiki.HDFS-RAID[EB/OL]. [2016- 06- 10].http://wiki.apache.org/hadoop/HDFS-RAID.

[12]ZHANGB,IOSUPA,POUWELSEJ,etal.Thepeer-to-peertracearchive:designandcomparativetraceanalysis[C]//ProceedingsoftheACMCoNEXTStudentWorkshop.NewYork:ACM, 2010:ArticleNo. 21.

[13]YEUNGKH,SZETOCW.OnthemodelingofWWWrequestarrivals[C]//Proceedingsofthe1999InternationalWorkshopsonParallelProcessing.Piscataway,NJ:IEEE, 1999: 248-253.

[14]Wikipedia.Openstack[EB/OL]. [2016- 06- 10].https://en.wikipedia.org/wiki/OpenStack.

[15]Wikipedia.Prim’salgorithm[EB/OL]. [2016- 06- 10].https://en.wikipedia.org/wiki/Prim%27salgorithm.

[16]LIUS,HUANGX,FUH,etal.Understandingdatacharacteristicsandaccesspatternsinacloudstoragesystem[C]//Proceedingsofthe2013 13thIEEE/ACMInternationalSymposiumonCluster,CloudandGridComputing.Piscataway,NJ:IEEE, 2013: 327-334.

[17]SUNY,ZHENGZ,KOKSALCE,etal.Provablydelayefficientdataretrievinginstorageclouds[C]//Proceedingsofthe2015IEEEConferenceonComputerCommunications.Piscataway,NJ:IEEE, 2015: 585-593.

[18]JOSHIG,LIUY,SOLJANINE.Onthedelay-storagetrade-offincontentdownloadfromcodeddistributedstoragesystems[J].IEEEJournalonSelectedAreasinCommunications, 2013, 32(5): 989-997.

[19]CHANGF,DEANJ,GHEMAWATS,etal.Bigtable:adistributedstoragesystemforstructureddata[J].ACMTransactionsonComputerSystems, 2008, 26(2): 205-218.

[20]HUANGC,SIMITCIH,XUY,etal.Erasurecodinginwindowsazurestorage[C]//Proceedingsofthe2012USENIXConferenceonAnnualTechnicalConference.Berkeley,CA:USENIXAssociation, 2012: 2.

[21]CHENS,SUNY,KOZATUC,etal.Whenqueueingmeetscoding:optimal-latencydataretrievingschemeinstorageclouds[C]//Proceedingsofthe2014ProceedingsIEEEINFOCOM.Piscataway,NJ:IEEE, 2014: 1042-1050.

[22]LIANGG,KOZATUC.TOFEC:achievingoptimalthroughput-delaytrade-offofcloudstorageusingerasurecodes[C]//Proceedingsofthe2014ProceedingsIEEEINFOCOM.Piscataway,NJ:IEEE, 2014: 826-834.

[23] 羅象宏,舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2012,49(1):1-11.(LUOXH,SHUJW.Summaryofresearchforerasurecodeinstoragesystem[J].JournalofComputerResearchandDevelopment, 2012, 49(1): 1-11.)

[24] 蔣海波,王曉京,范明鈺,等.基于水平糾刪碼的云存儲數(shù)據(jù)布局方法[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2013,45(2):103-109.(JIANGHB,WANGXJ,FANMY,etal.Adataplacementbasedonlevelarraycodesincloudstorage[J].JournalofSichuanUniversity(EngineeringScienceEdition), 2013, 45(2): 103-109.)

[25] 李曉愷,代翔,李文杰,等.基于糾刪碼和動(dòng)態(tài)副本策略的HDFS改進(jìn)系統(tǒng)[J].計(jì)算機(jī)應(yīng)用,2012,32(8):2150-2158.(LIXK,DAIX,LIWJ,etal.ImprovedHDFSschemebasedonerasurecodeanddynamical-replicationsystem[J].JournalofComputerApplications, 2012, 32(8): 2150-2158.)

[26] 葛君偉,李志強(qiáng),方義秋.云存儲環(huán)境下基于分散式服務(wù)器的ErasureCode算法[J].計(jì)算機(jī)應(yīng)用,2011,31(11):2940-2942.(GEJW,LIZQ,FANGYQ.Erasurecodealgorithmbasedondistributedserverincloudstorageenvironment[J].JournalofComputerApplications, 2011, 31(11): 2940-2942.)

[27] 程振東,欒鐘治,孟由,等.云文件系統(tǒng)中糾刪碼技術(shù)的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)與探索,2013,7(4):315-325.(CHENGZD,LUANZZ,MENGY,etal.Researchandimplementationonerasurecodeincloudfilesystem[J].JournalofFrontiersofComputerScienceandTechnology, 2013, 7(4): 315-325.)

ThisworkispartiallysupportedbytheNationalHighTechnologyResearchandDevelopmentProgram(863Program)ofChina(2015AA01A202).

LIAO Hui, born in 1991, M. S. candidate. His research interests include cloud computing and big data.

XUE Guangtao, born in 1976, Ph. D., professor. His research interests include mobile and wireless computing, social network, distributed computing, wireless sensor network, cloud computing and big data.

QIAN Shiyou, born in 1977, Ph. D., assistant professor. His research interests include cloud computing and big data.

LI Minglu, born in 1965, Ph. D., professor. His research interests include vehicular Ad Hoc network, wireless sensor network, cloud computing and big data analysis.

Fine-grained scheduling policy based on erasure code

LIAO Hui, XUE Guangtao*, QIAN Shiyou, LI Minglu

(DepartmentofComputerScienceandEngineering,ShanghaiJiaoTongUniversity,Shanghai200240,China)

Aiming at the problems of long data acquisition delay and unstable data download in cloud storage system, a scheduling scheme based on storage node load information and erasure code technique was proposed. Firstly, erasure code was utilized to improve the delay performance of data retrieving in cloud storage, and parallel threads were used to download multiple data copies simultaneously. Secondly, a lot of load information about storage nodes was analyzed to figure out which performance indicators would affect delay performance, and a new scheduling algorithm was proposed based on load information. Finally, the open-source project OpenStack was used to build a real cloud computing platform to test algorithm performance based on real user request tracing and erasure coding. A large number of experiments show that the proposed scheme not only can achieve 15% lower average delay but also reduce 40% volatility of delay compared with other scheduling policies. It proves that the scheduling policy can effectively improve delay performance and stability of data retrieving in real cloud computing platform, achieving a better user experience.

cloud storage system; erasure code; scheduling algorithm; average delay; stability

2016- 09- 21;

2016- 10- 18。

國家863計(jì)劃項(xiàng)目(2015AA01A2020)。

廖輝(1991—)，男，江西南豐人，碩士研究生，主要研究方向：云計(jì)算、大數(shù)據(jù)； 薛廣濤(1976—)，男，山東濟(jì)南人，教授，博士，CCF會員，主要研究方向：移動(dòng)和無線計(jì)算、社交網(wǎng)絡(luò)、分布式計(jì)算、無線傳感網(wǎng)、云計(jì)算、大數(shù)據(jù)； 錢詩友(1977—)，男，江蘇連云港人，助理研究員，博士，主要研究方向：云計(jì)算、大數(shù)據(jù)； 李明祿(1965—)，男，重慶人，教授，博士，CCF會員，主要研究方向：車輛自組網(wǎng)、無線傳感器網(wǎng)絡(luò)、云計(jì)算、大數(shù)據(jù)分析。

1001- 9081(2017)03- 0613- 07

10.11772/j.issn.1001- 9081.2017.03.613

TP391.9

A