基于遺傳算法的Kubernetes資源調度算法①

胡程鵬,薛 濤

(西安工程大學 計算機科學學院,西安 710048)

1 引言

隨著互聯網規模的擴大,服務器產生的海量數據促使云計算[1]的快速發展.云計算是指將大量用網絡連接的計算資源進行統一管理和調度,構成一個計算資源池向用戶提供服務.通過云計算,可以合并組織現有的公司信息資源,并為其員工和合作伙伴提供通用的遠程訪問權限[2].云計算的問題之一是對資源的利用不均.傳統云計算架構中基礎設施及服務層(IaaS)的資源分配是以虛擬機為基本單位進行調度,但是虛擬機的調度是一種粗粒度的資源調度,會出現調度緩慢等問題.

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

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

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

2 默認調度算法分析

Kubernetes Scheduler是Kubernetes 資源調度的核心組件,其職責是將API Server 或Controller Manager新建的待調度Pod 根據指定的調度算法與集群中的某個合適的工作節點進行綁定,并將Pod和節點的綁定信息寫入ETCD 中[16].而后工作節點通過守護進程Kubelet 監聽到Kubernetes 調度器發出的Pod和節點的綁定信息,并從ETCD 中獲取Pod 配置文件,最后根據配置文件完成容器應用的啟動.

Kubernetes 調度器中的默認調度算法分為3 個階段:預選階段(Predicates)、優選階段(Priority)和選定階段(Select).Predicates 階段的工作是查詢集群中的所有節點,根據Predicates的算法選擇適用的節點完成初篩.Priority 階段的工作是根據Priority 中的算法給Predicates 階段初篩的節點進行評分,挑選出得分最高的節點作為調度的目標節點.

Predciates 階段要求滿足條件的節點必須通過所有篩選策略.下面介紹幾種策略的篩選內容:

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

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

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

4)MatchNodeSelector:檢查Pod的節點選擇器是否匹配節點的標簽;

5)CheckNodeMemoryPressure:如果節點正在報告內存壓力,并且沒有配置的異常,則不會再此處分配Pod;

6)CheckNodeCondition:節點可以報告具有完全完整的文件系統,網絡不可用或者Kubelet 尚未準備好運行的Pod.如果為節點設置了這樣的條件,并且沒有配置的異常,則不會在此處分配Pod.

優選階段會根據優選策略對每個節點進行打分,最終把Pod 調度到分值最高的節點.Kube-Scheduler 用一組優先級函數處理每個通過預選的節點,每個函數返回0-10的分數,各個函數有不同權重,最終得分是所有優先級函數的加權和,即節點得分的計算公式為:

式(1) 中,FinalScoreNode表示最終得分,weighti表示各個函數的權重值,priorityFunci表示具體的優先級函數得分.

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

1)Least RequestedPriority 算法默認權重為1,此算法盡量將Pod 調度到計算資源占用比較小的節點上.此算法設計兩種計算資源:CPU和內存.計算公式如下:

式(2)中,cpuCapacity表示候選節點CPU 資源的總量,cpuRequest表示Pod 需要的CPU 資源量,cpuS core表示根據CPU 指標計算的得分.式(3)中,memoryCapacity表示候選節點內存資源的總量,memoryRequest表示Pod 需要的內存資源量,memoryS core表示根據內存指標計算的得分.式(4)中,leastS core表示使用Least RequestedPriority 算法獲得的得分.

2)NodeAffinityPriority 默認權重為1,此算法盡量調度到標簽匹配Pod 屬性要求的節點,判斷行為與預選中的MatchNodeSelector 類似.該算法提供兩種選擇器:requiredDuringSchedulingIgnoredDuringExecution和preferredDuringSchedulingIgnoredDuringExecution.計算公式如下:

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

在獲取了兩種算法對候選節點的評分后,Kubernetes調度器取兩種算法的加權平均值作為各個節點的最終評分:

