基于組合權重TOPSIS的Kubernetes調度算法①

張文輝,王子辰

(桂林電子科技大學 計算機與信息安全學院,桂林 541004)

1 概述

近幾年,隨著云計算技術的發展,在云上部署應用服務有利于降低成本和提高效率,但卻引出了資源利用率低、部署和重啟應用服務等待時間長等問題,而Docker 作為容器技術的代表,為應用程序提供了更加輕量級和易于部署的解決方案,如今已是云計算領域的熱點.

Kubernetes是容器編排技術的代表,是Google 公司Borg 項目的一個開源版本,它基于Docker 容器技術,目的是實現資源管理的自動化,以及跨多個數據中心的資源利用率最大化.Kubernetes 具有完備的集群管理能力,包括多層次的安全防護和準入機制、多租戶應用支撐能力、透明的服務注冊和服務發現機制、可擴展的資源調度機制等[1].在Kubernetes 集群中,以Pod 作為資源調度的基本單位,而Pod中可以容納多個容器,集群根據其生命周期進行管理,滿足了產品內運行程序的需求,Kubernetes 已成為大規模容器化應用程序部署的事實標準[2].近年來,大多數互聯網公司的相關技術人員相繼把Kubernetes 運行在重要業務上,同時越來越多的微服務也使用Kubernetes 進行部署和管理.

Kubernetes 資源調度是其核心的模塊,不合理的資源調度策略會造成云平臺整體資源利用率低,用戶的部署請求得不到快速響應,服務質量下降,同時也提高服務商的軟硬件設施成本.

Kubernetes 調度策略首先根據用戶提交的Pod 應用的最小資源需求過濾掉不符合要求的節點,其次以節點剩余CPU和內存的資源利用率為評分指標,對候選節點評分,選擇得分最高的節點進行部署.該策略存在兩處不足:(1)只考慮了CPU和內存兩種資源指標,無法滿足各異的應用需求;(2)采用相同權重計算候選節點得分,易造成資源使用的過度傾斜.

關于Kubernetes 資源調度問題,已經有學者在優化節點負載、提高集群資源利用率和減少資源成本等方面做了大量研究.Menouer 等[3]在Docker Swarm中利用TOPSIS 多屬性決策方法結合Spread和Bin Packing原理優化了多個資源指標下容器的調度問題;El Haj Ahmed等[4]通過容器應用的時間線和執行的歷史信息來優化容器應用的部署;Imdoukh 等[5]提出了一種基于多目標遺傳算法進行優化的調度算法MOGAS (manyobjective genetic algorithm scheduler),該調度算法與基于蟻群算法優化的調度算法相比較效果更佳;Zhang等[6]通過結合蟻群算法和粒子群優化算法改進了Kubernetes 調度模型,不僅減少了總的資源成本和節點最大負載,也使得應用部署更加平衡;孔德瑾等[7]提出一種基于資源利用率進行指標權重自學習的調度機制,提升了集群資源均衡度和資源綜合利用率;Li等[8]提出BDI (balanced-disk-IO-priority)算法來動態調度容器應用以改善節點間磁盤I/O 平衡,提出BCDI(balanced-CPU-disk-IO-priority)算法動態調度容器應用以解決單節點CPU和磁盤I/O 負載不平衡的問題;吳雙艷[9]通過灰色預測算法對資源負載進行預測,對容器云平臺彈性伸縮系統優化來提高服務質量;Dua 等[10]提出一種可供選擇的任務調度算法,為特定類型任務打上標簽,并基于標簽將任務遷移實現集群負載均衡;Zheng 等[11]提出一種基于Docker 集群的自定義Kubernetes 調度器調度策略,使用優化的預選算法模型和優選算法模型改進Kubernetes 默認調度策略,提高集群調度的公平性和調度效率.

雖然國內外學者針對Kubernetes 資源調度的研究已經取得了較多的成果,但在異構環境下兼顧資源指標權重和資源指標本身都有些欠缺.針對此問題,本文主要在崔廣章等[12]、龔坤等[13]的基礎上,選擇CPU、內存、帶寬、磁盤容量和IO 速率的實時資源利用率作為評價指標,并將基于層次分析法和熵權法得到的組合權重應用到TOPSIS 多屬性決策算法中,致力于將Pod 應用部署到最合適的節點上.

