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

(西安電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710071)

隨著云計(jì)算和容器技術(shù)的發(fā)展[1]，微服務(wù)架構(gòu)已經(jīng)越來越多地被應(yīng)用程序設(shè)計(jì)和開發(fā)采用[2-3]?；谖⒎?wù)的應(yīng)用程序運(yùn)行時(shí)，通常涉及多個(gè)微服務(wù)的執(zhí)行和互操作，每個(gè)微服務(wù)獨(dú)立實(shí)現(xiàn)、部署、更新[4-5]。盡管這種新的架構(gòu)給開發(fā)人員帶來了便利，但系統(tǒng)維護(hù)多個(gè)并發(fā)服務(wù)正常運(yùn)行的同時(shí)，還需要保證服務(wù)之間的交互協(xié)作，這為基于微服務(wù)開發(fā)的任務(wù)調(diào)度帶來了挑戰(zhàn)[6-7]。

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

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

1 系統(tǒng)模型

假設(shè)一個(gè)小型應(yīng)用程序中微服務(wù)的調(diào)用關(guān)系如圖1所示，圖中有4條微服務(wù)鏈，經(jīng)過9個(gè)微服務(wù)。其中，2號、5號、6號都是可能發(fā)生交叉競爭的微服務(wù)，若調(diào)度策略不當(dāng)，則會導(dǎo)致服務(wù)響應(yīng)時(shí)間增加。

圖1 一個(gè)小型應(yīng)用程序中微服務(wù)的調(diào)用關(guān)系

為了對微服務(wù)鏈關(guān)系進(jìn)行清晰表征，采用二進(jìn)制編碼的方式進(jìn)行描述，服務(wù)間的調(diào)用關(guān)系可以表示為

1.1 響應(yīng)時(shí)間模型

每個(gè)任務(wù)的完工時(shí)間包含當(dāng)前執(zhí)行任務(wù)的前繼任務(wù)的結(jié)束時(shí)間以及自身執(zhí)行任務(wù)花費(fèi)的時(shí)間。單個(gè)物理節(jié)點(diǎn)的完工時(shí)間取決于在該節(jié)點(diǎn)上執(zhí)行的任務(wù)隊(duì)列中最后一個(gè)任務(wù)的結(jié)束時(shí)間。

微服務(wù)鏈i上服務(wù)j在物理節(jié)點(diǎn)p上處理任務(wù)的執(zhí)行用時(shí)ri，j為

ri，j=hi，j/xp，

(1)

其中，hi，j表示鏈i上服務(wù)j所需處理的任務(wù)大小，xp表示物理節(jié)點(diǎn)p的處理能力。

鏈i上服務(wù)j的開始執(zhí)行的時(shí)間為bi，j，物理節(jié)點(diǎn)p的完工時(shí)間fp可表示為

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

(2)

請求響應(yīng)時(shí)間取決于最晚結(jié)束工作的物理節(jié)點(diǎn)的完工時(shí)間，全局響應(yīng)時(shí)間Tglobal計(jì)算如下：

Tglobal=max(fp) 。

(3)

為保證單條服務(wù)鏈能合理執(zhí)行，必須對任務(wù)的處理順序進(jìn)行約束，即在同一條鏈上，調(diào)用順序靠后的服務(wù)必須在它的前繼服務(wù)完工后才能執(zhí)行，約束如下：

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

(4)

其中，bi，j+1為鏈i上依賴于服務(wù)j的服務(wù)j+1的開始時(shí)間。

用Zi，j，p來表示鏈i上的服務(wù)j是否在物理節(jié)點(diǎn)p上處理。如果是，則Zi，j，p=1；反之，則取Zi，j，p=0。為保證在同一時(shí)刻有且僅有一個(gè)服務(wù)能夠在物理節(jié)點(diǎn)p上運(yùn)行，設(shè)計(jì)以下約束：

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

(5)

該約束表示鏈i上的服務(wù)j和鏈v上的服務(wù)w都需要在物理節(jié)點(diǎn)p上處理時(shí)，服務(wù)w的開始時(shí)間要大于等于服務(wù)j的結(jié)束時(shí)間。

