基于多目標(biāo)遺傳算法的微服務(wù)粒度識(shí)別方法

袁海銘

（昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500）

0 引 言

近年來(lái)，微服務(wù)架構(gòu)的提出改變了應(yīng)用程序創(chuàng)建、測(cè)試、實(shí)現(xiàn)及維護(hù)的方式。而微服務(wù)架構(gòu)在給人們帶來(lái)便捷的同時(shí)，也存在一些明顯的問(wèn)題。其中，如何確定微服務(wù)的適當(dāng)大?。６龋?，是最常被討論的問(wèn)題之一。HASSAN 等人[1]提出了微服務(wù)環(huán)境，它是一種針對(duì)微服務(wù)粒度的體系結(jié)構(gòu)元建模方法，使用“切面”來(lái)定義在運(yùn)行時(shí)支持粒度變化所需的適應(yīng)行為。HASSELBRING 等人[2]為了達(dá)到足夠的粒度，建議在整個(gè)業(yè)務(wù)服務(wù)的自包含系統(tǒng)中進(jìn)行垂直分解。GOUIGOUX 等人[3]解釋說(shuō)，粒度的選擇應(yīng)該基于質(zhì)量保證成本和部署成本之間的平衡。本文旨在利用多目標(biāo)遺傳算法，以敏捷方法中的用戶故事這一概念作為輸入，來(lái)對(duì)微服務(wù)架構(gòu)的粒度劃分進(jìn)行研究。當(dāng)前，微服務(wù)的拆分主要應(yīng)用于棕地應(yīng)用領(lǐng)域（即現(xiàn)有系統(tǒng)遷移到微服務(wù)），很少有研究針對(duì)綠地應(yīng)用領(lǐng)域（即重新構(gòu)建一個(gè)新的系統(tǒng)），因?yàn)閷误w系統(tǒng)重構(gòu)為微服務(wù)系統(tǒng)的傳統(tǒng)觀念一直影響著相關(guān)從業(yè)人員。本文研究將主要集中于構(gòu)建新的微服務(wù)應(yīng)用程序，即“綠地問(wèn)題”。從一組功能需求開(kāi)始，這些需求在產(chǎn)品待辦事項(xiàng)（Product Backlog）[4]中以用戶故事的形式表現(xiàn)出來(lái)；通過(guò)以用戶故事之間的依賴關(guān)系作為輸入，使用多目標(biāo)遺傳算法中的NSGAII 算法對(duì)微服務(wù)粒度進(jìn)行識(shí)別。本文的主要貢獻(xiàn)在于提出了用于識(shí)別微服務(wù)粒度的模型，建立分配給微服務(wù)的用戶故事數(shù)量和作為應(yīng)用程序一部分的微服務(wù)數(shù)量，確保微服務(wù)具有低耦合性和高內(nèi)聚性。通過(guò)對(duì)比NSGAII 算法與另外三種多目標(biāo)優(yōu)化算法的性能指標(biāo)來(lái)對(duì)算法優(yōu)劣做出評(píng)價(jià)，輔助架構(gòu)師做出合理的微服務(wù)拆分決策。

1 微服務(wù)粒度模型的建立

確定微服務(wù)粒度模型，可以明確對(duì)微服務(wù)粒度產(chǎn)生影響的相關(guān)指標(biāo)有哪些，并在這些指標(biāo)的基礎(chǔ)上得出相應(yīng)的目標(biāo)函數(shù)。目標(biāo)函數(shù)旨在最小化耦合指標(biāo)和加權(quán)服務(wù)接口數(shù)指標(biāo)，最大化內(nèi)聚性指標(biāo)。目標(biāo)函數(shù)將在粒度模型提出之后定義，本文將基于微服務(wù)架構(gòu)的應(yīng)用程序的粒度模型表示為：

式中：MS表示一組微服務(wù)集，MS={MS1,MS2,…,MSn}；而MTS是一組為MSGM計(jì)算的指標(biāo)。然后：

