# 8-2 Omega: flexible, scalable schedulers for large compute clusters

## Introduction
Figure 1前兩張圖是目前常用的調度器結構，但都不適合應用在規模迅速增長和需求快速響應的集群調度上，會有資源利用率及擴展性的問題。
* Monolithic：中央集中式的調度框架，將資源的調度和作業的管理功能全部放到一個進程中完成，擴展性差。
* Two-level：保留一個經過簡化的中央式調度器，但調度策略下放到各個應用程式調度器完成，如Yarn、Mesos。不過受資源可見度和Lock的影響，在資源分配和併發程度上的效果不是那麼理想。
* 各個框架無法知道整個叢集的即時資源使用情況，可能會因此造成需長時間等待資源釋放。
* 採用悲觀鎖(通常用lock來處理concurrency)，會大大降低性能。

因此Google 開發了一種基於共享狀態的新平行調度器架構Omega，來解決上述兩種結構導致的在大型集群上資源利用和效率和可擴展性不夠高的問題。
* Shared state：將雙層調度器中的集中式資源調度模組簡化了一些持久的共享資料（狀態）和針對這些資料的驗證程式碼，使用樂觀鎖 (MVCC, Multi-Version Concurrency Control) 來控制concurrency，支援更大的叢集和更高的並發。

## Requirements
集群調度要滿足的目標：
1. 硬體資源的高利用率
2. 使用者定義的調度策略
3. 快速調度決策過程
4. 兼顧各種層面的公平調度
5. 保持穩健且始終可用

而要達成上述目標之所以複雜，最主要的因素是在大型計算集群中常見的硬件和工作負載的異質性，Google將長期運行的服務工作（如網路服務）和內部基礎設施服務（如BigTable）與執行計算後結束的批量工作分開，將所有低優先級的工作和那些標記為“最佳努力”或“批量”的工作放入批量類別中，其餘的則放入服務類別中。
>工作負載由兩大類作業組成：
>* **批次作業:** 工作負載中的大部分作業都是批次作業，與服務作業相比，批次作業的生命週期較短，到達間隔也較短，快速反應非常重要，因此輕量級、低品質的放置方式就足夠好了。
>* **服務作業:** 大部分的資源都被服務作業消耗。而長時間運行的高優先級服務工作（20–40% 的工作運行超過一個月）必須滿足嚴格的可用性和性能目標，需要仔細放置其任務，以最大限度地抵抗故障並提供良好的性能。

不過上述嘗試放置任務來抵抗獨立和協調的故障可能會產生head of line blocking(隊列首阻塞)問題，可以透過引入concurrency來避免，因此需要一個調度器架構，能夠容納兩種類型的工作，靈活支持特定於工作的政策，並且還能夠應對不斷增長的調度工作量。

## Taxonomy
Table 1列出了集群調度器必須解決的問題，以及檢查不同調度器架構如何處理這些問題。
* **Partitioning the scheduling work:** 將工作分散到調度器的方式：
* 不考慮工作負載類型的負載平衡
* 將專門的調度器專門用於工作負載的不同部分
* 綜合以上兩者
* **Resource choice:** 調度器可以被允許從集群的所有資源中選擇，或限制為一個子集以簡化決策。
* **Interference:** 如果調度器競爭資源，多個調度器可能會同時申請同一資源。
* 悲觀方法通過確保一次只向一個調度器提供特定資源來避免此問題
* 樂觀方法則檢測（希望很少發生的）衝突，並撤銷一個或多個相互衝突的申請，增加並行性，但如果衝突過於頻繁，可能會增加浪費的調度工作量。
* **Allocation granularity:** 由於工作通常包含許多任務，調度器可以對如何調度它們有不同的政策。
* 一個極端是對工作中的任務進行原子性的全包（all-or-nothing）幫調度，可以通過逐步獲取資源並囤積(hoarding)它們直到可以開始工作來近似實現，但降低了集群利用率並且也可能導致死鎖。
* 另一個極端是隨著資源的發現逐步放置任務，如果沒有提供回退機制，可能導致死鎖。
* **Cluster-wide policies:** 有些行為涵蓋多個調度器，尤其是在確保公平性、工作的相對重要性的共識方面，以及在一個調度器可能會預占另一個調度器任務的情境下的行為。因此需要決定如何在多調度器環境中協調和管理不同的調度策略和政策，確保整個集群的公平、有效運作。

### Monolithic schedulers
只有單一實例、沒有並行性、並且必須在single code base中實現所有政策選擇的單體調度器，在高性能計算（HPC）界很常見，通常運行調度程式碼的單一實例，並對所有進來的工作應用相同的算法，但經實作發現使用單一算法實現來持續支持廣泛的政策範圍比想像中困難許多，因此成為Google轉向支持並行、獨立調度組件架構的主要動機。

