基于Kubernetes的資源調度策略研究與改進

于澤川， 張 娜， 包梓群， 蘇鴻斌

(浙江理工大學 信息學院， 杭州 310018)

0 引 言

底層虛擬化技術的快速成熟，各大云計算廠商也開始積極建立自己的云部署平臺, 與此同時以Kubernetes(以下簡稱K8s)為代表的容器編排技術成為云原生的標準。K8s集群中主要包括api-server、kube-scheduler、controller-manager 3大組件。其中，kube-scheduler負責執行調度指令，將需要運行的Pod(基于Docker實現的K8s的基本調度單位，提供一組服務的集合)調度到符合要求的Node(負責負載Pod的基本單位)節點上去運行；kube-scheduler的默認資源調度策略相對簡單，但考慮不夠全面，默認調度采用先到先服務的原則，選擇負載服務的節點時采用貪心思想，保證當前最優，在多Pod調度的任務場景中無法保證全局最優[1-3]。由于容器云平臺的資源調度存在很大的優化空間，由此引起了廣大學者的研究改進。

張玉芳等[4]在考慮節點本身性能的情況下，為不同資源給出不同計算權重，率先提出利用負載權值計算的方法；李華東等[5]提出基于合作博弈論的多資源負載均衡(Multi-resource load Balancing algorithm based on Cooperative Game Theory，MBCGT)算法，解決面對不同資源請求時的算法下界和集群資源碎片化現象；聶清彬等[6]提出基于改進蟻群算法的自適應云資源調度模型。目前，關于智能優化算法在資源調度方面的研究成為主流。Kaewkasi等[7]將蟻群算法應用于SwarmKit集群進行容器調度，較貪心算法的性能有大幅提升；Mathiyalagan等[8]借助網格計算編程的粒子群優化算法發展系統能力；王悅悅等[9]使用自適應神經網絡構建云資源預測模型，解決資源供求不均衡導致的資源利用率差等問題。隨著大量研究的進行，智能優化算法被廣泛應用于優化資源調度，并取得不錯的成果。在智能優化算法中，粒子群算法因其簡單易行、收斂速度快被廣泛關注，其借助多個粒子在解空間中的迭代尋優尋找最優解[10]。本文針對智能優化算法中的粒子群算法作出改進，通過動態改變慣性因子、個體學習因子以及社會學習因子的計算權重，改善其前期的全局尋優能力和后期的局部尋優能力，加快其后期收斂速度，將之運用在K8s的資源調度方面，建立多Pod調度模型，并將改進的粒子群算法和傳統粒子群算法以及K8s默認的調度策略進行比較，證明改進后的粒子群算法對集群的負載均衡度有所改善。

1 K8s默認調度策略分析與粒子群算法

1.1 K8s默認資源調度策略分析

K8s的默認資源調度過程分為預選和優選兩個環節。在預選過程中，根據用戶提交的yaml配置文件遍歷所有Node，過濾掉不符合要求的Node，該過程保證了通過預選的節點都是足以運行當前Pod的節點。優選過程是為通過篩選的節點打分，整個選擇過程通過預選階段選擇出可支持運行當前Pod的Node集合，作為下一階段的輸入，得到節點集合輸入的優選過程以為各個節點打分為目標，得到分數最高的節點作為Pod落戶的目標節點。打分范圍是[0,10]之間的整數，通過分數表明該節點的優先級，10代表最優，0代表最差。當最高分節點不唯一，系統會從最高分節點中隨機選擇一個作為目標節點，存在一定隨機性。

K8s的默認調度策略保持著啟發式調度策略中的先到先服務準則(FCFS)，會將調度Pod按照先后順序依次執行上述預選和優選的過程，在為Pod選擇負載節點時則使用貪心思想，永遠將當前Pod調度到得分最高的節點上去，追求局部忽略了整個多任務調度過程的全局性；其次，K8s的調度策略只將CPU和內存作為資源調度的主要考量，忽略了網絡帶寬和磁盤IO的影響，Kubernetes集群的綜合性能離不開這兩者的的支持，因此網絡帶寬和磁盤IO需要加入運算，完成對節點更完整的畫像；最后，在待調度隊列中Pod被逐個調度時，同一副本下的調度任務可能創建多個副本，相同副本擁有相同的資源需求量，在進行相同副本的首次調度時，對符合要求的Node節點已經進行過打分，在調度下一個相同副本下的Pod時，大部分的節點打分仍然具有意義，但在K8s的調度策略中無法復用?；谏鲜鰡栴}，本文將對粒子群算法進行優化，并應用于K8s的資源調度，解決上述問題。

