梁兆楷 高建明

摘要：為了改善Kubernetes資源調(diào)度算法的負(fù)載均衡性，針對傳統(tǒng)的Kubernetes默認(rèn)調(diào)度算法只考慮了節(jié)點的CPU利用率和內(nèi)存利用率，未考慮磁盤IO利用率和網(wǎng)絡(luò)帶寬利用率的問題，提出一種基于鴿群算法的 Kubernetes資源調(diào)度算法。選擇CPU、內(nèi)存、磁盤IO和網(wǎng)絡(luò)帶寬平均資源利用率標(biāo)準(zhǔn)差作為適應(yīng)度函數(shù)，通過鴿群算法的調(diào)度分配實現(xiàn)資源的最佳分配。研究結(jié)果表明，PIO-Kubernetes算法提高了集群負(fù)載能力，并且具有更強的并行處理能力。

關(guān)鍵詞：鴿群算法；負(fù)載均衡；Kubernetes；平均資源利用率

中圖分類號：TP391.9??????????? 文獻標(biāo)志碼：A?????????? 文章編號：1001-5922（2023）03-0192-05

Study on? Kubernetes improved optimization algorithm based? on? load? balancing

LIANG Zhaokai1，GAO Jianming2

（1. Guangzhou Power Supply Bureau of Guangzhou Power Grid Co.，Ltd.，Guangzhou 510000，Chian；2. China Southern Digital Power Grid Technology（Guangdong）Co.，Ltd.，Guangzhou 510000，Chian）

Abstract： The default scheduling mechanism of Kubernetes only considers the resource utilization of CPU and memory of a single node，but does not consider the resource utilization of disk IO and network bandwidth. In order to balance the load of the whole cluster，a Kubernetes resource scheduling algorithm based on pigeon flock algo- rithm is proposed. The standard deviation of average resource utilization of CPU，memory，disk IO and network bandwidth was selected as the fitness function，and the optimal resource allocation was achieved through the sched- uling and allocation of pigeon swarm algorithm. The results show that the PIO-Kubernetes algorithm improves the cluster load capacity and has stronger parallel processing ability.

Keywords： pigeon-inspired optimization algorithm；load balancing；kubernetes；average resource utilization

隨著我國用電量持續(xù)增加，我國電力系統(tǒng)始終處于高負(fù)荷工作狀況，其主要原因為電力系統(tǒng)無法有效承受集群負(fù)載能力，易使電腦系統(tǒng)崩潰，且長期的高負(fù)荷工作也會使電腦CPU運行溫度高，導(dǎo)致線路老化，硅脂材料開裂。且硅脂開裂易使傳統(tǒng)導(dǎo)熱填料以金屬粉體、氧化物、碳化物、氮化物等為主的材料發(fā)生變化。伴隨著隨著互聯(lián)網(wǎng)的快速普及以及網(wǎng)絡(luò)應(yīng)用規(guī)模的不斷擴大，服務(wù)器產(chǎn)生的數(shù)據(jù)量呈現(xiàn)指數(shù)級增長，使得云計算技術(shù)得到了快速發(fā)展和應(yīng)用。云計算是分布式計算的一種，通過網(wǎng)絡(luò)“云”將豐富的網(wǎng)絡(luò)數(shù)據(jù)資源進行統(tǒng)一分析、處理、計算、管理和調(diào)度，可以極大提高電腦系統(tǒng)運行效率，減少電腦內(nèi)部材料老化及損傷，且由于長時間受到高溫影響破壞，從而導(dǎo)致防護層的損壞，進而導(dǎo)致絕緣材料性能下降。在云計算模式下，軟件、硬件和平臺等網(wǎng)絡(luò)資源以服務(wù)的方式提供給使用者，有效解決用戶基礎(chǔ)設(shè)施建設(shè)和系統(tǒng)維護成本高、效率低下以及網(wǎng)絡(luò)資源的利用不均的問題[1]。傳統(tǒng)云計算架構(gòu)中基礎(chǔ)設(shè)施即服務(wù)（IaaS）在虛擬機上作為基礎(chǔ)單元來安排資源分配，但是，虛擬機的計劃是一種粗粒度的資源分配方式，其運行速度較慢[2-3]。隨著 Docker容器技術(shù)的快速發(fā)展，以容器為基礎(chǔ)的虛擬化技術(shù)已經(jīng)逐漸被云計算開發(fā)者和云服務(wù)提供商所青睞。容器技術(shù)相對于虛擬機來說節(jié)省了資源、啟動速度快、鏡像小以及應(yīng)用部署靈活等優(yōu)點[4]，可以降低電力系統(tǒng)負(fù)載能力，減少系統(tǒng)硬件元器損傷，同時，電荷的聚集、渦流、絕緣介質(zhì)的損耗，都會產(chǎn)生額外的熱量，導(dǎo)致系統(tǒng)線路的溫度上升。長時間的超負(fù)荷運轉(zhuǎn)，高溫會使絕緣加速老化，最終導(dǎo)致絕緣破裂。然而，實際工作中需要管理的容器數(shù)量較為龐大且容器之間的關(guān)系相當(dāng)復(fù)雜，一般會使用某個工具對數(shù)量龐大的容器進行編排、管理和控制，其中以Kubernetes[5]為代表的容器編排工具是當(dāng)前較為熱門的編排管理工具。

