基于多目標遺傳算法的微服務粒度識別方法

袁海銘

（昆明理工大學 信息工程與自動化學院，云南 昆明 650500）

0 引 言

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

1 微服務粒度模型的建立

確定微服務粒度模型，可以明確對微服務粒度產生影響的相關指標有哪些，并在這些指標的基礎上得出相應的目標函數。目標函數旨在最小化耦合指標和加權服務接口數指標，最大化內聚性指標。目標函數將在粒度模型提出之后定義，本文將基于微服務架構的應用程序的粒度模型表示為：

式中：MS表示一組微服務集，MS={MS1,MS2,…,MSn}；而MTS是一組為MSGM計算的指標。然后：

式中：MSi是第i個微服務，US是與第i個微服務相關的用戶故事集，可以給出US={US1,US2,…,USn}，MTS是一組計算MSi的指標。在這種情況下，模型中計算和使用的指標對應于耦合性、內聚性以及與微服務相關的用戶故事數量。這些指標的定義如下。

1.1 耦合性指標

將耦合指標定義為Coup={AIS,ADS,SIY}，其中，AIS表示服務的絕對重要性，ADS表示服務的絕對依賴性，SIY表示服務的相互依賴性。這些指標是根據每個微服務的用戶故事的依賴性來計算的。

AISi是至少調用一個微服務操作的客戶數量。在系統層面，定義AIS向量。該向量包含每個微服務計算出的AIS值，因此在計算其系統級上的值時，可以將其定義為：ADSi是第i個微服務所依賴的其他微服務的數量?？梢詫⑵涠x為：

SIY定義了相互依賴的微服務對的數量除以微服務的總數量，其被定義為：

用Coup代表這三種指標的合并，可以將Coup表示為：

1.2 內聚性指標

同理，第i個微服務的內聚性定義為缺乏內聚性度量（LC），每個微服務的內聚度定義為缺乏內聚性度量除以作為應用一部分的微服務總數的比例。

式中：n表示微服務的數量，則Coh可以表示為：

加權服務接口數量（Weighted Service Interface Count，WSIC）這一指標概念源于面向服務架構（Service-Oriented Architecture，SOA）的設計指標，它表示WSDL 文檔（一種簡單的XML 文檔，包含一系列描述某個網絡服務的定義）中定義的每個服務公開接口或操作的加權數，默認權重設置為1。對于本文的模型，用戶故事與操作相關，因此將這個指標調整為與微服務相關的用戶故事的數量。采用WSIC作為分配給每個微服務的用戶故事數。然后將WsicT定義為與微服務相關聯的最大用戶故事數，可以將其表示為：

在內聚性與耦合性指標的基礎上，結合加權服務接口數量，可以將目標函數表達為以下等式：

式（10）可以確定分解的結果是好是壞。一個低的目標函數值是模型想要獲得的，因為模型的目標是獲得一個較低缺乏內聚度量、低耦合以及較小的加權服務接口數量的解決方案，最后通過多目標優化遺傳算法試圖找到指標間最好的組合。

2 基于多目標搜索遺傳算法的微服務識別

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

2.1 初始種群的生成

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

表1 用戶故事與微服務對應表

通過該矩陣圖可以看出，用戶故事2、用戶故事3、用戶故事5 被分配到微服務1 中，而用戶故事1、用戶故事4 被分配到微服務2 中。這樣一來，就可以得到父代的染色體。染色體將是每個用戶故事分配給每個微服務的并集，對于本文的假設，它將是01101 10010。基于這條染色體，定義適應函數或目標函數。該目標函數基于所提出的耦合性指標、內聚性指標以及用戶故事指標的組合。所使用的目標函數如下：

2.2 交叉算子介紹

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

2.3 變異方法

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

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

2.4 參數設置

根據NSGAII 算法的現有工作校準了關于實驗的參數，將種群規模設置為25 個個體，因為根據實驗，這一設置能夠實現有效性和效率之間的平衡。使用0.8 作為交叉概率，0.05×log2(n)作為變異概率。將最大代數配置為200 次，搜索過程重復30 次，以減少遺傳算法隨機性造成的偏差。

2.5 候選微服務的獲取

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

圖1 用戶故事依賴輸入圖

圖2 微服務粒度識別結果圖

3 多目標優化算法性能對比

將NSGAII 算法與另外三種主流多目標優化算法的性能指標進行對比，來比較不同多目標優化算法之間對于識別微服務粒度的效果而言的優劣程度。首先對三種算法加以簡要介紹。

第一種算法是強度帕累托進化算法[6]（Strength Pareto Evolutionary Algorithm 2，SPEA2）。相比于SPEA 算法，SPEA2 采用了改進的適應度分配方式。該方式充分考慮了每個個體中所支配和被支配的個體數量，并且采用了最近鄰密度估計技術。這使其能夠更精確地指導搜索過程，另外還有一種新的存檔截斷方法保證了邊緣解的保留。

第二種算法是基于分解的多目標進化算法（Multi-Objective Evolutionary Algorithm Based on Decomposition，MOEA/D）[7]。該算法將一個多目標優化問題劃分為多個標量優化子問題，并同時對子問題進行優化。每個子問題可僅通過運用其他幾個鄰近子問題的信息進行優化。通過這種方式，降低了計算復雜度，提升了算法的效率。

