前言

近日，數據庫和數據工程領域的頂級學術會議之一 ICDE（IEEE International Conference on Data Engineering）在荷蘭烏得勒支舉行，字節跳動基礎架構團隊的論文《Resource Allocation with Service Affinity in Large-Scale Cloud Environments》成功入選。

背景與現狀

隨著云計算的普及與迅速發展，微服務架構已被越來越多的互聯網公司采用。在此架構中，應用被拆分為多個微服務，每個服務負責特定功能，它們通過網絡協議（RPC）高效連接，實現數據傳輸和通信。然而，雖然微服務架構提供了多種優勢，如可擴展性、輕量級特性及故障隔離等，但其頻繁的網絡互動也不可避免地增加了網絡負擔，從而導致更高的延遲，并增加了系統的不穩定性。

為了解決這些挑戰，字節跳動基礎架構的服務框架團隊、編排調度團隊和 ByteBrain 團隊合作提出了微服務親和性部署的解決方案，它的核心思路是將有強依賴關系的服務進行同機部署，減少它們之間的調用開銷，從而實現性能和成本的優化。具體而言，它包含 2 個操作：

• 通過策略性地重新部署服務的 Pod，盡量將頻繁通信的服務 Pod 部署在同一臺機器上（Collocation）；
• 通過調整網絡通信協議，采用本地通信方式（IPC）替代網絡通信，顯著降低網絡開銷，減少請求延遲，增強系統的穩定性。

與直接將微服務合并為更大的服務相比，親和性部署方案仍保留了微服務架構中服務的獨立性、敏捷性和易擴展性等優勢。下圖展示了通過模擬實驗的初步驗證結果：親和性部署和本地通信策略（Collocation+IPC）顯著優化了端到端延遲和請求失敗率。

盡管上述方案展示了顯著的潛在收益，但在實際落地過程中仍會面臨諸多工程和算法上的挑戰。其中比較關鍵的挑戰之一就是如何有效地編排 Pod，以便盡可能多的相關服務可以部署在同一臺機器上，從而最大化可以通過本地化通信處理的流量。

為了克服這一問題，字節跳動基礎架構團隊進行了數學化建模，提出了一個考慮服務親和性的 Pod 調度問題 RASA（Resource Allocation with Service Affinity）。

注：本文中所指的服務間親和性即服務間流量的大小

從理論到實踐的挑戰

RASA 問題本質上是一個二次調度（或全局調度/重調度）問題，旨在在滿足特定約束條件下，重新編排 Pod 以最大化全局可本地化的流量（即最大化服務間的親和性）。但隨著字節跳動業務規模的迅速擴張和復雜度提升，服務數量日益增多，每個服務又包含多個運行中的 Pod，決定這些 Pod 的最佳擺放位置以最大化本地通信流量并非易事：

• 在制定 Pod 的擺放策略時，我們不僅需要考慮各種約束條件，還要綜合考慮不同服務之間的依賴關系。在線上環境中，服務之間如同網狀結構相互連接，它們需要頻繁通信，這種流量關系稱為“親和性”。在這種情況下，要優化某個服務，如服務 A，常常需要重新調度多個其他親和服務的 Pod，這不僅涉及到資源的約束（如可容納的 Pod 數量），還要考慮不同服務Pod的放置比例，以確保最大化本地化流量。在這樣復雜的環境中，設計一個既考慮到多種約束又能最大化本地化流量的算法極具挑戰。
• 在字節跳動內部，由于線上服務數量眾多、關系復雜，且各服務的 Pod 數量龐大，重調度的算法求解時間也成為一大限制（求解時間過長可能導致由于集群狀態的變化而使得算法得出的部署方案無效）。在這種背景下，傳統元啟發式算法在處理大規模且約束條件及目標函數復雜的情況下，難以在短時間內有效地給出優質解。

因此，在解決 RASA 問題時，其復雜的特性和龐大的求解規模對算法提出了嚴峻的挑戰。然而，常見的啟發式和元啟發式算法往往難以兼顧求解時間和解的質量，這種雙重要求使得尋找高效且有效的求解方法變得尤為重要。

微服務親和性部署二次調度方案

下圖展示了字節跳動基礎架構團隊所提出的方案的完整優化流程：

• 首先，控制器會收集集群的關鍵數據，包括服務列表、機器列表及流量信息等（步驟 1）；
• 接著，控制器將這些數據打包并發送至算法模塊（步驟 2）；
• 算法模塊完成求解后，會將新的 Pod 排布方案及 Pod 遷移方案回傳給控制器（步驟 3）；
• 最后，控制器執行 Pod 遷移方案（步驟 4）。

所有 Pod 遷移完成后，集群的 Pod 排布將與 RASA 算法推薦的新排布一致，從而實現流量本地化的優化。

下面，我們將主要介紹圖中算法模塊的設計和實現。我們開發了一種高效的親和性調度算法（下文簡稱 RASA 算法），該算法能夠處理大規模輸入，并且能夠獲得高質量的解決方案。

RASA 算法的核心思想主要基于兩個方面：

