Kubernetes集群中多節點合作博弈負載均衡策略

李華東，張學亮，王曉磊，劉 惠，王鵬程，杜軍朝

(1.西安電子科技大學 計算機科學與技術學院，陜西 西安 710071；2.中國電子科技集團公司 航天信息應用技術重點實驗室，河北 石家莊 050081；3.中國電子科技集團公司 第五十四研究所，河北 石家莊 050081)

隨著云計算技術的飛速發展，虛擬機技術將操作系統與硬件分離，實現了物理資源的按需分配，然而虛擬機不能很好地適應當今應用所需的輕量級、高敏捷、可遷移等需求[1]。Docker為代表的容器技術以其跨平臺、可移植、易用性等特點被廣泛接受，改變了現有分布式應用的架構、部署及管理方式[2]。由此催生了一系列的容器編排和管理工具：Flynn、Deis和Fleet等。Flynn和Deis由于主要參考了PaaS(Platform as Service)層的架構、功能和設計理念，對整個軟件環境的控制力存在較大的限制，而單純依靠Fleet編排部署系統不能很好地提供云計算服務。由Google公司開源的容器編排系統Kubernetes，因其優秀的容器部署、運維、管理能力而成為業界容器編排系統的首選[3]。

針對Kubernetes集群，已有一些工作圍繞資源利用率、服務質量、資源成本、維護開銷、節點性能展開[4-9]。雖然負載均衡的研究已經有大量工作[10-11]，但是針對Kubernetes集群資源負載均衡的研究工作較少，而在實際大規模Kubernetes集群中，往往會因為調度不均衡導致存在資源碎片現象，造成集群整體的成本損耗。因此，如何設計能確保集群資源負載均衡度這個指標的調度器，以降低集群資源碎片化程度和集群成本，具有實際重要意義。

對此，文獻[12]和文獻[13]設計了負載平衡器和多集群作業調度器，使集群間資源的平均利用率趨于平衡。但是它們屬于靜態資源調度算法，沒有考慮服務請求資源與Pod實際使用資源可能會不一致這種在真實應用場景中存在的現象。文獻[14]和文獻[15]均提出了動態資源調度算法。該算法通過對節點資源使用情況進行實時監控并計算優先級，改進后的算法提高了集群資源的負載均衡程度。但是僅考慮了CPU和內存兩種資源。同樣地，文獻[16]提出了一種領導者選舉算法。該算法通過將領導者均勻分布在集群中的節點上來克服網絡瓶頸問題。但是僅考慮了網絡流量的負載均衡。上述工作只針對一兩種資源間的負載均衡，在多資源負載均衡方面的研究還處于空白，而在真實應用統一調度場景中，這些資源之間不能孤立看待。所以筆者認為在實際調度中應考慮更多的必要因素。

綜上所述，筆者對 Kube-scheduler 進行了優化和擴展，提出一種將合作博弈論與服務調度和集群資源負載均衡相結合的調度算法。主要貢獻如下：

(1)設計了Kubernetes集群動態資源調度管理平臺，通過監控組件實時獲取服務資源使用情況，避免了服務請求資源與Pod實際使用資源不一致的問題。

(2)提出了一種基于合作博弈論的多資源負載均衡(Multi-resource load Balancing algorithm based on Cooperative Game Theory，MBCGT)算法，充分考慮CPU、內存、網絡帶寬以及磁盤IO資源之間的負載均衡，建立節點間的合作博弈模型，提高集整體負載均衡程度，減少了集群資源碎片，降低了集群成本。

(3)利用MBCGT算法對 Kube-scheduler 進行了優化和擴展，使其在不同場景下依然能穩定、高效地調度各種類型的復雜工作負載。

1 相關知識

Kubernetes Scheduler是Kubernetes系統的核心組件之一，負責整個集群Pod資源對象的調度。其根據內置或擴展的調度算法(預選與優選調度算法)，將待調度Pod資源對象調度到最優工作節點上，從而更加合理充分地利用集群的資源，同時提高應用運行效率。

BalancedResourceAllocation算法[17]是Kubernetes默認的負載均衡算法。該算法的目的是從候選節點中選出各項資源利用率最均衡的節點。其計算方法可表示為

(1)

