基于模擬退火算法的粒子群優化算法在容器調度中的應用

劉哲源,呂曉丹,蔣朝惠,2

(1.貴州大學 計算機科學與技術學院，貴陽 550025;2.貴州省公共大數據重點實驗室，貴陽 550025)

0 引言

隨著云計算產業的高速發展，面對高并發量的業務壓力，虛擬機靈活性不足、創建速度慢、不易擴展等缺點越來越凸顯。容器技術易擴展、秒級啟動、靈活的彈性伸縮等特點，為這些問題提供了一種全新的解決方案。軟件容器化已經成為軟件部署和當今互聯網的新趨勢。Docker[1]則是其中一個開源的應用容器引擎，不僅是一個新型虛擬化技術，同時也是應用程序交付的一種方式。傳統虛擬機一般由虛擬硬件和操作系統兩部分組成，而Docker容器不需要安裝特定的操作系統和VMM(虛擬機監控)，Docker容器通過共享主機操作系統內核，用主機的硬件和操作系統來完成程序的操作，一定程度上減少了資源的浪費問題，兩者架構對比如圖1所示。

圖1 傳統VM和Docker的架構對比

Kubernetes[2]是目前主流的Docker容器編排平臺之一，負責對容器的整個生命周期的管理。Pod是Kubernetes的基本運行單元，一個Pod內可以有多個容器，且可以在創建Pod的yaml配置文件中聲名容器所需要的資源需求。Kubernetes在對Pod任務進行調度時，首先通過預選算法篩選出所有符合運行條件的節點，接著通過優選算法為這些節點進行打分，最終選擇分數最高的節點用來綁定Pod任務，接著調用Docker-daemon通過Http方式向鏡像倉庫下載相應的容器鏡像，具體步驟如圖2所示。

圖2 Kubernetes調度過程

雖然Kubernetes的Balanced Resource Allocation調度算法雖然能一定程度上解決資源均衡問題，但是仍然達不到數據中心的預期水平。Kubernetes的調度算法僅僅考慮了工作節點的CPU和內存利用率，而未考慮工作節點的網絡負載能力，從而影響Pod的任務最少等待時間。

目前，國內外對容器調度后的資源利用率不均衡問題有較多的研究。文獻[3]設計了EVCD(基于虛擬機彈性供給的容器部署)，利用貪婪first-fit和round-robin，并EVCD可以在運行時重新分配容器實現QoS的改進，提升容器調度的效果。文獻[4-5]通過對容器需求的CPU和內存資源進行分類，針對不同類型的容器使用不同的調度算法。文獻[6]提出了基于應用歷史記錄的調度算法，減少容器調度后的鏡像分發過程中帶來的網絡資源的損耗。文獻[7-10]使用群優化算法對容器的多指標調度設計，實現了較好的資源使用率。文獻[11]通過對數據中心資源進行更細粒度的劃分，在保證了服務器性能的同時，集群資源利用率也得到了提高。文獻[12-13]針對容器動態調度的問題，設計尋找最優解的動態調度算法，解決了動態調度中的資源浪費問題。文獻[14]設計一種多目標容器調度算法Multiopt，通過對工作節點當前狀態進行計算評估出合適的調度節點。文獻[15-16]對集群負載均衡性進行考慮，采用智能算法對集群中所有節點進行評定，最終確定調度節點。文獻[17]通過預先訓練隨機森林回歸模型，預測集群壓力進行容器調度。文獻[18]提出了一種VM-Container混合分層資源調度機制，通過調度狀態綜合性將任務劃分為不同的級別，針對不同的級別制定不同的PSO調度算法，但沒有考慮到特殊情景下的容器調度。文獻[19-20]關注容器資源要求環境和任務規模變化，提出采用粒子群優化算法來進行容器部署，解決了容器部署過程中的網絡消耗問題。

盡管國內外很多學者已經為此做了很多有價值的工作，但是仍然存在不足。因此，研究的重點在于改進容器調度算法以提高集群節點的資源利用率從而達到數據中心的預期水平，減少容器任務最少等待時間，提升容器云的服務質量。

1 數學模型的設計與構建

在Kubernetes平臺中，創建容器首先采用聲明式方法在Pod的yaml文件中聲明容器所需要的資源信息，接著通過kubectl命令來創建Pod。因此，在Pod開始調度之前，系統已經獲取了Pod的資源需求情況。同時，Kubernetes中的api-server組件收集集群中節點的指標資源使用情況。構建數學模型如下。

容器云集群：

Cluster={Node1,Node2,...,Noden}

(1)

式中，Cluster為n個Node節點組成的集群，每個Nodei節點都具有4維屬性表示為：

