面向交叉微服務鏈的任務調度優化

張宇鵬，吳自力，陳 鳴，張璐璐

(西安電子科技大學 計算機科學與技術學院，陜西 西安 710071)

隨著云計算和容器技術的發展[1]，微服務架構已經越來越多地被應用程序設計和開發采用[2-3]?；谖⒎盏膽贸绦蜻\行時，通常涉及多個微服務的執行和互操作，每個微服務獨立實現、部署、更新[4-5]。盡管這種新的架構給開發人員帶來了便利，但系統維護多個并發服務正常運行的同時，還需要保證服務之間的交互協作，這為基于微服務開發的任務調度帶來了挑戰[6-7]。

目前，已經有許多基于微服務架構的任務調度研究。文獻[8]利用合作博弈論提出了一個多目標函數，通過考慮內存、CPU、用戶預算等不同約束條件來降低節點能耗和任務最大完工時間。文獻[9]考慮計算資源的異構特點，提出了一種針對異構多云環境的多目標任務調度算法。文獻[10]考慮計算及存儲資源的成本，設計了考慮定價機制的多目標云工作流調度模型，有效提高了云平臺資源利用率。文獻[11]同時考慮任務調度與微服務的伸縮性，在滿足任務截止時間的同時最小化部署服務的成本。文獻[12]提出了一個基于多代理的開發框架，用于處理微服務體系結構中的分布式事務。

在已有的研究中，研究人員較多考慮容器調度和資源管理對基于微服務的應用程序性能的影響，而忽略了多條微服務鏈訪問共享微服務時產生的資源競爭問題。然而，用戶每發起一次請求往往牽扯多個微服務的調用，當需要處理大量用戶請求時，多條微服務鏈會產生多個交叉點，從而導致微服務間資源的競爭問題。綜上所述，筆者將主要工作聚焦于微服務之間的競爭問題，設計了一種面向鏈的微服務任務調度算法來解決微服務鏈的交叉競爭問題，在提高資源利用率的同時，降低了任務執行的全局響應時間。

1 系統模型

假設一個小型應用程序中微服務的調用關系如圖1所示，圖中有4條微服務鏈，經過9個微服務。其中，2號、5號、6號都是可能發生交叉競爭的微服務，若調度策略不當，則會導致服務響應時間增加。

圖1 一個小型應用程序中微服務的調用關系

為了對微服務鏈關系進行清晰表征，采用二進制編碼的方式進行描述，服務間的調用關系可以表示為

1.1 響應時間模型

每個任務的完工時間包含當前執行任務的前繼任務的結束時間以及自身執行任務花費的時間。單個物理節點的完工時間取決于在該節點上執行的任務隊列中最后一個任務的結束時間。

微服務鏈i上服務j在物理節點p上處理任務的執行用時ri，j為

ri，j=hi，j/xp，

(1)

其中，hi，j表示鏈i上服務j所需處理的任務大小，xp表示物理節點p的處理能力。

鏈i上服務j的開始執行的時間為bi，j，物理節點p的完工時間fp可表示為

fp=max(ri，j+bi，j) 。

(2)

請求響應時間取決于最晚結束工作的物理節點的完工時間，全局響應時間Tglobal計算如下：

Tglobal=max(fp) 。

(3)

為保證單條服務鏈能合理執行，必須對任務的處理順序進行約束，即在同一條鏈上，調用順序靠后的服務必須在它的前繼服務完工后才能執行，約束如下：

bi，j+1-bi，j≥ri，j，

(4)

其中，bi，j+1為鏈i上依賴于服務j的服務j+1的開始時間。

用Zi，j，p來表示鏈i上的服務j是否在物理節點p上處理。如果是，則Zi，j，p=1；反之，則取Zi，j，p=0。為保證在同一時刻有且僅有一個服務能夠在物理節點p上運行，設計以下約束：

Zi，j，p=Zv，w，p=1，bv，w-bi，j≥ri，j。

(5)

該約束表示鏈i上的服務j和鏈v上的服務w都需要在物理節點p上處理時，服務w的開始時間要大于等于服務j的結束時間。

1.2 資源利用率模型

在集群物理資源有限的情況下，應盡可能最大化的利用物理資源。定義矩陣A來表示鏈和服務之間的關系：

A=(ac，m)C×M，

(6)

其中，C是微服務鏈的總數，M是微服務類型總數。ac，m∈{0，1}，ac，m取0時表示微服務鏈c沒有穿過微服務m，反之取1。

應用的特征表示為〈Gset，Grelation〉，其中Gset是應用程序的微服務集；Grelation是服務之間的消費關系集。當一個微服務需要其他微服務生成的結果時，將建立消費關系，表示為(mcons，mprov)∈Grelation。矩陣S表示微服務節點上的資源分配情況：

S=(sc，m)C×M，

(7)

其中，sc，m表示鏈c上服務m所需要的資源數。

