王萬(wàn)良，臧澤林，陳國(guó)棋，屠杭垚，王宇樂(lè)，陸琳彥

（1. 浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027；2. 倫敦大學(xué)國(guó)王學(xué)院工程科學(xué)學(xué)院，英國(guó) 倫敦 WC2R 2LS）

1 引言

云計(jì)算是分布式計(jì)算（distributed computing）、網(wǎng)絡(luò)存儲(chǔ)（network storage technology）、負(fù)載均衡（load balance）等傳統(tǒng)計(jì)算機(jī)和通信技術(shù)發(fā)展融合的產(chǎn)物，由于云計(jì)算技術(shù)的通用性和高可靠性，該技術(shù)得到了廣泛的發(fā)展[1]。隨著云計(jì)算規(guī)模的逐步擴(kuò)大，谷歌、阿里巴巴、百度等大型互聯(lián)網(wǎng)企業(yè)紛紛搭建了自己的云服務(wù)平臺(tái)。它們建立的平臺(tái)可容納超過(guò)萬(wàn)臺(tái)的服務(wù)器，為超過(guò)百萬(wàn)的用戶進(jìn)行服務(wù)。大規(guī)模云服務(wù)平臺(tái)的建立，使云服務(wù)的調(diào)度系統(tǒng)變得更加重要[2]。在龐大的云服務(wù)平臺(tái)基數(shù)下，云服務(wù)平臺(tái)的性能即使有1%的提高也會(huì)帶來(lái)巨大的收益[3]。

目前，云計(jì)算調(diào)度分為云服務(wù)請(qǐng)求實(shí)時(shí)調(diào)度和基于歷史數(shù)據(jù)的云服務(wù)優(yōu)化調(diào)度。

云服務(wù)請(qǐng)求實(shí)時(shí)調(diào)度以調(diào)度系統(tǒng)的快速性、穩(wěn)定性為出發(fā)點(diǎn)，研究如何實(shí)時(shí)地將云計(jì)算任務(wù)指派給一臺(tái)或幾臺(tái)宿主機(jī)服務(wù)器實(shí)現(xiàn)負(fù)載均衡。在這類研究中，傳統(tǒng)的方法有Max-Min方法[4]、RR算法[5]、FCFS算法、FIFO算法[6]等。另外，一系列的商業(yè)軟件如 Google的 Borg調(diào)度系統(tǒng)[7-8]、阿里巴巴的Sigma調(diào)度系統(tǒng)[9]和MapReduce等開(kāi)源軟件都做出了相應(yīng)的學(xué)術(shù)貢獻(xiàn)。但是上述研究存在以下2個(gè)尚待解決的問(wèn)題：1)上述方法只能應(yīng)用于過(guò)程迭代和異構(gòu)任務(wù)類型，無(wú)法執(zhí)行遞歸或復(fù)雜的業(yè)務(wù)流；2)上述方法會(huì)出現(xiàn)占用特定的虛擬機(jī) I/O，造成其他作業(yè)“饑餓”的情況。

在基于歷史數(shù)據(jù)的云服務(wù)優(yōu)化調(diào)度領(lǐng)域，同樣出現(xiàn)了大量的研究成果。其中，Tsai等[10]闡述了實(shí)時(shí)的云計(jì)算的生命周期問(wèn)題，并在此基礎(chǔ)上提出了一種面向云計(jì)算實(shí)時(shí)調(diào)度的框架，該框架能夠有效地解決云計(jì)算實(shí)時(shí)調(diào)度的一般問(wèn)題。在此基礎(chǔ)上，Zhu等[11]提出了一種用于虛擬化云中實(shí)時(shí)任務(wù)調(diào)度的新型滾動(dòng)調(diào)度架構(gòu)，然后提出并分析了面向任務(wù)的能耗模型。另外，Zhu等[11]開(kāi)發(fā)了一種新的能量感知調(diào)度算法（EARH, energy awar），并通過(guò)實(shí)驗(yàn)證明了該算法能夠在可調(diào)度性和節(jié)能之間做出良好的權(quán)衡。王吉等[12]在考慮調(diào)度快速性和有效性的背景下，又考慮了調(diào)度的容錯(cuò)性，提出了一種在虛擬云平臺(tái)中的容錯(cuò)調(diào)度算法（FSVC, fault-tolerant scheduling algorithm in virtualized cloud），通過(guò)主副版本方法實(shí)現(xiàn)對(duì)物理主機(jī)的容錯(cuò)控制，采用副版本重疊技術(shù)與虛擬機(jī)遷移技術(shù)提高算法的調(diào)度性能。郭平等[13]將云平臺(tái)的調(diào)度問(wèn)題簡(jiǎn)化為本地化的調(diào)度問(wèn)題，并且結(jié)合主導(dǎo)資源公平調(diào)度策略 DRF和Delay調(diào)度約束機(jī)制，提出了一種滿足本地化計(jì)算的集群資源調(diào)度策略（DDRF, delay-dominant resource fairness），并討論了本地化計(jì)算時(shí)延對(duì)作業(yè)執(zhí)行效率的影響。另外，對(duì)于提供 GPU服務(wù)的云平臺(tái)，Peng等[14]提出了一種高效的、動(dòng)態(tài)的深度學(xué)習(xí)資源調(diào)度方法—— Optimus，該方法使用在線訓(xùn)練來(lái)擬合訓(xùn)練模型，并建立性能模型以準(zhǔn)確地估計(jì)每個(gè)作業(yè)的訓(xùn)練速度。就工作完成時(shí)間而言，Optimus的調(diào)度性能有63%的提高。

