胡程鵬,薛 濤

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,西安 710048)

1 引言

隨著互聯(lián)網(wǎng)規(guī)模的擴(kuò)大,服務(wù)器產(chǎn)生的海量數(shù)據(jù)促使云計(jì)算[1]的快速發(fā)展.云計(jì)算是指將大量用網(wǎng)絡(luò)連接的計(jì)算資源進(jìn)行統(tǒng)一管理和調(diào)度,構(gòu)成一個(gè)計(jì)算資源池向用戶提供服務(wù).通過云計(jì)算,可以合并組織現(xiàn)有的公司信息資源,并為其員工和合作伙伴提供通用的遠(yuǎn)程訪問權(quán)限[2].云計(jì)算的問題之一是對(duì)資源的利用不均.傳統(tǒng)云計(jì)算架構(gòu)中基礎(chǔ)設(shè)施及服務(wù)層(IaaS)的資源分配是以虛擬機(jī)為基本單位進(jìn)行調(diào)度,但是虛擬機(jī)的調(diào)度是一種粗粒度的資源調(diào)度,會(huì)出現(xiàn)調(diào)度緩慢等問題.

2013年,隨著Docker[3]等容器技術(shù)的快速發(fā)展,基于容器的虛擬化技術(shù)迅速成為各大云計(jì)算廠商和云計(jì)算開發(fā)者的首選.與虛擬機(jī)相比,容器技術(shù)具有鏡像小、資源消耗少、應(yīng)用部署靈活和啟動(dòng)速度快等優(yōu)點(diǎn)[4].大量的容器依托容器編排工具進(jìn)行管理和控制,其決定容器之間如何進(jìn)行交互.以Kubernetes[5]為代表的容器編排工具漸漸成為云原生的事實(shí)標(biāo)準(zhǔn),越來越多的微服務(wù)使用Kubernetes 進(jìn)行部署和管理.Kubernetes自動(dòng)化部署的功能可以使開發(fā)者輕松部署應(yīng)用,自動(dòng)化管理的功能可以讓定義好的服務(wù)一直按照用戶期望的狀態(tài)運(yùn)行,自動(dòng)擴(kuò)容縮容的功能讓服務(wù)器擁有的副本數(shù)量隨著用戶訪問負(fù)載的變化而增減成為可能.

Kubernetes的資源調(diào)度技術(shù)是云計(jì)算中的關(guān)鍵技術(shù),良好的資源調(diào)度策略可以使云服務(wù)提供商提高其資源利用效率,節(jié)約軟硬件成本,同時(shí)也可以讓用戶得到更優(yōu)質(zhì)的云服務(wù)體驗(yàn).目前,云計(jì)算資源調(diào)度領(lǐng)域的研究集中在兩個(gè)方向上[6]:一是根據(jù)各種指標(biāo)尋找最佳調(diào)度方案,并根據(jù)其周期性對(duì)收集的服務(wù)器負(fù)載統(tǒng)計(jì)信息進(jìn)行分析.此方法提供對(duì)云平臺(tái)的連續(xù)監(jiān)視和對(duì)其工作量的定期評(píng)估,基于此評(píng)估可以決定是否需要重新調(diào)度;二是根據(jù)服務(wù)器負(fù)載的周期性,使用機(jī)器學(xué)習(xí)方法和時(shí)間序列分析,如LSTM[7],通過分析收集的重要時(shí)期負(fù)載數(shù)據(jù),從而確定調(diào)度時(shí)機(jī).何龍等[8]實(shí)現(xiàn)了一種基于應(yīng)用歷史記錄的Kubernetes 調(diào)度算法,該方法實(shí)現(xiàn)簡單,對(duì)集群資源利用率有一定提高,但是其只考慮了CPU和內(nèi)存的資源利用率,諸如網(wǎng)絡(luò)和磁盤資源等方面的研究不足.常旭征等[9]針對(duì)Kubernetes僅考慮了CPU和內(nèi)存,加入了磁盤和網(wǎng)絡(luò)兩個(gè)指標(biāo),提高了集群資源利用率,但是并未考慮節(jié)點(diǎn)本身的性能指標(biāo).Kong 等[10]通過將時(shí)間和可靠性作為資源調(diào)度的目標(biāo),以模糊規(guī)則作為預(yù)測模型,提出了一種基于模糊規(guī)則預(yù)測的調(diào)度算法.李天宇[11]提出了一種基于強(qiáng)化學(xué)習(xí)的云計(jì)算虛擬機(jī)資源調(diào)度問題的解決方案和策略,采用Q 值[12]強(qiáng)化學(xué)習(xí)機(jī)制實(shí)現(xiàn)了虛擬機(jī)資源調(diào)度策略.雖然強(qiáng)化學(xué)習(xí)算法能動(dòng)態(tài)調(diào)整自身參數(shù)和網(wǎng)絡(luò)結(jié)構(gòu),擁有良好控制策略,但是模型訓(xùn)練本身需要占用大量資源.Kang[13]提出了容器代理系統(tǒng).該系統(tǒng)使用k-medoid 算法和分段算法來實(shí)現(xiàn)容器工作負(fù)載感知和節(jié)能,同時(shí)還保證了集群的資源利用率和負(fù)載均衡能力,但是此方法未考慮節(jié)點(diǎn)的網(wǎng)絡(luò)和磁盤等資源利用情況.Rao 等[14]提出一種分布式學(xué)習(xí)機(jī)制,將云資源分配視為一種分布式學(xué)習(xí)任務(wù),開發(fā)了一種增強(qiáng)學(xué)習(xí)算法并在iBallon 系統(tǒng)中對(duì)分布式學(xué)習(xí)算法進(jìn)行了原型設(shè)計(jì),但是該方法僅考慮單個(gè)虛擬機(jī)資源,忽略了集群的整體資源性能.Tsoumakos 等[15]提出了TIRAMOLA這一支持云的開源框架,它可以根據(jù)用戶定義的策略對(duì)NoSQL 集群進(jìn)行自動(dòng)調(diào)整大小,并且這一過程是實(shí)時(shí)進(jìn)行的,但是此框架只對(duì)NoSQL 集群效果顯著.