• 利用親和性關系圖的分割和算法選擇技術來簡化問題規模并加速求解過程；
• 通過對子問題運用基于數學規劃求解器（Solver）的方法，以提升解的質量，獲取高本地化流量比例的解。

服務分割

在字節跳動的線上環境中，集群內可能存在上百甚至上千個微服務。如果對所有微服務進行重調度計算，將導致計算量極大。為此，我們提出了一套多階段服務流量圖分割技術。這種技術依據流量圖的特性，對服務進行多次分割，部分分割后的服務集合可能會被直接過濾丟棄，將原問題劃分為多個規模更小的子問題。

在這些分割過程中，最關鍵的是主親和性分割（Master-Affinity Partitioning）。該策略基于一個觀察：大部分服務對間的流量非常小，合并它們的價值并不高，因此這些服務對無需納入重調度算法考慮。例如，在一個約有 40 個微服務的小集群流量分布案例中，前五個服務間的流量就占了總流量的 95% 以上。只需考慮這五個服務的合并，就能實現大部分流量的本地化，從而顯著降低問題的規模。

除了主親和性分割外，我們還引入了以下幾種分割技術，以進一步優化子問題的求解效率和效果：

• 非親和性分割：這種分割策略旨在排除不存在流量關系的服務。
• 兼容性分割：此分割旨在識別可能互相沖突或不兼容的服務，確保分割后的每個子問題包含的服務都能和諧共處。
• 均衡分割：旨在進一步減少每個子問題的規模，同時最小化由于服務分割可能引起的最優性損失，并且嘗試均衡各個子問題的計算負載。

通過這些精細化的分割策略，我們能夠有效地管理大規模集群中的服務調度問題，優化資源利用率，提升服務性能。

調度算法池

在調度算法池中，為了確保獲得高質量的解決方案，我們引入了兩種基于數學規劃求解器的算法：列生成算法（Column Generation Algorithm，CG）和混合整數規劃求解算法（Mixed Integer Programming，MIP）。這些算法能夠有效處理涉及整數變量的問題，并通過系統性的和技巧性的遍歷解空間來尋求最優解，因此常常能獲得高質量的解決方案。

以下是針對 RASA 問題設計的混合整數規劃表達式。利用這一表達式，我們開發了 CG 和 MIP 兩種算法，用于精確求解子問題：

算法選擇

在處理分割后的子問題時，每個子問題的求解需要在一分鐘內完成。盡管服務分割技術已經降低了每個子問題的規模，但子問題中的變量數目可能仍然達到上千或上萬，因此無法保證所有基于求解器的算法在限定時間內都能得到最優解。實驗表明，對于一部分子問題，列生成算法（CG）在一分鐘內獲得的解的質量（以可本地化的流量大小來評估）優于混合整數規劃算法（MIP），而對于其他子問題，則是 MIP 表現更優。

為了進一步提高求解效率并在有限時間內獲取更優解，我們引入了算法選擇策略，即針對每個子問題在{CG, MIP}中選擇更適合的算法。我們利用每個子問題的特征——包括微服務數量、機器數量和服務間的流量關系——構建特征圖。在這些圖中，微服務作為節點，服務間的流量大小作為邊權，節點還包含服務本身的特征信息。

通過對特征圖進行隨機采樣，我們構造了訓練樣本，并利用這些樣本訓練了一個基于圖卷積網絡（GCN）的二分類器。這個分類器的任務是為每個子問題選擇最合適的求解算法（CG 或者 MIP）。分類器的訓練過程中，我們特別注意模型的泛化能力和分類精度，以確保在實際應用中能夠有效地指導算法選擇。

在獲得每個子問題的最佳求解算法后，我們分別用選定的算法獨立求解每個子問題。求解完成后，我們將所有子問題的解合并，形成最終的解決方案。通過這種方式，我們不僅提高了求解的效率，還優化了解的質量，從而有效支持了大規模集群環境下的服務調度需求。

Running Example

為了幫助讀者更深入地理解 RASA 算法，我們在此提供一個簡單的實例，全面展示算法的工作過程。

我們的示例中包含 15 個微服務，它們之間的流量關系如上圖最左側所示，其中邊權代表流量值，藍色節點表示該微服務只能部署在類型為 X 的硬件上，綠色節點表示只能部署在類型為 Y 的硬件上。服務分割的具體步驟如下：

• 第一步：非親和分割（Non-Affinity Partitioning） —— 移除那些沒有親和關系的微服務，因為重調度這些服務的容器不會帶來收益。
• 第二步：主親和分割（Master-Affinity Partitioning） —— 分析每個節點的流入和流出總流量，并進行排序，選出流量占比超過 90%的前幾個微服務。在我們的例子中，選擇了占比為 94.8%的前 6 個微服務。這一步將問題規模縮減為原來的一半。
• 第三步：兼容性分割（Compatibility Partitioning） —— 因為 X 和 Y 類型硬件的微服務不能共同部署在同一臺機器上，按硬件要求進一步細分，將問題規模進一步縮小。在此示例中，原先的 6 個微服務問題被分解為兩個子問題，分別包含 2 個和 4 個微服務。
• 第四步：損失最小化均衡分割（Loss-Minimization Balanced Partitioning） —— 對于仍然規模較大的子問題，例如一個包含 4 個微服務的子問題，進行最小權重均衡分割，將其細分為兩個各包含 2 個微服務的子問題。

