服務(wù)器無感知計(jì)算場景下基于時(shí)空特征的函數(shù)調(diào)度

金 鑫 吳秉陽 劉方岳 章梓立 賈云杉

（北京大學(xué)計(jì)算機(jī)學(xué)院 北京 100871）

（高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室（北京大學(xué)） 北京 100871）

（xinjinpku@pku.edu.cn）

隨著云計(jì)算技術(shù)的發(fā)展，在云計(jì)算平臺(tái)上開發(fā)和部署應(yīng)用已經(jīng)成為一種主流方式.傳統(tǒng)云計(jì)算平臺(tái)將資源以虛擬機(jī)和容器等形式提供給用戶.除了開發(fā)應(yīng)用邏輯外，用戶還需要進(jìn)行虛擬機(jī)和容器等資源的配置和管理.服務(wù)器無感知計(jì)算[1]是一種新興的以函數(shù)為中心的云計(jì)算范式.服務(wù)器無感知計(jì)算向用戶提供高層次的函數(shù)抽象在云計(jì)算平臺(tái)開發(fā)和部署應(yīng)用程序，讓用戶可以專注于應(yīng)用邏輯的開發(fā)，而無需關(guān)注資源的配置和管理.

服務(wù)器無感知計(jì)算(serverless computing)以函數(shù)為粒度分配資源.用戶基于函數(shù)抽象編寫應(yīng)用程序，并將其打包為函數(shù)鏡像部署于服務(wù)器無感知計(jì)算平臺(tái).當(dāng)函數(shù)請求到來時(shí)，函數(shù)請求被發(fā)往服務(wù)器無感知計(jì)算調(diào)度器，由調(diào)度器負(fù)責(zé)函數(shù)請求的調(diào)度和執(zhí)行.調(diào)度器在集群中找到空閑服務(wù)器，在空閑服務(wù)器上加載相應(yīng)的函數(shù)鏡像，將函數(shù)鏡像啟動(dòng)為一個(gè)函數(shù)實(shí)例運(yùn)行來處理請求.

服務(wù)器無感知計(jì)算平臺(tái)使用函數(shù)鏡像存儲(chǔ)系統(tǒng)來保存函數(shù)鏡像.當(dāng)加載函數(shù)鏡像時(shí)，服務(wù)器需要通過網(wǎng)絡(luò)從函數(shù)鏡像存儲(chǔ)系統(tǒng)將所需函數(shù)鏡像傳輸?shù)奖镜兀写罅康木W(wǎng)絡(luò)傳輸和存儲(chǔ)系統(tǒng)讀取開銷，本地函數(shù)運(yùn)行時(shí)也需要加載相關(guān)依賴庫和進(jìn)行初始化操作，加載時(shí)間長.從遠(yuǎn)程函數(shù)鏡像存儲(chǔ)系統(tǒng)加載和啟動(dòng)容器及函數(shù)運(yùn)行時(shí)的過程稱為冷啟動(dòng).為了優(yōu)化函數(shù)啟動(dòng)時(shí)間，服務(wù)器無感知計(jì)算平臺(tái)通常會(huì)在服務(wù)器本地對(duì)函數(shù)鏡像進(jìn)行緩存.當(dāng)所需函數(shù)鏡像在本地緩存時(shí)，服務(wù)器可以直接啟動(dòng)該函數(shù)鏡像，而無需再從遠(yuǎn)程函數(shù)鏡像存儲(chǔ)系統(tǒng)加載.除此之外，容器和函數(shù)運(yùn)行時(shí)也可以預(yù)先啟動(dòng)等待執(zhí)行函數(shù)代碼，這個(gè)函數(shù)啟動(dòng)過程稱為熱啟動(dòng).

函數(shù)完成時(shí)間是從函數(shù)請求到來直到函數(shù)執(zhí)行結(jié)束所經(jīng)過的時(shí)間，其直接反映函數(shù)應(yīng)用的性能，是衡量服務(wù)器無感知計(jì)算平臺(tái)的重要指標(biāo).影響函數(shù)完成時(shí)間的因素主要包括排隊(duì)時(shí)間、啟動(dòng)時(shí)間和執(zhí)行時(shí)間3 個(gè)方面.函數(shù)排隊(duì)時(shí)間指函數(shù)請求在調(diào)度器隊(duì)列中等待被調(diào)度的時(shí)間.如果函數(shù)服務(wù)器本地沒有緩存函數(shù)鏡像，則需要通過冷啟動(dòng)從遠(yuǎn)程函數(shù)鏡像存儲(chǔ)系統(tǒng)加載并啟動(dòng)函數(shù)鏡像和函數(shù)運(yùn)行時(shí)，產(chǎn)生額外的冷啟動(dòng)開銷.函數(shù)執(zhí)行時(shí)間指函數(shù)鏡像加載和啟動(dòng)后，函數(shù)實(shí)例運(yùn)行處理函數(shù)請求的時(shí)間.

在服務(wù)器無感知計(jì)算場景下，對(duì)函數(shù)請求進(jìn)行調(diào)度來優(yōu)化函數(shù)完成時(shí)間是一項(xiàng)挑戰(zhàn)，其主要面臨問題規(guī)模大和動(dòng)態(tài)性強(qiáng)2 個(gè)難點(diǎn).

1）問題規(guī)模大.服務(wù)器無感知計(jì)算平臺(tái)以函數(shù)為粒度進(jìn)行調(diào)度，需要在短時(shí)間內(nèi)調(diào)度大量并發(fā)的函數(shù)來執(zhí)行處理函數(shù)請求.這要求調(diào)度器有很好的可擴(kuò)展性，限制了調(diào)度器為每個(gè)函數(shù)維護(hù)過多的調(diào)度信息.

2）動(dòng)態(tài)性強(qiáng).來自用戶的函數(shù)請求動(dòng)態(tài)性強(qiáng)，不同函數(shù)執(zhí)行時(shí)間、資源需求等時(shí)空特征差異較大，并且在調(diào)度時(shí)無法知道未來函數(shù)請求精確的任務(wù)時(shí)空特征，不能基于所有信息直接做約束求解.

現(xiàn)有服務(wù)器無感知計(jì)算相關(guān)工作使用先來先服務(wù)（first come first serve，F(xiàn)CFS）算法作為函數(shù)調(diào)度算法[2-4].當(dāng)隊(duì)頭請求的函數(shù)執(zhí)行時(shí)間很長，或者本地沒有該函數(shù)鏡像的緩存，冷啟動(dòng)時(shí)間很長時(shí)，會(huì)導(dǎo)致隊(duì)頭阻塞（head-of-line blocking），排在隊(duì)列后面的請求需要等待很久才能被執(zhí)行，使得整個(gè)系統(tǒng)的平均函數(shù)完成時(shí)間變長.最短任務(wù)優(yōu)先（shortest job first，SJF）策略是一種經(jīng)典的解決隊(duì)頭阻塞問題的策略.然而，在服務(wù)器無感知計(jì)算場景下，經(jīng)典的最短任務(wù)優(yōu)先策略不能完全解決隊(duì)頭阻塞問題，因?yàn)榕旁陉?duì)頭的請求可能因?yàn)槔鋯?dòng)造成較長的完成時(shí)間，影響隊(duì)列后面請求的執(zhí)行，仍舊造成隊(duì)頭阻塞.除此之外，最短任務(wù)優(yōu)先策略等經(jīng)典算法也沒有考慮不同函數(shù)在資源消耗方面的空間特征，這導(dǎo)致資源消耗較大的函數(shù)任務(wù)可能阻礙后續(xù)多個(gè)資源消耗較少的任務(wù)并發(fā)執(zhí)行，進(jìn)而加劇隊(duì)頭阻塞.

目前有一些工作通過設(shè)計(jì)函數(shù)鏡像緩存策略降低函數(shù)冷啟動(dòng)率[3-6].AWS 和Azure 等商用平臺(tái)以及OpenWhisk 等開源平臺(tái)使用固定函數(shù)鏡像緩存策略.該策略在函數(shù)執(zhí)行完成后，將運(yùn)行時(shí)環(huán)境保存一個(gè)固定時(shí)間長度（例如10 min）.一些工作對(duì)緩存策略進(jìn)行了優(yōu)化，比如利用貪心對(duì)偶大小頻率（greedy-dual size frequency，GDSF）緩存算法等.這些工作側(cè)重于設(shè)計(jì)更好的緩存策略來降低冷啟動(dòng)概率，但沒有將冷啟動(dòng)與調(diào)度進(jìn)行綜合考慮.這些工作在調(diào)度上使用基礎(chǔ)的FCFS 調(diào)度策略，即使通過緩存策略降低了冷啟動(dòng)概率，還是會(huì)遇到由于調(diào)度順序不佳造成的隊(duì)頭阻塞問題，影響整個(gè)系統(tǒng)的平均函數(shù)完成時(shí)間.

為此，本文研究了服務(wù)器無感知計(jì)算場景下的函數(shù)調(diào)度問題，提出了針對(duì)服務(wù)器無感知計(jì)算的函數(shù)調(diào)度方案，主要貢獻(xiàn)有3 個(gè)方面:

1）分析了服務(wù)器無感知計(jì)算場景下的函數(shù)調(diào)度問題，并定位了3 個(gè)影響函數(shù)完成時(shí)間的因素，分別是排隊(duì)時(shí)間、啟動(dòng)時(shí)間和執(zhí)行時(shí)間.基于該分析，提出了數(shù)學(xué)模型對(duì)服務(wù)器無感知計(jì)算場景下函數(shù)調(diào)度問題進(jìn)行形式化建模，為函數(shù)調(diào)度問題提供優(yōu)化目標(biāo).

2）設(shè)計(jì)了基于函數(shù)時(shí)空特征的服務(wù)器無感知計(jì)算調(diào)度算法FuncSched，綜合考慮時(shí)間和空間2 個(gè)維度的特征.在時(shí)間維度上，利用時(shí)間分析器評(píng)估函數(shù)執(zhí)行時(shí)間，并利用預(yù)熱的函數(shù)鏡像的狀態(tài)和函數(shù)請求對(duì)應(yīng)的位置預(yù)測函數(shù)啟動(dòng)時(shí)間；在空間維度上，考慮函數(shù)運(yùn)行時(shí)的資源占用量.該策略根據(jù)時(shí)間和空間維度的特征計(jì)算函數(shù)請求優(yōu)先級(jí)，基于優(yōu)先級(jí)進(jìn)行調(diào)度，并根據(jù)運(yùn)行時(shí)狀態(tài)對(duì)優(yōu)先級(jí)進(jìn)行動(dòng)態(tài)更新.

3）針對(duì)服務(wù)器無感知計(jì)算場景下函數(shù)調(diào)度問題，為了驗(yàn)證本文所提調(diào)度算法的有效性，實(shí)現(xiàn)了原型系統(tǒng)，并使用了真實(shí)世界服務(wù)器無感知計(jì)算負(fù)載數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明所提調(diào)度算法可以有效降低平均函數(shù)完成時(shí)間，并對(duì)性能提升原因進(jìn)行了分析.實(shí)驗(yàn)還評(píng)估了所提調(diào)度算法與不同緩存策略的兼容性，表明所提調(diào)度算法在多種緩存策略下都能有效降低平均函數(shù)完成時(shí)間，從而驗(yàn)證了本文所提調(diào)度算法的有效性.

1 相關(guān)工作

1.1 服務(wù)器無感知計(jì)算函數(shù)性能優(yōu)化

函數(shù)性能優(yōu)化是當(dāng)前服務(wù)器無感知計(jì)算領(lǐng)域的重要研究方向.眾多工作基于檢查點(diǎn)/恢復(fù)、自模版啟動(dòng)、運(yùn)行時(shí)環(huán)境預(yù)啟動(dòng)等多種技術(shù)縮減冷啟動(dòng)開銷，減少用戶請求的響應(yīng)延遲.接下來，我們分類概述已有相關(guān)工作，并將其與本文工作進(jìn)行比較分析.

當(dāng)用戶請求對(duì)應(yīng)的鏡像文件未存儲(chǔ)在本地時(shí)，云平臺(tái)需要首先從遠(yuǎn)端下載鏡像文件，而后再啟動(dòng)運(yùn)行時(shí)環(huán)境，這一過程的耗時(shí)可能長達(dá)數(shù)秒.為了優(yōu)化鏡像文件的下載速度，文獻(xiàn)[7]基于共享網(wǎng)絡(luò)文件系統(tǒng)對(duì)鏡像文件進(jìn)行存儲(chǔ)和拉取，并基于延遲加載加速容器啟動(dòng).文獻(xiàn)[8]和文獻(xiàn)[9]通過分布式文件系統(tǒng)存儲(chǔ)鏡像文件以提升讀取效率.文獻(xiàn)[10]使用P2P 結(jié)構(gòu)加速容器鏡像文件的分發(fā).文獻(xiàn)[11]基于樹狀P2P 網(wǎng)絡(luò)加速虛擬機(jī)鏡像文件的傳輸.文獻(xiàn)[12]將虛擬機(jī)組織為動(dòng)態(tài)變化的樹結(jié)構(gòu)以完成虛擬機(jī)鏡像文件的快速分發(fā)，并采用樹平衡算法在大型服務(wù)器無感知計(jì)算平臺(tái)的高可變環(huán)境下保證樹結(jié)構(gòu)穩(wěn)定.

部分工作將已就緒的運(yùn)行時(shí)環(huán)境打包為快照文件并存儲(chǔ)起來，在后續(xù)的用戶請求到來時(shí)直接復(fù)現(xiàn)，從而縮減運(yùn)行時(shí)環(huán)境的啟動(dòng)時(shí)間.文獻(xiàn)[13]將用戶函數(shù)代碼、語言解釋器、依賴庫在內(nèi)的運(yùn)行時(shí)狀態(tài)打包為Unikernels[14]快照文件以優(yōu)化其后續(xù)啟動(dòng)速度.文獻(xiàn)[15]通過多個(gè)容器間的狀態(tài)共享支持高并發(fā)的負(fù)載場景.文獻(xiàn)[16]基于類似思路實(shí)現(xiàn)了虛擬機(jī)間的即時(shí)編譯（just-in-time compilation，JIT）文件共享.文獻(xiàn)[17]同時(shí)對(duì)快照文件中的應(yīng)用狀態(tài)（如內(nèi)存使用）及系統(tǒng)狀態(tài)（如文件打開情況）進(jìn)行按需恢復(fù)與延遲恢復(fù)，進(jìn)一步加速其啟動(dòng)速度.

部分工作為使用相似運(yùn)行時(shí)環(huán)境的一類函數(shù)創(chuàng)建普適的運(yùn)行時(shí)環(huán)境模板，從而用戶函數(shù)可以自模版快速啟動(dòng).文獻(xiàn)[5]借鑒了安卓系統(tǒng)中的Zygotes[18]機(jī)制，將常用的依賴庫安裝在本地，并以只讀方式掛載到容器當(dāng)中以跳過Python 依賴庫的安裝與加載過程.文獻(xiàn)[19]利用調(diào)用頻率較低的空閑容器創(chuàng)建Zygotes 容器.在Zygotes 容器中安裝所有用戶函數(shù)的依賴包，從而后續(xù)函數(shù)請求在函數(shù)執(zhí)行過程中無需再進(jìn)行依賴包加載.

在服務(wù)器無感知計(jì)算中，函數(shù)執(zhí)行的時(shí)間通常只有數(shù)秒[3]，而函數(shù)的冷啟動(dòng)時(shí)間包括函數(shù)鏡像拉取開銷和函數(shù)運(yùn)行所依賴環(huán)境的啟動(dòng)開銷，往往也需要幾秒的時(shí)間[3]，因此優(yōu)化函數(shù)的冷啟動(dòng)是服務(wù)器無感知計(jì)算系統(tǒng)的重要目標(biāo).通過提前啟動(dòng)運(yùn)行時(shí)環(huán)境可以避免冷啟動(dòng)的發(fā)生.主流商用及開源服務(wù)器無感知平臺(tái)[2,20-22]通常在函數(shù)執(zhí)行結(jié)束之后將運(yùn)行時(shí)環(huán)境在集群中保留固定時(shí)長（例如10 min），由此調(diào)用頻繁的用戶函數(shù)能夠?qū)崿F(xiàn)穩(wěn)定熱啟動(dòng)，這類策略規(guī)則簡單，但帶來了顯著的資源浪費(fèi).

部分工作基于調(diào)用預(yù)測針對(duì)性地預(yù)啟動(dòng)運(yùn)行時(shí)環(huán)境.文獻(xiàn)[3]從周期性角度對(duì)函數(shù)進(jìn)行分類，對(duì)于周期性較差的函數(shù)使用ARIMA[23]等標(biāo)準(zhǔn)時(shí)間序列預(yù)測算法，而對(duì)于具有明顯周期性的函數(shù)則使用基于直方頻率分布的啟發(fā)式規(guī)則進(jìn)行負(fù)載預(yù)測，在函數(shù)最可能被調(diào)用的時(shí)段內(nèi)維持預(yù)啟動(dòng)環(huán)境.文獻(xiàn)[6]基于傅里葉變化對(duì)函數(shù)未來并發(fā)數(shù)進(jìn)行預(yù)測.在此基礎(chǔ)上，根據(jù)預(yù)測結(jié)果調(diào)整運(yùn)行時(shí)環(huán)境在集群內(nèi)的部署位置，將有更大可能被調(diào)用的運(yùn)行時(shí)環(huán)境部署在高性能服務(wù)器上，調(diào)用概率較低的則部署在低性能服務(wù)器上，從而降低維持預(yù)啟動(dòng)環(huán)境的花費(fèi).文獻(xiàn)[24]設(shè)計(jì)了長短直方預(yù)測（long-short term histogram，LSTH）算法，綜合分析函數(shù)在天和小時(shí)粒度下的周期性特征，以適應(yīng)機(jī)器學(xué)習(xí)任務(wù)以天為粒度的周期性特征以及以小時(shí)/分鐘為粒度的偶然性波動(dòng).文獻(xiàn)[25]基于長短期記憶（long short-term memory，LSTM）網(wǎng)絡(luò)對(duì)函數(shù)調(diào)用歷史進(jìn)行特征抓取，在此基礎(chǔ)上基于貝葉斯優(yōu)化對(duì)預(yù)啟動(dòng)資源池進(jìn)行動(dòng)態(tài)調(diào)整.

