云環境下數據中臺能耗感知的微服務任務調度算法

謝裕清 王 淵 江 櫻 李 浩 王永利*

1(國網浙江省電力有限公司信息通信分公司 浙江 杭州 310000) 2(南瑞集團有限公司(國網電力科學研究院有限公司) 江蘇 南京 211100) 3(江蘇瑞中數據股份有限公司 江蘇 南京 211100) 4(南京理工大學計算機科學與工程學院 江蘇 南京 210094)

0 引 言

數據中臺的理念源自阿里巴巴“構建規范定義的、全域可連接萃取的、智慧的數據處理平臺”，數據中臺的建設目標是實現前臺數據的高效分析和應用[1]。數據中臺的機制是通過云計算等數據技術，對海量數據進行采集、計算、存儲、加工，并將數據的標準和口徑進行統一。數據中臺將數據存儲為經統一之后所形成的標準數據，構成大數據資產層，進而為客戶提供高效服務。

隨著數據中臺建設與計算機網絡云計算服務的發展，數據中臺中越來越多的用戶開始向云計算提交服務請求，利用數據中臺提供的虛擬資源來完成任務，而云服務供應商需要根據云計算的特點、用戶的偏好、實際的情況為用戶動態地提供調度服務。在數據中臺體系中，由于云平臺任務調度面臨的是一個非定常多項式(Non-deterministic Polynomial，NP)完全問題,引起了眾多學者的關注,尤其是云平臺下的多任務調度問題成為目前云計算領域研究的一個熱點。

數據中臺下的云數據中臺用戶越來越多，在擴大云平臺規模的同時，為了提高調度的靈活性并且避免不必要的能耗浪費，云服務供應商提出了微服務架構[2]。微服務架構中的服務是指細粒度的、相互間松耦合的、可獨立開發部署的組件。采用微服務架構設計的系統由一組通過輕量級接口實現的通信服務組成。

由于微服務架構將應用系統分為多個細粒度項目，原本單體式應用中的一系列操作可能需要多個服務協同完成，因此需要設計一個任務調度服務來處理關聯多個服務的任務，比如在某一操作完成后執行另一類別的一個操作[3-4]。云計算數據中臺具有異構性、動態性和地理分布性等特點，微服務工作流任務在云平臺執行時，不但要保證任務執行時間滿足截止期限制，云服務提供商還要最大限度優化數據中心能耗，否則可能違反SLA(Service Level Agreement)協議。因此，如何設計啟發式調度算法并應用到調度系統中來優化任務調度問題中的目標約束成為眾多學者研究的核心問題。

文獻[5]提出一種基于二次分派問題QAP的調度算法，在任務-資源映射階段和資源頻率分配階段中同步進行能量優化；文獻[6]提出了一個多目標遺傳進化算法用于云平臺中的任務調度，認為優化問題中的多個目標函數都是相互沖突的，目的是找到這些多目標折中的非支配Pareto解集。文獻[7]針對云環境下數據密集型任務的調度問題，設計了一個基于二叉樹建模的調度方法，同時滿足用戶QoS(Quality of Service)需求[8]。

現有云計算環境下的工作流任務調度的研究大多針對獨立任務或元任務的特殊形式，忽視了任務間的數據關聯與優先約束關系，不能反映應用任務間的實際特征。同時缺少調度大規模復雜的微服務工作流的工作，無法充分利用微服務工作流提高應用的靈活性和敏捷性。

鑒于此，本文提出一種利用Docker容器融入能耗感知的微服務工作流任務調度算法，綜合考慮了微服務任務間的數據依賴和優先級依賴，引入了能耗效益函數。在此基礎上，設計兩個子算法——任務映射算法和任務合并算法，用于協助云資源調度器調度管理提交到云數據中臺的微服務工作流任務，最小化數據中臺能耗的同時，滿足工作流任務截止期限制，以實現用戶QoS需求。仿真實驗表明，在同等條件下，與經典的EES(Enhanced Energy-Efficient Scheduling)[9]和EHEFT(Enhancing Heterogeneous Earliest Finish Time)[10]等算法相比，在任務截止期長度變化以及子任務個數變化等環境下，本文算法具有較好的綜合性能。