### Statically partitioned schedulers
(這邊沒有多探討這個部分)
大多數「雲計算」調度器（如Hadoop和Dryad的Quincy）假設它們對一組資源有完全控制權，因為它們通常部署在專用的、靜態劃分的機器集群上，或者通過將單一集群分割成支持不同行為的不同部分，這會導致碎片化和利用率不好，對於需要高效率和靈活性的大規模操作環境來說是不可行的，因此沒有進一步探索這個選項。

### Two-level scheduling
使用中央協調者動態調整分配給每個調度器的資源，決定每個子集群可以擁有多少資源，如Mesos和Hadoop-on-Demand（HOD)。
* **Mesos:** 一個集中的資源分配器動態的將一個集群劃分，將資源分配給不同的調度器框架，資源以提供形式分發給框架，其中只包含目前未被使用的資源，分配器通過**一次只向一個框架提供給定資源來避免衝突**，也就是在調度決定的過程中對該資源持有鎖(**悲觀併發控制**)，適用於任務壽命短並且頻繁釋放資源，以及當工作大小與集群大小相比較小的時候。
雖然 Mesos 框架可以使用filter來描述它希望被提供的資源類型，但**沒辦法知道整個叢集目前資源使用情況**，使用hoarding來實現幫調度，可能因此導致死鎖。
>**Yarn:** 看起來是一個兩級調度器，實際上是一個單體調度器架構。
>每個工作都有一個Application Master，當需要請求資源時，Application Master會向Resource Manager中的一個全局調度器發送資源請求，該調度器根據應用指定的限制在各種機器上分配資源。
>因此實際控制資源分配的是Resource Manager，Application Master提供的是工作管理服務，而不是調度。

### Shared-state scheduling
Omega使用的共享狀態方法，**允許每個調度器完全訪問整個集群**，讓它們自由競爭共享資源，並使用**樂觀並發控制**來調解它們在更新集群狀態時發生的衝突，解決了Two-level scheduling由於悲觀並發控制導致的有限並行性及調度器框架中資源可見性受限的問題，但樂觀並發假設不正確時可能需要重做工作，本文目的就是**在提高效率和可能重做操作之間進行取捨**。
* 調度器操作
* 每個調度器擁有對單元狀態（集群的資源分配狀態）的私人、本地且定期更新的副本。
* 調度器根據單元狀態做出調度決策，可以申請任何可用的資源，即使是已被其他調度器申請的資源，決策完成後，調度器會原子性地更新共享的單元狀態副本，如果發生衝突，只有一個調度器的更新會成功。

**Omega 的調度器完全平行運作**，不必等待其他調度器的工作，且不存在調度器間的隊列首阻塞，為了防止衝突導致饑餓，通常選擇使用增量交易，接受除衝突更改外的所有更改（也就是交易提供原子性但不提供獨立性），也可選擇使用全有或全無的交易來實現幫調度，減少等待和資源囤積。
所有調度器必須遵守共同的資源分配規則，例如機器是否已滿的共同認知和工作優先級，避免中央化管理帶來的複雜性。
**共享狀態方法的性能取決於交易失敗的頻率和失敗的成本。**

## Design comparisons
為了理解之前單體、兩級和共享狀態調度器之間的取捨，構建了兩個模擬器來比較不同調度器架構的性能。
1. **輕量級模擬器(lightweight simulator):** 主要用於在相同的工作條件和負載下比較上述三種不同的調度器架構，**使用合成工作負載來模擬調度器在管理計算資源時的行為**，在保持模擬的核心真實性的同時，簡化了某些計算過程，**運行效率較高**。調度程式每個作業的決策時間被建模為固定作業時間加上與任務數量成線性比例的可變分量。
>**合成工作負載是什麼?**
>基於從真實工作負載數據中提取的參數生成的工作負載，也就是模擬器使用從實際運行環境中得到的數據（如任務數量、持續時間、資源需求等）來創建模擬情境，而非真正發生的情境。
2. **高保真度模擬器(high-fidelity simulator):** 在真實模擬器上完成並由真實軌跡驅動，**得到了更接近實際系統的行為**，但**只支持 Omega 架構且運行速度遠慢於輕量級模擬器**：單次運行可能需要數天。