在負(fù)載預(yù)測之外，部分工作優(yōu)化固定內(nèi)存大小下的實(shí)例集合以降低函數(shù)冷啟動(dòng)率.部分工作借鑒緩存策略管理預(yù)啟動(dòng)環(huán)境，將運(yùn)行時(shí)環(huán)境視為緩存對(duì)象，將冷啟動(dòng)與熱啟動(dòng)分別視為緩存未命中和緩存命中，從而將緩存策略應(yīng)用于服務(wù)器無感知計(jì)算領(lǐng)域.文獻(xiàn)[5]使用最近最少使用（least recently used，LRU）策略管理運(yùn)行時(shí)環(huán)境的緩存.文獻(xiàn)[4]則借鑒貪心對(duì)偶大小頻率（greedy-dual size frequency，GDSF）緩存算法[26]，綜合考慮運(yùn)行時(shí)環(huán)境的調(diào)用頻率、大小、用戶函數(shù)冷啟動(dòng)時(shí)間、最近調(diào)用間隔等因素，在內(nèi)存中保留優(yōu)先級(jí)最高的運(yùn)行時(shí)環(huán)境.此外，部分工作致力于縮減單個(gè)運(yùn)行時(shí)環(huán)境的內(nèi)存占用，從而增加固定內(nèi)存中可容納的運(yùn)行時(shí)環(huán)境實(shí)例個(gè)數(shù).例如，文獻(xiàn)[27]針對(duì)服務(wù)器無感知場景縮減USB 等虛擬機(jī)構(gòu)件，從而將內(nèi)存開銷壓縮至QEMU 的數(shù)十分之一；文獻(xiàn)[28]同樣通過優(yōu)化虛擬機(jī)開銷將單個(gè)安全容器的內(nèi)存占用壓縮至數(shù)百M(fèi)B.

雖然已有工作從多個(gè)角度優(yōu)化了服務(wù)器無感知計(jì)算場景下的函數(shù)完成時(shí)間，然而由于本節(jié)工作均未意識(shí)到調(diào)度算法對(duì)函數(shù)完成時(shí)間的影響，從而仍舊無法避免函數(shù)請求在高負(fù)載場景下的隊(duì)頭阻塞問題.與之相對(duì)的，本文提出了基于函數(shù)時(shí)空特征的服務(wù)器無感知計(jì)算函數(shù)調(diào)度算法FuncSched，降低函數(shù)完成時(shí)間.

1.2 任務(wù)調(diào)度

任務(wù)調(diào)度器通過調(diào)整任務(wù)執(zhí)行順序來優(yōu)化任務(wù)完成時(shí)間.SJF 算法[29]能夠有效避免長任務(wù)對(duì)后續(xù)多個(gè)短任務(wù)的長時(shí)間阻塞.最短剩余時(shí)間（shortest remaining time first，SRTF）優(yōu)先算法[30]允許新到來的短任務(wù)搶占正在運(yùn)行的長任務(wù)，以實(shí)現(xiàn)更優(yōu)的任務(wù)完成時(shí)間.Gittins 索引策略[31]能夠在用戶任務(wù)耗時(shí)不定，但符合特定分布時(shí)降低平均任務(wù)完成時(shí)間，而多級(jí)反饋隊(duì)列（multi-level feedback queue，MLFQ）算法[32]以及最小獲得服務(wù)者優(yōu)先（least attained service，LAS）算法[33]等啟發(fā)式算法則規(guī)避了文獻(xiàn)[29-31]所述算法必須對(duì)任務(wù)運(yùn)行時(shí)間具有先驗(yàn)知識(shí)的弊端，從而適用于機(jī)器學(xué)習(xí)等難以估計(jì)任務(wù)運(yùn)行時(shí)間的場景[34].此外，文獻(xiàn)[35]通過頻繁搶占長任務(wù)保證短任務(wù)的優(yōu)先執(zhí)行，從而優(yōu)化尾部延遲.

部分工作通過任務(wù)分類與資源預(yù)留避免任務(wù)阻塞，優(yōu)化任務(wù)完成時(shí)間.例如文獻(xiàn)[36]將用戶請求劃分為長任務(wù)和短任務(wù)，并專門預(yù)留部分資源處理短任務(wù)，以避免短任務(wù)阻塞.另一些工作則通過提高調(diào)度效率縮減任務(wù)完成時(shí)間，例如文獻(xiàn)[37]和文獻(xiàn)[38]將長任務(wù)和短任務(wù)分別部署在集中式和分布式調(diào)度器上，由此避免巨量短期任務(wù)在調(diào)度過程中被阻塞.文獻(xiàn)[39]和文獻(xiàn)[40]則采用了工作竊取策略，允許空閑工作線程“竊取”高負(fù)載工作線程的任務(wù)隊(duì)列，從而在分布式調(diào)度場景中實(shí)現(xiàn)良好的負(fù)載均衡，避免不必要的任務(wù)阻塞.其他工作則同時(shí)考慮到不同任務(wù)的延遲要求，例如BVT 算法[41]計(jì)算任務(wù)的排隊(duì)時(shí)間與目標(biāo)延遲時(shí)間的比值，并優(yōu)先調(diào)度比值最大的任務(wù).而文獻(xiàn)[42]則允許用戶通過聲明式語言為高優(yōu)先級(jí)任務(wù)預(yù)留部分計(jì)算資源，從而避免高優(yōu)先級(jí)任務(wù)被低優(yōu)先級(jí)任務(wù)阻塞.

文獻(xiàn)[29-41]所述的工作沒有考慮服務(wù)器無感知計(jì)算場景的時(shí)空特點(diǎn)，時(shí)間上不同的函數(shù)請求的執(zhí)行時(shí)間差異很大，最高可差8 個(gè)數(shù)量級(jí)[3]；空間上不同的函數(shù)請求的資源占用差異也很大[3].這些工作無法直接應(yīng)用于服務(wù)器無感知計(jì)算場景的函數(shù)調(diào)度.本文根據(jù)函數(shù)時(shí)空特性，設(shè)計(jì)了面向服務(wù)器無感知計(jì)算場景的調(diào)度算法，在保證調(diào)度器高效運(yùn)行的前提下優(yōu)化函數(shù)完成時(shí)間.

2 問題定義和建模

2.1 問題分析

本文旨在研究面向服務(wù)器無感知計(jì)算場景的函數(shù)調(diào)度算法.服務(wù)器無感知計(jì)算平臺(tái)提供基于函數(shù)的高層次抽象，使得用戶無需顯式配置和管理云資源，只需要編寫和提交應(yīng)用邏輯相關(guān)的函數(shù).服務(wù)器無感知計(jì)算平臺(tái)負(fù)責(zé)調(diào)度函數(shù)、分配資源和執(zhí)行函數(shù)，圖1 展示了服務(wù)器無感知計(jì)算平臺(tái)的框架和工作流程.在這一框架中，控制平面的調(diào)度器需要結(jié)合函數(shù)時(shí)間分析器和資源管理器決定具體的函數(shù)執(zhí)行順序.在這種執(zhí)行模式下，調(diào)度算法和函數(shù)鏡像緩存策略[4,6]會(huì)極大影響函數(shù)執(zhí)行性能.因此，本文研究的問題是在服務(wù)器無感知計(jì)算場景下的函數(shù)調(diào)度，以優(yōu)化函數(shù)完成時(shí)間.

Fig.1 Architecture overview圖1 架構(gòu)概覽

2.2 問題建模

1）系統(tǒng)建模.我們將服務(wù)器無感知計(jì)算平臺(tái)的集群資源建模成一個(gè)大小為m×n的矩陣M.集群包含m個(gè)函數(shù)服務(wù)器，計(jì)算負(fù)載包含n個(gè)函數(shù).M[i,j]=1表示第i個(gè)函數(shù)服務(wù)器上緩存了第j個(gè)函數(shù)對(duì)應(yīng)的鏡像；E(j)表示函數(shù)j的執(zhí)行時(shí)間；D(j) 表示函數(shù)j對(duì)應(yīng)的冷啟動(dòng)時(shí)間.

2）任務(wù)建模.總共有l(wèi)個(gè)函數(shù)請求，函數(shù)請求的集合是F，F(xiàn)[k]表示第k個(gè)函數(shù)請求對(duì)應(yīng)的函數(shù)編號(hào)，F(xiàn)[k]a表示第k個(gè)函數(shù)請求的到達(dá)時(shí)間，F(xiàn)[k]s表示第k個(gè)函數(shù)請求被系統(tǒng)調(diào)度開始執(zhí)行的時(shí)間，F(xiàn)[k]e表示第k個(gè)函數(shù)請求被執(zhí)行完成的時(shí)間，O為順序數(shù)組[1,2,…,l]的置換數(shù)組.本文中主要符號(hào)及含義如表1所示.

