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

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

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

（xinjinpku@pku.edu.cn）

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

2 問題定義和建模

2.1 問題分析

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

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

2.2 問題建模

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

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

Table 1 Symbol Table表1 符號表

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

2.3 問題定義

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

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

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

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

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

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

目標函數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.4 調(diào)度示例

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

每個樣本集在不同降采樣比例下的總函數(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 綜合性能實驗與分析

本節(jié)說明評估FuncSched 算法綜合性能的實驗指標和對照組，展示實驗結(jié)果并對所提算法在不同場景下的性能進行分析.

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

在對照算法方面，實驗選取OpenWhisk 默認的FCFS 算法作為對照組.

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 性能提升原因分析

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

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

Fig.6 Average queuing time of different policies圖6 不同策略的平均排隊時間

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

Fig.7 Average cold start time of different policies圖7 不同策略的平均冷啟動時間

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

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

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

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

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

4.6 緩存策略兼容性

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

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

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

5 總結(jié)

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

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

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