Poseidon：Firmament與Kubernetes的融合

Poseidon這個項目是為了將 Firmament 融合進 Kubernetes 而產生的項目，是華為的 Cloud PaaS Platform 團隊與 Ionel Gog 和 Malte 一起推動的。之前的文章中有介紹過Firmament這個工作，傳送門如下：Firmament：Fast, Centralized Cluster Scheduling at Scale（OSDI 2016）。

Poseidon是希臘神話中的海神的名字，可能因為Firmament這個項目將作業調度問題建模為網路流的優化問題，並用的最小費用最大流演算法進行求解，所以用了海神的名字。

Poseidon項目的github傳送門如下：https://github.com/kubernetes-sigs/poseidon

Kubernetes是支持第三方調度器插件的，而Firmament本身是用C++寫的，Kubernetes是用Golang寫的，所以Poseidon起的是橋樑的作用，把Firmament調度器集成到Kubernetes中。之前的文章有介紹過Firmament，它是將集群中的機器和負載都建模為網路流，並用最小費用最大流演算法來對這個網路流進行求解來做出調度決策。在本文中，主要介紹Firmament的原理，它與pod-by-pod調度程序的區別，它與k8s的默認調度器的不同，以及Poseidon的架構。

Pod-by-pod scheduling

pod-by-pod調度程序（例如 Kubernetes scheduler）一次只處理一個pod，這種調度程序很適合併行化，但是也有以下三個缺點：

• Scheduler會提前提交一個pod的放置方案，這樣的話限制了其他等待被調度的pod的選擇
• 在多個pod之間很難進行work的分攤，因為這些pod是單獨進行調度的
• 重新調度需要外部調度邏輯來決定哪些pod需要重新調度

Batching scheduling

可以通過批處理來解決pod-by-pod調度程序的前兩個缺點。通過同時處理多個pods來對它們同時進行調度，從而找到最好的trade-off的方案。對這個想法進行進一步的擴展就是考慮所有的pods，並且根據需要來對pod進行搶佔或遷移來滿足調度的目標，該方法解決了pod-by-pod調度的第三個缺點，並且重新調度還有一些潛在的優勢，例如可以提高應用級程序的性能，避免由低優先順序任務引起的資源浪費等。

Firmament是基於網路流的調度程序，它使用了高效的批處理技術，即用最小費用最大流的演算法來進行優化，這種優化再加上Firmament的調度策略可以達到很好的pod放置效果。

Firmament

Firmament是一個基於網路流的調度程序，它將負載（運行和提交的pod）和集群（例如：節點、機架）建模為網路流。Firmament根據其調度策略並通過集群中發生的事件（例如：task的提交、完成，節點故障等）和監控信息（例如：資源利用率）來對網路流進行修改，之後Firmament運行最小費用最大流演算法求解器來找到好的調度方案。

網路流是一個有向圖，圖中的邊將來自源點（即pod節點）的流匯聚到匯點S，每個邊上都會有限制條件，比如流經這條邊的成本和這條邊最大可承受的流量等，並且也會有調度時的偏好信息。圖1展示了一個有五個pod和四個node的集群網路流圖，圖的左側每個pod節點Pi都代表了一個單位流，所有的流最終都要匯聚到匯點S中，以尋求一個優化問題的可行解。

為了使網路流到達匯點S，來自Pi的流可以通過機器節點Nj，這意味著將pod Pi調度到節點Nj上運行，或者，流可以通過不進行調度的聚合器節點（U）來直接到達匯點S。在上圖中，pod對調度的偏好通過連接到機器節點的邊的cost來表示，讓作業不進行調度或在運行時不進行搶佔的代價是pod節點指向聚合器節點（U）邊的cost，給定這麼一個網路流圖，使用最小費用最大流的求解器求出最優的網路流。

在圖1中，pod僅對機器節點Ni、機架節點Rj、不進行調度的聚合器節點U或表示集群C的節點有直接連線，但是，可以對調度策略進行自定義，例如像機架節點Rj，可以將具有類似資源或機器需求的pods進行分組。

Firmament提供了一個策略API來配置調度策略，可以包含例如作業干擾、公平性、優先順序搶佔等。Firmament目前支持多種調度策略：

• 數據局部性策略，用於權衡pod數據局部性與pod搶佔成本和pod調度等待時間 ；
• 避免co-location的pod相互干擾的策略；
• Network-aware策略；
• 基於running pods數量的負載均衡策略。

