古 丹，張 鷹，何先波

(西華師范大學(xué) 計(jì)算機(jī)學(xué)院，四川 南充 637009)

0 引言

云計(jì)算[1]作為一種大規(guī)模的異構(gòu)服務(wù)器集群，允許用戶通過(guò)互聯(lián)網(wǎng)以低廉的價(jià)格租用高性能的服務(wù).云端處理大量應(yīng)用的同時(shí)對(duì)云計(jì)算平臺(tái)任務(wù)調(diào)度的性能要求也急劇加升.一方面，大量終端用戶提交的任務(wù)具有動(dòng)態(tài)不確定性，任務(wù)到達(dá)時(shí)間及任務(wù)所需資源未知.另一方面異構(gòu)性在云環(huán)境中很常見(jiàn)，首先，用戶提交的大規(guī)模請(qǐng)求是異構(gòu)的，如計(jì)算密集型和I/O密集型.其次，云環(huán)境下部署的不同服務(wù)器的硬件配置是異構(gòu)的.動(dòng)態(tài)工作負(fù)載會(huì)導(dǎo)致同處虛擬機(jī)之間的資源競(jìng)爭(zhēng)，因此，如何實(shí)現(xiàn)大規(guī)模動(dòng)態(tài)異構(gòu)任務(wù)與虛擬機(jī)實(shí)例之間的映射，同時(shí)保證虛擬機(jī)實(shí)例之間的負(fù)載均衡，是學(xué)術(shù)界和研究的熱點(diǎn).

為了應(yīng)對(duì)上述挑戰(zhàn)，現(xiàn)有的方法大多側(cè)重于運(yùn)用排隊(duì)論[2]、控制論[3]等理論研究，將調(diào)度系統(tǒng)建立為數(shù)學(xué)模型，對(duì)作業(yè)調(diào)度方案進(jìn)行理論分析.但是，由于這些解決方案對(duì)時(shí)間和資源非常敏感，因此它們不適用于動(dòng)態(tài)負(fù)載.此外，啟發(fā)式調(diào)度算法[4]將任務(wù)分配視為NP問(wèn)題，在靜態(tài)環(huán)境下進(jìn)行任務(wù)調(diào)度，忽略了云環(huán)境的動(dòng)態(tài)性.

針對(duì)未知類(lèi)型的工作負(fù)載輸入，本文采用K-means聚類(lèi)方法[5]對(duì)任務(wù)進(jìn)行解析，識(shí)別其類(lèi)型.其次，將任務(wù)調(diào)度問(wèn)題定義為動(dòng)態(tài)優(yōu)化問(wèn)題，并利用DDPG(深度確定性策略梯度)[6]算法求解該問(wèn)題.最后，本文評(píng)估了在實(shí)際工作負(fù)載下所提出的調(diào)度器的效能，與現(xiàn)有的調(diào)度方法相比，該方法在任務(wù)響應(yīng)時(shí)間和VM實(shí)例間的負(fù)載均衡方面表現(xiàn)良好.

1 系統(tǒng)框架

一個(gè)常見(jiàn)的任務(wù)調(diào)度系統(tǒng)包括最終用戶、聚類(lèi)器、云服務(wù)提供者和應(yīng)用程序提供者.圖1所示為任務(wù)調(diào)度系統(tǒng)的框架.首先，應(yīng)用提供商從云服務(wù)公共平臺(tái)租用不同類(lèi)型的VM實(shí)例，形成自己的服務(wù)資源池.其次，聚類(lèi)器對(duì)提交的任務(wù)進(jìn)行識(shí)別、聚類(lèi)和處理，再將具有該類(lèi)型信息的任務(wù)提交給任務(wù)調(diào)度模塊.調(diào)度模塊由兩部分組成：監(jiān)視器和基于深度強(qiáng)化學(xué)習(xí)的任務(wù)調(diào)度器.監(jiān)視器負(fù)責(zé)獲取所有狀態(tài)信息，包括虛擬機(jī)狀態(tài)和任務(wù)狀態(tài).狀態(tài)信息作為輸入發(fā)送到任務(wù)調(diào)度器，并輸出任務(wù)分配策略.最后，調(diào)度系統(tǒng)根據(jù)該策略分配和執(zhí)行任務(wù).

圖1 任務(wù)調(diào)度框架圖

