一種基于共享公平和時變資源需求的公平分配策略

李 杰 張 靜 李偉東 張學杰

1(云南大學信息學院 昆明 650500)2(云南大學數學與統計學院 昆明 650500)

云計算資源提供商可以將云計算資源動態地提供給用戶使用，由于其可靠性和方便的特點，目前大量的企業和個人都傾向于將計算和存儲任務提交到云平臺上執行.如何提高資源利用率，無論從高效或者降低成本的角度來說，對于用戶和資源提供商都是當前關注的重點.資源共享方式[1]，是一種非常有效的提高資源利用率的方法，系統通過云計算虛擬化技術將計算資源整合，實現資源共享功能，如Mesos[2]和Hadoop Yarn[3]等.在資源共享系統中，如何保證在用戶間公平高效地分配資源是需要解決的關鍵問題.

目前，對于多種資源分配機制的公平性和高效性主要由經濟學中一些屬性來定義.

1) 激勵共享[4].系統中所有用戶在共享情形下由機制分配的資源量不小于其在獨自占有資源情形下獲得的資源量.

2) 帕累托最優[4].系統中任意一個用戶在分配機制中獲得比原來更多資源時，至少有另外一個用戶將受到損失.

3) 無嫉妒[5].系統中沒有任何用戶嫉妒其他用戶所分配的任意一種資源.

4) 可信[5].系統中任何謊報任務資源需求的用戶將不會獲得更多的資源.

目前，占優資源公平分配機制(dominant resource fairness, DRF)[6]被廣泛用于Mesos和Hadoop Yarn等云計算系統中.DRF計算用戶任務所需的每種資源累計分配量占系統中該資源總量的比值，所有資源中比值最大的那種資源為占優資源(dominant resource, DR),與其相對應的比值為占優份額(dominant share，DS).DRF機制的基本思想是使所有用戶中占優資源份額最小的用戶所分得的資源盡可能大.該機制能夠在多資源并存情形下保證分配的公平.然而，DRF機制是基于資源由第三方提供分配，在實際資源共享系統中，每個用戶對資源的共享量可能不同，共享資源多的往往期望得到更多的資源.

文獻[7]針對動態情形下資源分配公平性和效率做出了改進，允許用戶隨時進入系統但不離開系統，假設每個用戶的任務數是無限的，并未考慮實際環境中用戶任務數是有限的情形；文獻[8]在DRF機制的基礎上提出了一種解決動態情形下資源分配的機制，即動態占優資源公平分配機制(dynamic dominant resource fairness mechanism, DDRF)，并給出了求解DDRF機制的一種線性多項式時間算法，該算法在動態資源分配中有很好的效果，但未考慮異構云計算環境下資源分配的問題；文獻[9]針對系統中具有多個異構虛擬機的資源分配問題提出了面向異構云計算系統占優資源公平分配機制(dynamic dominant resource fairness mechanism in heterogeneous cloud computing system, DRFH)，該機制利用全局占優資源份額公平[9]的概念對具有異構虛擬機的云計算資源系統進行資源分配，該機制假設用戶任務數沒有上限，并未考慮用戶具有有限任務數的情形；針對用戶有限任務數的資源分配問題，文獻[10]提出了一種資源分配機制，考慮了在動態情形下用戶具有有限個任務數需求的資源分配問題；文獻[11]提出了多種啟發式資源分配算法，在異構資源分配情形下取得了較好效果，但算法未考慮資源共享情形下用戶具有多組資源需求的情形.針對用戶具有多組資源需求的動態資源分配情形，文獻[12]設計了一種啟發式算法，提出了資源共享公平概念,解決了用戶具有多組任務需求的問題，但是該文并未考慮系統具有多個異構的虛擬機，用戶在不同時刻每個任務所需資源不同的情形.

