功能分發網絡:基于容器的智能邊緣計算平臺*

楊 術,陳子騰,崔來中,明中行,程 路,唐小林,蕭 偉

1(深圳大學 計算機與軟件學院,廣東 深圳 518060)

2(中國移動通信集團浙江有限公司,浙江 杭州 310016)

3(華潤集團-潤聯智慧科技有限公司,廣東 深圳 518060)

4(深圳清華大學研究院,廣東 深圳 518057)

隨著物聯網、機器學習、VR/AR 等應用的發展,網絡數據量正在快速增大.5G 時代的到來,加快了數據產生的速度,網絡的流量也會大幅增加,并會出現更多基于5G 的新型應用.這些應用都將大幅度增加數據規模和網絡流量,對數據實時處理的速度提出了更高的要求[1].

學術界和工業界也提出了很多提高數據處理效率和應對網絡流量的解決方案.Pallis 等人提出了內容分發網絡CDN(content delivery network)[2],將網絡資源存放到分布式的服務器上,而用戶可以根據網絡情況訪問響應速度更快的服務器上.但是CDN 只解決了數據存儲,而不涉及數據計算.邊緣計算(edge computing)[3,4]將服務器部署到距離用戶更小的邊緣端,從而高性能的邊緣服務器能夠以更小的延遲處理用戶的數據請求和流量.但是邊緣計算存在大量分布式的邊緣計算集群,面對用戶不同的計算任務需求,管理者經常需要將不同的計算環境從管理中心遷移到相應的邊緣服務器,這加大了應用的開發和部署難度.

容器化技術是當前學術界和工業界研究的熱點問題之一,它能夠快速直接在操作系統層級向用戶開放多個獨立的用戶態空間實例,并支持攜帶程序包與軟件庫,讓容器直接在機器部署并運行,并在不同計算實體上實現資源的快速遷移,省去了開發人員繁瑣的資源部署和配置步驟.研究人員也提出了一些容器化的邊緣計算平臺,改善了邊緣計算中環境遷移困難的問題.但由于其分布式架構的特點,邊緣計算平臺仍然存在著分布式資源難以統一管理的問題,包括網絡流量和計算資源的管理和調度等.因此,我們需要改進現有的架構,開發一種方便部署、管理和統一調度的邊緣計算平臺.

本文中,我們提出了功能分發網絡FDN(function delivery network),能夠有效管理和調度分布式邊緣服務器的計算資源,并結合無服務化計算(serverless computing)[5],為用戶提供了訪問計算資源的接口.我們將網絡分成了控制器、DNS(domain name server)以及邊緣計算集群.其中:DNS 會解析用戶的地址以及提交的任務等信息;而控制器會收集網絡流量和用戶的信息,計算出一個容器編排策略,將任務對應的容器分配到不同的邊緣計算器,最小化任務的計算延遲;邊緣計算集群會根據編排策略將相應容器部署并運行,并最終將任務計算后的結果返回給用戶.FDN 保持了邊緣計算中網絡延遲小、響應速度快的優點,同時,通過中心化控制器統一管理網絡中的邊緣計算集群和流量信息,實現了分布式資源的收集、管理和調度.另外,通過容器技術并結合無服務化計算,FDN 將計算任務函數化,實現了計算環境的快速遷移.

由于不同的容器編排策略會對系統的計算性能產生影響,因此在FDN 中,我們需要考慮容器編排的效率問題.目前,工業界存在一些容器編排工具,例如Mesos[6],Kubernetes[7],Yarn[8],Borg[9]等,但它們不能取得很好的編排性能.一方面,它們采用的是低效的容器編排策略,例如先來先服務等;另一方面,它們沒有考慮計算任務的數據結構.對于以有向無環圖(directed acyclic graph,簡稱DAG)作為底層的數據結構的復雜計算任務,可能存在著多個子任務,并且子任務間存在著數據依賴和執行順序要求,因此,我們需要考慮不同容器的編排順序.同時,目前的編排器只支持單一數據中心,無法在多集群系統中實現跨集群的容器資源編排.

為了在邊緣計算平臺中取得更好的容器編排效果,本文為FDN 系統設計了一種基于啟發式的跨集群容器編排策略.我們證明了計算最優化容器編排問題是一個NP 難問題,無法在多項式時間內解決.因此,我們開發了基于啟發式的容器編排算法.它綜合考慮了有向無環圖任務中子任務的先后執行順序以及每個子任務的計算量、計算需求等信息,同時考慮了用戶到集群的訪問延遲以及集群本身的網絡流量、閑置資源等信息.算法會根據任務和網絡流量信息生成一個待編排的容器列表,并按照優先級進行排序.算法會不斷訪問待編排容器列表,按順序把容器貪心地編排到完成時間最快同時滿足計算要求的邊緣計算集群,直到把所有容器編排完畢.每當用戶提交計算任務時,FDN 控制器將收集全局的網絡流量和任務信息并執行上述過程,最終將容器編排策略傳送給相關的集群和用戶.相比傳統的簡單容器編排算法,啟發式容器編排策略能夠更合理地實現容器的編排過程,進而優化系統的計算延遲.

