google集群操作系統borg

1. Introduction

google服務器集群的管理系統，類似于百度的Matrix，阿里的fuxi，騰訊的臺風平臺等等，還有開源的mesos

Borg provides three main benefits: it

1. hides the details of resource management and failure handling so its users can focus on application development instead;
2. operates with very high reliability and availability, and supports applications that do the same; and
3. lets us run workloads across tens of thousands of machines effectively.
</ol>




2. The user perspective


borg主要面向于系統管理員和google開發者，這些用戶在borg上面運行他們的服務和應用程序，用戶以job的形式提交任務，每個job包含一個或者多個tasks，每個job運行在一個cell里，cell是機器的集合，可以理解為是一個邏輯的IDC




2.1 The workload


borg上運行的服務通常可以分為兩類：

1. prod：long-running服務，幾乎不停機，時延敏感，例如gmail，google docs，google搜索等等，另外還有一些google內部的基礎架構平臺，例如bigtable，GFS
2. non-prod：batch型任務，時延不敏感，通常幾小時或者幾天即可跑完
</ol>

這兩種不通類型的任務在borg的cell里通常是混部的，同時又需要結合不同類型任務的特點，以及IDC屬性，等等做出不同的調度策略。例如end- user-facing服務利用率通常都會有一個固定的模式，白天的時候利用率很高，晚上機器又很閑，深夜可能幾乎沒什么訪問量等等，另外Batch型任 務執行時間段，一般上來跑個幾分鐘，幾小時就完成任務了。等等。




borg最主要的目的，就是要提高機器的利用率。




在google內部，很多應用程序框架都是構建在borg之上的，例如mapreduce系統，FlumeJava，Millwheel，Pregel， 還有google的分布式存儲服務，例如GFS，Bigtable，Megastore。像mapreduce，flumejava這種服 務，master和他們的job都是跑在borg上的，這里的master和job區別于borg里的master和job

In a representative cell, prod jobs are allocated about 70% of the total CPU resources and represent about 60% of the total CPU usage; they are allocated about 55% of the total memory and represent about 85% of the total memory usage.

2.2 Clusters and cells


數據中心 > 集群  > cell

A cluster usually hosts one large cell and may have a few smaller-scale test or special-purpose cells. We assiduously avoid any single point of failure. 中等規模的cell大約10k臺服務器左右，不包括測試cell，我的理解這些smaller-scale test cell的主要作用是小流量專用？每個機器上可供調度的資源類型包括：cpu，內存，網絡，磁盤，甚至是處理器性能，類型，以及ssd，ip地址等等（我 的理解，對于某些類型的服務，是需要固定IP，而不允許隨意調度，例如存儲系統）。

用戶在提交job的時候申請資源，然后borg將它們調度到某機器上執行，監控他們的狀態，如果有必要在job的狀態failed后重啟它們

2.3 Jobs and tasks


job的屬性包括：名稱，owner，tasks，同時還包括一些調度的約束條件，例如處理器架構，os版本，ip地址等等，這些會影響borg-master調度的結果，當然這些條件不一定是強制約束的，分hard和soft兩種。

一個job只能跑在一個cell里，每個job會有N個task，每個task運行期間會有多個進程，google并沒有使用虛擬機的方式來進行task之間的資源隔離，而是使用輕量級的容器技術cgroup。

task也有自己的屬性：資源需求和一個index，大部分時候一個job里的所有task的資源需求都是一樣的。

Users operate on jobs by issuing remote procedure calls (RPCs) to Borg, most commonly from a command-line tool, other Borg jobs, or our monitoring systems

job是通過一個google自己實現的BCL語言來描述的，用戶可以通過update的方式來更新job的描述文件，基于過程狀態機：






update過程是輕量的，非原子的，而且也是有可能會失敗的，Updates are generally done in a rolling fashion, and a limit can be imposed on the number of task disruptions (reschedules or preemptions) an update causes; any changes that would cause more disruptions are skipped

2.4 Allocs


alloc的本質上就是現在的容器，用來運行一個或者多個task，是task的運行環境，是一組資源的描述。只要是alloc里的資源，不管有沒有使 用，都是已經分配了的（不允許給Batch類型的任務使用）。不過google也提到這個alloc是可以并發使用，也可以是重復利用的，并發的意思是說 多個task可以同時跑在一個alloc里，重復利用的意思是說一個task跑完了可以繼續分配給另外一個task使用。

并發使用可以舉個例子：有兩個Job，一個job是web server實例，另一個job是相關的一些task，例如日志收集等等，這兩個job的task可以同時跑在一個alloc里，這樣日志收集模塊可以將 web server的日志從local disk傳輸到分布式文件系統里。

通常一個task會關聯一個alloc，一個job會關聯一個alloc set

2.5 Priority, quota, and admission control


每個task都會有一個優先級，高優先級的task可以搶占低優先級的task的資源，優先級是一個正整數，borg里將這些優先級分成4類：monitoring, production, batch, and best e ort