Kubernetes 默認(rèn)調(diào)度機(jī)制只考慮了單節(jié)點(diǎn)的資源利用率,未考慮整個(gè)集群的負(fù)載情況.因此,本文針對(duì)這一問題提出了一種基于遺傳算法的Kubernetes 資源調(diào)度算法.在種群初始階段,通過隨機(jī)方式初始化種群,引入校驗(yàn)字典對(duì)種群中的個(gè)體進(jìn)行校驗(yàn),同時(shí)修復(fù)不符合配置要求的個(gè)體;在計(jì)算適應(yīng)度值階段,將集群平均負(fù)載的標(biāo)準(zhǔn)差作為目標(biāo)函數(shù)值,標(biāo)準(zhǔn)差越小則表示集群負(fù)載越均衡;使用輪盤賭選擇方法選擇優(yōu)良個(gè)體進(jìn)入下一代,在交叉、變異操作后使用校驗(yàn)字典再次對(duì)種群中的個(gè)體進(jìn)行校驗(yàn)和修復(fù).

2 默認(rèn)調(diào)度算法分析

Kubernetes Scheduler是Kubernetes 資源調(diào)度的核心組件,其職責(zé)是將API Server 或Controller Manager新建的待調(diào)度Pod 根據(jù)指定的調(diào)度算法與集群中的某個(gè)合適的工作節(jié)點(diǎn)進(jìn)行綁定,并將Pod和節(jié)點(diǎn)的綁定信息寫入ETCD 中[16].而后工作節(jié)點(diǎn)通過守護(hù)進(jìn)程Kubelet 監(jiān)聽到Kubernetes 調(diào)度器發(fā)出的Pod和節(jié)點(diǎn)的綁定信息,并從ETCD 中獲取Pod 配置文件,最后根據(jù)配置文件完成容器應(yīng)用的啟動(dòng).

Kubernetes 調(diào)度器中的默認(rèn)調(diào)度算法分為3 個(gè)階段:預(yù)選階段(Predicates)、優(yōu)選階段(Priority)和選定階段(Select).Predicates 階段的工作是查詢集群中的所有節(jié)點(diǎn),根據(jù)Predicates的算法選擇適用的節(jié)點(diǎn)完成初篩.Priority 階段的工作是根據(jù)Priority 中的算法給Predicates 階段初篩的節(jié)點(diǎn)進(jìn)行評(píng)分,挑選出得分最高的節(jié)點(diǎn)作為調(diào)度的目標(biāo)節(jié)點(diǎn).

