Firmament：Fast, Centralized Cluster Scheduling at Scale（OSDI 2016）

首先介紹一下兩位作者，一作是 Ionel Gog，他現在是伯克利的博士後，關注於分散式、操作系統和大規模的數據處理。二作是Malte Schwarzkopf，提起Omega大家應該就比較熟悉，Omega這篇文章就是他在Google實習的時候發的文章，那篇集群的調度框架發展史就出自他之手。這個工作也是Malte 2015年畢業時的工作，他的畢業論文為：Operating system support for warehouse-scale computing，其中Firmament這個工作是畢設的一部分。

這個工作也是他們與Google合作的，並且Firmament也在計劃融合進kubernetes中，目前項目的名稱叫做poseidon。

看過調度框架發展史這篇文章的小夥伴應該知道，中心化的數據中心調度框架可以獲得很好的作業調度，但是在數據中心規模在不斷擴大的情況下，作業調度的時間開銷也在不斷增大，因為數據中心的機器變多了，要計算一個作業更適合在哪個機器上運行就需要花費更多的時間，這樣就會降低一些作業的響應時間，並且降低集群的資源利用率。

為了在保證好的作業調度的同時也擁有很低的調度延遲，這篇文章就提出了一個中心化的調度框架Firmament，它將作業調度的問題建模為最小費用最大流的問題來進行優化，該工作有以下特點：

• 中心化調度框架
• 擁有好的作業調度效果
• 保證次秒級的調度延遲
• 可以支持集群擴展到10000+台機器

上面提到，該工作將作業調度的問題建模為最小費用最大流的問題來進行優化，這個方法其實是在SOSP 2009就出現過，這篇文章Quincy：Fair Scheduling for Distributed Computing Clusters首次使用這種方法來解決調度問題，但是局限性是，Quincy這個工作對集群的擴展性支持的不太好。

將作業調度建模為最大流的方法如上圖所示（圖摘自作者的Slide），將每個作業和每台機器都抽象為一個節點，如果一個作業可以放在某台機器上運行，這兩點之間就有一個連線，表明流可以從作業節點流到機器節點，如果一個作業可以在多台機器上運行，該作業節點就可以和多台機器節點進行連接，每個連線上會標明費用（cost），這個費用表示將這個作業放在這個機器上運行的開銷，對於每台機器之後再抽象出來一個匯點。每個作業所在的節點就抽象為源點，每個源點有一個流，每個作業的流從源點流向匯點的就是演算法中的最小費用最大流的問題。如下圖所示。

Firmament的調度框架如下圖所示，首先通過調度的策略（Scheduling policy）對集群中的機器和提交的作業生成一個網路流圖，然後將這個圖提交給求解器（slover）來計算最大流，也就是最後的作業調度方法。

其中作者發現最消耗時間的地方就是求解器（slover）部分，因此嘗試了很多種演算法來優化這個部分，努力把時間給降低下來，作者嘗試了以下三種演算法：

• Cost Scaling
• Successive Shortest Path
• Relaxation

這個工作的目標是，通過中心化的調度，延遲能達到次秒級，經過實驗作者發現，在這三種演算法中Relaxation演算法最合適。

但是實驗過程中發現，在集群的資源利用率已經很高的情況下，Relaxation演算法的效果其實並不好。以下圖為例，假設集群中有四台機器，三種顏色的機器節點代表不同的資源利用率，顏色越深代表機器的資源利用率越高，在集群普遍資源利用率較高的情況下，演算法是優先將作業調度到負載較低的機器上，這樣的調度考慮了干擾和資源利用率等因素。以下圖的例子來看，在四台機器中，資源利用率最低的機器就是M2，但是此時機器M2隻能再接受一個作業去運行，那麼在這種情況下，另外3個作業就要返回去重新進行調度，這樣在集群資源利用率很高的情況下會導致很高的延遲。

作者通過實驗發現了，在集群利用率很高的情況下，雖然Relaxation演算法的延遲很高，但是Cost scaling演算法相較而言卻很好，因此作者就想到了一個idea，在solver中同時跑兩個演算法：Relaxation和Cost scaling演算法，這兩個演算法哪個先完成就用這個結果，並且把另外一個殺掉，這樣在集群負載較小時，就可以用relaxation演算法，在負載較高的情況下，就可以使用Cost scaling演算法，保證延遲不會太高。