Table 1 Symbol Table表1 符號(hào)表

基于上述問題建模，本文的研究問題包含如何設(shè)計(jì)函數(shù)調(diào)度算法和決定函數(shù)的執(zhí)行順序，以優(yōu)化平均函數(shù)完成時(shí)間.

2.3 問題定義

對(duì)于第k個(gè)函數(shù)請求，如果要調(diào)度該函數(shù)到函數(shù)服務(wù)器i，其完成時(shí)間為F[k]e-F[k]a=E(F[k])+D(F[k])×M[i,F[k]]+F[k]s-F[k]a，由執(zhí)行時(shí)間、冷啟動(dòng)時(shí)間和排隊(duì)時(shí)間組成.要優(yōu)化的目標(biāo)是所有函數(shù)請求的平均完成時(shí)間，那么目標(biāo)函數(shù)歸約為：

式（1）中，不確定的變量有函數(shù)的調(diào)度時(shí)間F[k]s和函數(shù)的放置位置i.其中M[i,F[k]]表示函數(shù)是否是熱啟動(dòng)，如果是熱啟動(dòng)則不需要從全局函數(shù)鏡像存儲(chǔ)拉取鏡像，對(duì)應(yīng)的函數(shù)冷啟動(dòng)開銷為0.

首先分析函數(shù)請求的執(zhí)行順序O所帶來的約束條件.對(duì)于k=O[u]，即順序中的第u個(gè)函數(shù)請求，對(duì)應(yīng)函數(shù)請求集合中的第k個(gè)元素.排在其順序之前的所有函數(shù)請求（O[1],O[2],…,O[u-1]）都應(yīng)該比O[u]有更高的優(yōu)先級(jí)，即需要滿足約束條件：

即O[u]的調(diào)度時(shí)間一定不早于排在其前面的函數(shù)請求的調(diào)度時(shí)間.其次是集群資源的限制，令時(shí)刻t函數(shù)服務(wù)器i的空閑資源量為Vi(t)，函數(shù)請求O[u]可以在函數(shù)服務(wù)器i上執(zhí)行的約束條件是：

即要求目標(biāo)放置服務(wù)器的空閑資源數(shù)量足夠容納即將要調(diào)度的函數(shù)請求，假設(shè)數(shù)組A表示函數(shù)請求放置的服務(wù)器標(biāo)號(hào)，那么在決定O[u]的放置策略時(shí)，?q

綜上所述，該問題的數(shù)學(xué)模型為：

目標(biāo)函數(shù)：

約束條件，即式（2）（3）：

約束條件（2）保證了調(diào)度的優(yōu)先級(jí)，約束條件（3）保證了有資源執(zhí)行對(duì)應(yīng)函數(shù).

3 服務(wù)器無感知計(jì)算調(diào)度算法

在第2 節(jié)的問題建模指導(dǎo)下，本文分析了服務(wù)器無感知計(jì)算調(diào)度的挑戰(zhàn)和現(xiàn)有算法的局限性.基于問題建模和現(xiàn)有調(diào)度算法現(xiàn)狀，本節(jié)針對(duì)服務(wù)器無感知計(jì)算的特點(diǎn)，提出了一個(gè)基于函數(shù)時(shí)空特征的服務(wù)器無感知計(jì)算函數(shù)調(diào)度算法FuncSched，在兼容現(xiàn)有其他服務(wù)器無感知計(jì)算優(yōu)化模塊的基礎(chǔ)上，實(shí)現(xiàn)更低的平均函數(shù)完成時(shí)間.

3.1 服務(wù)器無感知計(jì)算調(diào)度的挑戰(zhàn)

服務(wù)器無感知計(jì)算旨在讓用戶只需編寫跟實(shí)際業(yè)務(wù)邏輯相關(guān)的代碼，無需關(guān)心底層資源調(diào)度、機(jī)器配置、分布式執(zhí)行等復(fù)雜底層硬件集群細(xì)節(jié)和日常運(yùn)維難點(diǎn).這一計(jì)算編程模型雖然減輕了用戶開發(fā)負(fù)擔(dān)并降低了用戶運(yùn)維成本，但是也極大增加了服務(wù)器無感知計(jì)算調(diào)度的難度.具體來說，服務(wù)器無感知計(jì)算調(diào)度存在問題規(guī)模大和動(dòng)態(tài)性強(qiáng)2 個(gè)技術(shù)難點(diǎn).

首先，由于用戶編寫的服務(wù)器無感知計(jì)算框架代碼需要以函數(shù)粒度來進(jìn)行調(diào)度，服務(wù)器無感知計(jì)算調(diào)度器需要在短時(shí)間內(nèi)調(diào)度大量并發(fā)函數(shù)執(zhí)行[3].這要求服務(wù)器無感知計(jì)算調(diào)度算法要有很好的可擴(kuò)展性.此外，對(duì)于每個(gè)函數(shù)不能維護(hù)過多的信息，因?yàn)檫@會(huì)極大增加調(diào)度器的資源消耗和復(fù)雜度.第2 節(jié)針對(duì)函數(shù)調(diào)度優(yōu)化建模的約束求解問題難以在短時(shí)間內(nèi)解出，這是因?yàn)槠浣３龅募s束求解問題本身就已經(jīng)難于整數(shù)線性規(guī)劃問題，屬于NP 問題，不能在線性時(shí)間復(fù)雜度內(nèi)解出.而在約束求解問題中，變量O可能達(dá)上百乃至上千量級(jí).如此大規(guī)模的函數(shù)調(diào)度問題不能采用指數(shù)級(jí)的約束求解器來給出調(diào)度方案.許多函數(shù)執(zhí)行時(shí)間很短，指數(shù)級(jí)時(shí)間復(fù)雜度的約束求解器調(diào)度本身的時(shí)間消耗很可能遠(yuǎn)大于函數(shù)執(zhí)行時(shí)間本身，造成極大性能損耗.

其次，服務(wù)器無感知計(jì)算調(diào)度需要面對(duì)動(dòng)態(tài)性強(qiáng)的函數(shù)執(zhí)行請求.在第2 節(jié)的問題建模中，函數(shù)請求到達(dá)時(shí)間F[k]a很難在每次調(diào)度執(zhí)行時(shí)知道其全部信息.因此，服務(wù)器無感知計(jì)算調(diào)度也不能基于所有信息的情況直接做約束求解，進(jìn)而也不能達(dá)到最優(yōu)調(diào)度計(jì)劃.現(xiàn)有研究也表明函數(shù)請求到達(dá)規(guī)律很難用泊松分布、定時(shí)執(zhí)行等模型來完全擬合[3]，因此也很難基于預(yù)測來得到較好的調(diào)度方案最優(yōu)近似解.

服務(wù)器無感知計(jì)算平臺(tái)中的函數(shù)鏡像緩存模塊也影響服務(wù)器無感知計(jì)算調(diào)度.函數(shù)鏡像緩存模塊有自己的存儲(chǔ)策略.在設(shè)計(jì)函數(shù)調(diào)度算法時(shí)，需要考慮與函數(shù)鏡像緩存模塊的兼容，并通過優(yōu)化調(diào)度算法進(jìn)一步降低平均函數(shù)完成時(shí)間.

3.2 現(xiàn)有服務(wù)器無感知計(jì)算調(diào)度的局限性

現(xiàn)有服務(wù)器無感知計(jì)算框架，例如OpenWhisk，Knative 等，通過預(yù)熱（prewarm）、延遲函數(shù)鏡像存活時(shí)間（keep-alive）等機(jī)制[2-3]優(yōu)化函數(shù)性能.最新的相關(guān)研究工作也從緩存策略等方面對(duì)服務(wù)器無感知計(jì)算進(jìn)行優(yōu)化提升[4-5].但這些工作都是優(yōu)化單一用戶函數(shù)應(yīng)用的執(zhí)行性能和資源分配.當(dāng)大量用戶函數(shù)請求同時(shí)被觸發(fā)時(shí)，用戶函數(shù)間會(huì)產(chǎn)生資源競爭.如何在用戶函數(shù)調(diào)用請求間進(jìn)行資源調(diào)度，目前的實(shí)踐和最新研究都深度不夠.

具體來說，目前的服務(wù)器無感知計(jì)算框架，當(dāng)面對(duì)大量同時(shí)到達(dá)的用戶函數(shù)調(diào)用請求時(shí)，采用的是FCFS 算法進(jìn)行調(diào)度，即

這樣的調(diào)度算法優(yōu)勢在于其調(diào)度算法執(zhí)行開銷較小，不會(huì)較大影響函數(shù)調(diào)用的端到端完成時(shí)間.另一方面，這一調(diào)度算法會(huì)產(chǎn)生隊(duì)頭阻塞.當(dāng)一個(gè)函數(shù)請求執(zhí)行時(shí)間較長時(shí)，后繼的函數(shù)請求將經(jīng)受很長的等待時(shí)間，進(jìn)而造成函數(shù)性能下降.