Predciates 階段要求滿足條件的節(jié)點(diǎn)必須通過所有篩選策略.下面介紹幾種策略的篩選內(nèi)容:

1)PodFitsHostPorts:檢查Pod 請(qǐng)求的端口是否空閑;

2)PodFitsHost:檢查Pod是否通過其主機(jī)名指定了特定的Node;

3)PodFitsResources:檢查節(jié)點(diǎn)是否有空閑資源(例如CPU和內(nèi)存)來滿足Pod的要求;

4)MatchNodeSelector:檢查Pod的節(jié)點(diǎn)選擇器是否匹配節(jié)點(diǎn)的標(biāo)簽;

5)CheckNodeMemoryPressure:如果節(jié)點(diǎn)正在報(bào)告內(nèi)存壓力,并且沒有配置的異常,則不會(huì)再此處分配Pod;

6)CheckNodeCondition:節(jié)點(diǎn)可以報(bào)告具有完全完整的文件系統(tǒng),網(wǎng)絡(luò)不可用或者Kubelet 尚未準(zhǔn)備好運(yùn)行的Pod.如果為節(jié)點(diǎn)設(shè)置了這樣的條件,并且沒有配置的異常,則不會(huì)在此處分配Pod.

優(yōu)選階段會(huì)根據(jù)優(yōu)選策略對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行打分,最終把Pod 調(diào)度到分值最高的節(jié)點(diǎn).Kube-Scheduler 用一組優(yōu)先級(jí)函數(shù)處理每個(gè)通過預(yù)選的節(jié)點(diǎn),每個(gè)函數(shù)返回0-10的分?jǐn)?shù),各個(gè)函數(shù)有不同權(quán)重,最終得分是所有優(yōu)先級(jí)函數(shù)的加權(quán)和,即節(jié)點(diǎn)得分的計(jì)算公式為:

式(1) 中,FinalScoreNode表示最終得分,weighti表示各個(gè)函數(shù)的權(quán)重值,priorityFunci表示具體的優(yōu)先級(jí)函數(shù)得分.

在Priority 階段的算法有:Least RequestedPriority、NodeAffinityPriority 等.下面說明這兩種算法:

1)Least RequestedPriority 算法默認(rèn)權(quán)重為1,此算法盡量將Pod 調(diào)度到計(jì)算資源占用比較小的節(jié)點(diǎn)上.此算法設(shè)計(jì)兩種計(jì)算資源:CPU和內(nèi)存.計(jì)算公式如下:

式(2)中,cpuCapacity表示候選節(jié)點(diǎn)CPU 資源的總量,cpuRequest表示Pod 需要的CPU 資源量,cpuS core表示根據(jù)CPU 指標(biāo)計(jì)算的得分.式(3)中,memoryCapacity表示候選節(jié)點(diǎn)內(nèi)存資源的總量,memoryRequest表示Pod 需要的內(nèi)存資源量,memoryS core表示根據(jù)內(nèi)存指標(biāo)計(jì)算的得分.式(4)中,leastS core表示使用Least RequestedPriority 算法獲得的得分.

2)NodeAffinityPriority 默認(rèn)權(quán)重為1,此算法盡量調(diào)度到標(biāo)簽匹配Pod 屬性要求的節(jié)點(diǎn),判斷行為與預(yù)選中的MatchNodeSelector 類似.該算法提供兩種選擇器:requiredDuringSchedulingIgnoredDuringExecution和preferredDuringSchedulingIgnoredDuringExecution.計(jì)算公式如下:

式(5)中,weighti表示節(jié)點(diǎn)滿足requiredDuringSchedulingIgnoredDuringExecution 中所有滿足條件的規(guī)則的權(quán)值,CountWeight表示preferredDuringSchedulingIgnoredDuringExecution 中所有規(guī)則的權(quán)值總和.nodeA f finityS core表示使用NodeAffinityPriority 算法獲得的得分.

在獲取了兩種算法對(duì)候選節(jié)點(diǎn)的評(píng)分后,Kubernetes調(diào)度器取兩種算法的加權(quán)平均值作為各個(gè)節(jié)點(diǎn)的最終評(píng)分:

通過分析Kubernetes 調(diào)度器的默認(rèn)算法可以發(fā)現(xiàn)其默認(rèn)算法對(duì)節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)中只考慮了CPU和內(nèi)存的使用率,沒有考慮磁盤IO和網(wǎng)絡(luò)帶寬的使用.并且Kubernetes 調(diào)度器是一種靜態(tài)調(diào)度策略,該調(diào)度機(jī)制雖然簡單,但是缺乏靈活性.且只能在Pod 初次部署時(shí)進(jìn)行資源配置.同時(shí),默認(rèn)調(diào)度策略只能保證單節(jié)點(diǎn)的服務(wù)質(zhì)量,未考慮整個(gè)集群的負(fù)載情況.從而導(dǎo)致集群資源利用率低.

3 Pod 分配模型與遺傳算法

Scheduler 根據(jù)調(diào)度策略將Pod 部署到不同的節(jié)點(diǎn)中,Pod在節(jié)點(diǎn)之間的分配模型如圖1所示,其可以說明Pod 與節(jié)點(diǎn)之間的相互關(guān)系.

圖1 Pod在Node的分配模型

假設(shè)N是系統(tǒng)中所有節(jié)點(diǎn)的集合,即N={Node1,Node2,Node3,…,Noden},n表示節(jié)點(diǎn)總數(shù),單一節(jié)點(diǎn)表示為Nodei,i表示節(jié)點(diǎn)編號(hào),i∈[1,n].假設(shè)P是系統(tǒng)中所有Pod的集合,即P={Pod1,Pod2,Pod3,…,Podm},m表示Pod 總數(shù),單一Pod 表示為Podj,j表示Pod 編號(hào),j∈[1,m].假設(shè)在某個(gè)節(jié)點(diǎn)Nodei上有一組Pod,使用C表示節(jié)點(diǎn)中Pod的分配情況,Ci={Pod1,Pod2,Pod3,…,Podk},k表示Nodei上Pod的數(shù)量.因此圖1中的分配情況表示為:C1={Pod1,Pod4},C2={Pod3,Pod5},C3={Pod2,Pod6}.

以上模型描述了Pod在節(jié)點(diǎn)上的分配結(jié)果,默認(rèn)資源調(diào)度模型盡力將待調(diào)度Pod 分配在性能最好的節(jié)點(diǎn)上運(yùn)行,這會(huì)導(dǎo)致集群節(jié)點(diǎn)的負(fù)載不均衡,集群整體服務(wù)質(zhì)量下降.通過分析Pod 與節(jié)點(diǎn)之間的分配關(guān)系,若將m個(gè)Pod 分配到n個(gè)節(jié)點(diǎn)中,根據(jù)排列組合可得出共有nm種情況[17],這是一個(gè)NP Hard 問題,在解決這類問題上,如果問題的固有知識(shí)不能被用來減少搜索空間,很容易產(chǎn)生搜索的組合爆炸.

針對(duì)NP Hard 問題,常用啟發(fā)式算法來解決,其中遺傳算法(GA)[18]是由Holland 教授于1975年提出的一種模擬生物進(jìn)化的全局搜索算法.遺傳算法具有智能、并行、自組織、可擴(kuò)展和易于使用的特點(diǎn).遺傳算法作為一種啟發(fā)式智能優(yōu)化搜索算法,經(jīng)常用來解決多目標(biāo)優(yōu)化的群體搜索問題.

4 改進(jìn)的遺傳算法