Nodei={UCPU,UMem,UNet,status_now}

(2)

式中，Nodeid表示為Node節點i中的可用第d維資源，Nodei4表示節點Nodei得可用第4維資源status_now，即為當前主機狀態，其具體取值如下：

(3)

式中，當節點Nodei當前處于宕機狀態時，status_now為值0，反之，status_now為值1。

對于每次創建任務Podi，都具備3維屬性：

Podi={RCPU,RMem,Rimage}

(4)

式中，Rmem,Rimage分別為任務Podi所需要的CPU、內存、容器鏡像等資源需求。當開始調度時，通過Kubernetes編排平臺中的預選決策后，集群已經通過預選決策篩選出了一部分可以滿足調度任務可正常工作節點：

(5)

式中，Node為篩選出來符合調度條件的工作節點的集合，且被篩選出來的Node節點均包含有當前節點目前的資源使用情況，UCPU為節點當前的內存使用量，Umem為當前節點的內存使用量。盡管篩選出了一部分可以使用的工作節點，我們仍需要通過優選測了為Podi找到一個最優節點進行調度，以提升集群的整體資源利用率。

對于每個數據中心而言，CPU、內存等資源的長期閑置也是一種開銷損耗，而資源利用率超過一定負荷閾值則證明其在負荷運行，同樣也是對服務器的生命周期的一種損耗，因此保證資源利用率不低于資源閾值，且不高于負荷閾值，則是提升資源利用率的一種有效方式。對于資源利用率我們希望其：

(6)

式中，Z表示為資源類型，包括CPU、內存、網絡等資源類型，Zmin為云服務廠商所希望資源不低于的最低資源閾值，Zmax為云服務廠商所希望的不高于的負荷閾值。ZNodei-use為若Podi綁定到Nodei節點后Z資源使用率，ZNodei-t為Nodei節點的總資源，ZNodei-U為當前節點此時刻的Z資源類型的資源使用量，ZPodi-R為任務Podi所需要的資源量。

容器云調度過程應盡可能多地為上層應用分配計算機資源，給容器云經營者帶來更多的收益，因此，以所有執行任務所需要的資源量的價值來表示容器云經營者滿意度函數如式(7)所示:

f(Z,Nodei)=(Zmin+Zmax)*ZNodei-t-2UZ

(7)

式(7)意為：當適應性函數在節點i的函數值越高，則證明資源Z在Nodei上的資源使用率低，越不符合數據中心的資源使用率預期，因此是Pod任務綁定的較優節點。在Pod任務綁定到Nodei節點后，Z資源的使用率高于最低資源閾值，且不高于最高負載閾值，以達到容器云運營者的滿意程度。

因此，我們主要對數據中心資源使用不均情況較為常見的CPU、內存指標和工作節點當前網絡負載情況進行數學建模：

1)CPU模型構建。根據Pod所需要的CPU需求量RCPU，與篩選出的節點Nodei中目前所使用的CPU使用量UCPU進行量化建模，具體公式如式(8)所示:

(8)

為了滿足任務Pod所需CPU資源，E1應受限于：

0

2)內存模型構建。根據Pod所需要的內存需求量RMem，與篩選出的節點Nodei中目前所使用的內存使用量UMem進行量化建模，具體公式如式(9)所示:

(9)

為了滿足任務Pod所需內存資源，E2應受限于：

0

3)網絡負載建模。根據Pod所需要的鏡像需求Rimage，與篩選出的節點Pod中目前所使用的網絡負載量Unet進行量化建模，具體公式如式(10)所示:

(10)

4)適應性函數構建。針對以上問題，對適應性函數公式可以建立為：

(11)

式(11)中，Nodei4是Nodei得第4維屬性status_now，當節點宕機時，該宕機節點得適應性函數function值為0，當適應性函數function值越高，則代表當前Nodei資源利用率越滿足任務Pod運行條件，且綁定Pod任務后集群資源利用率趨于數據中心滿意度。

2 基于模擬退火的粒子群優化算法

2.1 標準粒子群優化算法

粒子群優化算法(PSO)[21]是一種模擬生物行為活動的群智能化算法，每個粒子都存在一個存在可行解的搜索空間，且每個粒子都具備一定的空間搜索能力，通過粒子速度V,粒子位置X來表示粒子空間位置特征，并由目的函數確定適應度值，其值的好壞表示粒子的優劣程度。

粒子在獨自的搜索空間內，每個粒子會記錄自身最優位置與全局最優位置，并通過判斷當前自身位置和個體最優位置以及群體最優位置的距離，若自身位置優于全局最優位置，則更新全局最優位置，并不斷更新自身的位置和速度，不斷迭代，直到找到種群最優位置。更新公式如式(12)所示：