1.2 粒子群算法

粒子群算法(PSO)是一種智能優化算法，由Kennedy和Eberhart于1995年提出，作為一種基于群體智能(Swarm Intelligence)的優化方法，具有簡單易行，收斂速度快和設置參數少的特點[11]。PSO通過在解空間中部署大量粒子來尋優。粒子僅具有兩個重要屬性，速度和位置。速度代表移動的快慢，從某種程度上反映了單次移動的步長；位置代表其作為一個解自身所對應的屬性。一個粒子通過速度計算出在某維度上的速度，即會發生在該維度上的移動距離，當所有維度的數據特征聚集在一起就完成了一個粒子在解空間中的位置改變[12]。

首先，在解空間中給出大量粒子，每個粒子需要在解空間具有一個初始位置和速度，這些粒子要求均勻分布于解空間中，以防止結果陷入局部最優，無法收斂于全局最優。

粒子的速度更新公式(1)如下：

vi+1=ωvi+c1×random1()×(Pbesti-xi)+

c2×random2()×(Gbesti-xi)

(1)

其中，ω為慣性因子，取值一般為0.9，為保持上一步移動的慣性，來對下一步移動產生影響，決定了粒子繼承先前移動軌跡的權重；c1是個體學習因子，表明自身歷史最優值對當前移動的影響；c2是社會學習因子，表明群體最優粒子對當前粒子的吸引力，c1和c2的取值一般為2；Pbest是當前自身歷史最優位置；Gbest是當前群體最優位置；xi就是當前位置；i為迭代次數；random1()和random2()為兩個隨機函數，隨機產生范圍在[0,1]的值，用于增強粒子尋優的隨機性，防止粒子過早收斂，全局尋優能力降低，陷于局部最優。

單維度上的粒子的位置更新公式(2)為

xi+1=xi+vi+1

(2)

其中，x代表相對位置，i為迭代次數。

由此可見，速度直接決定了位置變化。

ω越大，當前粒子群的全局搜索能力越強，ω越小，當前粒子群的局部搜索能力越強。所以在實際應用中，為保證粒子群在迭代前期擁有較好的全局搜索能力，在后期可以有較強的局部尋優能力從而迅速收斂，ω通常是動態的，常用的動態變換公式(3)為

(3)

其中，ωmax和ωmin分別代表慣性因子的上下界，選值通常為0.9和0.4；r是迭代次數；rmax為預設的最大迭代次數，本次取值200。

隨著迭代次數的不斷增加，慣性因子ω完成了從最大值到最小值的線性變化，某種程度上擺脫了固定慣性因子大小帶來的容易陷入局部最優的缺陷。

設置迭代次數后，對初始化粒子的位置還有個體歷史最優位置和全局最優位置進行迭代更新，而確認個體歷史最優位置和全局最優位置的方法就是通過適應函數計算粒子的適應值，結束條件通常為結果收斂或已經達到預設迭代次數。

2 粒子群算法改進與應用研究

2.1 改進粒子群算法Ku-PSO

PSO算法通過迭代尋優，具有易于實現，易于理解，設置參數少等特點，但其仍存在易陷入局部最優解，難以得到精確的全局最優解等缺陷。本文對傳統PSO算法作出改進，改進后的算法稱為Ku-PSO算法，前期迭代更為依賴個體學習，擁有更好的全局尋優能力，后期迭代更為依賴社會學習，擁有更好的局部搜索能力，利于收斂。在整個搜索過程中，當前位置適應度較低時給出更大速度，擴展更多可能性，在當前位置適應度較高時給出相對較高的慣性因子，提升收斂速度。

公式(1)中ω，c1和c2，分別充當了前一次迭代速度，前一次迭代全局最優位置和自身粒子歷史最優位置參與計算當前迭代速度的權重。

首先，對ω作出改進。ω較大時，粒子會擁有更好的全局尋優能力；ω較小時，粒子會擁有更好的局部尋優能力，故提出ω的動態變化公式(3)，使得ω完成了由ωmax到ωmin的線性變化。

此處將ω的線性變化公式由公式(3)替換公式(4)：

(4)

