廖 輝，薛廣濤，錢(qián)詩(shī)友，李明祿

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

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

廖 輝，薛廣濤*，錢(qián)詩(shī)友，李明祿

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1 單用戶(hù)請(qǐng)求調(diào)度算法。

輸入：用戶(hù)文件請(qǐng)求filej。

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

1)

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

2)

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

3)

根據(jù)filej使用的(nj,kj)糾刪碼，將文件請(qǐng)求映射到數(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ù)塊的存儲(chǔ)節(jié)點(diǎn)，利用storage[i]進(jìn)行初始化

8)

endfor

9)

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

10)

fori← 1 toki

11)

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

12)

endfor

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

實(shí)際上，在云存儲(chǔ)系統(tǒng)中，每秒往往有多個(gè)用戶(hù)請(qǐng)求到達(dá)。當(dāng)同時(shí)有多個(gè)請(qǐng)求到達(dá)時(shí)，由于算法1總是選擇負(fù)載最低的幾個(gè)存儲(chǔ)節(jié)點(diǎn)進(jìn)行調(diào)度，可能導(dǎo)致與代理節(jié)點(diǎn)建立的數(shù)據(jù)連接都集中在一部分存儲(chǔ)節(jié)點(diǎn)，從而造成這些節(jié)點(diǎn)吞吐量負(fù)載增高，影響文件獲取速度?？紤]同時(shí)有多個(gè)請(qǐng)求到達(dá)的情況，如果對(duì)請(qǐng)求一個(gè)一個(gè)進(jìn)行調(diào)度，前一個(gè)請(qǐng)求的調(diào)度結(jié)果會(huì)改變某些存儲(chǔ)節(jié)點(diǎn)的吞吐量，從而對(duì)下一個(gè)請(qǐng)求的調(diào)度產(chǎn)生影響，所以在這種情況下算法1不能達(dá)到最優(yōu)，它未考慮到請(qǐng)求之間的關(guān)聯(lián)性?，F(xiàn)在的問(wèn)題是，當(dāng)有多個(gè)請(qǐng)求同時(shí)到達(dá)時(shí)，如何進(jìn)行調(diào)度才能使每個(gè)存儲(chǔ)節(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)有的存儲(chǔ)節(jié)點(diǎn)storage[1,2,…,p]中。文中使用類(lèi)似于最小生成樹(shù)中的普里姆算法思想，對(duì)所有存儲(chǔ)節(jié)點(diǎn)按throughput_send信息進(jìn)行排序，然后每次從throughput_send最高的存儲(chǔ)節(jié)點(diǎn)中刪除一個(gè)數(shù)據(jù)塊，由于小數(shù)據(jù)塊對(duì)于吞吐量影響不大，在這里每次刪除最大的數(shù)據(jù)塊并更新當(dāng)前節(jié)點(diǎn)的throughput_send，重復(fù)操作，直到所有文件的數(shù)據(jù)塊數(shù)目分別等于k1,k2,…,kp，具體如算法2所示。

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

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

1)

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

2)

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

3)

fori← 1 top:

4)

根據(jù)file_list[i]使用的(ni,ki)糾刪碼，將文件請(qǐng)求映射到數(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對(duì)應(yīng)的所有數(shù)據(jù)塊的所在存儲(chǔ)節(jié)點(diǎn)信息，這里用storage[i]進(jìn)行初始化

9)

endfor

10)

fori← 1 toni

11)

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

12)

endfor

13)

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

14)

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

15)

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

16)

將該存儲(chǔ)節(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)測(cè)節(jié)點(diǎn)中保存的存儲(chǔ)節(jié)點(diǎn)負(fù)載信息初始化storage數(shù)組。3)～9)行將文件i請(qǐng)求根據(jù)使用的(ni,ki)糾刪碼映射到對(duì)數(shù)據(jù)塊的下載任務(wù)，利用ni、ki以及數(shù)據(jù)塊所在的存儲(chǔ)節(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ù)塊以及對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)信息初始化任務(wù)隊(duì)列chunk_task，進(jìn)行數(shù)據(jù)塊下載任務(wù)。該算法借鑒了普里姆算法的思路，使負(fù)載信息較為平均地分?jǐn)偟礁鱾€(gè)存儲(chǔ)節(jié)點(diǎn)，可以看出，當(dāng)同時(shí)有多個(gè)請(qǐng)求到達(dá)時(shí)，該算法接近最優(yōu)。

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

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

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

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

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

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

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

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

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