2 任務(wù)調(diào)度算法設(shè)計(jì)研究

2.1 任務(wù)負(fù)載聚類(lèi)

聚類(lèi)階段負(fù)責(zé)提取負(fù)載的類(lèi)型特征，并將其發(fā)送到基于深度強(qiáng)化學(xué)習(xí)的在線決策階段.本文使用K-means算法進(jìn)行聚類(lèi)分析，其流程如表1.

表1 任務(wù)聚類(lèi)偽代碼實(shí)現(xiàn)

2.2 異構(gòu)感知的云任務(wù)調(diào)度算法設(shè)計(jì)

2.2.1 狀態(tài)空間、動(dòng)作空間、獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)

2.2.1.1 狀態(tài)空間

當(dāng)前環(huán)境的狀態(tài)由任務(wù)狀態(tài)和VM實(shí)例狀態(tài)組成，更詳細(xì)地說(shuō)，任務(wù)屬性包括任務(wù)大小、任務(wù)所需CPU利用率和任務(wù)類(lèi)型.即任務(wù)狀態(tài)表示為si=(mii,cpuUtli,taskTypei).對(duì)于每個(gè)VM實(shí)例，其狀態(tài)由VM處理速率、任務(wù)等待時(shí)間和VM類(lèi)型組成，即sk=(mipsk,waitTk,vmTypek)，則狀態(tài)空間表示為：

i=1,…I;k=1,…，K.

(1)

2.2.1.2 動(dòng)作空間

當(dāng)用戶提交I個(gè)任務(wù)，動(dòng)作空間被表示為這I個(gè)任務(wù)分別分配的虛擬機(jī)的編號(hào)組成的一個(gè)向量.vmIdi表示為任務(wù)i分配的虛擬機(jī)編號(hào)，則動(dòng)作空間表示為：

actionik=[vmId1,vmId2,…,vmIdi,…,vmIdI]

vmIdi=1,…,I.

(2)

2.2.1.3 獎(jiǎng)勵(lì)函數(shù)

獎(jiǎng)勵(lì)可以判斷行動(dòng)策略的質(zhì)量，可以幫助智能體更新策略，以至未來(lái)做出更好的決策.在本文提出的模型中，獎(jiǎng)勵(lì)定義為任務(wù)平均響應(yīng)時(shí)間.

rewardIK=α×avgTik.

(3)

2.2.2 基于DDPG的云任務(wù)調(diào)度算法設(shè)計(jì)

DDPG在線決策階段使用動(dòng)作網(wǎng)絡(luò)和批評(píng)網(wǎng)絡(luò)，離線訓(xùn)練階段利用經(jīng)驗(yàn)回放和目標(biāo)網(wǎng)絡(luò)訓(xùn)練動(dòng)作網(wǎng)絡(luò)和批評(píng)網(wǎng)絡(luò).表2顯示了基于DDPG的任務(wù)調(diào)度算法.

表2 基于DDPG的任務(wù)調(diào)度偽代碼實(shí)現(xiàn)

2.2.3 異構(gòu)感知的動(dòng)作探索策略

原始的DDPG算法中的探索方式為OU過(guò)程.它在時(shí)序上具有很好的相關(guān)性，對(duì)于有慣性的系統(tǒng)探索效率較高.但在調(diào)度系統(tǒng)中，由于任務(wù)的爆炸性，這種探索方式不能很好地平衡智能體探索和重復(fù)利用的問(wèn)題；并且云環(huán)境中存在的異構(gòu)性使得任務(wù)處理的速度有所差別，所以在本文提出一種異構(gòu)感知?jiǎng)幼魈剿鞑呗?如表3為其偽代碼實(shí)現(xiàn).

表3 異構(gòu)感知?jiǎng)幼魈剿鞑呗詡未a實(shí)現(xiàn)

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)

