陸威然，魯騰飛，趙恪振，姜 煜

(浙江理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310000)

0 引言

隨著云計(jì)算技術(shù)的不斷革新，以Docker 為代表的輕量虛擬化的容器技術(shù)[1]因其逐漸被業(yè)界認(rèn)可并廣泛使用。容器編排[2]和管理工具應(yīng)運(yùn)而生，其中Kubernetes 因其優(yōu)秀的容器編排能力和輕量開源的特點(diǎn)，從眾多容器編排工具中脫穎而出。在Kubernetes集群研究中，已經(jīng)有學(xué)者在應(yīng)用部署、應(yīng)用遷移、服務(wù)質(zhì)量等領(lǐng)域做了大量研究工作。但是針對(duì)Kubernetes集群負(fù)載均衡與資源利用率的研究較少。

對(duì)此，李華東[3]等人提出基于云計(jì)算資源調(diào)度的合作博弈模型，根據(jù)Pod 請(qǐng)求量計(jì)算CPU 和內(nèi)存占用量，最大程度地減少資源碎片化，但是未考慮資源指標(biāo)在調(diào)度中對(duì)資源傾斜的影響；左燦和劉曉潔[4]將Kubernetes 中的應(yīng)用分為CPU 需求型和內(nèi)存需求型，針對(duì)資源使用情況動(dòng)態(tài)匹配Pod 和節(jié)點(diǎn)，提高了集群節(jié)點(diǎn)CPU 和內(nèi)存使用均衡度，但是其只考慮了CPU和內(nèi)存的資源利用率,沒(méi)有考慮網(wǎng)絡(luò)和磁盤資源等資源消耗對(duì)集群調(diào)度的影響；Wei-guo Z[5]等人針對(duì)大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室使用場(chǎng)景，提出了一種蟻群算法與粒子群算法結(jié)合的動(dòng)態(tài)調(diào)度策略，但在異構(gòu)環(huán)境下對(duì)資源利用率考慮不充分；平凡[6]等提出重新計(jì)算CPU 和內(nèi)存資源分值，但當(dāng)負(fù)載節(jié)點(diǎn)數(shù)量非簡(jiǎn)單線性關(guān)系時(shí)，資源負(fù)載會(huì)出現(xiàn)傾斜情況；常旭征[7]等在Kubernetes調(diào)度策略加入磁盤和網(wǎng)絡(luò)兩個(gè)指標(biāo),提高了集群資源利用率,但未考慮資源指標(biāo)權(quán)重在多任務(wù)調(diào)度時(shí)對(duì)節(jié)點(diǎn)優(yōu)先級(jí)的影響。

針對(duì)上述問(wèn)題，本文提出基于博弈論-VIKOR 的Kubernetes動(dòng)態(tài)資源調(diào)度方法，解決Kubernetes集群中各節(jié)點(diǎn)因長(zhǎng)時(shí)間工作而出現(xiàn)的集群負(fù)載不均衡、資源利用率不充分問(wèn)題。選擇CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、磁盤IO 作為節(jié)點(diǎn)資源指標(biāo)，運(yùn)用博弈論中Nash 均衡權(quán)重計(jì)算方法得到AHP 與熵值法組合權(quán)重，應(yīng)用在改進(jìn)的VIKOR 多則妥協(xié)解排序算法中，該方法充分考慮節(jié)點(diǎn)指標(biāo)權(quán)重與節(jié)點(diǎn)資源關(guān)系，從而提高集群資源均衡度與資源綜合利用率。

1 博弈論-VIKOR調(diào)度算法設(shè)計(jì)

1.1 層次分析法

層次分析法（AHP）可以解決多個(gè)層級(jí)或多指標(biāo)的復(fù)雜問(wèn)題，權(quán)衡決策資源各方面因素。該方法可以很好地將人的決策思維分類、細(xì)化、對(duì)比，通過(guò)逐層分析獲得各指標(biāo)重要性權(quán)值，但這一方法難以排除主觀因素干擾，因此在本文需要與熵值法結(jié)合使用。在利用AHP 進(jìn)行負(fù)載評(píng)價(jià)量化的過(guò)程中，具體操作分三步：①建立相應(yīng)的遞階層次結(jié)構(gòu)模型；②構(gòu)造兩兩比較判斷矩陣；③計(jì)算權(quán)重并做一致性檢驗(yàn)。

步驟1 建立遞階層次結(jié)構(gòu)模型

