作者：陶陽宇，花名舉水哥遮，阿里云高級技術(shù)專家岂丘，飛天分布式系統(tǒng)早期核心開發(fā)人員，開發(fā)和優(yōu)化過伏羲系統(tǒng)中多個功能模塊眠饮，參加了飛天5K奥帘、世界排序大賽等多個技術(shù)攻堅項目。在分布式計算仪召、高并發(fā)系統(tǒng)的設(shè)計和開發(fā)方面有較豐富的經(jīng)驗寨蹋。?
本文涉及阿里云分布式調(diào)度團(tuán)隊在分布式調(diào)度系統(tǒng)的設(shè)計、實現(xiàn)扔茅、優(yōu)化等方面的實踐以及由此總結(jié)的分布式系統(tǒng)設(shè)計的一般性原則钥庇，具體包括分布式調(diào)度的任務(wù)調(diào)度、資源調(diào)度咖摹、容錯機(jī)制评姨、規(guī)模挑戰(zhàn)、安全與性能隔離以及未來發(fā)展方向六部分萤晴。
云計算并不是無中生有的概念吐句，它將普通的單臺PC計算能力通過分布式調(diào)度軟件連接起來。其最核心的問題是如何把一百臺店读、一千臺嗦枢、一萬臺機(jī)器高效地組織起來，靈活進(jìn)行任務(wù)調(diào)度和管理屯断，從而可以像使用臺式機(jī)一樣使用云計算文虏。在云計算中，最核心的模塊是分布式調(diào)度殖演，它好比云計算的中央處理器氧秘。目前章办，業(yè)界已存在多種分布式調(diào)度實現(xiàn)方案总棵，如伏羲、Hadoop MapReduce竟秫、YARN彼棍、Mesos等系統(tǒng)灭忠。
阿里云伏羲
伏羲系統(tǒng)在前人的基礎(chǔ)上進(jìn)行了一系列改造膳算，首先與YARN和Mesos系統(tǒng)類似，將資源的調(diào)度和任務(wù)調(diào)度分離弛作，形成兩層架構(gòu)涕蜂，使其具備以下優(yōu)勢：
規(guī)模：兩層架構(gòu)易于橫向擴(kuò)展，資源管理和調(diào)度模塊僅負(fù)責(zé)資源的整體分配映琳，不負(fù)責(zé)具體任務(wù)調(diào)度宇葱，可以輕松擴(kuò)展集群節(jié)點(diǎn)規(guī)模；
容錯：當(dāng)某個任務(wù)運(yùn)行失敗不會影響其他任務(wù)的執(zhí)行刊头；同時資源調(diào)度失敗也不影響任務(wù)調(diào)度黍瞧；
擴(kuò)展性：不同的計算任務(wù)可以采用不同的參數(shù)配置和調(diào)度策略，同時支持資源搶占原杂；
調(diào)度效率：計算framework決定資源的生命周期印颤，可以復(fù)用資源，提高資源交互效率穿肄。
這套系統(tǒng)目前已經(jīng)在阿里集團(tuán)進(jìn)行了大范圍的應(yīng)用年局，能支持單集群5000節(jié)點(diǎn)、并發(fā)運(yùn)行10000作業(yè)咸产、30分鐘完成100T數(shù)據(jù)terasort矢否，性能是Yahoo在Sort Benchmark的世界紀(jì)錄的兩倍。
伏羲的系統(tǒng)架構(gòu)
伏羲的系統(tǒng)架構(gòu)如圖1所示脑溢，整個集群包括一臺Fuxi Master以及多臺Tubo僵朗。其中Fuxi Master是集群的中控角色，負(fù)責(zé)資源的管理和調(diào)度屑彻；Tubo是每臺機(jī)器上都有的一個Agent验庙，負(fù)責(zé)管理本臺機(jī)器上的用戶進(jìn)程；同時集群中還有一個叫Package Manager的角色社牲，因為用戶的可執(zhí)行程序以及一些配置需要事先打成一個壓縮包并上傳到Package Manager上粪薛，Package Manager專門負(fù)責(zé)集群中包的分發(fā)。
集群部署完后搏恤，用戶通過Client端的工具向Fuxi Master提交計算任務(wù)违寿；Fuxi Master接收到任務(wù)后首先通知某一個Tubo啟動這個計算任務(wù)所對應(yīng)的APP Master；APP Master啟動之后熟空，它獲知了自己的計算任務(wù)藤巢，包括數(shù)據(jù)分布在哪里、有多少的任務(wù)需要計算等等信息痛阻；接著APP Master會向Fuxi Master提交資源申請菌瘪，表明它需要多少計算資源腮敌；Fuxi Master經(jīng)過資源調(diào)度以后阱当，將資源的分配結(jié)果下發(fā)給APP Master俏扩；APP Master在這個資源的基礎(chǔ)之上進(jìn)行它的任務(wù)調(diào)度，來決定哪些機(jī)器上運(yùn)行哪些計算任務(wù)弊添，并且將這個計算任務(wù)發(fā)送給對應(yīng)機(jī)器上的Tubo進(jìn)程录淡；Tubo接受到命令之后就會從Package Manager中下載對應(yīng)的可執(zhí)行程序并解壓；然后啟動用戶的可執(zhí)行程序油坝，加載用戶的配置（圖1中的APP Worker）嫉戚；APP Worker根據(jù)配置中的信息讀取文件存儲系統(tǒng)中的數(shù)據(jù)，然后進(jìn)行計算并且將計算結(jié)果發(fā)往下一個APP Worker澈圈。其中彬檀，數(shù)據(jù)的切片稱之為Instance或者叫計算實例。
Fuxi Master與Tubo這套結(jié)構(gòu)解決了分布式調(diào)度中的資源調(diào)度瞬女，每個計算任務(wù)的APP Master以及一組APP Worker組合起來解決任務(wù)調(diào)度的問題窍帝。
任務(wù)調(diào)度
伏羲在進(jìn)行任務(wù)調(diào)度時，主要涉及兩個角色：計算框架所需的APP Master以及若干個APP Worker诽偷。
APP Master首先向Fuxi Master申請/釋放資源坤学；拿到Fuxi Master分配的資源以后會調(diào)度相應(yīng)的APP Worker到集群中的節(jié)點(diǎn)上，并分配Instance（數(shù)據(jù)切片）到APP Worker报慕；APP Master同時還要負(fù)責(zé)APP Worker之間的數(shù)據(jù)傳遞以及最終匯總生成Job Status深浮；同時為了達(dá)到容錯效果，APP Master還要負(fù)責(zé)管理APP Worker的生命周期眠冈，例如當(dāng)發(fā)生故障之后它要負(fù)責(zé)重啟APP Worker飞苇。
而APP Worker的職責(zé)相對比較簡單，首先它需要接收App Master發(fā)來的Instance蜗顽，并執(zhí)行用戶計算邏輯玄柠；其次它需要不斷地向APP Master報告它的執(zhí)行進(jìn)度等運(yùn)行狀態(tài)；其最為主要的任務(wù)是負(fù)責(zé)讀取輸入數(shù)據(jù)诫舅，將計算結(jié)果寫到輸出文件羽利；此處的Instance是指輸入數(shù)據(jù)的切片。伏羲任務(wù)調(diào)度系統(tǒng)的技術(shù)要點(diǎn)主要包括數(shù)據(jù)的Locality刊懈、數(shù)據(jù)的Shuffle以及Instance重試和Backup Instance三點(diǎn)这弧。
數(shù)據(jù)Locality
數(shù)據(jù)Locality是指調(diào)度時要考慮數(shù)據(jù)的親近性，也就是說APP Worker在處理數(shù)據(jù)時虚汛，盡量從本地的磁盤讀取數(shù)據(jù)匾浪，輸出也盡量寫到本地磁盤，避免遠(yuǎn)程的讀寫卷哩。要實現(xiàn)這一目標(biāo)蛋辈，在任務(wù)調(diào)度時，盡量讓Instance（數(shù)據(jù)分片）數(shù)據(jù)最多的節(jié)點(diǎn)上的AppWorker來處理該Instance。
數(shù)據(jù)Shuffle
數(shù)據(jù)Shuffle指的是APP Worker之間的數(shù)據(jù)傳遞冷溶。在實際運(yùn)行中渐白，APP Worker之間是有多種傳遞形態(tài)的，如一對一逞频、一對N纯衍、M對N等模式。如果用戶去處理不同形態(tài)的傳輸模式苗胀，勢必會帶來較大的代價襟诸。伏羲分布式調(diào)度系統(tǒng)將數(shù)據(jù)傳遞的過程封裝成streamline lib，用戶無需關(guān)心數(shù)據(jù)傳遞的細(xì)節(jié)基协。首先Map進(jìn)行運(yùn)算歌亲，將結(jié)果直接交給streamline，streamline底層會根據(jù)不同的配置將數(shù)據(jù)傳給下游計算任務(wù)的streamline澜驮；然后streamline將接到的數(shù)據(jù)交給上層的計算任務(wù)应结。
Instance重試和backup instance
在Instance的運(yùn)行過程中可能有多種原因?qū)е翴nstance失敗，比如APP Worker進(jìn)程重啟或運(yùn)行時機(jī)器泉唁、磁盤發(fā)生故障鹅龄，種種原因都可能導(dǎo)致一個Instance在運(yùn)行時最終失敗亭畜；另外APP Master還會監(jiān)控Instance的運(yùn)行速度扮休，如果發(fā)現(xiàn)Instance運(yùn)行非常慢（容易造成長尾），會在另外的APP Worker上同時運(yùn)行該Instance拴鸵，也就是同時有兩個APP Worker處理同一份數(shù)據(jù)玷坠，APP Master會選取最先結(jié)束的結(jié)果為最終結(jié)果。判斷一個Instance運(yùn)行緩慢的依據(jù)有：
該Instance運(yùn)行時間超過其他Instance的平均運(yùn)行時間劲藐；
該Instance數(shù)據(jù)處理速度低于其他Instance平均值八堡；
目前已完成的Instance比例，防止在整體任務(wù)運(yùn)行初期發(fā)生誤判聘芜。
資源調(diào)度
資源調(diào)度要考慮幾個目標(biāo)：一是集群資源利用率最大化兄渺；二是每個任務(wù)的資源等待時間最小化；三是能分組控制資源配額汰现；四是能支持臨時緊急任務(wù)挂谍。在飛天分布式系統(tǒng)中，F(xiàn)uxi Master與Tubo兩者配合完成資源調(diào)度瞎饲。
在飛天分布式系統(tǒng)中口叙，F(xiàn)uxi Master與Tubo兩者配合完成資源調(diào)度。Tubo是每個節(jié)點(diǎn)都有的嗅战，用于收集每個機(jī)器的硬件資源（CPU妄田、Memory、Disk、Net）疟呐，并發(fā)送給FuxiMaster脚曾；FuxiMaster是中控節(jié)點(diǎn)，負(fù)責(zé)整個集群的資源調(diào)度萨醒。當(dāng)啟動計算任務(wù)時斟珊，會生成APP Master苇倡，它根據(jù)自己的需要向Fuxi Master申請資源富纸，當(dāng)計算完成不再需要時，歸還該資源旨椒。
飛天分布式調(diào)度常用的分配資源策略包括優(yōu)先級和搶占晓褪、公平調(diào)度、配額综慎。在實際應(yīng)用場景中涣仿，不同策略可配合起來使用。
策略之優(yōu)先級和搶占
每個Job在提交時會帶一個priority值（整數(shù)值）示惊，該值越小優(yōu)先級越高好港；相同優(yōu)先級按提交時間，先提交的優(yōu)先級高米罚；FuxiMaster在調(diào)度時钧汹，資源優(yōu)先分配給高優(yōu)先級的Job，剩余的資源繼續(xù)分配給次高優(yōu)先級Job录择。
如果臨時有高優(yōu)先級的緊急任務(wù)加入拔莱，F(xiàn)uxiMaster會從當(dāng)前正在運(yùn)行的任務(wù)中，從最低優(yōu)先級任務(wù)開始強(qiáng)制收回資源隘竭，以分配給緊急任務(wù)塘秦，此過程稱為“搶占”。搶占遞歸進(jìn)行动看，直到被搶任務(wù)優(yōu)先級不高于緊急任務(wù)尊剔，也就是不能搶占比自己優(yōu)先級高的任務(wù)。
策略之公平調(diào)度
公平調(diào)度策略是指當(dāng)有資源時Fuxi Master依次輪詢地將部分資源分配給各個Job菱皆，它避免了較大Job搶占全部資源導(dǎo)致其他Job餓死現(xiàn)象發(fā)生赋兵。公平調(diào)度首先按優(yōu)先級分組，同一優(yōu)先級組內(nèi)的平均分配搔预，如果有剩余資源再去下一個優(yōu)先級組進(jìn)行分配霹期，依此類推。
配額
配額是資源分配時的第三個策略拯田，通常是按照不同的業(yè)務(wù)進(jìn)行區(qū)分历造，多個任務(wù)組成一個組，例如淘寶、支付寶等吭产；集群管理員會設(shè)立每一個組的資源上限侣监，意味著這個組最多能使用這么多CPU、Memory臣淤、磁盤等橄霉，該上限值稱為Quota；每個組的Job所分配的資源總和不會超過該組內(nèi)的Quota邑蒋，當(dāng)然如果每一個組內(nèi)沒有用完的Quota是可以分享給其他組的姓蜂，會按照Quota的比例進(jìn)行均分。
容錯機(jī)制
在大規(guī)模進(jìn)程集群中故障是常態(tài)医吊，這些常態(tài)會來自硬件钱慢，比如主板、電源卿堂、內(nèi)存條束莫；也可能來自軟件，比如進(jìn)程有Bug導(dǎo)致進(jìn)程Crash草描，機(jī)器故障導(dǎo)致性能慢览绿。因此，分布式調(diào)度必須具有容錯機(jī)制穗慕，以保證正在運(yùn)行的任務(wù)不受影響饿敲，并對用戶透明，能夠從故障中恢復(fù)過來揍诽，保障系統(tǒng)的高可用诀蓉。下面將從任務(wù)調(diào)度的Failover和資源調(diào)度的Failover兩個方面介紹。
AppMaster進(jìn)程重啟后的任務(wù)調(diào)度Failover
每個計算任務(wù)有自己的APP Master暑脆，如果APP Master進(jìn)程發(fā)生了重啟渠啤，那其重啟之后的任務(wù)調(diào)度如何進(jìn)行Failover呢？這里采用了Snapshot機(jī)制添吗，它將Instance的運(yùn)行進(jìn)度保存下來沥曹，當(dāng)APP Master重啟之后會自動加載Snapshot以獲取之前每個Instance的執(zhí)行進(jìn)度，然后繼續(xù)運(yùn)行Instance碟联；當(dāng)APP Master進(jìn)程重啟之后妓美，從APP Worker匯報的狀態(tài)中重建出之前的調(diào)度結(jié)果，繼續(xù)運(yùn)行Instance鲤孵。
FuxiMaster進(jìn)程重啟后的資源調(diào)度Failover
另一種情況是Fuxi Master發(fā)生了Failover壶栋。Fuxi Master Failover起來之后需要重建內(nèi)部狀態(tài)，該狀態(tài)通常分為兩種：一是Hard State普监，主要是之前提交的Application配置信息贵试，如不同的Job配置參數(shù)等琉兜，它們來自于Fuxi Master寫的Snapshot；另一類是Soft State毙玻，F(xiàn)uxi Master會收集來自各個Tubo以及APP Master的信息重建出自己的狀態(tài)豌蟋，這些信息包括機(jī)器列表、每個APP Master的資源請求以及之前的資源分配結(jié)果桑滩。
Fuxi Master進(jìn)程重啟之后的資源調(diào)度過程如圖4所示梧疲，首先會從Checkpoint中讀取出所有Job的配置信息；同時會收集所有的Tubo以及APP Master上報上來的關(guān)于資源分配的結(jié)果运准，如CPU多少幌氮、Memory多少等等。
規(guī)模挑戰(zhàn)
分布式系統(tǒng)設(shè)計主要目標(biāo)之一就是橫向擴(kuò)展（scale-out）戳吝，目前阿里云飛天在2013年時已支撐單個集群5000個節(jié)點(diǎn)浩销、并發(fā)1萬個任務(wù)贯涎。在做橫向擴(kuò)展設(shè)計時听哭，需要注意兩個要點(diǎn)：一是多線程異步；二是增量的資源調(diào)度塘雳。
多線程異步
多線程異步是編寫分布式程序一個非常重要而且常用的技術(shù)手段陆盘。在網(wǎng)絡(luò)通信模塊中，每個APP Master都需要跟Fuxi Master進(jìn)行資源通信败明，同時也需要跟多個Tubo進(jìn)行通信以啟動它們的APP Worker隘马。APP Master處理網(wǎng)絡(luò)通信的過程稱之為RPC，RPC通信時必須采用線程池來處理妻顶。如圖5中采用四個線程池來處理這些消息酸员。由于Fuxi Master是一個中控節(jié)點(diǎn)，而Tubo的數(shù)量非常眾多讳嘱，如果將這些消息都在同一個線程池中處理幔嗦，則Fuxi Master的消息有可能會被大量的Tubo消息阻塞（對頭阻塞問題）。為了解決該問題沥潭，在伏羲系統(tǒng)當(dāng)中設(shè)立了一個獨(dú)立的線程池來處理Fuxi Master的消息邀泉；另外一個線程池來處理Tubo的消息，將線程池進(jìn)行分開钝鸽，也稱之為泳道汇恤；獨(dú)立的泳道能有效解決Fuxi Master的消息被對頭阻塞的問題。
增量的資源調(diào)度
伏羲解決規(guī)模問題的另一個技術(shù)點(diǎn)是增量拔恰。目前因谎，伏羲采用增量的消息通信和資源調(diào)度，下面通過具體例子颜懊，來介紹伏羲所采用的增量資源調(diào)度的協(xié)議财岔。
圖6左側(cè)是中控節(jié)點(diǎn)Fuxi Master阱穗；右邊為某一個APP Master，如果說APP Master需要1000份資源使鹅，最直接的一種實現(xiàn)方式是將“我要1000個資源”這樣的消息直接發(fā)送給Fuxi Master揪阶；Fuxi Master在接到消息之后可能當(dāng)前的剩余資源只有200份，它將會“我分配給你200”這樣的消息發(fā)送給APP Master患朱；那APP Master還會繼續(xù)發(fā)送消息“我還要剩余的800”鲁僚，F(xiàn)uxi Master回復(fù)“此時沒有資源，我分配0個給你”裁厅；則APP Master在下一次通信的時候需要繼續(xù)發(fā)送“我還要剩余的800”……依此類推冰沙，可能某一個時刻Fuxi Master還能分一點(diǎn)資源下來。這就是最直觀的全量消息通信执虹，每一次APP Master提出請求時都要指明它總共需要多少拓挥。
而在伏羲的實現(xiàn)當(dāng)中為了減小通信量和不必要的開銷，采用了增量的語義袋励。首先APP Master發(fā)送一個請求“我要1000個資源”侥啤，F(xiàn)uxi Master收到之后將當(dāng)時空閑的200個資源返回給APP Master；之后APP Master無需再提交請求說我還需要800茬故，因為Fuxi Master會將這1000個請求記錄下來等到某一時刻又有更多的資源盖灸，比如150個資源釋放，它直接將150個分配結(jié)果發(fā)送給APP Master即可磺芭。這期間APP Master無需再發(fā)多余的網(wǎng)絡(luò)通信赁炎。
安全與性能隔離
在分布式系統(tǒng)當(dāng)中通常有多個用戶在執(zhí)行自己的計算任務(wù)，多個任務(wù)之間需要互相隔離钾腺、互相不影響徙垫。飛天伏羲實現(xiàn)了全鏈路的訪問控制，采用了兩種訪問控制進(jìn)行安全的驗證放棒，一種是Capability姻报，指通信雙方基于私鑰進(jìn)行解密并驗證的一種方式；還有一種稱為Token的方式哨查，這種方式需要通信的雙方臨時生成基于私鑰加密的口令逗抑，在通信時進(jìn)行驗證。
兩種方式最大區(qū)別在于口令生成的時機(jī)寒亥，Capability方式是在通信之前就已經(jīng)加密好邮府；而Token是需要在通信時臨時生成。
兩種方式使用于不同的場景溉奕，如圖7所示FuxiMaster與Tubo通信采用的是Capability方式褂傀，因為這兩個角色在集群部署時就已啟動，可以事先進(jìn)行加密生成好Capability加勤；FuxiMaster與APP之間是采用Token的方式仙辟，這是因為APP與FuxiMaster進(jìn)行通信時同波，當(dāng)每個任務(wù)執(zhí)行完計算之后會退出；在進(jìn)程與進(jìn)程之間叠国，伏羲采用了沙箱的方式將不同的進(jìn)程進(jìn)行隔離開未檩、互不干擾。
除了安全的隔離之外粟焊，還需要考慮性能的隔離冤狡。目前伏羲采用的幾種技術(shù)手段：Cgroup（Linux LXC）、Docker container项棠、VM等悲雳。這幾種技術(shù)的隔離性、資源配額/度量香追、移動性合瓢、安全性的比較如圖8所示，不再一一敘述透典。
伏羲目前采用的隔離技術(shù)是基于Docker和LXC混合部署的方式晴楔，之所以拋棄虛擬機(jī)的方式，是因為其性能損耗太多掷匠。當(dāng)運(yùn)行計算任務(wù)時滥崩，如果完全放在虛擬機(jī)當(dāng)中岖圈，它的IO以及CPU時間片會受到很大的影響讹语，會降低任務(wù)的執(zhí)行效率。在目前阿里的生產(chǎn)環(huán)境中蜂科，實踐發(fā)現(xiàn)基于Docker和LXC的隔離技術(shù)已經(jīng)可以很好地滿足需求。
分布式調(diào)度的發(fā)展方向
隨著計算能力和數(shù)據(jù)量的持續(xù)增長导匣，分布式調(diào)度未來可能朝向以下幾個方向發(fā)展：
在線服務(wù)與離線任務(wù)混跑才菠。云計算最終的目的是降低IT成本，最大限度地利用單臺PC的CPU處理能力贡定，所以未來的趨勢一定是在線服務(wù)與離線任務(wù)能夠在同一物理集群上運(yùn)行從而實現(xiàn)削峰填谷效果赋访、最大化提高集群利用率。但是由于兩種任務(wù)的特點(diǎn)不同缓待，在線運(yùn)用對于響應(yīng)時間要求很高蚓耽，而離線運(yùn)用則對調(diào)度的吞吐率要求比較高，因此混跑會帶來性能隔離與資源利用率之間的矛盾旋炒。
實時計算的發(fā)展步悠，Map Reduce是一個很偉大的框架，但其是為數(shù)據(jù)量一定的批處理而設(shè)計的瘫镇。隨著云計算越來越普及鼎兽，很多計算形態(tài)需要實時拿到計算結(jié)果答姥，并且其輸入數(shù)據(jù)可能是不間斷的。目前谚咬，伏羲也已經(jīng)開發(fā)出了實時的計算框架——OnlineJob鹦付，它可以提供更快的執(zhí)行速度。
更大的規(guī)模择卦，目前已能夠支撐5000臺的節(jié)點(diǎn)睁壁，隨著計算量越來越大，客戶的需求越來越多互捌，需要進(jìn)一步優(yōu)化伏羲系統(tǒng)潘明，能夠支撐起1萬、5萬秕噪、10萬等更大規(guī)模單集群钳降，同時能夠支撐更多的并發(fā)任務(wù)。