所有實(shí)驗(yàn)均在pythorch1.4和jdk1.8的python3.6仿真環(huán)境下進(jìn)行.服務(wù)器配置3.4 GHz Intel Core i7處理器和16 GB內(nèi)存.為簡(jiǎn)化實(shí)驗(yàn)，應(yīng)用程序提供商從Iaas供應(yīng)商租用了20個(gè)VM實(shí)例，包括4種類(lèi)型，每種類(lèi)型的VM有5個(gè)實(shí)例.使用Alibaba-Cluster-trace-v2018作為工作負(fù)載數(shù)據(jù)，這是Alibaba集群使用情況跟蹤.它提供任務(wù)跟蹤，包括任務(wù)開(kāi)始時(shí)間、CPU利用率、內(nèi)存利用率和任務(wù)大小.本文使用了第五天的負(fù)載跟蹤數(shù)據(jù)，其中每分鐘提交的任務(wù)數(shù)平均為2 268個(gè)，最大為2 957個(gè).本文截取了最后500 000個(gè)跟蹤數(shù)據(jù)作為數(shù)據(jù)集.K-means中的K值設(shè)置為4.

調(diào)度算法中的網(wǎng)絡(luò)包括兩組演員-評(píng)論家網(wǎng)絡(luò)，即四個(gè)神經(jīng)網(wǎng)絡(luò)，分別是演員網(wǎng)絡(luò)、評(píng)論家網(wǎng)絡(luò)、目標(biāo)演員網(wǎng)絡(luò)和目標(biāo)評(píng)論家網(wǎng)絡(luò).每個(gè)網(wǎng)絡(luò)有四個(gè)完全連接的層.目標(biāo)網(wǎng)絡(luò)的更新方式為軟更新，軟更新參數(shù)設(shè)置為ω=0.01.經(jīng)驗(yàn)池的大小設(shè)置為D=1 000，最小的樣本大小Ω=32，并選擇Adam優(yōu)化器作為網(wǎng)絡(luò)優(yōu)化器.演員和評(píng)論家網(wǎng)絡(luò)的學(xué)習(xí)率分別為0.000 6和0.001.探索率的值ε初始化為0.95，遞減率為0.999，最小值為0.1.

為了評(píng)估本文提出的任務(wù)調(diào)度方案，比較了其他五種任務(wù)調(diào)度方法：隨機(jī)調(diào)度Random,循環(huán)調(diào)度RR,最早調(diào)度Earliest和基于DQN的任務(wù)調(diào)度.隨機(jī)調(diào)度方法將任務(wù)隨機(jī)分配給VM實(shí)例.循環(huán)調(diào)度方法將用戶請(qǐng)求依次輪詢分配給VM實(shí)例.最早的調(diào)度方法將用戶提交的任務(wù)分配給最早的空閑VM實(shí)例.

3.2 實(shí)驗(yàn)結(jié)果及分析

如圖2(a)所示，不同任務(wù)類(lèi)型相對(duì)于VM實(shí)例類(lèi)型的分配結(jié)果，平均匹配度為56.3%.如圖2(b)所示，與其他算法相比，除本文算法外，Earliest是最好的算法，但是CDDPG的平均任務(wù)響應(yīng)時(shí)間比earliest好22%.隨機(jī)調(diào)度算法的平均任務(wù)響應(yīng)時(shí)間最長(zhǎng)，CDDPG的平均任務(wù)響應(yīng)時(shí)間比隨機(jī)調(diào)度算法高72%.圖2(c)顯示了VM實(shí)例的CPU利用率標(biāo)準(zhǔn)差的比較.如圖所示，CDDPG在CPU利用率標(biāo)準(zhǔn)差方面比其他算法平均低10%.這表明我們提出的算法能夠更好地保證大規(guī)模動(dòng)態(tài)環(huán)境下的負(fù)載均衡.

圖2 實(shí)驗(yàn)結(jié)果圖

4 總結(jié)

本文針對(duì)云環(huán)境中任務(wù)的高不確定性和動(dòng)態(tài)波動(dòng)性和云環(huán)境中集群的異構(gòu)性，建立云任務(wù)調(diào)度框架，采用K-means聚類(lèi)方法來(lái)識(shí)別不同的工作負(fù)載類(lèi)型；提出基于異構(gòu)感知的改進(jìn)深度確定性的策略梯度方法實(shí)現(xiàn)任務(wù)調(diào)度.研究的不足在于調(diào)度目標(biāo)考慮的不夠全面，未來(lái)的研究中，會(huì)從單目標(biāo)和多目標(biāo)兩個(gè)方面深入剖析算法優(yōu)化的可行性.另外會(huì)從容錯(cuò)的角度，對(duì)提高調(diào)度的質(zhì)量加以分析研究.