深入解析 Kubernetes 排程器：搶佔機制的奧秘

– 13 分鐘閱讀

在 OpenAI，我花費數月時間開發 Kubernetes 排程器外掛，客製化搶佔行為，以更好地適應我們的機器學習（Machine Learning）工作負載。這是我職業生涯中最具挑戰性的專案。期間有無數次想要放棄，因為它實在太困難了。我堅持下來的唯一原因是我真的想了解排程器是如何運作的。我曾數次以為我真正理解了排程器，但後來才意識到，更深層次還隱藏著許多奧秘。現在我相信我完全（🤞）理解了 kube-scheduler 的運作方式，並想分享我的心得。

理解 kube-scheduler 確實非常困難，因為網路上鮮少資源解釋它的實際運作方式。排程框架的 README 提供了一個良好的概要，但並不夠完整。排程框架也是一個有些洩漏的抽象概念，因此若你想編寫一個非平凡的外掛，你真的需要了解排程器的內部運作。排程器的程式碼函式庫複雜，本文旨在揭示一切是如何結合在一起的。我將主要專注於解釋搶佔（Preemption），因為它是排程器中最少檔案與最複雜的部分。我希望這能降低未來探索者建立自己排程外掛的門檻。

對 kube-scheduler 的誤解

我一直天真地以為我知道 kube-scheduler 在背後是如何運作的，因為它「只是進行二進位封裝」。我錯得離譜，並且透過研究它的內部運作學到了很多。依我來看，Kubernetes 排程器的設計非常出色，是一個令人鼓舞的例子，展示了良好的外掛框架可以是多麼有效。

先備知識

我假設讀者是一位經驗豐富的 Kubernetes 使用者，並且瞭解從使用者角度來看 Pod 排程是如何運作的。如果需要，您可以閱讀相關檔案來複習 Kubernetes 排程（Scheduling）。

術語定義

首先，讓我們定義一些可能只有經驗豐富的 Kubernetes 使用者才會遇到的術語。

  • 提名 Pod（Nominated Pod）：被提名的 Pod p 是一個剛搶佔了一組較低優先順序 Pod(s) v 的 Pod。在這次搶佔之後，p 會在 v 中所有 Pod 終止後重新排隊以進行排程。「被提名的節點（Nominated Node）」是發生搶佔的節點。排程器會優先將 p 放置到它的被提名節點，但這並不保證。
  • PDB（Pod Disruption Budget，Pod 中斷預算）：一個 Kubernetes 功能，讓您可以請求排程器在最佳努力的基礎上避免搶佔某些 Pod。PDB 物件具有一個標籤選擇器，用於比對您希望保護免受搶佔的一組 Pod。

排程框架概述

一個正在排程的 Pod 會經歷排程框架的以下不同階段。每個階段的行為可以透過自定義外掛和 K8s 原生外掛進行修改。此外，每個階段（除了 Sort）可以有多個註冊的外掛，框架檔案提供了有關同一階段的多個外掛如何相互作用的明確語義。

當前正在排程的 Pod p 一旦從排程器的 Pod 佇列中彈出，就會進入排程週期（Scheduling Cycle）。該佇列是按 Pod 優先順序排序的。每個排程週期都是按 Pod 逐個序列執行，並嘗試將當前 Pod 分配給叢集中的某個節點。下面我將解釋您需要了解的有關排程框架的最小集合，以便理解搶佔是如何運作的。

CycleState 基本上是一個執行緒安全的鍵值儲存（Key-Value Store）。在每個排程週期開始時會建立一個空的 CycleState 物件，以儲存當前排程週期所需的任意狀態。每個排程週期有一個分享的 CycleState 物件，外掛通常使用它來儲存其內部狀態，以及作為多個排程階段之間的溝通管道。CycleState 物件必須實作深複製（Deep Copy）功能，我們很快會看到這對於提高搶佔的效率和準確性是必要的。

如果目前正在排程的 Pod 沒有可行的節點，則排程器將透過執行 PostFilter 外掛來嘗試搶佔。

