基于負載均衡的 Kubernetes 改進優化算法研究

梁兆楷 高建明

摘要：為了改善Kubernetes資源調度算法的負載均衡性，針對傳統的Kubernetes默認調度算法只考慮了節點的CPU利用率和內存利用率，未考慮磁盤IO利用率和網絡帶寬利用率的問題，提出一種基于鴿群算法的 Kubernetes資源調度算法。選擇CPU、內存、磁盤IO和網絡帶寬平均資源利用率標準差作為適應度函數，通過鴿群算法的調度分配實現資源的最佳分配。研究結果表明，PIO-Kubernetes算法提高了集群負載能力，并且具有更強的并行處理能力。

關鍵詞：鴿群算法；負載均衡；Kubernetes；平均資源利用率

中圖分類號：TP391.9??????????? 文獻標志碼：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

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

為了改善Kubernetes資源調度算法的負載均衡性，提高電力系統處理信息能力，針對傳統的Kuber- netes默認調度算法只考慮了節點的CPU利用率和內存利用率，未考慮磁盤IO利用率和網絡帶寬利用率的問題，提出一種基于鴿群算法（PIO）的Kubernetes 資源調度算法。選擇鴿群算法作為Kubernetes資源調度算法，在計算適應度階段，選擇CPU、內存、磁盤IO 和網絡帶寬的平均資源利用率標準差作為適應度函數，通過鴿群算法的調度分配實現資源的最佳分配，進一步降低系統過載對元器件線路、硅脂、內存條的影響。

1 Kubernetes Scheduler調度算法

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

根據調度策略，Pod被 Scheduler部署到不同的節點中，Pod的分配模型如圖1所示。

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

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

2 鴿群算法（PIO）

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

2.1 指南針算子

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

式中：R 為指南針算子；Xi 和Vi 為第i只鴿子的速度和位置；rand為[0，1]的隨機數；Xg為鴿子最好位置。

2.2 地標算子

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

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

3 基于PIO-Kubernetes的資源調度算法

傳統的Kubernetes默認調度算法，只考慮了節點的CPU利用率和內存利用率，未考慮磁盤IO利用率和網絡帶寬利用率，無法均衡每個節點的負載。基于上述評估標準，本論文提出了提高硬盤 IO使用率及網路頻譜使用量的方法。

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

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

在實際應用部署中，不同類型的節點對評價指標的側重點不同，引入權重 W表征不同評價指標對節點負載的影響[9]。

式中：W（Cpui）、W（Memi）、W（Diski）和W（Neti）分別為CPU、內存、磁盤IO和網絡的權重。

為實現 Kubernetes集群的負載平衡，采用平均可用資源利用率標準差異作為確定的條件[10-13]。

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

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

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

因此，PIO優化Kubernetes集群負載均衡的適應度函數為（平均資源使用率標準差最小）：

基于PIO-Kubernetes的資源調度算法算法步驟如下：

Step1：算法初始化：設定種群規模Np、最大迭代次數Tmax、指南針因子R、指南針算子執行次數Nc1max、地標算子執行次數Nc2max。根據Pod分配模型，Kuber- netes調度問題可以看成0～1選擇問題，1表示Pod被分配在這個節點上；反之不分配給這個節點：

Step2：通過對每個鴿子的隨機定位和速度進行了隨機分析，發現并將其最優解進行了分析；

Step3：完成路標操作和羅盤操作。根據式（1）、（2）等式對鴿舍的定位及轉速進行了修正，再將各鴿群的適配性進行對比，發現并紀錄出最佳最佳方案；

Step4：如果重復操作的數量超過了指北針操作的最大數目，就會終止目前的循環，這時進行地標操作，或者跳到Step3；

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

Step6：判斷算法終止條件。若算法超過最大迭代次數Tmax，則輸出最佳位置，最佳位置對應Kubernetes 的最佳資源調度分配方案；否則，跳轉至Step5。

4 實驗分析

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

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

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

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

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

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

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

5 結語

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

【參考文獻】

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

[2] 徐正倫，楊鶴標.基于Kubernetes調度器的服務質量優化調度算法研究[J].軟件導刊，2018，17（11）：73-76

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

[4] 林博，張惠民.邊緣計算環境下基于動態反饋的 Kuber- netes 調度算法[J].信息技術與信息化，2019（10）：101-103

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

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

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

[8] 張文輝，王子辰.基于組合權重TOPSIS的Kubernetes調度算法[J].計算機系統應用，2022，31（1）：195-203.

[9] 胡程鵬，薛濤.基于遺傳算法的Kubernetes資源調度算法[J].計算機系統應用，2021，30（9）：152-160

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

[11] 郝曉培，單杏花，李永，等.基于Kubernetes的鐵路客運營銷深度學習平臺的設計與實現[J].鐵路計算機應用，2021，30（1）：57-61.

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

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

[14] 劉剛，朱林，祁升龍，等.基于拓撲結構變化的配電網自適應保護方法[J].電力科學與技術學報，2022，37（1）：106-112.

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

[16] 汪偉，于洋.基于ASON的電力系統調度數據網業務體系設計[J].機械與電子.2022，40（3）：17-20.

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

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

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

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