面向云計算多租戶的主模塊公平調(diào)度算法*

高 倩 王鉞霖 于世行 王淑玉

（中國石油大學(xué)（華東）計算機與通信工程學(xué)院 青島 266580）

1 引言

近年來，隨著互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的發(fā)展以及移動設(shè)備的普及，云計算［1］作為一種新型的計算模式得到了學(xué)術(shù)界、工業(yè)界以及政府等多方面的高度關(guān)注。云計算中的租戶［2］通常代表著一個組織機構(gòu)，而用戶通常表示使用該組織機構(gòu)租用資源中的一名成員，租戶的概念也可以更好地表示客戶對使用資源的租用關(guān)系。

為了進一步保證共享環(huán)境中租戶的服務(wù)質(zhì)量并提高資源利用效率，公平的資源分配和任務(wù)調(diào)度是多租戶服務(wù)面臨的重要問題。文獻［3］將虛擬機分配調(diào)度問題及滿足用戶QoS相結(jié)合，通過改進遺傳算法來實現(xiàn)最大化服務(wù)利潤。文獻［4］考慮了在云計算環(huán)境下基于用戶任務(wù)的信任QoS情況，提出了一種在多維QoS約束條件下的任務(wù)調(diào)度機制，同時為了實現(xiàn)云數(shù)據(jù)中心動態(tài)的負載均衡采用了相對成熟的虛擬機遷移技術(shù)。關(guān)于多種資源的公平分配，許多研究僅關(guān)注可交換資源的公平分配問題［5］，然而云計算環(huán)境中許多情況下需要研究不可交換資源的公平分配問題。文獻［6］首次對云計算中的多資源公平分配問題進行了系統(tǒng)性的調(diào)研，提出的主資源公平分配方法旨在使租戶之間的關(guān)鍵資源比例相等，并且進一步證明了該公平分配理論所具有的公平特性。文獻［7］提出了多資源分配的統(tǒng)一分析框架，可以調(diào)節(jié)多資源分配中公平與利用率之間的平衡。文獻［8］從另一個角度分析了多資源的公平分配問題，提出了基于資源瓶頸的公平分配，并分析其具有兩種公平特性。文獻［9］通過分析不同配置的主資源公平，給出了主資源公平與資源瓶頸公平之間的關(guān)系。文獻［10］基于最大最小公平算法［11］來滿足更多用戶在資源需求方面的要求，這也是這個公平性理論的體現(xiàn)。

首先需要明確租戶共享的工作流程，以及工作流中不同服務(wù)模塊的資源需求量。在租戶的資源需求具有差異性的情況下，需要將各個服務(wù)模塊的資源高效且公平地提供給每一位租戶。服務(wù)提供者需要設(shè)計公平的分配方案，使得租戶之間不存在嫉妒或者欺騙等不利于共享的情況。另一方面，需要設(shè)計任務(wù)調(diào)度機制，對租戶多個共享服務(wù)模塊的調(diào)度進行統(tǒng)一管理，以保證資源公平分配方案的高效執(zhí)行。因此，通過公平的資源分配和任務(wù)調(diào)度，可以更好地實現(xiàn)租戶之間的性能隔離。

2 系統(tǒng)模型

在云計算中，租戶們在一個共享的數(shù)據(jù)中心上部署他們的服務(wù)。在服務(wù)運行時，租戶的任務(wù)量隨著時間不斷變化，資源的供給也需要隨之變化。租戶的資源供給過程如圖1 所示，租戶通過調(diào)用不同的服務(wù)模塊完成租戶的任務(wù)，通過虛擬化底層硬件資源形成資源池，可以根據(jù)租戶的任務(wù)量進行動態(tài)供給［12］。

圖1 系統(tǒng)模型圖

3 主模塊公平形式化描述

3.1 定義主模塊

在多租戶服務(wù)系統(tǒng)中，資源的共享級別與租戶的隔離性［13］相互制約，即總資源是共享的，各個租戶之間的資源是隔離的。用戶可以共享同一應(yīng)用服務(wù)，如圖2 所示，租戶通過多個服務(wù)模塊的配合完成一項作業(yè)，租戶I 和租戶II 共享服務(wù)模塊A 和B，租戶I 需要服務(wù)模塊A 一個單位資源，需要服務(wù)模塊B 兩個單位資源，而租戶II 需要服務(wù)模塊A 兩個單位資源，需要服務(wù)模塊B一個單位資源。