通過分析Kubernetes 調度器的默認算法可以發現其默認算法對節點的評價指標中只考慮了CPU和內存的使用率,沒有考慮磁盤IO和網絡帶寬的使用.并且Kubernetes 調度器是一種靜態調度策略,該調度機制雖然簡單,但是缺乏靈活性.且只能在Pod 初次部署時進行資源配置.同時,默認調度策略只能保證單節點的服務質量,未考慮整個集群的負載情況.從而導致集群資源利用率低.

3 Pod 分配模型與遺傳算法

Scheduler 根據調度策略將Pod 部署到不同的節點中,Pod在節點之間的分配模型如圖1所示,其可以說明Pod 與節點之間的相互關系.

圖1 Pod在Node的分配模型

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

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

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

4 改進的遺傳算法

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

4.1 種群初始化

4.1.1 編碼的確定

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

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

4.1.2 校驗字典

在本小節中，我們通過具體的實驗，將普通的紋理貼圖、法線貼圖和視差貼圖三者的繪制效果進行對比來體現視差貼圖的特點。

確定編碼后隨機產生N個初始串結構數據,每個串結構數據成為一個個體,N個個體構成了一個種群.遺傳算法以這N個串結構作為初始點開始迭代.設置進化代數計數器;設置最大進化代數T;隨機生成M個個體作為初始群體P(0).

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

表1 隨機初始化個體

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

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

1)NodeAffinity 屬性從1.4 版本開始引入.如果在具有標簽X的Node 上運行了一個或者多個符合條件Y的Pod,那么Pod 應該運行在這個節點上.

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

為解決在隨機初始化種群和后續選擇操作、交叉操作和變異操作中產生不符合用戶配置的個體這一問題,根據配置文件生成校驗字典對生成的個體進行校驗操作.如表2表示為一個校驗字典.

表2 校驗字典

表2中,Type為Affine 表示Pod 傾向于運行在此節點上,Type為Forbid 表示Pod 禁止運行在此節點上.通過此校驗字典對上文隨機生成的個體編碼進行校驗并修復后所得編碼為:{100,010,001,010,011,100,100}.

4.2 多維度加權評價指標

在Kubernetes 默認調度算法的優選階段,只考慮了節點的CPU和內存利用率,但是對于互聯網應用,磁盤IO和網絡利用率也是十分重要的因素.因此本文在原有評價指標上加入了磁盤IO和網絡利用率指標.

式(7)中,CpuPodij表示編號為i的Node 節點上編號為j的Pod的CPU 使用量,CpuPodij表示編號為i的Node 節點上CPU 使用總量,PodNumi表示Nodei上Pod的總數.同理可求得該Node 上內存、磁盤IO和網絡的利用率L(Memi)、L(Diski)、L(Neti).進而可求得該Node 上的資源平均利用率:

在實際應用部署中,不同節點對資源的傾向性不同,如計算型節點更傾向于CPU的使用,磁盤類型為SSD的節點更傾向于磁盤IO的使用等.針對不同類型的節點對評價指標的側重點不同,引入權重weight決定各評價指標對節點負載的影響.

式(9)中,Weight(Cpui)、Weight(Memi)、Weight(Diski)、Weight(Neti)分別表示賦予CPU、內存、磁盤、網絡的權重值.不同于式(9)中分母為4,使用Count(Weight)根據weight決定分母的值,若weight為0 則不考慮此指標.

4.3 種群初始化

在遺傳算法中使用適應度(fitness)來度量群體中各個個體在優化計算中能達到或接近于或有助于找到最優解的優良程度.適應度函數(fitness function)也稱為評價函數,是根據目標函數確定的用于區分群體中個體好壞的標準,是算法演化的驅動力,也是進行自然選擇的唯一依據.適應度較高的個體遺傳到下一代的概率較大;而適應度較低的個體遺傳到下一代的概率較小[20].

在概率論中常用方差來度量隨機變量和均值之間的偏離程度,它刻畫了一個隨機變量值的分布范圍.方差越大,表示數據的波動越大,方差越小,表示數據的波動就越小.為了使Kubernetes 集群負載均衡,因此將可行解的平均資源利用率標準差作為適應度的判定條件.

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

