獲國際架構頂會ATC2021最佳論文！Fuxi2.0去中心化的調度架構詳解

簡介： 近日，在國際體系架構頂會USENIX ATC2021上，阿里云飛天伏羲團隊與香港中文大學合作的一篇論文《Scaling Large Production Clusters with Partitioned Synchronization》不僅成功被大會錄取，而且被大會專家組評定為三篇最佳論文之一（Best Paper Award），

作者 | 馮亦揮、劉智、趙蘊健、金曉月、吳一迪、張楊、鄭尚策、李超、關濤
來源 | 阿里技術公眾號

引言

近日，在國際體系架構頂會USENIX ATC2021上，阿里云飛天伏羲團隊與香港中文大學合作的一篇論文《Scaling Large Production Clusters with Partitioned Synchronization》不僅成功被大會錄取，而且被大會專家組評定為三篇最佳論文之一（Best Paper Award），

ATC在計算機系統領域極具影響力，自1992年至今，ATC已成功舉辦31屆，吸引了普林斯頓、斯坦福、加州大學伯克利分校、康奈爾、中國清華大學、北京大學等頂級名校，以及微軟、英特爾、三星等科技巨頭發布研究成果，ATC 對論文要求極高，必須滿足基礎性貢獻、前瞻性影響和堅實系統實作的要求，2021 USENIX組委會錄用64篇（錄取率為18%），全球僅選取3篇最佳論文（其他兩篇來自Stanford University和Columbia University），這也是ATC最佳論文首次出現中國公司的身影，

本次大會上，我們詳細介紹了Fuxi 2.0專案的最新成果，超大規模分布式集群去中心化的調度架構，首次向外界披露了阿里云在超大規模集群調度上的實作細節，也是飛天作業系統核心能力的又一次成功展現，

一 論文背景

AI/大資料計算場景，隨著計算需求的快速增長，云計算集群突破單集群萬臺規模（一個集群可能有10萬臺機器，每天執行數十億個任務，特別是短時任務），以實作高利用率低成本的附加值，具有重要意義，資源調度器作為大型生產集群的核心組件，它負責將集群內的多維度資源請求與機器資源進行高效匹配，而集群規模的增長，意味著有更高的并發請求，產生”乘積“效應，使調度復雜度急劇增加，因此，如何實作集群規模的可擴展，在保持良好的調度效果的同時，做到高并發、低延時，是業內公認的非常艱巨的任務，傳統的中心調度器，受限于單點調度能力，大多數無法處理生產級別的規模，也無法保證穩定性和健壯性，做到升級程序對用戶透明，

二 現狀分析

1 作業負載

在阿里巴巴，單個計算集群每天運行著數百萬的作業，圖1a（實心曲線）繪制了一個集群某個月份內每天隨機處理的作業數，334萬至436萬，而一個作業由許多任務組成，圖1a（虛線）顯示每天的任務數量大概為從31億到44億，其中大部分任務都是短時任務，如圖1b所示，87%的任務在10秒內完成，大規模集群的調度負載還是非常大的，

2 調度架構升級的必要性

在Fuxi1.0，調度器遵循典型的master-worker架構，FuxiMaster負責管理并調度集群中的所有資源，同時每臺機器上有一個agent，Tubo，定期通過心跳訊息向FuxiMaster同步狀態，用戶提交的每個作業都有其所在的quota組的資訊，quota組能使用資源的最大最小值由SRE設定，我們的quota機制既能在集群高負載時保證各個quota組之間的公平性，也能在集群相對較閑時，削峰填谷，讓集群資源被充分使用，

近年來，計算集群的規模在顯著地增長，在可預見的將來，集群規模很可能突破十萬臺，面對超大規模集群，一種方法是將集群靜態切分為幾個小集群，但該方法有著明顯的局限性，首先，一些超大規模作業的資源需求可能就超過上述單個集群的規模；其次，集群的切分也會帶來資源碎片問題，區域視圖無法保證全域調度結果的最優；最后是其他非技術的因素，比如project之間存在依賴關系，同一業務部門的不同project需要互相訪問資料，將它們部署在同一個集群（而不是拆分成一個個小集群）會大大降低運維和管理的代價，

但單master架構無法處理十萬級別的集群規模，主要有兩方面原因：1）隨著集群規模的擴大，受限于單調度器處理能力的上限，master和worker之間的心跳延時會增加，調度資訊不能及時下發，導致集群利用率下降；2）規模的提升意味著更高的任務并發度，使調度復雜度急劇增加，最終超過單調度器的處理能力，

3 調度的目標和挑戰

除了規模可擴展性上的挑戰，調度器還應在以下多個調度目標間進行權衡，我們關注的目標主要包括：

• 調度效率（或者延時），即一個任務需要在資源上等待多長時間，一個好的調度器應該讓資源快速流轉，
• 調度質量，資源的約束是否都被滿足，比如data locality，更大體積的記憶體，更快的CPU型號等，
• 公平性和優先級，在多租戶共享的生產環境，需要保證租戶間資源使用的公平性，同時提供高優先級作業的保障機制，
• 資源利用率，一個極其重要的目標，集群利用率低會面臨很多挑戰，尤其是財務上的挑戰，

