面向多工作流的基于容器的邊緣微服務選擇機制

邵蘇杰 吳 磊 鐘 成 郭少勇 卜憲德

①(北京郵電大學網絡與交換技術國家重點實驗室 北京 100876)

②(國網河北省電力有限公司雄安新區(qū)供電公司 雄安 071600)

③(國網智能電網研究院有限公司 南京 210003)

1 引言

隨著物聯(lián)網的發(fā)展，邊緣設備大規(guī)模普及，其數據逐漸呈現(xiàn)海量異構、處理復雜等特點，對業(yè)務的實時性和可靠性也提出了更高的要求[1]。云平臺與邊緣用戶的遠距離通信產生過大傳輸時延，業(yè)務時響應不及時，難以滿足業(yè)務QoS[2]。邊緣計算作為一種分布式的數據處理和存儲架構被提出，協(xié)同云計算提供就近服務[3]，為處于邊緣的業(yè)務提供更快的響應時間和更低的帶寬成本以及更好的數據隱私性[4,5]。然而，與云服務器相比，邊緣服務器在處理、存儲和通信等方面的資源相對有限，難以在單獨節(jié)點中承載復雜的物聯(lián)網(Internet of Things)應用[6]。

隨著微服務架構的提出[7]，復雜單體應用被分解為更細粒度且松散耦合的微服務集合，每個微服務集中實現(xiàn)一種功能，多個微服務結合成為工作流形式的組合服務，以提供完整的業(yè)務請求。為高效利用邊緣側資源，容器技術作為一種輕量級的虛擬化技術，成為微服務部署的絕佳選擇[8]，它將微服務封裝在容器中并實現(xiàn)資源隔離，可在資源受限和異構的邊緣服務器中部署多個容器實例，為完成業(yè)務的并發(fā)請求提供多種服務選擇方案。前驅微服務的選擇策略將直接影響工作流中后續(xù)所有微服務的完成時間，請求中關鍵微服務的阻塞很有可能導致請求的整體執(zhí)行時間超過預期，降低用戶服務質量。此外，基于邊緣計算的分布式特性，部署在網絡距離較遠的邊緣服務器上容器實例之間的通信，將造成通信時延和網絡資源消耗的增加。因此，相比線性結構的服務選擇而言，邊緣微服務選擇問題需要考慮到微服務之間的依賴關系以及并發(fā)請求對容器實例的競爭關系，如何在邊緣環(huán)境下為基于工作流的并發(fā)請求制定最優(yōu)的服務選擇策略成為難題。

近年來，國內外學者針對邊緣環(huán)境中的服務選擇問題做了研究，文獻[9]提出一種感知延遲的微服務混搭方法，在移動邊緣計算中為應用程序提供微服務的最佳配置，有效保證了時延并顯著降低網絡資源消耗，但只考慮了簡單串行結構，未考慮復雜工作流形式的應用架構。 文獻[10]采取工作流形式描述復合服務，結合實例處理速度和任務并發(fā)度，提出一種基于列表的微服務選擇算法，能有效保障業(yè)務服務質量，但沒有考慮邊緣環(huán)境的特性。文獻[11]提出一種基于最短路徑的性能感知服務路徑選擇方法，綜合了微服務實例的計算能力和微服務實例之間的傳輸條件以及任務特性，提高了整體效率，但無法滿足并發(fā)場景。文獻[12]基于帶約束的多服務選擇的基本模型，將問題轉化為一系列等價線性規(guī)劃子問題，提出一種公平感知的并發(fā)服務選擇算法，通過有限次的線性規(guī)劃迭代，為并發(fā)請求提供目標服務，并獲得更高QoS，但同樣只考慮了簡單結構的服務請求。文獻[13]基于李雅普諾夫優(yōu)化以及馬爾可夫近似提出一種CSS(Composite Service Selection)框架，在移動環(huán)境下優(yōu)化網絡服務的組合，最小化整體組合服務請求的總體響應時間，但沒考慮單個服務實例的請求隊列調度，難以實現(xiàn)全局優(yōu)化。