為了改善Kubernetes資源調(diào)度算法的負(fù)載均衡性，提高電力系統(tǒng)處理信息能力，針對傳統(tǒng)的Kuber- netes默認(rèn)調(diào)度算法只考慮了節(jié)點的CPU利用率和內(nèi)存利用率，未考慮磁盤IO利用率和網(wǎng)絡(luò)帶寬利用率的問題，提出一種基于鴿群算法（PIO）的Kubernetes 資源調(diào)度算法。選擇鴿群算法作為Kubernetes資源調(diào)度算法，在計算適應(yīng)度階段，選擇CPU、內(nèi)存、磁盤IO 和網(wǎng)絡(luò)帶寬的平均資源利用率標(biāo)準(zhǔn)差作為適應(yīng)度函數(shù)，通過鴿群算法的調(diào)度分配實現(xiàn)資源的最佳分配，進一步降低系統(tǒng)過載對元器件線路、硅脂、內(nèi)存條的影響。

1 Kubernetes Scheduler調(diào)度算法

Kubernetes 資源調(diào)度的核心組件為 Kubernetes Scheduler。Kubernetes Scheduler 的主要功能是按照指定的調(diào)度算法將 Controller Manager 或 API Server 新建的待調(diào)度Pod綁定到集群中某個合適的工作節(jié)點，與此同時將待調(diào)度的Pod和工作節(jié)點的綁定信息寫入ETCD組件。之后，Kubernetes調(diào)度器發(fā)出的待調(diào)度Pod和工作節(jié)點的綁定信息由工作節(jié)點通過Kubelet監(jiān)測到，并從ETCD組件中讀取待調(diào)度Pod配置文件完成容器應(yīng)用的啟動。

根據(jù)調(diào)度策略，Pod被 Scheduler部署到不同的節(jié)點中，Pod的分配模型如圖1所示。

假定系統(tǒng)中所有節(jié)點的集合為N=}Node1.Node2. Node3.….Nodenx，n 為節(jié)點總數(shù)，Nodei為第i個節(jié)點。系統(tǒng)中所有待調(diào)度 Pod 的集合為 N=}Pod1.Pod2.Pod3.….Podmx，m 為待調(diào)度 Pod總數(shù)，Podj為第j 個待調(diào)度 Pod。假設(shè)在某個工作節(jié)點Nodei上有一組Pod，工作節(jié)點中待調(diào)度Pod的分配情況可以用 C 表示，待調(diào)度 Pod 的分配情況 Ci =}Pod1.Pod2.Pod3.....Podk x ，k 為Nodei上待調(diào)度 Pod的數(shù)量。如圖1所示，將被調(diào)度 Pod的分布情況： C1={Pod1，Pod4}，C2={Pod3，Pod5}，C3={Pod2，Pod6}。