(12)

標準PSO算法的偽代碼如下所示：

Algorithm 1:Find the maximum position of the maximum function.

procedure PSO

for each particlei

Initialize velocityViand positionXifor particlei

Evaluate particleiand setpBesti=Xi

end for

gBest= max{pBesti}

while not stop

fori= 1 to N

Update the velocity and position of particlei

Evaluate particlei

if function(Xi) > function(pBesti)

pBesti=Xi;

if function(pBesti) > function(gBest)

gBest=pBesti;

end for

end while

printgBest

end procedure

2.2 基于模擬退火的粒子群優化算法思想

模擬退火算法[22]的是受固體退火過程的啟發而發展出來的一種算法，固體加熱至足夠的高的溫度時，再另其緩慢冷卻，而固體中的粒子在升溫過程中，內能增大，趨于無序；緩慢降溫時又能夠使得內能減小，趨于有序。因此理論上說，只要初始溫度足夠高，而降溫過程又足夠緩慢，那么算法在過程中將會收斂到全局極值。而之所以模擬退火算法可以有能力進行概率突跳，是因為采用了Metropolis準則，其表達式為如式(13)所示:

(13)

如圖3所示，在主節點api-server組件接收到Pod任務創建任務后，kube-scheduler組件調用基于模擬退火的粒子群優化算法，并向數據庫請求實時采集容器云中工作節點的當前資源信息，得到返回數據后開始計算，計算完成后返回最優節點，工作節點kubelet組件通過watch監聽主節點api-server得到調度任務后，調用本地Docker-daemon組件進行容器鏡像的檢索和下載工作，鏡像存在本機后，啟動任務，至此一次任務創建完成。

圖3 基于模擬退火的粒子群優化算法框架圖

粒子群優化算法的優化過程主要是通過粒子群中的粒子通過粒子間的信息(即個體最優解和全局最優解)不斷更新自身的位置和速度，使其能不斷地向全局最優解靠攏，最終得到全局最優解。但是由于基本粒子群算法處于運算后期時，因粒子多樣性減少，容易陷入局部最優，且后期收斂速度變慢。在整個計算流程中，慣性權重對粒子速度和位置的影響不同：運算前期，較大的慣性權重有利于全局搜索，粒子速度快，但尋優值不夠精確；相反，運算前期，較小的慣性權重有利于局部搜索，全局搜索能力較弱，但容易陷入局部最優。因此，將模擬退火算法嵌入粒子群優化算法中，就是在算法初期溫度較高的時候，讓種群例子有較大概率去接受非最優解，從而跳出局部最優解，而后期溫度降低時，又能夠收斂到全局最優，準確定位到全局最優解。由于模擬退火有能夠突跳的概率，因此可以有效避免算法陷入局部最優，有效避免了“早熟”現象。基于模擬退火的粒子群優化算法流程如圖4所示。

圖4 模擬退火的粒子群優化算法流程圖

3 實驗結果與分析

3.1 實驗環境

實驗環境采用翔明云提供的虛擬機作為操作主機，創建集群大小為17的高可用Kubernetes集群，集群中3臺節點搭建Master節點高可用，其中2臺既是Master節點也是Node節點，共計16個Node節點。實驗環境如表2所示。

表2 實驗環境表

對SA-PSO算法(后稱改進PSO算法)與標準PSO算法、文獻[23]動態權重調整的PSO算法(后稱權重PSO算法)進行性能及精度進行對比。同時對改進PSO算法與Kubernetes默認調度算法進行對比。服務器資源利用率的期望閾值根據貴州翔明云日常運維需求來進行設定，當CPU利用率在20%～80%，內存利用率在30%～80%之間，服務器性能較好，且資源利用率最合理，文獻[24]實驗得出當c1=c2=2.5時標準PSO算法的收斂效果最好，文獻[25]指出模擬退火中K=0.7和T0=10 000時，基于模擬退火的粒子群優化算法效果較好。實驗中具體參數設置如表3所示。

表3 實驗參數表

3.2 實驗與分析

3.2.1 性能測試和精度測試

對改進PSO算法的性能進行測試，通過對權重PSO算法，標準PSO算法的尋優過程中的迭代次數以及收斂性進行對比，測試改進算法的算法效率。實驗過程通過發布一個CPU需求量為1 000 m、內存需求量為1 G的Nginx容器Pod任務，使用目標函數對不同Node節點的資源利用情況進行計算得到該節點的適應性值，適應值最高的節點即為本次任務的全局最優目標節點，不同的粒子在不同節點間自主運動，并不斷與全局最優解進行比較，調整自身的運動方向以及運動速度，直到找到最高峰值，峰值所在節點既是全局最優節點，具體如圖5所示。