基于歷史數(shù)據(jù)的云服務(wù)優(yōu)化調(diào)度將同一云計(jì)算請(qǐng)求源產(chǎn)生的計(jì)算請(qǐng)求看成是可預(yù)測(cè)的時(shí)間序列。調(diào)度算法以該時(shí)間序列為基礎(chǔ)對(duì)宿主機(jī)服務(wù)器的分配進(jìn)行調(diào)度[15]。很多經(jīng)典的優(yōu)化方法和優(yōu)化理論可以引入調(diào)度框架[16]中，如遺傳算法（GA, genetic algorithm）[17]、群智能算法、局部搜索（LS, local search）算法[18]等。同時(shí)，有部分學(xué)者提出了專門面向服務(wù)器的調(diào)度算法。例如，林偉偉等[19]通過(guò)對(duì)約束滿足問(wèn)題對(duì)異構(gòu)的云數(shù)據(jù)中心的能耗優(yōu)化資源調(diào)度問(wèn)題建模，并且在此基礎(chǔ)上提出了能耗優(yōu)化的資源分配算法（DY, dynamic power）。Li等[20]提出了一種協(xié)調(diào)調(diào)度算法來(lái)解決過(guò)度生成虛擬機(jī)（VM, virtual machine）實(shí)例的問(wèn)題，并使用實(shí)際生產(chǎn)中的數(shù)據(jù)驗(yàn)證了該方法的有效性。Dong等[21]將云服務(wù)器調(diào)度問(wèn)題建模為混合整數(shù)規(guī)劃（MIP, mixed integer programming）問(wèn)題，將目標(biāo)函數(shù)設(shè)置為使數(shù)據(jù)中心服務(wù)器消耗的能量最小，并提出了一個(gè)有效的服務(wù)器優(yōu)先任務(wù)調(diào)度方案。

為了克服分支定界算法解決大規(guī)模問(wèn)題時(shí)間消耗龐大的問(wèn)題，本文將LS算法[22]的框架融入分枝定界算法，設(shè)計(jì)了最優(yōu)二元交換算法（OTECA,optimal two element exchange algorithm）。OTECA并不是使用分支定界法一次性解決全部問(wèn)題，而是每次只解決其中的部分子問(wèn)題。然后使用LS的思想不斷地選擇子問(wèn)題進(jìn)行解決。因此，OTECA可以通過(guò)求解多個(gè)子問(wèn)題獲得原問(wèn)題的解。上述求解策略可以快速有效地求解大規(guī)模的服務(wù)器調(diào)度問(wèn)題。實(shí)驗(yàn)證明，OTECA優(yōu)于LS、GA等算法。

2 云計(jì)算服務(wù)器調(diào)度模型

本節(jié)建立一個(gè)MIP模型，對(duì)云計(jì)算服務(wù)器調(diào)度問(wèn)題進(jìn)行描述。模型框架如圖1所示。

圖1顯示了云計(jì)算調(diào)度資源、調(diào)度方案、目標(biāo)函數(shù)、約束條件與運(yùn)算請(qǐng)求間的相互關(guān)系。本節(jié)將用數(shù)學(xué)方式對(duì)上述單元以建模的方式進(jìn)行描述。

2.1 云計(jì)算服務(wù)器的資源表示與數(shù)據(jù)描述

在整個(gè)調(diào)度過(guò)程中，需要處理的資源被抽象為5個(gè)集合：服務(wù)器集合M、應(yīng)用集合A、實(shí)例集合S、親和約束集合Q與反親和約束集合F。

每個(gè)宿主機(jī)服務(wù)器mj都可以提供多種類型的計(jì)算資源，服務(wù)器集合M可描述為

圖1 云計(jì)算服務(wù)調(diào)度模型框架

其中，n為服務(wù)器的數(shù)量，mj為第j臺(tái)服務(wù)器所能提供的資源，即

應(yīng)用集合A描述了請(qǐng)求服務(wù)器資源的應(yīng)用與其對(duì)服務(wù)器提供資源的消耗，即

其中，p為應(yīng)用的總量，ar為第r個(gè)應(yīng)用需求的資源，即

其中，CPU、DISK與MEM的每日資源消耗按照時(shí)間曲線給出，NET-IO、DISK-IO的每日資源消耗以常數(shù)的形式給出。為元素個(gè)數(shù)為N的列向量，其中k為時(shí)間維度的檢索句柄，滿足k∈{1,2,3,…,N}。

相互獨(dú)立的運(yùn)算請(qǐng)求被稱為實(shí)例。實(shí)例集合S包含調(diào)度過(guò)程中應(yīng)用產(chǎn)生的所有實(shí)例，即

其中，q為實(shí)例的總量，實(shí)例si為

親和約束與反親和約束描述了調(diào)度場(chǎng)景中的約束關(guān)系，主要分為2種情況：應(yīng)用與應(yīng)用之間的親和/反親和關(guān)系，應(yīng)用與服務(wù)器之間的親和/反親和關(guān)系。