圖1描述了待調(diào)度Pod在工作節(jié)點的分配情況， Kubernetes默認(rèn)資源調(diào)度算法一般是將待調(diào)度Pod 分配到性能最好的工作節(jié)點上運行，增加了性能高的工作節(jié)點的負(fù)載，造成了性能簇的負(fù)載不平衡，導(dǎo)致了整個簇的服務(wù)品質(zhì)下降。通過對被調(diào)度 Pod和工作節(jié)點的配置關(guān)系的分析，可以看出，Kubernetes調(diào)度問題實際就是將m 個Pod分配到n 個節(jié)點中的排列組合問題，該問題是一個 NP-Hard 問題。針對 NP-Hard問題，啟發(fā)式算法是解決該類問題的主要方法之一。鴿群算法[6]是模仿鴿子歸巢行為而提出的群智能優(yōu)化算法，與其他智能算法相比，該算法具有調(diào)整參數(shù)少、原理簡單、魯棒性更強以及計算更加簡單的優(yōu)點，目前被廣泛地應(yīng)用于機器學(xué)習(xí)、參數(shù)優(yōu)化等領(lǐng)域。為了改善Kubernetes資源調(diào)度算法的負(fù)載均衡性，針對傳統(tǒng)的Kubernetes默認(rèn)調(diào)度算法只考慮了節(jié)點的CPU利用率和內(nèi)存利用率，未考慮磁盤IO利用率和網(wǎng)絡(luò)帶寬利用率的問題，最大限度地發(fā)揮每個節(jié)點的性能，選擇鴿群算法作為Kubernetes資源調(diào)度算法，引入網(wǎng)絡(luò)帶寬、磁盤 IO評估指數(shù)并給出各種權(quán)值，采用平均資源利用基準(zhǔn)差異作為適應(yīng)性函數(shù)，通過鴿群算法的調(diào)度分配實現(xiàn)資源的最佳分配。

2 鴿群算法（PIO）

當(dāng)距離目標(biāo)很遙遠(yuǎn)時，信鴿會借助地球磁場和路標(biāo)來抵達目標(biāo)。PIO算法中鴿子歸巢包含了地圖羅盤算子和路標(biāo)算子。在遠(yuǎn)離目標(biāo)地點時，通過地球磁場識別方位，在接近目標(biāo)地點時使用本地標(biāo)志。在 PIO中，利用地球的地磁與太陽為基礎(chǔ)建立了地圖與指示器的數(shù)學(xué)模型，而標(biāo)志算子的建立則是以地標(biāo)為基礎(chǔ)的。

2.1 指南針?biāo)阕?/p>

地圖模型是基于地磁場，第i只鴿子的速度和位置更新公式為[7]：

式中：R 為指南針?biāo)阕樱籜i 和Vi 為第i只鴿子的速度和位置；rand為[0，1]的隨機數(shù)；Xg為鴿子最好位置。

2.2 地標(biāo)算子

地標(biāo)算子模仿導(dǎo)航工具地標(biāo)對鴿子的影響。當(dāng)鴿群接近目的地時，會依靠臨近地標(biāo)進行導(dǎo)航。如果某只鴿子熟悉地標(biāo)，則徑直飛向目的地；反之，如果不熟悉地標(biāo)并且遠(yuǎn)離目的，則該只鴿子會跟隨熟悉地標(biāo)的其他鴿子飛行到達目的地。首先將鴿子的適應(yīng)度值排序，然后每次迭代對其種群數(shù)量減半，假設(shè)中心鴿子熟悉地形，可以直接飛向目的地，其他的鴿子都在中心鴿子的引領(lǐng)下，向著目的地前進。鴿群位置更新策略如下：

式（3）～式（5）中：Np （t）為第t 代鴿子種群規(guī)模；Xc（t）為第t 代所有鴿子的中心位置；fitness（x）為每只鴿子的質(zhì)量。

3 基于PIO-Kubernetes的資源調(diào)度算法