如果一個task被搶占了，通常會調度到別的機器上繼續運行（同一個cell），we disallow tasks in the production priority band to preempt one another （單指production級別的還是平級的job都不能相互搶占？）




優先級確定是否搶占，quota決定是否可以調度，quota表示所需要的資源，例如cpu，內存，網絡帶寬，磁盤配額等等

高優先級的task通常會比低優先級的task需要更多的quota，用戶申請資源的時候建議申請的比實際的資源占用高一些，以確保task不會因為超發而被kill掉，特別是內存。另外，多申請些資源也可以應對流量突發的情況。

優先級0可以有無窮大的quota，但通常會因為資源不足處于PENDING狀態而得不到調度




2.6 Naming and monitoring


僅僅創建和調度task運行是不夠的，從服務的角度來說，還需要有一個服務自動發現的機制，調度需要對用戶透明，做到用戶無感知。borg的Borg name service（BNS）就是為了解決這個問題的。

borg為每個task創建一個BNS名字：cell名 + job名 + task索引，BNS名字和task的hostname + port會被持久化到chubby上，通過DNS解析，用戶憑BNS名字就能找到task，另外，Job的task數量和每個task的健康狀態也會更新 到chubby上，這么做的目的主要是為了服務（這里的服務是指job本身，可能是個web server，也可能是個分布式存儲系統等等）的高可用，對用戶請求做負載均衡。




每個task都會有一個內置的http服務，暴漏一些task的健康信息和各種性能指標，例如rpc時延等等。borg通過監控某個特定的url來決定task是否正常，如果不正常，比如http返回錯誤碼等，就重啟task。

google還有一個叫sigma的系統，用戶通過web界面就可以直觀的觀察到用戶自己所有的job，cell狀態，甚至是task的健康信息，資源利 用率，日志，狀態變更歷史等等。日志是rotated的，避免打飛磁盤，另外，為了調試方便，即使task運行結束后，log也會保留一段時間。

If a job is not running Borg provides a “why pending?” annotation, together with guidance on how to modify the job’s resource requests to better fit the cell. We publish guidelines for “conforming” resource shapes that are likely to schedule easily.




3. Borg architecture


每個cell，包含一個控制器，borgmaster，同時cell里的每個機器，都運行著一個叫borglet的agent程序，不管是master和agent，都是用c++寫的

3.1 Borgmaster


每個master包含兩個進程，一個主進程，一個調度進程，主進程處理用戶請求，例如創建job，查詢job等等，It also manages state machines for all of the objects in the system (machines, tasks, allocs, etc.), communicates with the Borglets, and offers a web UI as a backup to Sigma.

master有5個副本，每個副本維護一份整個cell狀態的內存拷貝，并持久化到一個 highly-available, distributed, Paxos-based store 的本地磁盤上。通過paxos選出一個leader，負責處理cell狀態變更的所有請求，例如用戶提交一個job，停止一個job等。如果leader 宕機之后，chubby會選舉出另外一個leader來提供服務，整個過程大概需要10s左右，如果cell規模很大，這個時間可能會持續到1分鐘。

master會定期checkpoint，snapshot + change log，這樣可以將borgmaster恢復到以往任意的一個時間點，fixing it by hand in extremis; building a persistent log of events for future queries; and offline simulations.




TODO: Fauxmaster




3.2 Scheduling


當用戶提交一個job時，borgmaster會將job的元數據存儲到一個基于paxos的存儲系統里，同時將job的task放到pending隊 列，如上面我們提到的master架構，這個隊列會被另外一個調度器進程定期異步地掃描，調度器進程一旦發現某個機器能夠滿足task的運行條件（例如資 源是否足夠，是否符合某些特定約束，處理器架構，內核版本等等），就將task調度到改機器上運行（注意：調度器調度的對象是task而不是job）

The scan proceeds from high to low priority, modulated by a round-robin scheme within a priority to ensure fairness across users and avoid head-of-line blocking behind a large job.

調度算法包括兩部分：

1. feasibility checking: to find machines on which the task could run,
2. scoring: which picks one of the feasible machines.
</ol>

在feasibility checking階段，調度器檢查機器是否滿足job的約束條件以及是否有足夠的可用資源（包括已經分配給低優先級job的資源，這些資源是可以被搶占的）。這里可用資源的定義是：

1. 如果task的優先級是prod的，那么機器的可用資源需要減去task的limit
2. 如果task的優先級是non-prod的，那么機器上的可用資源只需要減去task已使用資源
</ol>

在scoring階段，對機器進行打分，挑選出最合適的一個機器運行task，打分機制：

1. 主要是根據borg內置的各種優化指標給候選調度結果打分，如最小化被搶占的Task數，盡量選擇已經下載了相同package的機器，降低硬件故障會影響的Task數，高低優先級混部等
2. 也支持用戶直接傳入的一些偏好設置
</ol>

打分模型主要有兩種：