前置過濾階段（PreFilter Phase）

注意：這是排程框架中最令人困惑的階段。它對於真正理解搶佔至關重要。

所有的 PreFilter 外掛在上面的 Filter 階段之前執行一次。PreFilter 外掛的主要目的是初始化外掛所需的任何自定義狀態，並將其持久化到 CycleState。這個自定義狀態稍後會被相應的 Filter 外掛提取並用於做出排程決策。在排程器尋找可以合法搶佔的 Pod 時，這個自定義狀態也可以在搶佔期間被修改。

如果您的 Filter 外掛使用任何依賴於 Pod 資訊的自定義狀態，您需要實作 AddPod 和 RemovePod PreFilter 回呼。這確保了搶佔遵循您的 Filter 外掛所施加的限制，並且不會做出導致違反您約束的搶佔決策。如果過濾階段失敗，PostFilter 外掛將執行。

您可以根據需要註冊多個 PostFilter 外掛，它們將按照宣告的順序執行。PostFilter 外掛通常用於實作搶佔，但理論上您可以執行任何您想要的程式碼。Kubernetes 預設提供的搶佔演算法是由 DefaultPreemption PostFilter 實作的。

繫結週期（Bind Cycle）

一旦排程器決定 Pod 應該落在特定節點上，就會將 Pod 傳送進行「繫結」。理解繫結階段對於這篇文章並不是必要的，但有一件重要的事情需要注意，即所有 Pod 繫結都是非同步進行的。這樣做是為了不阻塞主排程迴圈，並提高排程吞吐量。一旦 Pod 進入繫結迴圈，排程器就開始假設該 Pod 已經被排程。如果 Pod 繫結後來因為某種原因失敗，所有外掛都會呼叫 Unreserve 回復鉤子，以便每個外掛可以還原其自定義狀態的任何樂觀更新。

吃自己的狗食（Eating Your Own Dog Food）

我最喜歡 kube-scheduler 程式碼函式庫中一件事是，每個原生排程功能都是使用上述框架實作的。以下是一些例子：

  1. Kubernetes 中的資源請求透過 Fit 外掛工作，該外掛實作了一個 Filter 外掛，以排除缺少 Pod 所請求資源的節點。
  2. 汙點和容忍功能來自 TaintToleration 外掛，該外掛還使用 Filter 外掛以確保節點汙點得到尊重。
  3. 標準 Pod 逐出來自 DefaultPreemption 外掛，該外掛是使用 PostFilter 外掛實作的。

探討：預設搶佔

Pod 逐出是排程器中最複雜的功能，因為它以複雜與未記錄的方式將多個排程階段聯絡在一起。在深入細節之前，澄清預設逐出的目標是很重要的。

預設搶佔的目標是找到位於同一節點上的最佳受害者 Pod 集合，這些 Pod 需要被移除，以便讓更高優先順序的 Pod p 使用該節點。這個最小的受害者集合也應該盡量不違反 PDB，具有最小的 Pod 優先順序，並且在驅逐後也能產生最小的 Pod 變動。

決定要預先剔除哪些 Pods 可能會變得複雜，因為 Pods 之間可能存在排程共同依賴。例如，如果受害者 Pod 伺服器（Server）與共置的受害者 Pod 資料函式庫atabase）有必要的 Pod 相關性，那麼預設的預先剔除也應該在決定移除資料函式庫除伺服器（但反之則不然！）。還要記住，任何自定義外掛都可以引入任意的排程依賴。

在執行預先剔除時，排程器必須始終遵守所有這些排程依賴，剔除最小的 Pod 集合，最佳化以遵守 PDB，並且還要最小化被剔除受害者的優先順序。因此，kube-scheduler 會如此複雜也就不足為奇了。不過，這一切如何相互作用實在是相當天才。

