李 友，陳世平,2

?

基于分布式包簇映射的云資源分配策略

李 友1，陳世平1,2

（1. 上海理工大學 光電信息與計算機工程學院，上海 200085； 2. 上海理工大學 上海理工大學信息化辦公室，上海 200085）

傳統(tǒng)以虛擬機為中心的管理方式在可擴展性和靈活性方面存在嚴重問題，其資源分配往往被視為約束優(yōu)化問題和簡化成多維裝箱問題，隨著云計算市場規(guī)模越來越大，很難在規(guī)定的時間內求得最優(yōu)解，針對該問題提出了一種基于分布式包簇映射的資源管理框架。本文以系統(tǒng)負載均衡為目標，將服務器劃分為若干個服務器集群，減小問題規(guī)模，然后在每個服務器集群完成包簇映射進一步減小問題規(guī)模，并利用模擬退火算法實現(xiàn)全局最優(yōu)解。將提出的基于分布式包簇映射框架與基于包簇框架的遺傳算法進行比較，試驗結果表明，隨著簇個數的增加，提出的基于分布式包簇映射調度方法在大規(guī)模云資源分配負載均衡上有明顯的性能優(yōu)勢，有效的減少了簇的個數。

云計算；數據中心；資源分配；包簇

0 引言

近幾年，云計算取得了巨大成功，大量高科技公司涌入云服務市場，如亞馬遜EC2，谷歌AppEngine微軟，微軟Azure以及蘋果iCloud。云計算市場規(guī)模也來越大，為服務于快速增長的異構需求和動態(tài)變化的用戶群體，大量的數據中心建立起來。數據中心的的管理問題在于:在資源一定且復雜的情況下[1]，實現(xiàn)虛擬機到服務器的動態(tài)配置關系。還要盡最大能力保證用戶的各項指標要求，對目標進行優(yōu)化，降低成本。傳統(tǒng)的以虛擬機為中心的管理方式在可擴展性和靈活性方面存在嚴重問題，每個虛擬機在運行過程中所需要的資源要求被具體化，完成虛擬機到服務器映射的資源分配矩陣就可能有數以萬億計的自由變量[2]，優(yōu)化計算量大的不可想象，再考慮到新舊用戶的動態(tài)進出，資源分配的優(yōu)化計算[3]問題需要持續(xù)性地被處理。文獻[4]提出了一種包簇資源分配框架，通過分層的抽象模型來降解問題的規(guī)模，該方法采用分治的思想，將大問題的規(guī)模進行降解，使得小問題可以快速求解，最后合并。與傳統(tǒng)的以虛擬機為中心[5]的框架相比，提高了資源利用率，減少了物理機器使用個數。文獻[6]提出了一種可擴展分布式調度方法，當數據中心待調度的物理服務器的數量比較大時，將待調度的服務器劃分為若干個服務器集群，然后在每個服務器集群建立能耗優(yōu)化的資源分配模型，并利用約束編程框架Choco求解模型，獲得能耗最優(yōu)的資源分配方式，通過分而治之的方法大大降低資源分配復雜度，實現(xiàn)了能耗優(yōu)化和高效的資源分配。文獻[7]提出了提出了一種基于組的多目標遺傳算法虛擬機資源分配算法，將物理機器個數和虛擬機占用物理機器資源整合，有效減少了物理機器個數使用和提高了物理機器資源使用率，達到了節(jié)能目的。

然而以上的資源調度大都是以虛擬機為中心[8]而且不利于資源共享，很多用戶想以集中的方式指定計算機和存儲總資源，以避免事先確定虛擬機資源配置兒導致真正工作時部分虛擬機資源短缺而其他虛擬機資源閑置的情況發(fā)生，當問題規(guī)模較大時，解的空間比較大，在合理時間內求得最優(yōu)解非常困難。針對以上問題本文提出一種全新的云資源調度架構。首先將所有服務器劃分為若干個服務器集群，然后在每個服務器集群中建立包簇映射模型。

1 系統(tǒng)結構

1.1 問題描述

現(xiàn)有的云計算系統(tǒng)通常采用集中式調度方法，其靈活性以及可擴展性等存在一定問題，資源調度算法都是把物理機資源和虛擬機資源歸并在一起進行計算分配，資源管理框架YARN[9]是一個主從結構關系，圖1描述了YARN的基本組成架構，其中ResourceManager負責所有資源的監(jiān)控、分配和管理；NodeManager負責每一個節(jié)點的維護；ApplicationMaster負責每一個具體應用程序的調度和協(xié)調；在整個資源管理框架中，RM是主節(jié)點，NM為從節(jié)點，主節(jié)點負責對各個從節(jié)點上的資源進行統(tǒng)一分配和管理。所有的物理機和虛擬機都是在一次分配算法的運行中實現(xiàn)，這個時候的云資源分配便成了一個約束滿足問題的解決，先建立一個約束滿足問題模型，然后根據模型的優(yōu)化目標對模型進行求解，當云數據中心云服務器規(guī)模較小時，可以使用分支定界法或動態(tài)規(guī)劃方法等最優(yōu)化方法來求解。然而，由于基于約束滿足的資源分配模型的求解復雜度為服務器個數的指數復雜度，當云數據中心資源分配的問題規(guī)模非常大時則不能在短時間內求得最優(yōu)解。

