關(guān)聯(lián)比賽:??首屆云原生編程挑戰(zhàn)賽【復賽】實現(xiàn)一個 Serverless 計算服務調(diào)度系統(tǒng)

比賽攻略—ONE PIECE團隊

代碼鏈接：

初賽：https://github.com/czy-gm/containerScheduler

復賽：https://github.com/czy-gm/serverlessScheduler

初賽（賽道二，語言Java）

1 賽題背景分析及理解

1.1賽題介紹

實現(xiàn)規(guī)?；萜黛o態(tài)布局和動態(tài)遷移：

1）規(guī)模化容器靜態(tài)布局場景。我們準備了確定數(shù)量多規(guī)格機器資源，使得在滿足調(diào)度約束條件下，確定數(shù)量、多種類的應用容器能在這些機器資源上滿足擴容訴求，保證建站的確定性(賽題中我們會給出充足的機器，但真正建站場景我們會先通過計算預估機器)。

2）規(guī)?；萜鲃討B(tài)遷移場景。我們會準備一個集群容器靜態(tài)布局數(shù)據(jù)，此時集群是一種碎片態(tài)。然后通過容器的遷移，按照規(guī)則要求盡可能騰空機器資源，并過濾空機器，使得碎片態(tài)集群現(xiàn)狀重新成為飽滿態(tài)。

1.2賽題分析

靜態(tài)布局問題可以理解為多約束的多維裝箱問題，約束有資源、綁核、堆疊和打散，約束條件多，判斷約束條件的時間較長。

考慮在三個方面著手：

減少判斷約束條件的時間，以擴大搜索解空間的范圍

選擇一個好的初始解，解空間很大，在比賽給出的時間內(nèi)能搜索的范圍很小，這時好的初始解很重要。

node的選擇，對于不同規(guī)格的容器，node的選擇順序決定了node資源的使用情況。

動態(tài)遷移問題可以從兩個思路解決：

先將所有容器按照靜態(tài)布局的方案進行放置，再通過前后位置的差異進行遷移

使用策略判斷是否需要遷移，逐漸減少node的使用數(shù)

綜上，初賽考察的是復雜的裝箱問題，在有限的時間內(nèi)找到較優(yōu)解，動態(tài)遷移使用較少的遷移次數(shù)達到飽和態(tài)。

2 核心思路

靜態(tài)布局考慮了兩個方案，一是使用模擬退火，二是模擬退火+局部DP。因為使用模擬退火時，后面的node資源利用率較差，可以用DP來改進這一缺陷。首先先試驗使用DP能夠跑多大的數(shù)據(jù)規(guī)模，每次判斷約束條件的時間大約在500ms，在調(diào)整數(shù)據(jù)結(jié)構(gòu)后，時間降低至200~300ms，但DP也只能跑幾個node，無法配合模擬退火。

最終方案主體采用模擬退火，pods根據(jù)cpu/ram從小到大排序，nodes根據(jù)與pod的資源不匹配分數(shù)從小到大排序。

動態(tài)遷移先將不滿足約束的pod進行遷移，然后采用靜態(tài)布局的方法將每個pod重新放置，根據(jù)布局前后的位置不同決定是否需要遷移。不采取任何優(yōu)化時，遷移次數(shù)在8000-8300?？紤]到靜態(tài)布局后，PodA的原node可能存在同規(guī)格的PodB，可以交換兩者位置，PodA就不用遷移，經(jīng)過優(yōu)化后遷移次數(shù)在4000~4200。

優(yōu)化策略如圖所示：

圖1 優(yōu)化前（PodA和PodB都需要遷移）

圖2 優(yōu)化后（PodA和PodB交換位置，PodA不需要遷移）

在遷移過程中，可能存在死鎖情況，都在等待對方遷移空出位置，需要跳轉(zhuǎn)到中轉(zhuǎn)node解除死鎖。方案如圖所示：

圖3 優(yōu)化前（PodA和PodB形成死鎖）

圖4 優(yōu)化后（根據(jù)遷移順序，解除死鎖）

復賽（語言Golang）

3 賽題背景分析及理解

3.1賽題介紹

一個簡化的Faas系統(tǒng)分為APIServer，Scheduler，ResourceManager，NodeService，ContainerService 5個組件，本題目中APIServer，ResourceManager，NodeService，ContainerService由平臺提供，Scheduler的AcquireContainer和ReturnContainer API由選手實現(xiàn)（gRPC服務，語言不限），Scheduler會以容器方式單實例運行，無需考慮分布式多實例問題。

