# 1. Introduction

Borg 是 Google 內部使用的集群管理系統，負責接納、調度、啟動、重啟和監控 Google 運行的所有應用程序。

Borg 提供三大主要優點：
1. 隱藏資源管理和故障處理的細節，讓用戶能專注於應用開發。
2. 提供高可靠性和高可用性，支持運行相同標準的應用程序。
3. 有效管理成千上萬台機器上的工作負載。

Borg 並非首個解決這些問題的系統，但在其規模和完整性上屬於少數幾個之一。

# 2. The user perspective

Borg 的用戶主要是 Google 的開發人員和系統管理員（網站可靠性工程師，SREs），負責運行 Google 的應用和服務。
用戶將他們的工作以作業 (jobs) 的形式提交給 Borg，每個作業包含一個或多個運行相同程序（binary）的任務 (tasks)。
每個作業在一個 Borg 細胞 (Borg cell) 中運行，細胞是一組作為一個單元管理的機器。

## 2.1 The workload

Borg 細胞 (Borg cells) 運行異質工作負載 (heterogeneous workload)，包括長期運行的服務和批處理作業。

- 長期運行的服務
- 不應該停機，處理短期的延遲敏感請求（從幾微秒到幾百毫秒）。
- 用於面向終端用戶的產品（如Gmail、Google Docs和網頁搜索）以及內部基礎設施服務（如BigTable）。
- 批處理作業
- 需要幾秒到幾天完成，對短期性能波動不敏感。
- 工作負載組合隨細胞而異，取決於其主要租戶。
- 例如：一些細胞相當批處理密集。
- 工作負載變化
- 工作負載組合隨時間變化：批處理作業來來去去，許多面向終端用戶的服務作業呈現日夜使用模式。
- Borg需要同樣有效地處理所有這些情況。
- 應用框架
- 許多應用框架在過去幾年中建立在Borg之上，包括內部的MapReduce系統、FlumeJava、Millwheel和Pregel。
- 這些框架中的大多數都有一個控制器，提交一個主作業和一個或多個工作作業。
- 前兩者在功能上類似於YARN的應用管理器。
- 分布式存儲系統
- 如GFS及其後繼者CFS、Bigtable和Megastore，均運行在Borg上。
- 作業分類
- 高優先級的Borg作業稱為"生產" (production) 作業，其餘的稱為"非生產" (non-production) 作業。
- 大多數長期運行的服務作業是生產作業；大多數批處理作業是非生產作業。
- 資源分配
- 在一個代表性的細胞中：
- 生產作業分配了約70%的總CPU資源，佔用約60%的總CPU使用量。
- 生產作業分配了約55%的總內存，佔用約85%的總內存使用量。

## 2.2 Clusters and cells

Borg 細胞中的機器屬於單個集群 (cluster)，由高性能數據中心規模的網絡連接。每個集群位於單個數據中心建築內，由多個建築組成一個站點 (site)。
一個集群通常包含一個大規模細胞，可能還有一些小規模的測試或特殊用途的細胞。我們極力避免任何單點故障。

- 中位數細胞大小約為 10,000 台機器（不包括測試細胞）；有些細胞規模更大。
- 細胞內的機器在多個維度上是異質的 (heterogeneous)：CPU、記憶體、磁碟、網絡等資源的大小和性能都不同，還有如外部 IP 地址或快閃存儲等功能差異。
- Borg 隔離用戶大部分這些差異，通過確定在細胞內的哪裡運行任務，分配其資源，安裝其程序及其他依賴項，監控其健康狀況，並在其失敗時重啟。

## 2.3 Jobs and tasks

每個作業 (job) 包含多個屬性，如名稱、所有者和任務數量。作業可以有約束條件，使其任務在具有特定屬性的機器上運行。
- 作業屬性包括名稱、所有者和任務數量。作業可以有約束條件，要求其任務在具有特定屬性的機器上運行，例如處理器架構、操作系統版本或外部 IP 地址。
- 約束條件可以是硬性的 (hard) 或軟性的 (soft)；軟性約束更像是偏好而非必須條件。作業的開始可以被延遲到先前的作業完成。

:::info
**任務運行**
- 每個作業在一個 Borg 細胞中運行，每個任務 (task) 對應於在機器上的一組 Linux 行程，這些行程在容器中運行。
- 大多數 Borg 工作負載不在虛擬機 (VM) 中運行，因為我們不想支付虛擬化的成本。此外，系統設計之時，我們在沒有硬體支持虛擬化的處理器上有相當大的投資。
:::