親和/反親和關(guān)系可以描述為2個(gè)應(yīng)用之間（或者應(yīng)用與宿主機(jī)服務(wù)器之間）存在相互依賴或者相互排斥的關(guān)系。具體的親和/反親和關(guān)系描述如表 1所示。

表1 親和/反親和關(guān)系描述

親和/反親和的關(guān)系使用 0-1矩陣Haa、Ham、Faa、與Fam描述。應(yīng)用與應(yīng)用間的親和關(guān)系Haa的結(jié)構(gòu)描述為

Faa的結(jié)構(gòu)與Haa的結(jié)構(gòu)相同，其矩陣內(nèi)元素為，當(dāng)時(shí)，r1應(yīng)用與r2應(yīng)用不存在反親和關(guān)系，反之存在。Ham的結(jié)構(gòu)描述為

其中，Ham描述應(yīng)用與機(jī)器間的親和關(guān)系。

Fam的結(jié)構(gòu)與Ham的結(jié)構(gòu)相同，其矩陣內(nèi)元素為當(dāng)時(shí)，r應(yīng)用與j機(jī)器不存在反親和關(guān)系，反之存在。

2.2 云計(jì)算服務(wù)器調(diào)度的決策變量與目標(biāo)函數(shù)

云計(jì)算服務(wù)器的調(diào)度問(wèn)題乃至大部分的資源調(diào)度問(wèn)題都可以轉(zhuǎn)化為一個(gè)多維度的背包問(wèn)題。調(diào)度的目的是為每一個(gè)計(jì)算請(qǐng)求（實(shí)例si）尋找一個(gè)合適的宿主機(jī)服務(wù)器mj，減少系統(tǒng)的運(yùn)行成本。因此以0-1整數(shù)的形式，定義二維決策變量V描述實(shí)例到機(jī)器的分配關(guān)系，即

其中，vi,j為0-1決策變量，vi,j=1代表實(shí)例s1被調(diào)度到機(jī)器mj中執(zhí)行，反之沒(méi)有。

為了方便對(duì)親和/反親和約束描述，另外，設(shè)定輔助決策變量W來(lái)描述應(yīng)用到機(jī)器的分配關(guān)系，即

其中，wi,j為0-1決策變量，wi,j=1代表應(yīng)用ai被調(diào)度在機(jī)器mj中執(zhí)行，反之沒(méi)有。V與W之間存在的約束關(guān)系為

其中，R(i)為一個(gè)從實(shí)例Si到其對(duì)應(yīng)的應(yīng)用的映射。優(yōu)化調(diào)度的目標(biāo)描述為：在一定調(diào)度時(shí)間段內(nèi)，尋找一種使用服務(wù)器數(shù)量最少、負(fù)載均衡的服務(wù)器調(diào)度方案。為了避免由于模型不精確帶來(lái)的資源使用溢出風(fēng)險(xiǎn)，本文通過(guò)懲罰的形式定義目標(biāo)函數(shù)為

其中，k為時(shí)間索引，滿足k∈{1,2,3,…,N}；C為時(shí)間采樣頻率；Fj為宿主機(jī)服務(wù)器mj獲得的分?jǐn)?shù)值，其可以描述為

其中，β為懲罰閾值，當(dāng)宿主機(jī)服務(wù)器的CPU使用率大于懲罰閾值時(shí)，開(kāi)始引入額外平方項(xiàng)對(duì)調(diào)度方案進(jìn)行懲罰；α為懲罰增量系數(shù)，描述進(jìn)行懲罰時(shí)的懲罰力度；xj,k為機(jī)器mj在k時(shí)刻的CPU使用率，計(jì)算式為

單一機(jī)器 CPU使用率與目標(biāo)分?jǐn)?shù)關(guān)系如圖 2所示。由圖2可知，當(dāng)機(jī)器在所有的時(shí)間內(nèi)保持CPU使用率為0時(shí)，目標(biāo)分?jǐn)?shù)為0；當(dāng)機(jī)器的CPU使用率大于0且小于懲罰閾值β時(shí)，目標(biāo)分?jǐn)?shù)為1；但當(dāng)CPU使用率大于懲罰閾值時(shí)，目標(biāo)分?jǐn)?shù)從1開(kāi)始以二次冪形式上升。

圖2 單一機(jī)器CPU使用率與目標(biāo)分?jǐn)?shù)關(guān)系

2.3 云計(jì)算服務(wù)器調(diào)度的約束條件

實(shí)際的云計(jì)算服務(wù)器調(diào)度環(huán)境中存在大量由硬件條件和應(yīng)用功能導(dǎo)致的限制。模型將這些限制轉(zhuǎn)化為模型約束、資源約束、親和/反親和約束和優(yōu)先級(jí)約束進(jìn)行處理。

模型約束描述了調(diào)度模型的基本約束，包括每個(gè)實(shí)例都應(yīng)被安排到一個(gè)宿主機(jī)服務(wù)器上，且只能被安排到一臺(tái)宿主機(jī)服務(wù)器上，即

資源約束是一種由于資源限制造成的約束，每個(gè)宿主機(jī)服務(wù)器上配置的不同類型的資源是有容量上限的。

CPU資源約束為

DISK資源約束為

MEM資源約束為