AHP 將決策問(wèn)題分成目標(biāo)層、準(zhǔn)則層和方案層，建立遞階層次結(jié)構(gòu)，本文在Kubernetes 集群服務(wù)節(jié)點(diǎn)負(fù)載研究的基礎(chǔ)上，選擇CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、磁盤IO 為資源指標(biāo)，最終建立針對(duì)服務(wù)節(jié)點(diǎn)負(fù)載評(píng)價(jià)的遞階層次結(jié)構(gòu)模型。

步驟2 構(gòu)造兩兩比較判斷矩陣

采用1～9 標(biāo)度法，將各要素的相對(duì)重要程度進(jìn)行量化，從而構(gòu)造成對(duì)比較矩陣A=(aij)，其中aij表示i元素和j元素相對(duì)于目標(biāo)的重要值。

步驟3 相對(duì)權(quán)重計(jì)算及一致性檢驗(yàn)

對(duì)判斷矩陣A一致性檢驗(yàn)，首先計(jì)算出判斷矩陣最大特征值λmax，計(jì)算出一致性檢驗(yàn)標(biāo)準(zhǔn)，接著計(jì)算隨機(jī)一致性比率CR，即CR=CI/RI，RI為平均隨機(jī)一致性指標(biāo)，一般認(rèn)為CR<0.1，則具有滿意的一致性。

1.2 熵值法客觀權(quán)重

熵值法是一種客觀賦權(quán)法，它是利用各資源指標(biāo)的離散程度來(lái)決定指標(biāo)權(quán)重的方法。具體操作步驟如下。

步驟1 數(shù)據(jù)標(biāo)準(zhǔn)化處理

正向指標(biāo)代表數(shù)值越高越好，負(fù)向指標(biāo)代表數(shù)值越低越好，因此對(duì)于高低指標(biāo)需要用不同的算法進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理。

步驟2 得到標(biāo)準(zhǔn)化矩陣

計(jì)算第j項(xiàng)指標(biāo)下第i個(gè)樣本值占該指標(biāo)的特征比重：

步驟3 求解第j項(xiàng)指標(biāo)(列)的熵值k

k的取值與本數(shù)n有關(guān)：

步驟4 求解第j項(xiàng)指標(biāo)(列)的差異系數(shù)dj

步驟5 計(jì)算各項(xiàng)指標(biāo)的權(quán)重W

1.3 改進(jìn)VIKOR確定最優(yōu)候選節(jié)點(diǎn)

VIKOR 方法是一種基于理想點(diǎn)解的多屬性決策方法，其根據(jù)群效用值、個(gè)體遺憾值[8]及綜合評(píng)價(jià)值，分別對(duì)方案進(jìn)行排序?；诟倪M(jìn)VIKOR 方法的節(jié)點(diǎn)打分步驟如下：

⑴構(gòu)造博弈論賦權(quán)模型計(jì)算組合權(quán)重；

⑵改進(jìn)VIKOR方法計(jì)算最優(yōu)候選節(jié)點(diǎn)。

1.3.1 博弈論賦權(quán)模型

集群節(jié)點(diǎn)采用多資源指標(biāo)，因此節(jié)點(diǎn)資源的權(quán)重在Pod 調(diào)度中起著至關(guān)重要的作用，利用博弈論Nash均衡研究AHP 與熵值法權(quán)重的協(xié)調(diào)作用[9]，尋求兩者的最優(yōu)解，降低主觀偏頗，增強(qiáng)賦權(quán)的科學(xué)性。該方法具體步驟如下：

構(gòu)造博弈論賦權(quán)模型方法，設(shè)Y={y1,y2,y3,…,ym} 為不同計(jì)算權(quán)重方案集合，G={g1,g2,g3,…,gm} 為資源指標(biāo)的屬性集合，且{g1,g2,g3,‥,gm} 為各個(gè)資源指標(biāo)，U=(u1,u2,u3,…,um)T為資源指標(biāo)的權(quán)重集合，且{u1,u2,u3,…,um}為權(quán)重

步驟1 任意向量線性組合