3.3 基于時(shí)空特征的函數(shù)調(diào)度算法FuncSched

針對(duì)3.1 節(jié)和3.2 節(jié)所述的問題和挑戰(zhàn)，本文提出了一個(gè)面向服務(wù)器無感知計(jì)算場景的基于時(shí)空特征的函數(shù)調(diào)度算法FuncSched 以優(yōu)化函數(shù)完成時(shí)間，并且能兼容服務(wù)器無感知計(jì)算的函數(shù)鏡像緩存模塊.這一算法從經(jīng)典的SJF 算法泛化而來，但是Func-Sched 同時(shí)考慮到了函數(shù)任務(wù)的時(shí)間和空間2 個(gè)維度的特征.

3.3.1 函數(shù)時(shí)間特征估測

在時(shí)間維度上，本文利用了服務(wù)器無感知計(jì)算平臺(tái)中的用戶函數(shù)會(huì)被反復(fù)調(diào)用的特點(diǎn)，提前利用時(shí)間分析器評(píng)估每個(gè)用戶函數(shù)需要執(zhí)行的時(shí)間E(j).服務(wù)器無感知計(jì)算調(diào)度器以這個(gè)時(shí)間指標(biāo)指導(dǎo)函數(shù)調(diào)度.傳統(tǒng)的SJF 算法以任務(wù)執(zhí)行時(shí)間E(j)為標(biāo)準(zhǔn)，優(yōu)先調(diào)度E(j)最小的任務(wù)執(zhí)行，從而避免了先到達(dá)的任務(wù)因?yàn)閳?zhí)行時(shí)間較長阻塞后續(xù)任務(wù)的問題.與之不同的是，F(xiàn)uncSched 同時(shí)綜合考慮了函數(shù)執(zhí)行時(shí)間和函數(shù)在服務(wù)器無感知計(jì)算平臺(tái)的啟動(dòng)時(shí)間.設(shè)計(jì)背景在于，細(xì)粒度函數(shù)的執(zhí)行時(shí)間通常較短，而函數(shù)的啟動(dòng)時(shí)間反而會(huì)對(duì)函數(shù)任務(wù)最終的端到端完成時(shí)間產(chǎn)生較大影響.當(dāng)函數(shù)處于熱啟動(dòng)狀態(tài)時(shí)，函數(shù)可以立刻執(zhí)行；當(dāng)函數(shù)處于冷啟動(dòng)狀態(tài)時(shí)，即使函數(shù)執(zhí)行時(shí)間較短，較長的函數(shù)啟動(dòng)時(shí)間也會(huì)阻塞后繼函數(shù).

函數(shù)啟動(dòng)時(shí)間，其不僅與函數(shù)自身代碼邏輯緊密相關(guān)，也受服務(wù)器無感知計(jì)算框架的函數(shù)鏡像緩存模塊的影響.函數(shù)鏡像緩存模塊的決策具有動(dòng)態(tài)性，其會(huì)基于現(xiàn)有負(fù)載、用戶要求等在運(yùn)行時(shí)做出決策，從而影響函數(shù)啟動(dòng)時(shí)間.對(duì)于這一動(dòng)態(tài)變化的函數(shù)運(yùn)行開銷，一個(gè)設(shè)計(jì)背景是，函數(shù)鏡像緩存模塊只會(huì)影響預(yù)熱的函數(shù)鏡像的狀態(tài)和函數(shù)請求對(duì)應(yīng)的位置F[k].因?yàn)榉?wù)器無感知調(diào)度平臺(tái)中的函數(shù)鏡像緩存模塊對(duì)調(diào)度器白盒可見，因此調(diào)度器可以提前預(yù)測后繼函數(shù)請求需要經(jīng)歷的啟動(dòng)時(shí)間.具體來說，F(xiàn)uncSched 會(huì)維護(hù)一個(gè)變量W(j)，表示函數(shù)j可以被熱啟動(dòng)的函數(shù)請求數(shù)量.當(dāng)函數(shù)j的鏡像被預(yù)熱或有函數(shù)j請求結(jié)束時(shí)，調(diào)度器即可立即將W(j)加1，表示新增一個(gè)可以熱啟動(dòng)的函數(shù)請求容量.當(dāng)函數(shù)j的鏡像被驅(qū)逐或有函數(shù)j請求開始執(zhí)行時(shí)，調(diào)度器立即將W(j)減1，表示減少一個(gè)可以熱啟動(dòng)的函數(shù)請求容量.通過維護(hù)變量W(j)，F(xiàn)uncSched 可以實(shí)時(shí)感知函數(shù)鏡像緩存模塊對(duì)函數(shù)啟動(dòng)時(shí)間的影響，進(jìn)而增強(qiáng)對(duì)函數(shù)整體運(yùn)行時(shí)間的把控.除此之外，利用W(j)進(jìn)行函數(shù)調(diào)度的過程還將函數(shù)啟動(dòng)時(shí)間的判定從每輪函數(shù)調(diào)度邏輯的關(guān)鍵路徑上移除，降低了大規(guī)模調(diào)度細(xì)粒度函數(shù)的開銷.并且，這一數(shù)據(jù)結(jié)構(gòu)所需存儲(chǔ)空間小，不會(huì)讓調(diào)度器產(chǎn)生額外的存儲(chǔ)壓力.

3.3.2 函數(shù)空間特征估測

在空間維度上，F(xiàn)uncSched 調(diào)度時(shí)考慮了每個(gè)函數(shù)的運(yùn)行時(shí)資源占用情況.傳統(tǒng)的調(diào)度算法，無論是FCFS 算法或者SJF 算法，其都是基于時(shí)間維度的調(diào)度算法.但是在服務(wù)器無感知計(jì)算環(huán)境中，函數(shù)資源占用差異較大，如果單純按照函數(shù)運(yùn)行時(shí)間進(jìn)行任務(wù)調(diào)度，仍然很難達(dá)到較低平均函數(shù)完成時(shí)間.例如，一個(gè)資源消耗量非常大的函數(shù)請求，即使其完成時(shí)間很短，也可能會(huì)導(dǎo)致很多可以并行執(zhí)行且資源消耗很少的函數(shù)請求被阻塞，進(jìn)而產(chǎn)生更長的平均函數(shù)完成時(shí)間.因此，函數(shù)的資源消耗情況也是函數(shù)調(diào)度需要考慮的關(guān)鍵因素.在資源消耗的度量上，F(xiàn)uncSched 選擇采用函數(shù)占用內(nèi)存作為表示函數(shù)資源消耗的中間量，其原因有2 個(gè)方面：這一方面是因?yàn)橛脩粼谔峤缓瘮?shù)給服務(wù)器無感知計(jì)算平臺(tái)時(shí)，會(huì)指定用戶函數(shù)需要的內(nèi)存大小，該信息調(diào)度器比較容易被獲取；另一方面，根據(jù)商用服務(wù)器無感知計(jì)算平臺(tái)AWS Lambda 的測算[27]，內(nèi)存成本大約占服務(wù)器成本的40%，是服務(wù)器中最重要的資源之一.

3.3.3 FuncSched 調(diào)度算法整體流程

通過綜合考慮每個(gè)函數(shù)的時(shí)間特征和空間特征，本文提出了一個(gè)新型的函數(shù)請求優(yōu)先級(jí)指標(biāo)P(k).對(duì)于使用函數(shù)容器j的函數(shù)請求k，P(k)計(jì)算為

基于這一優(yōu)先級(jí)P[k]，F(xiàn)uncSched 將優(yōu)先調(diào)度P[k]最小的函數(shù)請求.

對(duì)于一個(gè)函數(shù)而言，它的整個(gè)生命周期如圖2所示.首先在函數(shù)鏡像提交時(shí)，F(xiàn)uncSched 的性能分析器會(huì)基于提交的函數(shù)鏡像測算出該函數(shù)的冷啟動(dòng)時(shí)間D(j)、任務(wù)執(zhí)行時(shí)間E(j)以及函數(shù)資源消耗量R(j)，并將這些數(shù)據(jù)保存在函數(shù)性能數(shù)據(jù)存儲(chǔ)庫中.當(dāng)該函數(shù)的函數(shù)請求到達(dá)時(shí)，調(diào)度器會(huì)從函數(shù)性能數(shù)據(jù)存儲(chǔ)庫中將該函數(shù)的時(shí)間特征、空間特征取出，并結(jié)合函數(shù)鏡像緩存模塊提供的空閑可用的函數(shù)容器數(shù)W(j)來綜合算出該請求的優(yōu)先級(jí)P(k).當(dāng)該函數(shù)優(yōu)先級(jí)最高時(shí)，調(diào)度器會(huì)觸發(fā)函數(shù)服務(wù)器執(zhí)行該函數(shù).根據(jù)函數(shù)鏡像實(shí)時(shí)情況，調(diào)度器會(huì)相應(yīng)更新W(j)的值，并更新其待執(zhí)行的函數(shù)請求的優(yōu)先級(jí)P(k).最后，這些請求將根據(jù)優(yōu)先級(jí)重新排序，具體算法如算法1 所示.