NET-IO資源約束為

DISK-IO資源約束為

親和/反親和約束可以分為以下4種情況。

1) 應(yīng)用與應(yīng)用的親和約束

2) 應(yīng)用與應(yīng)用的反親和約束

3) 應(yīng)用與機(jī)器的親和約束

4) 應(yīng)用與機(jī)器的反親和約束

約束決策變量不能同時(shí)為1。

3 大規(guī)模云計(jì)算二元交換分析論證

將式(13)寫成max函數(shù)形式，定義評(píng)分函數(shù)為

其中，x為宿主機(jī)服務(wù)器某一時(shí)刻的CPU使用率，機(jī)器j的CPU使用率為xj。

引理1在所有對(duì)2臺(tái)機(jī)器進(jìn)行的CPU使用率(x1,x2)的重新分配(x1*,x2*)中，至少存在一個(gè)使評(píng)價(jià)分最小的最優(yōu)分配，且該最優(yōu)分配可由計(jì)算式和求得，其中，c為2臺(tái)機(jī)器的CPU容量的比例，即

證明將式(14)代入Ot(x1,x2)=f(x1)+f(x2)可得

由于實(shí)例的重新分配不改變其 CPU使用率絕對(duì)值之和，因此有

因此，可以表示成l(·)，即，將其代入式(26)，可得變量為x1*的方程為

對(duì)式(28)進(jìn)行分段討論后再對(duì)x1*求導(dǎo)可得

引理2定義機(jī)器j的特征計(jì)算式為xj為機(jī)器j的平均CPU使用率。在2臺(tái)機(jī)器的平均CPU占比為(x1,x2)的情況下，最優(yōu)分配(x1*,x2*)所帶來(lái)的評(píng)分之和的下降量Od(x1,x2,c)=Ot(x1,x2)-Ot(x1*,x2*,c)與 2臺(tái)機(jī)器的特征計(jì)算式的差的平方(g1-g2)2呈正相關(guān)。

證明對(duì)特征公式的差的平方(g1-g2)2進(jìn)行展開(kāi)，有

構(gòu)造函數(shù)

對(duì)于所有的自由變量，使用鏈?zhǔn)椒▌t進(jìn)行展開(kāi)，可得

其中

由于α、β與c皆大于或等于 0，Od對(duì)于特征計(jì)算式p的導(dǎo)數(shù)恒大于0，即D(x1,x2,c)＞0，因此2個(gè)方程呈正相關(guān)。證畢。

4 算法設(shè)計(jì)

混合整數(shù)規(guī)劃問(wèn)題是一個(gè)NP完全問(wèn)題，即求解該問(wèn)題的最優(yōu)解的時(shí)間復(fù)雜度與問(wèn)題的規(guī)模呈指數(shù)關(guān)系。隨著數(shù)據(jù)量的增長(zhǎng)，分支定界法不能在有效時(shí)間內(nèi)得到理想的解，基于此，本文設(shè)計(jì)了OTECA，尋找一個(gè)時(shí)間花費(fèi)與求解精度的平衡點(diǎn)，快速有效地解決云計(jì)算服務(wù)器調(diào)度問(wèn)題。

4.1 可行解生成方法

可行解生成方法負(fù)責(zé)生成占用盡量少的服務(wù)器資源且滿足約束要求的初始解。求解的流程如算法1所示。

算法1可行解生成方法（GSSM, good solution generation method）

輸入服務(wù)器集合M，應(yīng)用集合A，實(shí)例集合S

輸出調(diào)度初始可行解V，狀態(tài)矩陣E

1) 初始化可行解V，使用服務(wù)器數(shù)下限Nml=0，使用服務(wù)器數(shù)上限Nmh=p

2) whileNml!=Nmhdo

3) 機(jī)器指示m=0

4) for 實(shí)例索引s=0,s≤q,s++

5) if 實(shí)例s可裝入機(jī)器mthen

6)V,E=put(s,m) %將s放入m中，并更新?tīng)顟B(tài)

7) else

8)m=m+1,s=s-1

9) end if

10) ifm==Nmhthen %機(jī)器數(shù)選取過(guò)少

17) end if

18) end for

19) end while

20) returnV,E

算法通過(guò)二分法的形式對(duì)使用服務(wù)器數(shù)量的上限和下限不斷更新，從而不斷地拉近使用服務(wù)器的上下限的差距，最終在上下限相等時(shí)停止程序，完成對(duì)最合適的可行解的生成。步驟5)驗(yàn)證機(jī)器m裝入實(shí)例s后，是否仍然滿足模型約束。步驟 10)與步驟 15)判斷當(dāng)前的機(jī)器數(shù)量上限Nmh能否得到可行解，如果可以得到可行解，則進(jìn)一步減少機(jī)器數(shù)量，如果無(wú)法得到可行解，則增加機(jī)器的數(shù)量，直至上下限相等則退出方法。

在時(shí)間復(fù)雜度方面，由于每次進(jìn)入步驟 11)、步驟12)與步驟16)判斷都會(huì)造成Nmh與Nml的差減少一半，因此外部循環(huán)的復(fù)雜度為log(p)。步驟4)～步驟18)的內(nèi)部循環(huán)的次數(shù)受到實(shí)例數(shù)p與機(jī)器數(shù)n的影響，在最壞的情況下將進(jìn)行n+p次循環(huán)，因此整個(gè)算法的時(shí)間復(fù)雜度為(n+p)log(p)。