我們基于IBM 開發的無服務化計算開源軟件Openwhisk 實現了功能分發網絡技術,并在中國移動網絡中部署了FDN 計算平臺.我們租用6 個阿里云實例作為核心網環境,其中3 個實例作為Master 節點,另外3 個作為Worker 節點.同時,部署了兩個邊緣計算中心,每個中心由1 臺機架式服務器和6 臺配置不同的臺式機模擬.我們在網絡中部署了客戶端,并進行真實的人臉識別的任務測試.實驗結果表明,FDN 計算平臺能夠取得137.82ms 的平均計算延遲.同時,我們在不同條件下模擬了基于啟發式的容器編排策略,并與傳統的編排算法作性能對比.實驗結果表明了,我們的編排策略能夠自適應于不同的網絡環境.與傳統的編排算法相比,啟發式的容器編排策略能夠取得更好的計算性能,提高了FDN 的計算效率.

本文的貢獻列舉如下:

? 提出了功能分發網絡FDN,它為用戶提供了統一的接口,使得用戶能夠上傳自己的計算任務,并且系統會將該任務分配給最合適的邊緣計算集群,讓用戶享受到低延遲高性能的計算服務;

? 提出了一種基于啟發式的容器編排策略,實現容器的跨集群編排,優化用戶任務的計算延遲;

? 實現并部署了FDN 系統并評估了其性能,實驗結果表明:我們提出的FDN 架構和容器編排算法能夠取得很好的計算延遲,能夠滿足當前網絡中的數據計算需求.

本文第1 節將會介紹當前的計算平臺和容器編排工具的相關工作.第2 節和第3 節將會展示提出的FDN平臺和容器編排模型.FDN 系統的實現細節、部署和測試會在第4 節進行介紹.容器編排算法模擬的實驗過程和結果將會分別在第5 節進行展示.最后,結論會在第6 節中給出.

1 相關工作

1.1 流量優化與計算平臺

當前,網絡數據量呈指數級的增長速度.如何更高效快速處理這些龐大數據和流量,成為網絡領域的最大挑戰之一.學術界和工業界提出了很多流量優化和計算平臺的改進方案.CDN[2]是一種分布式的存儲機制,它將數據內容分發到分布式服務器上,而用戶能夠在靠近的服務器上直接獲取數據內容,避免訪問距離更遠的中心服務器.但是CDN 只針對數據存儲,無法提供數據的計算等功能.云計算[10,11]通過搭建高性能的計算中心,使得用戶能夠把計算任務和數據上傳到云計算平臺,并由高性能的機器進行計算.同時,用戶能夠按需購買指定數量和性能的機器和計算服務,為用戶節省了購買服務器的費用.但是文獻[12]指出:當前的云計算平臺是中心化的,數據中心部署在距離用戶較遠的地方,這會導致用戶到中心服務器的延遲較大,無法滿足當前實時性的要求.同時,在使用云計算平臺過程中,開發人員需要花費大量時間進行服務器的環境搭建及數據和計算資源的部署等,加大了開發人員的開發難度.

1.2 邊緣計算

為了解決中心化平臺延遲大的問題,研究人員提出了邊緣計算[3,4].邊緣計算采用了分布式的網絡拓撲結構,多個邊緣服務器集群被放置在距離用戶更近的邊緣端,而用戶能夠把計算任務和數據提交給相對距離更近的邊緣計算集群并由其進行計算.相比云計算,分布式的邊緣計算平臺降低了用戶到計算資源的距離和延遲,從而提高了數據流量的處理和計算速度.邊緣計算現已成為業界研究的熱點之一,并應用到不同的領域中,例如物聯網[13]、5G[14]等.

但是邊緣計算是基于分布式的網絡結構,如何管理、調度和優化分布式的邊緣計算資源,成為了最大的挑戰之一.Teixeira 等人[15]指出:由于缺少統一的管理和調度中心,分布式的邊緣計算平臺無法獲得網絡流量和計算資源的實時情況,因此無法得到最優的資源管理和調度方案,也無法達到更好的計算性能.因此,我們為分布式的邊緣計算平臺提供一個中心化的結構,負責管理和調度邊緣計算平臺的流量和分布式計算資源,提高邊緣計算平臺的性能表現.

1.3 無服務化計算與容器編排模型

無服務化計算(serverless computing)[5]是一種新的計算平臺,為用戶提供了函數化的計算服務.用戶只需要調用統一接口,就能夠進行函數化計算,無需額外管理和調度運行時需要的資源,使得用戶可以更好的關注自己的業務邏輯.利用容器化技術,用戶提交的函數將被快速部署到容器,并運行在對應的計算實體上,這免去了復雜的計算資源部署、配置和調度過程.同時,容器能夠在不同的計算實體進行快速遷移,這提高了計算平臺的可擴展性,提高用戶的開發效率.

在容器技術使用過程中,我們需要把容器部署和運行在恰當的服務器上,這也是容器編排的概念.工業界提出了許多容器編排器,包括Mesos[6],Kubernetes[7],Yarn[8],Borg[9]等.但是目前的容器編排器采用的仍是一些簡單的編排策略,例如,Kubernetes 和Borg 只提供了簡單的先來先服務(FCFS)和基于優先級順序的容器編排策略,而Mesos,Yarn 等編排工具只支持先來先服務的編排策略.它們沒有考慮到任務和容器本身先后執行順序等信息,并且現有的容器編排器都是基于單個數據中心的,無法進行跨集群的容器編排.對于分布式邊緣計算網絡,現有的容器編排策略無法在多集群平臺中使用.因此在本文中,為了適應FDN 網絡中多個邊緣計算集群的分布式結構,我們設計一種跨集群的容器編排器,提供一種基于有向無環圖結構的容器編排策略,優化用戶到邊緣集群的計算延遲.