但上述幾個目標之間通常是互相沖突的，比如，更好的調度效果往往意味更長的調度延時，絕對的公平性有時會導致資源未能被充分使用，從而導致集群利用率下降，

經過十幾年的積累，伏羲的資源調度器通過各種策略在上述幾大目標間實作了很好的權衡，但考慮資源調度周邊還有其他兄弟團隊開發的應用組件，我們在設計新的調度器時，也應該做到盡量少改動，以保持系統的健壯性和向前兼容性，調度器架構調整引入的系統升級應該對用戶是透明的，不管是內部用戶還是外部用戶，

三 理論概述

針對調度器的規模可擴展問題，我們對業內現有的調度模型做了廣泛的調研（詳見論文），并選取了其中一個最適合我們場景的方案（Omega）進行進一步的分析，以Omega為代表的shared-state的多調度器架構能滿足我們之前說的那兩個約束條件，向后兼容和對用戶透明，但是share-state方案不可避免的會帶來調度沖突，我們希望能清楚如下幾個問題：

1. 有哪些因素會影響沖突，它們各自的權重是多少？
2. 調度延遲會惡化到什么程度？
3. 如何才能夠避免或級訓沖突？

我們首先對沖突進行建模，得出沖突(Conflict)的期望為(推導程序詳見論文)：

在上述公式中，Yi是多調度器在某個slot上沖突的期望， N是調度器的數量，K是單個調度器的處理能力，S是機器可調度的槽位數，可見，如果想減少沖突的概率，可以通過增加S或者N來實作，增加S是一種很符合直覺的方式，通過額外的資源供給來降低沖突概率，增加N的方式有些反直覺，因為調度器越多，越容易增加沖突，然而雖然在一輪調度程序中沖突變多了，但每個調度器一開始分到的task調度壓力也等比例地減小了，所以就有了更多的時間來解決沖突，最終反而起到了降低沖突概率的效果，總結起來，增加N是在整體壓力不變的情況下，通過降低每個調度器的調度壓力來實作沖突的減少的，

此外我們也通過公式證明了，在調度器數量>1的情況下，無法徹底消除沖突，

下面的實驗反映了不同的沖突因素對沖突的影響：

• 圖a考量的是任務壓力變化對沖突產生的影響，R表示調度器收到的task速率，可以看到在調度器數量相同的情況下，隨著R的增大，為了保持沖突數量不發生明顯的變化，需要額外補充的slot數目就越多；反過來，在R不變的情況下，隨著調度器數量的增加，每個調度器承受的調度壓力下降，需要額外補充的slot數目就越少，
• 圖b反映的是資源視圖同步頻率變化對沖突的影響，G表示同步的延遲，可以看到在調度器數量相同的情況下，隨著G的增大，為了保持沖突數量不發生明顯的變化，需要額外補充的slot數目就越多；反過來，在G不變的情況下，隨著調度器數量的增加，每個調度器承受的調度壓力下降，需要額外補充的slot數目就越少，
• 圖c反映的是機器分數(比如更好的硬體性能)對沖突的影響，V表示機器分數的方差，可以看到在調度器數量相同的情況下，隨著V的增大，為了保持沖突不發生明顯的變化，需要額外補充的slot數目就越多；反過來，在V不變的情況下，隨著調度器數量的增加，每個調度器承受的調度壓力下降，需要額外補充的slot數目就越少，
• 圖d反映的是機器partition數量對沖突的影響，可以看到這個因素對沖突幾乎沒有影響，因為不管機器partition的數量是多少，調度器總是以自己內部的視圖狀態進行調度，即使有些視圖的狀態已經不夠新了，所以partition數量并不會對沖突產生明顯的影響，

由以上分析不難發現，在shared-state架構下，如果我們想盡可能的降低沖突，可以采取增加額外資源或者增加調度器數量的方式來降低沖突，但在實際的生產環境中，增加額外資源是不可能的，一方面是集群大小是相對固定的，此外新引入slot也會大幅增加集群的成本；而增加調度器則會顯著帶來維護\升級的代價，

四 方案實作

由于我們的目標是為了減少沖突，所以我們先簡單介紹下一種能夠完全消除沖突的策略，悲觀鎖策略，悲觀鎖策略是每個調度器能夠調度的機器是“靜態排他\靜態劃分”的，這樣顯然能夠消除沖突，但是對利用率是非常不利的，因為會產生資源浪費（其他調度器本來可以調度），還有一種策略是通過類似于zookeeper等組件實作的基于鎖搶占的調度策略，當一批機器被某一個調度器鎖住時，其他機器是由于拿不到機器鎖從而暫時無法調度，當持鎖的調度器放鎖時，其他調度器可以通過鎖競爭來嘗試進行調度，但是在大規模高并發的調度場景下，這種高頻的互動會對調度效率產生很大的負作用，