4.2 最優(yōu)二元交換算法

分支定界法求解大規(guī)模MIP問(wèn)題消耗的時(shí)間常常是不能接受的，但是求解較小規(guī)模的MIP問(wèn)題卻有很高的效率。該算法將通過(guò)求解一系列小規(guī)模的 MIP子問(wèn)題，去逼近整個(gè)大規(guī)模的 MIP問(wèn)題。

可以證明，在所有的實(shí)例都滿足約束被分配進(jìn)入宿主機(jī)服務(wù)器的情況下，將其中2臺(tái)機(jī)器中的實(shí)例以 BBM 方法重新分配到原來(lái)的宿主機(jī)服務(wù)器中，不會(huì)造成調(diào)度目標(biāo)值的上升（如引理1所示），且這2臺(tái)機(jī)器的特征計(jì)算式gj差距越大，其獲得更高分?jǐn)?shù)下降的可能性也就越大（如引理2所示）。

OTECA流程如圖3所示。

圖3 OTECA流程

最優(yōu)二元交換算法偽代碼如算法2所示。

算法2OTECA

輸入服務(wù)器集合M，應(yīng)用集合A，實(shí)例集合S，懲罰系數(shù)α和β，集合選擇系數(shù)γ，小規(guī)模MIP子問(wèn)題求解次數(shù)Ns

輸出服務(wù)器調(diào)度結(jié)果Vbest

1)V=GSSM(M,A,S) %生成可行解

2)M,ScoreList=Score(E,M) %按照式(14)對(duì)當(dāng)前可行狀態(tài)中每個(gè)服務(wù)器進(jìn)行打分，并按照分?jǐn)?shù)進(jìn)行排序

3) for loop=0, loop＜Naim, loop++

4)M=SMWS(M, ScoreList) %按照分?jǐn)?shù)調(diào)整順序

5)Smh,Sml=CMSet(Mc,A,S,α,β,γ) %選取高分服務(wù)器集合與低分服務(wù)器集合

6)Mh,Ml=ChoMach(Smh,Sml) %分別在2臺(tái)服務(wù)器集合中選取一臺(tái)待交換機(jī)器

7)VMIP,E=BBM(Mh,Ml,A,α,β)%分支定界法求解該小規(guī)模MIP問(wèn)題，得到新的分配方案與機(jī)器狀態(tài)

8) end for

9) returnVbest

最優(yōu)二元優(yōu)化部分是算法的核心部分，該部分為尋找一個(gè)優(yōu)秀的大規(guī)模服務(wù)器調(diào)度方案，其主要循環(huán)中包括高分機(jī)器集合與低分機(jī)器集合的維護(hù)、MIP子問(wèn)題選擇、MIP子問(wèn)題求解等步驟。

步驟 4)和步驟 5)生成一個(gè)高分機(jī)器集合與低分機(jī)器集合，其中特征分?jǐn)?shù)概念由目標(biāo)函數(shù)中目標(biāo)分?jǐn)?shù)的概念變化而來(lái)。該特征分?jǐn)?shù)綜合考慮了機(jī)器當(dāng)前負(fù)載與機(jī)器的容量這2個(gè)特性，可以表現(xiàn)機(jī)器未來(lái)的負(fù)載能力，如引理 2所示。步驟 5)中，使用最高分sh與最低分sl生成高分集合與低分集合，生成的標(biāo)準(zhǔn)為

其中，γ為集合選擇系數(shù)，一個(gè)較大的值可以使高分機(jī)器集合和低分機(jī)器集合隨循環(huán)次數(shù)的選擇增長(zhǎng)得更快；Smh為高分機(jī)器集合，Sml為低分機(jī)器集合。

步驟7)中設(shè)定當(dāng)機(jī)器得分不變的前提下，實(shí)例負(fù)載盡量裝入容量較大的服務(wù)器，從而盡量減少服務(wù)器的使用。步驟 4)～步驟 7)不斷解決子問(wèn)題優(yōu)化調(diào)度結(jié)果。

每個(gè)循環(huán)子問(wèn)題由高分機(jī)器、低分機(jī)器與機(jī)器中的實(shí)例組成。子問(wèn)題的最優(yōu)解一定是上述實(shí)例在上述機(jī)器上的重新組合?？梢宰C明，新解的目標(biāo)分?jǐn)?shù)之和一定優(yōu)于原解（如引理 1所示）。另外，高分機(jī)器與低分機(jī)器的分差越高，重新組合后分?jǐn)?shù)的優(yōu)化越顯著（如引理 2所示）。上述引理是算法挑選高分集合和低分集合進(jìn)行混合的原因。因此，最優(yōu)二元優(yōu)化算法比傳統(tǒng)的基于隨機(jī)或啟發(fā)的算法有更強(qiáng)的目的性，在前期擁有更高的收斂速度，在后期擁有更強(qiáng)的調(diào)度精確度。

