# Abstract

- 目前單一集群 scheduler 架構難以應對日益增長的規模和快速 response 變化需求的挑戰。
- 這限制了新功能的部署速度，降低了效率和利用率，最終將限制集群的增長。
- 提出了一種新方法，使用並行性、共享狀態和無鎖的樂觀並行控制來解決這些需求。

### 主要內容

比較了該方法與現有集群 scheduler 設計的差異。
評估了 scheduler 之間的干擾程度及其在實踐中的重要性。
提出了一些技術來減輕干擾。
最後通過一個實際應用案例，展示了該方法的優勢，所有結果均基於真實的 Google 生產工作負載。

### 關鍵詞

- 集群調度 (Cluster scheduling)
- 樂觀並行控制 (optimistic concurrency control)

這段摘要介紹了本文的研究背景、提出的解決方案以及主要研究發現，並強調了新方法在應對集群 scheduler 挑戰中的潛在優勢。

# 1. Introduction

- 大型計算集群非常昂貴，因此需要充分利用。
- 通過在相同機器上運行多種工作負載，可以提高利用率和效率。
- 包括 CPU 和記憶體密集型作業、小型和大型作業、以及批次處理和低延遲作業 **(job)**。
- 這樣的整合減少了完成工作負載所需的硬體數量，但也使得調度問題變得更加複雜。
- 調度問題變得複雜的原因：
- 需要考慮更廣泛的需求和政策。
- 集群和工作負載持續增長，導致 scheduler 的工作量大致與集群規模成正比，最終成為可擴展性的瓶頸。

Google 過去的產品的job scheduler 已經歷了上述所有挑戰。
經過多年的發展，變得複雜且難以改變。
在重新設計這個 scheduler 的過程中，我們尋找了一種更好的方法。

### 傳統 scheduler 架構

- Monolithic scheduler 使用一個集中的調度演算法處理所有作業（如現有的 scheduler）。
- Two-level scheduler 有一個活躍的資源管理器，將計算資源提供給多個並行且獨立的 “scheduler frameworks”，如 Mesos 和 Hadoop-on-Demand。

### 問題

- Monolithic scheduler 難以靈活添加新政策和專門實現，且難以擴展到我們計劃的集群規模。
- Two-level 調度架構提供靈活性和並行性，但其保守的資源可見性和鎖定演算法限制了這些優勢，且難以安置難以調度的“挑剔”作業或做出需要整個集群狀態的決策。
### 解決方案

- 新的並行 scheduler 架構基於共享狀態，使用無鎖的樂觀並行控制，實現可擴展性和靈活性。
- 該架構已應用於 Omega，即 Google 的下一代集群管理系統。

## 1.1 Contributions
### 主要貢獻

提出了一個集群 scheduler 開發選項空間的輕量級分類法（§3）。
引入了一種使用共享狀態和無鎖樂觀並行控制的新 scheduler 架構（§3.4）。
比較了 monolithic、two-level 和共享狀態調度架構的性能，通過模擬和合成工作負載進行評估（§4）。
使用基於生產 scheduler 的代碼和實際工作負載跟踪數據，深入探討了共享狀態方法的行為（§5）。
通過一個實際應用案例展示了共享狀態方法的靈活性：新增一個 scheduler 利用全域集群利用率調整 MapReduce 作業 **(job)** 的資源分配（§6）。

# 2. Requirements

集群 scheduler 必須同時滿足多個目標：
高資源利用率
使用者指定的安置約束
快速決策
各種程度的“公平性”和業務重要性
同時需具備穩定性和高可用性
這些需求隨時間演變，隨著功能增長，單一的 monolithic scheduler 變得越來越難以新增政策。
隨著功能的增長，代碼積累，部分使用者依賴於系統內部行為的詳細理解來完成工作，這使得其功能和結構都難以改變。

## 2.1 Workload heterogeneity

硬體和工作負載的異質性在大型計算集群中很常見，是複雜性的主要驅動因素之一。

### 工作負載異質性

- 我們檢視了三個具有代表性的 Google 產品計算集群的工作負載異質性：
- 集群 A：中型且相當繁忙
- 集群 B：Google 目前使用的較大型集群之一
- 集群 C：最近發布了 scheduler 工作負載跟蹤的集群