綜上，在多種共享虛擬資源分配的問題上，目前的研究已經取得了許多積極的成果，但是在考慮用戶共享資源[1-2]，用戶在不同時刻有不同的任務需求和有限的任務數情形下，用戶貢獻資源與分配資源的公平性問題上仍然面臨挑戰.本文研究一種公平的多資源動態分配機制，旨在解決用戶在不同時刻具有多組有限時變任務需求情形下云計算資源共享系統的資源分配問題.本文具體包括2方面研究:

1) 多資源動態分配機制設計.動態情形下，用戶可提出多組有限時變多資源的任務需求，較其他分配機制，可使得用戶在多組時變需求情形下，滿足共享資源量與分配的資源量公平性，為云計算資源動態分配問題提出了更現實的解決方案.

2) 多資源分配算法設計.結合字典序最優[13]的概念，提出了合理的資源分配模型以滿足動態云計算資源分配場景，設計了啟發式的資源分配算法，解決了共享資源系統中共享公平性問題.

理論和實驗表明：本文提出的方法解決了云計算共享資源系統中用戶多組時變任務需求的多資源公平分配問題.

1 問題描述及模型定義

1.1 問題描述

在云計算資源共享系統[12]中，用戶將服務器資源共享到云計算虛擬機集群中，用戶有任務需求時，系統再將資源分配給用戶以達到更高的資源利用率.用戶任務的資源請求是由具有不同資源配置的虛擬機進行響應.用戶任務的資源分配過程為虛擬機資源調度過程.

文獻[13]假定用戶需求的任務數在不同時刻是有限的，用戶i在時刻t需求任務數上限為Bi(t).與文獻[13]不同的是，本文假定每個用戶在不同時刻的任務資源需求是不相同的.令:

αi(t)=(αi1(t),αi2(t),…,αim(t))，

為用戶i在時刻t的每個任務所需資源向量，其中αij(t)表示用戶i在時刻t的每個任務對第j種資源的需求量.對于任意一個用戶i∈U，令i在時刻t的最大任務資源需求為向量

Di(t)=(Di1(t),Di2(t),…,Dim(t))，

其中,Dij(t)=αij(t)·Bi(t)表示在時刻t用戶i的任務對第j種資源的最大需求量.方便起見，對于任意用戶i∈U和任意資源j(1≤j≤m)，令Dij(t)>0，任務執行時長為單位時長.

對任意用戶i∈U在時刻t的資源分配向量U(t)已知情形下，用戶i在時刻t在虛擬機k上能執行的最大任務數為

(1)

用戶i在時刻t能執行的最大任務數為

(2)

(3)

根據文獻[14]可知,用戶完成的任務數跟其任務需求中的占優資源有關，令:

(4)

為任意一個用戶i∈U，在時刻t每個任務中資源需求量占總資源容量比例最大值，我們定義用戶i到時刻t為止的累計帶權全局占優資源份額為

(5)

其中:

為用戶i到時刻t為止在虛擬機k上所分得的累計帶權的全局占優資源份額.為了方便起見，我們將累計帶權的全局占優資源份額簡稱為累計全局占優資源份額.

1.2 資源共享公平定義

(6)

在時刻t用戶i的第j種資源在所有虛擬機全局共享系數為

(7)

根據文獻[14],由于在多種資源分配中，用戶分得的資源所能執行的任務數由其占優資源決定，定義用戶i在時刻t的全局共享系數為

(8)

在共享資源情形中，βi>1表示i用戶完成的任務數比不共享資源情形多，稱為共享受益;βi<1表示表示i用戶完成的任務數比不共享資源情形少，稱為共享缺損;βi=1表示i用戶完成的任務數與不共享資源情形相同.為了使用戶在共享資源的情形下執行的任務數不小于不共享情形，必有βi≥1.

1.3 資源動態分配公平性質

在云計算資源共享系統中，資源分配的公平性是非常關鍵的.只有當每個系統中用戶能夠公平分配到資源時，多資源共享分配才可行.文獻[4]中引入了4個重要屬性：激勵共享、帕累托最優、無嫉妒、可信.下面結合本文所研究用戶具有時變有限任務資源需求的情形，將上述公平性進行描述.