1. E-PVM，通過多個維度計算出一個單一的指標，但是實際操作上，E-PVM算法經常會將task打散到不同的機器上，這樣的好處是讓機器保留一點資源以應對峰值負載，壞處是資源碎片太多，會導致某些大型的task調度不上來。所以這種算法也叫worst fit
2. 和worst fit對立的是best fit，就是盡可能的將task緊湊地調度到一個機器上，好處是減少資源碎片，有利于大型作業的調度，壞處是對Batch型任務不友好，而且無法應對任務的峰值負載
</ol>

borg目前使用的是介于worst fit和best fit之間的一個變種：hybrid，盡可能的減少閑置資源。

如果打分后選擇出來的機器可用資源不足，那么搶占就會發生，低優先級的作業首先會被踢掉，直到有足夠的空閑資源為止。被搶占的作業重新回到borgmaster的PENDING隊列里等待遷移（如果得不到資源也有餓死的可能）。

由于大部分包都是不會被修改的，所以borg在調度的時候還有一些優化的策略，為了減少每次部署時下載包的時間（平均25s左右），borg在調度時會優先選擇那些已經存在這個包的機器。（由于包很少被修改的特性，包是可以被cache的）




3.3 Borglet


borglet是borg運行在單機上的agent程序，borglet的職責如下：

1. 啟/停任務
2. 如果任務失敗，負責任務重啟
3. 任務之間的資源隔離，主要通過修改內核參數來實現，例如cgroup等等
4. 日志
5. 監控&報告 任務狀態
</ol>

borgmaster會定期輪詢所有的borglet，收集處理所有任務的運行狀態。master連agent的好處是有利于master控制負載，也有大部分分布式系統是agent去連master的，好處是master的異常處理邏輯相對簡單。

前面我們提到master是多副本的，leader負責向agent發送心跳，并根據agent的返回結果更新master的狀態，為了提高性能，心跳的 內容可能會被壓縮，只傳輸diff。另外，如果一個borglet長期不響應master的心跳，則master會認為該機器已經宕機，并且這機器上的所 有task都會被重新調度。如果borglet突然恢復，則master會讓該機器kill掉所有的task。

master宕機并不影響borglet以及正在運行的task，另外，borglet進程掛了也是不影響正在運行的task的。

3.4 Scalability


在google里，平均每個borgmaster需要管理數千臺機器（前面我們提過，一個中等規模的cell大約是1w臺服務器左右），有些cell每分 鐘提交的任務數就超過1w個，一個繁忙的borgmaster甚至可以用到10-14核，超過50G的內存。那么google如何解決集群規模不斷擴展帶 來的可擴展性問題呢？

早期的borgmaster只有一個簡單的，同步的循環過程：

1. 接收用戶請求
2. 調度任務
3. 和borglets通訊
</ol>

為了解決大集群，borgmaster分離出一個調度進程，兩個進程并行協作，當然，災備是有的。

分離出來的調度進程職責是：

1. 從elected master接收cell狀態 (including both assigned and pending work);
2. 更新本地拷貝
3. 預調度task（并非真正的調度）
4. 通知master確認調度結果（可能成功or失敗，例如過期）
</ol>

這個過程和Omega里的樂觀并發控制精神是一致的，borg最近還新增了一個feature，針對不同的workload類型使用不同的調度器

此外，borg針對可擴展性還做了幾個優化：

1. Score caching: 給機器打分的開銷是很大的，而且通常機器的屬性靜態的，task的屬性也不會經常發生變化，所以，這個結果可以cache，除非機器或者task屬性發生變化
2. Equivalence classes: 同一個job里的task通常都有一致的資源需求和約束條件，borg這將這些具有相同配置的task進行分類，打分的時候只按照分類給機器打分
3. Relaxed randomization: 只隨機取一部分機器或者緯度來進行打分，以提升效率。
</ol>

4. Availability


在一個大型的分布式系統里，單點故障是常態，運行在borg中的task，故障的原因既可能是機器宕機，也可能是被搶占調度，下圖是borg測試數據里發現的被搶占情況：



除了應用程序自身需要考慮容災之外，borg在此方面也做了不少事情，來提高job的可用性：

1. automatically reschedules evicted tasks, on a new machine if necessary
2. reduces correlated failures by spreading tasks of a job across failure domains such as machines, racks, and power domains
3. limits the allowed rate of task disruptions and the number of tasks from a job that can be simultaneously down during maintenance activities such as OS or machine upgrades
4. uses declarative desired-state representations and idempotent mutating operations, so that a failed client can harmlessly resubmit any forgotten requests
5. rate-limits finding new places for tasks from machines that become unreachable, because it cannot distinguish between large-scale machine failure and a network partition
6. avoids repeating task::machine pairings that cause task or machine crashes
7. recovers critical intermediate data written to local disk by repeatedly re-running a logsaver task (x2.4), even if the alloc it was attached to is terminated or moved to another machine. Users can set how long the system keeps trying; a few days is common
</ol> </div> 來自：http://pipul.org/2015/05/large-scale-cluster-management-at-google-with-borg/