Kubernetes 排程器的搶佔機制是一個複雜但極其強大的功能，它允許叢集在資源緊張時，優先排程重要的工作負載。透過深入瞭解排程框架的各個階段，以及預設搶佔的目標和運作方式，開發者可以更好地理解和客製化排程行為，以滿足特定的應用需求。無論是機器學習工作負載的最佳化，還是其他特殊場景的排程策略，理解 kube-scheduler 的內部運作都將為您帶來更大的靈活性和控制力。

在 Kubernetes 中，排程器（Scheduler）負責將 Pods 分配到叢集中的節點。當叢集中資源不足時，排程器會啟動搶佔（Preemption）機制，透過移除優先順序較低的 Pods，為優先順序較高的 Pods 騰出空間。本文將探討 Kubernetes 排程器的搶佔機制，剖析其控制流程、SelectVictimsOnNode 函式的運作方式，以及如何減少 Pod 變動，並解析快照（Snapshot）機制的額外好處。

搶佔控制流程：完整程式碼追蹤

以下是 Pod p 成功搶佔時，排程週期中每個重要步驟的完整程式碼追蹤：

  1. 排程器啟動： 排程器從優先順序佇列中取出 Pod p，開始進行排程週期。
  2. 叢集快照： 排程器在當前時刻對叢集中所有節點物件和 Pod 物件進行快照。
  3. 預處理階段（PreFilter）：
    • 所有 PreFilter 外掛都會執行，部分外掛可能會將其初始自定義狀態持久化到 CycleState 中。
    • 任何 PreFilter 外掛都有權力宣告失敗，導致整個排程週期中止，針對 Pod p。
  4. 過濾階段（Filter）：
    • 所有過濾器外掛在叢集中的每個節點上平行執行，評估節點是否適合 Pod p。
    • 如果所有過濾器外掛對特定節點都透過，則該節點被視為可行（Feasible）。
  5. DefaultPreemption PostFilter 執行： 如果沒有可行的節點，DefaultPreemption PostFilter 會啟動：
    • 搜尋驅逐候選者： findCandidates 搜尋合法的驅逐候選者，這些候選者的移除將允許優先者 p 進行排程。
      • 驅逐候選者是指位於同一節點上的一組受害者 Pod，如果將其移除，將允許 p 在該節點上進行排程。
      • DryRunPreemption 會搜尋以找出叢集中所有可能的驅逐候選者。它透過在叢集中的每個節點上平行執行 SelectVictimsOnNode 函式來實作這一點。每個平行呼叫都會獲得自己獨立的節點和 CycleState 物件的副本。
      • 每次對 SelectVictimsOnNode 的呼叫如果存在驅逐候選者 C，則會回傳該候選者 C 針對其指定的節點。
    • 選擇最佳驅逐候選者： SelectCandidate 從 findCandidates 回傳的列表中選擇最佳驅逐候選者 B。
      • 驅逐候選者是根據這些標準選擇的，這些標準偏好驅逐違反 PDB（Pod Disruption Budget）的次數較少、優先順序較低的 Pod 等候選者。
    • 執行搶佔： prepareCandidate 執行 B 的實際搶佔。
      • 刪除屬於 B 的受害者 Pod，並在必要時清理受害者 Pod 的提名。
      • 發出 Kubernetes 被搶佔事件。
  6. PostFilter 回傳節點： 如果 PostFilter 外掛成功地進行了搶佔，則回傳指定的節點 nn。
  7. 更新 Pod 狀態： 排程器將 p 的 .status.nominatedNodeName 欄位設定為 nn，並且還在排程器的本地快取中追蹤提名。
  8. Pod 重新排隊： Pod p 被重新排隊，因為在被搶佔的受害者終止並釋放其資源之前，無法進行排程。

深入理解 SelectVictimsOnNode 函式

SelectVictimsOnNode 函式搜尋在特定節點 n_i 上可能發生的最佳驅逐，以便 p 能夠進行排程。傳遞給此函式的節點 n_i 和 CycleState s_i 物件是深層複製，因此可以安全地進行修改。這使得排程器能夠平行地對所有節點執行 SelectVictimsOnNode，以搜尋整個叢集中可以合法搶佔的內容。