2 Kubernetes 默認調度策略

Kubernetes Scheduler是Kubernetes 集群的調度器,用于將用戶創建的Pod 按照特定的調度算法和調度策略綁定到集群中某個合適節點上.其調度過程可以分為兩個階段,分別是預選和優選階段.

預選階段主要是根據用戶提交Pod 應用的最小資源需求過濾掉不滿足需求的節點,Kubernetes 也提供了多種預選策略供用戶選擇,如PodFitsResources、PodsFitsPorts 等.

優選階段主要是在預選階段的基礎上,采集剩下節點上CPU和內存的空閑利用率進行評分,選擇評分最高的節點作為部署節點,最后將Pod 應用綁定到該節點上.同樣的,Kubernetes 也提供了幾種優選策略:

1)LeastRequestedPriority,該策略用于從候選節點中選出資源消耗最小的節點,即CPU和內存空閑資源越多,評分越高,其計算公式如下:

2)BalancedResourceAllocation,該策略用于從候選節點中選出CPU和內存使用率最均衡的節點,即CPU和內存使用率越接近,評分越高,其計算公式如下:

上述兩種策略,均只考慮了CPU和內存,且策略中CPU和內存利用率是由Pod 應用的需求來衡量調度的優先級的,無法準確反映節點實際資源使用情況,也會影響節點的整體資源均衡性.

3)SelectorSpreading,該策略將相同標簽選擇器選取的Pod 應用盡可能散開部署到多個節點上,節點上該標簽選擇器匹配的Pod 應用數目越少,則該節點的評分越高,使用標簽選擇器的資源對象有:Service,Replication Controller,ReplicaSet 等.

此外,調度策略還包括NodePerferAvoidPods,InterPodAffinity,NodeAffinity,TaintToleration 等.

上述公式中,Scpu和Smem分別表示節點上總的CPU和內存容量,而Ncpu和Nmem分別表示節點上已被使用的CPU和內存的容量加上將要部署的Pod 應用的CPU和內存的容量之和.

3 組合權重的TOPSIS 調度策略

由于Kubernetes 默認調度算法僅僅考慮CPU和內存,沒有考慮到帶寬、IO 速率、磁盤容量等資源的需求,無法對帶寬敏感型、IO 速率敏感型等Pod 應用進行合理的資源調度,同時兩個評分指標都采用相同權重,無法滿足Pod 應用各異的資源需求,當Pod 應用部署的數量逐步增加時,可能會造成其他指標如帶寬、IO 速率等資源過度浪費.

在評價指標方面,考慮到評價指標應該有效且有代表性,因此本文選擇CPU、內存、帶寬、磁盤容量、IO 速率作為評價指標.

在權重方面,本文利用熵權法[14]對層次分析法[15]得到的主觀權重進一步優化,有效避免了層次分析法權重的主觀性和熵權法權重的客觀性.

最后將組合權重應用到TOPSIS[16]多屬性決策方法中,來計算Pod 應用調度方案解和理想最優解及最劣解之間的距離,通過理想貼合度的大小排序,為Pod 應用選擇最合適的節點進行部署.

3.1 資源信息獲取

本文主要采集兩種資源信息:

(1)節點當前的各個資源指標的資源利用率.

(2)已部署的Pod 應用在節點上占用的資源份額.

通過在集群中每個節點上部署Proxy 監控代理,用于采集上述兩種資源信息,具體流程如圖1所示.首先準備兩個數據庫,分別用于存儲監控節點的資源利用率和Pod的CPU、內存、帶寬、磁盤、IO 速率占用率信息.在控制器模塊逐個分析節點Node 標識和Pod 應用標識,控制器可獲取到Proxy 代理的IP、端口,向Proxy 代理發送監控命令,之后采集實驗需要的監控信息存放到對應的數據庫中.

圖1 采集資源利用率

3.2 層次分析法求權重