所有集群運行多種job，有些是手動配置，有些是由自動系統配置，如 MapReduce、Pregel 和 Percolator。

### 工作負載劃分

集群的工作負載可以通過多種方式在不同的 scheduler 之間劃分。
在這裡，我們選擇了一種簡單的二分法：
- 長期運行的服務：提供最終使用者操作或內部基礎設施服務（如 BigTable）
- 批次作業：執行計算並完成

### 特徵




作業由一個或多個任務組成，有時多達數千個任務。
大多數（>80%）作業是批次作業，但大多數資源（55–80%）分配給服務。
服務作業通常運行時間更長，且任務數量比批次作業少。
批次作業通常較短，快速完成很重要，輕量級、低品質的放置方法效果很好。
長期運行的高優先級服務需要滿足嚴格的可用性和性能目標，這需要謹慎的放置以避免失敗並提供良好性能。
### 挑戰

我們需要一種 scheduler 架構能夠同時適應這兩種類型的作業，靈活支援job specific的policy，並能擴展到不斷增長的schedule工作量。
下一節將詳細探討這些需求以及滿足這些需求的一些方法。

# 3. Taxonomy

我們首先對集群 scheduler 必須解決的設計問題進行了簡短調查，然後檢視可能滿足這些需求的不同 scheduler 架構。

### 調度工作分配

- 調度工作可以通過以下方式在 scheduler 之間分配：
- load balance：與工作負載類型無關。
- 專用 scheduler：針對不同部分的工作負載分配專用 scheduler。
- 組合方式：結合以上兩種方法。

### 資源選擇

- Scheduler 可以選擇全部集群資源，或者選擇一部分資源以簡化決策過程。
- 前者增加了做出更好決策的機會，對於需要在接近滿負荷的集群中放置“挑剔”作業或依賴整體狀態的決策特別重要。
- 如果 scheduler 可以搶占現有分配的資源，而不僅考慮閒置資源，則放置任務的靈活性更大，但這會浪費掉被搶占任務已完成的一些工作。

### 干擾

- 如果 scheduler 競爭資源，可能會同時嘗試獲取相同資源。
- 悲觀方法：通過確保特定資源一次僅供一個 scheduler 使用來避免這個問題。
- 樂觀方法：檢測到衝突並撤銷一個或多個衝突的資源請求。
樂觀方法增加了並行性，但如果衝突太頻繁，可能會浪費大量調度工作。

### 分配粒度

- 由於作業通常包含許多任務，scheduler 可以採用不同的策略進行調度：
- 一種極端是原子性全有或全無的集體調度。
- 另一種極端是隨著找到資源逐步放置任務。
集體調度可以通過逐步獲取資源並在作業啟動前保留它們，但這會在此期間浪費這些資源。

### 跨集群行為

某些行為跨越多個 scheduler。
- 例如，實現各種公平性和對工作相對重要性的共同協議，特別是當一個 scheduler 可以搶占其他 scheduler 的任務時。
- 這些行為的嚴格執行可以通過集中控制來實現，但也可以依賴於涌現行為來近似。
- 技術如限制 scheduler 可用的優先級範圍，可以部分實現所需行為，並且通過事後審計確保符合集群範圍的政策。

### 調度架構比較

- 本文集中探討了以下組合的比較：
- Monolithic scheduler
- Statically partitioned scheduler
- Two-level scheduler (如 Mesos)
- Shared-state scheduler (如 Omega)


## 3.1 Monolithic schedulers

- Single instance scheduler 是我們比較的基準，它沒有並行性，必須在單一代碼庫中實現所有策略選擇。
- 這種方法在高性能計算 (HPC) 領域很常見，通常運行 single instance 調度代碼，對所有進來的作業應用相同的算法。

### 策略支持
- HPC scheduler，如 Maui 和其後繼者 Moab，以及 Platform LSF，通過多個加權因子計算總優先級來支持不同的策略。
- 計算後，scheduler 會大致按照優先級順序啟動作業。
- 另一種支持不同調度策略的方法是提供多條代碼路徑，對不同的作業類型運行獨立的調度邏輯。
- 然而，這比看起來要困難得多。
- Google 當前的集群 scheduler 實際上是 monolithic 的，儘管它經過多年優化，具有內部並行性和多執行緒來解決佇列首阻塞和擴展性問題。