算法1.基于時(shí)間感知的函數(shù)調(diào)度算法.

3.3.4 調(diào)度示例

圖3 展示了一個(gè)不同調(diào)度算法的示例.該示例中，一個(gè)包含2 個(gè)單位內(nèi)存的函數(shù)服務(wù)器需要服務(wù)4 個(gè)依次到來的函數(shù)請求F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，其中只有F4有已經(jīng)預(yù)熱的函數(shù)鏡像，F(xiàn)1，F(xiàn)2占用一個(gè)單位內(nèi)存，F(xiàn)3，F(xiàn)4占用2 個(gè)單位內(nèi)存.D表示函數(shù)請求的冷啟動(dòng)時(shí)間，若函數(shù)請求為熱啟動(dòng)則不存在D；E表示函數(shù)請求的執(zhí)行時(shí)間.可以看到，F(xiàn)CFS，SJF 和FuncSched 的平均函數(shù)完成時(shí)間分別是7.25，9.25 和5.5.因?yàn)镕uncSched考慮了緩存機(jī)制的影響和函數(shù)的空間特性，會(huì)優(yōu)先執(zhí)行F4函數(shù)請求，這樣一方面減少了函數(shù)請求的等待時(shí)間，另一方面也增大了函數(shù)的熱啟動(dòng)概率，進(jìn)而實(shí)現(xiàn)了最優(yōu)的平均函數(shù)完成時(shí)間.而FCFS，SJF 只考慮了函數(shù)請求的時(shí)間特性，嚴(yán)格要求函數(shù)請求按序執(zhí)行，忽略了緩存機(jī)制和函數(shù)空間特性，效果均不理想.

Fig.3 Example of different algorithms圖3 不同算法的示例

3.3.5 函數(shù)執(zhí)行公平性

當(dāng)使用FuncSched 調(diào)度時(shí)，如果優(yōu)先級(jí)P[k]較高的函數(shù)請求不斷到達(dá)，可能會(huì)導(dǎo)致有些函數(shù)的饑餓.這是因?yàn)檎麄€(gè)服務(wù)器無感知計(jì)算平臺(tái)的資源可能會(huì)一直分配給不斷到達(dá)的函數(shù)高優(yōu)先級(jí)請求，而其他函數(shù)請求一直處于待執(zhí)行狀態(tài).

對(duì)于這種狀況，F(xiàn)uncSched 會(huì)維護(hù)一個(gè)更高的優(yōu)先級(jí)隊(duì)列Qstarve，并設(shè)置一個(gè)可調(diào)節(jié)的閾值StarveThreshold.當(dāng)一個(gè)函數(shù)請求的等待時(shí)間F[k]s-F[k]a>StarveThreshold時(shí)，該請求將會(huì)被調(diào)入Qstarve.在Qstarve中，所有函數(shù)請求按照等待時(shí)間從大到小排序，隊(duì)頭函數(shù)請求將被FuncSched 調(diào)度器最先執(zhí)行.當(dāng)Qstarve為空時(shí)，剩余函數(shù)請求再按照函數(shù)請求優(yōu)先級(jí)P[k]執(zhí)行.依靠這一機(jī)制，F(xiàn)uncSched 能夠避免低優(yōu)先級(jí)函數(shù)請求的饑餓情況.

3.3.6 FuncSched 調(diào)度性能優(yōu)化

每當(dāng)空閑可用的函數(shù)容器數(shù)W(j)發(fā)生變化時(shí)，調(diào)度器就需要對(duì)所有依賴該函數(shù)鏡像的函數(shù)請求更新其優(yōu)先級(jí)P[k]，并對(duì)這些函數(shù)請求進(jìn)行重排序.這有一定的調(diào)度開銷，尤其是在整個(gè)服務(wù)器無感知計(jì)算平臺(tái)負(fù)載很大的情況下.

針對(duì)這一問題，一個(gè)關(guān)鍵觀察是，對(duì)于同一函數(shù)，其所有待執(zhí)行的函數(shù)請求優(yōu)先級(jí)P(k)相同.因此，可以將這些函數(shù)請求按照依賴的函數(shù)鏡像聚合在一起，形成按照時(shí)間排序的函數(shù)請求列表,在Qstarve為空時(shí)，F(xiàn)uncSched 通過對(duì)聚合后的集合按照優(yōu)先級(jí)排序來進(jìn)行調(diào)度.微軟公司開源的服務(wù)器無感知計(jì)算平臺(tái)實(shí)際用戶函數(shù)執(zhí)行數(shù)據(jù)集Azure Functions顯示，大約20%的服務(wù)器無感知函數(shù)應(yīng)用產(chǎn)生了99.6%的函數(shù)請求[3]，所以待執(zhí)行的函數(shù)請求所屬的函數(shù)鏡像是有限的.通過聚合函數(shù)請求能進(jìn)一步降低函數(shù)請求的調(diào)度開銷.

4 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估所提調(diào)度算法的性能，本文基于真實(shí)世界服務(wù)器無感知計(jì)算負(fù)載數(shù)據(jù)集，進(jìn)行了一系列實(shí)驗(yàn).本節(jié)首先對(duì)實(shí)驗(yàn)中算法的實(shí)現(xiàn)進(jìn)行詳細(xì)說明，然后介紹實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集的選擇，最后展示實(shí)驗(yàn)結(jié)果并進(jìn)行深入分析.

4.1 調(diào)度算法實(shí)現(xiàn)

本文基于開源的OpenWhisk 服務(wù)器無感知計(jì)算框架實(shí)現(xiàn)了原型系統(tǒng).通過修改中央控制器和工作結(jié)點(diǎn)代碼，實(shí)現(xiàn)了所提的基于時(shí)空特征的函數(shù)調(diào)度算法FuncSched，其能夠兼容各種函數(shù)鏡像緩存策略.

在中央控制器端，實(shí)現(xiàn)了基于時(shí)空特征的優(yōu)先級(jí)調(diào)度器.當(dāng)調(diào)度器接收到任務(wù)時(shí)，它將任務(wù)插入一個(gè)優(yōu)先級(jí)隊(duì)列中.當(dāng)有空閑資源，包括空閑內(nèi)存或者空閑的熱容器時(shí)，調(diào)度器會(huì)從優(yōu)先級(jí)隊(duì)列中選取具有最高優(yōu)先級(jí)的任務(wù)，并將其下發(fā)到工作節(jié)點(diǎn)進(jìn)行執(zhí)行.為了配合優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)，實(shí)現(xiàn)了緩存容器統(tǒng)計(jì)組件以及函數(shù)冷啟動(dòng)和執(zhí)行時(shí)間測量統(tǒng)計(jì)組件，以支持優(yōu)先級(jí)的計(jì)算.

在工作節(jié)點(diǎn)端，在容器池的源代碼中復(fù)現(xiàn)了3 種現(xiàn)有函數(shù)鏡像緩存算法，分別是LRU 算法、Faas-Cache[4]的優(yōu)先級(jí)驅(qū)逐算法、Serverless in the Wild[3]的基于歷史統(tǒng)計(jì)的預(yù)熱和驅(qū)逐算法.為實(shí)現(xiàn)Serverless in the Wild 的預(yù)熱算法，修改了中央控制器與工作節(jié)點(diǎn)之間的通信機(jī)制，使系統(tǒng)能夠根據(jù)算法預(yù)測結(jié)果及時(shí)預(yù)熱和驅(qū)逐指定容器.

4.2 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文實(shí)驗(yàn)使用了一個(gè)由9 臺(tái)機(jī)器構(gòu)成的集群，其中1 臺(tái)機(jī)器用作控制節(jié)點(diǎn)，另外8 臺(tái)機(jī)器用作工作節(jié)點(diǎn).每臺(tái)機(jī)器都配置了Ubuntu 18.04 操作系統(tǒng)，并配備了硬件規(guī)格：1 個(gè)Xeon E5-2450 處理器（8 核，2.1 GHz）、16 GB 內(nèi)存（4×2 GB RDIMMs，1.6 GHz）、4 個(gè)500 GB 7.2K SATA 硬盤.通過Kubernetes 在這9 臺(tái)節(jié)點(diǎn)的集群上部署了OpenWhisk.

本文實(shí)驗(yàn)選取微軟Azure Functions 數(shù)據(jù)集[3]，該數(shù)據(jù)集為Azure Functions 服務(wù)器無感知計(jì)算平臺(tái)上的函數(shù)樣本，包含超過5 萬個(gè)函數(shù)，每個(gè)函數(shù)信息包含函數(shù)調(diào)用記錄、執(zhí)行時(shí)間和內(nèi)存占用大小.

為了評(píng)估所提調(diào)度算法在不同種類任務(wù)集上的性能，本文采取和文獻(xiàn)[4]相同的采樣方法，通過代表性函數(shù)采樣、少見函數(shù)采樣、隨機(jī)函數(shù)采樣3 種方法，采樣出具有不同降采樣比例的小樣本.每個(gè)小樣本集均包含200 個(gè)不同函數(shù)在5min 內(nèi)的數(shù)千次到數(shù)萬次調(diào)用.每個(gè)數(shù)據(jù)集分別選取從低到高多個(gè)不同的降采樣比例采樣，代表不同的負(fù)載量，以綜合評(píng)判測試算法在不同負(fù)載狀況下的性能.3 種采樣方法的具體采樣原理描述及其選取目標(biāo)為：