:::info
**任務屬性**
- 任務屬性包括資源需求和任務在作業中的索引。大多數任務屬性在作業的所有任務中是相同的，但可以被覆蓋，例如提供任務特定的命令行參數。
- 每個資源維度（CPU 核心、記憶體、磁碟空間、磁碟訪問率、TCP 端口等）獨立地以細粒度指定；我們不強制固定大小的桶或槽。
:::

- Borg 程序是靜態鏈接的，以減少對其運行環境的依賴，並結構為二進制文件和數據文件的包，其安裝由 Borg 協調。
- 用戶通過向 Borg 發出遠程過程調用 (RPC) 來操作作業，最常見的是通過命令行工具、其他 Borg 作業或我們的監控系統。
- 大多數作業描述是用聲明式配置語言 BCL 編寫的，這是 GCL 的變體，生成 Protobuf 文件，並擴展了一些 Borg 特定的關鍵字。


圖 2 展示了作業和任務在其生命週期中所經歷的狀態。
- 作業和任務的狀態包括提交、接受、等待、運行和死亡。
- 用戶可以通過提交、殺死和更新過渡來改變任務的屬性。

## 2.4 Allocs

Borg alloc 是機器上一組保留的資源，可以用來運行一個或多個任務；即使資源未被使用，也會保持分配。

Allocs 在資源管理中扮演著重要角色，其功能包括：
- **資源保留**：為未來的任務保留資源，或者在停止任務與重新啟動任務之間保持資源。
- **資源共享**：將不同作業的任務集中到同一台機器上，例如將一個網頁伺服器實例和一個相關的日誌保存任務集中在一起，將伺服器的 URL 日誌從本地磁碟複製到分布式檔案系統。

Alloc 的資源管理如下：
- 資源類似性：Alloc 的資源與機器的資源類似，多個任務在同一個 alloc 內共享其資源。
- 遷移：如果一個 alloc 必須遷移到另一台機器，它的任務將隨之重新調度。

:::info
**Alloc 組**
Alloc 組（alloc set）類似於作業：它是一組 alloc，保留在多台機器上的資源。一旦建立 alloc 組，可以提交一個或多個作業在其中運行。這些 alloc 的特點如下：
:::

- **作業和任務的指代**：通常使用"任務"來指代 alloc 或頂級任務（在 alloc 之外的任務），使用"作業"來指代作業或 alloc 組。

## 2.5 Priority, quota, and admission control

當工作量超過系統可容納範圍時，Borg 使用優先級 (priority) 和配額 (quota) 來管理資源分配。這部分解釋了如何通過優先級和配額來控制作業的入門 (admission control)。

**優先級 (Priority)**
每個作業都有一個小的正整數作為優先級。高優先級的任務可以獲得資源，即使這意味著要搶占低優先級的任務。優先級的具體使用如下：
- 優先級區段：Borg 定義了不同用途的非重疊優先級區段，包括（按優先級遞減順序）：監控 (monitoring)、生產 (production)、批處理 (batch) 和最佳努力 (best effort)。
- 搶占規則：高優先級的任務可以搶占低優先級的任務，但生產區段內的任務不能互相搶占。
- 應用實例：例如，MapReduce 主任務的優先級比它們控制的工作任務略高，以提高可靠性。

**配額 (Quota)**
配額用於決定哪些作業可以被接納調度。配額的具體管理方式如下：
- 配額表達式：配額以資源數量（如 CPU、記憶體、磁碟等）的向量形式表示，並且在指定的時間段（通常為幾個月）內生效。
- 優先級成本：高優先級的配額成本更高。生產優先級的配額限於細胞內實際可用的資源。
- 超賣配額：低優先級層級的配額會被超賣，以確保所有用戶在低優先級有無限的配額，儘管這些資源經常被過度訂閱。

**入門控制 (Admission Control)**
入門控制是配額檢查的一部分，用於在提交作業時立即拒絕資源不足的作業。入門控制的作用如下：
- 使用範圍：用戶作業只有在其擁有足夠的配額時才會被接納調度。
- 物理容量規劃：配額分配與物理容量規劃緊密結合，反映在不同數據中心中配額的價格和可用性。