借助拋物線，獲得更為合理的由ωmax到ωmin的非線性變換。由于粒子群算法易陷入局部最優解，通過非線性變換使得ω在前期迭代中緩慢減小，后期迭代中快速減小，從而增強前期全局尋優能力和后期的局部收斂能力。

在此基礎上，為增強粒子的全局尋優能力，設計在粒子適應度較小時，繼續維持較大的速度，從而獲得更大的步長，得到更廣闊的解空間搜索范圍。因此對c1和c2給出式(5)變化，假設公式(1)中c=c1=c2。

(5)

其中，cmin即為c的最小值，取值為1；cmax即為c的最大值，取值為3；F為當前粒子通過適應函數計算出的適應度；Fmax為前一次迭代全局最佳適應度；Favg為前一次迭代的粒子群平均適應度；θ為曲線平滑度控制因素，此處取值為3。

tanh(x)為雙曲正切函數，其特征x在(0，+∞)的范圍內，其值在(0，1)上非線性遞增，斜率逐漸降低。設置θ為3，邊界更靠近1，使得c完成了從cmin到cmax的非線性變換。隨著迭代次數增加，從一定程度上降低了慣性因子的影響，使得自身收斂特征更為明顯。通過分段函數使得粒子在自身適應度較低時，可以通過一個更大的速度移動，從而探索更多的解空間，而在自身適應度高于均值時，進行正常的收斂。這樣做防止了粒子過早地陷入局部最優，保存了種群多樣性。

為再次強化前期的全局搜索能力和后期的局部搜索能力，有必要在前期給個體學習因子c1更高的權重，在后期將權重逐漸偏向社會學習因子c2。

于是給出公式(6)和公式(7)，使得在前期迭代中，個體學習因子c1占較大比重，可以增強前期的全局尋優能力，探索更大的解空間；后期迭代中，社會學習因子c2比重逐漸升高，可以在基本確定全局最優范圍后迅速收斂。

(6)

(7)

Ku-PSO針對慣性因子，個體學習因子，社會學習因子均給出了優化方案，使得前期的尋優能力大幅提升的同時不影響后期粒子群的收斂速度，基本解決了粒子群算法容易陷入局部最優的問題，借此完成均衡調度。

2.2 Ku-PSO在K8s資源調度的應用

通過Ku-PSO算法針對K8s集群多Pod應用部署創建模型。

將n個Pod應用部署到m個負載應用的工作節點上，設置對應配置矩陣。部署Pod集合為Pods={p1,p2,p3,…,pn}，負載節點集合Nodes={n1,n2,n3,…,nm}，為Pods中每個Pi在Nodes中選擇一個負載節點nj進行部署。

配置矩陣如下：

dij取值為0或1，為1代表將第i個Pod部署到了第j個Node上運行，為0則相反。一個矩陣D就是一種調度方案。在Ku-PSO算法中，一個粒子代表一個配置矩陣，即代表一種調度方案。

K8s默認調度算法只將CPU和內存性能考慮其中，忽略了網絡帶寬和磁盤IO對Pod部署的影響。在網絡應用和涉及存儲的Pod部署時，網絡帶寬和磁盤IO也同樣重要，此次在考慮CPU和內存的基礎上將網絡帶寬和磁盤IO也加入運算，通過時序數據庫InfluxDB來獲取各個Node節點的資源總量{Ccpu,Cmem,Cnet,Cdisk}，和各個Pod的資源請求數值{Rcpu,Rmem,Rnet,Rdisk}。

接下來為粒子群算法設置目標函數，即為適應函數，式(8)，對所有的方案進行篩選和優化比較。

(8)

其中，U代表資源的利用率；j為Node的編號；Uavg代表所有工作節點上的平均利用率。

借此式來表示一種部署方案下的集群負載均衡度，式(9)：

(9)

設置好部署矩陣和評判粒子好壞的適應函數，接下來需要為配置矩陣設置約束條件，避免Pod應用部署時產生矛盾。

首先，每個Pod最多只能部署到一個Node上運行，故存在式(10)：

(10)

其次，各Node節點上部署到Pod請求資源總量不得超過當前節點上擁有的資源總量。故存在式(11)：

(11)

其中，i為部署到第j個Node上的Pod編號。

上述過程按照標準的粒子群算法改進，但K8s多Pod任務部署過程是一個離散型問題，需要在Ku-PSO算法的基礎上，進行二進制離散粒子群的映射。標準粒子群算法使用sigmoid函數進行映射，通過映射的方式得到映射概率，可以計算出當前粒子在該維度突變為1的概率，式(12)：