層次分析法是一種使人們的思維過程和主觀判斷實現規劃化的方法,可以使因素的不確定性得到很大程度降低,不僅簡化了系統分析與計算工作,而且有助于決策者保持其思維過程和決策過程原則的一致性,是一種確定權重的科學方法,其計算步驟如下:

Step 1.構造資源指標判斷矩陣

假設集群中有m個資源指標,通過兩兩比較確定指標重要程度,進而得出判斷矩陣A=(aij)m×m,i=1,2,…,m;j=1,2,…,m,重要程度的定義如表1所示.

表1 相對重要程度表

矩陣中,m表示資源指標的個數,aij表示相對于第j個資源指標,第i個資源指標的重要程度,且aii=1.

本文以5 種資源指標CPU,內存,帶寬,磁盤,IO速率為基礎,給出判斷矩陣如下,選取理由如表2所示.

表2 部分指標對比結果

Step 2.一致性檢驗

判斷矩陣客觀反映了不同資源指標之間的相對重要性,但是并不能保證每個判斷矩陣都是一致的.例如,指標A1比指標A2重要,指標A2比指標A3重要,那么指標A3比指標A1重要就不合理,因此需要通過計算一致性檢驗CI(consistency index)和一致性比例CR(consistency ratio)來衡量判斷矩陣是否完全一致,具體計算公式如下:

其中,λmax為判斷矩陣的最大特征根,m為矩陣的階數,RI為平均一致性指標,其取值如表3所示.若CR<0.1,則通過一致性檢驗,否則判斷矩陣需要修正.

表3 平均隨機一致性指標

Step 3.計算資源指標權重

本文選擇常用特征值法來計算權重,只需要計算符合A·W=λmax·W的特征向量,然后Wλmax將歸一化,即可得到權重wAj,具體權重信息如表4所示.

表4 AHP 資源指標權重

3.3 熵權法求權重

熵權法基本思路是根據指標變異性的大小來確定客觀權重.該方法可以深刻反映出指標的區分能力,若某個指標的信息熵越小,表明指標值的變異程度越大,提供的信息量越多,在綜合評價中所能起到的作用也越大,其權重也就越大.其計算步驟如下.

Step 1.數據預處理

假設集群中有n個節點,m個資源指標,通過監控代理Proxy 采集到的資源利用率的實時數據,構造矩陣xij表示第i個節點上第j個資源指標的資源利用率.

Step 2.資源指標歸一化處理

考慮到每個資源指標的計量單位不同,有必要在計算綜合資源指標前,進行標準化處理,即把資源指標的絕對值轉化為相對值.

正向型資源指標歸一化,用于處理效益型決策參數,這類決策參數的特點是值越大效果越好,其計算公式如下:

負向型資源指標歸一化,用于處理成本型決策參數,這類決策參數的特點是值越小效果越好,其計算公式如下:

Step 3.計算第j個資源指標下第i個節點的值所占該資源指標的比重Pij,i=1,2,…,n;j=1,2,…,m.

Step 4.計算第j個資源指標的熵值ej,j=1,2,…,m.

其中,k=1/In(n)>0,滿足ej≥0.

Step 5.計算資源指標的差異系數dj,j=1,2,…,m.

Step 6.計算各指標的權重wEj,j=1,2,…,m.

3.4 計算組合權重

將熵權法得到的權重與層次分析法得到的權重結合,用于避免層次分析法的主觀影響和熵權法的客觀影響,其計算公式如下:

其中,wj為第j個資源指標的組合權重,wAj和wEj分別表示通過層次分析法和熵權法得到的第j個資源指標的權重.

以表4得到的AHP 權重為基礎,監控代理Proxy采集到的某個時間段的5 種資源指標的實時利用率如表5所示,根據表5的數據計算出熵權權重,最后根據式(14)計算得到組合權重,具體權重信息如表6所示.

表5 資源實時利用率 (%)

表6 詳細權重信息

3.5 TOPSIS 確定最優節點

逼近理想解排序方法(TOPSIS)是一種有效的多屬性決策方案,通過從歸一化的數據矩陣中構造出決策問題的正負理想解,計算出方案與正負理想解的距離,最終得到貼合度作為評價方案的優劣依據.其計算步驟如下.