4.2 算法性能

圖3為用戶(hù)請(qǐng)求到達(dá)滿(mǎn)足韋伯分布得出的結(jié)果。橫坐標(biāo)表示用戶(hù)請(qǐng)求的總次數(shù)，本文測(cè)試了10，20，50，100，200，500幾組數(shù)據(jù)，縱坐標(biāo)表示完成所有請(qǐng)求所需的時(shí)延。文中使用4種不同的糾刪碼對(duì)文件進(jìn)行編碼，如圖3所示。從圖3可以看出，相比之前的工作，在請(qǐng)求量比較少的情況，存儲(chǔ)節(jié)點(diǎn)負(fù)載相對(duì)比較低，所以平均時(shí)延大致相同。而當(dāng)請(qǐng)求比較多時(shí)，可能會(huì)出現(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為用戶(hù)請(qǐng)求到達(dá)滿(mǎn)足真實(shí)用戶(hù)請(qǐng)求數(shù)據(jù)下得出的結(jié)果。橫坐標(biāo)表示用戶(hù)請(qǐng)求的總次數(shù)，縱坐標(biāo)表示所有請(qǐng)求完成所需的時(shí)延。同樣，這里使用了與圖3相同的幾組數(shù)據(jù)進(jìn)行測(cè)試以及相同的四種糾刪碼對(duì)文件進(jìn)行編碼?？梢钥闯?，本文提出的LOAD-ALGORITHM算法比SERPT-R算法完成所有請(qǐng)求所需的時(shí)間更短，降低10%～15%數(shù)據(jù)獲取的平均時(shí)延，相比FCFS-R算法降低20%～30%的平均時(shí)延。

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

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

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

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

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

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

6 結(jié)語(yǔ)

在云存儲(chǔ)系統(tǒng)中，本文基于糾刪碼技術(shù)，根據(jù)存儲(chǔ)節(jié)點(diǎn)的負(fù)載信息反向指導(dǎo)代理節(jié)點(diǎn)，從更細(xì)粒度層面進(jìn)行數(shù)據(jù)下載任務(wù)的調(diào)度。本文通過(guò)分析大量存儲(chǔ)節(jié)點(diǎn)的負(fù)載信息，找出影響文件獲取速度的性能指標(biāo)，并基于該指標(biāo)設(shè)計(jì)了新的調(diào)度算法。為了驗(yàn)證算法的性能，利用開(kāi)源項(xiàng)目OpenStack搭建了一個(gè)真實(shí)的云計(jì)算實(shí)驗(yàn)平臺(tái)，通過(guò)多種糾刪碼方案對(duì)大量文件進(jìn)行編碼存儲(chǔ)，在真實(shí)的云存儲(chǔ)環(huán)境下模擬不同用戶(hù)請(qǐng)求到達(dá)的情況，進(jìn)行大量的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，在云存儲(chǔ)系統(tǒng)中，本文提出的調(diào)度算法不僅能夠有效地降低數(shù)據(jù)獲取時(shí)延，還能保證不同用戶(hù)的數(shù)據(jù)下載時(shí)延趨于一致，提高數(shù)據(jù)獲取的穩(wěn)定性，從而提供更好的用戶(hù)體驗(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] 羅象宏,舒繼武.存儲(chǔ)系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2012,49(1):1-11.(LUOXH,SHUJW.Summaryofresearchforerasurecodeinstoragesystem[J].JournalofComputerResearchandDevelopment, 2012, 49(1): 1-11.)

[24] 蔣海波,王曉京,范明鈺,等.基于水平糾刪碼的云存儲(chǔ)數(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),方義秋.云存儲(chǔ)環(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。

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

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

1001- 9081(2017)03- 0613- 07

10.11772/j.issn.1001- 9081.2017.03.613

TP391.9

A