(12)

其中，vij為標準粒子群計算所得速度。

2.6 九種病原體的混合感染情況 本次研究僅存在兩種病原體的混合感染，感染率為2.78%（194/6 984），占陽性病例的10.55%（194/1 839）。其中肺炎支原體合并乙型流感病毒居首位，占陽性病例的5.00%（92/1 839），其次為肺炎支原體合并副流感病毒，占陽性病例的3.75%（69/1 839）。

位置更新公式(13)：

(13)

其中，random()為隨機函數，計算得值范圍為[0,1]。

然而這種計算方式已被劉建華[13]等學者證明：隨著迭代次數增加，其突變的隨機性會逐漸升高，在最終迭代次數時達到最大，使得后期需要收斂的結果產生了更多不確定性，不易收斂到全局最優值。

在此使用劉建華等學者改進的方法，將式(12)改為式(14)：

(14)

速度在原點左右對稱，為偶函數。速度為正時，概率函數遞增；速度為負時，概率函數遞減。

對應的位置變化公式由(13)改為式(15)～式(16)：

當vij<0時，

(15)

當vij>0時，

(16)

為避免s(vij)過于接近極值1，可通過vij∈[-vmax,vmax]進行限制。通過二進制映射關系，使得粒子群算法應用到二進制離散的K8s多pod部署問題。

對粒子進行初始化，其位置初始化過程，式(17)：

(17)

速度初始化公式(18)為

vij=vmin+random()×(vmax-vmin)

(18)

其中，vmin=-2,vmax=2。

3 實驗設計

3.1 實驗過程

實驗環境采用Kubernetes1.18，通過虛擬機的形式部署在PC上，集群中包括1個Master節點和3個用于負載Pod的Node節點。

構建4臺虛擬機作為Node節點，具體參數見表1。

表1 集群節點配置

部署Pod描述：本次部署選取應用場景最為豐富的網絡服務web應用，該應用使用SpringBoot開發，接受無參請求，通過循環從100到1的階乘計算，并在循環中進行當前結果的字符串拼接，并在計算完成后，存儲進入文件中，其結果會返回給前端。web應用打包為Docker鏡像，該Pod名稱成為test-forpso。

測試流程：通過yaml文件進行文件部署，鏡像在私有鏡像倉庫拉取，每個yaml文件中定義的Pod使用CPU、內存、磁盤的資源請求量見表2。

表2 Pod資源請求量

test-forpso部署數量為5個，依次遞增至50個，每次調度在提升數量的同時，刪除已部署的Pod，借此計算部署時間。

實驗中使用默認調度算法，PSO和Ku-PSO分別進行實驗，并對結果進行比較。

3.2 實驗結果分析

通過實驗，分別統計test-forpso不同部署個數的負載均衡度。結果如圖1所示。

圖1 負載均衡度對比

對比3種調度方法的負載均衡度，Ku-PSO明顯更為穩定，且隨著調度的Pod數目不斷增多的過程中，其全局尋優能力更為明顯，反觀PSO算法更容易陷入局部最優導致負載均衡度降低，而默認的調度方法在多Pod調度時無法觀察整個調度過程全局的特征，因而導致負載均衡度下降嚴重。

分別統計不同調度個數的時間消耗，結果如圖2所示。

圖2 調度時間消耗對比

對比3種調度方法的時間消耗，默認的調度算法由于調度過程較為簡單，時間消耗最少；PSO由于過程復雜，時間消耗最長；Ku-PSO由于改進了后期的收斂速度，使得時間消耗在多Pod調度時得到迅速收斂，較傳統的PSO算法消耗時間更短。

4 結束語

本文針對Kubernetes的默認調度算法中的不足進行改進，通過改進粒子群算法(PSO)得到Ku-PSO算法，使用二進制離散粒子群映射的方式將Ku-PSO應用于K8s多Pod部署過程中。Ku-PSO極大程度改善了經典粒子群算法中容易陷入局部最優的問題，通過調整慣性因子非線性變化，給予前期適應值較低的粒子更高的速度，防止陷入局部最優，使得迭代過程個體學習因子和社會學習因子權值動態調整，前期的全局尋優能力和后期的局部收斂速度均得到保證。實驗結果表明，使用Ku-PSO在保證集群負載均衡度和調度時間上都有非常不錯的表現。