**特權管理**
Borg 有一個特權系統，給某些用戶特殊的權限，例如允許管理員刪除或修改任何細胞中的作業，或允許用戶訪問受限的內核功能或 Borg 行為（如禁用資源估算）。

## 2.6 Naming and monitoring

為了確保服務的客戶端和其他系統能夠找到任務，即使它們被重新定位到新的機器上，Borg 創建了一個穩定的名稱服務 (naming service) 和健康監控系統。

**命名 (Naming)**
- Borg 名稱服務 (BNS)：Borg 為每個任務創建一個穩定的“Borg 名稱服務” (BNS) 名稱，名稱包括細胞名、作業名和任務號碼。
- 名稱解析：Borg 將任務的主機名和端口寫入 Chubby 中的一個一致且高度可用的文件，該文件用於 RPC 系統查找任務端點。這些 BNS 名稱還構成了任務的 DNS 名稱
- 例如使用者 `ubar` 的作業 `jfoo` 的第 50 個任務在 `cc` 細胞中會被解析為 `50.jfoo.ubar.cc.borg.google.com`。
- 狀態更新：Borg 也會將作業大小和任務健康信息寫入 Chubby，每當這些信息發生變化時，負載均衡器可以據此決定將請求路由到哪裡。

**監控 (Monitoring)**
- 內建 HTTP 伺服器：幾乎每個在 Borg 下運行的任務都包含一個內建的 HTTP 伺服器，發布有關任務健康狀況和性能指標的信息（例如，RPC 延遲）。
- 健康檢查：Borg 監控健康檢查 URL，並在任務未能及時響應或返回 HTTP 錯誤代碼時重啟它們。
- 監控工具：其他數據由監控工具跟踪，用於儀表板和服務水平目標 (SLO) 違規警報。

**用戶界面 (UI)**
- Sigma 服務：Sigma 提供了一個基於網頁的用戶界面，通過它用戶可以檢查所有作業的狀態、一個特定細胞的狀態，或深入到單個作業和任務中，查看它們的資源行為、詳細日誌、執行歷史和最終狀況。
- 日誌管理：應用程序生成大量日誌，這些日誌會自動輪轉，以避免耗盡磁碟空間，並在任務退出後保存一段時間以便調試。
- 未執行作業的診斷：如果一個作業未在運行，Borg 提供“為什麼等待？”的註釋，並提供修改作業資源請求以更好適應細胞的指導。

**記錄與分析**
- Infrastore：Borg 記錄所有作業提交和任務事件，以及詳細的每任務資源使用信息到 Infrastore，一個具有互動式 SQL 介面的可擴展只讀數據存儲。這些數據用於基於使用量的計費、調試作業和系統故障，以及長期容量規劃。

# 3. Borg architecture

Borg 的架構由一組機器、一個邏輯集中控制器（Borgmaster）和運行在每台機器上的代理行程（Borglet）組成。這部分將介紹 Borg 的核心組成部分及其功能。

## 3.1 Borgmaster

Borgmaster 是 Borg 系統的核心控制器，負責管理細胞中的所有機器和任務。每個細胞的 Borgmaster 由兩個行程組成：主 Borgmaster 行程和一個獨立的調度器。

**組成**
- 主 Borgmaster 行程：處理客戶端的 RPC，管理所有系統對象（如機器、任務、alloc 等）的狀態機，與 Borglets 通訊，並提供一個網頁 UI 作為 Sigma 的備用。
- 調度器：獨立運行，負責任務的分配。

Borgmaster 的複製和容錯機制如下：
- 每個細胞的 Borgmaster 實際上被複製五次，每個副本保持細胞狀態的內存副本，並將這些狀態記錄在基於 Paxos 的高度可用的分布式存儲中。
- 每個細胞選舉一個主 Borgmaster，負責所有改變細胞狀態的操作，如提交作業或終止機器上的任務。選舉過程通常需要大約 10 秒，但在大細胞中可能需要最多一分鐘。

Borgmaster 的狀態管理通過檢查點 (checkpoints) 實現：
- 狀態檢查點：Borgmaster 的狀態以定期快照和變更日誌的形式保存，這些檢查點可以用於恢復 Borgmaster 的狀態到過去的任意點。
- 檢查點的用途：包括在接受可能觸發軟體缺陷的請求前恢復狀態、手動修復、構建事件的持久日誌和離線模擬。