基于此，本文提出一種基于優(yōu)先級機制和改進蟻群算法的邊緣微服務選擇方案，本文的主要貢獻如下：

(1)根據邊緣計算場景特點，本文結合微服務依賴關系，構建基于容器的邊緣微服務選擇3層架構，并基于此建立了時延模型和網絡資源消耗模型，以求最大化滿足約束時延的請求數量，并減少網絡資源消耗。

(2)考慮并發(fā)請求對容器實例的競爭性，引入優(yōu)先級機制，利用工作流拓撲優(yōu)化任務調度順序，并采用改進蟻群算法的全局優(yōu)化形成最優(yōu)決策。利用真實的工作流對算法進行了評估，與基準方案相比，本文方案能有效滿足并發(fā)請求QoS。

2 系統(tǒng)模型與問題表述

2.1 系統(tǒng)架構

基于容器的微服務選擇架構如圖1所示，該架構被劃分為應用層、容器實例層及邊緣節(jié)點層。

應用層包含一系列開發(fā)人員以微服務架構開發(fā)的邊緣業(yè)務，這些業(yè)務被分解為一組互相依賴的輕量級獨立微服務，并遵循工作流的執(zhí)行邏輯，即后驅微服務必須等待其所有前驅微服務完成并傳遞數據才可開始執(zhí)行[14]。依次執(zhí)行該業(yè)務包含的所有微服務才視為一次請求的完成。

為避免單個節(jié)點宕機無法提供可靠服務，容器實例層抽象底層物理資源創(chuàng)建容器實例承載用戶請求。同一業(yè)務的并發(fā)請求爭用容器實例，容器實例同一時刻只能執(zhí)行一個請求，選擇該實例的其他請求將在該實例上排隊[15]。當現(xiàn)有容器實例隊列過長無法滿足當前并發(fā)請求時延約束時，也可從云中鏡像倉庫下載微服務基礎鏡像，打包所需編譯器、開發(fā)庫和配置文件等組件創(chuàng)建新的容器實例擴展服務能力[16]。

邊緣節(jié)點層旨在為用戶提供分布廣泛、快速高效的計算資源。節(jié)點分布在不同的地理區(qū)域，由各類異構設備組成，如無線接入點、網關或高性能服務器[17]，擁有不同容量的CPU、內存等資源。邊緣節(jié)點內嵌容器管理平臺，如docker和LXC，以管理本地容器實例[18]。

以圖1為例，業(yè)務1包含的6個微服務[A,B,C,D,E,F]分別在不同邊緣節(jié)點創(chuàng)建多個容器，當用戶對業(yè)務1發(fā)起請求，經過決策為該請求包含的6個微服務分別選擇[A2,B1,C3,D2,E1,F1]形成完整執(zhí)行路徑。

2.2 系統(tǒng)模型

2.2.1 應用模型

2.2.2 邊緣節(jié)點模型

邊緣集群定義為一組PM(Physics Machine)組成的物理網絡，網絡中的異構服務器可以抽象為具有不同資源容量的邊緣節(jié)點EN ={EN1,EN2,...,ENN}，E Nn的 資源向量表示為={,,...,}，其中表示E Nn中第r類資源的容量。創(chuàng)建實例需要保證該節(jié)點的可用資源容量超過實例的各類資源需求，定義微服務的資源需求向量為=

2.2.3 時延模型

(1)傳輸時延。對于邊緣環(huán)境中的服務請求，傳輸時延主要考慮用戶上傳數據的時間、選中容器實例之間的數據傳輸時間和返回結果的時間，用戶上傳數據的時延包括端口速率引起的傳輸時延和傳播時延。假設請求上傳的平均數據大小為din，用戶與邊緣節(jié)點的平均帶寬為W，則用戶將輸入數據全部上傳到邊緣節(jié)點上的時延表示為

其中，TP代表用戶設備的傳輸功率，H代表用戶設備與邊緣節(jié)點的信道增益，δ2代表噪聲功率；D代表用戶設備與邊緣節(jié)點的物理距離，t ran(EN,U)代表無線信道的傳播速度。而由于邊緣節(jié)點的下行鏈路帶寬通常遠遠大于上行鏈路帶寬，且業(yè)務結果數據量較小，因此忽略返回結果的時間。

