Google最近公布了他們在系統基礎設施領域的一顆王冠寶石：Borg，一個集群調度器。這促使我重新閱讀論論述相同主題的Mesos和Omega的論文。我想這幾種系統做一個的對比會很有意思。Mesos因為其開創性的兩層調度(two-level scheduling)理念而廣受美譽，Omega在此基礎上用類似數據庫的技術做了改進，Borg可以看作是對所有這些思想的***之作。

1 背景

集群調度器可謂是歷史久遠，它出現在大數據的概念之前。在高性能計算(HPC)的領域里，關于如何調度成千的核心已經有了豐富的資料，但相比于數據中心調度解決的問題，核心調度的問題范圍顯然簡單很多。而Mesos/Borg等系統要解決的正是數據中心調度。接下來，讓我們通過幾個維度對比下它們。

1.1 調度中的局部性(Scheduling for locality)

超級計算機可以將存儲和計算分離，并用和內存速度差不多的近乎全等分帶寬的網絡將它們連接起來。這意味著你的任務可以放在集群的任何地方，而不用擔心具體位置，因為所有的計算節點都可以相同快速訪問到數據。有一些特別優化過的應用會針對網絡拓撲進行優化，但是這些情況很少見。

數據中心調度器需要關心具體位置，實際上這是GFS和MapReduce共同設計的所有關鍵所在。21世紀初的時候，相比于硬盤帶寬，網絡帶寬更加昂貴。所以為了降低成本，設計上會把數據存儲和計算任務放到同一個節點上。這是一個主要的調度限制，盡管之前在你能將任務放到任何地方，如今你需要將它放在三個副本的某一副本中。

1.2 硬件的配置

超級計算機通常由同類節點組成，例如他們都有一樣的硬件配置。這是因為超級算計通常是一次性采購的：一個實驗室獲得了數百萬的經費用于更新硬件。一些HPC的應用是根據某超級計算機中特定的CPU模型來優化的。新的技術如GPU或者協處理器，會當做一個新的集群推出。

在大數據的領域，集群主要受到存儲的限制。因而運維會不斷的添加新機架來為集群擴容。這意味著對于節點有著不同的CPU、內存能力、硬盤數量等現象很常見。同時也會添置一些特別如SSD、GPU或者疊瓦式硬盤(shingled drive)。一個單獨的數據中心需要大范圍的應用，而這一切又會強加額外的調度約束。

1.3 隊列管理和調度

當在超級計算機上運行應用時，你需要指定需要的節點數，要提交作業的隊列，以及作業的運行時間。隊列會對你能請求多少資源和你的任務可以運行多久做不同限制。隊列也有一個基于優先級或預留的系統，來決定排序。因為這個任務的時長都知道了，這是一個十分簡單的裝箱的問題。如果隊列很長(通常是這樣)，并且有相當多的小任務來填充大的任務留下的空間，你可以獲得相當高的利用率。我喜歡將這個描述用2D的方式可視化呈現，時間是X軸，資源利用率作為Y軸。

如前文所述，數據中心調度是一個普遍的問題。資源請求的形式可以各種各樣，并且可以有更多的維度。任務也沒有一個設定好的時間范圍，因此預先計劃隊列很困難。于是乎，我們有了越來越復雜的調度算法，然后調度器的性能變得至關重要。

利用率一般而言是會變得越來越差(除非你是Google;后面還會再提到)，但是相比HPC工作量的一個優點是，MapReduce和類似的任務，可以增量調度(incrementally scheduled)而無需成組調度(gang scheduled)。在HPC中，我們須等待請求的N個節點都到位，然后一次性運行任務。MapReduce可以一波一波地運行它的任務，這意味著它仍然可以有效地利用剩余的資源。單一的MR作業也可以基于集群的需求停止或者繼續，避免了搶占或資源預留，并且還有助于實現多用戶之間的公平性。

2 Mesos

Mesos早于Yarn出現，設計的時候考慮到了最初MapReduce存在的問題。在那時候，Hadoop集群只能運行單一的應用：MapReduce。這就很難運行不符合一個map階段跟著一個reduce的階段這種模型的應用。這里***的一個例子是 Spark。先前，你不得不為Spark安裝一套全新的worker和master，用來和你的MapReduce的worker和master一起運行。這從資源利用的角度來講完全不理想，因為它們通常是靜態分區的。