### 挑戰

- 這增加了本已困難的任務：scheduler 必須在尊重優先級、每個作業限制和多個策略目標（如容錯和擴展到數千台機器的工作負載）的同時，將作業等待時間降至最低。
- 雖然這種方法非常成功，但我們發現難以在單一算法實現中持續支持廣泛的策略。
- 因此，基於這種考量，是我們轉向支持並行、獨立調度組件架構的主要動機。

## 3.2 Statically partitioned schedulers

- 大多數“雲計算” scheduler（如 Hadoop 和 Dryad 的 Quincy）假設它們擁有一組資源的完全控制權，通常部署在專用的靜態劃分集群上，或將單個集群劃分成不同部分以支持不同行為。
- 這導致了資源的碎片化和非最佳利用。
- 由於我們無法接受這種方案，本文不再深入探討這一選項。

## 3.3 Two-level scheduling

- 靜態劃分問題的一個明顯解決方案是動態調整分配給每個 scheduler 的資源數量，使用一個中央協調器來決定每個子集群可以擁有多少資源。
- 二級調度方法被許多系統採用，包括 Mesos 和 Hadoop-on-Demand (HOD)。

### Mesos

- 在 Mesos 中，集中資源分配器動態劃分集群，將資源分配給不同的 scheduler 框架。
- 資源以“資源提供”的形式分配，僅包含當前未使用的資源。
- 分配器通過僅向一個框架提供特定資源來避免衝突，並通過選擇提供的順序和大小來實現主要資源公平性 (DRF)。
- Mesos 假設 scheduler 決策快速且作業較小，當調度決策時間長或集群中有大量長期運行的服務作業時，效果會變差。

### 局限性

- Mesos 框架無法訪問整個集群狀態，因此無法支持搶占或需要訪問整個集群狀態的政策。
- 使用資源囤積實現群體調度，可能導致deadlock。

### YARN

- YARN 看起來也是二級調度器，但實際上是一個 monolithic scheduler 架構，因為資源請求由全局 scheduler 分配。

## 3.4 Shared-state scheduling

- Omega 使用共享狀態方法，允許每個 scheduler 完全存取整個集群，並使用樂觀並行控制來協調衝突。
- 消除了二級 scheduler 方法中的並行性限制和資源可見性限制，但可能需要重新進行衝突時的工作。

### 實施細節

- Omega 沒有中央資源分配器，所有資源分配決策在 scheduler 中進行。
- 每個 scheduler 都有一個私人本地副本的集群狀態，用於做出調度決策。
- 一旦做出放置決策，scheduler 會以原子方式更新共享的集群狀態。
- 如果發生衝突，則只有那些不會導致超額分配的更改會被接受。
- Scheduler 之間的操作完全並行，無需等待其他 scheduler 的工作完成。

### 策略實現

- Omega 的 scheduler 可以實現不同的策略，但必須在某些共同規則上達成一致，如機器是否已滿。
- 中央資源分配器簡化為持久資料儲存和驗證碼。
- Fairness 在 Omega 中不是主要關注點，更注重滿足業務需求。

### 性能可行性

- 共享狀態方法的性能可行性取決於衝突發生頻率和處理失敗的成本。
- Omega 的架構提供了靈活性，可以增加專門的 scheduler 和其他好處，如更好的資源利用率。

# 4. Design comparisons

- 為了理解不同方法之間的取捨，我們構建了兩個模擬器：
- 輕量級模擬器：驅動合成工作負載，使用從經驗工作負載分佈中提取的參數。
- 高擬真模擬器：重用 Google 過去產品集群的歷史workload數據，並重用大部分產品 scheduler 的代碼。

### 輕量級模擬器

- 通過一些簡化來提高速度和靈活性：
- 初始化集群狀態時，使用從相關跟蹤中提取的任務大小數據，但僅實例化足夠多的任務以利用大約60%的集群資源。
- 支援多種 scheduler 類型，初始僅考慮批次和服務兩種類型。
- 限制單個作業最多嘗試1000次調度，如果有任務仍未調度成功，則放棄該作業。
### 高擬真模擬器

