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

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

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

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

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

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

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

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

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

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

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

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

本文的貢獻列舉如下:

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

? 提出了一種基于啟發(fā)式的容器編排策略,實現(xiàn)容器的跨集群編排,優(yōu)化用戶任務的計算延遲;

? 實現(xiàn)并部署了FDN 系統(tǒng)并評估了其性能,實驗結(jié)果表明:我們提出的FDN 架構(gòu)和容器編排算法能夠取得很好的計算延遲,能夠滿足當前網(wǎng)絡中的數(shù)據(jù)計算需求.

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

1 相關(guān)工作

1.1 流量優(yōu)化與計算平臺

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

1.2 邊緣計算

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

但是邊緣計算是基于分布式的網(wǎng)絡結(jié)構(gòu),如何管理、調(diào)度和優(yōu)化分布式的邊緣計算資源,成為了最大的挑戰(zhàn)之一.Teixeira 等人[15]指出:由于缺少統(tǒng)一的管理和調(diào)度中心,分布式的邊緣計算平臺無法獲得網(wǎng)絡流量和計算資源的實時情況,因此無法得到最優(yōu)的資源管理和調(diào)度方案,也無法達到更好的計算性能.因此,我們?yōu)榉植际降倪吘売嬎闫脚_提供一個中心化的結(jié)構(gòu),負責管理和調(diào)度邊緣計算平臺的流量和分布式計算資源,提高邊緣計算平臺的性能表現(xiàn).

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

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

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

2 FDN 技術(shù)架構(gòu)

2.1 FDN系統(tǒng)概況

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

Fig.1 Overview of FDN system圖1 FDN 系統(tǒng)概況

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 FDN控制器

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

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

2) FDN 分發(fā)器:負責計算并實現(xiàn)容器的跨集群編排,優(yōu)化每個計算任務的計算延遲.編排算法會在第3 節(jié)展示;

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

4) FDN 網(wǎng)關(guān):負責收集網(wǎng)絡的流量信息以及函數(shù)的分發(fā)與路由、集群內(nèi)的負載均衡等功能.同時,FDN網(wǎng)關(guān)還承擔著流量控制、安全策略管理、用戶授權(quán)等功能,保證FDN 系統(tǒng)安全可靠的運行;

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

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

2.3 邊緣計算集群

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

2.4 DNS

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

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

3 容器編排

3.1 問題定義

定義的記號見表1.

Table 1 Notation list表1 記號表

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

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

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

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

在容器計算的過程中,用戶需要實時把數(shù)據(jù)傳送給對應的容器進行計算.定義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 部分:一部分是在服務器上的計算消耗時間,一部分是容器間的通信時間,另一部分是用戶傳送數(shù)據(jù)給容器所在的邊緣服務器的延遲.我們定義容器c的實際開始執(zhí)行時間(actual start time)為AST(c)和實際完成執(zhí)行時間(actual finish time)為AFT(c).類似地,我們定義將容器c在集群p上最早的開始執(zhí)行時間(earliest start time)為EST(c,p),并且:

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

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

3.2 編排算法

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

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

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

假設現(xiàn)在有兩個邊緣計算集群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,那么系統(tǒng)就能取得更好的計算時間性能.

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

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

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

基于啟發(fā)式的容器編排算法具體細節(jié)見算法1.

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

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

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

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

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

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

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

4 FDN 系統(tǒng)實現(xiàn)、部署與測試

4.1 FDN實現(xiàn)細節(jié)

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

Fig.3 Implementation of FDN system圖3 FDN 系統(tǒng)實現(xiàn)

4.2 部署設定

我們在中國移動網(wǎng)絡中部署了FDN 系統(tǒng),如圖4 所示.

Fig.4 Deployment of FDN system圖4 FDN 系統(tǒng)部署

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

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

4.3 測試結(jié)果

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

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

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

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

5 容器編排模擬實驗

5.1 實驗設定

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

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

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

5.2 實驗結(jié)果

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

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

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

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

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

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

2) 邊緣集群數(shù)量

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

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

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

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

6 結(jié) 論

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

致謝感謝華為技術(shù)有限公司基于圖理論的網(wǎng)絡優(yōu)化算法研究項目YBN2019125156 的支持.