高佳曼 徐歡樂

(1. 東莞理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 廣東東莞 523808；2. 香港中文大學(xué) 計(jì)算機(jī)學(xué)院， 香港 999077)

虛擬化是構(gòu)建云計(jì)算基礎(chǔ)架構(gòu)的重要技術(shù)之一[1]，虛擬化技術(shù)支持一臺物理機(jī)上綁定多臺虛擬機(jī)，每臺虛擬機(jī)上應(yīng)用程序的資源請求和負(fù)載更改類型均不相同，虛擬機(jī)之間獨(dú)立運(yùn)行且互不影響。多處理器系統(tǒng)在性能提高和節(jié)能計(jì)算領(lǐng)域的優(yōu)異表現(xiàn)，成為云計(jì)算虛擬化領(lǐng)域最受關(guān)注的話題。早期多處理器系統(tǒng)多數(shù)是UMA架構(gòu)的，但隨著系統(tǒng)規(guī)模的不斷增大，前端總線和內(nèi)存控制器容易產(chǎn)生系統(tǒng)的性能瓶頸。在此背景下，NUMA架構(gòu)應(yīng)運(yùn)而生且逐步被各大服務(wù)商采用。NUMA架構(gòu)[2]中每個(gè)節(jié)點(diǎn)都由一個(gè)物理CPU和它所有的本地內(nèi)存、I/O資源組成，具有遠(yuǎn)端內(nèi)存訪問特性，即每個(gè)節(jié)點(diǎn)不僅可以訪問本地內(nèi)存，還可以訪問整個(gè)系統(tǒng)的所有其他內(nèi)存，如圖1所示。

針對計(jì)算密集型任務(wù)時(shí)，虛擬機(jī)需要占用較多的CPU和內(nèi)存資源，但對網(wǎng)絡(luò)帶寬和IO的需求較少；針對IO密集型任務(wù)時(shí)，虛擬機(jī)主要的需求在于快速的IO響應(yīng)，CPU常處于低載狀態(tài)[3]。若NUMA架構(gòu)上的虛擬機(jī)系統(tǒng)在運(yùn)行過程中遇到“短時(shí)間內(nèi)大量的讀寫/計(jì)算操作請求時(shí)”就會產(chǎn)生高并發(fā)現(xiàn)象，導(dǎo)致虛擬機(jī)之間對共享資源的競爭，從而造成系統(tǒng)性能的下降。

圖1 NUMA架構(gòu)