1.3.1 激勵共享

系統中對于任意一個用戶i∈U.在任意一個時刻t有βi(t)≥1.即系統中所有用戶在共享情形下獲得資源量不小于其在獨自占有資源情形獲得資源量，則認為該機制滿足激勵共享屬性.

1.3.2 帕累托最優

1.3.3 無嫉妒

若用戶i∈U到時刻t由分配機制分配的資源為向量Ui(t).首先，當用戶完成累計任務數達到其累計需求任務數上限，即:

則用戶i不會嫉妒其他用戶.

其次，當用戶完成累計任務數小于其累計需求任務數上限時，即:

用戶h≠i在時刻t由分配機制分配的資源為Uh(t),當至少存在一種資源j(1≤j≤m),到時刻t為止用戶i累計分配的第j種資源與共享權重之比不比用戶h所分配的少，即:

滿足時，稱資源分配機制滿足無嫉妒屬性.

1.3.4 可信

2 TV-DRF機制設計

本文設計一種針對用戶在不同時刻提出有限時變資源需求的無浪費資源公平 (time varied-DRF, TV-DRF) 分配機制.由于資源的有限性，如何設計分配機制使資源能夠公平地分配是一個難點，根據文獻[13]，字典序最大最小公平分配策略是一種較好的滿足任務數和資源數都有限情形下的分配策略:

令G(t)=(G1(t),G2(t),…,Gn(t))為時刻t系統中所有用戶累計全局占優資源份額向量.根據文獻[13]，結合本文我們得出累計全局占優資源份額向量滿足字典序最大最小最優的定義：

G(t)=(1.0,0.2,0.6)，

G′(t)=(0.6,0.3,0.4)，

按遞增排列為

maxGτ(t),

(9)

βi(t)≥1,?t,i∈U.

Gτ(t)表示在分配Ui(t)已知情形下任意時刻t累計全局占優資源份額向量的遞增排序.式(9)目標函數是指當所分配資源使用戶累計全局累計占優資源份額向量G(t)滿足字典序最優.式(9)第1個約束條件表示在時刻t所有用戶在任意1臺虛擬機分得的資源量不能超過該虛擬機的資源總量，第2個約束條件是指分配機制保證所有用戶不發生共享缺損.

因為用戶i在時刻t的最大需求任務數具有上限值為Bi(t)，所以根據式(5)可得用戶i在時刻t累計全局累計占優資源份額最大值為

根據文獻[13],在時刻t對于任意一個非負數G(t)>0,令A(G(t))=(G1(t),G2(t),…,Gn(t))為用戶累計全局占優資源份額向量，其中:

假設有一個用戶k∈U在時刻t的累計全局占優資源份額為

其中:

由于G′(t)為一個可行的累計全局占優資源份額向量，可得:

且有:

證畢.

引理2.若用戶k到時刻t分配資源所完成累計任務數小于時刻t累計提交任務需求上限，即:

成立時，字典序最優累計全局占優資源份額向量G*(t)中用戶k累計全局占優資源份額大于或等于所有用戶累計全局占優資源份額,即:

證畢.

其中:

根據式(5)，我們可以得到時刻t新的累計全局占優資源份額向量

其中:

由式(5)可得:

證畢.

定理1.當系統中有n個用戶、K個虛擬機時，TV-DRF機制所滿足激勵共享屬性.

證明. 若到任意時刻t為止，使任意一個用戶i∈U分得的累計資源量為其獨有的資源量時，有βi(t)=1.這就是說在任意時刻t,對于任意一個用戶i∈U而言，有使βi(t)≥1的分配是存在.從而有，到任意t時刻為止,TV-DRF機制使所有用戶全局共享系數均大于等于1的分配也是存在的，即βi(t)≥1,?t,i∈U.所以TV-DRF機制滿足激勵共享屬性.

證畢.

定理2.當系統中有n個用戶、K個虛擬機時， TV-DRF機制滿足帕累托最優屬性.