Step 1.構造決策矩陣

假設集群中有n個節點,m個資源指標,通過監控代理Proxy 采集到的資源利用率的實時數據加上Pod部署所占用的資源利用率,構造決策矩陣i=1,2,…,n;j=1,2,…,m.

其中,xij表示第i個節點上第j個資源指標的資源利用率.

Step 2.歸一化決策矩陣

采用極差標準化方法對決策矩陣進行歸一化處理,目的是消除決策參數不同量綱之間的影響.

Step 3.構造加權決策矩陣

各異的Pod 應用對節點資源指標的需求敏感程度不同.大體上可以分為內存傾向型、CPU 傾向型、IO速率傾向型,帶寬傾向型等等,若是每個資源指標都采用相同權重,無法滿足各異需求的Pod 應用,因此有必要分別為節點的資源指標設置不同的權重.

基于此,在考慮資源指標的差異性,和避免了層次分析法人為的主觀影響和熵權法帶來的客觀影響下,本文通過結合層次分析法與熵權法得到組合權重,并應用到決策矩陣中,構造了加權決策矩陣i=1,2,…,n;j=1,2,…,m.

其中,wj是第j個資源指標的組合權重.

Step 4.計算正負理想解

其中,Z+表示加權決策矩陣的正理想解,由所有候選節點上每種資源指標參數的最大值構成;Z-表示加權決策矩陣的負理想解,由所有候選節點上每種資源指標參數的最小值構成.

Step 5.計算每個候選節點到正、負理想解的距離

其中,D+和D-分別代表各候選節點到正負理想解的歐式距離.

Step 6.計算每個候選節點與最優候選節點的相對貼合度Si

其中,相對貼合度Si越大,說明該候選節點越適合當前需要部署的Pod 應用.

以表5和表6的數據為基礎,結合TOPSIS 多屬性決策算法可以得到相對貼合度S,如表7所示,可以看出節點1的相對貼合度S 最大,因此將Pod 應用部署到節點1 最合適.

表7 相對貼合度

4 實驗驗證與分析

為測試本文提出的Kubernetes 調度算法的性能,進行實驗驗證.所有實驗均由PyCharm 2020.2 編程實現,并基于平臺:Windows 10,Intel(R) Core(TM) i7-8565U CPU 1.80 GHz,16 GB 內存.

4.1 實驗環境

在仿真環境下,模擬一個包含60 個節點的Kubernetes 集群,集群中節點分為3 種類型,每種類型20 個來模擬異構的環境,節點具體信息如表8所示.

表8 節點資源信息

同樣的,鑒于容器應用資源多樣化的需求,本文按照CPU 敏感型、內存敏感型、帶寬敏感型、存儲敏感型、IO 速率敏感型以及無傾向類型6 類容器應用構造了Pod 資源需求,表9為部分Pod 資源需求.

表9 部分Pod 資源需求表

4.2 實驗評價指標

假設Kubernetes 集群中有n個節點,每個節點上有m種資源.資源的實時利用率是通過監控代理Proxy 采集獲取得到的.U(i,j) 表示節點i上資源j的資源利用率;Uavg(i) 表示節點i上各個資源利用率總和的平均值;S(i) 表示節點i上各個資源利用率的標準差,即資源失衡度;Savg表示所有節點的平均資源失衡度.Savg的值越小,代表集群中各個資源的利用率越平衡,就不容易出現資源傾斜,如此就可以部署更多的Pod 應用,具體計算公式如下:

4.3 實驗結果和分析

在上述Kubernetes 集群中,分別采用Kubernetes的LeastRequestedPriority (LRP)策略與BalancedResource-Allocation (BRA)策略和本文提出的組合權重TOPSIS調度算法(CWT),從資源平衡度、CPU、內存、帶寬、IO 速率角度來對比3 種算法的表現.

1)集群資源失衡度

集群失衡度變化曲線如圖3所示,當Pod 數量小于1 200 時,此時集群負荷相對較低,LRP和BRA 策略與CWT 算法的資源失衡度相差不大,但隨著部署的Pod 應用數量越來越多,可以很明顯的發現CWT 算法開始發揮作用,它的資源失衡度明顯好于LRA 策略.