1.2 資源利用率模型

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

A=(ac，m)C×M，

(6)

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

應(yīng)用的特征表示為〈Gset，Grelation〉，其中Gset是應(yīng)用程序的微服務(wù)集；Grelation是服務(wù)之間的消費(fèi)關(guān)系集。當(dāng)一個(gè)微服務(wù)需要其他微服務(wù)生成的結(jié)果時(shí)，將建立消費(fèi)關(guān)系，表示為(mcons，mprov)∈Grelation。矩陣S表示微服務(wù)節(jié)點(diǎn)上的資源分配情況：

S=(sc，m)C×M，

(7)

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

每個(gè)物理節(jié)點(diǎn)所擁有的資源數(shù)量用Im表示，則總資源數(shù)I可以表示為

(8)

鏈中微服務(wù)分配的資源不能超過部署該微服務(wù)的節(jié)點(diǎn)擁有的資源數(shù)，具體限制如下：

(9)

將單位時(shí)間內(nèi)節(jié)點(diǎn)的資源利用率Ut形式化為

(10)

其中，E表示單位時(shí)間內(nèi)正在執(zhí)行的鏈的集合。時(shí)間Tglobal內(nèi)的總體資源利用率U計(jì)算如下：

(11)

1.3 多目標(biāo)優(yōu)化模型

基于上述兩小節(jié)的時(shí)間模型和資源模型可以得出以下多目標(biāo)優(yōu)化模型：

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)表示當(dāng)總資源數(shù)一定時(shí)，最大化每一時(shí)刻的資源利用率之和同整條服務(wù)鏈的響應(yīng)時(shí)間之比；式(13)表示最小化最晚響應(yīng)服務(wù)的物理節(jié)點(diǎn)的全局響應(yīng)時(shí)間；式(14)表示分配給任務(wù)的資源數(shù)不能超過節(jié)點(diǎn)的資源量；式(15)表示鏈中服務(wù)必須在其前繼服務(wù)結(jié)束之后開始執(zhí)行；式(16)表示每個(gè)節(jié)點(diǎn)在同一時(shí)刻只能處理一個(gè)任務(wù)請求。

2 面向交叉微服務(wù)鏈的任務(wù)調(diào)度算法設(shè)計(jì)

基于上述系統(tǒng)模型，為解決微服務(wù)調(diào)用鏈間的競爭問題，受閆群民等人[13]的啟發(fā)，筆者將蟻群算法同模擬退火算法結(jié)合，提出了一種面向交叉微服務(wù)鏈的任務(wù)調(diào)度算法(Chain-Oriented Task Scheduling Algorithm，COTSA)。COTSA在蟻群并行尋求可行解過程中加入模擬退火的降溫和Metropolis準(zhǔn)則[14]，來降低螞蟻?zhàn)叩骄植孔顑?yōu)的可能性。

2.1 關(guān)鍵函數(shù)及算法實(shí)現(xiàn)

2.1.1 蟻群的路徑選擇算法

算法將服務(wù)調(diào)用鏈看作一個(gè)森林，根據(jù)服務(wù)間的調(diào)用關(guān)系進(jìn)行拓?fù)渑判?，排序結(jié)果構(gòu)成n棵樹。每次螞蟻k必須選擇森林中的根節(jié)點(diǎn)，將根節(jié)點(diǎn)加入待訪問集合Callow(k)。當(dāng)螞蟻k基于轉(zhuǎn)移概率選擇Callow(k)集合中節(jié)點(diǎn)n作為下一個(gè)訪問對象時(shí)，將該節(jié)點(diǎn)從Callow(k)中刪除，此時(shí)在樹中n的子節(jié)點(diǎn)將成為新的根節(jié)點(diǎn)加入集合Callow(k)供螞蟻k進(jìn)行下一次的訪問。螞蟻選擇路徑的轉(zhuǎn)移概率為

(17)

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

(18)

其中，bi，j+ri，j表示截止到t時(shí)刻，鏈i執(zhí)行到服務(wù)j的總時(shí)間；Tave表示在當(dāng)前最優(yōu)解情況下每個(gè)節(jié)點(diǎn)處理請求的平均運(yùn)行時(shí)間。螞蟻的路徑選擇算法如算法1所示。

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