2 FDN 技術架構

2.1 FDN系統概況

我們設計了一種新的邊緣計算平臺,功能分發網絡FDN,系統結構如圖1 所示.它是一種分布式的邊緣計算平臺,能夠為用戶提供基于函數的計算服務.在FDN 平臺中,用戶只需要通過FDN 提供的統一接口,上傳計算任務數據等相關信息,就能夠訪問FDN 中邊緣計算的資源.此時,復雜的計算任務就會被上傳到系統,并且控制器將根據任務和網絡流量等信息,把相關容器編排和部署到合適的邊緣計算集群,最終將計算結果返回給用戶.

Fig.1 Overview of FDN system圖1 FDN 系統概況

在FDN 中,我們主要有以下角色.

? 用戶:向FDN 系統上傳相應的計算任務和數據,訪問邊緣計算資源,并且支付對應的費用;

? 邊緣計算集群:負責計算用戶提交的復雜的計算任務,并且將計算結果返回給用戶;

? 控制器:負責收集用戶和分布式邊緣集群的信息(例如網絡流量、閑置資源等),并且通過算法得出一個容器編排和調度策略;

? DNS:負責為用戶提供統一的接口,讓用戶能夠訪問邊緣計算資源.它根據用戶的請求解析出用戶所在的位置,同時接收控制器的容器編排和調度策略,將用戶與對應的邊緣計算集群進行綁定.

FDN 的運行過程如圖2 所示,主要分為以下步驟進行.

(1) 用戶會通過FDN 提供的統一接口,向DNS 發出請求,并提交相應的任務和網絡等信息;

(2) DNS 會解析用戶的地址信息,并將其發送給控制器;控制器同時也會采集邊緣計算集群的狀態信息,包括網絡狀況、計算資源被占用率和閑置情況等;

(3) 控制器根據收集到的信息計算得到一個合理的調度和容器編排策略,并將其回傳給DNS,并將容器部署到對應的邊緣計算集群.由于不同容器編排策略將直接影響系統的計算效率,因此我們將在第3 節研究FDN 的容器編排問題;

(4) DNS 將根據編排策略,將用戶與對應的邊緣計算集群進行綁定;

(5) DNS 將目標邊緣計算集群的網絡信息傳給用戶,使用戶能夠連接到目標集群;

(6) 用戶將原始數據發送給邊緣計算集群,最后,邊緣計算集群將會進行計算并把計算結果返回給用戶.

Fig.2 Flow chart of FDN system圖2 FDN 運行流程圖

在設計上,FDN 結合了無服務化計算及邊緣計算的特點.通過系統提供的統一接口,用戶可以訪問到無服務化計算的計算資源.在實際運行過程中,我們采用URL 鏈接的形式作為接口,用戶只需要輸入URL 地址,就能夠訪問FDN 資源.當用戶通過接口上傳自己的任務和位置信息后,利用容器化技術,計算任務所對應的容器將會被部署并運行在邊緣計算集群,而用戶只需提交自己的任務信息和原始數據,就能夠獲得無服務化計算的計算服務.

我們在FDN 系統中會維護一個代碼庫(code repository),其中包含一些基本的容器鏡像,例如人臉識別、大數據分析、目標檢測等,保證了用戶常用的計算需求都能得到滿足.用戶能夠方便高效地調用并使用無服務化計算資源,不需要再進行繁瑣的環境和計算資源部署過程;同時,我們改善了邊緣計算的分布式架構.我們引入了控制器和DNS 等中心化組件,負責管理和優化邊緣計算集群和用戶的資源和網絡流量信息.控制器也能夠根據網絡狀況計算合理的容器編排策略,保證了FDN 平臺合理正常運行,克服了傳統邊緣計算平臺難以管理的缺點.FDN 既擁有方便使用、管理和調度的優點,又能夠保證更好的計算延遲,滿足了許多應用實時性和計算速度的需求.

2.2 FDN控制器

控制器是FDN 中心化的調度組件,負責整個系統的正常運轉.它負責流量優化和容器的編排,讓計算任務調度到更合適的邊緣計算集群.同時,控制器還負責用戶接入、代碼庫的維護、網關等功能,保持系統穩定高效運行.FDN 控制器包含了以下幾個組件.

1) FDN-Web:負責存儲用戶的個人信息、項目信息以及功能函數的創建等功能;

2) FDN 分發器:負責計算并實現容器的跨集群編排,優化每個計算任務的計算延遲.編排算法會在第3 節展示;

3) FDN 費用中心:負責記錄用戶使用平臺所需要支付的費用;

4) FDN 網關:負責收集網絡的流量信息以及函數的分發與路由、集群內的負載均衡等功能.同時,FDN網關還承擔著流量控制、安全策略管理、用戶授權等功能,保證FDN 系統安全可靠的運行;

5) FDN 代碼庫管理:負責管理和維護代碼庫的穩定和更新,并且判定用戶上傳的容器鏡像是否合法以及有效.

