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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2 存儲節(jié)點負載信息分析

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

表1 負載信息采集表

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

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

圖2 存儲節(jié)點性能指標分析

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

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

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

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

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

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

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

輸入：用戶文件請求filej。

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

1)

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

2)

storage[1 tonj].ip← 當前存儲節(jié)點的ip

3)

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

4)

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

5)

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

6)

fori← 1 tonj

7)

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

8)

endfor

9)

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

10)

fori← 1 toki

11)

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

12)

endfor

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

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

思路 傳輸一個數(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ù)塊導致負載提高的信息更新到現(xiàn)有的存儲節(jié)點storage[1,2,…,p]中。文中使用類似于最小生成樹中的普里姆算法思想，對所有存儲節(jié)點按throughput_send信息進行排序，然后每次從throughput_send最高的存儲節(jié)點中刪除一個數(shù)據(jù)塊，由于小數(shù)據(jù)塊對于吞吐量影響不大，在這里每次刪除最大的數(shù)據(jù)塊并更新當前節(jié)點的throughput_send，重復操作，直到所有文件的數(shù)據(jù)塊數(shù)目分別等于k1,k2,…,kp，具體如算法2所示。

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

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

1)

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

2)

storage[1 toq].ip← 當前存儲節(jié)點的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,恢復文件i需要的數(shù)據(jù)塊個數(shù)

7)

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

8)

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

9)

endfor

10)

fori← 1 toni

11)

更新storage[1-q]信息。假設(shè)需要下載文件的所有數(shù)據(jù)塊，利用chunk[i]信息更新所在存儲節(jié)點的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é)點，即storage[1]，找出最大的數(shù)據(jù)塊chunk[j]，并從存儲節(jié)點中刪除該數(shù)據(jù)塊并更新storage[1],storage[1].throughput_send←storage[1].throughput_send-chunk[j].size

16)

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

4 實驗結(jié)果與分析

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

4.1 實驗環(huán)境

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

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

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

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

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

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

4.2 算法性能

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

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

圖3 用戶請求到達服從韋伯分布時平均時延

圖4 用戶請求到達服從真實的用戶請求時平均時延

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

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

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

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

6 結(jié)語

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

)

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

[2] 華為.大數(shù)據(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].計算機研究與發(fā)展,2012,49(1):1-11.(LUOXH,SHUJW.Summaryofresearchforerasurecodeinstoragesystem[J].JournalofComputerResearchandDevelopment, 2012, 49(1): 1-11.)

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

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

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

[27] 程振東,欒鐘治,孟由,等.云文件系統(tǒng)中糾刪碼技術(shù)的研究與實現(xiàn)[J].計算機科學與探索,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計劃項目(2015AA01A2020)。

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

1001- 9081(2017)03- 0613- 07

10.11772/j.issn.1001- 9081.2017.03.613

TP391.9

A