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

(1.西安電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710071；2.中國電子科技集團(tuán)公司 航天信息應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081；3.中國電子科技集團(tuán)公司 第五十四研究所，河北 石家莊 050081)

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

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

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

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

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

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

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

1 相關(guān)知識(shí)

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

BalancedResourceAllocation算法[17]是Kubernetes默認(rèn)的負(fù)載均衡算法。該算法的目的是從候選節(jié)點(diǎn)中選出各項(xiàng)資源利用率最均衡的節(jié)點(diǎn)。其計(jì)算方法可表示為

(1)

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

2 系統(tǒng)建模

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

2.1 Kubernetes集群資源建模

2.2 任務(wù)建模

2.3 節(jié)點(diǎn)資源均衡度評(píng)估模型建模

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

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

(2)

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

(3)

(4)

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

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

(5)

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

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

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

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

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

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

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

(6)

s.t.τij=0，1 ，

(7)

(8)

(9)

(10)

(11)

(12)

(13)

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

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

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

forj=1 tondo

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

end for

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

表2 Pod資源請(qǐng)求量

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

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

表3 集群資源負(fù)載均衡度對(duì)比

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

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

(a)node 1

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

4 結(jié)束語

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