每個物理節點所擁有的資源數量用Im表示，則總資源數I可以表示為

(8)

鏈中微服務分配的資源不能超過部署該微服務的節點擁有的資源數，具體限制如下：

(9)

將單位時間內節點的資源利用率Ut形式化為

(10)

其中，E表示單位時間內正在執行的鏈的集合。時間Tglobal內的總體資源利用率U計算如下：

(11)

1.3 多目標優化模型

基于上述兩小節的時間模型和資源模型可以得出以下多目標優化模型：

maxU，

(12)

minTglobal，

(13)

(14)

bi，j+1-bi，j≥ri，j，

(15)

Zi，j，p=Zv，w，p=1，bv，w-bi，j≥ri，j。

(16)

式(12)表示當總資源數一定時，最大化每一時刻的資源利用率之和同整條服務鏈的響應時間之比；式(13)表示最小化最晚響應服務的物理節點的全局響應時間；式(14)表示分配給任務的資源數不能超過節點的資源量；式(15)表示鏈中服務必須在其前繼服務結束之后開始執行；式(16)表示每個節點在同一時刻只能處理一個任務請求。

2 面向交叉微服務鏈的任務調度算法設計

基于上述系統模型，為解決微服務調用鏈間的競爭問題，受閆群民等人[13]的啟發，筆者將蟻群算法同模擬退火算法結合，提出了一種面向交叉微服務鏈的任務調度算法(Chain-Oriented Task Scheduling Algorithm，COTSA)。COTSA在蟻群并行尋求可行解過程中加入模擬退火的降溫和Metropolis準則[14]，來降低螞蟻走到局部最優的可能性。

2.1 關鍵函數及算法實現

2.1.1 蟻群的路徑選擇算法

算法將服務調用鏈看作一個森林，根據服務間的調用關系進行拓撲排序，排序結果構成n棵樹。每次螞蟻k必須選擇森林中的根節點，將根節點加入待訪問集合Callow(k)。當螞蟻k基于轉移概率選擇Callow(k)集合中節點n作為下一個訪問對象時，將該節點從Callow(k)中刪除，此時在樹中n的子節點將成為新的根節點加入集合Callow(k)供螞蟻k進行下一次的訪問。螞蟻選擇路徑的轉移概率為

(17)

其中，Callow(k)表示滿足約束條件的一組可用節點；τi，j(t)表示鏈i上服務j在t時刻的信息濃度函數；ηi，j(t)表示鏈i上服務j在t時刻的啟發函數；λ1和λ2分別是信息素和啟發式信息的調節器，值越大表明啟發函數對選擇路徑的影響越大。啟發函數可表示為

(18)

其中，bi，j+ri，j表示截止到t時刻，鏈i執行到服務j的總時間；Tave表示在當前最優解情況下每個節點處理請求的平均運行時間。螞蟻的路徑選擇算法如算法1所示。

算法1螞蟻的路徑選擇算法。

① 輸入任務拓撲排序結果集合

② for 序列 in 拓撲 do

③ if 存在以序列初始節點為根的樹 then

④ 根據節點的前后繼關系使用深度搜索構建樹

⑤ else

⑥ 將當前序列的初始節點初始化為新的根節點

⑦ end if

⑧ 將新的根節點存入森林集合cforest

⑨ end for

⑩ for n in do

一旦螞蟻遍歷所有微服務，它經過的路徑就可以作為一個可行解。為了得到最佳的可行解，需要對得到的可行解進行評估。根據筆者建立的多目標優化模型，將評估函數可表示為

E(X)=αU(X)+β[Tglobal(X)]-1，

(19)

其中，α和β分別是資源利用率和響應時間的權重系數。E(X)的值越大，X越接近最佳值，文中經過多組實驗對比，將α和β的數值選定為0.8和0.2。

2.1.2 信息素更新

信息素更新如下所示：

τi，j(t+1)=(1-ρ)τi，j(t)+Δτi，j，

(20)

其中，τi，j(t)是路徑ri，j時間t時的信息素；τi，j(t+1)是更新的信息素；信息素初始值為τi，j(t0)=1；信息素的消散因子為ρ，ρ∈(0，1)；1-ρ是信息素的揮發程度；Δτi，j是一次迭代后路徑ri，j上增加的信息素濃度。Δτi，j的計算公式為

(21)

(22)

2.1.3 模擬退火算法中生成新可行解的擾動策略

為了能夠加快蟻群算法的收斂速度，引入模擬退火算法，即每次螞蟻遍歷完所有服務后并不是立即返回到源點，而是隨機交換在樹中層數相同的兩個節點生成新的可行解。將生成的新解的評估值同擾動前的解的評估值根據

ΔE=Ek-Q，

(23)