本文的貢獻如下：

(1) 提出使用Docker容器調度云數據中臺的微服務工作流，相比于直接使用IaaS虛擬機，可有效提高計算資源的利用率。

(2) 綜合考慮微服務任務間的數據依賴和優先級依賴，體現微服務工作流執行的靈活性。

(3) 引入了能耗效益函數，滿足不同的工作流截止期約束條件下，以最小化計算資源租賃成本為目標，有效提高云環境下數據中臺調度大規模微服務工作流的經濟效益。

1 問題描述及建模

數據中臺上基于微服務的應用程序調度可以通過三個組件的屬性來表征，即應用程序模型、系統模型和性能模型。應用程序模型定義基于業務工作流調度的應用程序結構；系統模型描述執行應用程序的VM和基礎網絡；性能模型負責調度優化等任務。這種由三部分組成的視圖與定義經典調度問題的表示法一致。

應用模型中基于微服務的工作流模型采用有向無環圖(Directed Acyclic Graph,DAG)W=(T,E)，其中頂點T={t1,t2,…,tn}代表n個任務，一對相鄰任務ti和tj之間的執行依賴性由它們之間的有向邊表示，可以附加權重wi,j表示從ti傳遞到tj的數據大小。任務ti從其每個先前功能接收數據輸入并執行預定義的業務邏輯。成功執行后，任務ti的輸出數據將立即發送到其后續任務。如圖1所示，ti從tj和tk接收輸入數據執行其自身的功能，并在完成執行后將輸出數據wi,p發送至tp。此處不考慮應用程序模型中功能的計算開銷。系統模型IaaS支持運行基于微服務的應用程序的基礎環境，其中在互連的物理計算機上保留、部署和執行虛擬機。本文將這樣的云環境建模為完全連接的有向圖G，頂點由VM集合組成，邊由虛擬機之間的一組有向鏈接組成，VM虛擬機vi和vj之間的每個通信鏈路li,j與帶寬(BW)bi,j和最小鏈路延遲(MLD)di,j相關聯。應用程序的每個功能都由微服務實現，每個微服務都需要部署在一個容器中，該容器的計算能力定義為四元式pci=(c,f,r,d)，其中：c表示CPU內核數；f表示每一CPU核的頻率；r表示RAM總大??；d表示總磁盤空間。功能ti被映射到微服務msi并由微服務msi實現，然后微服務msi被封裝在容器ci中，而計算能力pci部署在VMvy上。

圖1 云數據中臺上基于微服務的應用程序調度模型

在IaaS中，云提供商以互連VM的形式租用計算資源。通常，提供具有不同計算能力的不同類型的VM，根據計算能力c、f、r、d滿足不同的應用程序需求。不同的VM類型以不同的價格收費。以Amazon EC2.3為例，提供五種按需實例類型的配置和價格，Amazon采用分步計費模式，其中VM不足1小時使用時間會被四舍五入到1小時。本文的工作針對單一公共云中的計算環境，在該公共云中物理機通過高帶寬Intranet互連，因此不專門考慮數據傳輸成本。更籠統地說，考慮一個具有l個VM類型的公共云環境vm1,vm2,…,vml，其中每種類型的vmk都與成本和性能相關的屬性相關聯，并定義為算力、最大功率、帶寬三元組。圖1給出了在示例系統模型中由vy表示的一個vmk類型的VM實例和由vq和vx表示的兩個vmj類型的VM實例。每個通信鏈路(例如，從vx到vy)是有方向的，并與帶寬(bx,y)和最小鏈路延遲(dx,y)相關聯。

性能模型主要負責在公共數據中臺云中執行基于微服務的應用程序調度，滿足用戶指定的預算約束、功耗約束下實現最小的端到端延遲(MED)目標。本文擴展了主要考慮能耗因素，將它們擴展到具有函數間依賴性的應用程序模型中，以識別和量化公共云的功耗成分。使用微服務和容器的一個關鍵優勢是快速復制和遷移的便利性，因此將復制的微服務作為不同的實例運行，每個微服務都可以實現不同應用程序所需的相同功能。