### Monolithic schedulers
* **單路徑調度器（Single-path）:** 不論工作類型，調度器對所有工作使用相同的決策時間(模擬器的設置)。如果這個時間很短，所有工作的等待時間也會很短；但如果決策時間延長，所有工作的等待時間都會增加，如Figure 5(a)，隨著調度器作業決策時間的增加，調度器的繁忙程度呈線性成長Figure 6(a)，調度器效能很差。
* **多路徑調度器（Multi-path）:** 批次工作可以通過快速路徑快速得到資源(模擬器的設置)，即使在服務工作的決策時間很長的情況下，因為大部分工作都是批次工作，平均工作等待時間和調度器繁忙度也明顯降低，如Figure 5(b)、Figure 6(b)，但批次工作仍然可能因為排在難以調度的服務工作後面而卡在隊列中，出現隊列首阻塞。

### Two-level scheduling: Mesos
這邊基於Mesos架構來做實驗，模擬了一個單一的資源管理器和兩個調度器框架，一個處理批次工作，另一個處理服務工作。這邊保持批次調度器的決策時間不變，並通過調整 *t~job~(service)* 來改變服務調度器的決策時間。
從Figure 7(a)可以看到在不同集群中，服務調度器的決策時間增加對工作等待時間的影響相對一致。而從Figure 7(b)可以觀察到批次調度器的繁忙程度顯然比單體多路徑案例中的要高許多。
>**主要原因:**
Mesos透過輪流向不同的調度器提供所有可用的集群資源來實現公平，但這個方法必須建立在資源頻繁可用，而且調度器決策很快的前提下，但這邊服務決策時間長，會導致資源長時間被鎖定，批次作業也只能訪問那些調度器決策過程中偶然可用的少量資源，這些資源通常不足批次工作的需求。
儘管資源不足，調度期仍會嘗試調度，導致調度器異常忙碌，最後因達到嘗試上限而將工作放棄，如Figure 7(c)。


### Shared-state scheduling: Omega
這邊模擬兩個調度器，一個處理批次工作負載，另一個處理服務工作負載。
可以觀察到調度的效能至少與多路徑單晶片調度器一樣好，也因為服務作業和批次作業有不同的平行調度程序，不會有隊列首阻塞，如Figure 5(c)。
除此之外還調查了Omega在工作負載變化時的擴展性，提高了批次調度器的工作到達率 λ~job~(batch)，圖8顯示工作等待時間和調度器繁忙度均有所增加，在批次工作中，這是由於更高的工作到達率所致；而在服務工作中，則是由於額外的衝突所導致。如虛線垂直線所示，A 集群的擴展性約為原工作負載的2.5倍，而B和C集群分別可擴展到6倍和9.5倍。
Figure 9顯示不同數量的批次調度器對衝突率和繁忙度的影響，可以從Figure 9(a)看到隨著批次工作到達率的增加，衝突比例上升，但從Figure 9(b)可以看到使用更多的批次調度器能夠有效降低個別調度器的繁忙度，代表Omega模型能夠在承受高批次工作負載的同時，仍然為服務工作提供良好的行為。

### Summary
* 單體調度器不具有擴展性，儘管增加多路徑功能降低了平均調度決策時間，但對於批次工作來說仍會有隊列首阻塞的問題。
* Mesos的兩級模型可以支持獨立的調度器實現，但它受到悲觀鎖定的阻礙，也不擅長處理長時間的決策，無法調度多樣化負載。
* 共享狀態的Omega方法提供了具有競爭力的、可擴展的性能，並且在實際運行點上干擾很小，支持獨立的調度器實現，並向調度器公開整個分配狀態。

## Trace-driven simulation

在這個部分使用前面提到高保真度模擬器(high-fidelity simulator)去做實驗，主要是為了釐清以下三個問題:
* **現實世界工作負載中的調度干擾有多少，以及在生產中我們能夠承受的調度決策時間是多長？**
* **不同的衝突檢測和解決技術對真實工作負載有何影響？**
* **調度器能否利用訪問整個單元狀態的優勢？**

### Scheduling performance

圖11說明了調整 $t_{task}(service)$ 與 $t_{job}(service)$ 對於實際調度器的忙碌度的影響，在這張圖內在幾乎所有範圍內忙碌度都維持在比較低的範圍。這說明了以下兩件事:
* 調度器能夠有效地處理大部分工作負載，並且在不同時間段內都保持良好的性能。
* 即使在工作負載高峰期，調度系統也能夠保持穩定運行，這體現了系統的高效性和穩定性。

#### Scaling the workload

接下來是測試 Omega 在更大型的工作負載下的性能。
在圖12b中，當 $t_{job}(service)$ 接近10秒時，衝突率超過1.0，這意味著調度一個服務作業平均需要至少一次重試。

在大約同一時間點，我們無法滿足服務調度器的30秒作業等待時間SLO（圖12a）