針對(duì)目前Kubernetes 調(diào)度算法只考慮單節(jié)點(diǎn)資源利用率,并未考慮集群整體負(fù)載均衡的問題,本文選擇遺傳算法作為資源調(diào)度算法:在計(jì)算適應(yīng)值階段,通過引入磁盤IO、網(wǎng)絡(luò)帶寬評(píng)價(jià)指標(biāo),并賦予指標(biāo)權(quán)重值,使用標(biāo)準(zhǔn)差衡量集群的負(fù)載均衡情況.在Kubernetes的yaml 配置文件中可以配置Pod 運(yùn)行的最低要求,如內(nèi)存至少為4 GB,最大為16 GB;磁盤空間至少為1 TB,最大為2 TB 等.同時(shí),Pod 擁有NodeAffinity和Taint 兩種屬性.在標(biāo)準(zhǔn)遺傳算法種群初始化階段、選擇階段、交叉階段和變異階段會(huì)產(chǎn)生不符合配置文件的個(gè)體,如將一個(gè)最低內(nèi)存配置為8 GB的Pod 分配給了內(nèi)存為4 GB的節(jié)點(diǎn).對(duì)這些個(gè)體進(jìn)行適應(yīng)度計(jì)算和下一階段操作都是無意義的,所以針對(duì)此問題對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行了改進(jìn):在初始種群生成階段、選擇階段、交叉階段和變異階段,通過引入校驗(yàn)字典對(duì)不符合配置的個(gè)體進(jìn)行校驗(yàn)和修復(fù).

4.1 種群初始化

4.1.1 編碼的確定

編碼是應(yīng)用遺傳算法時(shí)要解決的首要問題,也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵步驟.針對(duì)一個(gè)具體應(yīng)用問題,設(shè)計(jì)一種完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)之一,也是遺傳算法的一個(gè)重要研究方向.由于遺傳算法應(yīng)用的廣泛性,迄今為止人們已經(jīng)提出了許多種不同的編碼方法,可以分為3 大類:二進(jìn)制編碼方法、符號(hào)編碼方法和浮點(diǎn)數(shù)編碼方法[19].

根據(jù)Pod在節(jié)點(diǎn)上的分配模型即可得出這是一種01 背包問題,1 表示Pod 分配在此節(jié)點(diǎn)上,反之不分配.并且,二進(jìn)制編碼方法是遺傳算法中最重要的一種編碼方法,它使用的編碼符號(hào)集是由二進(jìn)制符號(hào)0和1 所組成的二值符號(hào)集{0,1},它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào).因此本文選用二進(jìn)制編碼作為編碼方案.

4.1.2 校驗(yàn)字典

在本小節(jié)中，我們通過具體的實(shí)驗(yàn)，將普通的紋理貼圖、法線貼圖和視差貼圖三者的繪制效果進(jìn)行對(duì)比來體現(xiàn)視差貼圖的特點(diǎn)。

確定編碼后隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù),每個(gè)串結(jié)構(gòu)數(shù)據(jù)成為一個(gè)個(gè)體,N個(gè)個(gè)體構(gòu)成了一個(gè)種群.遺傳算法以這N個(gè)串結(jié)構(gòu)作為初始點(diǎn)開始迭代.設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器;設(shè)置最大進(jìn)化代數(shù)T;隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0).

本文的染色體(Chromosome)編碼采用二進(jìn)制編碼方法,每個(gè)個(gè)體的基因編碼是一個(gè)二進(jìn)制編碼符號(hào),即0和1,采用二維數(shù)組存儲(chǔ)個(gè)體染色體,行代表Pod,列代表Node.Chromosome[i][j]=1,表示要在編號(hào)為j的節(jié)點(diǎn)上分配第i個(gè)Pod.例如i=1,j=3 表示第1 個(gè)Pod 被分配在第3 個(gè)節(jié)點(diǎn)上.如果生成了以下染色體{100,001,010},通過解碼可以知道第1 個(gè)Pod在Node1上,第2 個(gè)Pod在Node2上,第3 個(gè)Pod在Node3上.如表1所示為在一次隨機(jī)初始化種群中產(chǎn)生的一個(gè)染色體編碼.

表1 隨機(jī)初始化個(gè)體

表1表示隨機(jī)初始化種群中的一個(gè)個(gè)體,編碼為:{100,010,001,100,010,100,100}.

解決Kubernetes 資源調(diào)度問題的目的是找到合理的資源分配方案,但是由于Kubernetes的Pod 中擁有NodeAffinity (親和性)和Taint (污點(diǎn))兩種屬性,使得種群中的個(gè)體很可能不符合配置:

1)NodeAffinity 屬性從1.4 版本開始引入.如果在具有標(biāo)簽X的Node 上運(yùn)行了一個(gè)或者多個(gè)符合條件Y的Pod,那么Pod 應(yīng)該運(yùn)行在這個(gè)節(jié)點(diǎn)上.

