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

（北京大學計算機學院 北京 100871）

（高可信軟件技術教育部重點實驗室（北京大學） 北京 100871）

（xinjinpku@pku.edu.cn）

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

1.2 任務調度

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

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

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

2 問題定義和建模

2.1 問題分析

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

Fig.1 Architecture overview圖1 架構概覽

2.2 問題建模

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

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

Table 1 Symbol Table表1 符號表

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

2.3 問題定義

對于第k個函數請求，如果要調度該函數到函數服務器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)化的目標是所有函數請求的平均完成時間，那么目標函數歸約為：

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

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

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

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

綜上所述，該問題的數學模型為：

目標函數：

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

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

3 服務器無感知計算調度算法

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

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

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

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

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

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

3.2 現有服務器無感知計算調度的局限性

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

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

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

3.3 基于時空特征的函數調度算法FuncSched

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

3.3.1 函數時間特征估測

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

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

3.3.2 函數空間特征估測

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

3.3.3 FuncSched 調度算法整體流程

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

基于這一優(yōu)先級P[k]，FuncSched 將優(yōu)先調度P[k]最小的函數請求.

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

算法1.基于時間感知的函數調度算法.

3.3.4 調度示例

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

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

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

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

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

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

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

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

4 實驗結果與分析

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

4.1 調度算法實現

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

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

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

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

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

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

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

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

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

3）隨機函數采樣指隨機采樣的200 個函數樣本.

每個樣本集在不同降采樣比例下的總函數調用次數和調用頻率如表2 所示.

Table 2 Total Invocation Amount and Frequency in Traces表2 樣本數據集中函數調用總次數和頻率

4.3 綜合性能實驗與分析

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

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

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

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

圖4 展示了綜合性能實驗的結果.可以看到，在各個數據集上，FuncSched 均有高達2～6 倍的加速比.

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

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

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

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

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

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

1）時間片輪轉調度（round robin，RR）算法.這是任務調度系統常用的算法，每個任務每次被調度時獲得至多固定長度的時間片.本文實驗選取的時間片為100 ms.

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

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

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

Fig.5 Average completion time of FuncSched and classical scheduling algorithms圖5 FuncSched 和經典調度算法的平均完成時間

4.4 性能提升原因分析

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

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

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

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

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

4.5 函數完成時間分布

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

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

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

Fig.9 Function finish rate under SLO圖9 函數的 SLO 達成率

4.6 緩存策略兼容性

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

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

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

5 總結

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

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

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