在多核虛擬化平臺中，都是將片上的所有可共享資源作為一個(gè)整體，調(diào)度器對虛擬機(jī)進(jìn)行公平的共享資源分配，虛擬機(jī)之間可以獨(dú)立地運(yùn)行自己的應(yīng)用程序。實(shí)際系統(tǒng)運(yùn)行過程中，服務(wù)器可能存在大量的最終用戶，而應(yīng)用程序具有不同的資源需求。由于NUMA體系結(jié)構(gòu)具有可擴(kuò)展的帶寬性能特性，一直是主要的多處理器體系結(jié)構(gòu)[4]。然而，NUMA體系結(jié)構(gòu)卻引入了額外的開銷，如遠(yuǎn)程訪問延遲和內(nèi)存流量擁塞，嚴(yán)重影響應(yīng)用程序的性能。當(dāng)前VMM(Virtual Machine Monitor)虛擬機(jī)監(jiān)控器的vCPU調(diào)度器通常采用負(fù)載均衡機(jī)制進(jìn)行調(diào)度，但負(fù)載均衡機(jī)制不考慮應(yīng)用程序的訪存特征，只提高多核服務(wù)器下CPU資源的利用率，而造成其他資源的競爭與浪費(fèi)[5]。因此，如何讓虛擬機(jī)監(jiān)控器根據(jù)虛擬機(jī)之間的資源占用情況和系統(tǒng)的負(fù)載特點(diǎn)合理的為虛擬機(jī)進(jìn)行適當(dāng)?shù)恼{(diào)度，以減少共享資源競爭，從而提高系統(tǒng)的性能已經(jīng)成為了在實(shí)現(xiàn)調(diào)度程序時(shí)所考慮的重要因素。

1 相關(guān)工作

隨著云計(jì)算業(yè)務(wù)的不斷擴(kuò)大，用戶需求日益增多，資源調(diào)度面臨著更大的挑戰(zhàn)。在多核CPU結(jié)構(gòu)中，每個(gè)核心有其獨(dú)立的L1、L2緩存和共用的L3緩存[6]。如果一個(gè)進(jìn)程在核心間來回切換，各個(gè)核心的緩存命中率就會受到影響。相反如果不管如何調(diào)度，進(jìn)程都始終可以在一個(gè)核心上執(zhí)行，那么其數(shù)據(jù)的L1、L2 緩存的命中率可以顯著提高。為了讓一些進(jìn)程始終在一個(gè)核心上執(zhí)行，就需要進(jìn)行一定的綁核操作。綁定以后，調(diào)度器就會讓這個(gè)進(jìn)程/線程只在所綁定的核上運(yùn)行。

線程綁定的并行優(yōu)化程度和服務(wù)器架構(gòu)有密切關(guān)系，線程綁定的主要目的是提高線程訪問cpu的cache(緩存)命中率，從而提高程序的并行性能。NUMA模式是一種并行分布式存儲器訪問方式，處理器可以同時(shí)訪問多個(gè)不同的存儲器地址，因此NUMA架構(gòu)相比SMP架構(gòu)上使用線程綁定的方式更能提高并行效率。在NUMA系統(tǒng)架構(gòu)中，可以理解為虛擬機(jī)是某核心的一個(gè)進(jìn)程，而虛擬機(jī)的vCPU是核心進(jìn)程中的一種特殊的線程[7]。不同的vCPU是不同的線程，不同的線程是運(yùn)行在不同的CPU上的。通過處理器的關(guān)聯(lián)可以讓虛擬機(jī)的vCPU/內(nèi)存綁定到固定主機(jī)的物理核心上，也可以進(jìn)行動(dòng)態(tài)分配，綁核的vCPU/內(nèi)存只在所綁定的核上運(yùn)行，但并不代表該vCPU/內(nèi)存獨(dú)占這個(gè)核，其他vCPU/內(nèi)存也可以在這個(gè)核上工作。而虛擬機(jī)的初始化放置就是虛擬CPU/內(nèi)存與物理機(jī)核心的一種綁定關(guān)系，且虛擬機(jī)的初始化放置具有長期效應(yīng)。通過設(shè)置合理的初始化虛擬機(jī)放置，可以有效地減少NUMA系統(tǒng)中的遠(yuǎn)端內(nèi)存訪問和資源競爭。

1.1 共享資源競爭

在多核NUMA架構(gòu)服務(wù)器系統(tǒng)中，內(nèi)存訪問密集型線程對共享資源的競爭已經(jīng)嚴(yán)重影響了系統(tǒng)的性能。Blagodurov等人[8]進(jìn)行的相關(guān)研究指出，當(dāng)時(shí)最先進(jìn)的競爭管理算法(Compare And Swap，CAS)在NUMA系統(tǒng)架構(gòu)中并不能有效地發(fā)揮作用，甚至與默認(rèn)的操作系統(tǒng)調(diào)度程序相比，可能會降低性能。先前的研究也提出了一些方法來解決虛擬化系統(tǒng)中的NUMA開銷，但仍然存在一些限制。例如，文獻(xiàn)[9]通過采用vCPU的性能監(jiān)控?cái)?shù)據(jù)(PMU)信息進(jìn)行采樣，分析歸納vCPU特征并采取針對性調(diào)度的策略，可以減少系統(tǒng)中vCPU的遠(yuǎn)端內(nèi)存訪問和緩解共享資源競爭，提升訪存密集型應(yīng)用程序的性能。但是這種方法存在一定的誤差，影響最終的調(diào)度決策效率。Blagodurov等人[10]提出了一種線程調(diào)度機(jī)制DINO，該機(jī)制可以根據(jù)當(dāng)前內(nèi)存親和度和存在的競爭資源來調(diào)度線程或者遷移內(nèi)存，使線程CPU和內(nèi)存盡可能處在同一個(gè)節(jié)點(diǎn)上。通過對比不同綁定策略性能的差異，來分析不同因素造成的資源開銷；但是這樣的量化方式忽略了各因素之間的相互影響。文獻(xiàn)[11]認(rèn)為執(zhí)行時(shí)間最小化并不能代表最大化數(shù)據(jù)局部性。他們認(rèn)為將數(shù)據(jù)分配給遠(yuǎn)端的內(nèi)存可能更有利于避免內(nèi)存沖突，達(dá)到性能提升。因此，設(shè)計(jì)了一種新線程調(diào)度機(jī)制N-MASS，該機(jī)制充分地利用數(shù)據(jù)局部性特點(diǎn)，通過均衡LLC競爭，達(dá)到提高系統(tǒng)的整體性能目的。

Christina等人[12]提出了一個(gè)在線可擴(kuò)展的調(diào)度器Paragon。它利用系統(tǒng)先前的關(guān)于應(yīng)用程序的信息，使用協(xié)同過濾技術(shù)，通過識別與之前設(shè)計(jì)的應(yīng)用程序的相似性，快速準(zhǔn)確地對不同資源需求的工作進(jìn)行分類。Paragon能夠以最小化干擾和最大化服務(wù)器利用率的方式調(diào)度應(yīng)用程序， 但比較依賴于先前的應(yīng)用程序信息。此后，Shuang Chen等人[13]提出一個(gè)不需要應(yīng)用的先驗(yàn)知識，能夠利用細(xì)粒度的檢測與資源劃分動(dòng)態(tài)地調(diào)整系統(tǒng)應(yīng)用間的共享資源分配的控制器Parties。它由一個(gè)檢測組件和一個(gè)資源分配組件組成，前者檢測每個(gè)應(yīng)用的尾延遲、內(nèi)存容量、網(wǎng)絡(luò)帶寬使用量，后者使用檢測結(jié)果來決定恰當(dāng)?shù)馁Y源分配，并強(qiáng)制對他們隔離。它能夠讓多個(gè)延遲敏感的應(yīng)用在不違反QoS前提下共享一個(gè)物理主機(jī)的資源管理器，大幅提升吞吐率。此外，Parties適用于動(dòng)態(tài)變化的負(fù)載，并可利用資源替換性來快速實(shí)現(xiàn)收斂。