式中：MSi是第i個(gè)微服務(wù)，US是與第i個(gè)微服務(wù)相關(guān)的用戶故事集，可以給出US={US1,US2,…,USn}，MTS是一組計(jì)算MSi的指標(biāo)。在這種情況下，模型中計(jì)算和使用的指標(biāo)對(duì)應(yīng)于耦合性、內(nèi)聚性以及與微服務(wù)相關(guān)的用戶故事數(shù)量。這些指標(biāo)的定義如下。

1.1 耦合性指標(biāo)

將耦合指標(biāo)定義為Coup={AIS,ADS,SIY}，其中，AIS表示服務(wù)的絕對(duì)重要性，ADS表示服務(wù)的絕對(duì)依賴性，SIY表示服務(wù)的相互依賴性。這些指標(biāo)是根據(jù)每個(gè)微服務(wù)的用戶故事的依賴性來(lái)計(jì)算的。

AISi是至少調(diào)用一個(gè)微服務(wù)操作的客戶數(shù)量。在系統(tǒng)層面，定義AIS向量。該向量包含每個(gè)微服務(wù)計(jì)算出的AIS值，因此在計(jì)算其系統(tǒng)級(jí)上的值時(shí)，可以將其定義為：ADSi是第i個(gè)微服務(wù)所依賴的其他微服務(wù)的數(shù)量。可以將其定義為：

SIY定義了相互依賴的微服務(wù)對(duì)的數(shù)量除以微服務(wù)的總數(shù)量，其被定義為：

用Coup代表這三種指標(biāo)的合并，可以將Coup表示為：

1.2 內(nèi)聚性指標(biāo)

同理，第i個(gè)微服務(wù)的內(nèi)聚性定義為缺乏內(nèi)聚性度量（LC），每個(gè)微服務(wù)的內(nèi)聚度定義為缺乏內(nèi)聚性度量除以作為應(yīng)用一部分的微服務(wù)總數(shù)的比例。

式中：n表示微服務(wù)的數(shù)量，則Coh可以表示為：

加權(quán)服務(wù)接口數(shù)量（Weighted Service Interface Count，WSIC）這一指標(biāo)概念源于面向服務(wù)架構(gòu)（Service-Oriented Architecture，SOA）的設(shè)計(jì)指標(biāo)，它表示W(wǎng)SDL 文檔（一種簡(jiǎn)單的XML 文檔，包含一系列描述某個(gè)網(wǎng)絡(luò)服務(wù)的定義）中定義的每個(gè)服務(wù)公開(kāi)接口或操作的加權(quán)數(shù)，默認(rèn)權(quán)重設(shè)置為1。對(duì)于本文的模型，用戶故事與操作相關(guān)，因此將這個(gè)指標(biāo)調(diào)整為與微服務(wù)相關(guān)的用戶故事的數(shù)量。采用WSIC作為分配給每個(gè)微服務(wù)的用戶故事數(shù)。然后將WsicT定義為與微服務(wù)相關(guān)聯(lián)的最大用戶故事數(shù)，可以將其表示為：

在內(nèi)聚性與耦合性指標(biāo)的基礎(chǔ)上，結(jié)合加權(quán)服務(wù)接口數(shù)量，可以將目標(biāo)函數(shù)表達(dá)為以下等式：

式（10）可以確定分解的結(jié)果是好是壞。一個(gè)低的目標(biāo)函數(shù)值是模型想要獲得的，因?yàn)槟Ｐ偷哪繕?biāo)是獲得一個(gè)較低缺乏內(nèi)聚度量、低耦合以及較小的加權(quán)服務(wù)接口數(shù)量的解決方案，最后通過(guò)多目標(biāo)優(yōu)化遺傳算法試圖找到指標(biāo)間最好的組合。

2 基于多目標(biāo)搜索遺傳算法的微服務(wù)識(shí)別