Fauxmaster 是一個高保真的 Borgmaster 模擬器，其功能如下：
- 高保真模擬：Fauxmaster 能夠讀取檢查點文件並包含完整的生產 Borgmaster 代碼，可以用來調試故障、進行容量規劃和配置更改的檢查。
- 模擬使用：用戶可以像操作實際 Borgmaster 一樣與 Fauxmaster 交互，觀察系統狀態的變化。

## 3.2 Scheduling

調度 (Scheduling) 是 Borg 系統中的核心功能之一，負責將作業 (jobs) 的任務 (tasks) 分配到機器上運行。調度過程包括將提交的作業持久化到 Paxos 存儲中，並將作業的任務添加到等待佇列中。

調度過程分為以下幾個步驟：
- 任務提交：當作業提交時，Borgmaster 將其記錄在 Paxos 存儲中，並將任務添加到等待佇列中。
- 異步掃描：調度器異步掃描等待佇列，從高優先級到低優先級分配任務。
- 可行性檢查：調度器首先檢查每台機器是否符合任務的約束條件，並確保有足夠的“可用”資源，包括可以被搶占的低優先級資源。
- 評分：調度器根據任務的偏好和內置標準（如最小化被搶占任務的數量、選擇已有任務包的機器等）對可行的機器進行評分。
- 資源預留：如果選定的機器沒有足夠的資源，Borg 會搶占低優先級的任務，以騰出資源。

調度模型
Borg 採用混合調度模型：
- E-PVM 模型：最初使用 E-PVM 模型，根據異構資源生成單一成本值，並最小化任務放置時的成本變化。
- 最優適應模型：在實際運行中，E-PVM 模型會將負載分散到所有機器上，但會增加資源碎片化，特別是對需要大部分機器資源的大任務。
- 混合模型：目前採用混合模型，試圖減少被限制資源的數量，提供比最佳適應 (best fit) 更高的打包效率。

任務啟動延遲
任務從提交到運行的延遲是調度的關鍵問題之一：
- 延遲來源：包安裝佔總延遲的 80%，磁碟爭用是已知瓶頸之一。
- 優化策略：調度器優先將任務分配到已安裝所需包的機器上，大多數包是不可變的，可以共享和快取。

可擴展性
Borg 調度器使用多種技術來實現對數萬台機器的管理：
- 評分快取：對機器的可行性和評分進行快取，以減少重新計算的次數。
- 等價類：對具有相同需求和約束條件的任務進行等價類分組，減少需要評估的任務數量。
- 隨機化放寬：調度器以隨機順序檢查機器，直到找到足夠的可行機器，再從中選擇最佳機器。

這些技術使 Borg 調度器能夠高效地分配資源，並在大規模系統中保持性能和可擴展性。

## 3.3 Borglet

Borglet 是 Borg 系統中的本地代理，運行在每台細胞 (cell) 機器上。Borglet 負責管理本地資源，啟動和停止任務，並與 Borgmaster 通訊。

Borglet 的主要功能如下：

- **任務管理**：Borglet 啟動和停止任務，並在任務失敗時重新啟動它們。
- **資源管理**：通過操作操作系統內核設置來管理本地資源，並滾動調試日誌。
- **狀態報告**：定期向 Borgmaster 報告機器的當前狀態，並執行任何未完成的請求。

**通訊與控制**
Borgmaster 通過輪詢的方式與 Borglet 通訊：

- **輪詢機制**：Borgmaster 每幾秒鐘輪詢一次每個 Borglet，檢索機器的當前狀態並發送任何未完成的請求。這種方法控制了通訊速率，避免了顯式流量控制機制，並防止恢復風暴。
- **狀態同步**：選定的主 Borgmaster 負責準備發送給 Borglets 的消息，並通過接收 Borglets 的響應來更新細胞的狀態。

**故障處理**
Borglet 在與 Borgmaster 的通訊中斷時仍能正常運行：

- **機器標記為故障**：如果 Borglet 未能響應多個輪詢消息，其機器將被標記為故障，並重新調度其上運行的任務。
- **通訊恢復**：如果通訊恢復，Borgmaster 會指示 Borglet 終止已重新調度的任務，以避免重複。

**負載分擔與容錯**
Borgmaster 副本分擔與 Borglets 的通訊負載，以提高性能和容錯性：