進行比較，得到兩個解的差值。其中，Ek表示新的可行解的評估值；Q表示最優可行解的評估值；ΔE是評估新的可行解同當前最優可行解的差值，如果小于0，則表示新產生的可行解不如當前最優解。如果新產生的任務執行序列的資源利用率和任務響應時間優于當前解，則將其更新為最優解；否則，根據模擬退火的Metropolis準則判斷是否接受新解。根據下式計算接受新解的概率：

(24)

2.2 算法流程

初始將多只螞蟻都放置在超級源點上，蟻群會根據用戶請求的不同隨機爬行到不同的起始服務上，設定模擬退火中的初始溫度并將初始信息素設定為固定的數值。隨后通過上述中螞蟻對路徑的選擇策略，選取要經過的節點。當所有螞蟻都走到終點的時候，將路徑上的信息素更新，同時保留所有爬行路徑。COTSA算法偽代碼如算法2所示。

算法2COTSA算法。

① 初始化信息素矩陣

② whileT>Tmindo

③ foriinN

④ 將所有螞蟻放置在超級源點上

⑤ forkinKdo

⑥ 對服務之間的依賴關系進行拓撲排序

⑦ 分析排序結果得到螞蟻行走的可行點集合

⑧ 螞蟻k根據算法1的路徑選取策略，從當前點走到下一個滿足條件的物理節點，并將該點加入ri，j

⑨ end for

⑩ 根據式(21)對信息素矩陣進行更新

3 實 驗

3.1 實驗設置

將COTSA算法與先來先服務算法(First Come First Service，FCFS)和傳統的蟻群算法(Ant Colong Optimization，ACO)從全局響應時間和資源利用率兩方面進行比較。實驗測試數據集采用阿里巴巴集群跟蹤V2018集群數據集[15]。該數據集由6張表組成，提供了機器和容器的信息及資源使用情況，事件信息和工作負載的實例信息。表1描述了微服務之間的依賴關系以及微服消耗的資源數。Cconsume(i)表示微服務i消費的微服務集合，Rresource(i)表示微服務之執行時需要的物理資源數，Nrequest(i)表示微服務i的請求數，Nscale(i)表示部署了微服務i的容器數。

表1 微服務屬性參數

通過評估參數對算法的影響，設定參數如表2所示。

表2 COTSA中的參數設置

3.2 相關算法比較

對比實驗中，用戶請求數在100～500之間變化，初始請求個數為100。

3.2.1 全局響應時間

圖2所示為3種算法在用戶請求的全局響應時間上的實驗對比。實驗結果表明，ACO算法的全局響應時間高于COTSA算法和FCFS算法的；當用戶請求數小于300時，COTSA算法和FCFS算法的全局響應時間相近；當用戶請求數高于300時，COTSA算法的全局響應時間相較ACO算法和FCFS算法分別降低了約12.67%和7.71%。這是由于COTSA算法結合了模擬退火算法的擾動策略，具有較好的局部搜索能力，提高了蟻群跳出局部最優的概率，故而找到了更好的可行解。

圖2 不同用戶請求數下的全局響應時間對比

3.2.2 單位時間內資源利用率

圖3分別展示了用戶請求量從100增加到400時，3種算法單位時間內的資源利用率。

(a)100個用戶請求時資源利用率

圖3中每條折線結束位置對應的時間即為3種算法求得調度序列所需要的執行用時?？梢钥闯觯噍^于FCFS，COTSA和ACO算法的資源利用率變化較為平緩。這是因為這兩種算法在進行調度優化時將平均資源利用率納入考慮范圍，在不影響服務之間前后繼關系的前提下，調度排在后面的任務執行，以盡可能地減少物理資源的空閑時間，提高單位時間內資源利用率。

3.2.3 整體資源利用率

針對請求處理過程中的整體資源利用情況，對FCFS、ACO和COTSA 這3種算法進行了對比實驗，實驗結果如圖4所示。

圖4 不同用戶請求數下的整體資源利用率對比

從圖4可以看出，使用FCFS算法時，集群的資源利用率隨著用戶請求數的增多而逐漸降低，而ACO和COTSA由于任務調度的不確定性使得資源利用率的整體趨勢呈上升狀態。此外，COTSA在產生可行解的時候增大了跳出局部最優的概率，隨著用戶請求數的增多，解空間變大，COTSA通過在當前解的鄰域中隨機置換生成新的可行解，從而比ACO算法更容易找到全局最優解，故整體的資源利用率會高于ACO算法。結果表明，COTSA算法在資源利用率方面是優于FCFS算法和ACO算法的，相比這兩種算法分別提高了約61.29%和44.68%。

4 結束語

針對微服務調用鏈間的資源競爭問題，以減少請求的全局響應時間及提高整體資源利用率為優化目標，筆者建立了多目標優化模型。同時，結合蟻群算法并行計算與模擬退火算法局部擾動的優勢提出了COTSA算法對優化模型進行求解，得到調度決策。與FCFS算法和ACO算法相比，COTSA算法在減少請求的全局響應時間以及提高集群的整體資源利用率方面具有明顯優勢。