0 背景
0.1 Borg簡介
Borg是Google内部的大規模叢集管理系統，已經延續十餘年的時間，大體上與MapReduce、GFS、BigTable、Chubby是同時代的産物，但一直被雪藏，直至今年才發表論文，披露其實作細節。論文連結（http://research.google.com/pubs/pub43438.html）。
Kubernetes被認為是Borg的開源版本（研發團隊部分重合、功能簡化聚焦、架構類似）。許多研發Borg的工程師現在正投身于Kubernetes系統，并從Borg中汲取經驗，不斷打磨Kubernetes。這也是我将此篇部落格歸類到“Docker& k8s”的原因。
0.2 筆者與Borg
筆者所在團隊的前輩曾經聯合騰訊公司研發過叢集管理系統T-Borg（公司内部代号），即Torca的原型。從名字上看，不難推測T-Borg也是類似Borg的叢集管理系統。筆者本人從碩士階段就一直從事雲平台/叢集管理系統的研發，期間也曾從T-Borg中汲取經驗。可以說我一直在關注和學習Borg系統，是以Borg公開發表論文，我也在第一時間關注。
1 Abstract & Introduction
Borg系統為Google進行叢集管理，其上運作着十萬級别的作業（Job）、數千級别的應用（App）、管理着數萬級别的機器（Machine）。
Borg的三大優勢：
（1）隐藏資源管理和錯誤處理的細節，使得使用者可以聚焦應用開發；
（2）高可靠性和高可用性，同時支援應用的高可靠和高可用；
（3）在數萬節點上有效運作工作負載。
個人解讀：這三條優勢說的已經比較明确了，如果再總結一下，可以歸結為（1）易用性（解決分布式共性問題，屏蔽細節）；（2）高可用性；（3）可擴充性（數萬節點）和高使用率（有效運作）。這些都是雲平台需要解決的核心問題。
Borg不是第一個關注這些問題的系統，卻是僅有的幾個如此大規模的系統之一。個人解讀：這句話說得較為低調，Borg有可能是這個世界上規模最大的叢集管理系統。
2 使用者視角 The user perspective
Borg的使用者是Google的開發人員和系統管理者。使用者以作業（Job）的形式向Borg送出工作，其中每個作業（Job）包含着一個或者多個運作相同程式的任務（task）。每個作業（Job）運作在同一個Borg單元（Cell）中，單元（Cell）是一組機器的集合。
2.1 工作負載
Borg Cell中運作着異構的工作負載，主要包括兩個部分：服務和批處理作業。服務長時間運作，幾乎不會停止，處理短期的、延遲敏感的請求，服務通常是面向終端使用者的産品（如Gmail、Google Docs、web search）和一些内部基礎設施服務（BigTable，即HBase的Google版本）。批處理作業運作時間在幾秒到幾天不等；它們對短期性能波動并不敏感。工作負載會在Cell上混合部署。
大部分應用架構已經運作在Borg上多年，包括内部的MapReduce、FlumeJava、Millwhell、Pregel。Google的分布式存儲系統也都運作在Borg之上，包括GFS、BigTable、Megastore等。
論文将高優先級的作業成為“生産型作業”（prod），将其他稱為“非生産型作業”（non-prod）。大部分長時間運作的服務都是生産型作業，生産型作業被配置設定了大約70%的CPU資源并占用了大約60%的使用率；同時被配置設定了大約55%的記憶體資源并占用了大約85%的記憶體使用率。
個人解讀：可以發現，在Google内部，無論是服務型還是批處理型，絕大多數作業都運作在Borg之上，包括其核心産品和非常重要的基礎設施。
2.2 叢集和單元Cluster and cells
一個叢集Cluster通常包括一個大規模的單元Cell和若幹個小規模的用于測試和特殊目的的單元Cell。Cell的規模大約是10k節點，且機器是異構的。
個人解讀：叢集Cluster包含若幹個單元Cell，單元Cell又包含大量的機器Machine。三者關系示意圖如下圖所示。相比于Cluster和Machine，Cell的概念較為少見。但其實Cell的概念在工程實踐中比較常見，很多項目在上線之初将Cluster作為一個整體使用，後來出于某種目的（絕大多數時候是就是為了測試）又将叢集分為兩部分使用，這樣叢集就被劃分成為一個主體Cell和一個用于測試的小Cell，與論文描述一緻。可以說，Cell的概念脫胎于實踐，而不是Google拍腦袋想出來的。
2.3 作業和任務Jobs and tasks
一個Borg作業Job具有屬性，包括name、owner、task數量等。Job具有限制（constraint）來強制其任務運作在具有特定屬性的機器上，例如處理器架構、OS版本、IP位址等。限制可以分為硬限制和軟限制，前者是需求，必須滿足；後者是偏好，盡量滿足。
個人解讀：文中提到了限制constraint的概念，在叢集排程領域提出限制主要是為了解決任務和叢集的異構性挑戰。本人在研究和實踐中也一直關注限制，并在工程中應用了自己的相關研究成果。這裡不做過多展開，如果要進一步了解限制的概念以及軟硬限制的差別，可以研讀下面兩篇論文：Modelingand Synthesizing Task Placement Constraints in Google Compute Cluster（http://research.google.com/pubs/pub36953.html）和Alsched: Algebraic Scheduling of Mixed Workloads in Heterogeneous Clouds（http://www.pdlNaNu.edu/PDL-FTP/CloudComputing/alsched-socc2012.pdf）。
每個任務，可以映射為一個container中的一組Linux程式。Borg絕大部分工作負載不運作在虛拟機中，這主要是由于虛拟機性能開銷較大，此外一些硬體不支援虛拟化。
一個任務也具有屬性，例如資源需求和task index。Borg程式采用靜态連結庫，以減少對運作環境的依賴，軟體包中主要包括二進制程式和資料檔案。
個人解讀：在雲平台工程實踐中，打包和部署是一個難以忽視的重要挑戰。Docker基本上就是憑借解決部署問題而風靡開源界的。在Docker出現之前，傳統虛拟機（例如KVM、Xen）雖然支援鏡像部署，但是性能開銷較大；輕量級虛拟化（例如LXC和更底層的cgroups）雖然性能開銷小，但是自身不具備鏡像，打包部署瑣碎繁雜。Docker兼具二者優勢，解決了這個問題。
使用者向Borg發送RPC用以操作作業。使用者可以送出作業、查詢作業，也可以改變作業、任務屬性。作業Job和任務task的狀态圖如下圖所示。使用者可以觸發submit、kill和update事務。
個人解讀：作業Job和任務task的生命周期管理要基于這個狀态圖來實作，特别是錯誤處理，要在狀态圖的基礎上基于事件觸發來實作。例如，在我實作的系統中，當任務finish、fail、kill、lost時，系統會根據特定事件進行專門處理。
任務Task在被搶占之前，會收到通知，二者都是通過Unix信号，搶占通過SIGKILL信号，程式直接退出；通知通過SIGTERM信号，可以被處理。這樣做主要是為了讓程式關閉前清理環境、儲存狀态、完成目前請求等。
個人解讀：雲平台需要支援任務“優雅”的退出，Borg不是個例，LXC和Docker也有類似功能。例如，docker stop指令就是優雅退出，其機制與Borg類似；而docker kill則是直接退出。
2.4 Allocs
一個Borg alloc是一台machine上預留資源的集合，可以用于一個或多個任務運作。Alloc被用于為未來的task預留資源，用來在停止和再次啟動任務之間保持資源，或者将不同作業Job的任務task聚合在一起運作（例如一個web伺服器執行個體和一個相關的logsaver）。
一個Alloc集合類似一個job：它是在多個機器上預留資源的一組alloc。一旦一個alloc集合被建立，一個或者多個作業Job就可以被送出在其中運作。簡而言之，一個task與一個alloc對應，一個job與一個alloc集合對應。
個人解讀：Alloc是allocation的簡稱，應該可以了解為資源配置設定對應的邏輯單元，或者直接了解為資源單元。初讀覺得alloc類似container，但是由于一個alloc可以支援一個或多個task運作，是以alloc實際上更類似Kubernetes中的pod（一個pod中包含若幹個container）。另外，Kubernetes中沒有Job和Task的概念，我個人感覺Kubernetes中的Service類似于Borg中Job（僅限于服務型Job）的概念，Kubernetes中container類似于Borg中task的概念。當然，僅是類似，說完全相同是不準确的。
2.5 優先級，配額和準入控制 Priority, quota, and admission control
每個作業都有一個優先級，具體形式是一個小的正整數。Borg定義非重疊優先級，包括：monitoring, production, batch, and best effort (also known as testing or free)，生産型作業（prod job）包含前兩種優先級。
為了避免“搶占洪流”，Borg不允許一個生産型作業區搶占另一個，隻允許生産型作業搶占非生産型作業。
資源配額Quota是一組資源量化表達式（CPU、RAM、Disk等），它與一個優先級和一個時間段對應。如果Quota不足，作業送出會被拒絕。
個人解讀：在我們的工程實踐中，Quota設定沒有如此細粒度，但是基本思路一緻。有一點不同需要說明一下，在Borg中如果Quota不足會立即拒絕作業送出；但是在我們的系統中，Quota不足并不影響作業送出，作業會進入等待隊列，待前序作業運作完畢、Quota充足後，系統再自動排程和運作該作業。起初，我對于Borg的設計不是很了解，拒絕送出不是更“麻煩”嗎？後來我思考，我的系統的使用者多是不太熟悉分布式的應用開發人員，希望我們盡可能的為他們屏蔽細節，是以我們自動化的進行送出、排程和運作；Borg的使用者是Google開發人員，是高水準的程式員，我猜測他們需要了解一些必要的“細節”來進行後續操作。前者更需要便利，後者更需要靈活，使用者的不同導緻系統設計機制的不同。
2.6 名字服務和監控 Naming and monitoring
僅僅是建立和放置任務是不夠的，一個服務的用戶端或者其他系統需要找到服務，當服務被重新定位到新機器之後也是如此。為此，Borg建立了一個穩定的Borg名字服務（BNS），用于為每個任務命名。任務名字包括cell name、job name和task number這個三元組。Borg将任務的主機名和端口号寫入Chubby中的一緻性、高可用檔案。Borg也會将作業規模和任務健康資訊寫入Chubby，負載均衡器LoadBalancer據此來進行路由。
個人解讀：名字服務也被稱為服務發現，通常使用高可用存儲系統（例如Chubby，可以視為Google内部的Zookeeper，當然現在開源界etcd似乎更火）存儲任務名字與通路方式endpoint的映射關系。在Borg中，任務名字包括cell name、job name和task number三元組；通路方式endpoint則是hostname和port二進制組。用戶端或其他系統需要通路服務時，就通路BNS根據任務名字查詢通路方式endpoint，以此來“發現”服務。
每個任務會建構HTTP server來釋出其健康資訊和性能名額，Borg根據URL來監控任務，并重新開機異常任務。
個人解讀：在我們的工程實踐中，每個任務（更準确說其實是虛拟機）中都會包含一個代理agent，這個代理開機自啟，定時上傳心跳，内含健康資訊和性能名額。可以說上傳内容是類似的，但是通信方式是不同的。我們是虛拟機代理定時主動上傳心跳，不過最近感覺“釋出資訊，由需要該資訊的元件來查詢”這種服務化的通信方式更為優雅和主流。
3 Borg架構 Borg architecture
一個Borg cell包含一組機器集合、一個邏輯中央控制器Borgmaster、每台機器上都運作的代理程序Borglet。Borg的所有元件都使用C++開發。
個人解讀：我們的雲平台元件也都使用C++開發，基本屬于雲平台慣例。不過，由于Docker、Kubernetes、etcd等開源系統都是基于Golang開發，我最近正在學習Golang。
3.1 Borgmaster
Borgmaster包含兩類程序：主Borgmaster程序和分離的排程器程序。主Borgmaster程序處理用戶端RPC；管理系統中所有對象Object的狀态機，包括machines、tasks、allocs；與Borglet通信；提供webUI。
Borgmaster邏輯上一個程序，但是擁有5個副本。每個Borgmaster副本維護cell狀态的一份記憶體副本，cell狀态同時在高可用、分布式、基于Paxos的存儲系統中做本地磁盤持久化存儲。一個單一的被選舉的master既是Paxos leader，也是狀态管理者。當cell啟動或者被選舉master挂掉時，系統會選舉Borgmaster，選舉機制按照Paxos算法流程進行。
個人解讀：Borgmaster基于高可用、分布式、基于Paxos的存儲系統進行中繼資料持久化和熱Borgmaster備份，以此實作Borg系統的高可用。關于這個基于Paxos的存儲系統，在Google内部應該就是Chubby，不過不知道為何這裡沒有提及，難道還有新的系統？開源界etcd最近比較火，但是etcd沒有采用Paxos算法，而是使用更為簡單且易于了解的raft。這裡還是采用Paxos算法，本人暫時還認識不到替代Chubby的必要性。
Borgmaster的狀态會定時設定checkpoint，具體形式就是在Paxos store中存儲周期性的鏡像snapshot和增量更改日志。
3.2 排程Scheduling
當作業被送出，Borgmaster将其記錄到Paxos store中，并将作業的任務增加到等待隊列中。排程器異步浏覽該隊列，并将任務配置設定給機器。排程算法包括兩個部分：可行性檢查和打分。
可行性檢查，用于找到滿足任務限制、具備足夠可用資源的一組機器；打分，則是在“可行機器”中根據使用者偏好，為機器打分。使用者偏好主要是系統内置的标準，例如挑選具有任務軟體包的機器、分散任務到不同的失敗域中（出于容錯考慮）。
個人解讀：在我們的學術研究和工程實踐中，排程也分為這兩個部分。我們也将這個排程流程和限制有機結合起來，可行性檢查用于處理硬限制，其中具備足夠可用資源也可以看作一種特殊的硬限制；打分用于處理軟限制，符合“盡量滿足軟限制”的原則。
Borg使用不同的政策進行打分。實踐中，E-PVN（worst fit）會将任務分散到不同的機器上；best fit，會盡量“緊湊”的使用機器，以減少資源碎片。Borg目前使用一種混合模型，盡量減少“受困資源”。
3.3 Borglet
Borglet是運作在每台machine上的本地Borg代理，管理本地的任務和資源。Borgmaster會周期性地向每一個Borglet拉取目前狀态。這樣做更易于Borgmaster控制通信速度，避免“恢複風暴”。
為了性能可擴充性，每個Borgmaster副本會運作一個無狀态的link shard去處理與部分Borglet通信。當Borgmaster重新選舉時，會重新分區。Borgmaster副本會聚合和壓縮資訊，僅僅向被選舉master報告狀态機的不同部分，以此減少更新負載。
如果Borglet多輪沒有響應資源查詢，則會被标記為down。運作其上的任務會被重新排程到其他機器。如果恢複通信，則Borgmaster會通知Borglet殺死已經重新排程的任務，以此保證一緻性。
3.4 規模可擴充性Scalability
我們不确定Borg中心化架構的可擴充性極限在哪裡；不過到目前為止，每次接近極限，我們都能設法消除它。一個Borgmaster可以管理數千台機器，任務到達率約為每分鐘10K個任務。一個忙碌的Borgmaster使用10-14個CPUcore和50GB記憶體。
個人解讀：這句話有點牛啊！對于分布式領域的關鍵挑戰——可擴充性，Google人員說還沒有真正遇到過極限。這句話的霸氣程度不亞于在酒桌上說“我從來沒醉過”（哈哈哈哈），當然最關鍵的是人家不是嘴炮，人家真的做到了。
為了提升可擴充性，我們将排程器分割為獨立程序，這樣它可以與Borgmaster并行進行操作。排程器具備多個副本，每個排程器在cell狀态的副本上進行操作。它重複以下操作：從被選舉master中檢索狀态變更；更新本地狀态副本；進行排程、配置設定任務；将配置設定通知被選舉master。Master會檢查排程器的排程操作，如果發生排程沖突則再下一輪重新排程，否則接受并應用該排程結果。這套機制與Omega一文中的樂觀并發控制高度相似。此外，Borg最近支援為不同負載類型使用不同排程器。
個人解讀：Omega的核心思想就是采用樂觀并發控制，使得排程并行化，解決排程器可能成為叢集系統性能瓶頸的問題，提高系統的可擴充性。根據上述描述，Borg多排程器并發排程采用了這種機制。
為了提高系統可擴充性，Borg排程器還作了幾種優化，分别是得分緩存（可以将可行性檢查和打分結果緩存下來）、等價類（同一job中的task通常具有類似的限制，是以可以将多個任務視為一個等價類）、輕松随機化（在大規模cell中計算所有機器的可行性和得分代價太高，可以随機周遊直到找到一個“足夠好”的機器）。
4 可用性 Availability
失敗在大規模系統中非常常見。本文列舉了Borg提高可用性的例子：
（1）自動重新排程器被驅逐的任務；
（2）為了降低相關失敗，将任務分散到不同的失敗域中；
（3）限制一個作業中任務的個數和中斷率；
（4）限制任務重新排程的速率，因為不能區分大規模機器故障和網絡分區；
（5）避免引發錯誤的任務-機器比對對；
（6）關鍵資料持久化，寫入磁盤。
5 使用率 Utilization
本節首先通過實驗證明，混合部署（prod負載和non-prod負載）比獨立部署具有更高的使用率。實驗結果下圖。
随後，結合實驗說明，幾種方法可以提高叢集使用率，具體包括Cell sharing、Large cell、Fine-grained resource requests和Resource reclamation。前幾種方法都比較直覺，不做展開。Resource reclamation比較有意思，重點闡述。
一個作業（job）可以定義一個資源上限（resource limit），資源上限用于Borg決定使用者是否具有足夠的資源配額（quota）來送出作業（job），并且用于決定是否具有足夠的空閑資源來排程任務。因為Borg會kill掉一個嘗試使用更多RAM和disk空間資源（相比于其申請的資源）的task，或者節流CPU資源（相比于其要求的），是以使用者總是申請更多的資源（相比其實際所有的）。此外，一些任務偶爾會使用其所有資源，但大部分時間沒有。
個人解讀：使用者總是會處于“心理安全”和負載高峰波動等原因，申請較多的資源，但大部分時候，任務不會真正使用如此之多的資源。這就造成了資源浪費。
對于可以容忍低品質資源的工作（例如批處理作業），Borg會評估任務将使用的資源，并回收空閑資源。這個整個過程稱為資源回收（resource reclamation）。評估過程稱為任務預留（task reservation）。最初的預留值與其資源請求一緻，然後300秒之後，會慢慢降低到實際使用率外加一個安全邊緣。如果使用率超過資源預留值，預留值會快速增長。
這裡引用華為鐘誠的圖檔，直覺的表明實際使用資源、預留資源、資源上限的關系。
6 隔離 Isolation
包括安全隔離和性能隔離，這裡不做展開。
7 相關工作 Related work
資源排程是熱點研究問題，具有許多相關研究。論文介紹了許多相關系統，我這裡找幾個重點系統進行簡要分析。
7.1 Mesos
Mesos通過resourceoffer機制，将資源管理和放置功能分開。Mesos的中央資料總管（Mesos master）負責資源管理，多個架構（例如Hadoop、Spark）負責具體的任務放置（即任務排程）。Borg采用基于請求（request-offer）的機制，而非基于offer的機制，更易于系統擴充。
7.2 YARN
YARN是Hadoop中心化的叢集管理器。每個應用都有一個管理器（AM）用于向中央資料總管（RM）協商請求資源。這種機制類似于2008年以前Borg為Google MapReduce配置設定資源的機制。
7.3 阿裡巴巴Fuxi
Fuxi不是像Borg那樣把task排程到合适的machine上，而是“反向排程”，為最近可用的machine比對任務task。
7.4 Omega
Omega支援并發排程，其機制在前文3.4節已經介紹.
7.5 Kubernetes
建設Borg的許多工程師正在研發Kubernetes，并将Borg的經驗應用到Kubernetes之中。
8 經驗以及未來工作 Lessons and futurework
介紹了一些經驗教訓。最後提到Google将繼續改進Borg，并将其中的經驗應用到Kubernetes之中。