為了更好地管理分布式邊緣集群,我們還設計了分層的控制器管理結構.在每個邊緣計算集群內部有一個控制器,分別管理自己所在的集群.而全網還有一個中心控制器,作為全網的指揮,收集來自各個集群控制器的信息,以實現對全網信息的統一管理和調度.這種分層結構能夠同時在中心和邊緣端更便捷高效地管理各類計算資源和網絡流量,保證FDN 平臺的可靠運行.

2.3 邊緣計算集群

為了讓不同地理位置的用戶享受更低的計算延遲,多個邊緣計算集群分布在網絡的不同地點,并由控制器進行管理.我們為每個邊緣服務器安裝了容器的運行環境.當用戶提交計算任務時,目標邊緣計算集群會根據控制器的容器編排策略,從代碼庫中下載、安裝并運行任務所需要的容器.同時,它會接收DNS 的映射指令并與對應的用戶綁定,與用戶進行直接的數據通信,并最終將計算結果返回給用戶.

2.4 DNS

DNS 為用戶提供了統一的接口,用戶在使用時,只需要輸入一個URL 地址,就可以訪問計算資源.DNS 會解析用戶的地址,并且將地址和任務信息傳送給中心控制器.同時,在容器編排時,DNS 將與控制器協同工作.當控制器計算出容器編排策略后,DNS 會根據調度策略將目標邊緣計算集群與用戶進行綁定,通過發送映射命令,讓它們進行數據通信.我們指出DNS 在FDN 系統中起到了橋梁的作用,連接了用戶與中心控制器,為控制器提供準確的用戶位置和任務信息.DNS 將解析用戶信息與計算調度策略功能進行解耦,為系統的可擴展性提供了有力支撐;同時也能夠減輕中心控制器的壓力,保證平臺的可靠運行.在實際運行中,為了讓用戶以更小的延遲訪問FDN 資源,我們采用了Smart DNS 技術,優化地址訪問和解析策略,以適應FDN 在不同用戶規模下的實際使用效果.FDN 中采用的Smart DNS 具體分為兩個部分:1) 控制器根據容器編排算法,計算出最優的用戶流量調度策略,然后將用戶的IP 地址與邊緣服務器對應,更新DNS 服務器;2) DNS 本身不需要做任何修改,但它直接與控制器聯動,共同組成FDN 的Smart DNS 功能.

通過以上各個組件的協同工作,用戶能夠享受到便捷的計算服務,同時保證了用戶的計算延遲.但是我們指出,對于容器化技術,目前的容器編排器采用的是一些較為簡單的編排策略(例如先來先服務、優先級等).這種編排策略沒有考慮到容器和網絡流量等重要信息,會加大任務的計算延遲;同時,對于分布式的網絡架構,現有的編排器無法支持跨集群的資源調度,不能很好地支持邊緣計算的系統架構.相比傳統的單集群內部調度,跨集群容器編排需要進行容器的遷移,需要考慮集群間的傳播延遲;而單集群調度不需要考慮延遲,因為集群內部的傳播延遲約等于0.我們指出:傳統的容器編排方案(例如,使用docker 和kubernetes 分別作為容器引擎和編排器)只支持單集群的容器編排,無法擴展到多集群容器編排.因此,本文為FDN 設計了一種支持跨集群的容器編排策略,支持在多個邊緣計算集群間進行容器調度,發揮FDN 控制器統一管理的優勢,進一步優化容器化計算平臺的延遲.

3 容器編排

3.1 問題定義

定義的記號見表1.

Table 1 Notation list表1 記號表

在FDN 系統中,定義P={p1,p2,…,pn}為系統中的n個邊緣計算集群集合,其中,pi∈L(1≤i≤n)表示第i個邊緣計算集群.當一個用戶u申請FDN 服務時,它會向中心控制器提供該計算任務J運行時所需要的容器鏡像信息.對于一個計算任務J,它可能存在著多個子任務,而且這些子任務之間存在著一定的依賴關系,執行時需要遵循一定的先后順序.任務J可抽象成一個有向無環圖J=(V,E),其中,V={v1,v2,…,v|V|}表示子任務集合,而E= {e1,e2,…,e|E|}表示子任務間的數據依賴關系.對于節點va到節點vb,假設它們之間存在有向邊(ea,eb)從節點va指向節點vb,表示只有先執行節點va才能執行節點vb.對于一個節點v,我們將它的父節點集合和子節點集合分別定義為prev(v)和succ(v);同時,我們假設對于每一個任務J,它都會存在唯一的入口任務(entry job,也稱為ventry),而出口任務(exit job,也稱為vexit)可能有多個.也就是說:入口任務的ventry入度為0,而出口任務vexit的出度大于等于0.當任務在被調度和編排的時候,系統都會從ventry開始執行,并且最終某一個vexit結束計算.我們令執行入口任務的容器稱為centry,令執行出口程序的容器稱為cexit.

對于任務J,我們假設它運行時可分配的容器集合為C={c1,c2,…,cm},其中,ci∈C代表每一個獨立的容器.我們假設每一個子任務j都由一個獨立的容器c進行計算,因此一個任務J的執行需要由多個容器間的協同工作來完成.由于子任務之間存在著一定的數據依賴,因此容器的編排順序也受到了要求;同時,容器間也存在著數據通信.當容器ci和cj被編排到兩個不同的邊緣計算集群時,定義通信代價為ω(ci,cj),其中,ω(ci,cj)為正整數.而如果容器ci和cj被編排到相同的邊緣計算集群,那么通信代價為0,即ω(ci,cj)=0.由于中心云到邊緣云的延遲比較穩定,而且容器在邊緣會有緩存時間,所以用戶后續上傳的數據都可以享受低延遲的服務.在本文中,我們主要考慮用戶的流量調度,暫不考慮中心云下發容器的過程延時.在以后的研究中,我們將會進一步研究容器從中心云下放到邊緣云的延遲這一重要因素.