圖1 資源管理框架YARN

1.2 基于分布式包簇映射的云資源分配方法設計

1.2.1 集群劃分

當云數據中心資源分配的問題規(guī)模比較大時，資源分配復雜度比較高。如果采用分布式方法，則會極大提高其靈活性及擴展性。為此，本文提出了基于分布式包簇映射的云資源分配方法，該方法采用了分層的抽象模型，將所有待調度的服務器劃分為若干個服務器集群，針對每個服務器集群建立負載均衡性能最優(yōu)化的資源分配模型，將所有待調度的服務器劃分為若干個服務器集群，減小問題規(guī)模，從而大大降低資源分配的復雜度，實現(xiàn)負載均衡的資源分配[10]。

1.2.2 簇的結構

在每個集群中云計算的資源將劃分為很多自治[11]的簇，簇就是數據中心拓撲中位置相近的服務器或者更低級別的簇的集合。簇中所擁有的資源就是組成這個簇的每一部分的資源之和。當低級別簇聚合成為高級別簇之后，又可進一步向上歸并，依據不同的層次包含關系可構造出不同的簇結構。

1.2.3 包的結構

定義“包”作為虛擬機或者子包的集合，是一個遞歸定義，即一個包可由多個二級包組成，每個二級包亦可由多個三級包組成或由多個虛擬機組成，以此類推，包的集中實現(xiàn)有利于包內虛擬機間的資源共享。這種遞歸定義允許用戶通過一種層次化結構來組織自己的資源需求，簇和包的結合降低了數據中心資源管理的復雜度。

2 算法實現(xiàn)

2.1 集群劃分算法

（1）輸入包、簇資源

（2）設定分組大小M，判斷簇的的個數是否大于M，如果總的簇個數大于M，則將所有的簇分割成不同的等份和集群，每個等份最多包含個數為M的簇，最后一個集群的簇個數大于或小于M，集群個數N = NC/M，其中NC為總的簇個數。

（3）對每個集群上的簇資源進行統(tǒng)計，將各個資源集群資源總和進行排序。

（4）在上一步驟中可以得知集群的個數為N，所以需要把包分割成N等份。

（5）將每份包資源進行統(tǒng)計并和步驟（3）一樣進行排序。

（6）將包資源總和排序高的分配給簇資源總和排序高的集群。

2.2 基于模擬退火的負載均衡算法

2.2.1 問題描述

目標是找到最佳的包分配方案使得系統(tǒng)負載平衡的性能達到最好。模型總結如下:

2.2.2 算法描述

（1）確定超過或將要超過負載的簇。即判定那一個簇將要超過額定負載，則將一個或多個分配在該簇上的包重新分配至其他簇，以減輕該簇的負載。

（2）確定負載過低的簇。判斷哪一個簇的負載過低，可以考慮將分配在該簇上的所有包重新分配至另外一個簇，以減少簇的個數來降低能耗。

（3）從負載過重的簇中選擇需要重新分配的包。

（4）為需要重新分配的包選擇合適的簇。

3 實驗及結果分析

為了驗證本文分基于分布式包簇映射的云資源分配策略（DPCM）的分配合理性，在CloudSim上進行仿真實驗[12]。CloudSim可以模擬真實的云計算系統(tǒng)及應用環(huán)境，并對其仿真建模，是一款可動態(tài)擴展的仿真工具包。

實驗平臺選取1000臺虛擬機部署到600臺物理服務器上。在基于包簇框架下進行集群劃分，這里服務器性能相同，將600臺物理服務器劃分為6個集群。DPCM算法中參數設置如下表：

表1 DPCM參數

Tab.1 DPCM parameters

實驗1 本文將提出的DPCM算法與基本的模擬退火算法（SA）和隨機調度算法（Random）相比，以簇的剩余資源的標準差最小化為目標，使得整個系統(tǒng)負載達到均衡，實驗結果如圖2所示。

圖2 DPCM算法與Random、SA算法對比

實驗結果分析：隨著包的個數增加，簇的剩余容量的標準差都將減少。但是DPCM算法的標準差明顯低于SA和Random，這是因為SA算法的初始解和領域解的產生是都是隨機的，而DPCM算法劃分集群減小了問題規(guī)模，根據優(yōu)化目標函數得到初始解和產生新的領域。Random算法完全沒有考慮簇的負載情況。該圖說明DPCM算法在負載均衡性能方面要比其他兩個算法好。

實驗2 將提出的DPCM和IMOPC進行比較，驗證簇的使用個數。實驗結果如圖。

圖3 DPCM算法與IMOPC算法對比

實驗結果分析：隨著包的個數增加，DPCM算法展現(xiàn)出明顯的優(yōu)勢，這是因為隨著包的個數增加，問題規(guī)模不斷上升，劃分集群有利于減小問題規(guī)模。該圖說明隨包個數增加，DPCM算法在減小簇的個數方面要好于IMOPC算法。

4 結束語