文獻(xiàn)[14]針對最新的NUMA系統(tǒng)，通過實(shí)驗(yàn)說明影響系統(tǒng)性能的最主要因素是內(nèi)存訪問控制器和互連總線競爭，提出了一種解決算法，將多線程程序?qū)?nèi)存的訪問均勻地分配在所有的 NUMA 節(jié)點(diǎn)上，避免多個(gè)內(nèi)存訪問請求集中在單個(gè)NUMA節(jié)點(diǎn)上，能夠減少系統(tǒng)競爭。文獻(xiàn)[15]提出了一種在非一致性內(nèi)存訪問(NUMA)多socket多核平臺上共定位并行應(yīng)用的協(xié)同調(diào)度技術(shù)。該技術(shù)為并行應(yīng)用程序分配核心資源，使內(nèi)存控制器和CPU核心的利用率最大化。文獻(xiàn)[16]提出了虛擬化環(huán)境下多核片上共享資源管理技術(shù)，主要包括LLC的劃分控制和訪存帶寬控制，并在此基礎(chǔ)上提出了二者的動(dòng)態(tài)調(diào)節(jié)優(yōu)化技術(shù)和虛擬機(jī)分組優(yōu)化技術(shù)，在系統(tǒng)整體負(fù)載較大的情況下能夠保證其響應(yīng)時(shí)間，提高系統(tǒng)的實(shí)時(shí)性。文獻(xiàn)[17-18]研究了資源競爭引起的NUMA架構(gòu)性能下降問題，文獻(xiàn)[18]雖然緩解了內(nèi)存訪問控制器的競爭，但是效果有限。

1.2 虛擬機(jī)的放置

虛擬機(jī)的放置[19]是指在如何根據(jù)虛擬機(jī)對各類資源的請求如CPU、內(nèi)存、帶寬等，將若干虛擬機(jī)合理放置到合適的物理機(jī)上，同時(shí)滿足物理機(jī)的資源約束條件以及平臺要求的高資源利用率和低能源消耗等目標(biāo)。虛擬機(jī)放置問題近年來已逐漸成為研究的重點(diǎn)，現(xiàn)有的研究通常會考慮以下兩種類型的約束類型[20]。一是虛擬機(jī)與物理機(jī)的映射關(guān)系，每個(gè)虛擬機(jī)只能放置到一臺物理主機(jī)上，但每臺物理機(jī)上可以有多個(gè)虛擬機(jī)；二是一臺物理機(jī)上的所有虛擬機(jī)的資源需求量之和不能超過物理機(jī)的資源容量。

研究者一般根據(jù)目標(biāo)的數(shù)量，使用不同的算法來解決虛擬機(jī)的放置問題。由于虛擬機(jī)放置問題也可以看作是一種特殊的裝箱問題，啟發(fā)式算法如首次適應(yīng)下降算法(First Fit Decreasing，F(xiàn)FD)或最佳適應(yīng)下降算法(Best Fit Decreasing，BFD)是求解裝箱問題的常用算法[21]，但當(dāng)主機(jī)數(shù)量極其龐大時(shí)，啟發(fā)式算法不能在有效的時(shí)間內(nèi)得到較好的放置方案。此外，元啟發(fā)式算法和混合啟發(fā)式算法通常用于解決虛擬機(jī)放置的多目標(biāo)問題。例如，文獻(xiàn)[22]針對最小化能源消耗和最大化資利用率兩個(gè)目標(biāo)，應(yīng)用多目標(biāo)蟻群算法來解決虛擬機(jī)放置問題。文獻(xiàn)[23]用局部優(yōu)化程序擴(kuò)展了遺傳算法，提高了原遺傳算法的收斂性。LR(Logistic Regression，邏輯回歸)算法[24]通過建立擬合模型預(yù)測曲線趨勢，能夠大幅度減少系統(tǒng)功耗。但以上兩種算法在計(jì)算密集型任務(wù)虛擬化環(huán)境中，完成時(shí)間不可估量。雖然MGA(Micro-Genetic Algorithm，微遺傳)算法[25]能夠在增加服務(wù)商利潤的同時(shí)降低系統(tǒng)能耗，但當(dāng)該算法陷入局部最優(yōu)時(shí)不能建立有效反饋。

在NUMA架構(gòu)中，由于虛擬機(jī)的初始放置位置產(chǎn)生的資源競爭不可忽視。如果虛擬機(jī)初始位置放置不當(dāng)，就會造成大量的遠(yuǎn)端內(nèi)存訪問，使得帶寬性能會至少下降57%，而內(nèi)存流量擁塞可能會將內(nèi)存訪問延遲增加到5倍。此外，由于虛擬化層引入的語義差距，運(yùn)行在虛擬機(jī)內(nèi)的應(yīng)用程序?qū)Φ讓拥腘UMA特性并不了解。如果沒有NUMA感知的虛擬機(jī)放置資源管理，就無法保證應(yīng)用程序的性能。因此，在NUMA架構(gòu)下如何獲得更健壯的虛擬機(jī)放置方案也受到了云提供商越來越多的關(guān)注。