對于每一個容器c,當它被編排到某一個邊緣計算集群時,需要集群內的機器花一定時間進行計算.我們假設容器c的計算量為δ(c),其中,δ(c)為正整數,并且假設邊緣計算集群p當前的閑置算力為θ(p),θ(p)也為正整數.那么容器c在系統中的平均完成時間可以表示為

每一個容器都會有對于計算設備的需求,我們把容器c的需求(包括內存、存儲等)定義為r(c),其中,r(c)的值為正整數;同時,對于集群p∈P,它都會有當前閑置的資源量,我們將其定義為I(p),并且I(p)為正整數.如果容器c要在集群p上順利運行,那么c的計算需求必須小于等于p的閑置資源,即r(c)≤I(p).

在容器計算的過程中,用戶需要實時把數據傳送給對應的容器進行計算.定義d(u,c,p)為用戶u到容器c所在的邊緣計算集群p的延遲.為了簡單起見,令每d(u,c,p)在0 到1 之間變化,也就是0≤d(u,c,p)≤1.我們令pentry和pexit分別表示入口容器和出口容器所在的集群,那么用戶u到pentry和pexit的延遲我們也簡單表示為dentry和dexit.

另外,為了表示某個容器是否被編排到某個邊緣集群,我們令f(c,p)表示為

對于用戶u提交的任務,當容器被編排到對應的集群時,任務的計算延遲包括3 部分:一部分是在服務器上的計算消耗時間,一部分是容器間的通信時間,另一部分是用戶傳送數據給容器所在的邊緣服務器的延遲.我們定義容器c的實際開始執行時間(actual start time)為AST(c)和實際完成執行時間(actual finish time)為AFT(c).類似地,我們定義將容器c在集群p上最早的開始執行時間(earliest start time)為EST(c,p),并且:

其中,avail[p]表示為集群p準備好執行容器c的時間,而公式后面的max 函數指的是集群p等待執行完容器c的父容器的最大時間.特別地,對于入口容器centry,它的最早開始執行時間為用戶到入口容器所在的集群延遲,即EST(centry,pentry)=dentry.我們同時定義容器c在集群p上的最早完成執行時間(earliest finish time)為EFT(c,p),其中,該值的大小包括容器c的執行時間加上最早執行時間,即:

我們指出,EST(c,p)和EFT(c,p)的值可以通過迭代的方式計算得到.同時,當容器已經確認被編排到某個計算集群上時,它在集群上的最早執行時間就等于實際開始執行時間;同時,它在集群上的最晚完成時間就等于實際完成實行時間.在本文中,我們的目標是讓所有任務的計算延遲最小(其中包括各個容器在集群上的計算時間、容器間的數據通信時間以及用戶到容器的延遲).因此,算法的目標是讓某個任務的最后一個出口容器的計算延遲最小,同時滿足設備的閑置資源和容器的資源需求,我們將其形式化為

3.2 編排算法

我們指出,存在最優算法得到計算延遲最小的容器編排策略.最優算法的主要思路是:遍歷所有滿足限制要求的容器編排策略,并最終選出一個計算延遲最小的編排方案.我們指出:只要等待足夠長的時間,最優算法始終能計算出最優的容器編排方案,任務的計算延遲也必然是最小的.但是,最優算法不能夠在線性時間內解決,這對于一個實際應用的系統顯然是不合適的.接下來,我們會證明使用最優算法來得到最優的容器編排策略是一個NP 難的問題.

定理1.找到一個最優的容器編排策略是一個NP 難問題.

證明:在線性時間內,驗證一個給定的容器編排策略是可行的.因此,找到一個最優的容器編排策略屬于NP問題的范疇.為了證明該問題是一個NP 難問題,我們將最大子集和問題歸約為最優容器編排問題.其中,最大子集和問題已經被證明為NP 完全問題[16].最大子集和問題是:給定一個有限集合Q,對于每一個q∈Q,都有一個特 定的值v(q)∈Z+、一個正整數B∈Z+,找到一個子集Q′?Q,讓并且最小化.

假設現在有兩個邊緣計算集群pA和pB,并假設用戶u到它們的延遲分別為d(u,pA)和d(u,pB),其中,d(u,pA)的值很小,而d(u,pB)的值很大.同時假設pA和pB的可分配算力為θ(pA)和θ(pB),并假設θ(pA)的值很大,而θ(pB)的值很小.并且假設任務在pA預計完成的時間很短,而pB預計完成的時間很長.因此,對于待編排容器列表C={c1,c2,…,cm}來說,如果有更多的容器被編排到pA,那么系統就能取得更好的計算時間性能.