Mesos可以為所有集群應用提供一個通用的調度器API來解決了這個問題。MapReduce和Spark變成了不同簡單應用，使用的是同一個底層資源分享框架。最簡單的方式是寫一個中心化的調度器，但是這有一些缺點：

• API的復雜度。我們需要一個API，其得是所有已知的框架調度器API的超集。這是本身就很困難。如何表達資源的請求，同樣變得十分復雜。
• 性能。數萬的節點和數百萬的任務數目不小。特別當調度問題復雜的時候。
• 代碼的敏捷性。新的調度器和新的框架不斷的出現，這會帶來新的需求。

相反的，Mesos引入了新的“兩層調度”(two-level scheduling)的概念。Mesos將每應用程序自身的調度工作委派給應用程序，但Mesos仍然負責在應用之間的分派資源，保證整體上的公平性。所以Mesos非常的輕量，只有10K行代碼。

“兩層調度”是通過一個比較文藝的API叫做“資源發放(resource offer)”的接口來完成的。Mesos會周期地向應用程序調度器“發放”一些資源。這在開始聽起來可能很落后(請求從master發到應用?)，但是實際上沒有那么奇怪。在MR1中，“任務追蹤器工作者(TaskTracker worker)”了解各節點上具體的運行情況。當一個“任務追蹤器工作者”通過的心跳說某一任務已經完成，“作業追蹤器”(JobTracker)會隨后選擇其他作業來在該“任務追蹤器”上運行。調度決策是通過該worker中的一個資源發放來觸發的。在Mesos中，資源發放由Mesos的master 而不是slave發出，因為Mesos管理著集群。并沒有太大的不同。

“資源發放”就好似一個對部分資源有時限的租約。Mesos依據不同的策略，如優先級、公平分享等向應用發放資源。然后，應用會計算如何使用這些資源，同時告訴Mesos發放的資源中哪些是它需要的。這給了應用很大的靈活性，因為其可以選擇暫時先運行一部分的任務，并等待稍后更大塊的資源分配(成組分配)，或者對任務進行體積調整來適應實際發放的資源情況。因為資源是有時間約束的，這也促使應用盡快的進行調度。

一些問題和它們是如何被解決的：

• 長時間的任務會霸占(hogging)著資源。Mesos能讓你為一些占時短的任務保留一些資源，并能在任務超過時間限制后殺掉。這也鼓勵使用短線任務，其對公平有利。
• 性能隔離。使用Linux的容器(cgroups)。
• 大型任務的餓死。要獲得一個節點的獨有的訪問權是很困難的，因為一些應用中較小任務會蠶食它。修復方法是可以設置“最小發放大小”。

尚未解決/和解決方案未知的問題：

• 成組調度。我認為這種調度策略若不預先知道任務的長度或者進行搶占是不可能達到高利用率的。在低利用率的情況下不斷地囤積資源是可以的，但是可能會導致死鎖
• 跨應用的搶占(Cross-application preemption)也并非易事。資源發放API沒有辦法說“這里是一些低優先級的任務，如果你們有需要我可以停止他們”。Mesos依靠任務的占時短來獲得公平。

3. Omega

Omega可以說是Mesos的后繼者，并且實際上有一個共同的作者。因為該論文對于其評估使用的是模擬的結果，我懷疑其從來沒有在Google進入過生產，并且其中的理念被帶入了下一代的Borg。即使對于Google來說，重寫API很可能還是改動太大。

Omega將資源發放往前更推進了一步。在Mesos中，資源發放是悲觀的(pessimistic)或者叫獨占的(exclusive)。如果資源已發放給了一個應用，同樣的資源不會發放給另外一個應用，除非該發放的資源超時。在Omega中，資源發放是樂觀的(optimistic)，每一個應用都發放了所有的可用的資源，沖突是在提交的時候被解決的。Omega的資源管理器，本質上是一個保存著每一個節點的狀態關系數據庫，并且用不同的樂觀并發控制來解決沖突。這樣的好處是其大大的提高了調度器的性能(完全的并行，full parallelism)和資源利用率。

不足的的地方是，應用處于一種可以隨時獨占天下的狀態，因為它們允許以任意的速度吞食資源，甚至搶占在其他用戶之前。這對于Google來說是可行的，因為他們使用的系統是基于優先級的，并且可以對著他們內部的用戶吼。他們的任務量大概分為兩種優先級類：高優先級的服務類作業(HBase，web 服務器，長期運行的服務)和低優先級的批量式作業(MapReduce等類似的)。應用允許搶占低優先級的作業，并且可以停留在靠合作式強力取得的范圍內，包括提交的作業數，分配的資源大小等。我想雅虎在對著用戶吼這種做法上有不同的看法(這顯然不是一種可伸縮的做法)，但不知為何在Google居然可以。