傳統(tǒng)的Kubernetes默認(rèn)調(diào)度算法，只考慮了節(jié)點的CPU利用率和內(nèi)存利用率，未考慮磁盤IO利用率和網(wǎng)絡(luò)帶寬利用率，無法均衡每個節(jié)點的負(fù)載。基于上述評估標(biāo)準(zhǔn)，本論文提出了提高硬盤 IO使用率及網(wǎng)路頻譜使用量的方法。

CPU 在特定節(jié)點上的利用率L（Cpui）定義如式（6）所示[8]：

式中：CpuPodij為第i個 Node節(jié)點上第j 個 Pod 的 CPU 使用量；PodNumi為第i個 Node 節(jié)點上 Pod 的總數(shù)。同理，可以計算出該 Node 上內(nèi)存的利用率L（Memi）、磁盤IO的利用率L（Diski）和網(wǎng)絡(luò)的利用率L（Neti），進而可以計算出該Node上的資源平均利用率：

在實際應(yīng)用部署中，不同類型的節(jié)點對評價指標(biāo)的側(cè)重點不同，引入權(quán)重 W表征不同評價指標(biāo)對節(jié)點負(fù)載的影響[9]。

式中：W（Cpui）、W（Memi）、W（Diski）和W（Neti）分別為CPU、內(nèi)存、磁盤IO和網(wǎng)絡(luò)的權(quán)重。

為實現(xiàn) Kubernetes集群的負(fù)載平衡，采用平均可用資源利用率標(biāo)準(zhǔn)差異作為確定的條件[10-13]。

首先，根據(jù)不同的分配方式，對資源的平均使用率L（Cluk）進行了計算：

式中：N為符合要求的可行解數(shù)量。

其次，根據(jù)不同Node上的資源評價利用率LN）和不同分配方案的資源平均使用率L（ Clus）。

因此，PIO優(yōu)化Kubernetes集群負(fù)載均衡的適應(yīng)度函數(shù)為（平均資源使用率標(biāo)準(zhǔn)差最?。?/p>

基于PIO-Kubernetes的資源調(diào)度算法算法步驟如下：

Step1：算法初始化：設(shè)定種群規(guī)模Np、最大迭代次數(shù)Tmax、指南針因子R、指南針?biāo)阕訄?zhí)行次數(shù)Nc1max、地標(biāo)算子執(zhí)行次數(shù)Nc2max。根據(jù)Pod分配模型，Kuber- netes調(diào)度問題可以看成0～1選擇問題，1表示Pod被分配在這個節(jié)點上；反之不分配給這個節(jié)點：

Step2：通過對每個鴿子的隨機定位和速度進行了隨機分析，發(fā)現(xiàn)并將其最優(yōu)解進行了分析；

Step3：完成路標(biāo)操作和羅盤操作。根據(jù)式（1）、（2）等式對鴿舍的定位及轉(zhuǎn)速進行了修正，再將各鴿群的適配性進行對比，發(fā)現(xiàn)并紀(jì)錄出最佳最佳方案；

Step4：如果重復(fù)操作的數(shù)量超過了指北針操作的最大數(shù)目，就會終止目前的循環(huán)，這時進行地標(biāo)操作，或者跳到Step3；

Step5：按鴿子的健康值對它們進行分類，按照式（3）～式（5）進行轉(zhuǎn)角操作，儲存最好的位置，并保留最好的解決方案；

Step6：判斷算法終止條件。若算法超過最大迭代次數(shù)Tmax，則輸出最佳位置，最佳位置對應(yīng)Kubernetes 的最佳資源調(diào)度分配方案；否則，跳轉(zhuǎn)至Step5。

4 實驗分析

為驗證PIO-Kubernetes進行資源調(diào)度的有效性和可靠性，通過虛擬機的方式部署在宿主機上，實驗采用 Kubernetes1.17。宿主機操作系統(tǒng)為Windows10系統(tǒng)，內(nèi)存為16 GB ，CPU為i7-8750H。