算法初始階段將快速地消除高負(fù)載機(jī)器，造成低負(fù)載機(jī)器分?jǐn)?shù)上升、高負(fù)載機(jī)器分?jǐn)?shù)下降，這時(shí)高分機(jī)器集合和低分機(jī)器集合將出現(xiàn)一定重疊。隨著這種重疊現(xiàn)象的逐步加深，算法的子問(wèn)題選擇將逐漸退化為對(duì)機(jī)器的隨機(jī)優(yōu)化，從而對(duì)機(jī)器中實(shí)例進(jìn)行整理，并減小宿主機(jī)服務(wù)器的數(shù)量。最后該算法將返回從實(shí)例到宿主機(jī)服務(wù)器的優(yōu)化分配。

在時(shí)間復(fù)雜度方面，4.1節(jié)已經(jīng)論證了算法 2步驟1)的復(fù)雜度為(n+p) log(p)，步驟2)作為一個(gè)排序的工作，復(fù)雜度為nlog(n)。因?yàn)椴襟E3)～步驟7)在最壞情況下復(fù)雜度為Naim2x，其中x為子問(wèn)題中實(shí)例的數(shù)量，這并不意味著該步驟是十分耗時(shí)的，因?yàn)樵谧訂?wèn)題中，x受到機(jī)器容量的約束。在實(shí)際的應(yīng)用環(huán)境中，步驟7)均可以在可接受的時(shí)間（秒級(jí)）范圍內(nèi)得到響應(yīng)，則算法2總的時(shí)間復(fù)雜度為(n+p)log(p)+nlog(n)。

5 仿真與驗(yàn)證

5.1 實(shí)驗(yàn)硬件架構(gòu)描述與數(shù)據(jù)集描述

為了保證改進(jìn)算法得到充分穩(wěn)定的測(cè)試，本文使用不同規(guī)模的調(diào)度測(cè)試數(shù)據(jù)與阿里云計(jì)算中心公開(kāi)的實(shí)際數(shù)據(jù)集（ALISS）進(jìn)行仿真實(shí)驗(yàn)。數(shù)據(jù)中心擁有10 000臺(tái)不同配置的宿主機(jī)服務(wù)器。實(shí)驗(yàn)仿真硬件平臺(tái)為：曙光天闊W580-G20服務(wù)器，CPU E5-2620 v4 2.1 GHz；軟件環(huán)境為：ubuntu 18 LTS，Python3.6。

實(shí)驗(yàn)的硬件架構(gòu)如圖4所示。硬件架構(gòu)按照功能由4種節(jié)點(diǎn)組成，分別為資源節(jié)點(diǎn)、管理節(jié)點(diǎn)、調(diào)度節(jié)點(diǎn)和服務(wù)節(jié)點(diǎn)。其中，服務(wù)節(jié)點(diǎn)負(fù)責(zé)收集云計(jì)算請(qǐng)求，并以集合A、S的形式提交給調(diào)度節(jié)點(diǎn)。管理節(jié)點(diǎn)負(fù)責(zé)監(jiān)控資源節(jié)點(diǎn)的資源使用和工作情況，并以集合M的形式提交給調(diào)度節(jié)點(diǎn)。調(diào)度節(jié)點(diǎn)綜合整個(gè)云計(jì)算服務(wù)平臺(tái)的情況進(jìn)行調(diào)度工作，將運(yùn)算請(qǐng)求調(diào)度到資源節(jié)點(diǎn)中。

ALISS數(shù)據(jù)集中每一組數(shù)據(jù)由4張表格組成，分別是機(jī)器信息列表、應(yīng)用信息列表、實(shí)例信息列表、親和與反親和信息列表。其中，機(jī)器信息列表中含有M-id、M-c、M-m、M-d，M-id為機(jī)器的ID，M-c、M-m、M-d分別對(duì)應(yīng)機(jī)器集合的miCPU、miDISK、miMEM。應(yīng)用信息列表中含有 A-id、A-c、A-m、A-d，A-id為應(yīng)用的 ID，A-c、A-m、A-d分別對(duì)應(yīng)集合中的。時(shí)變數(shù)據(jù) CPU-use、MEM-use的采樣周期為15 min，即C=96。

圖4 實(shí)驗(yàn)的硬件架構(gòu)

5.2 OTECA在ALISS上的求解結(jié)果

本節(jié)使用OTECA求解ALISS-2數(shù)據(jù)集中的調(diào)度問(wèn)題。為了保證服務(wù)器運(yùn)行的穩(wěn)定性與資源分配的合理性，設(shè)置模型參數(shù)為α=10，β=0.5，選取OTECA參數(shù)為擇優(yōu)選取集合選擇系數(shù)γ=1.5，子問(wèn)題求解次數(shù)Ns=300，并對(duì)問(wèn)題進(jìn)行求解。求解過(guò)程如圖5～圖7所示。

圖5 ALISS-2問(wèn)題宿主機(jī)服務(wù)器數(shù)、目標(biāo)函數(shù)與循環(huán)次數(shù)關(guān)系

圖6 ALISS-2問(wèn)題高低分機(jī)器數(shù)與循環(huán)次數(shù)關(guān)系變化

圖7 ALISS-2宿主機(jī)服務(wù)器使用率與循環(huán)次數(shù)關(guān)系變化