本文提出了一種基于分布式包簇映射的資源管理框架，該方法采用分而治之的思想來降低問題規(guī)模，并使用包簇分配模型能夠有效求得全局最優(yōu)解。實驗表明，隨著資源分配規(guī)模的增大，使得系統(tǒng)達到負載均衡的同時減小的簇的個數。

[1] RODRIGUES H, SANTOS J R, TURNER Y, et al. Gate-keeper: supporting bandwidth guarantees for multi-tenant datacenter networks[C]// WIOV 2011: Proceedings of the 3rd Conference on I/O Virtualization. Berkeley: USENIX, 2011: 6.

[2] JIN H, PAN D, EFFICIENT VM. Placement with multiple deter ministic and stochastic resources in data centers[C]// Proceedings of 2012 IEEE Global Communications confer-ence. Piscataway, NJ: IEEE, 2012: 2505-2510.

[3] Xu J, Fortes J. Optimization in autonomic data center resource and performance management[R]. Florida, USA: University of Florida, 2012.

[4] 盧浩洋, 陳世平. 基于包簇映射的云計算資源分配框架[J]. 計算機應用, 2016, 36(10): 2704-2709.

[5] Chen M, Zhang H, Su Y Y, et al. Effective VM sizing in virtualized data centers[C]. Macro: Proceeding of ACM SIGCOMM, 2011.

[6] 林偉偉, 朱朝悅. 面向大規(guī)模云資源調度的可擴展分布式調度方法[J]計算機本工程與科學11(37): 1997-2005.

[7] 陳小嬌, 陳世平, 方芳. 云計算中虛擬機資源分配算法[J], 2014, 31(9): 2584-2587.

[8] 李強, 郝沁汾, 肖利民, 等. 云計算中虛擬機放置的自適應管理與多目標優(yōu)化[J]. 計算機學報, 2011, 34(12): 2253-2264.

[9] 李媛禎. Hadoop YARN 資源分配與調度的研究[D]. 南京: 南京航空航天大學, 2015.

[10] 陳斌, 甘茂林, 李娟. 一種基于負載均衡的云資源調度方法[J]. 計算機技術與發(fā)展, 2017, 27(6): 51-55.

[11] 朱靜宜. 分布式云計算資源組織和任務分配策略. [J], 2013, 21(4): 1074-1076.

[12] CALHERIROS R N, RANJAN R, DE ROSE C A F, et al. Cloudsim: a novel framework for modeling and simulation of cloud computing infrastructures and services, RIDS-TR-2009-1 [R]. Parkville, VIC: University of Melbourne Australia, Grid Computing and Distributed System Laboratory, 2009: 47-58.

[13] 丁小盼, 周浩, 賀珊, 等. 基于OpenStack 的云測試平臺及其性能分析研究[J]. 軟件, 2015, 36(1): 6-11.

[14] 劉玄. 基于網絡虛擬化條件下的資源監(jiān)控研究[J]. 軟件, 2015, 36(1): 122-124.

[15] 陳若飛, 姜文紅. Hadoop 作業(yè)調度本地性的研究與優(yōu)化[J]. 軟件, 2015, 36(2): 64-68.

[16] 楊彬. 移動云計算中分布式計算卸載框架的研究 [J]. 軟件, 2015, 36(6): 129-133.

[17] 王書夢, 吳曉松. 大數據環(huán)境下基于MapReduce 的網絡輿情熱點發(fā)現(xiàn)[J]. 軟件, 2015, 36(7): 108-113.

Cloud Resource Allocation Based on Distribute Package Cluster Mapping

LI You1, CHEN Shi-ping1,2

(1. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology，Shanghai 200085, China; 2. Information Office of USST, University of Shanghai for Science and Technology, Shanghai 200085, China)

The traditional virtual machine-centric management has serious problems in scalability and flexibility, resource allocation is often regarded as constraint optimization problem and reduced to multidimensional packing problem. As the cloud market becomes large and large, it’s difficult to find optimal solution within the specific time, a resource allocation management framework based on distribute a distributed package-cluster mapping was proposed.This paper takes load balancing as the target, divides the servers into several server clusters, reduces the problem scale, and then completes the packet cluster mapping in each cluster to further reduce the problem scale. Moreover, an Simulated Annealing Algorithm was used in this framework. Experimental results showed that, compared with the tradition virtual machine centered framework based genetic algorithm, The distributed packet cluster mapping scheduling method has obvious performance advantages on the load balancing of large-scale cloud resource allocation, effectively reducing the number of clusters.

Cloud computing; Date center; Resource allocation; Package-cluster

TP39

A

10.3969/j.issn.1003-6970.2018.12.003

國家自然科學基金項目(61472256、61170277)；上海市一流學科建設項目(S1201YLXK)；上海理工大學科技發(fā)展基金(16KJFZ035?2017KJFZ033)；滬江基金(A14006)

李友(1993-)，男，研究生，主要研究方向：云計算；陳世平(1964-)，男，博士，教授，博士生導師，主要研究方向：云計算。

李友，陳世平. 基于分布式包簇映射的云資源分配策略[J]. 軟件，2018，39（12）：10-13