遺傳算法由HOLLAND 等人[5]首次提出，它是具有迭代性的。在每次迭代中，選擇最優(yōu)的個(gè)體，每個(gè)個(gè)體都有一條染色體，與另一個(gè)個(gè)體雜交產(chǎn)生新的種群，產(chǎn)生一些突變來(lái)尋找問(wèn)題的最優(yōu)解。而在遺傳算法中，為了解決多目標(biāo)問(wèn)題，將使用非支配排序遺傳算法（NSGA-II）。NSGA-II 在軟件重構(gòu)中得到了廣泛的應(yīng)用。這種有效的遺傳技術(shù)可以在近似最優(yōu)解所在的位置搜索分布良好的帕累托前沿，最后得到一組帕累托最優(yōu)解，這些解就是最后的目標(biāo)解。本文的遺傳算法包括自動(dòng)分配或分配用戶故事給微服務(wù)，考慮耦合和內(nèi)聚指標(biāo)，實(shí)現(xiàn)方法如下。

2.1 初始種群的生成

假設(shè)根據(jù)用戶的需求和架構(gòu)師的設(shè)計(jì)，得到一組用戶故事集US={US1,US2,…,USm}，這些用戶故事必須分配給它們所屬的微服務(wù)，有一組微服務(wù)集MS={MS1,MS2,…,MSn}以及從用戶故事中包含的信息計(jì)算出的一些指標(biāo)。父代染色體的定義是從用戶故事分配到微服務(wù)，采用二進(jìn)制編碼，1 表示某個(gè)用戶故事分配給一個(gè)微服務(wù)，而0 表示沒(méi)有用戶故事分配給微服務(wù)，由此可以得到一個(gè)分配矩陣，其中列為用戶故事，行為微服務(wù)?，F(xiàn)給出示例，假設(shè)有兩個(gè)微服務(wù)MS={MS1,MS2}和5 個(gè)用戶故事US={US1,US2,US3,US4,US5}的例子。矩陣如表1 所示：

表1 用戶故事與微服務(wù)對(duì)應(yīng)表

通過(guò)該矩陣圖可以看出，用戶故事2、用戶故事3、用戶故事5 被分配到微服務(wù)1 中，而用戶故事1、用戶故事4 被分配到微服務(wù)2 中。這樣一來(lái)，就可以得到父代的染色體。染色體將是每個(gè)用戶故事分配給每個(gè)微服務(wù)的并集，對(duì)于本文的假設(shè)，它將是01101 10010?；谶@條染色體，定義適應(yīng)函數(shù)或目標(biāo)函數(shù)。該目標(biāo)函數(shù)基于所提出的耦合性指標(biāo)、內(nèi)聚性指標(biāo)以及用戶故事指標(biāo)的組合。所使用的目標(biāo)函數(shù)如下：

2.2 交叉算子介紹

一個(gè)不同的分配將從選定的父代生成。在這種情況下，雙親是從種群中隨機(jī)選擇的，為了生成子節(jié)點(diǎn)信息，需要從雙親節(jié)點(diǎn)獲取信息，從分配矩陣中獲取父節(jié)點(diǎn)的第一列，并連接母節(jié)點(diǎn)的最后一列，生成一個(gè)新的分配。此過(guò)程必須考慮到一個(gè)問(wèn)題，即一個(gè)用戶故事不能被分配兩次，這意味著在分配矩陣中，每一列都只能出現(xiàn)一個(gè)用戶故事。在實(shí)驗(yàn)中，將使用SBXcrossover 交叉算子。

2.3 變異方法

突變表示隨機(jī)地改變一個(gè)染色體。在本文的問(wèn)題中，突變表示染色體從1 到0 或者從0 到1 的改變，這意味著一個(gè)用戶故事被分配到或者沒(méi)有被分配到一個(gè)微服務(wù)，以及必須分配或者沒(méi)有被分配到另一個(gè)微服務(wù)。因此，染色體上將有兩個(gè)基因發(fā)生改變，示例如下。所獲得的染色體的第七位發(fā)生突變01101 10010，突變后的染色體為01101 11010。