令Q代表待編排的容器,并且每一個容器c都會請求pA的服務,同時,r(c)|c∈C等同于v(q)|q∈Q.由于d(u,pA)與d(u,pB)以及θ(pA)與θ(pB)之間的值相差很大,因此pA是唯一可選的邊緣計算平臺,并且令它的閑置資源I(pA)=B.我們接下來證明,找到最優的容器編排策略等同于找到最大子集和問題的解決辦法.最優的容器編排策 略是:找到一個容器的子集和,并且是最大的.因此,找到最優的容器編排策略與解決最大子集和問題是等價的.

參考了文獻[17]的做法,我們首先計算每個容器的優先級,并且用貪心的方式將每個容器編排到當前響應最快、同時滿足資源需求的集群上.我們根據子任務信息計算出每個子任務對應的容器的score值(也稱為優先級,它綜合考慮了容器的數據依賴以及容器的執行時間等),并且按照score值的遞減順序形成一個容器列表.其中,score值的計算方式如下:

平均計算時長越低,同時與其他節點通信代價越低的節點,它所在容器的score值就越高,并且score值越大,說明它應該先被執行.在容器編排的過程中,算法會依次根據容器列表依次調度每一個容器,并根據計算時間編排到響應最快的邊緣計算集群.如果存在某個邊緣計算集群的閑置資源無法滿足容器的需要,那么算法會考慮響應時間第二快的計算集群,判斷它是否能容納和運行當前的容器.以此類推,直到找到滿足計算要求的邊緣集群為止.

基于啟發式的容器編排算法具體細節見算法1.

算法1.Heu-Orche(J,P,C).

第1 行、第2 行是容器優先級計算過程.首先,在第1 行,算法會先獲取每個容器運行的計算量、資源需求等,以及在每個集群的預計開始執行時間和完成執行時間等.接著,在第2 行,算法會根據信息計算每個容器的score值,并按照score值的遞減順序依次對容器進行排序,并形成列表C={c1,c2,…,cm},而接下來算法也會按照該列表對它們進行調度.

接著是集群選擇階段.從第3 行~第10 行,算法不斷選出列表中未被編排的容器計算出合適的編排策略,計算方式則是采用貪心的方式,直到待編排容器列表為空.在第4 行,算法每次都會選出列表中第1 個未被編排的容器c進行操作,并且會收集c的計算量和需求信息.從第5 行~第8 行,算法遍歷所有可用的邊緣計算集群,收集所有集群的資源使用信息、集群間的傳輸代價以及用戶與集群的延遲信息.第6 行、第7 行,對于每個集群p,算法首先會判斷該集群當前是否滿足容器的需求,也就是判斷r(c)是否小于等于I(p):如果滿足,算法會繼續計算容器c編排到該集群的預計完成執行時間EFT(c,p);如果不滿足,則直接跳到下一個集群進行判斷.在遍歷完所有的集群后,算法會選擇預計完成時間最小、并且滿足容器計算需求的那個邊緣計算集群,并把容器編排給它,并更新網絡的信息.最后,所有容器就會被貪心地編排到合適地邊緣計算集群,并在第11 行更新網絡的信息.

定理2.算法1 的時間復雜度為O(n|E|).

證明:在第2 行,算法需要考慮子任務間的數據依賴以及每個子任務在邊緣計算集群的平均計算時間,因此,第2 行的時間復雜度為O(n|E|).而從第3 行~第10 行為循環遍歷過程,其時間復雜度為O(mn).因此,算法1 的時間復雜度為O(n|E|).

基于貪心策略的啟發式容器編排算法能夠充分考慮容器間的數據依賴關系以及每個容器的計算延遲和計算需求,為任務運行提供合理的容器編排順序,是一種簡單易用并且高效的編排算法,并且將控制器的計算負載維持在一個較低的水平,以適應大規模的用戶數量.算法的時間復雜度為O(n|E|),即使在稠密圖的情況下,算法的時間復雜度為O(nm2).因此,隨著用戶數量和邊緣服務器數量的增長,算法的執行時間也呈多項式時間增長的速度,具有較強的擴展性,能夠很好地保證大規模用戶下容器的編排效率和算法執行時間.

算法將運行在FDN 控制器中.每當有用戶提交任務請求時,FDN 控制器會先收集任務、集群和網絡等重要信息,再執行容器優先級計算過程和集群選擇階段.它會將容器編排策略放進分發器,并按規則編排到目標邊緣計算集群.DNS 也會根據編排策略,將用戶與集群進行映射綁定.經過以上過程,用戶提交的計算任務能夠更合理地部署到邊緣計算集群進行計算,優化任務的計算延遲,提高系統的計算效率.

4 FDN 系統實現、部署與測試

4.1 FDN實現細節

我們實現了FDN 系統,包括了FDN 控制器和各個邊緣計算集群,系統架構如圖3 所示.對于FDN 控制器,我們實現了客戶管理后臺(FDN-WEB)、FDN 分發器、中心網關和費用中心等功能,每部分的功能也如第2 節描述.其中,我們使用了RabbitMQ 作為消息隊列代理軟件,用于處理網絡中用戶發出的計算請求;同時,用戶和容器等信息也都存放在數據庫中,以進行費用和其他用戶信息的統一管理.當消息隊列不為空時,FDN 分發器就會依次處理隊列中的消息,并找到代碼庫中對應的代碼、容器等信息,進而將容器分發到對應的邊緣計算集群上.對于FDN 網關,我們也使用了Nginx 作為服務器代理軟件,用于進行負載均衡、安全管理和流量監控等網絡狀態管理.另外,我們在FDN 系統中也部署了一系列高性能的邊緣計算集群(我們以3 個為例,如圖3 所示).對于系統中的邊緣計算集群,我們安裝了K8S 和Openwhisk 并進行了一定的改進,作為底層的容器編排工具,實現系統的容器化管理和基于函數的計算功能.每個邊緣計算集群內部也會實現邊緣網關,功能與控制器網關類似,用于維護邊緣集群內部的正常運轉.我們也使用并改進了Prometheus 軟件,將其作為分布式集群的管理工具,讓多個邊緣計算集群間協同工作.