- 使用從 Google 產品集群獲得的詳細workload數據，模擬實際集群操作。
- 支援 Omega 架構的詳細行為模擬，但運行速度比輕量級模擬器慢得多。

## 結果比較

- 我們在輕量級模擬器中比較以下幾種組合：
- Monolithic scheduler
- Two-level scheduling
- Shared-state scheduling (Omega)

## 4.1 Monolithic schedulers
### 單路徑

- baseline是單路徑 monolithic scheduler，使用相同的決策時間處理所有作業。
- 隨著決策時間增加，scheduler 繁忙度線性增長，作業等待時間相應增加，直到 scheduler 飽和，無法應對工作負載。

### 多路徑

- 多路徑 monolithic scheduler 為批次作業提供快速路徑，顯著降低平均作業等待時間和 scheduler 繁忙度，但批次作業仍可能因服務作業的慢速調度而阻塞。
-
## 4.2 Two-level scheduling: Mesos
### 架構

- 模擬基於 Mesos 設計，包含一個資源管理器和兩個 scheduler 框架。
- 資源以提供的形式分配，只有閒置資源會被提供，框架只看當前可用的資源。
### 結果

- 批次 scheduler 的繁忙度比 monolithic 多路徑情況高得多，因為服務 scheduler 的長決策時間鎖定了幾乎所有資源。
- 結果是，批次作業被迫重複嘗試調度，導致作業被放棄。

## 4.3 Shared-state scheduling: Omega
### 架構

- 使用 Omega 的共享狀態方法，每個 scheduler 可以看到整個集群狀態，並使用樂觀並行控制來協調衝突。
### 結果

- Omega 方法的作業等待時間和 scheduler 繁忙度與 monolithic 多路徑方法相當，顯示出較低的衝突和干擾。
- 隨著批次工作負載增加，Omega 模型可以通過增加 scheduler 的數量來提高可擴展性。

## 4.4 Summary
- 輕量級模擬器有助於比較不同的 scheduler 架構。
- Monolithic scheduler 無法擴展，儘管多路徑功能降低了平均調度決策時間，但批次作業仍會阻塞。
- Mesos 二級模型受限於悲觀鎖定，無法很好地處理長決策時間。
- Omega 共享狀態方法提供了具有競爭力和可擴展的性能，支持獨立的 scheduler 實現，並且在現實的操作點上干擾較少。


# 5. Trace-driven simulation

- 在比較了不同 scheduler 架構後，我們使用高擬真模擬器進一步探討 Omega 共享狀態方法的一些特性。
- 高擬真模擬器的核心是 Google 產品調度系統的代碼，並遵從任務放置限制。
- 我們使用詳細的工作負載跟蹤資料來驅動模擬，評估共享狀態設計在真實世界工作負載中的表現。

### 主要問題

- 我們旨在回答以下問題：
1. 在實際工作負載中，調度干擾有多大？我們能承受多長的 scheduler 決策時間？（§5.1）
2. 不同的衝突檢測和解決技術對實際工作負載有何影響？（§5.2）
3. 我們能否利用對整個集群狀態的訪問來提升調度決策？（§6）

### 簡化假設

- 儘管是高擬真模擬，該模擬器仍做了一些簡化：
- 不模擬機器故障，因為這只會對 scheduler 產生小量負載。
- 不模擬資源請求與實際使用之間的差異。
- 固定分配於初始請求大小（受跟蹤資料限制）。
- 禁用搶占，因為我們發現其對結果影響不大，但顯著減慢了模擬速度。

### 模擬器一致性

- 高擬真模擬器和輕量級模擬器的輸出通常一致。主要區別在於輕量級模擬器的干擾較少，這可能是因為它不支援放置限制和簡化了機器滿載的判斷。

### 結果確認

- 我們確認高擬真模擬器展示的趨勢與輕量級模擬器一致，這證實了輕量級模擬器實驗在一組共同假設下進行不同 scheduler 架構比較的合理性。

## 5.1 Scheduling performance

### 服務 scheduler 繁忙度

- 我們探討了服務 scheduler 繁忙度如何隨 $t_{job(service)}$ 和 $t_{task(service)}$ 變化：
- 服務 scheduler 繁忙度在幾乎整個範圍內保持較低，顯示 Omega 架構能夠很好地適應長決策時間的服務作業。
### 負載平衡