圖2 多租戶之間的性能隔離與資源共享

將服務(wù)模塊最小的資源單位設(shè)定為單位大小的虛擬機，服務(wù)模塊不同的任務(wù)類型不同，租戶對不同服務(wù)模塊需要的虛擬機數(shù)量也不同，根據(jù)主資源公平理論［14］，我們將租戶需要資源比例最大的共享服務(wù)模塊定義為租戶的主模塊。

將第i個租戶表示為ti，將其第j個共享服務(wù)模塊資源需求量表示為tdij。租戶需要的總資源

完成一項作業(yè)需要n 個共享服務(wù)模塊的集合表示為C：

第j 個共享服務(wù)模塊的最大虛擬機數(shù)量為Cj。tdij/cj表示租戶i 需要共享模塊j 的資源所占該共享服務(wù)模塊總資源的比例。其最大的比例值dci可表示為

例如，租戶I 和租戶II 共享服務(wù)模塊A 和服務(wù)模塊B，服務(wù)模塊A的虛擬機容量為10，服務(wù)模塊B的虛擬機容量為20。租戶I 對服務(wù)模塊A 的虛擬機需求量為3，對服務(wù)模塊B 的虛擬機需求量為4；租戶II 對服務(wù)模塊A 的虛擬機需求量為1，對服務(wù)模塊B的虛擬機需求量為4。如圖3所示。

即租戶I 對A 和B 的需求比例分別為30%和20%，根據(jù)主模塊定義，租戶I需要資源比例最大的共享服務(wù)模塊A 為主模塊。同理可求得，租戶II對A 和B 的需求比例分別為10%和20%，租戶II 的主模塊為B。

圖3 共享模塊分配示例

3.2 定義公平

由于多租戶需要共享基礎(chǔ)設(shè)施、數(shù)據(jù)庫甚至應(yīng)用服務(wù)模塊，而且租戶都本能地希望通過占有更多的資源以獲得更好的服務(wù)，共享服務(wù)模塊被所有租戶競爭共享，因此保證資源的公平分配尤其關(guān)鍵。同一公平分配策略在不同的應(yīng)用場景下具有不同的有效性，在多租戶環(huán)境中判斷一個分配策略是否公平，不能僅從資源分配的數(shù)量去判斷。

當有兩個共享服務(wù)模塊A 和B 時，部分租戶需要較多服務(wù)模塊A的資源，部分租戶需要較多服務(wù)模塊B 的資源，簡單將不同模塊資源進行平分的策略將導(dǎo)致資源與需求的不合理匹配主模塊公平策略將盡可能使租戶I使用模塊A的資源比例與租戶II使用模塊B的資源比例相等。

每個租戶都擁有主模塊，主模塊公平的核心思想就是讓各個租戶主模塊分配到的資源比例盡可能相等，在該約束條件下，為了使資源充分利用，可以將主模塊公平分配形式化為最大化可執(zhí)行任務(wù)數(shù)的優(yōu)化問題：

在如上主模塊共享資源例子中，求解優(yōu)化方程組：

求解方程組，可得：

x 和y 分別表示租戶I 和租戶II 可以完成的作業(yè)個數(shù)。因此，根據(jù)主模塊公平策略可以得到圖3所示的分配方案，租戶I 在其主模塊A 中獲得60%的資源，租戶II 在其主模塊B 中也同樣獲得60%的資源，兩個租戶主模塊資源比例相等。

4 主模塊公平調(diào)度算法

4.1 虛擬隊列