網絡中的每對邊緣節(jié)點彼此之間通過路由聯(lián)通，很明顯部署在不同節(jié)點上且具有依賴關系的容器實例之間數據傳輸時間由數據傳輸量和傳輸速率決定。

定義二元變量xikn

(2)執(zhí)行時延。本文假設微服務處理的數據是其所有前驅微服務傳輸給它的數據之和。一般來說，相同微服務的不同容器實例在異構服務器上的執(zhí)行時間與該服務器的CPU處理速度有關。假設容器實例I(a,i,k)所 在節(jié)點CPU處理速度為，則該實例上任務的執(zhí)行時間定義為

(3)排隊時延。容器實例同時只能執(zhí)行一個請求，容器實例有一個請求隊列來緩存選擇實例的任務，隊列中的這些任務按順序執(zhí)行。因此，在選擇容器實例時，需要考慮實例的請求隊列，如果選擇實例I(a,i,k)，則必須等待隊列中其他任務的執(zhí)行，如果隊列中沒有其他任務，則無需等待，排隊時間=0，否則隊列中所有任務的排隊時間可以迭代計算為

(4)總時延。每個任務都必須等到其所有前驅任務完成后才能執(zhí)行，任務本身就緒時間是其所有前驅任務的完成時間和前驅任務之間的通信時間，計算如下

假設不消耗其他加載時間，則可以在獲得實際開始時間后計算實際完成時間

由于業(yè)務由具有復雜拓撲結構的微服務組成，請求的完成時間不是每個任務的執(zhí)行時間和傳輸時間的簡單累積，而是取決于出口任務的完成時間，即F Tq=FT()。

2.2.4 網絡消耗模型

用Dis(ENn1,ENn2)表示兩個節(jié)點之間的最短跳數，源節(jié)點和目的節(jié)點之間跳數越多，數據將通過更多中間路由傳輸，從而消耗更多的網絡資源。若是的前驅任務，則進行數據傳輸的網絡消耗計算為

此外，創(chuàng)建新容器時從云端下載微服務鏡像也會造成較大的網絡資源消耗，假設選定邊緣節(jié)點與云之間的距離為D is(ENn,cloud) ，為的鏡像數據量大小，則創(chuàng)建新容器實例所消耗的網絡資源為

綜上，完成一個請求所消耗的網絡資源為請求的所有任務之間的數據傳輸和新建容器的網絡消耗之和

其中，c ta,i代 表是否創(chuàng)建新的容器實例。

2.3 問題描述

基于上述系統(tǒng)模型，本文希望找到一種合理的微服務容器實例選擇策略，在考慮任務依賴性和高度并發(fā)的情況下，最大限度地保證用戶QoS，提高在延遲約束下完成的請求數量，并減少網絡資源的消耗。因此，邊緣微服務選擇問題可以定義為目標

約束條件C1和C2表示容器實例是任務分配的最小單元，每個任務只能由一個實例執(zhí)行；C3表示所選邊緣節(jié)點必須有足夠的資源部署微服務實例，如果任一類資源不足，則無法放置容器實例；C4限制了每個任務的開始執(zhí)行時間，任務必須等到其每個前驅任務都執(zhí)行完畢，并將所需數據傳輸給它，才可開始執(zhí)行。

3 本文算法

本文提出了一種基于優(yōu)先級機制和改進蟻群的微服務路徑選擇算法(Microservice Selection algorithm based on Priority mechanism and improved Ant Colony, MS-PAC)。傳統(tǒng)蟻群算法的收斂速度較慢，當搜索空間較大時，需要很大計算時間?？紤]任務的緊迫性和容器實例的競爭性，本文添加任務優(yōu)先級機制優(yōu)化任務調度隊列，再利用蟻群算法的正反饋機制尋找全局最優(yōu)解。

3.1 微服務優(yōu)先級機制