其中，Φcpu表示所有備選節點上運行的Pod和待調度Pod的總CPU占用量，Ωcpu為節點的CPU計算能力，Φmem表示所有備選節點上運行的Pod和待調度Pod的總內存占用量，Ωmem為節點的內存大小。該算法對節點打分所使用的CPU和內存占用量是根據待調度Pod的預請求量來計算的。然而，Pod的資源預請求量和實際運行時Pod對資源的使用情況并不一致，導致該打分方法存在較大的誤差。因此節點資源均衡度調度算法有待改進。

2 系統建模

本節給出系統建模：集群資源建模針對Kubernetes集群中節點資源信息進行描述；任務建模針對每個任務所需資源信息進行建模；基于上述建模給出資源均衡度評估模型的建模和節點得分計算公式；最后整合各種任務調度場景抽象出集群資源負載均衡的問題定義，并給出該問題的解決算法。

2.1 Kubernetes集群資源建模

2.2 任務建模

2.3 節點資源均衡度評估模型建模

在給出Kubernetes集群資源建模和任務建模后，本節給出節點資源均衡度評估模型的建模，并計算出將Pod調度到相應節點上的得分。

定義資源均衡度這個物理量來衡量CPU、內存、網絡、磁盤IO的資源使用率相差程度。資源均衡度越大，則資源碎片化程度越大；資源均衡度值越小，則資源碎片化程度越小。下面給出資源均衡度的計算公式：

(2)

其中，μij為任務j調度到節點i上時，節點i資源的總體均值：

(3)

(4)

其中，τij表示一個二進制決策變量，如果任務j調度到節點i上，則τij=1成立；否則，τij=0成立。

根據以上模型，節點i的打分公式定義如下：

(5)

2.4 基于合作博弈論的多資源負載均衡調度算法

2.3節給出了節點資源均衡度評估模型的建模。本節整合各種任務調度場景來抽象出集群資源負載均衡問題的定義，并給出該問題的解決算法。

問題定義：給定一個或多個獨立任務P，通過自定義調度算法，求出每個任務最優的選擇節點以及資源負載均衡度，在保證集群中單個節點資源使用負載均衡的同時，最大化集群整體資源負載均衡度。

針對上述問題，引入了合作博弈論模型[18]。博弈論被廣泛應用于邊緣卸載[19]、異構網絡[20]以及車聯網[21]等領域。合作博弈論，也稱正和博弈，是指博弈雙方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受損害，從而達到整體利益增加。這十分切合文中的問題模型。

將集群中的節點N={n1，n2，n3，…，ni，…，nn}與待調度的任務P={p1，p2，p3，…，pj，…，pm}之間形式化為一個合作博弈。在該合作博弈中，博弈者是進行任務編排的節點。經過若干輪博弈后，n個博弈者將達成互贏，稱為納什討價還價解決方案[22]。此時集群中每個節點間期望負載均衡的公平性達到最大，且集群整體負載均衡也達到最優。

一個合作博弈通常表示為最大化博弈者效用函數的乘積。在本節研究的問題中，節點ni的效用函數如式(5)所示，其表明一個節點的各資源利用率的方差越大，即節點中資源碎片化程度越大，則該節點的效用函數值越小。

因此，基于合作博弈論的多資源負載均衡調度算法的目標函數可以定義為

(6)

s.t.τij=0，1 ，

(7)

(8)

(9)

(10)

(11)

(12)

(13)

基于式(2)～(13)，筆者提出的MBCGT算法如下。

MBCGT算法：基于合作博弈論的多資源負載均衡算法。

輸入：任務P={p1，p2，p3，…，pj，…，pm}，集群節點N={n1，n2，n3，…，ni，…，nn}。

forj=1 tondo

步驟2 求出滿足約束式(9)～(12)的節點N°，如果沒有滿足約束的節點，則算法結束；反之，繼續執行。

end for

在MBCGT算法中，步驟1利用監控組件可以求出集群中所有節點的剩余計算能力，為任務調度提供參考。步驟2用于檢測節點是否符合任務部署的約束條件，即保證任務調度到相應節點上的可用性。步驟3根據目標函數求出最優的節點選擇策略，在保證集群中單個節點資源使用負載均衡的同時，提高集群整體資源負載均衡的程度。步驟4根據最終的調度選擇求出最終的資源負載均衡度。

3 實驗結果及分析

3.1 實驗環境