虛擬隊列表示服務(wù)模塊優(yōu)先級最高的任務(wù)集合，虛擬隊列中的任務(wù)根據(jù)其加入虛擬隊列的時間實行FCFS的調(diào)度方式。由于工作流程導(dǎo)致服務(wù)模塊之間本身具有一定的先后順序，假設(shè)服務(wù)模塊中選擇當前主模塊資源比例最少的租戶任務(wù)作為高優(yōu)先級進行調(diào)度。如果租戶的主模塊是流程中靠后的服務(wù)模塊，那么即使在第一個模塊調(diào)度了該租戶的作業(yè)，由于需要一段時間才能執(zhí)行到租戶的主模塊，其主模塊資源比例也不會提高。這樣可能出現(xiàn)即使調(diào)度了該租戶大量的作業(yè)，但是由于主模塊資源比例提高的延遲性，其作業(yè)在一段時間內(nèi)將被作為高優(yōu)先級調(diào)度，這也將導(dǎo)致其他租戶等待時間的增長。但是當該租戶作業(yè)的任務(wù)到達其主模塊時，其主模塊資源比例又會大幅提高，這樣其優(yōu)先級又變得很低，這將出現(xiàn)系統(tǒng)調(diào)度的不穩(wěn)定性。

所以我們設(shè)計一個虛擬隊列來解決調(diào)度時不穩(wěn)定的問題，當模塊資源任務(wù)來臨時，若空閑資源量大于需要的資源量時，服務(wù)模塊從實際隊列中選擇時間戳小的任務(wù)執(zhí)行；若空閑資源量不能滿足所需的資源量時，服務(wù)模塊的虛擬隊列就進行任務(wù)入隊操作，且以當前時間作為任務(wù)的時間戳，任務(wù)調(diào)度流程圖如圖4所示。

4.2 公平因子

虛擬隊列可以使調(diào)度算法在保證公平的基礎(chǔ)上，提高系統(tǒng)調(diào)度的穩(wěn)定性。為進一步提高資源利用率本節(jié)提出調(diào)度的公平因子，通過調(diào)節(jié)公平因子閾值的大小，進行公平與效率之間的平衡［15］。

圖4 任務(wù)調(diào)度流程圖

使用公平因子需要對任務(wù)執(zhí)行時間有一定的估計能力。假設(shè)服務(wù)模塊現(xiàn)有空閑資源量為w，在虛擬隊列中需要執(zhí)行的任務(wù)為a，其需要的資源量為n 且n＞w。在實際隊列中需要執(zhí)行的任務(wù)為b，其需要的資源為m且m＜w。按照公平的原則，需要等待服務(wù)模塊中有任務(wù)完成，等待總空閑資源可以執(zhí)行a 時，優(yōu)先調(diào)度執(zhí)行a。但是這可能造成空閑資源量w 的浪費。通過獲取模塊中所有任務(wù)的執(zhí)行情況，可以預(yù)估出等待可用資源n 所需要的時間tn，當tn大于任務(wù)b的執(zhí)行時間tb時，即使選擇執(zhí)行任務(wù)b也不會影響任務(wù)a的執(zhí)行。這樣可以進一步提高資源的利用率。

設(shè)定服務(wù)模塊擁有執(zhí)行虛擬隊列任務(wù)所需資源的最短等待時間為TN，當前空閑資源執(zhí)行實際隊列中可調(diào)度任務(wù)所需要的完成時間為TB。公平因子Δ 表示為兩者的比值：

可見Δ 的值越大，表明可以選擇實際隊列中可執(zhí)任務(wù)的調(diào)度彈性空間越大，根據(jù)貪心的思想選擇優(yōu)先級高且資源需求大的可執(zhí)行任務(wù)。由于任務(wù)執(zhí)行時間具有隨機性，因此根據(jù)任務(wù)執(zhí)行時間的均值方差S 統(tǒng)計數(shù)據(jù)，可以設(shè)定不同的公平因子閾值X，那么：

1）計算得到的公平因子大于閾值，即Δ ＞X時，調(diào)度器可以選擇充分利用空閑資源，調(diào)度實際隊列中的任務(wù)；

2）當計算得到的公平因子小于閾值，即Δ ＜X時，調(diào)度器等待正在執(zhí)行的任務(wù)完成并調(diào)度虛擬隊列中優(yōu)先級最高的任務(wù)。

5 算法實現(xiàn)及分析

本節(jié)針對上述調(diào)度算法機制，給出調(diào)度算法偽代碼。調(diào)度過程可以分為兩部分，首先是主模塊選擇算法，如算法5.1所示，從整體上根據(jù)主模塊公平對租戶的作業(yè)進行調(diào)度，其目的是保證整體的公平；其次是服務(wù)模塊調(diào)度算法，如算法5.2 所示，根據(jù)模塊中任務(wù)調(diào)度的優(yōu)先級，并且通過虛擬隊列和公平因子保證調(diào)度的穩(wěn)定性并提高模塊的資源利用率。