前驅任務的延遲會累計起來影響后續(xù)任務的開始時間，應使任務都盡可能在其子截止時間內完成，然而同一業(yè)務的并發(fā)請求彼此爭用容器實例，無法確保任務始終能分配到最快的容器實例上執(zhí)行。因此，添加并發(fā)系數conf代表并發(fā)程度，優(yōu)化傳統(tǒng)工作流任務截止時間計算公式為

由前文可得任務的最早開始時間取決于其自身就緒時間和所有容器實例的最早可用時間，則任務的最早完成時間(EFT)可以計算為

利用上述任務的截止時間和最早開始時間來定義任務的優(yōu)先級hop()

其中， 指從當前任務到退出任務的路徑上的任務數，其值越大，則表示該任務被延遲后影響的任務越多，其后續(xù)任務的執(zhí)行受各種因素影響的風險也會越高，有必要盡快為當前任務分配容器實例，以減少排隊時間。任務的優(yōu)先級并非一直不變，每有一個任務被分配，則它的后續(xù)任務的最早開始時間必然會根據該任務的分配結果動態(tài)變化，并發(fā)系數也會隨著容器實例數量改變而改變，因此優(yōu)先級會隨著任務分配的過程不斷更新，保證越緊急的任務優(yōu)先級越高。

3.2 容器部署策略

當已部署容器實例的等待隊列太長，導致任務最早完成時間超過任務的截止時間時，需部署新的容器實例來執(zhí)行任務。首先考慮邊緣節(jié)點的資源容量，資源不足的節(jié)點無法部署實例，即需要滿足以下約束

該約束保證了節(jié)點的各類資源滿足創(chuàng)建實例的需求，滿足約束的邊緣節(jié)點將成為候選節(jié)點。網絡資源消耗為選取節(jié)點的主要因素，計算候選節(jié)點與部署了的前驅及后驅容器實例的節(jié)點之間的平均網絡距離

其中，K1表 示的每個前驅微服務的實例數，K2表示的每個后續(xù)微服務的實例數，選擇平均網絡距離最小的候選邊緣節(jié)點作為部署新實例的節(jié)點。

3.3 基于優(yōu)先級機制和改進蟻群的微服務選擇算法

本文提出一種基于改進蟻群算法的微服務選擇算法MS-PAC，以獲得全局最優(yōu)的微服務執(zhí)行路徑策略。除了保留基本蟻群算法的隨機和并行搜索特性之外，為提高搜索過程的收斂性，利用前一節(jié)所述優(yōu)先級機制優(yōu)化任務調度順序。與遺傳算法[19]、粒子群算法[20]等元啟發(fā)式算法相比，改進后的蟻群算法采用信息素策略，實現(xiàn)了不同群體之間的經驗信息共享。

MS-PAC算法模擬螞蟻的進食過程，各個螞蟻通過啟發(fā)式信息和信息素的指導為并發(fā)請求中的任務選擇容器實例，保留它們走過的路徑，并選取螞蟻中的最優(yōu)解以保留經驗，從而在迭代過程中逐漸趨于全局最優(yōu)解。其具體流程如下：

(1)首先必然存在多個沒有前驅任務的起點任務，將這些任務添加進候選列表中，并將螞蟻A ntl隨機放置在候選列表中的一個任務上作為起點。

(2) Antl以 概率選擇公式為當前任務選擇一個映射元組,I(a,i,j)> ，即根據信息素τi,j和啟發(fā)式信息ηi,j，將分配給容器實例I(a,i,j)或為任務創(chuàng)建一個新的容器實例，之后該任務將被放入螞蟻禁忌列表T abul中，不再進行調度。

(3)對某個任務做出調度后，若該任務的后驅任務中存在所有前驅任務都已完成調度的任務，則將該任務將添加到候選列表中。

(4) 更新候選列表中任務的優(yōu)先級，從優(yōu)先級最高的前Top N任務中隨機選擇一個任務作為Antl下一個任務，重復上述過程，直到完成所有任務的容器實例分配。

(5)所有螞蟻均完成全部任務的分配可以視作一次迭代，算法在達到最大迭代次數后終止。