在這種情況下，染色體的第七位基因0 必須改為1，即矩陣中第二列中的用戶故事必須分配給第二個(gè)微服務(wù)，同時(shí)從第一個(gè)微服務(wù)中取消分配。突變的染色體必須包含在群體中。這個(gè)過(guò)程是隨機(jī)進(jìn)行的，從種群中選擇要突變的個(gè)體，也隨機(jī)進(jìn)行基因的突變，對(duì)于突變目標(biāo)函數(shù)的值被計(jì)算并包含在總體中。

2.4 參數(shù)設(shè)置

根據(jù)NSGAII 算法的現(xiàn)有工作校準(zhǔn)了關(guān)于實(shí)驗(yàn)的參數(shù)，將種群規(guī)模設(shè)置為25 個(gè)個(gè)體，因?yàn)楦鶕?jù)實(shí)驗(yàn)，這一設(shè)置能夠?qū)崿F(xiàn)有效性和效率之間的平衡。使用0.8 作為交叉概率，0.05×log2(n)作為變異概率。將最大代數(shù)配置為200 次，搜索過(guò)程重復(fù)30 次，以減少遺傳算法隨機(jī)性造成的偏差。

2.5 候選微服務(wù)的獲取

在CargoTracking 的示例中，通過(guò)NSGA-ii 算法的處理，使用Matlab 對(duì)算法進(jìn)行編碼。輸入用戶故事依賴，得到4 個(gè)由用戶故事組成的微服務(wù)，分別如圖1、圖2 所示。

圖1 用戶故事依賴輸入圖

圖2 微服務(wù)粒度識(shí)別結(jié)果圖

3 多目標(biāo)優(yōu)化算法性能對(duì)比

將NSGAII 算法與另外三種主流多目標(biāo)優(yōu)化算法的性能指標(biāo)進(jìn)行對(duì)比，來(lái)比較不同多目標(biāo)優(yōu)化算法之間對(duì)于識(shí)別微服務(wù)粒度的效果而言的優(yōu)劣程度。首先對(duì)三種算法加以簡(jiǎn)要介紹。

第一種算法是強(qiáng)度帕累托進(jìn)化算法[6]（Strength Pareto Evolutionary Algorithm 2，SPEA2）。相比于SPEA 算法，SPEA2 采用了改進(jìn)的適應(yīng)度分配方式。該方式充分考慮了每個(gè)個(gè)體中所支配和被支配的個(gè)體數(shù)量，并且采用了最近鄰密度估計(jì)技術(shù)。這使其能夠更精確地指導(dǎo)搜索過(guò)程，另外還有一種新的存檔截?cái)喾椒ūＷC了邊緣解的保留。

第二種算法是基于分解的多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm Based on Decomposition，MOEA/D）[7]。該算法將一個(gè)多目標(biāo)優(yōu)化問(wèn)題劃分為多個(gè)標(biāo)量?jī)?yōu)化子問(wèn)題，并同時(shí)對(duì)子問(wèn)題進(jìn)行優(yōu)化。每個(gè)子問(wèn)題可僅通過(guò)運(yùn)用其他幾個(gè)鄰近子問(wèn)題的信息進(jìn)行優(yōu)化。通過(guò)這種方式，降低了計(jì)算復(fù)雜度，提升了算法的效率。

第三種算法是多目標(biāo)粒子群算法[8]（Multi-Objective Particle Swarm Optimization，MOPSO），是在粒子群優(yōu)化算法的基礎(chǔ)上實(shí)現(xiàn)的，其靈感來(lái)源于鳥(niǎo)群的編排。該算法也可被認(rèn)為是一種分布式行為算法，它采用群體智能的進(jìn)化技術(shù)，并由于其特殊的搜索機(jī)理以及優(yōu)異的收斂特性而被廣泛應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域。

3.1 性能指標(biāo)介紹

GD（Generational Distance） 和IGD（Inverted Generational Distance）是測(cè)量帕累托近似解和帕累托真實(shí)解之間收斂性（或緊密度）的性能指標(biāo)[9]。GD 是一種誤差度量，用于檢查通過(guò)算法得到的帕累托近似解（PFapprox）與已知帕累托最優(yōu)解（PFtrue）之間的距離。而IGD 是基于GD 的指標(biāo)，其目標(biāo)是評(píng)估帕累托最優(yōu)解（PFtrue）到帕累托近似解（PFapprox）的距離，它的逆由GD 來(lái)考慮。