將Firmament調度器接入Kubernetes是因為它與默認的k8s調度器相比有以下優點：

• 它使用最小費用最大流演算法對policy進行了全局的調度策略優化，以最低的成本進行pod放置；
• Firmament支持作業的重新調度，在每個調度程序運行時它會考慮所有的pods，包括正在運行中的pods，並可以對pod進行遷移或驅逐；
• Firmament在進行pod放置時使用集群利用率的統計信息；
• Firmament支持多種調度策略，並為實施新策略提供了一個簡單的介面。

Poseidon

Firmament是開源的，可以在https://github.com/camsas/firmament找到。為了能夠在Kubernetes集群中部署Firmament，必須解決以下三個問題：

• Kubernetes提供了豐富的API，包括job、replica sets、deployments等，而Firmament的API由分組到jobs中的tasks組成，需要在Kubernetes和Firmament的API之間架起一個橋樑；
• Firmament是用C++實現的，因此需要一個Kubernetes的C++客戶端或使用Go客戶端與Firmament進行通信；
• Firmament在對pod進行調度時需要Kubernetes集群利用率的統計信息。

Poseidon 項目就是用來解決上述問題的，Poseidon 是用 Go 實現的，並充當 Kubernetes 集群和 Firmament 之間的橋樑。圖2是 Poseidon、Firmament 和 Kubernetes 的融合框架，Poseidon 監視 Kubernetes 集群的更新，將 pods 的信息轉換為與 Firmament 兼容的信息（例如 tasks & jobs），它還接收調度決策並通知 Kubernetes server API 來進行 pod 綁定。此外，Poseidon 提供了一個用來接收 Heapster 利用率統計信息的 gRPC 服務，這些統計信息從每個 pod 轉換為每個 task 的統計，並轉發到 Firmament 調度器。

圖3是 Poseidon 的詳細設計圖。Poseidon 有兩個線程（即 node watcher 和 pod watcher）從 Kubernetes 集群接收更新，這些 watchers 隊列會轉換成為定製化的 keyed 隊列，這些keyed 隊列將具有相同 key 的所有更新組合在一起（即對 pod 的更新按照唯一的 pod 標識符進行分組，對 node 的更新按照唯一的 node 標識符進行分組）。Node 和 pod 隊列由兩個 pool 組成：node worker pool 和 pod worker pool，這些 pool 將更新轉換為 Firmament 的特定信息，並與 Firmament 的 gRPC 服務進行通信，這個服務期望通過 task 和 node 狀態轉換事件（task 的提交、完成，節點故障等）來通知。有關更多的詳細信息，請參考Firmament gRPC服務。

Firmament 不會一次只調度一個 task，而是會考慮每個調度器的所有負載，Firmament 調度器連續運行，並在每次調度時考慮集群在前一次調度期間所發生的改變（例如，task 提交、完成），因此 Poseidon 有一個調度循環，在前一輪完成時開始 Firmament 調度。

最後，Poseidon 提供了一個簡單的 gRPC 服務，它從 Heapster Poseidon 接收器接收利用率統計信息。我們不直接從 Heapster 向 Firmament 發送統計信息是因為必須將這些統計數據從Kubernetes 的概念（如 pod）映射到 Firmament 的概念（如task），我們希望保持 Firmament gRPC 調度程序服務不受任何集群管理系統特定概念的影響，因此 Poseidon statistics gRPC 服務負責完成這種映射。

Firmament gRPC service

Firmament scheduler gRPC service 是一個集群不可知的調度程序，它接收 task 和 node 事件和利用率統計信息。圖4是 Firmament 工作流程，它首先使用接收到的集群和負載信息定義一個網路流圖，之後將這個圖提交給最小費用最大流的求解器來求解最優解，求解之後， Firmament 可以從中提取到task放置方案。

Poseidon Heapster sink

Firmament 的許多調度策略都是利用真實的集群利用率信息做出的決策，在與 Kubernetes 進行集成中，Poseidon 使用 Heapster 來獲取信息，最終發送給 Firmament，如圖5所示。

接收器創建一個處理Heapster利用率統計信息的線程，該線程將統計信息發送到兩個正在運行的sender之一，這些sender線程維護與Poseidon utilization stats gRPC服務的連接並將數據轉發給Poseidon。