為了驗證 PIO-Kubernetes 算法的優(yōu)越性，將 PIO-Kubernetes 與 PSO-Kubernetes、GA-Kubernetes 和DE-Kubernetes相比，通用參數(shù)設(shè)置[14-17]：種群規(guī)模10，最大迭代次數(shù)100；粒子群算法（PSO）學(xué)習(xí)因子 c1=c2=2；PIO算法指南針因子R=0.5，指南針?biāo)阕訄?zhí)行次數(shù)Nc1max=80，地標(biāo)算子執(zhí)行次數(shù)Nc2max=20；遺傳算法（GA）交叉概率pc=0.7，變異概率pm=0.1；差分進化算法（DE）縮放因子CR=0.5，交叉概率pc=0.7，不同算法尋優(yōu)對比圖如圖2所示。由圖2可知，PIO-Kubernetes 具有更快的收斂速度和尋優(yōu)能力。

PIO-Kubernetes算法的并行計算效果如表1。

為了說明PIO-Kubernetes算法的并行性能，采用人工方式將原來數(shù)據(jù)擴充1000、2000、4000和8000倍，不同集群節(jié)點數(shù)的加速比 Speedup如圖3所示。文中分別取集群節(jié)點數(shù)4、8、16、32。

由圖3和表1可知，PIO-Kubernetes算法加速比隨著數(shù)據(jù)集的增大而接近于線性，并且數(shù)據(jù)量越大加速效果越好；此外隨著數(shù)據(jù)量的增大，加速比和并行效率也相應(yīng)增加，說明PIO-Kubernetes算法適合分布式存儲環(huán)境，具有良好的并行性能。

統(tǒng)計分析在120 s內(nèi)3個節(jié)點CPU、內(nèi)存、磁盤IO 和網(wǎng)絡(luò)帶寬的使用率[18-20]，對比 Kubernetes Schedule 算法和 PIO-Kubernetes 算法在不同性能節(jié)點上 CPU、內(nèi)存、磁盤IO和網(wǎng)絡(luò)帶寬等使用率均值，不同資源使用率對比如表2所示。

由表2可知，采用PIO-Kubernetes算法后，工作節(jié)點的工作負(fù)荷會更大，如高性能內(nèi)存工作節(jié)點 Node1使用 Kubernetes Schedule 算法和 PIO-Kuber- netes算法使用率分別為70.07%和78.50%，這是因為在高性能工作節(jié)點中，向其分配了較低的權(quán)重，減少了工作節(jié)點的負(fù)荷，并向其分配了更多的Pod。但是低性能內(nèi)存工作節(jié)點Node2使用Kubernetes Schedule 算法和PIO-Kubernetes算法使用率分別為39.61%和35.32%，表明采用PIO-Kubernetes方法可以有效地減少低工作結(jié)點的負(fù)荷。雖然高性能工作節(jié)點負(fù)載提高了，但因為工作結(jié)點具有良好的效能，所以沒有給工作結(jié)點帶來任何壓力。因此，與 Kubernetes Schedule方法相比較，PIO-Kubernetes方法能夠有效地改善簇的性能。

5 結(jié)語

在 Kubernetes 系統(tǒng)中，對于 Kubernetes 的缺省排序方法，僅從 CPU使用和存儲效率兩方面進行分析，以提高 Kubernetes的負(fù)荷平衡。未考慮磁盤IO利用率和網(wǎng)絡(luò)帶寬利用率的問題，最大限度地發(fā)揮每個工作節(jié)點的性能，選擇鴿群算法作為Kubernetes資源調(diào)度算法。在適配性階段，引入網(wǎng)絡(luò)帶寬、磁盤 IO 評估指數(shù)和不同的權(quán)值，采用平均的資源利用基準(zhǔn)差異作為適應(yīng)性的函數(shù)，通過鴿群算法的調(diào)度分配實現(xiàn)資源的最佳分配。研究結(jié)果表明，PIO-Kuber- netes算法提高了集群負(fù)載能力，并且具有更強的并行處理能力。然而，鴿群算法的初始種群是隨機產(chǎn)生的，導(dǎo)致初始種群分布均勻性較差，使得優(yōu)化時存在局部最優(yōu)問題，后續(xù)將改進鴿群算法進行Kubernetes 資源調(diào)度，提高模型的可靠性和精度。

【參考文獻】