優(yōu)化開(kāi)始時(shí)，宿主機(jī)服務(wù)器平均 CPU使用率僅在45%左右，這證明優(yōu)化開(kāi)始時(shí)服務(wù)器組的負(fù)載并不均衡。隨著算法迭代循環(huán)次數(shù)的增加，算法將得分較高的機(jī)器中的實(shí)例與得分較低的機(jī)器中的實(shí)例使用整數(shù)規(guī)劃的方法進(jìn)行最優(yōu)的重新組合，重新分配到原來(lái)的機(jī)器中，并將負(fù)載進(jìn)行有效的重組。由圖5可知，隨著優(yōu)化的進(jìn)行，得分在快速地下降。在最理想的情況下，算法將所有的機(jī)器的負(fù)載都調(diào)整到從下方逼近β的情況。由圖6可知，由于優(yōu)化開(kāi)始時(shí)機(jī)器分?jǐn)?shù)差異較大，以最高分和最低分劃定的高分機(jī)器集合和低分機(jī)器集合中元素較少。隨著優(yōu)化的進(jìn)行，機(jī)器的負(fù)載逐步平均，分?jǐn)?shù)的分布逐步集中，高分機(jī)器集合和低分機(jī)器集合逐漸包含同一部分機(jī)器。

當(dāng)loop＞100時(shí)，由于機(jī)器的負(fù)載已經(jīng)達(dá)到了平均水平，機(jī)器數(shù)與得分的差距基本不再變化，此時(shí)分?jǐn)?shù)的下降主要來(lái)自機(jī)器數(shù)的削減。當(dāng)某臺(tái)機(jī)器不執(zhí)行任何程序時(shí)，其得分為 0。因此在交換無(wú)法使負(fù)載更加均衡的情況下，OTECA的同樣的交換操作將盡量清除多余的宿主機(jī)服務(wù)器。由圖7可知，隨著循環(huán)次數(shù)的上升，CPU的平均使用率逐漸接近β，達(dá)到接近最優(yōu)解的狀態(tài)。

5.3 不同規(guī)模服務(wù)器調(diào)度問(wèn)題上算法性能對(duì)比

本文在不同規(guī)模的調(diào)度問(wèn)題中進(jìn)行算法性能的比較。實(shí)驗(yàn)算法包括 OTECA、分離化差分進(jìn)化算法（C-MSDE, cost modified separation differential evolution）[23]、成本時(shí)間進(jìn)化算法（CT-DE, cost time differential evolution）[24]、GA[17]和 LS[18]。

擇優(yōu)選取 OTECA 中參數(shù)γ=1.5，Ns=300；C-MSDE中選擇變異因子為 1，交叉因子為 0.5；CT-DE中Ptime=Pcost=0.5；GA中選擇概率為0.2，交叉概率為0.2，變異概率為0.2；LS中搜索范圍為3；C-MSDE、CT-DE、GA的種群數(shù)為300。測(cè)試使用的服務(wù)器規(guī)格數(shù)據(jù)與云計(jì)算要求數(shù)據(jù)皆從阿里巴巴公司公布的Alibaba Cluster Data V2018中抽取，測(cè)試結(jié)果如表2所示。

表2 不同規(guī)模服務(wù)器調(diào)度問(wèn)題上5種算法性能對(duì)比

表 2中顯示了不同規(guī)模（SSP1～SSP6）的調(diào)度問(wèn)題，其中SSP1～SSP3是規(guī)模與實(shí)例數(shù)較小的服務(wù)器調(diào)度問(wèn)題，SSP4～SSP6是規(guī)模與實(shí)例數(shù)較大的服務(wù)器調(diào)度問(wèn)題。其中，Nm代表算法調(diào)度結(jié)果使用的宿主機(jī)服務(wù)器數(shù)量，Score代表算法所得目標(biāo)分?jǐn)?shù)，CPU代表調(diào)度結(jié)果平均CPU使用率，目標(biāo)為50%。處理小規(guī)模問(wèn)題時(shí)，進(jìn)行比較的算法擁有相似的性能表現(xiàn)，但是OTECA、CT-DE與LS擁有較好的表現(xiàn)，目標(biāo)分?jǐn)?shù)的平均值相比其他算法優(yōu)秀 1%。處理較大規(guī)模問(wèn)題時(shí)，OTECA展現(xiàn)出比較突出的性能優(yōu)勢(shì)，目標(biāo)分?jǐn)?shù)的平均值比其他算法中最優(yōu)秀的LS優(yōu)秀3%。綜合上述2種情況，OTECA表現(xiàn)更好。

5.4 5種算法在ALISS數(shù)據(jù)集上性能對(duì)比

設(shè)置算法參數(shù)與5.3節(jié)相同，以實(shí)例在宿主機(jī)服務(wù)器中的轉(zhuǎn)移次數(shù)為橫坐標(biāo)，以分?jǐn)?shù)為縱坐標(biāo)，得到5種算法求解ALISS-1問(wèn)題如圖8所示。

圖8 5種算法求解ALISS-1問(wèn)題

圖8中最下方的虛線為該問(wèn)題的最優(yōu)解。在算法的初始階段，OTECA與C-MSDE的效率較高。隨著優(yōu)化的進(jìn)行，目標(biāo)值快速下降，GA、LS與CT-DE因優(yōu)化策略原因效率較低。在優(yōu)化的中后階段，OTECA表現(xiàn)出了較強(qiáng)的調(diào)度能力與精確性，通過(guò)解決子問(wèn)題，有目的地將組合不合理的機(jī)器挑選出來(lái)并進(jìn)行重新組合，該操作在效果上優(yōu)于基于隨機(jī)遷移的GA、LS、C-MSDE等其他算法，OTECA得到的調(diào)度結(jié)果能夠跳出局部最優(yōu)解。