在集群資源整體快達到飽和時,CWT 算法優于BRA 策略.這是由于CWT 算法不僅考慮了集群節點的5 種資源指標,還分別考慮了各個資源指標的權重情況,這就降低了集群中單個節點出現單個資源用盡而其他資源大量剩余的可能.尤其是在集群資源整體飽和的情況下,CWT 算法的資源失衡度比LRA 策略整體下降18%,比BRA 策略整體下降7.7%,這說明CWT 算法在集群資源飽和的情況下可有效的調節集群資源平衡度.

2)CPU、內存資源利用率

圖3和圖4反映了在Pod 應用數量為7 200 時,CWT 算法、LRP 策略和BRA 策略下各個節點的CPU和內存資源利用率的情況.在BRA 策略下,CPU 資源利用率和內存資源利用率好于CWT 算法,且遠遠好于LRP 策略,這是由于BRA 策略會選取CPU和內存資源使用率最接近的節點進行部署.而在LRP策略下,有3 個節點CPU 資源已經飽和,1 個節點的內存資源已經飽和,飽和率達到6.7%,這意味著這4 個節點上所有Pod 應用的處在資源受到限制的環境,嚴重影響了集群的整體健康.在CWT 算法下,CPU和內存的資源利用率波動比BRA 策略稍微大一些,這是由于CWT 算法綜合考慮了5 種資源指標,相較于BRA策略只考慮CPU和內存兩種資源指標,CWT 算法則考慮的更加全面,更加能適應實際生產環境的需求.

圖2 集群資源失衡度變化

圖3 不同策略下的CPU 利用率

圖4 不同策略下的內存利用率

3)帶寬、IO 速率資源利用率

圖5和圖6反映了在Pod 應用數量為7 200 時,CWT 算法、LRP 策略和BRA 策略下各個節點的帶寬和IO 速率資源利用率的情況.由于LRP 策略與BRA策略只考慮CPU和內存,未考慮帶寬和IO 速率等因素,隨著Pod 應用數量增加,在這兩種策略下資源失衡度上升,集群中部分節點出現資源傾斜,尤其是帶寬和IO 資源利用率,很明顯可以看出集群中節點之間利用率波動較大.

圖5 不同策略下的帶寬利用率

圖6 不同策略下的IO 利用率

在LRP 策略下,帶寬利用率最大的節點與利用率最小的節點相差48%,IO 資源利用率最大的節點與利用率最小的節點相差24%,而在BRA 策略帶寬利用率最大的節點與利用率最小的節點相差47%,IO 資源利用率最大的節點與利用率最小的節點相差41%,甚至有多個節點的帶寬和IO 資源利用率已超過100%,這說明這些節點的帶寬和IO 資源已經完全飽和,LRP 策略下飽和率達到25%,BRA 策略下飽和度達到18.3%.若是帶寬和IO 速率敏感型的Pod 應用被部署在這些帶寬和IO 資源飽和的節點上,會帶來網絡和IO 讀寫的擁堵.

在CWT 算法下,全部節點的帶寬和IO 資源利用率都在75%到95%的區間內震蕩,沒有出現帶寬資源利用率超過100%的情況,相較于LRP 策略和BRA 策略,CWT 算法更加保障了集群的帶寬穩定.

5 結論與展望

本文針對Kubernetes 默認調度算法僅考慮CPU、內存兩種資源指標,且對需求各異的Pod 應用采用相同權重的調度策略進行了改進,通過增加帶寬、磁盤、IO 速率3 項指標,結合層次分析法與熵權法得到每個資源指標的組合權重,并應用到TOPSIS 多屬性決策方法中,為Pod 應用選擇合適的節點進行部署,有效提高了集群整體的資源平衡度,避免了集群中節點上單個資源耗盡而其他資源尚有剩余的情況,通過實驗驗證,證明了組合權重TOPSIS 調度算法的有效性和合理性.下一階段將考慮集群的動態調度與多租戶情況相結合,使得集群資源調度更加高效,集群資源更加平衡,集群資源利用率更高.