其中測試函數(shù)由平臺提供，可能包含但不局限于helloworld，CPU intensive，內(nèi)存intensive，sleep等類型；調(diào)用模式包括稀疏調(diào)用，密集調(diào)用，周期調(diào)用等；執(zhí)行時間包括時長基本固定，和因輸入而異等。

選手對函數(shù)的實現(xiàn)無感知，可以通過Scheduler的AcquireContainer和ReturnContainer API的調(diào)用情況，以及NodeService.GetStats API獲得一些信息，用于設計和實現(xiàn)調(diào)度策略。

3.2賽題分析

賽題需要完成AcquireContainer和ReturnContainer兩個接口，根據(jù)請求函數(shù)分配相應的node和container，主要考察node的資源分配，以及請求的響應時間。

評分從兩個方面，總的響應時間RT和資源使用時間ND，兩者的權(quán)重都是0.5，分數(shù)是與基準分相比得出的，所以基準的實現(xiàn)策略對選手的策略有很大影響。

node的初始可用數(shù)只有10個，需要過一段時間才可以申請新的node，總的可用node數(shù)為20個。要規(guī)劃好node的資源分配，避免前期請求申請超過初始node時出錯，造成懲罰性分數(shù)。

內(nèi)存密集型函數(shù)占用內(nèi)存較大，同一container同時運行多個實例，可能會導致OOM，cpu密集型函數(shù)也盡量避免同一container運行多個實例，可能會造成超時，這兩種情況也會有懲罰性分數(shù)。

有些函數(shù)（如helloworld、sleep等）占用資源很小，同一container同時運行多個實例，響應時間變化不大，可以減少創(chuàng)建容器的時間。

4 核心思路

由于賽題使用grpc，不限制語言的使用，對于比拼速度的比賽，語言的選擇也是考慮的一方面，分別嘗試使用c++，java，golang三種語言實現(xiàn)demo，經(jīng)測試發(fā)現(xiàn)，c++與golang的速度差不多，java要比其他兩個慢10%~20%。Golang對于并發(fā)開發(fā)具有天生的優(yōu)勢，再加上官方提供了demo，所以最終選擇了golang作為開發(fā)語言。

官方前期沒有提供評測系統(tǒng)，每次提交系統(tǒng)需要等待1到3小時才能得到結(jié)果，等待結(jié)果的同時并不能并行開發(fā)，效率極低。通過線上跑出的日志，自己使用java實現(xiàn)了一個評測demo，每個函數(shù)的調(diào)用頻率、調(diào)用時間、首次調(diào)用時間都可以通過日志分析出。由于無法模擬真實環(huán)境，所以NodeService只是實現(xiàn)基本功能，無法根據(jù)負載情況做出相應的執(zhí)行時間。評測demo可以檢驗程序的正確性，以及資源的使用情況，避免了線上等待很久才發(fā)現(xiàn)出錯的情況，提升了開發(fā)效率。

程序的整體策略就是負載均衡和動態(tài)擴縮，負載均衡提升響應速度，動態(tài)擴縮應對調(diào)用壓力的變化以及不同數(shù)據(jù)，避免出現(xiàn)大規(guī)模的調(diào)用失敗的情況。分別從以下幾點著手：

選取node的策略

如果當前請求函數(shù)的并發(fā)數(shù)大于現(xiàn)有的node數(shù)，且現(xiàn)有node不超過初始node數(shù)量（設定10個node），則獲取新的node創(chuàng)建容器，目的是充分利用前期僅能獲取的初始node，讓每個node響應較少的請求，可以更快的創(chuàng)建容器以及更快的響應速度。

使函數(shù)均勻分布在每個node，首先按照node內(nèi)該函數(shù)容器數(shù)量排序，優(yōu)先數(shù)量少的node，如果數(shù)量相同，優(yōu)先可用內(nèi)存多的node。目的是資源分配更加平均，避免資源搶占。

當初始node數(shù)不能再滿足新的請求時，申請新的node，滿足高壓力的請求。

選取container的策略

當容器數(shù)大于等于請求數(shù)，每個容器同時滿足一個請求。如果容器數(shù)不夠，則創(chuàng)建新的容器。

如果該函數(shù)（不包括內(nèi)存密集型和cpu密集型）當前不能再創(chuàng)建容器，則每個容器同時滿足多個請求。

函數(shù)分類

當使用內(nèi)存高于分配內(nèi)存的30%時，判定為內(nèi)存密集型函數(shù)。