2)Taint 屬性讓Pod 避開那些不合適的節(jié)點(diǎn),在節(jié)點(diǎn)上設(shè)置一個(gè)或者多個(gè)Taint 之后,除非Pod 明確聲明能夠容忍這些污點(diǎn),否則無法在這些節(jié)點(diǎn)上.

為解決在隨機(jī)初始化種群和后續(xù)選擇操作、交叉操作和變異操作中產(chǎn)生不符合用戶配置的個(gè)體這一問題,根據(jù)配置文件生成校驗(yàn)字典對(duì)生成的個(gè)體進(jìn)行校驗(yàn)操作.如表2表示為一個(gè)校驗(yàn)字典.

表2 校驗(yàn)字典

表2中,Type為Affine 表示Pod 傾向于運(yùn)行在此節(jié)點(diǎn)上,Type為Forbid 表示Pod 禁止運(yùn)行在此節(jié)點(diǎn)上.通過此校驗(yàn)字典對(duì)上文隨機(jī)生成的個(gè)體編碼進(jìn)行校驗(yàn)并修復(fù)后所得編碼為:{100,010,001,010,011,100,100}.

4.2 多維度加權(quán)評(píng)價(jià)指標(biāo)

在Kubernetes 默認(rèn)調(diào)度算法的優(yōu)選階段,只考慮了節(jié)點(diǎn)的CPU和內(nèi)存利用率,但是對(duì)于互聯(lián)網(wǎng)應(yīng)用,磁盤IO和網(wǎng)絡(luò)利用率也是十分重要的因素.因此本文在原有評(píng)價(jià)指標(biāo)上加入了磁盤IO和網(wǎng)絡(luò)利用率指標(biāo).

式(7)中,CpuPodij表示編號(hào)為i的Node 節(jié)點(diǎn)上編號(hào)為j的Pod的CPU 使用量,CpuPodij表示編號(hào)為i的Node 節(jié)點(diǎn)上CPU 使用總量,PodNumi表示Nodei上Pod的總數(shù).同理可求得該Node 上內(nèi)存、磁盤IO和網(wǎng)絡(luò)的利用率L(Memi)、L(Diski)、L(Neti).進(jìn)而可求得該Node 上的資源平均利用率:

在實(shí)際應(yīng)用部署中,不同節(jié)點(diǎn)對(duì)資源的傾向性不同,如計(jì)算型節(jié)點(diǎn)更傾向于CPU的使用,磁盤類型為SSD的節(jié)點(diǎn)更傾向于磁盤IO的使用等.針對(duì)不同類型的節(jié)點(diǎn)對(duì)評(píng)價(jià)指標(biāo)的側(cè)重點(diǎn)不同,引入權(quán)重weight決定各評(píng)價(jià)指標(biāo)對(duì)節(jié)點(diǎn)負(fù)載的影響.

式(9)中,Weight(Cpui)、Weight(Memi)、Weight(Diski)、Weight(Neti)分別表示賦予CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)的權(quán)重值.不同于式(9)中分母為4,使用Count(Weight)根據(jù)weight決定分母的值,若weight為0 則不考慮此指標(biāo).

4.3 種群初始化

在遺傳算法中使用適應(yīng)度(fitness)來度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度.適應(yīng)度函數(shù)(fitness function)也稱為評(píng)價(jià)函數(shù),是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn),是算法演化的驅(qū)動(dòng)力,也是進(jìn)行自然選擇的唯一依據(jù).適應(yīng)度較高的個(gè)體遺傳到下一代的概率較大;而適應(yīng)度較低的個(gè)體遺傳到下一代的概率較小[20].

在概率論中常用方差來度量隨機(jī)變量和均值之間的偏離程度,它刻畫了一個(gè)隨機(jī)變量值的分布范圍.方差越大,表示數(shù)據(jù)的波動(dòng)越大,方差越小,表示數(shù)據(jù)的波動(dòng)就越小.為了使Kubernetes 集群負(fù)載均衡,因此將可行解的平均資源利用率標(biāo)準(zhǔn)差作為適應(yīng)度的判定條件.

首先,計(jì)算每一種分配方案的資源平均利用率L(Cluk),式(10)中N表示符合要求的可行解數(shù)量:

