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

1(深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院,廣東 深圳 518060)

2(中國移動(dòng)通信集團(tuán)浙江有限公司,浙江 杭州 310016)

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

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

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

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

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

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

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

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

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

本文的貢獻(xiàn)列舉如下:

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

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

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

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

1 相關(guān)工作

1.1 流量優(yōu)化與計(jì)算平臺(tái)

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

1.2 邊緣計(jì)算

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

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

1.3 無服務(wù)化計(jì)算與容器編排模型

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

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

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

2.1 FDN系統(tǒng)概況

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

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

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

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

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

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

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

FDN 的運(yùn)行過程如圖2 所示,主要分為以下步驟進(jìn)行.

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

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

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

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

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

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

Fig.2 Flow chart of FDN system圖2 FDN 運(yùn)行流程圖

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

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

2.2 FDN控制器

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

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

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

3) FDN 費(fèi)用中心:負(fù)責(zé)記錄用戶使用平臺(tái)所需要支付的費(fèi)用;

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

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

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

2.3 邊緣計(jì)算集群

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

2.4 DNS

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

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

3 容器編排

3.1 問題定義

定義的記號(hào)見表1.

Table 1 Notation list表1 記號(hào)表

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

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

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

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

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

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

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

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

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

3.2 編排算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 FDN實(shí)現(xiàn)細(xì)節(jié)

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

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

4.2 部署設(shè)定

我們?cè)谥袊苿?dòng)網(wǎng)絡(luò)中部署了FDN 系統(tǒng),如圖4 所示.

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

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

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

4.3 測試結(jié)果

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

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

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

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

5 容器編排模擬實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)定

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

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

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

5.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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

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