現(xiàn)代多核系統(tǒng)具有復(fù)雜的共享資源層次結(jié)構(gòu)，不同的虛擬cpu與硬件的映射關(guān)系對系統(tǒng)性能影響有很大的差異。文獻(xiàn)[26]對NUMA架構(gòu)下虛擬機(jī)位置放置問題進(jìn)行了充分的討論：需要分配給容器的硬件資源決定了容器的性能以及消耗的能量。一般來說，資源如何分配受到兩方面決策影響。其一，用戶決定容器需要多少內(nèi)核、內(nèi)存和其他資源；其二，系統(tǒng)軟件在啟動(dòng)容器時(shí)，決定如何將容器的虛擬核心映射到物理核心上。當(dāng)所有虛擬核心集中到單個(gè)NUMA節(jié)點(diǎn)中時(shí)，它們會有更多的資源共享，一個(gè)容器的最佳性能位置很難預(yù)測。如果目標(biāo)不僅是選擇性能最好的位置，而且是在使用節(jié)點(diǎn)的數(shù)量和性能之間實(shí)現(xiàn)平衡，那么問題就會變得更加復(fù)雜。作者將虛擬機(jī)放置問題轉(zhuǎn)化為調(diào)度問題，單調(diào)度問題即調(diào)度只有一種硬件資源，或一組綁定的會影響vCPU放置性能的硬件資源。多調(diào)度問題即多種資源，轉(zhuǎn)化為調(diào)度問題的主要目的是在給定vCPU放置時(shí)提供一個(gè)數(shù)值分?jǐn)?shù)，該分?jǐn)?shù)表示特定資源的靜態(tài)利用率，這意味著它只依賴于vCPU的位置，而不是動(dòng)態(tài)的工作負(fù)載。分?jǐn)?shù)越高，則表示給定的虛擬機(jī)放置效果越好。

基于上述分析，將虛擬機(jī)放置問題轉(zhuǎn)化為調(diào)度問題，提出了一個(gè)虛擬機(jī)放置的模型，并設(shè)計(jì)了一種基于強(qiáng)化學(xué)習(xí)的調(diào)度算法。該方法根據(jù)虛擬機(jī)的任務(wù)類型進(jìn)行資源調(diào)度，將虛擬機(jī)的放置過程描述為隨機(jī)采樣的過程，并根據(jù)系統(tǒng)的運(yùn)行狀態(tài)引入近端策略優(yōu)化[27](Proximal Policy Optimization，PPO)和交叉熵[28](Cross Entropy，CE)強(qiáng)化學(xué)習(xí)機(jī)制。智能體通過與虛擬機(jī)資源環(huán)境的不斷交互來分析出虛擬機(jī)與物理機(jī)之間的綁定關(guān)系對系統(tǒng)性能的影響，進(jìn)而選擇出對系統(tǒng)性能影響最小的解決方案，達(dá)到優(yōu)化目的。

2 問題描述

根據(jù)文獻(xiàn)[29]，面向NUMA架構(gòu)的虛擬化系統(tǒng)主要包括以下四個(gè)方面的資源競爭：一是內(nèi)存的競爭，如果兩個(gè)節(jié)點(diǎn)同時(shí)訪問相同的數(shù)據(jù)存儲器，那么一個(gè)節(jié)點(diǎn)必須等到另一個(gè)節(jié)點(diǎn)完成訪問才能進(jìn)行訪問，這將降低性能；二是當(dāng)多個(gè)vCPU共享一個(gè)緩存空間時(shí)，由于緩存的大小有限，容易產(chǎn)生一個(gè)vCPU緩存的數(shù)據(jù)被另外一個(gè)vCPU的數(shù)據(jù)替代的情況，稱為緩存競爭；三是所有vCPU對LLC的競爭，且LLC競爭是不可避免的；四是對互聯(lián)總線的競爭，當(dāng)多個(gè)核心需要訪問其他節(jié)點(diǎn)上的內(nèi)存時(shí)，就會造成多個(gè)核心對互聯(lián)總線的競爭。當(dāng)競爭已經(jīng)存在，數(shù)據(jù)訪問時(shí)間將會達(dá)到正常數(shù)據(jù)訪問的5倍以上[30]。

2.1 數(shù)學(xué)模型

虛擬機(jī)的放置是計(jì)算機(jī)領(lǐng)域的一個(gè)關(guān)鍵課題，目前研究者對負(fù)載均衡、資源利用率和能耗等方面的優(yōu)化算法[31-33]都有所研究。離線放置表示在虛擬機(jī)資源請求量及物理服務(wù)器資源均確定的情況下，考慮不同優(yōu)化目標(biāo)的虛擬機(jī)放置。文中主要考慮離線放置，問題可以表示為如圖2，用數(shù)學(xué)語言描述：將m個(gè)具有不同資源請求的虛擬機(jī)分配到n個(gè)物理機(jī)中合適的物理節(jié)點(diǎn)上[34]，以實(shí)現(xiàn)包括最小化能源消耗和最大化資源利用率、負(fù)載平衡和魯棒性的目標(biāo)。每臺物理計(jì)算機(jī)都提供多種類型的資源，如CPU、內(nèi)存和網(wǎng)絡(luò)帶寬。物理機(jī)、虛擬機(jī)及其之間的綁定關(guān)系，以及放置方案可以描述如圖2。

圖2 虛擬機(jī)放置問題示意圖

a)物理機(jī)

在NUMA系統(tǒng)中，物理機(jī)可以描述為NUMA系統(tǒng)上的某個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上都有自己的內(nèi)部CPU、總線、內(nèi)存和內(nèi)存控制器等。假設(shè)本系統(tǒng)中節(jié)點(diǎn)集合表示為，其中N表示可供選擇的節(jié)點(diǎn)數(shù)量。

b)虛擬機(jī)

虛擬機(jī)表示為集合VM={VM1,VM2,…,VMM}，其中M為需要放置的虛擬機(jī)的個(gè)數(shù)。每個(gè)虛擬機(jī)的資源需求量不盡相同，根據(jù)任務(wù)類型，又分為IO密集型、CPU密集型等。

c)虛擬機(jī)與物理機(jī)的綁定關(guān)系