儘管這些衝突率相對較高，我們的實驗表明，共享狀態的 Omega 架構可以支持需要幾秒鐘做出決策的服務調度器。我們還調查了每任務決策時間的擴展，發現我們可以支持
為 $t_{task}(service)$ 1秒（在 $t_{job}(service)$ 為 0.1 秒的情況下），導致衝突率約為 0.2。這意味著我們可以支持具有高單次每作業決策時間的調度器，以及具有長每任務決策時間的調度器。

#### Load-balancing the batch scheduler

接著測試 Omega 在 scalability 的作用，藉由增加多個 batch 的 scheduler 來測試是否可以降低整體的 scheduler 的繁忙度。

圖13 是使用 3 個 batch 的 scheduler 的來測試是否可以降低整體的 scheduler 的繁忙度。


我們實現了可擴展性的提升，大約達到 3 倍，將飽和點從約 4 秒的 $t_{job}(batch)$ 移動到 15 秒（圖13a）。同時，衝突率保持在較低水平（約 0.1），所有調度器在達到飽和點之前都滿足 30 秒的作業等待時間 SLO（圖13b）。

### Dealing with conflicts

接下來測試以下兩個方法對於性能的影響:

* **粗粒度衝突檢測**: 調度器的放置選擇如果在事務開始時同步本地單元狀態後目標機器發生了任何更改，將被拒絕。這可以通過在機器的狀態對象中使用簡單的序列號來實現。
* **全有或全無調度**: 如果它會導致任何機器過度承諾，整個單元狀態事務將被拒絕。其目標是支持需要集體調度的作業，或者需要所有任務運行才能執行有用工作的作業。


不出所料，這兩種選擇都導致了額外的衝突和更高的調度器忙碌度（圖14）。在使用細粒度衝突檢測時，對所有作業啟用全有或全無調度僅導致調度器忙碌度的略微增加（圖14a），但衝突率增加約2倍，因為重試現在必須重新放置所有任務，增加了再次失敗的機會（圖14a）。因此，這個選項應該僅在作業級別上使用。依賴粗粒度衝突檢測使情況更糟：虛假衝突導致衝突率和調度器忙碌度增加2-3倍。

顯然，增量事務應該是默認選項。

## Flexibility: a MapReduce scheduler

* 探討在 Omega 的架構下，新增一個特定用途的 scheduler 是否是一件容易的事，這邊以專門給 MapReduce 的 scheduler 為例。
* 專門化的 MapReduce 調度器可以在有額外資源可用時自動選擇工作者數量，以便加快作業完成速度。這個調度器通過利用閒置的集群資源來加速 MapReduce 作業。它觀察集群的整體資源利用情況，預測擴展當前和待處理 MapReduce 作業的效益，並根據某些策略分配部分未使用的資源給這些作業。

### Implementation

對於該調度器，考慮以下的三個策略:
* *max-parallelism*: 只要有收益，就不斷增加 worker 的數量。
* *global cap*: 集群利用率高於一定程度後，就停止調度 MapReduce 的任務。
* *relative job size*: 將 worker 的最大數量限制為初始請求數量的 4 倍。

### Evaluation


結果表明，50-70%的MapReduce作業可以通過使用機會資源來加速完成（圖15）。由於我們使用的是簡單的線性加速模型，對於尾部的巨大加速效果應持謹慎態度，但對於第80百分位的值，我們的信心更高。模擬結果預測，使用積極的最大並行化策略可以實現3-4倍的加速。

* 最大並行化策略：該策略顯示出最大的改進，通過不斷增加工作節點提供顯著的加速效果。
* 相對作業大小策略：該策略也表現良好，實現了相當可觀的加速效果，且更有可能實現，因為它需要構建的新MapReduce工作節點較少。而簡單模型未完全考慮新機器上設置工作節點的時間。
* 全局上限策略：在小型、未充分利用的集群D中，該策略的效果幾乎與最大並行化相當，但在其他地方幾乎沒有收益，因為集群利用率通常高於設置的60%閾值。

增加MapReduce作業的資源將導致集群的資源利用率上升，使作業更快完成，並釋放該作業的所有資源。這種效果會增加集群資源利用率的變異性（圖16）。


**我們的 MapReduce 調度器展示了在 Omega 系統中添加專門功能是非常簡單的，代表 Omega 本身相較於我們之前的系統具有更多的 Flexibility。**

## Conclusions
本篇專注於一種**使用並行性、共享狀態和樂觀並發控制的集群調度架構**，使用輕量級模擬與合成工作負載以及基於追蹤的高保真模擬 Google 生產工作負載的表現評估，顯示樂觀並發控制在共享狀態上是一種可行且有用的集群調度方法，雖然可能會比悲觀鎖做更多的工作，但在合理運行上的開銷是可以接受的，在消除隊列首阻塞和更好的可擴展性方面的結果也更好。

## Reference