1）代表性函數(shù)采樣指以調(diào)用頻率為標(biāo)準(zhǔn)，從數(shù)據(jù)集中調(diào)用頻率分布的四分位分別進(jìn)行采樣，總計(jì)采樣出200 個(gè)函數(shù)樣本.這樣的數(shù)據(jù)集既能包含較少調(diào)用的函數(shù)，又能包含頻繁調(diào)用的函數(shù)，可以檢驗(yàn)算法在典型工作場景下的性能.

2）少見函數(shù)采樣指200 個(gè)最少調(diào)用的函數(shù)的隨機(jī)樣本，這樣的函數(shù)常常導(dǎo)致冷啟動(dòng)，可以檢驗(yàn)算法對(duì)冷啟動(dòng)的感知和利用.

3）隨機(jī)函數(shù)采樣指隨機(jī)采樣的200 個(gè)函數(shù)樣本.

每個(gè)樣本集在不同降采樣比例下的總函數(shù)調(diào)用次數(shù)和調(diào)用頻率如表2 所示.

Table 2 Total Invocation Amount and Frequency in Traces表2 樣本數(shù)據(jù)集中函數(shù)調(diào)用總次數(shù)和頻率

4.3 綜合性能實(shí)驗(yàn)與分析

本節(jié)說明評(píng)估FuncSched 算法綜合性能的實(shí)驗(yàn)指標(biāo)和對(duì)照組，展示實(shí)驗(yàn)結(jié)果并對(duì)所提算法在不同場景下的性能進(jìn)行分析.

采取平均函數(shù)完成時(shí)間作為性能指標(biāo).函數(shù)完成時(shí)間包括排隊(duì)時(shí)間、冷啟動(dòng)時(shí)間、執(zhí)行時(shí)間3部分.

在對(duì)照算法方面，實(shí)驗(yàn)選取OpenWhisk 默認(rèn)的FCFS 算法作為對(duì)照組.

綜合性能實(shí)驗(yàn)在代表性函數(shù)采樣、隨機(jī)函數(shù)采樣和少見函數(shù)采樣3 個(gè)數(shù)據(jù)集上進(jìn)行，計(jì)算了Func-Sched 調(diào)度算法在各參數(shù)下的平均完成時(shí)間加速比，即以對(duì)照算法的平均完成時(shí)間除以FuncSched 算法平均完成時(shí)間.在綜合性能的各項(xiàng)實(shí)驗(yàn)中，均采取了LRU 緩存策略作為函數(shù)鏡像緩存策略.

圖4 展示了綜合性能實(shí)驗(yàn)的結(jié)果.可以看到，在各個(gè)數(shù)據(jù)集上，F(xiàn)uncSched 均有高達(dá)2～6 倍的加速比.

Fig.4 Average completion time on different traces with LRU algorithm圖4 結(jié)合 LRU 算法在不同數(shù)據(jù)集上的平均完成時(shí)間

如圖4（a）所示，在代表性函數(shù)采樣數(shù)據(jù)集上，當(dāng)降采樣比例為0.6 時(shí)，可以取得2.7 倍的加速比.當(dāng)降采樣比例為0.7 時(shí)，加速比提升到3.3 倍.在典型場景下，F(xiàn)uncSched 能實(shí)現(xiàn)較高加速比，能夠大幅提升系統(tǒng)在大多數(shù)場景下的性能.

如圖4（b）所示，即使是在隨機(jī)函數(shù)采樣數(shù)據(jù)集上，系統(tǒng)也取得了高達(dá)2.2 倍的加速比.隨機(jī)函數(shù)采樣往往包含大量執(zhí)行時(shí)間和頻率均較短的函數(shù)，系統(tǒng)整體負(fù)載偏低，F(xiàn)uncSched 仍然能夠取得較大的性能提升，可見FuncSched 算法能夠普遍適用于服務(wù)器無感知計(jì)算的各個(gè)工作場景.

如圖4（c）所示，在少見函數(shù)采樣數(shù)據(jù)集上的加速比最為顯著.當(dāng)降采樣比例達(dá)到0.10 時(shí)，F(xiàn)uncSched能實(shí)現(xiàn)5 倍的加速比.當(dāng)降采樣比例達(dá)到0.20 時(shí)，加速比進(jìn)一步提高至6 倍.對(duì)于服務(wù)器無感知計(jì)算平臺(tái)，由于函數(shù)請求特征差別較大，大量函數(shù)請求只需消耗較少資源，少數(shù)函數(shù)請求消耗大量資源，冷啟動(dòng)時(shí)間較長.故能實(shí)現(xiàn)在該類少見函數(shù)采樣上的性能優(yōu)化，對(duì)于整體系統(tǒng)性能提升至關(guān)重要.

下面分析平均完成時(shí)間隨降采樣比例增加的變化趨勢.在圖4 中可以看到，隨著降采樣比例的增加，F(xiàn)uncSched 的平均完成時(shí)間僅緩慢增加.相比之下，F(xiàn)CFS 算法在超過一定降采樣比例后，平均完成時(shí)間迅速增加，使其性能顯著差于FuncSched.這在代表性函數(shù)采樣和少見函數(shù)采樣數(shù)據(jù)集上效果尤為明顯.在代表性函數(shù)采樣數(shù)據(jù)集上，當(dāng)降采樣比例為0.4 時(shí)2 種算法性能基本一致；當(dāng)降采樣比例為0.5 時(shí)FuncSched 開始優(yōu)于FCFS；當(dāng)降采樣比例達(dá)到0.6 時(shí)，F(xiàn)CFS 算法下的平均完成時(shí)間就已經(jīng)達(dá)到FuncSched算法的3 倍以上.同樣地，在少見函數(shù)采樣數(shù)據(jù)集中，降采樣比例為0.05 時(shí)，兩算法性能基本一致；當(dāng)降采樣比例達(dá)到0.10 時(shí)，F(xiàn)CFS 算法的平均完成時(shí)間達(dá)到FuncSched 算法的3 倍以上.故FuncSched 能夠承受遠(yuǎn)多于FCFS 算法負(fù)載，同時(shí)保持相對(duì)較低的平均完成時(shí)間.

為了進(jìn)一步對(duì)比FuncSched 和一些在操作系統(tǒng)等領(lǐng)域廣泛應(yīng)用的經(jīng)典調(diào)度算法的區(qū)別，本文在代表性函數(shù)采樣數(shù)據(jù)集上，分別采取不同參數(shù)進(jìn)行了實(shí)驗(yàn)，記錄了函數(shù)請求的平均完成時(shí)間.除了FCFS外，實(shí)驗(yàn)比較了其余3 種經(jīng)典調(diào)度算法.

1）時(shí)間片輪轉(zhuǎn)調(diào)度（round robin，RR）算法.這是任務(wù)調(diào)度系統(tǒng)常用的算法，每個(gè)任務(wù)每次被調(diào)度時(shí)獲得至多固定長度的時(shí)間片.本文實(shí)驗(yàn)選取的時(shí)間片為100 ms.

2）最短剩余時(shí)間優(yōu)先（shortest remaining time first，SRTF）算法.相比FuncSched 算法，SRTF 算法只考慮時(shí)間特征，不考慮空間特征.該算法每次調(diào)度剩余執(zhí)行時(shí)間最短的函數(shù)請求執(zhí)行，調(diào)度器在每個(gè)函數(shù)請求執(zhí)行至多100 ms 后決定是否搶占.

3）最小運(yùn)行時(shí)內(nèi)存優(yōu)先（smallest runtime memory first，SRF）算法.相比FuncSched 算法，SRF 算法只考慮空間特征，不考慮時(shí)間特征，每次調(diào)度選取占用內(nèi)存最小的函數(shù)請求.

圖5 展示了FuncSched 與這些經(jīng)典調(diào)度算法的實(shí)驗(yàn)對(duì)比結(jié)果.可以看出，由于函數(shù)冷啟動(dòng)開銷較大，帶有搶占的算法，即RR 算法和SRTF 算法，會(huì)因?yàn)轭l繁搶占帶來頻繁的冷啟動(dòng)開銷，性能差于Open-Whisk 原始的FCFS 算法.另外，只考慮空間特征的算法SRF 因?yàn)橹豢紤]了函數(shù)的單一維度特征，性能差于FuncSched 算法.故可以說明綜合考慮空間特征和時(shí)間特征能使得服務(wù)器無感知計(jì)算調(diào)度器獲得更優(yōu)的性能.

Fig.5 Average completion time of FuncSched and classical scheduling algorithms圖5 FuncSched 和經(jīng)典調(diào)度算法的平均完成時(shí)間

4.4 性能提升原因分析

