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

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

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

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

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

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

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

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

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

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

1 相關知識

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

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

(1)

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

2 系統(tǒng)建模

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

2.1 Kubernetes集群資源建模

2.2 任務建模

2.3 節(jié)點資源均衡度評估模型建模

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

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

(2)

其中，μij為任務j調(diào)度到節(jié)點i上時，節(jié)點i資源的總體均值：

(3)

(4)

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

根據(jù)以上模型，節(jié)點i的打分公式定義如下：

(5)

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

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

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

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

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

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

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

(6)

s.t.τij=0，1 ，

(7)

(8)

(9)

(10)

(11)

(12)

(13)

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

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

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

forj=1 tondo

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

end for

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

3 實驗結果及分析

3.1 實驗環(huán)境

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

表1 集群節(jié)點配置

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

3.2 實驗結果及分析

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

表2 Pod資源請求量

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

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

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

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

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

(a)node 1

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

4 結束語

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