- **分片處理**：每個 Borgmaster 副本運行一個無狀態的鏈接分片 (link shard)，處理與部分 Borglets 的通訊；選舉發生時重新計算分片。
- **狀態報告壓縮**：Borglet 總是報告其完整狀態，但鏈接分片只報告狀態變更，以減少主 Borgmaster 的更新負載。

## 3.4 Scalability

Borg 的可擴展性設計使其能夠管理數以千計的機器，每個細胞中的任務到達率超過每分鐘 10,000 個任務。為了達到這種規模，Borg 使用了多種技術和架構改進。

**性能和資源需求**
- **資源消耗**：一個繁忙的 Borgmaster 使用 10-14 個 CPU 核心和高達 50 GiB 的記憶體。

**調度器並行處理**
- **調度器分離**：將調度器從主 Borgmaster 行程中分離，使其能夠與其他複製 Borgmaster 功能並行運行。
- **調度器副本**：調度器副本在本地快取細胞狀態，反覆從主 Borgmaster 獲取狀態變更，執行調度任務，並將結果返回給主 Borgmaster。

**並行與分片**
- **多執行緒**：為了提高響應時間，添加了單獨的執行緒來與 Borglets 通信和響應只讀 RPC 請求。
- **分片機制**：將這些功能分片 (sharding) 到五個 Borgmaster 副本上，使得 UI 響應時間保持在 99% 的時間內低於 1 秒，並且 95% 的 Borglet 輪詢間隔低於 10 秒。

**調度優化技術**
Borg 調度器使用多種技術來提高可擴展性和性能：

- **評分快取(Score caching)**：對機器的可行性和評分進行快取，以減少重新計算的次數，僅在機器或任務屬性變更時重新計算。
- **等價類(Equivalence classes)**：將具有相同需求和約束條件的任務分組，僅對每個等價類的任務進行可行性和評分計算，減少需要評估的任務數量。
- **隨機化放寬(Relaxed randomization)**：調度器以隨機順序檢查機器，直到找到足夠的可行機器，再從中選擇最佳機器，減少評分和快取失效的頻率。

**調度性能**
- **從頭調度時間**：從頭調度一個細胞的全部工作負載通常需要幾百秒，但在禁用上述技術時，可能需要超過三天的時間才能完成。
- **在線調度**：正常情況下，處理等待佇列的在線調度僅需不到半秒的時間。

這些技術使 Borg 系統能夠高效地管理大規模的機器和任務，保持性能和可擴展性。

# 4. Availability

Borg 系統的高可用性設計旨在確保服務的連續性和可靠性，即使在出現硬體故障或其他問題時也是如此。Borg 採取了多種策略來提高系統的可用性，包括多副本架構、自動恢復機制和快速故障檢測。

**多副本架構**
- **Borgmaster 副本**：每個細胞的 Borgmaster 被複製五次，這些副本分散在多個機架上，以減少單點故障的風險。
- **Paxos 協議**：使用 Paxos 分布式協議來管理狀態變更，確保狀態的一致性和高可用性。

**自動恢復機制**
- **任務重新啟動**：Borg 會自動重新啟動失敗的任務，以確保服務的連續性。這種自動恢復機制涵蓋了軟體故障、機器故障和網絡問題。
- **快速故障轉移**：在 Borgmaster 或 Borglet 出現故障時，系統會迅速轉移到其他副本，最小化服務中斷。

**快速故障檢測**
- **健康檢查**：Borg 定期執行健康檢查，包括檢查任務的響應時間和資源使用情況。發現異常時，會自動啟動故障處理流程。
- **監控與警報**：使用多種監控工具實時跟踪系統健康狀態，並在發現潛在問題時發送警報。

**調度優化**
- **優先級調度**：Borg 使用優先級調度機制，確保高優先級的關鍵任務優先獲得資源。
- **資源預留**：為關鍵任務預留資源，確保在高負載情況下仍能正常運行。

**應對大規模故障**
- **多細胞架構**：將服務分佈在多個細胞中，以減少單個細胞故障對整體系統的影響。
- **區域間冗餘**：在不同地理區域部署多個細胞，提供區域間的冗餘和故障轉移能力。

**應用層容錯**
- **應用級別的故障處理**：應用程序設計時考慮到可能的故障，實施了多種容錯機制，如重試邏輯和降級服務。
- **負載均衡**：使用負載均衡技術分散流量，確保即使部分節點故障，整體服務仍能保持可用。