設(shè)基本權(quán)重向量集uk={uk1,uk2,uk3,‥,ukn},(k=(1,2,…,L),即構(gòu)造出{u1,u2,…,un} 權(quán)重集，n為資源評(píng)價(jià)指標(biāo)數(shù)量，L為權(quán)重計(jì)算方法個(gè)數(shù)，本文中L=2。設(shè)線性組合權(quán)重系數(shù)a={α1,α2,…,αL}。記L個(gè)權(quán)重向量uk的任意線性組合為：

步驟2 計(jì)算目標(biāo)函數(shù)

尋求不同權(quán)重之間的一致和妥協(xié)，對(duì)式⑽中L個(gè)線性權(quán)重組合系數(shù)ak進(jìn)行優(yōu)化，優(yōu)化的目標(biāo)是使與u各個(gè)uk的離差的極小化，對(duì)策模型如下：

從而得到與之對(duì)應(yīng)的線性方程組，對(duì)應(yīng)的線性方程組為：

步驟3 計(jì)算組合權(quán)重

將計(jì)算得到的優(yōu)化組合系數(shù)ak進(jìn)行歸一化處理得到，最后得到博弈論組合賦權(quán)的權(quán)重u*={u1,u2,…,un}

1.3.2 改進(jìn)VIKOR確定最優(yōu)候選節(jié)點(diǎn)

⑴設(shè)初始化資源利用率矩陣為[tij]n×m，平方和歸一化，得到新歸一化矩陣V=[vij]n×m

⑵確定指標(biāo)集的正理想解r+和負(fù)理想解r?，計(jì)算公式為：

其中，max vij和min vij分別為歸一化后第j 個(gè)指標(biāo)的最大值與最小值，n為資源指標(biāo)總個(gè)數(shù)。

⑶計(jì)算資源指標(biāo)集群體效用值Si值和個(gè)體遺憾值Ri值，計(jì)算公式為：

其中，u*為經(jīng)博弈論組合賦權(quán)后的權(quán)重值。

⑷計(jì)算利益比率Q值

其中，lambda為算法決策機(jī)制系數(shù)，該值默認(rèn)是0.5。

⑸根據(jù)評(píng)價(jià)值Qi的大小進(jìn)行排序和優(yōu)選，即對(duì)Kubernetes 節(jié)點(diǎn)進(jìn)行排序，Qi值越小，說(shuō)明節(jié)點(diǎn)綜合效益越高，排名越靠前，Qi越大，說(shuō)明節(jié)點(diǎn)綜合效益越低，最終根據(jù)排序進(jìn)行任務(wù)調(diào)度。

2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)設(shè)計(jì)

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

實(shí)驗(yàn)在ContainerCloudSim[10]仿真環(huán)境下，搭建Kubernetes 集群進(jìn)行仿真，其中Kubernetes 使用v1.18.0 版本，Docker 使用v18.06.1 版本，集群中部署5 個(gè)物理節(jié)點(diǎn)，其中1 個(gè)Master 節(jié)點(diǎn)，4 個(gè)Node 節(jié)點(diǎn)，集群中所有節(jié)點(diǎn)運(yùn)行一個(gè)node-exporter-1.1.2 負(fù)責(zé)采集指標(biāo)數(shù)據(jù)，Master 節(jié)點(diǎn)運(yùn)行Grafana-7.2.1 和Prometheus-2.15.0容器，負(fù)責(zé)存儲(chǔ)和可視化指標(biāo)數(shù)據(jù)，每臺(tái)虛擬機(jī)的具體配置如表1所示。

表1 節(jié)點(diǎn)資源信息

2.1.2 實(shí)驗(yàn)設(shè)計(jì)

在上述Kubernetes 集群中，分別采用Kubernetes默認(rèn)調(diào)度算法與本文提出的基于博弈論-VIKOR 算法（GTV），從資源均衡度、資源利用率兩個(gè)角度對(duì)比。本次實(shí)驗(yàn)準(zhǔn)備300 個(gè)測(cè)試應(yīng)用Pod，充分考慮到節(jié)點(diǎn)CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、磁盤IO 的權(quán)重占比情況，具體實(shí)驗(yàn)過(guò)程如下：①初始化Kubernetes 集群，向集群的ApiServer 連續(xù)發(fā)布60 個(gè)Pod 任務(wù)，之后每隔1min 就向集群中發(fā)布60 個(gè)Pod 應(yīng)用，直至發(fā)布300 個(gè)Pod。②等待部署完成并計(jì)算4 個(gè)節(jié)點(diǎn)的資源均衡度和資源利用率。③銷毀集群1，使用GTV 算法重新搭建K8s 集群，記作集群2，集群2 初始化與任務(wù)發(fā)布操作同集群1。④重復(fù)步驟②。⑤根據(jù)實(shí)驗(yàn)結(jié)果，統(tǒng)計(jì)并對(duì)比兩組實(shí)驗(yàn)資源均衡度和資源利用率。

2.2 實(shí)驗(yàn)結(jié)果與分析

2.2.1 性能指標(biāo)分析

對(duì)于衡量資源調(diào)度性能指標(biāo)，本文從資源失衡度和綜合資源利用率兩個(gè)方面考慮。具體評(píng)價(jià)方式如下：