其次,通過每一Node 上的資源評(píng)價(jià)利用率L(Ni)和每一種分配方案的資源平均利用率L(Cluk)可以很方便的計(jì)算出每一種分配方案的標(biāo)準(zhǔn)差:

在遺傳算法中,各個(gè)個(gè)體被遺傳到下一代的種群中的概率是由該個(gè)體的適應(yīng)度來確定的.適應(yīng)度越高的個(gè)體遺傳到下一代的概率就越大.為了使得集群負(fù)載均衡,標(biāo)準(zhǔn)差越小越好,所以我們無法直接使用標(biāo)準(zhǔn)差作為適應(yīng)度值,通常對(duì)于求解最小值的問題我們需要進(jìn)行轉(zhuǎn)換操作,因此適應(yīng)度函數(shù)如下所示:

式(12)中,Constmax為一個(gè)適當(dāng)?shù)南鄬?duì)較大的值,可以是標(biāo)準(zhǔn)差的最大估計(jì).

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

為驗(yàn)證改進(jìn)算法在Kubernetes 集群上的有效性,本文分別設(shè)計(jì)3 組實(shí)驗(yàn),實(shí)驗(yàn)采用Kubernetes1.17 版本,通過虛擬機(jī)的方式部署在宿主機(jī)上.宿主機(jī)配置為64 位Windows10 系統(tǒng),CPU為i7-8750H,內(nèi)存為32 GB.

實(shí)驗(yàn)1.驗(yàn)證引入校驗(yàn)字典的改進(jìn)遺傳算法有更少的迭代次數(shù).實(shí)驗(yàn)結(jié)果如圖2所示.標(biāo)準(zhǔn)遺傳算法從第190 代開始目標(biāo)函數(shù)值趨于最小值,使用校驗(yàn)字典的改進(jìn)遺傳算法在第110 代開始目標(biāo)函數(shù)值趨于最小值.因此,與標(biāo)準(zhǔn)遺傳算法相比,改進(jìn)的遺傳算法獲得相同的目標(biāo)函數(shù)值所需的迭代次數(shù)更少.

圖2 兩種算法迭代次數(shù)對(duì)比

實(shí)驗(yàn)2.對(duì)Kubernetes Scheduler 默認(rèn)資源調(diào)度器與基于改進(jìn)遺傳算法的自定義調(diào)度器(custom scheduler)在保證集群整體負(fù)載均衡能力上進(jìn)行對(duì)比.實(shí)驗(yàn)結(jié)果如圖3所示.由圖可知,使用Kubernetes 默認(rèn)調(diào)度器的集群負(fù)載比使用改進(jìn)遺傳算法自定義調(diào)度器的集群的平均負(fù)載更高,前者標(biāo)準(zhǔn)差為3.421 93,后者標(biāo)準(zhǔn)差為1.102 72,說明本文算法更能保證集群的負(fù)載均衡.

圖3 集群節(jié)點(diǎn)負(fù)載

實(shí)驗(yàn)3.首先驗(yàn)證引入網(wǎng)絡(luò)和磁盤IO 指標(biāo)對(duì)集群帶寬和磁盤IO的影響,權(quán)重值都為1.如圖4、圖5分別為使用網(wǎng)絡(luò)指標(biāo)和使用磁盤指標(biāo)后K8s 集群的網(wǎng)絡(luò)和磁盤IO 負(fù)載情況.由實(shí)驗(yàn)結(jié)果可知,使用K8s 默認(rèn)資源調(diào)度算法的網(wǎng)絡(luò)帶寬利用率標(biāo)準(zhǔn)差為0.304 89,磁盤利用率標(biāo)準(zhǔn)差為0.263 25.使用本文算法的網(wǎng)絡(luò)帶寬利用率標(biāo)準(zhǔn)差為0.1387,磁盤利用率標(biāo)準(zhǔn)差為0.174 34.本文算法的兩個(gè)指標(biāo)對(duì)應(yīng)的標(biāo)準(zhǔn)差都比K8s 默認(rèn)調(diào)度算法小,說明本文算法在保證帶寬和磁盤負(fù)載均衡方面優(yōu)于K8s 默認(rèn)資源調(diào)度算法.

圖4 網(wǎng)絡(luò)使用率

圖5 磁盤使用率