由前面的分析可以知道，降低資源同步的延遲能夠有效降低沖突，由此我們提出了一種基于“磁區同步”（下稱ParSync）的策略：首先將集群的機器分為P個partition，同時要求P>N，通過round robin策略，每個調度器在同一個時刻去同步不同partition的資源視圖，這樣做能夠保證在每個round內每個調度器都能夠更新完所有partition的資源，而P>N保證了同一時刻不同的調度器不會同步相同的patition資源，

根據前文所述，在大規模高并發的調度場景下，調度器最優先的目標往往不是locality prefer而是speed prefer，所以調度器會優先在最新同步的partition機器內進行資源調度，在該策略下多調度器間是不會產生資源沖突的，ParSync其實是變相降低了每個patition對其當前同步調度器的同步延遲，因為站在當前更新的調度器的視角，這個partiton的同步延遲其實是低于其他未同步的調度器的，這也是能夠有效降低沖突的理論原因，

我們提供三種調度策略：latency-first， quality-first， adaptive，latency-first是在優先在最新的partition上調度資源， quality-first是優先在score最好的機器上調度資源，而adaptvie是先采取quality-first的調度策略，當資源等待時間超過閾值時再采取latency-first的策略，我們通過一組實驗來驗證3種調度策略的調度效果：我們將調度器分為2類，A\B類調度器在階段1都收到自身調度能力的2/3調度請求；階段2，A類調度器收到等同于自身調度能力的調度請求，而B類調度器不變；階段3，A\B類調度器都收到等同于自身調度能力的調度請求，

• 從(a)(b)可以看出，在階段1\2\3, 調度quality的表現都是很好的，但是在階段2\3隨著調度壓力的增加，調度latency出現了直線上升的情況，這是符合直覺預期的，
• 從(c)(d)可以看到，在階段1調度器壓力只有2/3的時候，調度latency和quality都是表現比較好的，隨著調度壓力的增加，quality質量開始出現了下降，但是latency的增加卻非常有限，這也符合直覺預期，
• 從(e)(f)可以看到，在階段2，由于B類調度器的調度壓力仍只有2/3，所以還停留在quality-first策略，而A類調度器由于調度latency的增加進入到了latency-first策略，通過仔細觀察可以看到在quality的圖里B類調度器的quality質量(淺灰色)是優于latency-first策略的，在階段3，A\B類調度器同時將調度latency約束在了門限值(1.5s)，符合設計預期，

五 實驗分析

我們通過“風洞”系統來驗證整個調度框架，在風洞環境下，除了調度器是真實的，單機節點和am都是程式模擬出來的，它們和調度器進行真實的資源互動，通過sleep來模擬作業的執行，這樣在一個node上就可以進行1:500的模擬，

測驗環境：

1. 20個調度器，2個resource manager
2. 集群總共有20w個槽位
3. 調度器調度能力為40k task/s
4. 調度分為3個階段，調度壓力分別調度器能力的50%，80%， 95%，80%， 50%

從圖(a)可以看出，隨著調度壓力的變化，latency-first在調度latency上優于adaptive, 而quality-first優于StateSync(以Omega為代表的視圖同步策略，調度器每次同步整個視圖資訊)，latency-first策略能夠將latency控制在一個非常好的水準，而StateSync的latency已經不受控制了，這也很好地證明了ParSync策略對沖突控制的有效性，對于quality-first策略，其latency也出現了不受控制的情況，這是調度器一直嘗試在分數最高的機器上進行調度所帶來的副作用，而adaptive策略對latency-first和quality-first進行了一個良好的折中，

從圖(b)中可以看出，隨著調度壓力的變化，latency-first和adaptive策略在quality上表現都有一個明顯的下降，這個符合預期，而quality-first的表現基本和StateSync持平，

綜上，ParSync在quality與StateSync表現持平的情況下，latency表現遠優于StateSync，其他更多的詳細的資料分析詳見論文，

六 總結

論文首先介紹了分布式調度器領域在解決規模問題時的常見做法：多調度器聯合調度，其次介紹了多調度器的一種常見的資源供給模型StateSync，在StateSync模式下，不同調度器間會產生嚴重的調度沖突，進而影響集群的調度效率和利用率，針對上述問題，論文通過理論分析，給出了緩解沖突方法：增加可調度資源或擴充調度器，但是在實際中這2種方法都是不可接受的，

本文提出了一種新的資源供給模式：ParSync，在ParSync模式下，不同的調度器通過round robin的方式來分時更新機器資源，同時ParSync提供了三種調度策略：latency-first， quality-first， adaptive，用來滿足不同場景下調度器對于latency\quality的要求，大規模實驗表明，ParSync在調度質量上與其他調度器持平，但在調度延時上遠優于其他調度器，

附錄

生產集群資源調度架構圖

原文鏈接
本文為阿里云原創內容，未經允許不得轉載，