物理機(jī)與虛擬機(jī)之間的綁定關(guān)系表示為一個(gè)N×M的矩陣A。

矩陣A為0-1矩陣，對于每一個(gè)虛擬機(jī)VMj都有∑i=1naij=1，即一臺虛擬機(jī)只能分配到一個(gè)物理節(jié)點(diǎn)上。若aij=1 則表示第j臺虛擬機(jī)要綁定到第i個(gè)物理節(jié)點(diǎn)上。

d)虛擬機(jī)放置方案表示

同樣地，其他虛擬機(jī)在NUMA服務(wù)器上的放置概率由其對應(yīng)的其他N×M個(gè)參數(shù)決定。各虛擬機(jī)依次選擇放置節(jié)點(diǎn)位置，當(dāng)M個(gè)虛擬機(jī)全部選擇放置完后，得到一次放置方案，將其表示為d={Choose1,Choose2,…,Choosem,…,ChooseM}，Choosem值為{0，1，…，N-1}其中一個(gè)，它表示當(dāng)前虛擬機(jī)m選擇放置NUMA架構(gòu)的哪個(gè)節(jié)點(diǎn)操作。舉例說明，如d={2,4,…,2}，則表示第一臺和最后一臺虛擬機(jī)選擇放置到節(jié)點(diǎn)2，第二臺虛擬機(jī)選擇放置到節(jié)點(diǎn)4，以此類推。

2.2 問題目標(biāo)

在面向NUMA架構(gòu)的虛擬化系統(tǒng)中，若初始的虛擬機(jī)放置不當(dāng)，容易造成各虛擬機(jī)之間的資源競爭，而這種資源競爭也將導(dǎo)致虛擬機(jī)的不斷遷移，最終造成系統(tǒng)的整體性能下降。在本論文中，我們的最終目標(biāo)是減少虛擬化的NUMA系統(tǒng)的資源競爭，保證系統(tǒng)性能提高。

IPS(Instruction Per Second，處理器每秒平均完成的指令條數(shù))是衡量CPU性能的重要指標(biāo)之一，IPS越大，則反映出CPU的性能越好[35]。因此我們將測試得到的IPS作為虛擬機(jī)放置算法的優(yōu)化目標(biāo)，按照給定放置策略方案di訓(xùn)練模型，將系統(tǒng)執(zhí)行該策略di時(shí)對應(yīng)的IPS用T(d)表示。T(d)越大，則側(cè)面反映當(dāng)前系統(tǒng)的資源競爭越小，也就表示當(dāng)前的放置策略越好。此類設(shè)備放置問題用數(shù)學(xué)等式可以表述為：

其中A表示所有可能擺放位置的集合。

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

虛擬機(jī)資源調(diào)度是一個(gè)復(fù)雜的NP難問題，在進(jìn)行算法設(shè)計(jì)時(shí)如果使用太多參數(shù)，則會給系統(tǒng)帶來大量的計(jì)算開銷，尤其是AC(Actor-Critic)算法[36]。AC模型包含兩個(gè)神經(jīng)網(wǎng)絡(luò)，都是在連續(xù)狀態(tài)中更新參數(shù)，參數(shù)更新前后存在著一定的關(guān)聯(lián)性，致使神經(jīng)網(wǎng)絡(luò)不能全局看待問題，甚至學(xué)不到好結(jié)果。由于云計(jì)算環(huán)境負(fù)載波動(dòng)性和資源的不確定性，而基于策略的算法需要同種策略進(jìn)行迭代訓(xùn)練，所以這種方法不適宜云資源調(diào)度。因?yàn)楫?dāng)步長過大時(shí)，學(xué)出來的 Policy 震動(dòng)幅度較大，會導(dǎo)致算法不能收斂；當(dāng)步長太小時(shí)，完成訓(xùn)練的時(shí)間又超出了可等待的范圍。PPO 根據(jù)新舊策略的比值來限制新策略的更新幅度，避免了發(fā)生新策略突然嚴(yán)重偏離最優(yōu)解或者陷入局部最優(yōu)的問題，能夠達(dá)到不斷更新策略的目的。交叉熵優(yōu)化算法可以非常快速地得到最優(yōu)化結(jié)果，縮短整體求解時(shí)間。因此，采用了PPO和交叉熵優(yōu)點(diǎn)結(jié)合的算法來求解模型。

Post算法的框架如圖3所示，包括采集樣本算法、強(qiáng)化學(xué)習(xí)模塊等及部分。采集樣本算法：根據(jù)概率參數(shù)矩陣選擇放置策略；強(qiáng)化學(xué)習(xí)模塊：利用近端策略優(yōu)化算法(PPO)和交叉熵最小化算法交替地不斷更新采集樣本算法的參數(shù)矩陣。

3.1 采集樣本

假設(shè)對于第m臺虛擬機(jī)的放置，使用參數(shù)表示選擇第j個(gè)設(shè)備節(jié)點(diǎn)的概率。虛擬機(jī)與節(jié)點(diǎn)之間的選擇映射關(guān)系表示為一個(gè)D×M的概率矩陣B。

(1)

首先使用softmax函數(shù)對所有設(shè)備的參數(shù)進(jìn)行規(guī)范化，以獲得放置的概率分布。為第m臺虛擬機(jī)選擇放置到第j個(gè)設(shè)備節(jié)點(diǎn)的概率由下式給出：

(2)

3.2 強(qiáng)化學(xué)習(xí)模塊