Fig.3 Implementation of FDN system圖3 FDN 系統實現

4.2 部署設定

我們在中國移動網絡中部署了FDN 系統,如圖4 所示.

Fig.4 Deployment of FDN system圖4 FDN 系統部署

我們將FDN 控制器以及功能平臺部署在杭州,同時在邊緣端分別部署了兩個性能相同的邊緣計算集群,分別放置于北京和深圳.在功能中心中,我們準備了不同的常見容器鏡像,例如圖像增強、視頻編解碼、VR 應用等常見計算任務,為邊緣節點提供軟件支持.

在本實驗中將以人臉識別作為功能測試,評估FDN 的計算延遲性能.具體來說,我們在深圳部署了用戶(客戶端),通過DNS 提供的統一接口,每隔10s 向FDN 平臺提交計算量相同的人臉識別任務.同時,為了保證測試結果的準確性,我們令客戶端請求過程持續大約10 分鐘,測試任務總數為60 個,并統計任務的計算延遲.為了簡單起見,兩個邊緣計算集群的初始狀態都是一樣的,包括閑置資源、網絡流量以及各類硬件設備等.我們定義一個任務的計算延遲為該任務從上傳到邊緣服務器返回結果所需要的時間.我們將分別測試并比較兩個邊緣計算集群的計算延遲,以判斷不同邊緣計算集群對于任務計算延遲的影響.同時,我們將展示FDN 控制器的資源使用情況,并用CPU 利用率作為評估指標,以評估控制器計算編排策略時的計算負載情況.

4.3 測試結果

兩個邊緣計算集群的計算延遲如圖5 所示,其中,橫軸是任務的索引,縱軸是任務的計算延遲,單位是ms.從圖中可以看到,位于深圳的邊緣計算集群的計算延遲明顯小于北京的計算集群.其中:深圳計算集群的平均計算延遲為137.82ms;而北京計算集群的平均延遲為392.16ms,超過了深圳計算集群平均延遲65.1%.這是因為位于深圳的邊緣計算集群距離用戶更近,因此任務的計算延遲更小,而這些任務也被編排到深圳的邊緣計算集群進行計算.這說明我們的FDN 系統能夠根據延遲等計算資源信息,將任務調度到更合適的集群,最小化任務的計算延遲.同時,對于用戶來說,FDN 系統能大大提高復雜任務的計算速度,滿足了許多應用實時性的需求.FDN 控制器的CPU 資源利用率如圖6 所示,其中,橫軸代表任務的索引,縱軸代表CPU 的資源利用率并且均為百分數.

Fig.5 Latency performance of edge clusters圖5 邊緣計算集群的計算延遲

Fig.6 Utilization of FDN controller圖6 控制器的CPU 利用率

我們可以看到:位于杭州的FDN 控制器的CPU 資源利用率一直維持在穩定水平,其平均值為8.87%.這說明我們的FDN 控制器能夠高效快速地對網絡的信息進行收集,以及對任務所對應的容器編排策略進行快速的計算,同時保持較多的閑置資源,確保了FDN 計算平臺的穩定安全運行.

5 容器編排模擬實驗

5.1 實驗設定

我們實現并模擬了基于有向無環圖結構的啟發式容器編排算法(Heu-Orche),并評估了它在不同任務規模、用戶數量、網絡拓撲和設備算力下的計算延遲性能.我們首先生成了不同規模的有向無環圖計算任務,每個計算任務中包含了不同數量的子任務,且每個子任務均封裝為一個容器并編排到機器進行計算.我們隨機模擬了每個子任務的計算規模和計算量,以及子任務之間的數據依賴和通信時長等必要信息.我們為每個計算任務模擬了100~1000 個子任務,將容器編排到對應的計算集群,評估算法對不同任務規模的編排效果.

同時,為了評估不同的邊緣計算網絡環境,我們會改變網絡的拓撲和規模,包括邊緣計算集群的個數和集群的計算能力.在實驗中,分布式邊緣計算集群的數量會從1 變化到5,并隨機分布在網絡的不同位置.這些分布式邊緣計算集群會根據控制器計算得到的容器編排策略,將容器部署到對應的機器,并根據容器的數據依賴關系開始并行計算,并最終將計算結果返回給用戶.我們還會評估用戶數對算法執行效率的影響,將用戶數從1 000個變化到10 000 個.默認情況下,子任務的數量為100 個,邊緣計算集群的個數為3 個,用戶數量為1 000 個.

