基于博弈論-VIKOR的Kubernetes調度策略研究＊

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

(浙江理工大學計算機科學與技術學院，浙江 杭州 310000)

0 引言

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

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

針對上述問題，本文提出基于博弈論-VIKOR 的Kubernetes動態資源調度方法，解決Kubernetes集群中各節點因長時間工作而出現的集群負載不均衡、資源利用率不充分問題。選擇CPU、內存、網絡帶寬、磁盤IO 作為節點資源指標，運用博弈論中Nash 均衡權重計算方法得到AHP 與熵值法組合權重，應用在改進的VIKOR 多則妥協解排序算法中，該方法充分考慮節點指標權重與節點資源關系，從而提高集群資源均衡度與資源綜合利用率。

1 博弈論-VIKOR調度算法設計

1.1 層次分析法

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

步驟1 建立遞階層次結構模型

AHP 將決策問題分成目標層、準則層和方案層，建立遞階層次結構，本文在Kubernetes 集群服務節點負載研究的基礎上，選擇CPU、內存、網絡帶寬、磁盤IO 為資源指標，最終建立針對服務節點負載評價的遞階層次結構模型。

步驟2 構造兩兩比較判斷矩陣

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

步驟3 相對權重計算及一致性檢驗

對判斷矩陣A一致性檢驗，首先計算出判斷矩陣最大特征值λmax，計算出一致性檢驗標準，接著計算隨機一致性比率CR，即CR=CI/RI，RI為平均隨機一致性指標，一般認為CR<0.1，則具有滿意的一致性。

1.2 熵值法客觀權重

熵值法是一種客觀賦權法，它是利用各資源指標的離散程度來決定指標權重的方法。具體操作步驟如下。

步驟1 數據標準化處理

正向指標代表數值越高越好，負向指標代表數值越低越好，因此對于高低指標需要用不同的算法進行數據標準化處理。

步驟2 得到標準化矩陣

計算第j項指標下第i個樣本值占該指標的特征比重：

步驟3 求解第j項指標(列)的熵值k

k的取值與本數n有關：

步驟4 求解第j項指標(列)的差異系數dj

步驟5 計算各項指標的權重W

1.3 改進VIKOR確定最優候選節點

VIKOR 方法是一種基于理想點解的多屬性決策方法，其根據群效用值、個體遺憾值[8]及綜合評價值，分別對方案進行排序。基于改進VIKOR 方法的節點打分步驟如下：

⑴構造博弈論賦權模型計算組合權重；

⑵改進VIKOR方法計算最優候選節點。

1.3.1 博弈論賦權模型

集群節點采用多資源指標，因此節點資源的權重在Pod 調度中起著至關重要的作用，利用博弈論Nash均衡研究AHP 與熵值法權重的協調作用[9]，尋求兩者的最優解，降低主觀偏頗，增強賦權的科學性。該方法具體步驟如下：

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

步驟1 任意向量線性組合

