作者 | 馮亦揮、劉智、趙蘊健、金曉月、吳一迪、張楊、鄭尚策、李超、關濤
來源 | 阿裡技術公衆号
引言
近日，在國際體系架構頂會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方案不可避免的會帶來排程沖突，我們希望能清楚如下幾個問題：
- 有哪些因素會影響沖突，它們各自的權重是多少？
- 排程延遲會惡化到什麼程度？
- 如何才能夠避免或減緩沖突？
我們首先對沖突進行模組化，得出沖突(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的模拟。
測試環境：
- 20個排程器，2個resource manager
- 叢集總共有20w個槽位
- 排程器排程能力為40k task/s
- 排程分為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在排程品質上與其他排程器持平，但在排程延時上遠優于其他排程器。
附錄
生産叢集資源排程架構圖
論文位址
https://www.usenix.org/system/files/atc21-feng-yihui.pdf技術公開課
R語言程式設計基礎
作為目前在世界範圍内最受歡迎的資料挖掘開發語言——R語言以其特有的開放性、高可擴充性以及頂尖的制圖功能吸引了越來越多的資料分析愛好者。R語言文法通俗易懂，學會之後，可以編制自己的函數來擴充現有的語言。本課程共8個課時，帶同學們入門R語言。
[點選這裡](
https://developer.aliyun.com/learning/course/564?utm_content=g_1000287319），快去學習吧~