GD 和IGD 的值趨向于零，是本文研究希望得到的，因?yàn)檫@就表明PFapprox和PFtrue的值比較接近。HV（Hyper Volume）測(cè)量從參考點(diǎn)到解決方案空間前沿的目標(biāo)空間面積，該指標(biāo)可以分析帕累托前沿的緊密度和多樣性。通過(guò)將解的前沿歸一化到[0，1]來(lái)計(jì)算這個(gè)指標(biāo)。具有高HV 值的帕累托前沿是最好的，因?yàn)樗鼈兊慕鉀Q方案遠(yuǎn)離參考點(diǎn)。4 種算法性能指標(biāo)的折線圖與條形圖如圖3、圖4、圖5所示。

圖3 基于GD 指標(biāo)的算法性能對(duì)比

圖4 基于IGD指標(biāo)的算法性能對(duì)比

圖5 基于HV 指標(biāo)的算法性能對(duì)比

3.2 性能指標(biāo)對(duì)比分析

為了評(píng)估不同的多目標(biāo)優(yōu)化算法的優(yōu)劣程度，對(duì)算法的性能指標(biāo)進(jìn)行分析。根據(jù)上一小節(jié)描述可知，本文研究希望獲得較小的GD和IGD值。因?yàn)檫@兩個(gè)性能指標(biāo)越小，說(shuō)明算法的求解性能就越好。較大的HV值、高HV值同樣說(shuō)明算法具有較好的求解性能。

從折線圖可以看出，對(duì)于GD值來(lái)說(shuō)，基于分解的多目標(biāo)遺傳算法的性能優(yōu)勢(shì)優(yōu)于其他三種多目標(biāo)優(yōu)化算法；從條形圖可以看出，NSGAII 算法與MOPSO 算法的性能差異不大，差于SPEA2 算法，而MOEA/D 算法的求解性能最好。

對(duì)于IGD值來(lái)說(shuō)，從折線圖可以看出，MOEA/D 算法的性能優(yōu)于其他三種算法；從條形圖可以看出，MOEA/D 算法的求解性能最好，NSGAII 算法和SPEA2 算法的性能差異不大，而MOPSO 算法的求解性能最差。

對(duì)于HV值來(lái)說(shuō)，從折線圖可以看出，SPEA2算法和NSGAII 算法明顯優(yōu)于其他兩種算法；從條形圖可以看出，SPEA2 算法的求解性能最好，NSGAII 算法和MOEA/D 算法的性能差異不大，MOPSO 算法求解性能最差。

通過(guò)比較算法性能指標(biāo)可得知，對(duì)于不同的性能指標(biāo)，不同算法的性能表現(xiàn)各有差異，但總體來(lái)說(shuō)，SPEA2 和NSGAII 兩種多目標(biāo)優(yōu)化算法具有更好的表現(xiàn)。

4 案例研究以及實(shí)驗(yàn)對(duì)比

案例研究中，使用微服務(wù)架構(gòu)領(lǐng)域的基于SpringBoot 框架的CargoTracking[10]應(yīng)用程序。該應(yīng)用程序是運(yùn)用領(lǐng)域驅(qū)動(dòng)設(shè)計(jì)（Domain Driven Design，DDD）進(jìn)行微服務(wù)劃分的經(jīng)典項(xiàng)目。CargoTracking的重點(diǎn)是通過(guò)路由規(guī)范在兩個(gè)地點(diǎn)之間進(jìn)行貨物的運(yùn)輸（由TrackingID 標(biāo)識(shí)）。一旦貨物可用，它就與從現(xiàn)有Voyages 中選擇的一個(gè)貨運(yùn)計(jì)劃相關(guān)聯(lián)，然后，HandlingEvents 跟蹤行程中貨物的進(jìn)度，完成貨物的追蹤，而貨物交付描述了具體的運(yùn)輸狀態(tài)、預(yù)計(jì)到達(dá)時(shí)間，以及該貨物當(dāng)前是否被跟蹤，且在航線上?；谶@一系列的業(yè)務(wù)邏輯，本文提取并提出了用戶故事，如表2 所示。