第三種算法是多目標粒子群算法[8]（Multi-Objective Particle Swarm Optimization，MOPSO），是在粒子群優化算法的基礎上實現的，其靈感來源于鳥群的編排。該算法也可被認為是一種分布式行為算法，它采用群體智能的進化技術，并由于其特殊的搜索機理以及優異的收斂特性而被廣泛應用于多目標優化領域。

3.1 性能指標介紹

GD（Generational Distance） 和IGD（Inverted Generational Distance）是測量帕累托近似解和帕累托真實解之間收斂性（或緊密度）的性能指標[9]。GD 是一種誤差度量，用于檢查通過算法得到的帕累托近似解（PFapprox）與已知帕累托最優解（PFtrue）之間的距離。而IGD 是基于GD 的指標，其目標是評估帕累托最優解（PFtrue）到帕累托近似解（PFapprox）的距離，它的逆由GD 來考慮。

GD 和IGD 的值趨向于零，是本文研究希望得到的，因為這就表明PFapprox和PFtrue的值比較接近。HV（Hyper Volume）測量從參考點到解決方案空間前沿的目標空間面積，該指標可以分析帕累托前沿的緊密度和多樣性。通過將解的前沿歸一化到[0，1]來計算這個指標。具有高HV 值的帕累托前沿是最好的，因為它們的解決方案遠離參考點。4 種算法性能指標的折線圖與條形圖如圖3、圖4、圖5所示。

圖3 基于GD 指標的算法性能對比

圖4 基于IGD指標的算法性能對比

圖5 基于HV 指標的算法性能對比

3.2 性能指標對比分析

為了評估不同的多目標優化算法的優劣程度，對算法的性能指標進行分析。根據上一小節描述可知，本文研究希望獲得較小的GD和IGD值。因為這兩個性能指標越小，說明算法的求解性能就越好。較大的HV值、高HV值同樣說明算法具有較好的求解性能。

從折線圖可以看出，對于GD值來說，基于分解的多目標遺傳算法的性能優勢優于其他三種多目標優化算法；從條形圖可以看出，NSGAII 算法與MOPSO 算法的性能差異不大，差于SPEA2 算法，而MOEA/D 算法的求解性能最好。

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

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

通過比較算法性能指標可得知，對于不同的性能指標，不同算法的性能表現各有差異，但總體來說，SPEA2 和NSGAII 兩種多目標優化算法具有更好的表現。

4 案例研究以及實驗對比

案例研究中，使用微服務架構領域的基于SpringBoot 框架的CargoTracking[10]應用程序。該應用程序是運用領域驅動設計（Domain Driven Design，DDD）進行微服務劃分的經典項目。CargoTracking的重點是通過路由規范在兩個地點之間進行貨物的運輸（由TrackingID 標識）。一旦貨物可用，它就與從現有Voyages 中選擇的一個貨運計劃相關聯，然后，HandlingEvents 跟蹤行程中貨物的進度，完成貨物的追蹤，而貨物交付描述了具體的運輸狀態、預計到達時間，以及該貨物當前是否被跟蹤，且在航線上。基于這一系列的業務邏輯，本文提取并提出了用戶故事，如表2 所示。

表2 用戶故事列表

其中，如何識別用戶故事之間的依賴，是一個比較重要的問題。本文從程序源代碼中分析每個用戶故事之間的調用關系，通過調用關系來識別用戶故事之間的依賴。例如，要創建一個航行（voyage），必須首先獲得位置（Location），這意味著用戶故事1 依賴于用戶故事12。其他類似的用戶故事依賴如表3 所示。

以表3 中的用戶故事依賴作為輸入，使用NSGAII 算法對微服務粒度進行識別，識別后得到的結果如表4 所示。

表3 用戶故事依賴表

表4 用戶故事分布對比表

將基于NSGAII 算法的微服務粒度識別方法與傳統的微服務粒度識別方法DDD（領域驅動建模）的指標進行對比，從而選擇具有更好效果的方法。指標評估如表5 所示。

表5 指標評估表

具體評估過程為：根據用戶故事之間的依賴，計算得到所提出的指標具體值，對微服務粒度的評估通過這些具體值的比較來實現。在耦合性指標中，有4 種不同類型的指標，分別是AisT，AdsT，SiyT以及這三種指標的結合CoupT，比較本文方法與DDD 方法取得的這些參數的值，具有較小AisT值、AdsT值、SiyT值以及CoupT值的方法為最優方法，因為值較小說明所識別出的微服務粒度具有較低的耦合性。在內聚性指標中，使用CohT來進行評估，比較本文方法與DDD 方法取得的CohT值，具有較大CohT值的方法為最優方法，因為值較大說明所識別出的微服務粒度具有較高的內聚性。與微服務相關的最大用戶故事數指標用WsicT表示，比較本文方法與DDD 方法取得的WsicT值，具有較小WsicT值的方法為最優方法，值較小說明所識別出的微服務粒度具有較低的復雜性。

5 結 語

本文不同于以往從遺留系統中利用微服務架構這一技術，對應用程序進行重構，基于用戶故事這一概念來設計一個新的微服務運用程序，并結合遺傳算法中的多目標優化算法對微服務進行劃分，在此基礎上將本文所用的多目標優化遺傳算法與另外三種算法進行對比，為企業相關架構人員利用微服務架構這一技術對系統進行設計提供了參考。但本文所對比的案例較少，未來的工作中將加入新的項目進行對比實驗，對于用戶故事之間的依賴將使用自動化工具進行依賴分析。