本節(jié)通過分析平均完成時(shí)間的各個(gè)組成部分，分析FuncSched 算法相對(duì)于FCFS 算法得到大比例性能提升的原因.函數(shù)完成時(shí)間包括排隊(duì)時(shí)間、冷啟動(dòng)時(shí)間和執(zhí)行時(shí)間.由于對(duì)于同一個(gè)數(shù)據(jù)集的同一個(gè)降采樣比例，平均執(zhí)行時(shí)間相同，平均排隊(duì)時(shí)間和平均冷啟動(dòng)時(shí)間不同，故本節(jié)對(duì)后兩者進(jìn)行分析.

圖6 展示了FuncSched 和對(duì)照算法在不同緩存策略下平均排隊(duì)時(shí)間的對(duì)比.數(shù)據(jù)集選取為代表性函數(shù)采樣，降采樣比例為0.7.從平均排隊(duì)時(shí)間上看，在Serverless in the Wild 的緩存策略下，F(xiàn)uncSched 減少了92.5%的排隊(duì)時(shí)間，而在排隊(duì)時(shí)間最低的 LRU緩存策略下，F(xiàn)uncSched 也減少了83.9%的排隊(duì)時(shí)間.可見FuncSched 通過優(yōu)先調(diào)度執(zhí)行時(shí)間較短、內(nèi)存消耗較少的函數(shù)，顯著減少了函數(shù)請求的平均排隊(duì)時(shí)間.

Fig.6 Average queuing time of different policies圖6 不同策略的平均排隊(duì)時(shí)間

圖7 展示了FuncSched 和對(duì)照算法在不同緩存策略下平均冷啟動(dòng)時(shí)間的對(duì)比.數(shù)據(jù)集選取為代表性函數(shù)采樣，降采樣比例為0.7.平均冷啟動(dòng)時(shí)間減少了高達(dá)12.5%.在FuncSched 中仍存在的冷啟動(dòng)通常包括2 部分：一部分是因?yàn)檎{(diào)用十分稀少導(dǎo)致緩存性價(jià)比較低，故在調(diào)用時(shí)的冷啟動(dòng)是最佳選擇；另一部分是因?yàn)檎{(diào)用頻率很高，故需要維護(hù)大量容器盡快執(zhí)行該類函數(shù)的請求，以實(shí)現(xiàn)低服務(wù)延時(shí)，這些較大數(shù)量的容器初始化時(shí)就會(huì)有相應(yīng)的冷啟動(dòng)開銷也是不可避免的.故可知FuncSched 以降低平均任務(wù)完成時(shí)間為目標(biāo)，把冷啟動(dòng)時(shí)間考慮在優(yōu)先級(jí)內(nèi)，優(yōu)先執(zhí)行熱啟動(dòng)函數(shù)，從而減少冷啟動(dòng)發(fā)生率，使得冷啟動(dòng)時(shí)間幾乎減少到最低值.

Fig.7 Average cold start time of different policies圖7 不同策略的平均冷啟動(dòng)時(shí)間

4.5 函數(shù)完成時(shí)間分布

為了展現(xiàn)FuncSched 對(duì)于系統(tǒng)中單個(gè)函數(shù)的性能提升情況，實(shí)驗(yàn)統(tǒng)計(jì)了所有函數(shù)每次調(diào)用的完成時(shí)間.圖8 展示了函數(shù)完成時(shí)間的累計(jì)分布函數(shù)圖.這是在代表性函數(shù)采樣數(shù)據(jù)集、降采樣比例為0.7 下的實(shí)驗(yàn)結(jié)果.可以看出，F(xiàn)CFS 算法有大量函數(shù)完成時(shí)間顯著高于FuncSched 算法.FCFS 算法有25.9%的函數(shù)完成時(shí)間超過100 s，大量函數(shù)請求經(jīng)歷高完成延遲.相比之下，F(xiàn)uncSched 完成時(shí)間超過100 s 的只有5.2%，保持了較高的響應(yīng)速度.這表明FuncSched相對(duì)于原始OpenWhisk 在性能方面對(duì)于大部分函數(shù)都能使其性能明顯提升.

Fig.8 Function completion time CDF圖8 函數(shù)完成時(shí)間累積分布函數(shù)

服務(wù)器無感知計(jì)算的函數(shù)請求有時(shí)存在服務(wù)級(jí)別目標(biāo)（service level objective,SLO），常見的例如延遲目標(biāo).圖9 展示了FCFS 算法和FuncSched 算法在不同SLO 下的任務(wù)完成率，F(xiàn)uncSched 算法能夠?qū)⑷蝿?wù)完成率提高27%～41%.由此可見，F(xiàn)uncSched 可以提升函數(shù)整體SLO 達(dá)成率，不會(huì)導(dǎo)致運(yùn)行時(shí)間較長的函數(shù)過多違背SLO.

Fig.9 Function finish rate under SLO圖9 函數(shù)的 SLO 達(dá)成率

4.6 緩存策略兼容性

FuncSched 能夠兼容不同的函數(shù)鏡像緩存策略.在各個(gè)函數(shù)鏡像緩存策略下，F(xiàn)uncSched 相較于FCFS都能大幅減少函數(shù)請求的平均完成時(shí)間.為了驗(yàn)證這一點(diǎn)，本文在3 個(gè)數(shù)據(jù)集上進(jìn)行了一系列實(shí)驗(yàn)，將FuncSched 和FCFS 與LRU,FaasCache 和Serverless in the Wild 這3 種函數(shù)鏡像緩存策略相結(jié)合，并分別測量了平均完成時(shí)間.實(shí)驗(yàn)在代表性函數(shù)采樣數(shù)據(jù)集上進(jìn)行.

圖10 展示了在3 個(gè)數(shù)據(jù)集上，F(xiàn)uncSched 和FCFS采用不同緩存策略以及不同降采樣比例下的平均任務(wù)完成時(shí)間.在3 種緩存策略下，F(xiàn)uncSched 相較于FCFS 均有高達(dá)4～5 倍的加速比.在平均完成時(shí)間的絕對(duì)值上，當(dāng)降采樣比例不高于0.7 時(shí)，F(xiàn)uncSched 都能將平均完成時(shí)間保持在15 s 以內(nèi)，而FCFS 的平均完成時(shí)間會(huì)迅速上升至60 s 以上.實(shí)驗(yàn)結(jié)果表明Func-Sched 能夠兼容各種函數(shù)鏡像緩存策略，并能顯著降低函數(shù)平均完成時(shí)間.

Fig.10 Average completion time under different cache policies圖10 不同緩存策略下的平均完成時(shí)間

5 總結(jié)

本文研究了服務(wù)器無感知計(jì)算場景下的函數(shù)調(diào)度問題.通過對(duì)服務(wù)器無感知計(jì)算場景的分析和數(shù)學(xué)建模，提出了基于函數(shù)時(shí)空特征的服務(wù)器無感知計(jì)算函數(shù)調(diào)度算法FuncSched.FuncSched 通過分析函數(shù)的時(shí)間特征和空間特征，并且綜合考慮函數(shù)自身邏輯和服務(wù)器無感知計(jì)算平臺(tái)函數(shù)鏡像緩存機(jī)制的影響，實(shí)現(xiàn)了對(duì)函數(shù)性能的精準(zhǔn)評(píng)估.基于函數(shù)的時(shí)空特征，F(xiàn)uncSched 通過調(diào)度算法避免了函數(shù)請求的隊(duì)頭阻塞現(xiàn)象，進(jìn)而降低了平均函數(shù)完成時(shí)間.針對(duì)FunSched 原型系統(tǒng)的實(shí)驗(yàn)結(jié)果表明，F(xiàn)uncSched 能夠在各種函數(shù)請求場景中顯著降低平均函數(shù)完成時(shí)間，并且兼容各種服務(wù)器無感知計(jì)算函數(shù)鏡像緩存算法.

未來的工作包括3 個(gè)方面：1）考慮將函數(shù)運(yùn)行的生命周期分為函數(shù)拉取和函數(shù)執(zhí)行等多階段進(jìn)行異步調(diào)度，并考慮預(yù)測函數(shù)調(diào)用時(shí)間并預(yù)先異步拉取函數(shù)鏡像等機(jī)制和更細(xì)粒度的并發(fā)影響[43]；2）研究本地函數(shù)鏡像緩存的預(yù)取策略，將預(yù)取策略與調(diào)度算法進(jìn)行協(xié)同設(shè)計(jì)，進(jìn)一步優(yōu)化函數(shù)完成時(shí)間；3）將函數(shù)調(diào)度擴(kuò)展到函數(shù)工作流，根據(jù)函數(shù)工作流的函數(shù)依賴關(guān)系，設(shè)計(jì)面向函數(shù)工作流的函數(shù)調(diào)度算法，優(yōu)化函數(shù)工作流完成時(shí)間.

作者貢獻(xiàn)聲明：金鑫提出研究思路和算法設(shè)計(jì)；吳秉陽、劉方岳和章梓立負(fù)責(zé)實(shí)驗(yàn)設(shè)計(jì)和完成實(shí)驗(yàn)；賈云杉負(fù)責(zé)文獻(xiàn)調(diào)研；所有作者都參與了文章撰寫和修改.