算法對(duì)服務(wù)器組負(fù)載的均衡能力是衡量算法優(yōu)劣程度的重要指標(biāo)，本文對(duì)于ALISS-1的求解過(guò)程繪制機(jī)器負(fù)載量直方圖，如圖9所示。

圖9 機(jī)器CPU使用率標(biāo)準(zhǔn)差直方圖

由圖9可知，當(dāng)實(shí)例交換次數(shù)為0時(shí)，5種算法以相同的基礎(chǔ)進(jìn)行優(yōu)化。隨著實(shí)例交換次數(shù)的增加，5種優(yōu)化方法都能起到有效的負(fù)載均衡效果。當(dāng)實(shí)例的交換次數(shù)為20 000次時(shí)，OTECA的效果最為顯著，其對(duì)應(yīng)的機(jī)器 CPU使用率的標(biāo)準(zhǔn)差最小，相比初始值變化的幅度是GA的2倍。隨著優(yōu)化的繼續(xù)進(jìn)行，其他算法的標(biāo)準(zhǔn)差幾乎沒(méi)有發(fā)生改變，而OTECA的標(biāo)準(zhǔn)差有少量提升。這是因?yàn)殡S著交換的進(jìn)行，OTECA能夠有效地減少使用宿主機(jī)服務(wù)器的數(shù)量，從而提高了仍在工作的宿主機(jī)服務(wù)器使用率的標(biāo)準(zhǔn)差。5種算法求解ALISS數(shù)據(jù)集的結(jié)果對(duì)比如表3所示。

表3中評(píng)價(jià)了5種算法在數(shù)據(jù)集上的5個(gè)指標(biāo)，分別是目標(biāo)分?jǐn)?shù)（Score）、平均機(jī)器 CPU 使用率（CPU）、平均機(jī)器內(nèi)存使用率（DISK）、平均機(jī)器硬盤使用率（MEM）、機(jī)器 CPU使用率標(biāo)準(zhǔn)差（STD）。在 7個(gè)測(cè)試數(shù)據(jù)中，OTECA表現(xiàn)最佳，目標(biāo)分?jǐn)?shù)的平均分為 6 665.70，比第二優(yōu)秀的C-MSDE優(yōu)秀4%。

數(shù)據(jù)問(wèn)題的差異性會(huì)引起算法表現(xiàn)的差異，但是OTECA綜合性能占有一定優(yōu)勢(shì)。對(duì)于ALISS-3與ALISS-4這類實(shí)例粒度較?。▎蝹€(gè)實(shí)例占用的資源較?。┑膯?wèn)題，5種算法的表現(xiàn)相似。但是對(duì)于實(shí)例粒度較大的問(wèn)題，GA、LS、C-MSDE與CT-DE等算法表現(xiàn)稍遜于 OTECA，原因是不滿足約束的情況會(huì)降低上述算法的搜索效率。綜合考慮上述情況，OTECA具有更加優(yōu)秀的性能。

表3顯示，C-MSDE、CT-DE、GA與LS這4種算法在解決有相對(duì)嚴(yán)格約束的服務(wù)器調(diào)度問(wèn)題時(shí)沒(méi)有明顯優(yōu)勢(shì)，這是因?yàn)?種算法的解集更新具有隨機(jī)性，新生成的解很容易不滿足問(wèn)題的約束。因此，檢查新解是否滿足約束與丟棄不滿足約束的解花費(fèi)大量的運(yùn)算時(shí)間，從而大大降低了算法性能。OTECA不需要維護(hù)多個(gè)解的集合，也從不產(chǎn)生可能不滿足約束的解。OTECA只通過(guò)求解 MIP子問(wèn)題不斷地對(duì)解集進(jìn)行更新，因此擁有較高的效率與性能。

6 結(jié)束語(yǔ)

本文針對(duì)大規(guī)模云服務(wù)器調(diào)度問(wèn)題進(jìn)行研究。在對(duì)大規(guī)模云服務(wù)器調(diào)度問(wèn)題進(jìn)行MIP建模的基礎(chǔ)上，為了解決傳統(tǒng)方法很難及時(shí)地求解出最優(yōu)調(diào)度方案的問(wèn)題，本文提出了 OTECA。OTECA首先通過(guò)可行解生成算法求出可行解，然后通過(guò)在循環(huán)中不斷選取與解決MIP子問(wèn)題的方式優(yōu)化可行解，從而得到全局調(diào)度方案。結(jié)果表明，OTECA可以快速優(yōu)化大規(guī)模服務(wù)器調(diào)度方案，在測(cè)試數(shù)據(jù)集ALISS上較傳統(tǒng)的GA、LS、C-MSDE與CT-DE算法有較大的優(yōu)勢(shì)。在完成相同任務(wù)的情況下，OTECA使云計(jì)算中心的資源消耗減少4%以上。

表3 5種算法求解ALISS數(shù)據(jù)集的結(jié)果對(duì)比