以下邏輯用於確定當前節點上的最佳驅逐：

  1. 移除低優先順序 Pod： 所有優先順序低於 p 的 Pod 都會從複製的節點 n_i 中移除。所有這些被移除的 Pod v_j 都被視為可能的受害者。
    • 所有 PreFilter RemovePod 回呼都會以 ( v_j, n_i) 的形式呼叫，適用於所有排程外掛（包括自定義和原生外掛）。這會通知每個外掛某個 Pod 被移除，並給他們機會更新儲存在副本 s_i 中的自定義狀態。
  2. 嘗試還原 Pod： 這些被移除的 Pod 逐一進行迭代，並嘗試新增回複製的節點 n_i。
    • 受 PDB 保護的 Pods 會首先嘗試還原。然後會嘗試還原優先順序較高的 Pods。
    • 當嘗試還原每個單獨的受害者 Pod v_j 時，排程器將：
      • 重新執行所有預過濾器 AddPod 回呼，使用 ( v_j, n_i) 針對所有排程外掛（包括自定義和原生）。這會通知每個外掛有新的 Pod 被新增，並給予外掛更新其儲存在副本 s_i 中的自定義狀態的機會。
      • 然後所有的過濾器外掛都以 ( p, n_i, s_i) 作為輸入執行。如果它們都透過，那麼還原 v_j 的嘗試成功了，因為我們已經確認 p 可以在節點上排程，即使 v_j 存在。
    • 如果 v_j 已成功還原（或在 kube-scheduler 的術語中稱為“暫緩”），則它將不會包含在 SelectVictimsOnNode 回傳的驅逐候選者 C 中。
  3. 回傳受害者： 所有最初被移除但未能還原的 Pod 被作為受害者回傳到驅逐候選者 C 中。

減少 Pod 變動：提名 Pod 保留機制

排程器會欺騙所有過濾器外掛的實作，讓它們認為該節點上的提名 Pod 已經被排程。只有在提名 Pod 的優先順序大於或等於 p 時，排程器才會假裝該提名 Pod 已被排程。

已提名的 Pod 會重新排隊以進行排程，並且尚未進入繫結迴圈。因此，如果沒有這個隱藏的保留系統，大多數已提名的 Pod 將會經歷重複的波動，因為佇列中任何在前面的 Pod 都可以在其受害 Pod 終止後搶走它們的位置。

使用 p 的優先順序來決定為哪些已提名的 Pod 保留空間可以減少 Pod 的波動，因為這可以防止 p 現在進行排程，然後被更高優先順序的已提名 Pod 重新搶佔。這種最佳化是一個效率提升的例子，同時也創造了一個抽象漏洞。如果開發者想要實作一個不總是根據優先順序進行搶佔的自定義搶佔演算法，這個保留系統將會默地失效。

即使所有過濾器外掛在新增了提名的 Pod 後都透過，實際上在將節點視為可行之前還有一件事需要驗證。

假設我們正在執行一個網站，我們的伺服器 Pod 需要與資料函式庫od 共同放置，以便提供流量，我們透過所需的 Pod 之間的親和性（Affinity）來確保這一點。由於排程器對過濾器外掛謊稱所有提名的 Pod 都已排程，因此 Pod 之間的親和性過濾器外掛會高興地批准將伺服器 Pod 排程到資料函式庫名節點上。

然而，請記住，像資料函式庫的提名 Pod 並不保證會在其提名的節點上進行排程。因此，我們不能僅允許伺服器 Pod 現在排程到這個提名節點並將其傳送進行繫結，因為這樣做可能會違反所需的 Pod 之間的親和性。

這就是為什麼排程器還確保所有過濾器外掛在沒有提名 Pod 的情況下也能透過。這確保了一個節點的提名 Pod 實際上並不需要在該節點上合法排程 p。

快照的額外好處