強(qiáng)化學(xué)習(xí)[37]是機(jī)器學(xué)習(xí)領(lǐng)域的主要算法之一，智能體(Agent)的目的就是爭取在與環(huán)境的交互中獲得盡可能多的累計(jì)獎(jiǎng)勵(lì)。虛擬機(jī)放置問題是通過使用調(diào)度模塊不斷地調(diào)整虛擬機(jī)與物理節(jié)點(diǎn)的綁定關(guān)系，來達(dá)到最佳的放置策略。強(qiáng)化學(xué)習(xí)是求解優(yōu)化問題的有效工具，近年來強(qiáng)化學(xué)習(xí)在處理問題的能力和規(guī)模上面都得到了顯著的提升。對于自適應(yīng)調(diào)度而言，強(qiáng)化學(xué)習(xí)的隨機(jī)性質(zhì)與隨機(jī)虛擬機(jī)綁定的目標(biāo)是一致的，因此強(qiáng)化學(xué)習(xí)這種動(dòng)態(tài)規(guī)劃的思想比較適合應(yīng)用到虛擬機(jī)的放置算法中[38]。

在文中，采用近端策略優(yōu)化算法和交叉熵優(yōu)化算法相結(jié)合的強(qiáng)化學(xué)習(xí)優(yōu)化算法。強(qiáng)化學(xué)習(xí)過程中，模型概率矩陣采用策略梯度上升法不斷更新參數(shù)，使得放置策略對應(yīng)的T(d)不斷增加。假設(shè)每臺虛擬機(jī)放置到哪個(gè)設(shè)備節(jié)點(diǎn)是相互獨(dú)立的，則虛擬機(jī)放置位置分布即聯(lián)合分布f(du)，可以表示為：

(3)

為了獲得聯(lián)合分布概率最接近1的放置分布，從隨機(jī)生成的參數(shù)值開始迭代更新參數(shù)，直到最終收斂。最初使用均值參數(shù)u(0)，通過不斷迭代產(chǎn)生的目標(biāo)分布(參數(shù)為(u(1),u(2),…)逐漸改善聯(lián)合分布。第t次迭代的目標(biāo)分布定義為以下條件分布：

f(du(t+1))=f(du(t),T(d)≥γt)，

(4)

其中γt是常數(shù)，且γ0≤γ1≤γ2≤…≤γ*。

根據(jù)條件概率的定義，等式(4)可以轉(zhuǎn)化為式(5)：

(5)

其中I{·}是指標(biāo)函數(shù)，當(dāng)條件成立時(shí)等于1，否則等于0。等式(5)表示f(du(t))中好位置的概率歸一化。通過歸一化，將舊分布f(du(t))更新為目標(biāo)分布f(du(t+1))。隨著t在迭代中不斷增大，從樣本數(shù)據(jù)集中選擇出好放置策略的可能性不斷提高。根據(jù)這樣的直覺，可以通過最小化舊分布和目標(biāo)分布之間的隨機(jī)距離(KL-散度)來調(diào)整參數(shù)u(t)，最小化KL散度表示為等式(6)。

f(du(t))logf(du(t))，

(6)

(7)

(8)

其中，目標(biāo)分布f(du(t+1))由等式(5)給出。等式(6)的第一項(xiàng)關(guān)于u(t)是常數(shù)，因此等式(6)可以等效為等式(7)，進(jìn)一步將其轉(zhuǎn)化為等價(jià)的期望形式等式(8)。

1)交叉熵優(yōu)化算法

交叉熵方法主要是用來衡量兩個(gè)概率分布之間的差異性信息，用來優(yōu)化和重要性采樣，交叉熵并不對環(huán)境進(jìn)行任何的建模，只需要簡單地告訴智能體每步應(yīng)該采取的策略。一般的損失函數(shù)在進(jìn)行梯度下降計(jì)算時(shí)可能會由于梯度的彌散出現(xiàn)學(xué)習(xí)率下降的問題，而交叉熵作為損失函數(shù)可以避免這種影響。為了解決上述等式(8)的最小化問題，我們將期望值替換為N個(gè)樣本的平均值，并將期望值最大化樣本平均值表示如式(9)。

(9)

其中的d(n)是第n個(gè)采樣樣本。在N個(gè)采樣樣本中，滿足條件的子集由常數(shù)γt確定。每次選取前ρ*N個(gè)優(yōu)秀的放置位置(ρ∈(0，1))，將γt設(shè)置為所有采樣樣本中第ρ*N個(gè)最大的值，使用交叉熵方法求解式(9)，式(9)是一個(gè)凸優(yōu)化問題[39]，可以采用基于梯度的方法求解，以實(shí)現(xiàn)全局最優(yōu)解。此外，對于softmax分布，文獻(xiàn)[40]針對問題(9)導(dǎo)出了以下封閉解。

(10)

其中p表示好的位置，P=ρN是好的位置的總數(shù)。

在有效的展示位置中，重新計(jì)算分配給第m個(gè)設(shè)備的第j個(gè)節(jié)點(diǎn)的概率，并將其作為給定新參數(shù)的放置概率。在每次交叉熵最小化之后，選擇某種放置的概率可能為零，這不利于探索更多潛在的位置。為了更好的探索，將分布與均勻分布混合在一起，以epsilon(e.g. 0.1)的概率從所有可用設(shè)備中均勻選擇一個(gè)設(shè)備，而以1-epsilon(e.g. 0.9)的概率根據(jù)交叉熵最小化后的概率分布選擇設(shè)備。即如式(11)。