- 我們使用來自集群 B 的7天追蹤資料，探討共享狀態架構的性能：
- 當 $t_{job(service)}$ 達到約10秒時，衝突比率增加到1.0以上，意味著平均每次調度都需要至少一次重試。
- 服務 scheduler 繁忙度增加約40%，這是由於衝突造成的額外工作負載。

- 共享狀態 Omega 架構能夠支持決策時間為數秒的服務 scheduler，也能支持高達1秒的 $t_{task(service)}$

## 5.2 Dealing with conflicts
### 衝突檢測

- 我們探討了兩種衝突檢測和解決技術：
- 粗粒度衝突檢測：如果目標機器自同步以來有任何變更，則拒絕 scheduler 的放置選擇。
- 全有或全無調度：如果任何機器超額分配，則拒絕整個狀態交易。
### 結果

- 兩種技術都導致更多的衝突和更高的 scheduler 繁忙度。
- 全有或全無調度的衝突比率增加約2倍，應該僅在作業級別上使用。
- 粗粒度衝突檢測導致衝突比率和 scheduler 繁忙度增加2-3倍。

# 6. Flexibility: a MapReduce scheduler

本節介紹了一個範例，展示了 Omega 共享狀態架構如何增加新的 scheduler 以利用整個集群的利用率，來實現特定工作負載（例如 MapReduce 作業）資源分配的改進。
我們設計了一個專門的 MapReduce scheduler，它能夠識別閒置的資源，並在不影響其他服務的情況下，動態地將這些資源分配給 MapReduce 作業。

### 策略選擇

我們探索了三種資源分配策略：
- 最大並行度策略：盡量最大化並行運行的 MapReduce 作業數量。
- 全域上限策略：設置 MapReduce 作業的全域資源使用上限。
- 相對作業大小策略：根據作業大小動態分配資源，優先處理較小的作業以提高周轉率。

### 最大並行度策略

- 該策略目標是最大化同時運行的 MapReduce 作業數量：
- 當有新資源可用時，scheduler 立即將其分配給待處理的 MapReduce 作業。
- 結果顯示，這種方法能夠顯著提高資源利用率和作業完成速度。

### 全域上限策略

- 在這種策略下，我們設置了一個 MapReduce 作業的全域資源使用上限：
- 當達到上限時，新的資源不會分配給 MapReduce 作業，即使有閒置資源。
- 這種方法能夠控制 MapReduce 作業的資源消耗，避免其對其他關鍵服務的影響。
- 結果顯示，這種策略在控制資源分配和保證服務穩定性方面效果顯著，但會延長 MapReduce 作業的完成時間。

### 相對作業大小策略

- 該策略根據作業大小動態分配資源，優先處理較小的作業：
- 目的是提高作業的周轉率，使小作業能夠快速完成，而大作業在有多餘資源時得到分配。
- 結果顯示，這種策略在提高周轉率方面非常有效，特別是在有大量小型 MapReduce 作業的情況下。

### 結果分析

- 我們使用高擬真模擬器進行了測試，結果顯示 Omega 架構下的新 MapReduce scheduler 能夠靈活有效地分配資源，提高資源利用率和作業完成速度。
- 專門的 MapReduce scheduler 表現出比傳統 scheduler 更高的靈活性，能夠根據集群的實時狀態動態調整資源分配。

### 總結

這些實驗證明了 Omega 共享狀態架構的靈活性，可以輕鬆添加新的 scheduler，以優化特定類型的工作負載。
專門的 scheduler 可以根據實時狀態和策略調整資源分配，有效提高集群的整體性能。

# Conclusions

- 本文提出了 Omega，這是一種新的共享狀態、無鎖的樂觀並行控制 scheduler 架構，旨在應對大型計算集群的需求。
- 透過將共享狀態與樂觀並行控制結合，Omega 能夠顯著提高調度效率和可擴展性，並支援靈活的策略實現。
- 我們的實驗結果表明，Omega 架構在大多數操作點上能夠提供具有競爭力的性能，並且在處理多樣化工作負載時干擾較小。
- 透過設計專門的 MapReduce scheduler，我們展示了 Omega 在動態資源分配和提高資源利用率方面的靈活性。