實驗基于x86架構的OpenStack集群創建6臺虛擬機作為集群節點，其中包含1臺master節點、1臺監控節點和4臺node節點。而虛擬主機配置主要參考了當今云服務器提供商(阿里云、華為云等)的主流云服務器硬件配置，具有代表性。集群節點的詳細配置如表1所示。

表1 集群節點配置

實驗使用版本為v1.18.0的Kubernetes和版本為v18.06.1-ce的Docker搭建實驗基礎平臺。使用node_exporter-1.1.2軟件實時采集集群中各節點的數據，然后用Prometheus-2.26.0將各節點采集的數據作進一步的匯總，最終用Grafana-7.3.5將匯總的數據進行可視化展示。本次實驗使用Stress壓力測試軟件模擬真實應用，其鏡像版本為polinux/stress：latest。

3.2 實驗結果及分析

為了更好地驗證MBCGT算法在實際生產環境下集群負載均衡度的提升，以及使用監控實時獲取服務資源使用情況的優勢，實驗準備了12個測試應用。其中，涵蓋了計算密集型任務、內存密集型任務、網絡帶寬以及磁盤IO密集型任務，分別啟動12個Pod運行在Kubernetes集群中。測試Pod的資源請求量如表2所示。

表2 Pod資源請求量

使用所提出的MBCGT算法，設計了MBCGT算法調度器，為了更好地驗證該調度器的優勢，防止實驗的偶然性，共進行了3組對比實驗，每組實驗按照不同的部署順序各進行了5次實驗。取5次實驗結果的平均值作為每組實驗負載均衡度的對比，使實驗結果更具有說服力。每次實驗分別與Kubernetes的默認調度器以及動態資源調度器[12]進行比較，其中動態資源調度器相較于文獻[13]的調度器在服務部署時間以及節點資源負載均衡方面具有更好的效果。

實驗統計了每次調度完成后集群最終的資源均衡度和資源利用率，并統計每5次實驗集群負載均衡度的平均值作為每組實驗的負載均衡度。3組實驗的對比結果如表3所示。

表3 集群資源負載均衡度對比

從表3可以看出，使用MBCGT算法調度器，集群中各節點的平均負載均衡度相較于Kubernetes默認調度器分別提升了約8.15%、8.40%、6.31%；相較于動態資源調度器[12]分別提升了約7.41%、8.22%、5.88%，這說明CPU、內存、網絡以及磁盤IO的資源利用率更均衡。由于Kubernetes默認調度器和動態資源調度器[12]只考慮CPU和內存兩種資源進行任務調度，而實際的應用場景下，任務往往包含對網絡帶寬的訪問以及磁盤IO的讀寫需求，所以在進行任務調度時，集群中4種資源的負載均衡度往往出現波動。而MBCGT算法調度器充分考慮4種資源，提升了算法的魯棒性，使得該算法在實際應用場景中更具有穩定性。

根據實時監控，可得到各個測試Node節點在分別使用Kubernetes默認調度器、動態資源調度器[12]和MBCGT算法調度器時在資源利用率方面的對比圖，如圖1所示。

(a)node 1

圖1中4個分圖分別給出了3種調度器在調度完成后集群中4個節點(node)的CPU、內存、磁盤和網絡的資源利用率。由圖可以直觀看出，采用MBCGT算法調度器使得集群中各個節點的各類資源的資源利用率更加均衡，負載均衡程度更高。

4 結束語

由于實際任務對各資源需求量相差很大，所以集群中節點往往由于單個資源耗竭而導致任務無法部署；此時集群中節點存在大量的資源碎片無法被充分利用，用戶只能購買新的節點來滿足任務需求。為此，針對當今Kubernetes負載均衡算法中所使用的CPU和內存占用量是根據待調度Pod的請求量計算求得，與Pod實際資源使用情況不相同的問題，以及僅考慮CPU和內存兩種資源不充分的問題，筆者提出了MBCGT算法。通過監控組件實時獲取服務資源使用情況，并且充分考慮CPU、內存、網絡帶寬以及磁盤IO資源之間的負載均衡，建立了節點之間的合作博弈模型，在保證集群中單個節點資源使用負載均衡的同時，最大化集群整體資源負載均衡的程度，從而最大化減少資源碎片化程度，使系統具有更加均衡的資源節點，去服務于創建的任務，減少資源成本損耗。