f(du(t+1))=(1-epsilon)f(du(t+1))+

(11)

其中C為與概率矩陣B同形狀的全1矩陣。隨著智能體的不斷訓(xùn)練，T(d)的值會逐漸上升，最終達(dá)到滿意為止。

2)近端策略優(yōu)化算法

在強(qiáng)化學(xué)習(xí)中，交叉熵最小化是一種批處理學(xué)習(xí)算法，它在放置了大量(N個(gè)，可能是數(shù)百個(gè))放置樣本后更新參數(shù)，這種批處理學(xué)習(xí)算法缺乏增量參數(shù)的改進(jìn)。PPO算法是一種基于梯度優(yōu)化的、面向連續(xù)或離散動(dòng)作空間的在線決策深度強(qiáng)化學(xué)習(xí)算法，在計(jì)算梯度時(shí)確保與舊策略有相對較小的偏差。因此，整合了交叉熵最小化和近端策略優(yōu)化算法的優(yōu)點(diǎn)，每次增加少量K個(gè)樣本，以實(shí)現(xiàn)算法的學(xué)習(xí)加速。因此，第t次迭代的近端策略優(yōu)化的目標(biāo)可表示如式(12)。

(12)

其中b是所有采樣樣本運(yùn)行指令數(shù)的平均值，而DKL(·) 是新舊分布之間的KL散度。T(d(n)-b)表示獎(jiǎng)勵(lì)信號，如果其訓(xùn)練時(shí)間大于平均值，則為正，否則為負(fù)。Post算法在算法1中總結(jié)。

算法 1：交叉熵和近端策略優(yōu)化結(jié)合算法(Post算法)

輸入：樣本和概率矩陣。

輸出：更新后的概率矩陣。

a) 生成全1的概率矩陣并進(jìn)行softmax為u(0)；初始化 t=0

b) for n=1,2,…,L do

c) 放置樣本d(n)～f(du(t))；

d) 根據(jù)樣d(n)本搜索對應(yīng)的IPS值并記錄；

e) if n%K == 0 and n%N ≠ 0 then

f) 采用近端策略優(yōu)化算法(即等式11)更新概率矩陣；

g) 對概率矩陣進(jìn)行softmax歸一化；

h) t=t+1

i) end if

j) if n%N == 0 then

k) 采用交叉熵最小化使用等式(10)實(shí)現(xiàn)優(yōu)化；

l) t=t+1

n) end if

o) end for

每次從樣本中連續(xù)采樣放置策略并評估其對應(yīng)IPS。對于每K個(gè)采樣位置，采用近端策略優(yōu)化執(zhí)行隨機(jī)梯度上升步驟，從而逐步改善策略。對于每N個(gè)采樣位置(N比K大幾倍或幾十倍)，采用等式(10)更新參數(shù)來實(shí)現(xiàn)整個(gè)正向的策略改進(jìn)。

4 仿真實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)配置

在本論文中，以6臺虛擬機(jī)、3個(gè)節(jié)點(diǎn)的NUMA服務(wù)器場景為例。為了驗(yàn)證算法的有效性，在實(shí)驗(yàn)之前，采用不同類別虛擬機(jī)和物理機(jī)配置，對虛擬機(jī)放置在NUMA節(jié)點(diǎn)上對應(yīng)的IPS進(jìn)行測試，并進(jìn)行記錄，制作成虛擬機(jī)放置任務(wù)的數(shù)據(jù)集。

在基于強(qiáng)化學(xué)習(xí)的虛擬機(jī)放置算法測試過程中，相關(guān)參數(shù)設(shè)置為：學(xué)習(xí)率epsilon為0.1，K設(shè)置為10，N設(shè)置為20，參數(shù)更新100次即L=100。實(shí)驗(yàn)性能評價(jià)指標(biāo)如下：1)迭代求解的平均值和方差；2)算法的準(zhǔn)確率；3)算法迭代時(shí)間及CPU與內(nèi)存利用率等。對于上述平均值和準(zhǔn)確率性能指標(biāo)，實(shí)驗(yàn)結(jié)果的數(shù)值越大，表明基于NUMA架構(gòu)的數(shù)據(jù)中心的系統(tǒng)整體性能越好。相反，迭代時(shí)間及CPU與內(nèi)存利用率及方差的數(shù)值越小越好。

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

在相同配置下對各算法進(jìn)行平均采樣值分析、采樣值方差分析、準(zhǔn)確率分析以及CPU和內(nèi)存利用率以及運(yùn)行時(shí)間進(jìn)行綜合分析，最后得到算法對虛擬機(jī)放置樣本集的實(shí)驗(yàn)結(jié)果。首先對Post算法進(jìn)行算法的迭代求解，測試結(jié)果如圖4所示。

圖4 IPS隨迭代變化

從圖4可知，更新5次左右的訓(xùn)練迭代后，虛擬機(jī)放置對應(yīng)策略處理指令數(shù)的數(shù)量明顯增加，在10次迭代后已經(jīng)達(dá)到了比較好的效果。隨著迭代次數(shù)的增加，處理指令數(shù)量雖有波動(dòng)但逐漸收斂，說明提出的模型對一定資源約束條件下的虛擬機(jī)放置問題能夠有比較好的訓(xùn)練結(jié)果。