⑴集群資源失衡度

采用Std 標(biāo)準(zhǔn)差衡量集群中節(jié)點(diǎn)資源利用率的負(fù)載均衡差異，其中，U(i,t)為第i個(gè)節(jié)點(diǎn)t指標(biāo)的資源利用率，average(i)表示集群中第i個(gè)節(jié)點(diǎn)資源平均利用率，StdAve為集群節(jié)點(diǎn)資源失衡度，StdAve越小表示集群資源中資源利用越均衡，計(jì)算公式如下：

⑵資源綜合利用率

取節(jié)點(diǎn)k中各個(gè)資源指標(biāo)利用率的平均值作為該節(jié)點(diǎn)的資源綜合利用率，Uk為第k個(gè)節(jié)點(diǎn)的綜合利用率，取集群所有節(jié)點(diǎn)綜合利用率平均值作為集群綜合利用率，計(jì)算公式如下：

2.2.2 集群資源失衡度分析

集群資源失衡度變化曲線如圖1 所示，當(dāng)Pod 量小于60 時(shí)，集群負(fù)載均衡度良好，K8s 默認(rèn)調(diào)度與GTV 調(diào)度機(jī)制的資源失衡度相差不大，隨著Pod 數(shù)量增加到100，GTV 動(dòng)態(tài)調(diào)度機(jī)制發(fā)揮作用，由于GTV考慮了4種資源指標(biāo)使用情況，并優(yōu)化了指標(biāo)權(quán)重，降低了集群中某一Node資源使用率高而其他Node出現(xiàn)大量資源剩余情況，集群中各節(jié)點(diǎn)的平均負(fù)載均衡度相較于Kubernetes 默認(rèn)調(diào)度器提升了約11%，體現(xiàn)了GTV 算法在集群資源飽和的情況下可以有效地調(diào)節(jié)集群資源平衡度。

圖1 集群資源失衡度變化曲線

2.2.3 資源利用率分析

圖2對(duì)應(yīng)K8s默認(rèn)調(diào)度器與GTV算法調(diào)度器下的CPU 利用率情況與內(nèi)存利用率情況，當(dāng)部署的Pod 數(shù)量為60左右時(shí)，可見(jiàn)兩種算法機(jī)制在資源利用率穩(wěn)定性上區(qū)別不大，隨著Pod 數(shù)量不斷增加，K8s 默認(rèn)調(diào)度機(jī)制下會(huì)出現(xiàn)節(jié)點(diǎn)資源利用率不充分，有的節(jié)點(diǎn)并未被調(diào)度到任務(wù)，而GTV 調(diào)度機(jī)制下的節(jié)點(diǎn)資源利用率交錯(cuò)提升，整體更穩(wěn)定，說(shuō)明Pod任務(wù)分別被調(diào)度到了不同節(jié)點(diǎn)。可見(jiàn)GTV 算法調(diào)度器在資源利用率方面穩(wěn)定性優(yōu)于K8s默認(rèn)調(diào)度器。

圖2 不同策略下資源利用率

3 結(jié)束語(yǔ)

本文對(duì)Kubernetes優(yōu)選過(guò)程中的計(jì)算性能、權(quán)重、節(jié)點(diǎn)利用率等產(chǎn)生負(fù)載不均衡進(jìn)行分析，改進(jìn)VIKOR算法對(duì)其進(jìn)行改進(jìn)。通過(guò)監(jiān)控容器應(yīng)用采集各工作節(jié)點(diǎn)和Pod應(yīng)用的資源使用情況，以納什均衡為基礎(chǔ)，使用層次分析法、熵值法為資源指標(biāo)賦予較為客觀、準(zhǔn)確的權(quán)重，在多任務(wù)請(qǐng)求時(shí)使用改進(jìn)的VIKOR算法計(jì)算最優(yōu)調(diào)度節(jié)點(diǎn)，并進(jìn)行任務(wù)調(diào)度，實(shí)現(xiàn)任務(wù)動(dòng)態(tài)分配。從實(shí)驗(yàn)結(jié)果可以看出，本文的動(dòng)態(tài)資源調(diào)度算法與Kubernetes 默認(rèn)調(diào)度算法相比，在負(fù)載均衡方面更具有穩(wěn)定性，資源利用率更高。考慮到集群中存在不同搶占級(jí)別Pod，本文將在現(xiàn)有研究基礎(chǔ)上，進(jìn)一步結(jié)合資源類型進(jìn)行深入研究。