5.1 主模塊選擇算法

Require：

模塊總資源C，＜c1；c2；…cj＞；

模塊現(xiàn)有資源CR，＜cr1；cr2；…crj＞；

租戶i模塊占有量TCi，＜tci1；tci2；…tcij＞；

租戶i模塊需求量TDi，＜td1i；td2i；…tdij＞；

租戶i主模塊資源比例，dci；

Ensure：

是否可以進行調(diào)度；

1：選擇dci最小的租戶i，其主模塊為j；

2：if CR≥TDithen

3：TCi=TCi+TDi；

4：CR=CR-TDi；

5：dci=tci/cj；

6：returntrue；

7：else returnfalse；

8：end if

5.2 服務(wù)模塊調(diào)度算法

Require：

模塊資源空閑量,rw;

模塊正在執(zhí)行任務(wù)列表TE,＜te1;te2;…teq＞;

公平因子的閾值,X;

Ensure:

無返回值;

1:while!vheap.empty()andvheap.top().req＜=rwdo

2:TE.add(vheap.top());

3:rw=rw-vheap.top().req;

4:vheap.pop();

5:end while

6:if!vheap.empty()then

7:rn=vheap.top().req;

8:EN=set{sum(rheap.top(EN).req)＜rn};

9:ET=EN.makespan*X;

10:foreach i∈ETdo

11:foreach j∈TEdo

12:sumrn=TE[j].et＜ET[i]?sumrn+TE[j].et:sumrn;

13:end for

14:ifsumrn＜rnthen

15:TE.add(rheap.top());

16:rheap.pop();

17:elsebreak;

18:end if

19:end for

20:else:將rheap中可執(zhí)行任務(wù)添加至TE;

21:end if

6 性能評價

本節(jié)從模塊資源利用率以及完成時間兩個方面進行仿真實驗，仿真工具選擇CloudSim［16］平臺，對主模塊公平調(diào)度算法進行性能評價。仿真設(shè)置初始服務(wù)模塊數(shù)量為3，租戶量為2。租戶I的服務(wù)模塊資源需求向量為（2；10；2），租戶II的服務(wù)模塊資源需求向量為（10；5；40）。服務(wù)模塊A，B，C 的資源總量均為500，且服務(wù)速率均為2/s（完成時間期望為500ms）。根據(jù)設(shè)定參數(shù)可以計算，租戶I的主模塊為B，且主模塊資源需求比例為0.02；租戶II的主模塊為C，且主模塊資源需求比例為0.08。實驗中將主模塊公平與模塊比例公平進行性能比較，模塊比例公平中各個服務(wù)模塊均嚴格按租戶I與租戶II 的資源需求比例進行分配調(diào)度。實驗中將主模塊公平與模塊比例公平進行性能比較，模塊比例公平中各個服務(wù)模塊均嚴格按租戶I與租戶II的資源需求比例進行分配調(diào)度。

圖5 主模塊公平

在滿足算法分配比例的情況下，比較服務(wù)模塊的資源利用率。從圖5 中可以看出，主模塊公平除了模塊A 資源利用率在70%上下波動外，模塊B 和模塊C 的利用率均在90%以上。這也說明模塊B和模塊C 不僅為租戶的主模塊并且為系統(tǒng)的資源瓶頸，因此利用率很高。而圖6 的模塊比例公平中，三個模塊利用率均有較大波動且利用率均低于主模塊公平。

圖6 模塊比例公平

7 結(jié)語

本章對多租戶中公平的資源分配與任務(wù)調(diào)度問題進行了研究，首先，對主模塊以及公平性定義，分析其關(guān)鍵性。其次，為了在工作流中保證資源公平穩(wěn)定且高效地分配，提出基于虛擬隊列以及公平因子的調(diào)度算法。最后，通過性能評價展示了調(diào)度算法的有效性，與服務(wù)模塊比例公平的調(diào)度算法相比，主模塊公平調(diào)度保證了整體的公平性并提高了各個模塊的資源利用率。