論文大多數討論的是這種樂觀的分配策略是如何與沖突一起工作的，因為這是一個繞不開問題，這里有一些高層次的觀點:

• 服務類型的作業更大型，并且對安放的位置有更嚴格的需求，因為需要實現容錯(分布在不同的機架上)。
• Omega可以伸縮到數十個調度器，但無法伸縮到數百調度器，因為分發完整的集群狀態的開銷很大。
• 幾秒的調度時間是很平常的。他們也和高達數十秒甚至數百秒的調度器做了比較，這正是兩層調度真正了不起的地方。不能確定這種情況有多么普遍，或許只對于服務類的工作才這樣?
• 集群的資源利用率通常在60%。
• 沖突足夠的少見，OCC在實際中可行。在調度器崩潰之前，能達到6倍于他們正常的批量工作量。
• 增量調度非常重要。成組調度因為不斷增多的沖突，實現起來十分的昂貴。顯然，絕大部分的應用可以很好的適應增量調度，只需要幾次部分分配( partial allocations)就能達到他們總體想要的數量。
• 即使對于復雜的調度器來說(每作業幾十倍的的額外開銷)，Omega仍能在合理的等待時間下調度混合的工作量。
• 根據經驗，在Omege中實驗一個新的MapReduce調度器是十分容易的。

開放式問題

• 在一些情況下，樂觀的并發控制會因為高頻率的沖突和因重試產生的重復工作而崩潰。似乎他們在實際中不會遇到這個情況，但是我不知道是否在遇到奇形怪狀的任務時是否會遇到最壞的場景。這受服務型和批量式的作業的影響么?這個問題是否在實際中是否會進行調優?
• 缺少全局的策略真的可以接受么?如公平，搶占等等。
• 對于不同類型的作業的其調度時間的表現是怎樣的?是否有人已經寫出十分復雜的調度器了?

4. Borg

這是一個充滿生產環境的經驗的論文。它針對的工作量，與Omega一樣，因為都出自于Google，因而他們很基本點是一樣的。

4.1 高層次的

• 任何東西都運行在Borg之中，包含存儲系統，如CFS和BigTable等。
• 中等類型的集群包含10k左右的節點，盡管有的要大的多。
• 節點可以十分的異構。
• 使用了Linux的進程隔離(本質上來說是容器)，因為Borg出現在現在的虛擬機基礎設施之前。效率和啟動時間當時十分重要。
• 所有的作業都是靜態鏈接的可執行文件。
• 有非常復雜且豐富的資源定義語言可用。
• 可以滾動升級運行的作業，同時意味著配置和執行文件。這有時需要任務重啟，因而容錯是很重要的。
• 支持在最終被SIGKILL殺死之前，通過SIGTERM優雅的退出。也可以選擇溫柔地殺死，但不能保證正確性。

4.2 Allocs

• 資源分配是和進程的存活分開的。一個alloc可以用任務分組(task grouping)或者來在任務重啟之間來保持資源。
• 一個alloc集(alloc set)是一個組分配在不同的機器上的alloc。多個作業可以在同一個alloc里面運行。
• 這其實是一個常見的模式。多進程對于分離擔憂和開發是有用的。

4.3 優先級和配額

• 兩類優先級的：高和低，分別用于服務類和批量類的。
• 較高優先級的作業能搶占較低優先級的作業。
• 高優先級的任務能互相搶占(防止連串的活鎖場景)。
• 配額用于準入控制。用戶需要付更高的費用以獲得更高優先級的配額。
• 同時也提供了一個空閑的運行在***優先級層，來鼓勵高利用率和回填式的工作。
• 這是一個簡單易于理解的系統!

4.4 調度

• 兩個調度的階段：找到可用的節點，然后給這些節點打分用于***的安置。
• 可用性很大程度由任務的約束條件來決定
• 打分最主要是根據系統的屬性來決定的，像***匹配(best-fit)與最差匹配(worst-fit)的對比，作業混合(job mix)，失效域(failure domains)，局部性(locality)等等。
• 一旦最終節點被選中，Borg會在必要時進行搶占。
• 因為需要將依賴局部化( localizing dependencies)，一般的調度時間在25秒左右。下載執行文件占了80%的時間。這種局部化操作很重要。分發執行文件時用到了Torrent和樹協議。