蟻群算法的核心為概率選擇和信息素更新，Antl傾向于選擇期望值更高、信息素更多的容器實例，Antl選 擇p athi,j的概率計算公式表達為

其中，α和β分別是信息素和啟發(fā)信息的影響因子，反映了它們的相對重要性。α越大，信息素對螞蟻的影響越大，蟻群搜索的隨機性越小，β越大，螞蟻陷入局部優(yōu)化的可能性越大。

啟發(fā)式信息ηi,j代表螞蟻將任務分配給容器實例的期望，根據本文目標，提出了兩類啟發(fā)式信息，第1個目標是確保業(yè)務請求盡可能在約束時延內完成。因此，將候選實例上任務的實際完成時間作為衡量容器是否合適的標準之一，定義完成時間的啟發(fā)式信息公式為

第2個目標是減少網絡資源的消耗，定義為代表網絡資源消耗的啟發(fā)式信息

對于信息素的更新，本文提出一種結合局部和全局的信息素更新規(guī)則，局部更新通過蒸發(fā)螞蟻走過的路徑上的信息素，防止螞蟻選擇相同路徑，增加算法的探索能力，防止陷入局部最優(yōu)。全局更新則在所有螞蟻完成微服務選擇方案后，會根據目標函數評估當前所有方案的質量，并選擇其中質量最高的方案增加該路徑上的信息素，這可以促進螞蟻保留全局最優(yōu)解的經驗，在下一次迭代中找到更好的路徑。

在選擇一個新的映射元組,I(a,i,j)>后，螞蟻按如下方式進行局部信息素更新

其中，ρl為局部信息素蒸發(fā)參數，且ρl ∈[0,1]，ρl越大，則路徑上剩余的信息素越少。

信息素初始化為任務數Q，則全局信息素的更新公式為

其中，ρg為 全局信息素更新參數，?τij為一次迭代后信息素的增量，Lbest為 迭代中全局最優(yōu)路徑的目標函數值。

4 仿真實驗與對比分析

4.1 仿真參數設置

文獻[21]提供了4個基準工作流：Montage, LIGO,CyberShake和SIPHT，如圖2所示。每個工作流都由DAX文件描述，代表一類業(yè)務，該文件提供了工作流的詳細信息，包括任務名稱、工作負載、數據傳輸量和任務之間的依賴關系。微服務之間的數據傳輸量定義為10～15 MB，鏡像大小定義為30～50 MB，任務的工作量定義為文獻[22]中標準計算服務的執(zhí)行時間。在本文中業(yè)務的截止時間設置為工作流拓撲的關鍵路徑中任務執(zhí)行時間的ψ倍，以確保可以容忍一定的排隊時間。本文采用批處理請求策略，即假設在一個調度周期中所有請求都將同時啟動，并且所有請求都將被調度，每個調度周期彼此獨立。邊緣節(jié)點的CPU內核從[8, 16, 32]中隨機選擇，內存從[8, 16, 32] GB中隨機選擇，磁盤容量從[100, 200, 300, 400] GB中隨機選擇。邊緣節(jié)點之間的數據傳輸速率服從N(3×103, 102)(kB/s)，微服務CPU需求從[0.1–0.4]選擇，內存需求從0.1～0.4 GB選擇，磁盤需求從0.3～0.6 GB選擇。用戶與邊緣節(jié)點平均帶寬W為20 MHz，用戶傳輸功率TP為20 dBm，噪聲功率δ2為2×10–13W，信道增益H=127+30lgd。算法的迭代次數和螞蟻數量通過多次實驗選取300和30。實驗中的相關參數參照表1，除非另有規(guī)定，否則適用于模擬。

圖2 基準工作流

表1 仿真參數設置