1)采樣值分析。將Post算法與交叉熵算法(CE)、近端策略優(yōu)化算法(PPO)和策略梯度算法(PG)在采樣平均值和采樣值方差上進(jìn)行比較。在模擬實(shí)驗(yàn)中，對于每一個(gè)放置策略均對應(yīng)一個(gè)性能指標(biāo)。由于第一步涉及初始放置，因此采用十個(gè)樣本的平均性能指標(biāo)來衡量算法對性能的影響。在對樣本集進(jìn)行了十次采樣訓(xùn)練之后得到圖5和圖6所示的對比圖。

圖5 隨迭代變化的平均采樣值

圖6 十組采樣數(shù)據(jù)方差

基于NUMA系統(tǒng)的數(shù)據(jù)中心中，根據(jù)圖5采樣平均值的對比結(jié)果可以看出Post在每次訓(xùn)練均可比其他三種算法取得較好的成績。通過圖6可以看出，僅使用交叉熵算法或僅使用PPO算法的方差較大，Post和策略梯度算法方差相近且較小。綜合圖5和圖6的結(jié)果，Post算法相比其他算法表現(xiàn)出較好的提升系統(tǒng)性能的能力且具有相對穩(wěn)定性。

2)準(zhǔn)確率分析。經(jīng)過重復(fù)多次測試4種算法均可在相對較短的時(shí)間內(nèi)得到最優(yōu)解。為了驗(yàn)證算法準(zhǔn)確率，將算法迭代前5次能求得的最優(yōu)解進(jìn)行了統(tǒng)計(jì)對比，結(jié)果如圖7所示。

圖7 前五次迭代各算法能求得的最優(yōu)解

實(shí)驗(yàn)結(jié)果表明，在實(shí)驗(yàn)場景下，其他三種算法雖然能在5次迭代內(nèi)找到虛擬機(jī)放置的最佳位置，但并不是每次都能在5次迭代內(nèi)找到最優(yōu)解，而Post算法十次測試均能在5次迭代內(nèi)找到最優(yōu)解，本算法準(zhǔn)確率較高。為了進(jìn)一步加強(qiáng)算法測試的準(zhǔn)確性，對每個(gè)算法都進(jìn)行了100次測試，實(shí)驗(yàn)結(jié)果如表1所示。

表1 準(zhǔn)確率

其中本文算法Post有91次都能在5次迭代中找到最佳結(jié)果，比其他三種算法準(zhǔn)確率提升近40%。

3)綜合分析。由于算法時(shí)間復(fù)雜度和空間復(fù)雜度的不同，不同的算法迭代時(shí)間往往不同，對比了四種算法在同種配置下的迭代運(yùn)行時(shí)間，得到如圖8所示結(jié)果。

圖8 隨迭代所需時(shí)間變化

根據(jù)圖8實(shí)驗(yàn)結(jié)果可知，在僅使用PPO算法求解時(shí)，所需的時(shí)間開銷最大。Post算法時(shí)結(jié)合了PPO算法和交叉熵算法的優(yōu)點(diǎn)，在時(shí)間開銷方面得到了較大的提升。CE算法和PG算法隨著迭代次數(shù)的增加運(yùn)行時(shí)間呈現(xiàn)線性增長。在本次實(shí)驗(yàn)中，只對樣本集進(jìn)行了100次迭代，根據(jù)圖8所示各算法的運(yùn)行規(guī)律，可以預(yù)測當(dāng)樣本量較大時(shí)，Post算法所需時(shí)間最少。在算法迭代過程中，我們同時(shí)獲取了各算法每次迭代過程的內(nèi)存和CPU使用率，結(jié)果如表2所示。

表2 算法內(nèi)存和CPU使用率 %

從表2中可知，在系統(tǒng)配置相同情況下，各算法CPU和內(nèi)存利用率相差不大，則說明Post算法在保證算法準(zhǔn)確率，節(jié)約時(shí)間的同時(shí)能夠保證算法不對系統(tǒng)產(chǎn)生其他干擾。

綜合以上所有實(shí)驗(yàn)結(jié)果，認(rèn)為本文算法能提升現(xiàn)有的NUMA虛擬機(jī)系統(tǒng)的性能，可為現(xiàn)有互聯(lián)網(wǎng)基礎(chǔ)服務(wù)提供更好的技術(shù)支撐。

5 結(jié)語

虛擬化技術(shù)作為云計(jì)算的基礎(chǔ)，對云計(jì)算的發(fā)展有著重要的作用，優(yōu)化虛擬機(jī)的放置策略的性能的研究對現(xiàn)代云計(jì)算行業(yè)具有重要的意義。文中將設(shè)備放置表示為高維的softmax概率分布，將尋找最佳位置的虛擬機(jī)放置問題轉(zhuǎn)化為查找最大值的問題。以強(qiáng)化學(xué)習(xí)為基礎(chǔ)，提出了一種算法來解決NUMA架構(gòu)下虛擬機(jī)放置的資源競爭問題，在理論上保證了最佳的效率。主要包括以下兩個(gè)方面的貢獻(xiàn)：一是將NUMA架構(gòu)下的虛擬機(jī)之間的資源競爭問題進(jìn)行建模；二是將交叉熵和近端策略優(yōu)化算法強(qiáng)化學(xué)習(xí)算法融合起來來解決虛擬機(jī)放置問題。然而本算法沒有對虛擬機(jī)的遷移導(dǎo)致的性能下降做出優(yōu)化，進(jìn)一步的研究工作是改進(jìn)初始放置后由于虛擬機(jī)遷移而產(chǎn)生的競爭問題。