且不會使其他用戶最大可執行任務減少，相應地，根據式(5)可得新的時刻t累計全局累計占優資源份額向量為

其中，

證畢.

定理3.當系統中有n個用戶、K個虛擬機時，TV-DRF機制滿足無嫉妒屬性.

根據式(4)可得:

根據式(5)可得:

上式矛盾，所以TV-DRF機制滿足無嫉妒屬性.

證畢.

定理4.當系統中有n個用戶、K個虛擬機時，TV-DRF機制滿足可信性.

則用戶i在任何時刻謊報資源需求也不會增加其效用.所以，我們考慮用戶i累計完成任務數沒有達到提交任務數上限情形，即：

根據引理2可得:

(10)

根據式(1)～(5),TV-DRF機制所得用戶i在時刻t謊報資源需求時字典序最優全局累計占優資源份額向量為

根據式(1)(2)可知，若用戶i在時刻t謊報資源需求時，獲得的資源比誠實情形下多,則用戶i至少在某一個虛擬機k∈S上分得的資源比誠實情形下多：

(11)

根據式(5)可知, 當用戶i在時刻t謊報資源需求時,在虛擬機k上的累計全局占優資源份額比誠實情形下多：

根據式(5)可得:

(12)

所以一定存在至少一個用戶h≠i,當i在時刻t謊報需求時,在虛擬機k上獲得的第j種資源比i誠實報告需求時少：

(13)

結合上式，根據式(2)及用戶完成任務數不超過上限有:

(14)

(15)

根據引理2有:

(16)

結合式(10)(12)(15)(16)可得:

上式矛盾，所以TV-DRF機制滿足可信屬性.

證畢.

3 TV-DRF算法

本文結合第3節TV-DRF機制與文獻[9，12]的啟發式算法設計一個動態資源調度算法，即基于云計算資源共享系統多虛擬機情形下用戶提交多組有限的時變任務需求的動態多資源公平分配的啟發式算法TV-DRF (time varied-DRF)算法.

(17)

3) 執行步驟1、步驟2，當系統中的某種資源j,1≤j≤m分配完畢時，或者所有用戶任務執行完畢時，資源分配結束.

算法1.TV-DRF算法.

輸出:資源分配向量U(t).

βi(t)←0；*任意一個用戶i∈U,時刻t全局共享系數*

G(t)=(G1(t),G2(t),…,Gn(t))←0；*時刻t所有用戶累計全局占優資源份額向量*

② While 用戶任務沒有完成,?i∈U

③ Fori=1 ton

⑤ Ifβj(t)<1

⑥alloc(j)；

⑦ Else

⑧ Fori=1 ton

⑩alloc(g)；

在時刻t1，由于用戶A需要完成的任務數少，TV-DRF算法將2臺虛擬機資源分配給用戶A執行15個任務所需資源后將余下資源分給用戶B，用戶B分得70個任務所需資源，此時資源耗盡.根據全局共享系數定義可得βA(t1)=1，βB(t1)=1.4.在時刻t2開始時，根據2個用戶第2個時刻資源需求及時刻t1分配可知，用戶A全局共享系數為0.23，用戶B全局共享系數為0.7,優先分配資源給用戶A，分配資源(35CPU,35 GB)給用戶A，使得用戶A全局共享系數不小于用戶B.此時按照共享系數最小用戶優先分配資源的方式分配，當用戶A，B分別分得(50CPU,50 GB)和(40CPU,20 GB)資源時,2個用戶共享系數已等于1.此時按照累計全局占優資源份額最小的用戶最大的方式分配最終得βA(t2)=1.125，βB(t2)=1.

4 實驗及分析