與基于虛擬機的云服務相比，本文設計的基于容器的數據中臺微服務模型的技術特征及優勢為：

1) 微服務易于被開發人員理解、修改和維護。各個微服務可被獨立部署，各個微服務之間是松耦合的，每個微服務都很小，是有功能意義的服務，無論是在開發階段或部署階段都是獨立的，有助于聚焦指定的業務功能或業務需求。2) 基于容器的微服務運行占用的空間少啟動速度快且便于遷移。與虛擬機相比，容器中的微服務可以共享操作系統內核，不需要在主機上構建多個虛擬機擁有完整的副本，占用的空間更少，啟動速度也更快。每個微服務都可以實現不同應用程序所需的相同功能，可以將復制的微服務作為不同的實例運行，有利于快速復制和遷移。

為簡便起見，假設每個虛擬機只對應一個容器。

定義1微服務工作流模型。通常情況下，一個微服務工作流W=(T,E)可以用一個有向無環圖(DAG)來表示，如圖2所示。其中T={t1,t2,…,tn}為工作流中的任務集合，DAG中一個頂點代表一個任務，E是DAG中邊的集合，代表任務之間的依賴關系。若任務ti和任務tj(ti,tj∈T,ti≠tj,且1≤i

(ti)={tj|(tI,tj)∈E}

(1)

圖2 一個DAG工作流模型

定義2數據中臺虛擬機模型。數據中臺提供l種類型的虛擬機的類型集為VM={vm1,vm2,…,vmk…,vml}，每種類型VM的虛擬機的特性都可以用(c,pmax,B)三元組表示，其中:c是虛擬機的計算能力，用每秒運算的浮點數(MFLOPS)衡量；pmax是虛擬機的最大功率；B為帶寬。不同類型的虛擬機之間滿足如下約束關系：

(2)

式中：所有虛擬機實例的計算能力和最大功率均按升序排序。式(2)就意味著，虛擬機之間隨著計算能力的增強，虛擬機的功耗將隨之增加，且增加幅度超過虛擬機計算能力的增強幅度。

定義3基于容器的數據中臺虛擬機微服務任務調度問題可描述為：在數據中臺中，將微服務工作流的n個子任務分配給m個異構的虛擬資源節點執行(m

(3)

i∈{1,2,…,n},j∈{1,2,…,m}

(4)

(5)

(6)

定義5虛擬機空閑能耗。當虛擬機處在空閑狀態時，CPU芯片會使用動態電壓頻率調整(Dynamic Voltage Frequency Scaling，DVFS)技術把CPU的電壓和運行頻率調整到一個較低的水平。因此，虛擬機處在空閑狀態時的能耗可由式(7)計算。

(7)

定義6數據中臺的總能耗。由數據中臺中所有虛擬機實例的總能耗組成(動態能耗和空閑能耗)，因此，云數據中臺的總功耗Etotal為：

(8)

定義7基于以上定義，本文的調度問題可以描述為：找到一個微服務工作流調度方案，使得數據中臺執行工作流任務時產生的總能耗最小，且滿足工作流任務的截止期限制?？梢杂墒?9)定義。

minEtotal
s.t.makespan≤deadline(w)

(9)

2 算法設計與實現

任務的調度問題面臨的是一個NP-難問題[12]，本文的目標是設計啟發式調度算法以最大限度優化數據中臺產生的能耗。下面給出算法的實現以及偽代碼。

2.1 任務映射算法

定義8一個任務的完工時間由兩部分組成：該任務真實的執行時間和該任務的依賴數據需要傳輸的時間?？捎墒?10)計算得出。

(10)

定義9能耗效益函數。能耗效益函數代表消耗單位的能耗下能完成的工作負載的大小。任務ti在類型為k的虛擬機上執行時的能耗效益函數可以通過式(11)計算。