① 輸入任務(wù)拓?fù)渑判蚪Y(jié)果集合

② for 序列 in 拓?fù)?do

③ if 存在以序列初始節(jié)點(diǎn)為根的樹 then

④ 根據(jù)節(jié)點(diǎn)的前后繼關(guān)系使用深度搜索構(gòu)建樹

⑤ else

⑥ 將當(dāng)前序列的初始節(jié)點(diǎn)初始化為新的根節(jié)點(diǎn)

⑦ end if

⑧ 將新的根節(jié)點(diǎn)存入森林集合cforest

⑨ end for

⑩ for n in do

一旦螞蟻遍歷所有微服務(wù)，它經(jīng)過的路徑就可以作為一個(gè)可行解。為了得到最佳的可行解，需要對得到的可行解進(jìn)行評估。根據(jù)筆者建立的多目標(biāo)優(yōu)化模型，將評估函數(shù)可表示為

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

(19)

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

2.1.2 信息素更新

信息素更新如下所示：

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

(20)

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

(21)

(22)

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

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

ΔE=Ek-Q，

(23)

進(jìn)行比較，得到兩個(gè)解的差值。其中，Ek表示新的可行解的評估值；Q表示最優(yōu)可行解的評估值；ΔE是評估新的可行解同當(dāng)前最優(yōu)可行解的差值，如果小于0，則表示新產(chǎn)生的可行解不如當(dāng)前最優(yōu)解。如果新產(chǎn)生的任務(wù)執(zhí)行序列的資源利用率和任務(wù)響應(yīng)時(shí)間優(yōu)于當(dāng)前解，則將其更新為最優(yōu)解；否則，根據(jù)模擬退火的Metropolis準(zhǔn)則判斷是否接受新解。根據(jù)下式計(jì)算接受新解的概率：

(24)

2.2 算法流程

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

算法2COTSA算法。

① 初始化信息素矩陣

② whileT>Tmindo

③ foriinN

④ 將所有螞蟻放置在超級源點(diǎn)上

⑤ forkinKdo

⑥ 對服務(wù)之間的依賴關(guān)系進(jìn)行拓?fù)渑判?/p>

⑦ 分析排序結(jié)果得到螞蟻行走的可行點(diǎn)集合

⑧ 螞蟻k根據(jù)算法1的路徑選取策略，從當(dāng)前點(diǎn)走到下一個(gè)滿足條件的物理節(jié)點(diǎn)，并將該點(diǎn)加入ri，j

⑨ end for

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

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

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

表1 微服務(wù)屬性參數(shù)

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

表2 COTSA中的參數(shù)設(shè)置

3.2 相關(guān)算法比較

對比實(shí)驗(yàn)中，用戶請求數(shù)在100～500之間變化，初始請求個(gè)數(shù)為100。

3.2.1 全局響應(yīng)時(shí)間

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

圖2 不同用戶請求數(shù)下的全局響應(yīng)時(shí)間對比

3.2.2 單位時(shí)間內(nèi)資源利用率

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

(a)100個(gè)用戶請求時(shí)資源利用率

圖3中每條折線結(jié)束位置對應(yīng)的時(shí)間即為3種算法求得調(diào)度序列所需要的執(zhí)行用時(shí)?？梢钥闯?，相較于FCFS，COTSA和ACO算法的資源利用率變化較為平緩。這是因?yàn)檫@兩種算法在進(jìn)行調(diào)度優(yōu)化時(shí)將平均資源利用率納入考慮范圍，在不影響服務(wù)之間前后繼關(guān)系的前提下，調(diào)度排在后面的任務(wù)執(zhí)行，以盡可能地減少物理資源的空閑時(shí)間，提高單位時(shí)間內(nèi)資源利用率。

3.2.3 整體資源利用率

針對請求處理過程中的整體資源利用情況，對FCFS、ACO和COTSA 這3種算法進(jìn)行了對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4所示。

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

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

4 結(jié)束語

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