前言

近日，數(shù)據(jù)庫和數(shù)據(jù)工程領(lǐng)域的頂級(jí)學(xué)術(shù)會(huì)議之一 ICDE（IEEE International Conference on Data Engineering）在荷蘭烏得勒支舉行，字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)團(tuán)隊(duì)的論文《Resource Allocation with Service Affinity in Large-Scale Cloud Environments》成功入選。

背景與現(xiàn)狀

隨著云計(jì)算的普及與迅速發(fā)展，微服務(wù)架構(gòu)已被越來越多的互聯(lián)網(wǎng)公司采用。在此架構(gòu)中，應(yīng)用被拆分為多個(gè)微服務(wù)，每個(gè)服務(wù)負(fù)責(zé)特定功能，它們通過網(wǎng)絡(luò)協(xié)議（RPC）高效連接，實(shí)現(xiàn)數(shù)據(jù)傳輸和通信。然而，雖然微服務(wù)架構(gòu)提供了多種優(yōu)勢(shì)，如可擴(kuò)展性、輕量級(jí)特性及故障隔離等，但其頻繁的網(wǎng)絡(luò)互動(dòng)也不可避免地增加了網(wǎng)絡(luò)負(fù)擔(dān)，從而導(dǎo)致更高的延遲，并增加了系統(tǒng)的不穩(wěn)定性。

為了解決這些挑戰(zhàn)，字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)的服務(wù)框架團(tuán)隊(duì)、編排調(diào)度團(tuán)隊(duì)和 ByteBrain 團(tuán)隊(duì)合作提出了微服務(wù)親和性部署的解決方案，它的核心思路是將有強(qiáng)依賴關(guān)系的服務(wù)進(jìn)行同機(jī)部署，減少它們之間的調(diào)用開銷，從而實(shí)現(xiàn)性能和成本的優(yōu)化。具體而言，它包含 2 個(gè)操作：

• 通過策略性地重新部署服務(wù)的 Pod，盡量將頻繁通信的服務(wù) Pod 部署在同一臺(tái)機(jī)器上（Collocation）；
• 通過調(diào)整網(wǎng)絡(luò)通信協(xié)議，采用本地通信方式（IPC）替代網(wǎng)絡(luò)通信，顯著降低網(wǎng)絡(luò)開銷，減少請(qǐng)求延遲，增強(qiáng)系統(tǒng)的穩(wěn)定性。

與直接將微服務(wù)合并為更大的服務(wù)相比，親和性部署方案仍保留了微服務(wù)架構(gòu)中服務(wù)的獨(dú)立性、敏捷性和易擴(kuò)展性等優(yōu)勢(shì)。下圖展示了通過模擬實(shí)驗(yàn)的初步驗(yàn)證結(jié)果：親和性部署和本地通信策略（Collocation+IPC）顯著優(yōu)化了端到端延遲和請(qǐng)求失敗率。

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

為了克服這一問題，字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)團(tuán)隊(duì)進(jìn)行了數(shù)學(xué)化建模，提出了一個(gè)考慮服務(wù)親和性的 Pod 調(diào)度問題 RASA（Resource Allocation with Service Affinity）。

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

從理論到實(shí)踐的挑戰(zhàn)

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

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

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

微服務(wù)親和性部署二次調(diào)度方案

下圖展示了字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)團(tuán)隊(duì)所提出的方案的完整優(yōu)化流程：

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

所有 Pod 遷移完成后，集群的 Pod 排布將與 RASA 算法推薦的新排布一致，從而實(shí)現(xiàn)流量本地化的優(yōu)化。

下面，我們將主要介紹圖中算法模塊的設(shè)計(jì)和實(shí)現(xiàn)。我們開發(fā)了一種高效的親和性調(diào)度算法（下文簡(jiǎn)稱 RASA 算法），該算法能夠處理大規(guī)模輸入，并且能夠獲得高質(zhì)量的解決方案。

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