本文采用來自阿里巴巴集群數據集[15]12 951個任務運行所需的CPU和Memory資源作為本文實驗中用戶資源需求.數據集中每個用戶以Job的形式提交多組任務資源需求，每個Job包含多組任務需求，每組任務由多個具有相同資源需求的實例組成,實驗從該數據集中隨機選取5，20，100個用戶，用戶資源需求如圖1和圖2所示，圖1，2中縱坐標表示用戶每個實例需要CPU數，橫坐標表示每個實例需要內存數，實心圓的面積與用戶任務數成正比，任務數越多則圓的面積越大.本文實驗模擬服務器配置如表1所示，其中服務器臺數為每個用戶所具有的服務器資源.本文假設用戶共享資源后虛擬機數與物理服務器數量相同.

Fig.1 20 users demand distribution圖1 20個用戶需求分布

Fig. 2 100 users demand distribution圖2 100個用戶需求分布

User NumberPer User Own MachinesCPU Capacity∕coreMemory Capacity∕GB512504020125040100120040

本文實驗平臺配置為:CPU為Intel i5-3230 M,12 GB內存，500 GB硬盤，實驗配置如下：

1) 由于一個用戶可以提出多組時變任務需求，本文將數據集batch_task文件中每組task看作為一個用戶在一個時刻的任務資源需求.

2) 實驗假設每個用戶共享到集群中每一臺虛擬機的每一種資源比例相同.

3) 將數據集中batch_task文件的create_timestamp認為是用戶任務需求的提交時間,任務執行時長為單位時長.

4) 通過用戶任務實例隊列方式，對資源配置進行模擬，即每個用戶有一個任務實例隊列，需求提交事件看做是實例到達事件發生，此時TV-DRF算法對用戶共享資源進行分配.

本文通過實驗比較TV-DRF算法與用戶在資源不共享的分配情形下中，5用戶最小用戶累計占優資源份額和20,100用戶情形下資源利用率，執行100次取平均來評估TV-DRF算法性能.

1) 使用戶累計占優資源份額滿足字典序最優

從圖3可以看出，由于TV-DRF算法目標是使用戶累計占優資源份額滿足最大、最小，因為用戶不共享情形下分得的資源為其自有資源.所以，TV-DRF算法與用戶不共享資源情形相比，最小的累計占優資源份額，隨著時間的推移，差距越來越大.這說明TV-DRF算法保證了分配過程中累計占優資源最小的用戶能分配最多的資源，也就是該用戶完成任務數最大.與不共享算法相比，保證了用戶完成的累計任務數盡可能多.

Fig. 3 Cumulative dominant share圖3 累計占優資源份額

Fig. 4 CPU utilization (20 users)圖4 CPU利用率(用戶數20)

2) 高資源利用率

本文將TV-DRF算法下的資源利用率與用戶在不共享資源的條件下系統的資源率進行比較.圖4～7分別表示在用戶數為20和用戶數為100情形下系統的資源利用率.可以看出TV-DRF算法在任意時刻的系統資源利用率都高于用戶在不共享資源條件下系統的資源利用率.

Fig. 5 Memory utilization (20 users)圖5 Memory利用率(用戶數20)

Fig. 6 CPU utilization (100 users)圖6 CPU利用率(用戶數100)

Fig. 7 Memory utilization (100 users)圖7 Memory利用率(用戶數100)

總之，TV-DRF算法在滿足公平性，使所有分配用戶能夠完成較多任務的同時，具有很高的資源利用率.

5 結束語

本文針對云計算資源共享系統中用戶有限多組時變任務資源需求的分配問題，提出了一種基于資源共享公平的多資源公平分配機制.該機制根據用戶不同時刻的有限時變任務需求和用戶共享資源量建立規劃模型，證明了在這種機制下用戶所得分配滿足4個公平屬性：激勵共享、帕累托最優、無嫉妒、可信.最后，實驗基于用戶累計占優資源份額，資源利用率與不共享資源算法進行對比，進一步說明TV-DRF算法能在保證用戶滿足累計占優資源份額字典序最優的同時，有較高資源利用率.但是，由于在算法執行過程中需要判斷用戶共享缺損，累計資源分配量等因素，使得算法在用戶數和虛擬機數較多時分配執行速度不占優勢.所以如何有效地使任務和虛擬機得到更優化的分配，以提高分配速度將是下一步研究重點.