在每個排程週期開始時拍攝所有 Pods 和 Nodes 的快照還有其他好處：

  • 確保一致性： 確保所有外掛都能看到並根據相同的叢集狀態進行操作。
  • 降低 Etcd 負擔： 減少對 Etcd 的頻繁讀取操作，降低負擔。
  • 提升效能： 改善排程的吞吐量和延遲。
  • 實作最佳化： 給排程器提供了一個實作某些最佳化的途徑。例如，所有外掛都被欺騙以為正在繫結的 Pods 實際上已經被排程，因為排程器透過快照對此撒謊。

Kubernetes 排程器的搶佔機制是一個複雜但至關重要的功能，它確保了高優先順序 Pods 能夠在資源受限的叢集中獲得所需的資源。透過深入瞭解其運作方式，開發者和維運團隊可以更好地管理和最佳化 Kubernetes 叢集，確保應用程式的穩定性和效能。

在 Kubernetes 排程器（Scheduler）的程式碼函式庫作，讓玄貓（BlackCat）受益匪淺，成為一位更出色的程式設計師。這段時間裡，玄貓（BlackCat）內化了一些關鍵教訓，在此分享，希望能對其他開發者有所啟發。

擁抱源程式碼：深入理解技術的根本

所有現有的 Kubernetes 排程器檔案和線上的深度探討文章，都無法提供撰寫排程外掛所需的詳細程度。因此，必須接受一個事實：如果想要參與新的或邊緣專案，通常需要直接閱讀程式碼。玄貓（BlackCat）大部分的學習都來自於閱讀 scheduler-plugins 和 kube-scheduler 的源程式碼。

閱讀源程式碼不僅能幫助理解技術的底層實作，還能學習到優秀的程式設計風格和架構設計。透過分析 Kubernetes 排程器的源程式碼，玄貓（BlackCat）學習到如何設計可擴充套件、高效能的系統，以及如何處理複雜的併發問題。

Kubernetes 社群：互助與知識的寶函式庫Kubernetes 社群充滿了樂於助人和知識淵博的人們。當玄貓（BlackCat）在理解被提名的 Pod 的排程時遇到困難，聯絡了 Wei，幾個小時內問題就獲得解決。維護者如此願意幫助網路上的陌生人，實在令人驚訝。

因此，如果遇到難題或有非常具體的問題，建議加入 Kubernetes Slack 工作區。在這裡，可以向社群成員尋求幫助，獲得寶貴的建議和指導。社群的力量是無窮的，它能夠加速學習和解決問題的過程。

設計良好的框架：力量的源泉

玄貓（BlackCat）對排程外掛框架的通用性、可擴充套件性和強大功能印象深刻。每個 Kubernetes 排程功能仍然是使用這個幾乎已經有 10 次版本更新的框架實作的！允許開發者在同一框架上構建，為自定義開啟了無限的可能性，而無需分叉排程器。

排程外掛框架激勵玄貓（BlackCat）在設計自己的框架時，花更多時間尋找合適的核心抽象。一個設計良好的框架能夠簡化開發流程、提高程式碼的可重用性，並降低維護成本。

快照：一致性與效能的平衡

在開始開發排程外掛之前，玄貓（BlackCat）幾乎沒有考慮過使用快照（Snapshot），並將其視為一種僅用於複雜任務的技術，比如實作 MVCC（多版本併發控制）。現在，玄貓（BlackCat）已經開始在工作的其他系統中更多地使用快照，並且非常喜歡它。

快照是一種同時引入一致性和提高效能的技術。透過建立資料的快照，可以在不影響當前操作的情況下，對資料進行讀取和分析。然而，快照並非萬能，因為並非所有系統都能接受快照所帶來的過時資料的權衡。在使用快照時，需要仔細評估其對系統一致性和效能的影響。

在 Kubernetes 排程器程式碼函式庫作的經驗，讓玄貓（BlackCat）深刻體會到閱讀源程式碼、參與社群、設計良好框架和應用快照的重要性。這些教訓不僅適用於 Kubernetes 開發，也對軟體工程師在其他領域的實踐有啟發。透過不斷學習和實踐，才能成為更出色的程式設計師，並為社群做出更大的貢獻。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。