Meta 開源 Rebalancer：通用高效能資源分配最佳化引擎

Meta 開源了內部用了超過九年的 Rebalancer 引擎，這是一套處理資源分配與任務指派問題的通用求解工具。專案由 Richard Barnes、Neeraj Kumar 與 Pol Mauri Ruiz 等人主導開發，相關論文已獲選在 OSDI'24 發表。

核心設計理念

Rebalancer 的特別之處在於把問題拆成幾個獨立層面：如何定義指派問題、如何在記憶體中有效存儲、如何求解問題，以及如何除錯。這種切分被認為是 Rebalancer 好用、能擴展、也容易延伸的關鍵。

工具處理的基本問題是：給定一組對象與一組容器，該怎麼把對象指派到容器中，同時滿足約束條件並最佳化目標？

Meta 基礎設施中的應用層級

Rebalancer 在 Meta 基礎設施的各個層級都有派上用場：

硬體放置上，機架（對象）要在資料中心（容器）內定位，目的是讓機架在電力故障域中盡量分散，同時遵守功率與散熱限制。

服務分配上，伺服器（對象）要指派給服務（容器），滿足各服務的需求，同時最佳化容錯性（把服務的伺服器分散到不同故障域）與封裝效率。

任務放置上，任務（對象）要分配到伺服器（容器），遵守伺服器資源限制，並最佳化容錯性與共同定位需求。

流量路由上，來自數十億使用者的流量（對象）要路由到地理位置分散的資料中心（容器），目的是最佳化網路延遲和資料中心負載。

問題定義與規格系統

要設計出可復用的框架，主要難題在於可用性與可擴展性。可用性方面，實務工作者很難把現實中的策略轉換成正式最佳化方法所需的精確數學公式；可擴展性方面，NP-困難問題沒辦法用商業求解器有效率地解出來。

Rebalancer 的做法是把問題規格與求解分開處理。工具提供一套語言，用對象、容器、約束與目標來描述問題。問題描述完後，Rebalancer 會把它轉換成一個叫表達式圖的有向無環圖結構。

規格系統用三個步驟逐步拉高抽象層級：

第一步引入基本建模元件，包括維度（對象與容器的真實屬性）、分割（對象的分組）、範圍（容器的分組）與使用率（指派到容器的對象所貢獻的量）。

第二步提供 API 暴露常用的表達式，例如多個容器的使用率可以用 SUM 或 MAX 操作彙總，或用 SQUARE 操作做轉換。

第三步利用這些表達式，Rebalancer 暴露出實現數十個常見目標與約束的高階規格 API。每項規格可以看成一個預先定義好的配方，接受建模元件與額外參數當輸入，再用表達式 API 組出數學公式。

求解方法

問題透過上述 API 規格化後，Rebalancer 會把它轉譯成表達式圖。圖中的葉節點代表使用率表達式（例如伺服器 A 的記憶體使用率），這些值再遞迴地用 Max、Sum 等彙總節點或 Square、Abs 等轉換節點組合起來。表達式圖裡每個節點的值都取決於當前的指派狀態，每次指派一改變就要更新。

Rebalancer 提供兩種求解技術：

最佳求解器模式把表達式圖轉譯成可以餵給混合整數規劃（MIP）求解器的表達式集合，支援 FICO Xpress、Gurobi 或開源求解器 HiGHS。轉譯過程中，Rebalancer 得用二進制決策變數的加權和來表示容器的使用率，這可能產生非常龐大的 MIP 模型。工具會自動用變數彙總、互換性與對稱破缺等技術把模型縮小，但生成的 MIP 模型最壞情況還是可能到二次方等級，也就是 O(|對象|×|容器|)。規模最大的問題已經超出任何 MIP 求解器能處理的範圍。

局部搜尋求解器直接在表達式圖上運作，藉此突破這個限制，做法是探索當前指派周圍的局部鄰域，把部分對象移到其他容器。這個鄰域最壞情況的規模是 O(|對象|+|容器|)，讓 Rebalancer 可以模擬極大規模的問題而不受記憶體限制。每次移動都會產生新的候選指派，Rebalancer 會評估它對目標與約束帶來的新數值。評估完所有候選後，套用最佳候選指派（也就是不違反約束、且最能改善目標的那個）。這個評估與套用的過程會一直重複，直到無法再有進展或達到停止條件為止。Rebalancer 的局部搜尋演算法經過高度最佳化與平行化，每次評估的成本相對低（每秒可以做數百萬次評估），能快速探索搜尋空間。工具也懂得怎麼修剪搜尋空間，減少需要的評估次數。

要選哪種求解技術，得看實際需求。Meta 幾乎所有大規模問題都用局部搜尋。規模較小到中等、對求解時間要求沒那麼高的問題通常用最佳求解器。常見做法是先用最佳求解器做原型，找出高品質的基線方案後再改用局部搜尋。離線時也可以用最佳求解器來調校局部搜尋。

Meta 內部使用情況

過去十年 Rebalancer 一直在 Meta 內部使用並持續改進。它求解的基礎設施最佳化問題範圍很廣，包括把分片指派給伺服器（Shard Manager）、把伺服器指派給服務（RAS）、把流量從全球分散的邊緣資料中心路由到主資料中心（Taiji）、把無伺服器函數分組以改善定位、跨地區平衡線上機器學習訓練工作負載同時考慮優先級等等。

截至目前，Rebalancer 每天求解約 4,000 萬個指派問題，涵蓋超過 30 種不同的問題定義。在包含 26.5 萬個對象與 3,200 個容器的問題中，第 99 百分位求解時間是 12 秒。對於超過 100 萬個對象與 5,000 個容器的問題，平均求解時間是 171 秒，這類執行已經超過 3,400 次。

Rebalancer 也被用在非基礎設施的問題上，像是把會議指派到會議室以減少往返時間、把支援工單指派給工程師，以及最佳化辦公桌放置。

除錯工具

隨著 Rebalancer 讓工程師更容易制定與求解問題，工作重點也轉移到除錯求解器的行為上。為此，Meta 開發了 Rebalancer Explorer 這套專用 UI 工具。

Explorer 以 Docker 化網頁 UI 的形式隨這次開源版本一起發佈，協助開發者在使用局部搜尋和最佳求解器時快速除錯與迭代。工具可以回答像是「哪些約束是約束性的」、「放鬆某個約束會發生什麼」、「為什麼對象被放在這個容器而不是別的地方」這類問題。

開源發佈

Rebalancer 採 Apache 2.0 授權開源發佈。Meta 邀請系統與最佳化領域的專家試用 Rebalancer 並貢獻專案，方式包括找出效能瓶頸、加入新的求解技術、擴展支援新類型的問題，或修復缺陷。相關資源已在 GitHub 上線，並提供 Python 套件與完整文檔。