其次,通過每一Node 上的資源評價利用率L(Ni)和每一種分配方案的資源平均利用率L(Cluk)可以很方便的計算出每一種分配方案的標準差:

在遺傳算法中,各個個體被遺傳到下一代的種群中的概率是由該個體的適應度來確定的.適應度越高的個體遺傳到下一代的概率就越大.為了使得集群負載均衡,標準差越小越好,所以我們無法直接使用標準差作為適應度值,通常對于求解最小值的問題我們需要進行轉換操作,因此適應度函數如下所示:

式(12)中,Constmax為一個適當的相對較大的值,可以是標準差的最大估計.

5 實驗結果與分析

為驗證改進算法在Kubernetes 集群上的有效性,本文分別設計3 組實驗,實驗采用Kubernetes1.17 版本,通過虛擬機的方式部署在宿主機上.宿主機配置為64 位Windows10 系統,CPU為i7-8750H,內存為32 GB.

實驗1.驗證引入校驗字典的改進遺傳算法有更少的迭代次數.實驗結果如圖2所示.標準遺傳算法從第190 代開始目標函數值趨于最小值,使用校驗字典的改進遺傳算法在第110 代開始目標函數值趨于最小值.因此,與標準遺傳算法相比,改進的遺傳算法獲得相同的目標函數值所需的迭代次數更少.

圖2 兩種算法迭代次數對比

實驗2.對Kubernetes Scheduler 默認資源調度器與基于改進遺傳算法的自定義調度器(custom scheduler)在保證集群整體負載均衡能力上進行對比.實驗結果如圖3所示.由圖可知,使用Kubernetes 默認調度器的集群負載比使用改進遺傳算法自定義調度器的集群的平均負載更高,前者標準差為3.421 93,后者標準差為1.102 72,說明本文算法更能保證集群的負載均衡.

圖3 集群節點負載

實驗3.首先驗證引入網絡和磁盤IO 指標對集群帶寬和磁盤IO的影響,權重值都為1.如圖4、圖5分別為使用網絡指標和使用磁盤指標后K8s 集群的網絡和磁盤IO 負載情況.由實驗結果可知,使用K8s 默認資源調度算法的網絡帶寬利用率標準差為0.304 89,磁盤利用率標準差為0.263 25.使用本文算法的網絡帶寬利用率標準差為0.1387,磁盤利用率標準差為0.174 34.本文算法的兩個指標對應的標準差都比K8s 默認調度算法小,說明本文算法在保證帶寬和磁盤負載均衡方面優于K8s 默認資源調度算法.

圖4 網絡使用率

圖5 磁盤使用率

其次,為驗證權重對不同類型節點的影響,針對CPU,內存,帶寬和磁盤分別創建高性能和低性能兩種類型節點進行分組實驗,每組實驗3 個節點,其中Node1為高性能節點,Node2和Node3為低性能節點.各節點對應資源權重值分別設置為:0.5,1,1.

如圖6～圖9所示為3 個節點在120 s 時間內對應資源的使用率情況.

圖6 CPU 權重實驗

圖7 內存權重實驗

圖8 網絡權重實驗

圖9 磁盤權重實驗

統計3 個節點在120 s 內對應資源的使用率,對比Kubernetes 默認資源調度算法和本文算法在不同性能節點上資源使用率均值,將數據歸納如表3所示.

由表3可知,使用本文算法后高性能節點將承受更高的負載,如高性能內存節點Node1使用K8s 調度算法使用率為70.08%,使用本文算法后使用率為78.51%,這是因為賦予高性能節點更低的權重值降低節點負載從而將更多的Pod 調度至此節點.但是低性能內存節點Node2使用K8s 調度算法使用率為39.61%,使用本文算法后使用率為35.32%,說明本文算法降低了低性能節點負載.雖然高性能節點負載提高了,但是由于節點的性能優勢并不會給節點帶來嚴重負擔.所以,與K8s 默認資源調度算法相比,本文算法結合節點優勢特性提高了集群負載能力.

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

6 結語

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