(11)

式中：分子為任務ti的工作負載；分母為執行任務ti時產生的能耗。能耗效益函數值越大，表明該任務被映射到類型為k的虛擬機上執行時越節能。

微服務工作流任務與虛擬機分配映射算法偽代碼：

算法1微服務工作流任務與虛擬機分配映射算法TaskMapping

輸入：微服務工作流任務ti,i∈1,2,…,n,虛擬機能耗效益函數集合。

輸出：任務ti與虛擬機映射關系map。

3) 初始化任務集R=?，k=1；

4)whilek≤landR≠?do

5) 針對任務ti，選取能耗效益函數集合中的第k個虛擬機類型作為目標虛擬機類型，如果ti能在其截止期限執行完成，則選取當前第k種虛擬機類型機為VMopt，把任務ti映射到該類型的虛擬機的容器上，即map:ti→VMopt；

6) 否則，把任務ti放入R中，針對R中的每一個任務，選取該任務的能耗效益函數集合的下一個虛擬機類型作為目標虛擬機類型；

7)enddo

虛擬機類型的能耗效益排序采用快速排序或者堆排序，最優時間復雜度為O(llogl)，其中l為虛擬機類型數目，步驟5)到步驟7)算法復雜度為O(nl)，n為微服務工作流任務個數。與已有任務虛擬機映射算法相比，本文提出的啟發式微服務工作流任務與虛擬機分配映射算法具有復雜度低且滿足綜合能耗效益函數約束。

2.2 串行任務合并算法

定義10兩個存在依賴關系的串行任務之間數據傳輸時間可由式(12)獲得。

(12)

式中：data(ti,tj)表示有依賴關系的任務ti和tj之間傳輸的數據量。

從式(12)可以看出，如果兩個串行任務分配到一臺虛擬機上執行，那么這兩個任務間的依賴數據傳輸時間就會被節約。因此，下面給出串行任務合并算法的偽代碼。

算法2串行任務合并算法TaskMerging

輸入:微服務工作流任務ti,i∈1,2,…,n,虛擬機能耗效益函數集合。

輸出：微服務工作流任務集。

1) 初始化空任務集合，記為T。

2) 對工作流中的任務進行拓撲排序，然后把所有拓撲排序后的任務放入T中，i=1；

3)while任務集合T不為空do

4)if(ti只有一個直接后繼任務且該后繼任務只有一個前驅任務，或者ti只有一個前驅任務且該前驅任務只有一個后繼任務) then

5) 找到一個虛擬機類型k，滿足在(deadline(ti)+deadline(ti+1))時間內能完成ti和ti+1;

7) 合并ti和ti+1為一個新任務t′，

8) 更新t′的前驅任務、后繼任務、工作負載和截止期限;

9) 將ti從T中移除；

10)else

11) 不合并ti和ti+1，移除ti；

12)endif

13)endif

14)enddo

圖3給出串行任務合并過程示意圖，算法復雜度為O(nl)，其中n為微服務工作流任務個數。

圖3 串行任務合并過程示意圖

與已有的串行任務合并算法相比，本文提出的串行任務合并算法考慮到虛擬機能耗效益因素，并且關注存在依賴關系的串行任務合并，顯著地節約了數據傳輸時間。

2.3 能耗感知的任務調度算法

本文提出的能耗感知的微服務工作流任務調度算法旨在優化云環境下數據中臺執行微服務任務時產生的能耗，同時滿足任務截止期限制。算法主要由以上提出的兩個子算法構成。

算法3能耗感知的微服務工作流任務調度算法

輸入：微服務工作流任務集合T={t1,t2,…,tn}，虛擬資源節點集V={v1,v2,…,vm}。

輸出：任務與資源分配關系矩陣X。

1)while未達到調度評價指標do

2) 調用任務映射算法TaskMapping；

3) 調用串行任務合并算法TaskMerging；

4)enddo

算法復雜度為O(nlm)。

3 仿真實驗及結果分析