為了與其他編排算法進行對比,我們實現了在傳統容器編排器中廣泛采用的先來先服務算法(FCFS)和基于優先級(priority first)的編排算法[6-9].對于先來先服務算法,容器會根據先后順序部署并運行在機器;而對于優先級編排算法,我們會根據子任務的規模順序為容器進行優先級設定,并且讓優先級更高的容器優先進行編排.另外,對于邊緣計算的應用場景,我們開發了基于距離優先(distance first)的貪心編排策略,其中每個容器會被貪心地編排到距離最近的邊緣計算集群.這種距離優先的調度策略廣泛應用在邊緣計算中[18],因此我們對其作了一定改進,設計了基于距離優先的容器編排策略.另外,我們還引入了最長剩余時間優先(longest remaining time first,簡稱LRTF)算法.這是一種幾年來廣泛應用在容器編排的調度策略,容器會根據最長剩余時間進行搶占調度,以提高系統任務的計算延遲[19].我們將在同樣的實驗設定下,評估并比較這幾種編排算法的計算延遲性能.在實驗過程中,為了模擬更加真實的網絡環境,我們為網絡加入了5ms 的網絡抖動[20],并測試在該延遲抖動設定下的算法性能.

5.2 實驗結果

1) 不同子任務與用戶數量

我們首先測試了5 個算法在不同數量的子任務(100~1 000)下和不同用戶數量下(從1 000 個~10 000 個用戶)的編排性能,實驗結果如圖7 和圖8 所示.

Fig.7 Computation latency with different workflows圖7 不同子任務數量下的任務計算延遲

Fig.8 Computation latency with different users圖8 不同用戶數量下的任務計算延遲

在圖7 中,總體上,隨著子任務數量的增加,5 個算法隨著子任務數量的增加,任務的計算延遲都呈現上升趨勢.我們可以看到:傳統的FCFS、優先級編排算法和LRTF 算法之間的性能差異不是很大,并且保持著相似的增長趨勢.距離優先算法和LRTF 算法在子任務數量較小時能夠取得不錯的效果,但當任務規模增加后,它們的性能缺陷顯現出來了,其中,距離優先算法的性能甚至不如FCFS 等傳統的算法.我們提出的Heu-Orche 的性能總體上優于其他4 種算法,并且隨著子任務數量的增加,它的性能優勢就更大.例如:當子任務為100 個時,Heu- Orche 的性能分別勝過FCFS、優先級算法和LRTF 算法53.1%、35.7%和5.49%;而子任務提高到1 000 個時,Heu- Orche 的性能分別勝過它們62.9%、15.1%和25.5%.不同于那些簡單的編排策略,Heu-Orche 能夠考慮有向無環圖的數據依賴關系以及計算集群的資源使用情況,因此它能夠計算出一個更加合理的編排策略,優化任務的計算延遲.

而在圖8 中我們可以看到:當每個用戶同時進行1 000 個子任務的編排任務時,隨著用戶數量的增加,5 種算法的任務計算延遲基本上呈線性增長的趨勢.并且Heu-Orche 的性能隨著用戶數的增多,仍然保持較好的表現.相比Kubernetes,Mesos,YARN,Borg 等傳統容器編排器所使用的FCFS 和優先級算法以及傳統邊緣計算中經常使用的距離優先算法和LRTF 算法,我們提出的啟發式算法能夠更好地適應不同用戶和流量規模,具有很強的拓展性,也能夠取得更好的延遲性能,對基于有向無環圖結構的計算任務有很大的優勢.

2) 邊緣集群數量

我們測試了5 個算法在不同數量的邊緣計算集群下(1 個~5 個)和不同數量的子任務(100 個子任務和1 000個子任務)的編排性能,實驗結果如圖9 和圖10 所示.

Fig.9 Computation latency with different clusters圖9 不同邊緣集群數量下的任務計算延遲

Fig.10 Computation latency with different clusters圖10 不同邊緣集群數量下的任務計算延遲

我們可以看到:隨著邊緣計算集群數量的增加,5 個算法的計算延遲都呈現下降的趨勢;并且隨著集群數量的增加,任務的計算延遲下降的幅度會減小,因為后面加入的邊緣計算集群對于任務整體延遲的影響有限.對于FCFS、優先級算法和LRTF 算法,它們的變化趨勢基本保持穩定和一致,而距離優先算法則出現很大的波動.例如:當子任務為100 個時(如圖9 所示),距離優先算法總體上能夠獲得最優的性能,Heu-Orche 與距離優先之間的差距不是很大;而當子任務上升并固定為1 000 個之后(如圖10 所示),距離優先算法的性能是最差的,而Heu- Orche 依舊保持著很好的性能表現.這說明我們提出的啟發式編排算法能夠較好地適應不同的子任務和不同的邊緣計算集群的數量和規模.

6 結 論

在本文中,我們提出了一種容器化的邊緣計算平臺FDN.通過平臺提供的統一接口,用戶無需進行復雜的資源和環境配置就能夠訪問邊緣計算資源,計算任務也能夠被調度到最合適的邊緣計算集群進行計算.同時,我們開發了一種基于啟發式的跨集群容器編排策略,綜合考慮了用戶到集群的延遲、任務和集群閑置資源信息等,優化任務的計算延遲.我們在實際生產環境中實現并部署了FDN 平臺以及實驗模擬了啟發式的容器編排算法.實驗結果表明:我們的FDN 計算平臺能夠取得很快的計算延遲,同時,啟發式的容器編排算法相比傳統的編排策略有了較大的性能提升.

致謝感謝華為技術有限公司基于圖理論的網絡優化算法研究項目YBN2019125156 的支持.