當cpu使用率大于10%時，判定為cpu密集型函數(shù)。

當函數(shù)執(zhí)行時間小于50ms時，判定為短時間型函數(shù)，若再超過65ms的上限，取消判定為短時間型函數(shù)。

動態(tài)縮減

根據(jù)cpu密集型容器的數(shù)量，初步判斷可以縮減的node數(shù)量，判斷依據(jù)是縮減后每個node內(nèi)cpu密集型容器的數(shù)量不超過一定值（更優(yōu)的方案是根據(jù)cpu負載情況判斷數(shù)量），防止cpu資源緊張，響應時間過長。

選擇使用內(nèi)存最少的node，先校驗是否滿足遷移條件。遷移條件是剩余node的可用內(nèi)存是否滿足該node所有容器的需求，重點是內(nèi)存密集型函數(shù)。

當滿足遷移條件后，將該node的所有容器遷移到其他node，然后釋放該node。當縮減數(shù)量達到預判值或者不再滿足遷移條件，則停止該輪縮減。

回收資源

部分函數(shù)可能會從密集調(diào)用變?yōu)橄∈枵{(diào)用，或者調(diào)用一段時間后就不再調(diào)用，這樣會導致一些空閑容器，導致資源浪費（尤其是內(nèi)存密集型會一直占用內(nèi)存）。所以，當容器超過一定時間（設5分鐘）沒有執(zhí)行函數(shù)時，則釋放該容器。若node中沒有容器，則釋放該node。

根據(jù)以上幾個策略，程序沒有設定最終使用的node數(shù)，會根據(jù)實時壓力動態(tài)擴縮。程序每次分配node，都是根據(jù)node的可用內(nèi)存和函數(shù)的分配內(nèi)存進行選擇，并且內(nèi)存密集型容器只會同時執(zhí)行一個請求，避免發(fā)生OOM。cpu密集型容器只會同時執(zhí)行一個請求，避免出現(xiàn)執(zhí)行超時的情況。

根據(jù)基準分來看，RT相對與ND優(yōu)化空間更大，所以重點優(yōu)化響應時間，根據(jù)函數(shù)的分類指定多種策略：

函數(shù)執(zhí)行優(yōu)先級

函數(shù)：短時間型、cpu密集型（非短時間）、內(nèi)存密集型（非短時間）

分析：cpu密集型和內(nèi)存密集型函數(shù)一般執(zhí)行時間較長，占用資源較多，與短時間型同時執(zhí)行時，會存在資源競爭，導致短時間型執(zhí)行時間增加至兩到三倍。

策略：短時間型優(yōu)先級比cpu密集型和內(nèi)存密集型高，當短時間型正在執(zhí)行時，cpu密集型和內(nèi)存密集型等待其執(zhí)行完畢或者等待超時。由于cpu密集型和內(nèi)存密集型執(zhí)行時間較長，等待的時間對其影響不大。

預留容器

函數(shù)：所有函數(shù)

分析：創(chuàng)建容器的時間在0.4~1.0s，大大增加了請求的響應時間，要盡量避免在請求到來時創(chuàng)建容器。部分函數(shù)由稀疏調(diào)用逐漸變?yōu)槊芗{(diào)用，可以在空閑時間提前創(chuàng)建容器。

策略：當某函數(shù)的容器滿載時，則提前申請一個空閑容器，之后并發(fā)請求數(shù)增加時，省去創(chuàng)建容器的時間，減少了響應時間。

資源調(diào)整

函數(shù)：cpu密集型

分析：容器規(guī)格是由內(nèi)存決定的，cpu和內(nèi)存成比例，每1GB內(nèi)存對應0.67cpu。cpu密集型執(zhí)行時，可能存在cpu滿載的情況，執(zhí)行時間受資源限制不能再減少。

策略：當函數(shù)執(zhí)行時cpu使用率高于分配的90%，則認為當前分配的cpu資源不足，先創(chuàng)建新容器再刪除舊容器，新容器分配的內(nèi)存是舊容器的200%，對應的cpu資源也是200%，減少函數(shù)的執(zhí)行時間。

5 比賽經(jīng)驗總結(jié)和感想

初賽動態(tài)遷移部分，一開始選擇直接遷移這個方案，簡單實現(xiàn)后發(fā)現(xiàn)并不理想，然后就放棄了，賽后才發(fā)現(xiàn)這個方案要更優(yōu)，應該多做一些嘗試。在比賽中，學到了很多東西，也結(jié)識了很多大佬，感謝官方舉辦這次比賽。