完成服務分割后，只需為這些分割結果分配適當的機器，即可形成幾個獨立的 RASA 問題輸入。通過這種多階段分割策略，原本需要解決的 15 個微服務排布問題被有效地分解為 3 個僅包含 2 個微服務的子問題，且這些分割過程中的流量損失僅占總流量的 12%，實現了在最優性損失微小的情況下極大提升求解速度。

當前，我們面臨多個子問題和調度算法池中的 CG（Column Generation Algorithm）與 MIP（MIP-Based Algorithm）兩種算法，接下來的任務是為每個子問題選擇一個最適合的調度算法進行求解。

• 構建每個子問題的特征圖：首先，我們為每個子問題構建特征圖。這一特征圖是在流量關系圖的基礎上增加了每個節點的屬性，包括對應服務的 Pod 數量和每個 Pod 的平均資源規模。這樣，我們成功構建了每個子問題的特征描述。這一描述形式是一個帶權圖，其中邊權重展示了服務間的流量關系，而節點的屬性則詳細表示了每個服務的特征屬性。
• 算法選擇模塊的構建：接著，我們設計了一個基于圖卷積網絡（GCN）的二分類器來為每個子問題選擇算法，決定是使用 CG 還是 MIP。具體來說，我們通過對多個集群進行隨機采樣，構造了 1000 個子圖，進而形成了 1000 個子問題。對于每個子問題，我們分別運行 CG 和 MIP 算法，并在 1 分鐘內比較兩者的優化效果（通過目標函數值判斷）。更優的算法將作為該子問題的標簽（CG 或者 MIP）。這樣，我們得到了 1000 個形如<特征圖, 標簽>的訓練樣本。利用這些訓練樣本，我們訓練 GCN 網絡，得到了一個能夠接受特征圖輸入并輸出{CG, MIP}標簽的圖二分類器。
• 求解各個子問題：對于每一個子問題，我們將其特征圖輸入到上述圖二分類器中，得到一個標簽，CG 或 MIP。根據這個分類結果，我們使用相應的算法求解該子問題。最終，根據每個子問題生成的 Pod 新排布，我們構建出全局 Pod 的新排布，作為最終的解決方案。

這個過程通過機器學習方法自動適應不同的子問題特性，優化了調度算法的選擇，從而提高了解的質量和求解效率。

實驗評估

廣泛的實驗評估表明，RASA 算法在求解效率和解的質量上均表現出色，顯著優于現有的調度算法。

下圖顯示了 RASA 算法與其他算法（包括不考慮親和性的調度（Original）、基于均衡分割的親和性調度求解器算法（POP）、以及考慮親和性的啟發式算法 K8s+和 ApplSci19）在一分鐘的求解時間限制內的表現。結果表明，RASA 算法在本地化流量值上平均領先 17.66%，顯著優于其他算法。

圖中展示了使用 RASA 算法優化后（With RASA）與未使用 RASA 優化前（Without RASA）的服務在平均響應時延和請求錯誤率上的表現。結果顯示，平均響應時延降低了 23.75%，請求錯誤率降低了 24.09%，明顯提升了服務性能和可靠性。這些結果強調了 RASA 算法在提高調度效率和優化服務性能方面的有效性。

總結

本文詳細闡述了如何在微服務架構中利用服務間的親和性來提升服務性能和增強請求的穩定性。文章引入了親和性調度算法（RASA 算法），該算法專為優化容器部署以提高服務間親和性而設計。RASA 算法不僅計算高效，而且解的質量卓越，滿足了大規模線上應用的要求。自 2023 年在字節跳動上線以來，對于接入親和性部署的業務，該算法已實現了 10%-70% 的時延降低。

未來，字節跳動基礎架構團隊也將繼續深化親和性部署的優化工作，以期在性能提升、穩定性增強及資源成本節約等多方面獲得更多收益。

團隊介紹：ByteBrain 是字節跳動“基礎架構智能化”（AI for Infra）的落地平臺。ByteBrain 利用 AI 技術對基礎架構各系統的生命周期進行自動優化，主要包括智能決策（容量規劃、規格推薦、資源調度）、智能優化（參數調優、SQL 優化）、智能運維（異常檢測與排障）、智能助理（LLM 輔助決策、優化、運維）四大業務方向，目前已經服務了公司 30 余條業務線和產品。此外，團隊在 SIGMOD、VLDB、ICDE、KDD 等頂會有多篇論文發表。

招聘：目前團隊正在美國和中國招聘 AI＋Infra(AI for Infra & Infra for AI)，要求 Senior expert 或 PhD candidates（對標天才少年），有意向者請郵件聯系：tieying.zhang@bytedance.com