為了驗證本文算法在節約能耗方面的綜合性能，在不同的仿真參數和性能指標下將其與同樣為啟發式任務調度算法的EES和EHEFT進行了綜合對比分析。實驗環境為Windows 7系統，Intel(R) Core 3.20 GHz CPU，1 TB硬盤，8 GB RAM。仿真平臺為澳大利亞墨爾本大學的網絡實驗基于Java語言開發的Cloudsim云仿真平臺[13]。在Cloudsim仿真平臺中，DataCenter類代表數據中臺，VirtualMachine類代表虛擬資源節點，Cloudlet類代表任務。

3.1 兩個子算法之間節能性能比較

本實驗旨在比較兩個子算法隨任務截止期變化時的節能性能。實驗參數為：虛擬資源節點個數m=10，任務數n=30，虛擬資源節點類型數k=5。實驗結果如圖4所示。

圖4 任務截止期變化對兩個子算法能耗的影響

可以看出，隨著任務截止期的變長，兩者的能耗都在降低，且固定任務截止期時，任務合并算法的節能效果優于任務映射算法的節能效果，其原因在于，串行任務合并算法避免了數據依賴任務之間數據集的傳輸，而且任務合并后只需要租用更少的虛擬機實例。本文提出的能耗感知的任務調度算法在未達到調度評價指標情況下，綜合兩個子算法的節能優勢，實現綜合能耗最優化。

3.2 隨任務截止期變化的性能比較

本實驗的實驗參數與實驗1相同，主要考察隨任務截止期變化時本文算法與EES和EHEFT之間的節能性能比較，實驗結果如圖5所示。

圖5 任務截止期變化對能耗的影響

可以看出，本文算法的節能性能最優，這說明本文算法在調度任務執行時對數據中臺的能耗最敏感，因為本文算法的能耗效益函數總是在滿足任務截止期的前提下，借助工作流任務與虛擬機分配映射算法和串行任務合并算法，選擇能耗最優的虛擬機執行任務。EHEFT次之，EES的能耗保持不變且維持在一個較高水平，這是因為EES總是選擇數據中臺中性能最強的虛擬機執行任務，不考慮能耗因素。

3.3 隨任務數變化的性能比較

實驗參數為：虛擬資源節點個數m=30，虛擬資源節點類型數k=5。性能指標比較結果如圖6所示?？梢钥闯?，隨著任務數的擴充，本文算法、EES和EHEFT的能耗都有所增加，但是固定任務數時，EES和EHEFT產生的能耗均高于本文算法，說明在同等條件下，本文算法的能耗效益函數機制在執行任務時節約能耗性能和可擴展性均明顯優于EES和EHEFT。

圖6 任務個數變化對能耗的影響

3.4 隨虛擬資源節點異構性變化的性能比較

實驗參數為：任務個數n=100，虛擬資源節點個數m=30。能耗比較變化趨勢如圖7所示。可以看出，隨著虛擬資源節點異構性(虛擬機類型數)的變化，三個算法的能耗變化不明顯，跟實驗2類似，EES能耗最高，EHEFT次之，本文算法能耗最少。這說明本文算法對虛擬資源的異構性變化不敏感，但是節能性能最優。

圖7 虛擬資源節點異構性變化對能耗的影響

綜上，本文提出的能耗感知的微服務工作流任務調度算法與已有算法相比，在隨任務截止期變化、隨任務數變化、隨虛擬資源節點異構性變化等幾個方面均具有更好的性能。

4 結 語

能耗問題在基于微服務的數據中臺云數據中心表現得越來越重要。本文針對云數據中臺中依賴任務調度導致的能耗浪費問題，構建了能耗效益函數模型和云數據中臺能耗模型，并提出一個包含了兩個子算法的啟發式微服務工作流任務調度算法對模型進行求解。仿真實驗表明，本文算法在能耗管理方面具有較好的綜合性能。下一步的工作將是考慮虛擬資源節點的綜合成本問題，同時滿足基于用戶需求和云數據中臺節能的多目標優化調度算法，以及采用相應的數學模型來刻畫不同的用戶需求。