其次,為驗(yàn)證權(quán)重對(duì)不同類型節(jié)點(diǎn)的影響,針對(duì)CPU,內(nèi)存,帶寬和磁盤分別創(chuàng)建高性能和低性能兩種類型節(jié)點(diǎn)進(jìn)行分組實(shí)驗(yàn),每組實(shí)驗(yàn)3 個(gè)節(jié)點(diǎn),其中Node1為高性能節(jié)點(diǎn),Node2和Node3為低性能節(jié)點(diǎn).各節(jié)點(diǎn)對(duì)應(yīng)資源權(quán)重值分別設(shè)置為:0.5,1,1.

如圖6～圖9所示為3 個(gè)節(jié)點(diǎn)在120 s 時(shí)間內(nèi)對(duì)應(yīng)資源的使用率情況.

圖6 CPU 權(quán)重實(shí)驗(yàn)

圖7 內(nèi)存權(quán)重實(shí)驗(yàn)

圖8 網(wǎng)絡(luò)權(quán)重實(shí)驗(yàn)

圖9 磁盤權(quán)重實(shí)驗(yàn)

統(tǒng)計(jì)3 個(gè)節(jié)點(diǎn)在120 s 內(nèi)對(duì)應(yīng)資源的使用率,對(duì)比Kubernetes 默認(rèn)資源調(diào)度算法和本文算法在不同性能節(jié)點(diǎn)上資源使用率均值,將數(shù)據(jù)歸納如表3所示.

由表3可知,使用本文算法后高性能節(jié)點(diǎn)將承受更高的負(fù)載,如高性能內(nèi)存節(jié)點(diǎn)Node1使用K8s 調(diào)度算法使用率為70.08%,使用本文算法后使用率為78.51%,這是因?yàn)橘x予高性能節(jié)點(diǎn)更低的權(quán)重值降低節(jié)點(diǎn)負(fù)載從而將更多的Pod 調(diào)度至此節(jié)點(diǎn).但是低性能內(nèi)存節(jié)點(diǎn)Node2使用K8s 調(diào)度算法使用率為39.61%,使用本文算法后使用率為35.32%,說明本文算法降低了低性能節(jié)點(diǎn)負(fù)載.雖然高性能節(jié)點(diǎn)負(fù)載提高了,但是由于節(jié)點(diǎn)的性能優(yōu)勢并不會(huì)給節(jié)點(diǎn)帶來嚴(yán)重負(fù)擔(dān).所以,與K8s 默認(rèn)資源調(diào)度算法相比,本文算法結(jié)合節(jié)點(diǎn)優(yōu)勢特性提高了集群負(fù)載能力.

表3 不同資源使用兩種算法的資源使用率(%)

6 結(jié)語

本文為了優(yōu)化Kubernetes 集群平臺(tái)中受資源調(diào)度影響的負(fù)載均衡,降低集群的平均負(fù)載,提出了基于改進(jìn)遺傳算法的Kubernetes 資源調(diào)度算法,該算法根據(jù)Kubernetes 中Pod 擁有的NodeAffinity和Taint 屬性,為降低在隨機(jī)初始化種群、選擇操作、交叉操作和變異操作過程中會(huì)產(chǎn)生不符合用戶配置的個(gè)體對(duì)結(jié)果的影響,引入校驗(yàn)字典對(duì)種群中的個(gè)體進(jìn)行校驗(yàn)及修復(fù),實(shí)驗(yàn)表明校驗(yàn)字典的引入可以減少算法的迭代次數(shù),提高算法運(yùn)行效率.同時(shí),Kubernetes Scheduler 默認(rèn)資源調(diào)度算法只考慮了Node的CPU和內(nèi)存利用率,結(jié)合節(jié)點(diǎn)特性提出了多維度加權(quán)評(píng)價(jià)指標(biāo),并使用標(biāo)準(zhǔn)差作為適應(yīng)度函數(shù),降低了集群的平均負(fù)載且維持了集群的負(fù)載均衡.但與默認(rèn)資源調(diào)度算法相比本文算法對(duì)CPU的占用過高,進(jìn)而影響Master 節(jié)點(diǎn)中其他Kubernetes 組件的運(yùn)行,因此下一階段工作任務(wù)將針對(duì)此問題進(jìn)行研究.