• 利用親和性關(guān)系圖的分割和算法選擇技術(shù)來簡(jiǎn)化問題規(guī)模并加速求解過程；
• 通過對(duì)子問題運(yùn)用基于數(shù)學(xué)規(guī)劃求解器（Solver）的方法，以提升解的質(zhì)量，獲取高本地化流量比例的解。

服務(wù)分割

在字節(jié)跳動(dòng)的線上環(huán)境中，集群內(nèi)可能存在上百甚至上千個(gè)微服務(wù)。如果對(duì)所有微服務(wù)進(jìn)行重調(diào)度計(jì)算，將導(dǎo)致計(jì)算量極大。為此，我們提出了一套多階段服務(wù)流量圖分割技術(shù)。這種技術(shù)依據(jù)流量圖的特性，對(duì)服務(wù)進(jìn)行多次分割，部分分割后的服務(wù)集合可能會(huì)被直接過濾丟棄，將原問題劃分為多個(gè)規(guī)模更小的子問題。

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

除了主親和性分割外，我們還引入了以下幾種分割技術(shù)，以進(jìn)一步優(yōu)化子問題的求解效率和效果：

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

通過這些精細(xì)化的分割策略，我們能夠有效地管理大規(guī)模集群中的服務(wù)調(diào)度問題，優(yōu)化資源利用率，提升服務(wù)性能。

調(diào)度算法池

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

以下是針對(duì) RASA 問題設(shè)計(jì)的混合整數(shù)規(guī)劃表達(dá)式。利用這一表達(dá)式，我們開發(fā)了 CG 和 MIP 兩種算法，用于精確求解子問題：

算法選擇

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

為了進(jìn)一步提高求解效率并在有限時(shí)間內(nèi)獲取更優(yōu)解，我們引入了算法選擇策略，即針對(duì)每個(gè)子問題在{CG, MIP}中選擇更適合的算法。我們利用每個(gè)子問題的特征——包括微服務(wù)數(shù)量、機(jī)器數(shù)量和服務(wù)間的流量關(guān)系——構(gòu)建特征圖。在這些圖中，微服務(wù)作為節(jié)點(diǎn)，服務(wù)間的流量大小作為邊權(quán)，節(jié)點(diǎn)還包含服務(wù)本身的特征信息。

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

在獲得每個(gè)子問題的最佳求解算法后，我們分別用選定的算法獨(dú)立求解每個(gè)子問題。求解完成后，我們將所有子問題的解合并，形成最終的解決方案。通過這種方式，我們不僅提高了求解的效率，還優(yōu)化了解的質(zhì)量，從而有效支持了大規(guī)模集群環(huán)境下的服務(wù)調(diào)度需求。

Running Example

為了幫助讀者更深入地理解 RASA 算法，我們?cè)诖颂峁┮粋€(gè)簡(jiǎn)單的實(shí)例，全面展示算法的工作過程。

我們的示例中包含 15 個(gè)微服務(wù)，它們之間的流量關(guān)系如上圖最左側(cè)所示，其中邊權(quán)代表流量值，藍(lán)色節(jié)點(diǎn)表示該微服務(wù)只能部署在類型為 X 的硬件上，綠色節(jié)點(diǎn)表示只能部署在類型為 Y 的硬件上。服務(wù)分割的具體步驟如下：

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

完成服務(wù)分割后，只需為這些分割結(jié)果分配適當(dāng)?shù)臋C(jī)器，即可形成幾個(gè)獨(dú)立的 RASA 問題輸入。通過這種多階段分割策略，原本需要解決的 15 個(gè)微服務(wù)排布問題被有效地分解為 3 個(gè)僅包含 2 個(gè)微服務(wù)的子問題，且這些分割過程中的流量損失僅占總流量的 12%，實(shí)現(xiàn)了在最優(yōu)性損失微小的情況下極大提升求解速度。

當(dāng)前，我們面臨多個(gè)子問題和調(diào)度算法池中的 CG（Column Generation Algorithm）與 MIP（MIP-Based Algorithm）兩種算法，接下來的任務(wù)是為每個(gè)子問題選擇一個(gè)最適合的調(diào)度算法進(jìn)行求解。

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