本文使用時延和網絡資源消耗作為指標來衡量本文的方法與其他方法相比的性能。為了驗證本文算法的性能優(yōu)越性，選擇貪婪算法和文獻[10]中的MSS(Microservice Service Selection algorithm)算法進行比較。貪婪算法由延遲和網絡資源消耗兩個方面組成，前者會優(yōu)先考慮隊列時間最少的容器，或者創(chuàng)建一個新的容器；后者只在初始容器上分配任務，從不創(chuàng)建新容器。MSS算法考慮了實例的共享和競爭，根據任務子期限不斷更新任務的緊迫性，調整任務執(zhí)行順序或放棄特定任務的執(zhí)行，并尋求按時完成更多任務。

4.2 實驗結果

(1)對比不同的截止期限。為了驗證不同方法在不同的截止日期內完成請求的能力，本文將ψ的值從1.0變?yōu)?.0，步長為0.5。向每種應用發(fā)起相同次數的請求，總請求數量為80。圖3顯示相較于其他策略，本文所提策略能在不同截止期限內按時完成較多請求。尤其當ψ=3時，4種算法之間存在最明顯的差距。這是因為本文策略通過優(yōu)先級機制優(yōu)先調度緊急任務，減少關鍵任務的阻塞。圖4顯示隨著ψ的增加，所有策略都降低了創(chuàng)建容器的網絡資源消耗，與其他算法相比，本文算法在創(chuàng)建新容器時選取網絡距離較小的邊緣節(jié)點，并且將網絡資源消耗作為改進蟻群的啟發(fā)式信息之一，引導螞蟻向網絡資源消耗更小的微服務選擇結果收斂。

圖3 按時完成請求數量比較(ψ∈[1.0, 5.0])

圖4 總體網絡消耗比較(ψ∈[1.0, 5.0])

(2)對比不同請求數量。為了驗證每個方法在不同并發(fā)度下滿足截止期限約束的能力，本文將請求數量設置為20到100，步長為20。圖5顯示了不同請求數量下MS-PAC算法能有效降低時延。其能有效平衡時延和網絡資源消耗，采用優(yōu)先級機制優(yōu)化任務調度順序，并通過蟻群的自學習和正反饋機制，遏制非關鍵任務無限制創(chuàng)建新容器，從而避免擠占后續(xù)任務創(chuàng)建新容器資源，因此能更合理地實現(xiàn)任務到容器的映射以及節(jié)點資源的管理。

圖5 不同請求數量下平均時延比較

圖6展示了不同請求數量下網絡資源的消耗，可以看出，除網絡資源消耗貪婪算法外，其他3種算法中，MS-PAC在所有情況下均表現(xiàn)最好，通過容器部署策略，盡可能選擇與該容器有最少網絡資源消耗的邊緣節(jié)點新建容器，同時在為任務選擇容器實例時，會將網絡資源消耗作為啟發(fā)式信息，能在保證時延的基礎上，最大限度地降低網絡資源消耗。而時延貪婪算法和MSS算法沒有考慮到選擇實例時的網絡消耗。

圖6 不同請求數量下總體網絡資源消耗

圖7顯示了不同算法在約束期限內完成請求的數量，MS-PAC在所有情況下均表現(xiàn)出良好的性能，尤其是在并發(fā)量高時也能保證較高的按時完成率，這是因為其通過優(yōu)先級機制優(yōu)先安排即將到截止期限的任務，保證這些任務盡快執(zhí)行。MSS算法也會計算任務的緊急度，以安排任務的執(zhí)行順序，但是它會根據任務的子截止日期放棄超時任務。當請求數量為100時，與貪婪時延和MSS算法相比，本文按時完成的請求數量分別提高23.1%和8.9%。

圖7 不同請求數量下按時完成請求數比較

5 結束語

復雜的物聯(lián)網應用在資源有限的邊緣節(jié)點以微服務的形式組合提供服務，針對高并發(fā)情況下難以選擇合適服務實例的問題，本文提出了一種基于微服務優(yōu)先級和改進蟻群的微服務選擇策略，結合工作流機制，提高緊迫任務優(yōu)先級，利用時延和網絡成本指引蟻群收斂。通過在基準工作流上的實驗，本文算法能有效降低時延，在提高按時完成請求率的同時降低網絡成本。未來的研究將從云端協(xié)同、端端協(xié)同的角度探究如何高效執(zhí)行復雜的微服務應用。