圖5 集群節點適應值曲線

當迭代次數為50，粒子群大小為3時，對3種算法的迭代尋優變化曲線進行對比，具體實驗結果如圖6所示。

圖6 算法迭代尋優對比圖

依此反復測試10次，目的函數達到最大值記為一次成功命中，意味著沒有進入局部最優，達到了全局最優解，記為全局收斂成功。各個算法尋找到各自群體最優解看作完成迭代，記錄為迭代次數，同時該記錄也包含陷入局部最優解的情況。通過計算得出平均迭代次數、收斂成功率情況如表4所示。

表4 尋優情況表

實驗表明，當粒子群大小為3，最大迭代次數為50次時，標準PSO算法容易陷入局部最優情況而無法精確地找到目標節點，而改進PSO算法和權重PSO算法相較標準PSO算法的收斂成功率以及命中率均有較大提升，且平均迭代次數要少于標準PSO算法。改進PSO算法由于對學習因子進行動態調整，收斂性能略優于權重PSO算法。上述實驗可知，在本次實驗環境下，改進PSO算法的成功命中率相較標準PSO算法提高了近60%。

3.2.2 負載均衡測試

對集群負載均衡度進行測試。使用Kubernetes的Scheduler-framework用來實現改進PSO算法的調度算法。通過選擇先后選擇BLA調度算法和改進PSO調度算法分別部署4個高資源需要求的Nginx服務器作為調度任務，在yaml文件中限制CPU大小為1 000 m，內存大小為1 G，通過Kubernetes的BalanceResourceAllocation(后稱BLA)算法，將4個調度任務分別綁定到4個節點，先后次序為node15，node02，node05，node12，完成后集群資源利用使用圖如圖7所示。

圖7 BLA調度算法集群資源使用情況圖

實驗結果表明，雖然BLA調度算法一定程度上提高了資源利用率，但是仍有部分節點資源使用情況不理想。在BLA調度過程中，主要會考慮任務綁定到某個節點時節點資源使用率是否均衡而不會考慮資源利用率情況，因此容易造成某些節點資源利用率不高的情況。通過改進PSO算法先后部署同樣的4個調度任務，任務綁定節點先后次序為node08，node06，node04，node15，改進PSO算法能較好的提高整體資源利用情況，達到云提供商的資源使用預期，完成調度后的資源使用情況如圖8所示。

圖8 改進PSO調度算法集群資源使用情況圖

通過對比兩個算法的任務調度可以看出，改進PSO算法SA-PSO相對Kubernetes的Balance Resource Allocation算法實現了更好的集群資源利用率，同時部署節點的網絡負載率也處于較低水平，為下一步容器鏡像分發步驟節省了任務等待時間。在本實驗環境中，改進PSO算法(SA-PSO)可以準確地找到任務綁定的最優節點，從而提高集群的整體資源利用率。

3.2.3 任務最少等待時間測試

使用Kubernetes默認調度算法和改進PSO調度算法進行分別部署10次鏡像大小為133 MB的Nginx服務Pod任務，其資源需求配置如測試(2)相同，記錄其任務最短等待時間，實驗對比結果如圖9所示。

圖9 任務最少等待時間與網絡負載率對比圖

圖9中，網絡負載率1為默認算法調度工作節點的網絡負載率，網絡負載率2為改進PSO算法調度工作節點的網絡負載率。由實驗結果可知，改進PSO算法較于默認調度算法由于在調度過程中將工作節點的網絡負載率帶入計算，優先選擇網絡負載率低的節點進行調度，因此可以提升鏡像分發的效率，從而減少任務最少等待時間。

4 結束語

隨著云計算產業的快速發展，Docker的出現給了互聯網企業一種新的解決問題的思路。面對大規模的軟件部署，若不能合理利用服務器資源，無論對云提供商還是軟件方都是一項額外的開銷。而主流的容器編排平臺Kubernetes在調度容器的過程中存在著資源利用不足的問題，同時目前主流研究沒有將容器調度過程與鏡像分發過程相結合。因此，在此提出了一種基于SA-PSO調度算法，通過模擬退火算法解決粒子群算法易于陷入局部最優解的問題。經過實驗表明，SA-PSO算法相較標準PSO算法以及權重PSO算法有較強的收斂能力以及尋優精準度，在本實驗環境中，尋優精準度相較標準PSO算法提升約60%。同時，在Kubernetes平臺實驗測試中，SA-PSO調度算法不僅對數據中心期望的資源閾值進行考慮，而且在集群資源利用率方面優于BalanceResourceAllocation調度算法。對工作節點的網絡負載率進行考慮，顯著減少了容器任務的任務等待時間。