這個(gè)過程通過機(jī)器學(xué)習(xí)方法自動(dòng)適應(yīng)不同的子問題特性，優(yōu)化了調(diào)度算法的選擇，從而提高了解的質(zhì)量和求解效率。

實(shí)驗(yàn)評(píng)估

廣泛的實(shí)驗(yàn)評(píng)估表明，RASA 算法在求解效率和解的質(zhì)量上均表現(xiàn)出色，顯著優(yōu)于現(xiàn)有的調(diào)度算法。

下圖顯示了 RASA 算法與其他算法（包括不考慮親和性的調(diào)度（Original）、基于均衡分割的親和性調(diào)度求解器算法（POP）、以及考慮親和性的啟發(fā)式算法 K8s+和 ApplSci19）在一分鐘的求解時(shí)間限制內(nèi)的表現(xiàn)。結(jié)果表明，RASA 算法在本地化流量值上平均領(lǐng)先 17.66%，顯著優(yōu)于其他算法。

圖中展示了使用 RASA 算法優(yōu)化后（With RASA）與未使用 RASA 優(yōu)化前（Without RASA）的服務(wù)在平均響應(yīng)時(shí)延和請(qǐng)求錯(cuò)誤率上的表現(xiàn)。結(jié)果顯示，平均響應(yīng)時(shí)延降低了 23.75%，請(qǐng)求錯(cuò)誤率降低了 24.09%，明顯提升了服務(wù)性能和可靠性。這些結(jié)果強(qiáng)調(diào)了 RASA 算法在提高調(diào)度效率和優(yōu)化服務(wù)性能方面的有效性。

總結(jié)

本文詳細(xì)闡述了如何在微服務(wù)架構(gòu)中利用服務(wù)間的親和性來提升服務(wù)性能和增強(qiáng)請(qǐng)求的穩(wěn)定性。文章引入了親和性調(diào)度算法（RASA 算法），該算法專為優(yōu)化容器部署以提高服務(wù)間親和性而設(shè)計(jì)。RASA 算法不僅計(jì)算高效，而且解的質(zhì)量卓越，滿足了大規(guī)模線上應(yīng)用的要求。自 2023 年在字節(jié)跳動(dòng)上線以來，對(duì)于接入親和性部署的業(yè)務(wù)，該算法已實(shí)現(xiàn)了 10%-70% 的時(shí)延降低。

未來，字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)團(tuán)隊(duì)也將繼續(xù)深化親和性部署的優(yōu)化工作，以期在性能提升、穩(wěn)定性增強(qiáng)及資源成本節(jié)約等多方面獲得更多收益。

團(tuán)隊(duì)介紹：ByteBrain 是字節(jié)跳動(dòng)“基礎(chǔ)架構(gòu)智能化”（AI for Infra）的落地平臺(tái)。ByteBrain 利用 AI 技術(shù)對(duì)基礎(chǔ)架構(gòu)各系統(tǒng)的生命周期進(jìn)行自動(dòng)優(yōu)化，主要包括智能決策（容量規(guī)劃、規(guī)格推薦、資源調(diào)度）、智能優(yōu)化（參數(shù)調(diào)優(yōu)、SQL 優(yōu)化）、智能運(yùn)維（異常檢測(cè)與排障）、智能助理（LLM 輔助決策、優(yōu)化、運(yùn)維）四大業(yè)務(wù)方向，目前已經(jīng)服務(wù)了公司 30 余條業(yè)務(wù)線和產(chǎn)品。此外，團(tuán)隊(duì)在 SIGMOD、VLDB、ICDE、KDD 等頂會(huì)有多篇論文發(fā)表。

招聘：目前團(tuán)隊(duì)正在美國和中國招聘 AI＋I(xiàn)nfra(AI for Infra & Infra for AI)，要求 Senior expert 或 PhD candidates（對(duì)標(biāo)天才少年），有意向者請(qǐng)郵件聯(lián)系：tieying.zhang@bytedance.com