表2 用戶故事列表

其中，如何識(shí)別用戶故事之間的依賴，是一個(gè)比較重要的問(wèn)題。本文從程序源代碼中分析每個(gè)用戶故事之間的調(diào)用關(guān)系，通過(guò)調(diào)用關(guān)系來(lái)識(shí)別用戶故事之間的依賴。例如，要?jiǎng)?chuàng)建一個(gè)航行（voyage），必須首先獲得位置（Location），這意味著用戶故事1 依賴于用戶故事12。其他類似的用戶故事依賴如表3 所示。

以表3 中的用戶故事依賴作為輸入，使用NSGAII 算法對(duì)微服務(wù)粒度進(jìn)行識(shí)別，識(shí)別后得到的結(jié)果如表4 所示。

表3 用戶故事依賴表

表4 用戶故事分布對(duì)比表

將基于NSGAII 算法的微服務(wù)粒度識(shí)別方法與傳統(tǒng)的微服務(wù)粒度識(shí)別方法DDD（領(lǐng)域驅(qū)動(dòng)建模）的指標(biāo)進(jìn)行對(duì)比，從而選擇具有更好效果的方法。指標(biāo)評(píng)估如表5 所示。

表5 指標(biāo)評(píng)估表

具體評(píng)估過(guò)程為：根據(jù)用戶故事之間的依賴，計(jì)算得到所提出的指標(biāo)具體值，對(duì)微服務(wù)粒度的評(píng)估通過(guò)這些具體值的比較來(lái)實(shí)現(xiàn)。在耦合性指標(biāo)中，有4 種不同類型的指標(biāo)，分別是AisT，AdsT，SiyT以及這三種指標(biāo)的結(jié)合CoupT，比較本文方法與DDD 方法取得的這些參數(shù)的值，具有較小AisT值、AdsT值、SiyT值以及CoupT值的方法為最優(yōu)方法，因?yàn)橹递^小說(shuō)明所識(shí)別出的微服務(wù)粒度具有較低的耦合性。在內(nèi)聚性指標(biāo)中，使用CohT來(lái)進(jìn)行評(píng)估，比較本文方法與DDD 方法取得的CohT值，具有較大CohT值的方法為最優(yōu)方法，因?yàn)橹递^大說(shuō)明所識(shí)別出的微服務(wù)粒度具有較高的內(nèi)聚性。與微服務(wù)相關(guān)的最大用戶故事數(shù)指標(biāo)用WsicT表示，比較本文方法與DDD 方法取得的WsicT值，具有較小WsicT值的方法為最優(yōu)方法，值較小說(shuō)明所識(shí)別出的微服務(wù)粒度具有較低的復(fù)雜性。

5 結(jié) 語(yǔ)

本文不同于以往從遺留系統(tǒng)中利用微服務(wù)架構(gòu)這一技術(shù)，對(duì)應(yīng)用程序進(jìn)行重構(gòu)，基于用戶故事這一概念來(lái)設(shè)計(jì)一個(gè)新的微服務(wù)運(yùn)用程序，并結(jié)合遺傳算法中的多目標(biāo)優(yōu)化算法對(duì)微服務(wù)進(jìn)行劃分，在此基礎(chǔ)上將本文所用的多目標(biāo)優(yōu)化遺傳算法與另外三種算法進(jìn)行對(duì)比，為企業(yè)相關(guān)架構(gòu)人員利用微服務(wù)架構(gòu)這一技術(shù)對(duì)系統(tǒng)進(jìn)行設(shè)計(jì)提供了參考。但本文所對(duì)比的案例較少，未來(lái)的工作中將加入新的項(xiàng)目進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)于用戶故事之間的依賴將使用自動(dòng)化工具進(jìn)行依賴分析。