面向云計算多租戶的主模塊公平調度算法*

高 倩 王鉞霖 于世行 王淑玉

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

1 引言

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

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

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

2 系統模型

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

圖1 系統模型圖

3 主模塊公平形式化描述

3.1 定義主模塊

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

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

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

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

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

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

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

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

圖3 共享模塊分配示例

3.2 定義公平

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

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

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

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

求解方程組，可得：

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

4 主模塊公平調度算法

4.1 虛擬隊列

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

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

4.2 公平因子

虛擬隊列可以使調度算法在保證公平的基礎上，提高系統調度的穩定性。為進一步提高資源利用率本節提出調度的公平因子，通過調節公平因子閾值的大小，進行公平與效率之間的平衡［15］。

圖4 任務調度流程圖

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

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

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

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

2）當計算得到的公平因子小于閾值，即Δ ＜X時，調度器等待正在執行的任務完成并調度虛擬隊列中優先級最高的任務。

5 算法實現及分析

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

5.1 主模塊選擇算法

Require：

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

模塊現有資源CR，＜cr1；cr2；…crj＞；

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

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

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

Ensure：

是否可以進行調度；

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 服務模塊調度算法

Require：

模塊資源空閑量,rw;

模塊正在執行任務列表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中可執行任務添加至TE;

21:end if

6 性能評價

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

圖5 主模塊公平

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

圖6 模塊比例公平

7 結語

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