基于糾刪碼的細粒度云存儲調度方案

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

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

基于糾刪碼的細粒度云存儲調度方案

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

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

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

云存儲系統；糾刪碼；調度算法；平均時延；穩定性

0 引言

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

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

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

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

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

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

2)優化云存儲系統現有調度策略，根據存儲節點的負載信息反向指導代理節點進行線程調度，并基于負載信息設計一種新的調度算法。

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

1 系統架構

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

在本文中，云存儲系統同樣采用了以上所描述的體系架構，同時，在此基礎上新增了一個性能監測節點用于保存每個存儲節點的性能負載信息，為代理節點提供調度依據，如圖1所示。

圖1 云存儲系統架構

2 存儲節點負載信息分析

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

表1 負載信息采集表

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

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

圖2 存儲節點性能指標分析

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

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

3 云存儲調度算法

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

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

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

算法1 單用戶請求調度算法。

輸入：用戶文件請求filej。

輸出：數據塊下載任務隊列chunk_task[1-kj]。

1)

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

2)

storage[1 tonj].ip← 當前存儲節點的ip

3)

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

4)

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

5)

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

6)

fori← 1 tonj

7)

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

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

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

算法2 多用戶請求調度算法：LOAD-ALGORITHM。

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

1)

storage[1 toq].disk_read← 利用性能監測節點中記錄的負載信息，初始化storage數組

2)

storage[1 toq].ip← 當前存儲節點的ip

3)

fori← 1 top:

4)

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

5)

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

6)

chunk[i].k←ki,恢復文件i需要的數據塊個數

7)

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

8)

chunk[i].ips[1 toni] ← 保存文件i對應的所有數據塊的所在存儲節點信息，這里用storage[i]進行初始化

9)

endfor

10)

fori← 1 toni

11)

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

16)

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

4 實驗結果與分析

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

4.1 實驗環境

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

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

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

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

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

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

4.2 算法性能

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

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

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

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

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

圖5 調度算法對穩定性的影響

5 國內外相關研究

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

6 結語

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

)

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

[2] 華為.大數據和云計算[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] 羅象宏,舒繼武.存儲系統中的糾刪碼研究綜述[J].計算機研究與發展,2012,49(1):1-11.(LUOXH,SHUJW.Summaryofresearchforerasurecodeinstoragesystem[J].JournalofComputerResearchandDevelopment, 2012, 49(1): 1-11.)

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

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

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

[27] 程振東,欒鐘治,孟由,等.云文件系統中糾刪碼技術的研究與實現[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—)，男，江西南豐人，碩士研究生，主要研究方向：云計算、大數據； 薛廣濤(1976—)，男，山東濟南人，教授，博士，CCF會員，主要研究方向：移動和無線計算、社交網絡、分布式計算、無線傳感網、云計算、大數據； 錢詩友(1977—)，男，江蘇連云港人，助理研究員，博士，主要研究方向：云計算、大數據； 李明祿(1965—)，男，重慶人，教授，博士，CCF會員，主要研究方向：車輛自組網、無線傳感器網絡、云計算、大數據分析。

1001- 9081(2017)03- 0613- 07

10.11772/j.issn.1001- 9081.2017.03.613

TP391.9

A