[1] 孔德瑾，姚曉玲.面向5G邊緣計算的Kubernetes資源調(diào)度策略[J].計算機工程，2021（2）：32-38.

[2] 徐正倫，楊鶴標(biāo).基于Kubernetes調(diào)度器的服務(wù)質(zhì)量優(yōu)化調(diào)度算法研究[J].軟件導(dǎo)刊，2018，17（11）：73-76

[3] 羅鵬，李景文.基于PaaS環(huán)境的Kubernetes調(diào)度算法研究[J].中國新通信，2020，22（17）：43-45

[4] 林博，張惠民.邊緣計算環(huán)境下基于動態(tài)反饋的 Kuber- netes 調(diào)度算法[J].信息技術(shù)與信息化，2019（10）：101-103

[5] 譚莉，陶宏才.一種基于負(fù)載均衡的 Kubernetes調(diào)度改進算法[J].成都信息工程學(xué)院學(xué)報，2019，34（3）：228-231.

[6] 顧清華，孟倩倩.優(yōu)化復(fù)雜函數(shù)的粒子群-鴿群混合優(yōu)化算法[J].計算機工程與應(yīng)用，2019，55（22）：4-52.

[7] 尚志剛，王力，李蒙蒙，等.引入迷失探索與集群分裂機制的改進鴿群優(yōu)化算法[J].鄭州大學(xué)學(xué)報：工學(xué)版，2019（4）：25-31.

[8] 張文輝，王子辰.基于組合權(quán)重TOPSIS的Kubernetes調(diào)度算法[J].計算機系統(tǒng)應(yīng)用，2022，31（1）：195-203.

[9] 胡程鵬，薛濤.基于遺傳算法的Kubernetes資源調(diào)度算法[J].計算機系統(tǒng)應(yīng)用，2021，30（9）：152-160

[10] 李華東，張學(xué)亮，王曉磊，等. Kubernetes 集群中多節(jié)點合作博弈負(fù)載均衡策略[J].西安電子科技大學(xué)學(xué)報，2021，48（6）：16-22.

[11] 郝曉培，單杏花，李永，等.基于Kubernetes的鐵路客運營銷深度學(xué)習(xí)平臺的設(shè)計與實現(xiàn)[J].鐵路計算機應(yīng)用，2021，30（1）：57-61.

[12] 靳芳，龍娟.一種面向Kubernetes集群的網(wǎng)絡(luò)流量彈性管理方法[J].北京交通大學(xué)學(xué)報，2020，44（5）：77-86.

[13] 劉哲源，呂曉丹，蔣朝惠.基于模擬退火算法的粒子群優(yōu)化算法在容器調(diào)度中的應(yīng)用[J].計算機測量與控制，2021，29（12）：177-183.

[14] 劉剛，朱林，祁升龍，等.基于拓?fù)浣Y(jié)構(gòu)變化的配電網(wǎng)自適應(yīng)保護方法[J].電力科學(xué)與技術(shù)學(xué)報，2022，37（1）：106-112.

[15] 胡程平，陳婧，胡劍地，等.配電臺區(qū)線損率異常自動檢測系統(tǒng)設(shè)計[J].粘接，2022，49（5）：188-192.

[16] 汪偉，于洋.基于ASON的電力系統(tǒng)調(diào)度數(shù)據(jù)網(wǎng)業(yè)務(wù)體系設(shè)計[J].機械與電子.2022，40（3）：17-20.

[17] 周石金，何晉，楊凡，等. IIDG接入對配電網(wǎng)保護的影響分析[J].現(xiàn)代電子技術(shù).2021，44（17）：151-156.

[18] 何昕雷.基于模糊 PID 算法的自動控制研究[J].粘接，2022，49（3）：177-181.

[19] 董新濤，李文偉，李寶偉，等.基于補償零序壓差原理的110 kV 線路縱向故障保護方案[J].智慧電力，2022，50（9）：110-117.

[20] 謝珂，齊巖，李琛，等.基于測量阻抗加速的反時限過流保護新方案研究[J].能源與節(jié)能，2022（2）：109-112.