設基本權重向量集uk={uk1,uk2,uk3,‥,ukn},(k=(1,2,…,L),即構造出{u1,u2,…,un} 權重集，n為資源評價指標數量，L為權重計算方法個數，本文中L=2。設線性組合權重系數a={α1,α2,…,αL}。記L個權重向量uk的任意線性組合為：

步驟2 計算目標函數

尋求不同權重之間的一致和妥協，對式⑽中L個線性權重組合系數ak進行優化，優化的目標是使與u各個uk的離差的極小化，對策模型如下：

從而得到與之對應的線性方程組，對應的線性方程組為：

步驟3 計算組合權重

將計算得到的優化組合系數ak進行歸一化處理得到，最后得到博弈論組合賦權的權重u*={u1,u2,…,un}

1.3.2 改進VIKOR確定最優候選節點

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

⑵確定指標集的正理想解r+和負理想解r?，計算公式為：

其中，max vij和min vij分別為歸一化后第j 個指標的最大值與最小值，n為資源指標總個數。

⑶計算資源指標集群體效用值Si值和個體遺憾值Ri值，計算公式為：

其中，u*為經博弈論組合賦權后的權重值。

⑷計算利益比率Q值

其中，lambda為算法決策機制系數，該值默認是0.5。

⑸根據評價值Qi的大小進行排序和優選，即對Kubernetes 節點進行排序，Qi值越小，說明節點綜合效益越高，排名越靠前，Qi越大，說明節點綜合效益越低，最終根據排序進行任務調度。

2 實驗設計與結果分析

2.1 實驗環境與實驗設計

2.1.1 實驗環境

實驗在ContainerCloudSim[10]仿真環境下，搭建Kubernetes 集群進行仿真，其中Kubernetes 使用v1.18.0 版本，Docker 使用v18.06.1 版本，集群中部署5 個物理節點，其中1 個Master 節點，4 個Node 節點，集群中所有節點運行一個node-exporter-1.1.2 負責采集指標數據，Master 節點運行Grafana-7.2.1 和Prometheus-2.15.0容器，負責存儲和可視化指標數據，每臺虛擬機的具體配置如表1所示。

表1 節點資源信息

2.1.2 實驗設計

在上述Kubernetes 集群中，分別采用Kubernetes默認調度算法與本文提出的基于博弈論-VIKOR 算法（GTV），從資源均衡度、資源利用率兩個角度對比。本次實驗準備300 個測試應用Pod，充分考慮到節點CPU、內存、網絡帶寬、磁盤IO 的權重占比情況，具體實驗過程如下：①初始化Kubernetes 集群，向集群的ApiServer 連續發布60 個Pod 任務，之后每隔1min 就向集群中發布60 個Pod 應用，直至發布300 個Pod。②等待部署完成并計算4 個節點的資源均衡度和資源利用率。③銷毀集群1，使用GTV 算法重新搭建K8s 集群，記作集群2，集群2 初始化與任務發布操作同集群1。④重復步驟②。⑤根據實驗結果，統計并對比兩組實驗資源均衡度和資源利用率。

2.2 實驗結果與分析

2.2.1 性能指標分析

對于衡量資源調度性能指標，本文從資源失衡度和綜合資源利用率兩個方面考慮。具體評價方式如下：

⑴集群資源失衡度

采用Std 標準差衡量集群中節點資源利用率的負載均衡差異，其中，U(i,t)為第i個節點t指標的資源利用率，average(i)表示集群中第i個節點資源平均利用率，StdAve為集群節點資源失衡度，StdAve越小表示集群資源中資源利用越均衡，計算公式如下：

⑵資源綜合利用率

取節點k中各個資源指標利用率的平均值作為該節點的資源綜合利用率，Uk為第k個節點的綜合利用率，取集群所有節點綜合利用率平均值作為集群綜合利用率，計算公式如下：

2.2.2 集群資源失衡度分析

集群資源失衡度變化曲線如圖1 所示，當Pod 量小于60 時，集群負載均衡度良好，K8s 默認調度與GTV 調度機制的資源失衡度相差不大，隨著Pod 數量增加到100，GTV 動態調度機制發揮作用，由于GTV考慮了4種資源指標使用情況，并優化了指標權重，降低了集群中某一Node資源使用率高而其他Node出現大量資源剩余情況，集群中各節點的平均負載均衡度相較于Kubernetes 默認調度器提升了約11%，體現了GTV 算法在集群資源飽和的情況下可以有效地調節集群資源平衡度。

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

2.2.3 資源利用率分析

圖2對應K8s默認調度器與GTV算法調度器下的CPU 利用率情況與內存利用率情況，當部署的Pod 數量為60左右時，可見兩種算法機制在資源利用率穩定性上區別不大，隨著Pod 數量不斷增加，K8s 默認調度機制下會出現節點資源利用率不充分，有的節點并未被調度到任務，而GTV 調度機制下的節點資源利用率交錯提升，整體更穩定，說明Pod任務分別被調度到了不同節點。可見GTV 算法調度器在資源利用率方面穩定性優于K8s默認調度器。

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

3 結束語

本文對Kubernetes優選過程中的計算性能、權重、節點利用率等產生負載不均衡進行分析，改進VIKOR算法對其進行改進。通過監控容器應用采集各工作節點和Pod應用的資源使用情況，以納什均衡為基礎，使用層次分析法、熵值法為資源指標賦予較為客觀、準確的權重，在多任務請求時使用改進的VIKOR算法計算最優調度節點，并進行任務調度，實現任務動態分配。從實驗結果可以看出，本文的動態資源調度算法與Kubernetes 默認調度算法相比，在負載均衡方面更具有穩定性，資源利用率更高。考慮到集群中存在不同搶占級別Pod，本文將在現有研究基礎上，進一步結合資源類型進行深入研究。