4.5 伸縮性

• 中心化并沒有成為一個不可能的性能瓶頸。
• 每分鐘數萬節點，上萬任務的調度頻率。
• 通常Borgmaster使用10-14核和50GB左右的內存。
• 架構已經逐漸越來越多進程化(multi-process)，參考Omega和兩層調度。
• Borgmaster雖然為單主，但是一些責任有進行分片：如來自worker的狀態的更新，只讀的RPC等。
• 一些顯而易見的優化：緩存機器的評分，每任務類型一次性地計算可用性，在做調度的決策的時候不要嘗試獲得全局的***性。
• 反對增大cell的主要觀點是隔離操作的失誤和錯誤的上串。架構保持良好的伸縮性。

4.6 使用率

• 他們的主要指標是cell compaction(細胞壓縮)，或者叫能最滿足一組任務所需要最小的集群。本質上即盒包裝(box packing)。
• 從這些獲得了的大的提升：不隔離任務量或用戶，有大的共享的集群，細粒度的資源請求。
• 在一個每Borglet的基礎上樂觀的過量使用(Optimistic overcommit )。Borglet能做資源評估，并且回填非生產(non-prod)的工作。如果這個評估不正確，殺死非生產的工作。內存是非彈性化的資源。
• 分享不會大的影響CPI(CPU干擾，CPU interface),但是我比懷疑對于存儲這一塊的影響。

4.7 吸取的教訓

這里列舉的問題在Kubernetes里面已經修復了，這是他們的一個開放的開源的容器調度器。

壞處

• 能調度多作業的工作流而不是單作業會很好，有利于跟蹤和管理。這也需要更靈活的方式來指帶工作流的組件。這通過添加任意的鍵值對到每一個任務，并且讓用戶可以方便用戶查詢得到解決。
• 每一個機器一個IP。這帶一個機器上端口的沖突，和復雜的綁定和服務發現。這能通過Linux的命名空間，IPv6，SDN得到解決。
• 復雜的定義語言。太多的疙瘩需要解開，這讓一個普通用戶很難上手。需要一些在自動決定資源需求方面的工作。

好處

• Allocs 真是好極了。允許助手服務能方便的跟主要task放在一起。
• 內置的負載均衡和命名功能十分的有用。
• 指標，調試和Web界面，對于用于用戶解決自己的問題十分的有用。
• 中心化向上擴展的很好，但是需要分散到多個進程里面去。Kubernetes從頭做這個，意味在不同的調度器組件之間一個干凈的API。

5 ***的話

看起來YARN需要借鑒Mesos和Omega的設計，才能使伸縮達到10K的節點規模。相比于Mesos和 Omega，YARN仍然是一個中心化的調度器，常常像一個稻草人一樣在人們需要對Mesos和Omega進行類比的時候搬出來。Borg特別提到了需要進行分片以獲得伸縮性。

要獲得高資源利用率，又不犧牲SLO(Service Level Objective，服務水平目標)，隔離性就至關重要。這會浮現到應用的層面，在這一層應用自身需要進行容忍時延的設計。想一想BigTable中 tail-at-scale的請求復制。最終，這也會涉及到硬件開銷與軟件開銷成本的權衡。在低資源利用率下運行可以繞過這個問題。或者你可以迎難而上，通過OS的隔離機制，資源預估和對工作量及調度器的不斷調優來解決這個問題。對Google來說，擁有那樣的規模，足夠多的硬件，需要聘一大批內核的開發者是相當合情合理的。而且幸運的是，這些開發者已經幫我們解決了這些問題。

我不確定對Google工作量的設想是否適用更普通的場景。對優先級分類，保留資源和搶占對于Google來說奏效，但我們的客戶幾乎都使用公平分享調度器(fair share scheduler)。Yahoo使用容量調度器( capacity scheduler)。Twitter也使用公平調度器( fair scheduler)。我并沒有聽說過需要結合優先級+資源保留的調度器( priority + reservation scheduler)的需求。

***，運行大型的共享集群，這種我們預想在Google中的上演的狀況，在我們的客戶中卻很難遇到。我們的客戶中雖然也有使用成千的節點的，但它們實際上是分散到了成百節點上的pod里面去的。把不同的用戶和應用分到不同的集群，也仍然是常見的做法。集群通常在硬件上也是同構的，但我想這種情況會很快改變。

原文鏈接：http://www.dockone.io/article/571