背景 1

任務 2

Borg 3

——任務配額，分級，價格機制 4

——混部 4

——架構 5

——共享與隔離 6

——Storage Job 7

——效果 8

——總結 9

Borg: The Next Generation 9

——優先順序 10

——資源利用率 11

——極端的傾斜 12

——Autopilot 12

——關於Centralized vs Decentralized 13

——其他 14

Twine 14

——架構 15

——Host Profile 15

——Task Control API 16

——經濟小型機 17

——Scalability 18

——其他 19

Protean 19

——異構叢集 20

——Rule-Based Allocation 20

——架構和實現 22

——評估 23

Mesos, YARN, etc 24

——Mesos 24

——YARN 27

Kubernetes 29

——Omega 29

——K8S 31

總結 32

背景

最大的網際網路公司們早已擁有超過百萬臺的機器。機器的用地，採購，能耗都佔據了公司一大部分的成本開支。如何更好的利用這些海量資源很自然的成為了一個關鍵的技術問題。

從微觀角度，隨著摩爾定律難以維持，上百個CPU core，NUMA架構，TB級DRAM，異構計算開始出現，叢集通常混合多種不同規格和時代的機器。簡單的應用層任務獨佔物理機通常導致極大資源浪費。大約20年前，Xen， KVM等技術讓應用可以透過VM的方式靈活切分物理機資源，逐步解決資源共享帶來的安全、隔離等問題。而cgroup， container將解決問題的方法進一步的輕量化了。應用的開發可以不用關注IaaS層，更加的敏捷，靈活。

而叢集管理系統則承當了應用任務和IaaS層間的橋樑角色，解決資源利用率，QoS，彈性伸縮等一系列問題。然而，技術方案在許多公司很長的發展階段並不是特別明確，充滿了曲折，探索，轉型。即使是今天依然能看到歷史留下來的痕跡。

綜合考慮公司組織架構、研發難度，實際場景會變成出乎意料的複雜的混合雲：

組織內（公司、事業群、部門）會有保留自有的叢集。有非常多可能的原因，比如安全，可自主定製，歷史任務可遷移性，決策層偏好等等。

使用外部的叢集。

考慮到自身研發能力，成本等原因，中小公司常常會使用公有云。比如AWS S3， Google BigQuery，TPU等等。

很多時候，大資料和高效能計算叢集會由獨立的組織負責開發和運營，與上層的大資料元件一起，形成一個獨立的組織架構。比如大資料部門會負責在物理機上部署YARN叢集，同時提供Spark， Hive等大資料計算元件。或者機器學習部門獨立的CPU、GPU訓練叢集。

大公司的某些業務組織因為特殊人才負責帶隊，會有擅長的技術領域。比如有些擅長微服務框架開發，有些擅長分散式資料庫，有些擅長訊息中介軟體。這些元件和自己的組織叢集管理系統，海量應用層任務繫結，形成了公司內部的第三方雲，也限制了多雲融合。

那麼對於上層應用的開發者和組織管理者就會面臨一些難題。

開發者。應用開發者為了完成任務需要對接多套叢集管理系統。比如線上服務需要部署在叢集A，線上服務產生的日誌需要匯入到叢集B中處理。對應就可能需要掌握多套名字服務，閘道器路由，配置系統，微服務框架，以及他們之間的打通。更復雜問題，比如高效能計算和大資料儲存距離太遠，線上服務和資料庫太遠等等。

組織管理者。組織管理者關注人的效率和物理資源的效率。人的效率很大一部分體現在開發人員身上，上面已簡單描述。而資源的效率就是我們下面想詳細展開的問題。

任務

從任務的層面，任務有非常多不同的種類的和特性，有多種分類方式。以下舉幾個例子：

latency sensitive online service

。比如搜尋引擎和推薦系統中面向使用者搜尋和推薦請求的實時召回、排序服務。這類任務非常的挑剔，有嚴格長尾耗時要求。另外這裡面很大一部分具有明顯的潮汐現象，也就是白天短時間忙晚上閒。

後面也會被稱作

prod service, 線上服務

。雖然他們不太等價，但是這裡不失一般性。

batch, stream jobs

。batch任務和stream任務的特性其實不太一樣。batch任務常常是突發且短暫的，短期內希望使用很多的資源完成一個比較明確量級的任務。許多batch processing engine有較強的容錯能力，可以容忍較多的失敗重試，最終完成任務。而stream有時候像online service。它一直在跑著，不斷的處理”最近“（window）到來的資料，彈性和容錯能力常常不如batch processing那麼強。在實際工作中，大資料團隊在關注實時性等指標時，常常單純（委婉）的推崇stream processing。但是當後文討論排程時我們會發現，當考慮到成本等其他維度時，batch processing有它獨特的優勢。

HPC jobs

。因為AI技術近幾年的火熱和有效性，深度學習模型的GPU訓練任務增長非常迅猛。考慮到大型網際網路公司的核心業務（搜尋，推薦，廣告）強烈依賴AI的能力，可以預期HPC jobs的比例會進一步提高。HPC任務使用的單臺機器成本（e。g。 單機8GPU）會遠超普通伺服器，同時還會為GPU配套使用infiniband， 100Gbps+乙太網進行高速互聯。由於GPU的價格較為昂貴，任務從多目標最佳化（CPU，記憶體， etc）變成了更關注GPU利用率。

Borg

Large-scale cluster management at Google with Borg， EuroSys， 2015

Borg論文的發表對於很多做叢集管理的研發來說是一個重新整理認知的過程。與外界用得火熱的開源方案（YARN，Mesos， etc）不少都有較大的差異。下面展開一些關鍵點。

任務配額，分級，價格機制

任務分成多個不同的priority band（先過度簡單理解為優先順序）。高優先順序任務的在缺少資源時可以搶佔低優先順序任務。

任務優先順序越高，價格越高。有預算管理機制負責各種優先順序的配額。

高優先順序的任務配額不進行超賣，不考慮特殊約束，通常能執行起來。

這套”市場化“，”契約“的機制表面上和技術無關，但是解決了許多技術無法解決的上層建築問題，讓技術可以有機的成長。舉幾個反例：

無價格和優先順序時，先到先得，應用傾向於佔著資源不放，透過各種手段製造高利用率。

當沒有成本約束時，過度實時化、大規模、線上化，無法充分利用業務潮汐現象釋放的空閒資源，和資源分配自然出現的碎片資源。

避免了”人治“導致的問題。透過刷臉，找老闆，天天騷擾等各種手段爭取機器。

混部

Borg應該是非常早成功大規模運營的混部叢集管理系統。Borg的混部包含了前面提到latency sensitive online service， batch jobs， distributed file system等各種型別的任務。這種徹底的混部對於叢集管理系統的隔離能力是有非常高要求的，後面會討論。

這裡講一下為什麼要混部的原則性問題。

保障prod service的擴容能力。原因有點繞。現實情況通常滿足兩個前提。1。 資源永遠是不夠用的，除非平臺太難用。2。 叢集會被要求飽和部署，甚至超賣來提高利用率。prod service（通常是線上服務）在高峰期，當遇到突發情況時如果叢集中沒有低優先順序的”軟柿子“可以捏，很容易導致擴不出去的問題。

borg不會超賣prod優先順序資源。

按原文描述： prod jobs are allocated about 70% of the total CPU resources and represent about 60% of the total CPU usage

降低non-prod成本。由於prod service在大量非高峰期有冗餘的資源，加上人員保守過度購買，non-prod有大量的”閒置“資源可以使用。這部分資源因為基本是prod service買單，叢集可以透過非常低的價格賣給non-prod，鼓勵使用者合理錯峰部分計算，或者開發具有較好伸縮和容錯能力的non-prod任務，比如類似mapreduce的離線批任務。

架構

BorgMaster

有多個replica，其中一個透過paxos選為leader，負責狀態變更。當leader掛了後，會有其他replica被選為leader，重構記憶體狀態，成為新的leader。進而保障了BorgMaster的高可用性。

Scheduler

被單獨的拆了出來。任務提交到BorgMaster後會進入佇列，然後非同步的被scheduler獲取後進行排程。佇列即優先考慮了高優先順序任務，同時也規避低優先順序被head-of-line blocking。（詳見後面Omega）

具體的：

scheduler會具體的找到每個task最合適的placement。

scheduler讓使用者設定preference（軟約束），但更傾向於內建的策略，來最佳化叢集排程的多個維度指標。比如減少搶佔，任務容災，主動混部搭配等等。

scheduler使用了cache技術來提高排程的效率和可擴充套件性。

scheduler後來也吸取了Omega等的經驗，對不同workload使用了不同的scheduler，並透過optimistic concurrency control解決衝突。

Borglet

在大規模叢集的管理上扮演了比較重要的角色。Borglet被部署在每臺機器上，啟動、停止任務，管理本地的配置，實時隔離性管理，上報資訊給Master。

這裡有個小細節，由於Borglet非常多，每個Master replica都只負責和一個shard的Borglet通訊，各個Master replica進行資訊的彙總，壓縮。

一個10~14個core和40GB記憶體的BorgMaster可以管理數千臺機器。

共享與隔離

共享和隔離的問題值得單獨重點討論。隔離為了保障QoS和SLO，共享為了提高資源利用率。基於上面提到的“市場機制”，共享和隔離就有了技術上的操作空間。

——“50% of our machines run 9 or more tasks； a 90%ile machine has about 25 tasks and will be running about 4500 threads”

Borg內，不同優先順序的任務會混合部署在同一個叢集的物理機上。低優先順序任務資源被超賣。當高優先順序任務在低峰期實際使用資源低於申請的資源時，低優先順序資源可以借用（reclaim）這些資源。比如線上任務申請了10個CPU core，但是利用率夜間只有10%，低優先順序任務就可以使用這10個CPU core的部分時間片。

可以看到，reclaim的資源很有效的利用了資源，運行了更多的任務：

“About 20% of the workload （§6。2） runs in reclaimed resources in a median cell。”

隔離可以從3個維度討論：

核心：

Linux scheduler&cgroup隔離。對記憶體頻寬和L3 cache等一些OS通常不管的方面還是比較難。

節點：

Borglet會對應用程序進行預判，並基於持續監控的記憶體，IO等指標，調整可壓縮資源，或者在不可壓縮資源發生競爭時殺掉低優先順序任務。

叢集：

Scheduler也會基於應用畫像，混部策略，搶佔SLO等合理的分配機器上不同優先順序和資源使用情況的任務。

總體而言，這塊技術還是非常有挑戰性的。從微觀到宏觀都有非常多需要最佳化和除錯。

Storage Job

這方面感覺Borg文章並沒有描述的太詳細。但是個人認為Storage的部署屬於devils is in the details。Borg應該是使用了某種特殊的策略將Storage合理的打散部署在了各個叢集上。

在文中提到空機器依然會部署storage servers：“This leaves some machines empty of user jobs （they still run storage servers）”。因此，可能類似K8S上的DaemonSet。

Persistent （Or Semi-Persistent） Storage的需求其實無論對線上服務還是部分機器學習任務都非常重要。雖然現在經常談計算儲存分離，但是1。 它們不能離得太遠。2。 本地儲存對於很多應用最佳化都很大作用。

本地儲存對於許多記憶體型任務都是降冷（thanks to power-law distribution），或者降低記憶體突發增長和成本的寶貴手段。但是本地儲存的隔離和排程對容器平臺提出了挑戰和需求，常常被忽略或者簡單處理。

遠端儲存。遠端儲存帶來的存算分離使得部署策略可以更加靈活的最佳化。但是在實際操作時，他們的距離儘量不應該跨機房。跨機房對於線上NoSQL儲存會造成高延遲，對於離線資料批處理會造成CPU和GPU利用率低等問題。

效果

Borg對於業界常見的分離prod， non-prod做法進行了實驗評估，結論顯示分離會導致顯著的額外資源開銷。

segregating prod and non-prod work would need 20–30% more machines in the median cell to run our workload

另外，如果將大的任務獨立拆分池子部署，或者壓縮叢集的規模，也會造成顯著的額外資源開銷。

For this test， we split off a user’s workload into a new cell if they consumed at least 10 TiB of memory （or 100 TiB）。 Our existing policy looks good： even with the larger threshold， we would need 2–16× as many cells， and 20–150% additional machines。

基於Borg優異的隔離技術，混部從CPI指標看來，沒有造成顯著的CPU額外開銷和干擾。

從下圖可以看到，limit是任務申請的資源，usage是任務實際使用的資源，兩者有比較大的差異，可以理解成過度購買。Borg透過預測，給出了reservation來預估任務可能會使用的資源上限。limit - reservation的差就是reclaim可以額外用起來（賣出去）的資源。reservation的預測需要儘可能的接近usage，來騰出更多的資源，同時還要保障usage很少超過reservation，保障使用reclaim資源的任務不被頻繁殺死或者擠壓。

總結

這篇論文對業界的衝擊比較大。文章以有限的篇幅大量的描述了Borg的具體細節。我主要挑了一些關注的重點討論，沒有展開復述所有細節。

Borg： The Next Generation

時隔5年，Borg又發了一片論文，單從利用率就可以看出Borg的技術在持續的提升。叢集的利用率均值達到了驚人的60%。這裡還包含了許多資源被有意的空閒出來應對關鍵服務的突發情況。Borg的一個比較大的功能演進，放在了另一篇文章：Autopilot： workload autoscaling at Google，2020。

“The fraction of a cell’s total resource capacity allocated during each hour-long interval。”

優先順序

Borg對任務的優先等級做了進一步的演進：

Free Tier:

免費任務，任何人都可以用這個優先順序提交任務而不需申請任何預算。據個人使用體驗，如果將每個task拆的比較小，使用較多的task，從全球找到一些負載不是特別高的的叢集，夜間是可以跑起來的，但是白天可能會被高頻殺死。我在實習的時候用這個免費優先順序分析了大量Google File System的Trace，做了個非常重要的最佳化，整個專案無需申請任何預算。

Best-effort batch Tier:

這個優先順序的任務會價格比較便宜，但是依然沒有SLO。使用了特殊的batch-scheduler排程。

Mid Tier:

這個優先順序的任務有了SLO的保障。據個人經驗，很多團隊的正式離線任務，只要不是對時間非常敏感，通常會使用這個優先順序完成。比如在夜間執行。這個優先順序任務通常可以成功被排程執行，但是偶爾可能會有部分節點被搶佔，因此需要具備一定的自動Recovery能力。

Production Tier： 大部分重要的線上服務都執行在這個優先順序。個人經驗這個優先順序的任務從來沒有出現因為資源不足無法部署的問題（通常會有預先規劃capacity）。也幾乎沒有發現被搶佔的問題。偶爾會有壞機和核心升級導致的任務重啟。

Monitoring Tier： 這個優先順序稍微有點出乎意料。文章說監控系統會執行在這個等級。細想也合理。如果系統無法被監控，那其他任務的可用也就無從談起了。因此比所有任務優先順序都高也有道理。

資源利用率

前面有圖已經展示了Borg較高的1 hour-average利用率。從這張allocation圖，能看出來，prod資源是基本沒有超賣的，保持在總capacity的100%以內。而其他mid， beb等資源則明顯超賣。

顯然如果prod把limit用滿，其他是跑不起來的。但是現實情況就是prod無論是短期波段、還是晝夜潮汐，或者人為設定limit偏高，都導致了巨大的額外可以使用的資源。allocation可以達到capacity 200%，也就是

透過混部+優先順序+超賣來達到保障QoS+Utiliaztion的目的

。

極端的傾斜

文章花了很大的篇幅來描述傾斜的極端程度，並且越來越極端：

The heavy-tailed property we observed in the 2019 traces is even more extreme： the largest 1% of jobs comprise 99。2% of the CPU load （99。1% of the memory load）， and the largest 0。1% of jobs comprise 93。1% （92。6%） of the load。

這對於叢集管理系統的設計顯然是有重要影響的，比如，排程需要區分的對待這兩類任務（hogs vs mices）。

Autopilot

問題：

任務超過了limit可能會被叢集管理系統kill掉。因此為了避免這種問題，使用者傾向於設定過大的limit。導致了實際usage和申請limit的巨大差異（slack）。

因此，Borg的思路是預期讓人來做這個設定，不如我們自動的設定一個更優的。從實驗資料上看它的確做到了：

“In practice， Autopiloted jobs have a slack of just 23%， compared with 46% for manually-managed jobs。”

關於Centralized vs Decentralized

這裡提前討論一下叢集管理裡Job/Task Lifecycle的一些問題。

在實際場景中，Job/Task Lifecycle的管理有一定自定義的需求。比如被搶佔前處理退出清理，基於應用層資訊的擴縮容等等。可以很大的提高Job/Task的生存質量，降低資源成本等等。

然而，實際經驗上，實現Job/Task Lifecycle管理功能並不是一件很容易的事。對於許多應用層開發團隊，需要消耗許多人力和時間。同時也會導致類似需求的重複建造。

基於以上觀察，就很容易解釋Borg和K8S設計上的一些差異了。

K8S面向的事廣闊的開源社群，必須要將kube-controller開放出來，讓使用者自定義CRD。

Borg面向的是封閉的公司內部。由中心化的團隊統一抽象一些常見的需求，完成Job/Task Lifecycle功能的實現，並提供宣告式的介面給內部團隊。

其他

AllocSet依然被提起它對於任務資源預留的作用。

Job Dependency進一步改進了任務生命週期依賴的問題。

Batch scheduler體現了任務排程策略被單獨拆出來，特事特辦的普遍架構。

任務提交頻率比以前更高了。（這背後可能是上層系統自動化程度的提高）

Twine

Twine： A Unified Cluster Management System for Shared Infrastructure，2020

Facebook和Google就隔幾條街，顯然兩邊很多地方會互相借鑑。比如把一些給各種計算任務silo的小叢集變成統一的叢集管理系統。

架構

Capacity Portal： 配置使用者的quota

Frontend： 使用者提交任務的入口。

Scheduler： 管理job/task的lifecycle。Scheudler提供TaskControl API給使用者控制自己軟體宣告週期的能力。

Allocator：把任務分配到有資源的機器上。

Rebalancer： 非同步持續的最佳化部署。

ResourceBroker： 儲存機器資源的資訊。

Sidekick：調整機器資源的profile。

SRM：自動調整任務的規格。

Host Profile

考慮到Borg提到的1%任務佔用了99%以上資源，那麼叢集就很有必要為這些資源定製化的提供最佳化。而不應該被99%的任務拖慢這1%任務的效率。

Twine的創新解法是可以定製化Host Profile，比如Page Size的大小，底層驅動的配置，作業系統版本。每個細節的調優可能為某些頭部任務帶來~10%的額外收益，總體的收益是非常大的。

透過配合排程策略和Host Profile的配置，Twine可以做到這點，同時不影響統一混合部署。

Task Control API

Built-in Application-level Scheduler：batch， stream， stateful等不同的任務型別實現自己的Scheduler。Scheduler透過TaskControl API來將一部分邏輯交給這些Application-level Scheduler。

現在各種叢集管理系統都或多或少的給上層任務一定的控制權，但是會有些差異。叢集管理系統提供的空間有多有少：

配置項級。

這種的騰挪空間一般較少，相當於系統內建了幾種能力，使用者選擇其中一種。前面的Borg感覺比較接近這種型別。

Controller級。

Scheduler會請求應用自定義的Controller或者讓Controller自己請求Scheduler。Controller可能是一個線上服務，透過接收配置，監控應用狀態，內建狀態機邏輯來干預叢集對任務的控制。Twine更接近這個情況。TaskController API嚴格的定義了可以做的操作，比如是否approve scheduler的操作。K8S也類似。

當然，這些Scheduler通常只是給少量自定義的空間。Scheduler有最終的許可權，以最佳化叢集整體的利用率，SLO為目標。比如在特殊情況下可以無視自定義Controller殺死任務。

下面這句話還是挺那人尋味，隱藏不少detail。感覺是allocator會預分配一大塊資源長時間給Batch Scheduler，Batch Scheduler會把資源用來給多個任務在一段時間內複用。感覺有點像Mesos或者YARN。但是這樣就不太好解決多優先順序的搶佔問題，混部也不容易做徹底。下文的Omega則有不同的觀點。

Twine scheduler and allocator do not directly manage batch jobs， whose lifetime might last just a few seconds and cause high scheduling loads。 The applicationlevel batch scheduler acquires resources from Twine in the form of Twine tasks。 It reuses these tasks over a long period of time to host different batch jobs， avoiding frequent host profile changes。

經濟小型機

值得一提的事，Twine的叢集使用數百萬高性價比的小機器（18 core CPU and 64GB RAM）。小機器能帶來接近20%的TCO節省。

關於這一點，我還是有一些質疑的。

為了達到這個目標，許多上層應用需要進行對應的改造，比如支援RAM+磁碟的模式。這對於很多應用的確是可以的，但是對於許多應用，這造成了許多額外的軟體改造開發，甚至可能耽誤業務的快速推進。這裡相當於進行了

“成本轉移”。

總體成本上究竟是否更低？是否有

“沉默成本”

。

另外，從裝箱的角度，如果瓶子裡裝的都是沙子，那麼packing density肯定是很高的。但是，如果瓶子非常小，相當於裝進去的都是大石塊，packing density很難做的很高。同理，64GB RAM的機器比較小，如果每個機器都流出來幾GB的冗餘空間，海量小機器的資源碎片其實是很多的。但是如果是640GB的RAM，每個機器都流出來幾GB的冗餘空間，機器數少10倍，那麼資源碎片就會少很多。

Scalability

一個叢集管理系統管理上百萬臺機器是間比較有挑戰的事情。

Twine scales a single control plane to manage one million machines across all data centers in a geographic region and transparently move jobs across clusters。

Twine進行了比較徹底的sharding。各個使用者的Entitlements被shard到多個scheduler上，scheduler和allocator有1：1mapping。

Allocator透過1。 caching， 2。 將部分職責交個application-level scheduler，比如不負責短時間batch任務，3。 簡化初始分配策略，透過Rebalancer完成後期最佳化。實現較大的可擴充套件性。

Twine還特別跟Borg/K8S等基於Federation管理多個叢集的架構進行了對比。與Federation相比，Twine號稱可以透過簡單地實現支援更加複雜的multi-cloud， hybrid cloud操作。

Federation透過central機制去coordinate多個叢集的排程問題。但是Twine每個shard獨自可以完成，但是卻要面對concurrency control等問題，畢竟資源只有一份。

其他

說實話，和Borg的利用率比起來，Twine 40%的平均利用率似乎有點低，難道是統計口徑的問題？另外它也沒能體現出比定製化私有池子的優勢。

當然，文章中說他們當前叢集主要是online service。後續會定義好opportunitic resource的SLO，讓其他任務能夠利用一些online service off-peak resource，提高叢集利用率。

總體感覺Twine裡成熟還有一段距離。

Protean

Protean： VM Allocation Service at Scale，Microsoft， 2020

Protean和前面Borg， Twine不太一樣。Borg， Twine面向的是公司內部叢集容器化部署。而Protean面向公有云叢集的VM分配。

異構叢集

需求是非常多樣性的，有各種不同的裝置。這點和Facebook Twine有明顯的區別。這可能也因為Facebook內部業務場景多樣性相對少一些。

Rule-Based Allocation

可能人們會覺得以微軟的技術水平和Azure的業務規模，Protean應該是使用了非常高階的分配策略等等，達到了驚人的分配能力和碎片控制。然而，文章描述的卻是一種非常straght forward的基於規則的機制。

效能：VM的Allocation速度達到了20ms。如果回顧Borg，很多時候需要幾秒的時間（需要映象打包等等），VM的分配速度是非常快的。

可配置和理解：簡單地規則可以進行比較精確的除錯，同時也非常容易理解策略的結果，並基於此進行除錯。

可以比較清晰的看到，Rule-based allocation有幾個階段。

Cluster-level rule。即使用哪個叢集的機器。

Validator rule進行嚴格過濾

Preference rule進行軟規則計算。

Machine-level rule。也就是使用上一步被選出來的叢集的哪些機器。

同樣是先Validator rule，然後Preference rule。

Preference rule會進行對比打分，基於配置的權重進行調權，並且對分數quantization減少區分粒度。

架構和實現

Allocation Agent： AA是有多個replica的，從佇列裡面獲取VM請求，在高峰期AA的replica增加，進而擴容，低峰期則縮容。AA會基於一份Cache的叢集狀態進行分配，進而極大的提高效能。

Conflict Detector：由於資源池是共享資源，而AA replica又彼此獨立基於cache進行決策，必然會導致conflict和錯誤的分配。Conflict Detector能檢測到這些情況。進而觸發重試或者失敗。

Pubsub： Pubsub會把共享資源的狀態變更非同步的同步給各個AA，防止Cache過於Stale。

文章花了大量的篇幅描述Cache機制。其實也並不複雜。Cache分為多層，比如底層的原子資源狀態cache，（比如cpu cores， memory分別還剩下多少），上層是組合資源的狀態，比如（10 cores + 1GB RAM的需求哪些分配能滿足）。

當然，cache有效性的前提是Azure發現VM Alcoation Requests在一段時間內有非常高頻的重複性。可以看到下圖，cache的命中率的確是非常高的。

評估

Packing Density（PD） 評價了平臺資源分配的效率，過多碎片顯然不利於平臺在成本上的競爭力。當然，如果使用了過於複雜的策略，降低了分配的速度，或者沒有考慮容災問題，也會導致使用者的不滿。

Mesos， YARN， etc

Mesos

Mesos： A Platform for Fine-Grained Resource Sharing in the Data Center，2011

Mesos算是曾經火過的叢集管理系統。它切中了當時場景下存在許多排程Framework的痛點，另外精簡的實現也非常利於理解和擴充套件（魔改）。

在當時，有許多專門為某種計算定製的叢集管理工具（Framework），比如Hadoop， Dryad等等。他們有一定的叢集管理能力，但是無法和其他workflow共享叢集資源。Mesos想的問題是如何複用這些Framework的能力，同時讓他們在一個叢集上共享資源。

因此，為了與Borg， K8S這些相比，Mesos最大的特點就是我大部分都不管，交給上層的Framework。

Framework問Mesos要資源，Mesos提供可行的資源offer，Framework可以挑選合適的。

Framework基於挑選的資源，排程jobs，並管理他們的生命週期。Mesos不參與這些過程。

Mesos的設計會有一些limiations：

分散式的scheduler會更容易導致碎片。比如如何協調這些自治的Framework scheduler，達到更優的bin packing。在極端情況下，碎片的資源會不斷被分配給小的碎片任務，永遠不會有足夠大塊的資源片被分配給大的任務。導致叢集一直處於小碎片狀態。而所有任務的全域性scheduler這可以規劃碎片任務，留出足夠大的空閒機器給打的任務。

Framework間的任務如果有協同需求（比如隔離或者親和性），Mesos master很難去協同這些自治的framework。

Framework需要自己實現一定程度的排程策略，對於部分小Framework，這是額外的開發成本。

YARN

YARN是典型在開源社群的炮火中成長的系統，它從實踐中總結了10條需求，並基於此設計和實現了YARN：

Scalability

。 很好理解，那是個資料快速爆炸的時候，想要執行更大規模和更多的任務自然需要更強大的叢集管理能力。

Multi-tenancy

。 很多資料被放在共享的HDFS集群裡。不同團隊的人在上面執行任務，自然衍生了多租戶需求。

Serviceability

。 這個更多指的是平臺升級時能能夠平滑，保障使用者的正常使用。

Locality awareness

。 在更大叢集，更多工執行時，如何儘量的讓計算離資料更近。

High Cluster Utilization

。 提高叢集利用率，最佳化成本是永恆的話題。

Reliability/Availability

。 叢集需要保障穩定性和高可用性。

Secure and auditable operation

。 資料來自多個團隊，對於需要一定的安全和審計能力。

Support for Programming Model Diversity

。 機器學習，圖計算的需求顯然不是簡單地mapreduce可以滿足的，平臺需要支援靈活的程式設計和計算模型，滿足多樣性的需求。

Flexible Resource Model

。 固定資源種類、使用順序等不利於叢集排程的靈活性。

Backward compatibility

。 考慮Hadoop積累的龐大生態，YARN的設計必然要考慮這些老使用者的使用習慣，防止新系統的斷檔。

看完YARN的架構，感覺幾乎就是換了名字的Mesos，除了一些細節的區別：

ResourceManager負責管理叢集資源，分配資源需求，進行認證鑑權等工作。NodeManager被部署在各個節點上，管理本地的狀態，並和ResourceManager進行心跳同步。

ApplicationManager則負責不同框架任務的生命週期，包括向ResourceManager申請資源，拉起節點上的容器，控制任務執行的宣告週期。

這麼看ResourceManager類似Mesos Master，而ApplicationManager則類似Mesos Framework。NodeManager類似Mesos的slave。區別的話，Mesos Framework有更大的自主權和排程空間，而AM則更受限於RM的資源分配。

一些比較有意思的細節：

RM能找AM要回一點資源。其實就是換句話說能支援搶佔，不過給了AM一些選擇被搶佔容器，或者任務graceful退出的空間。

如果RM獲得了新的節點資源，會通知到AM。

AM和RM的溝通是心跳式的，AM就像一個mini的scheduler和allocator一樣根據自己當前pending的任務（各種需求，包括locacility等）去向RM獲取資源，或者退回資源給RM。而AM瞭解自己需要執行的任務，因此能具備一定彈性的排程這些任務。

RM基本上完全不管任務的生命週期，容器掛了之類的訊息會通知給對應的AM，然後AM會決定後續操作。

Kubernetes

Omega

說K8S之前還要在說一下Omega。Omega在老的Borg上進行了改進，其中一些思想影響了K8S的設計。

Omega： flexible， scalable schedulers for large compute clusters，2013

Omega首先透過資料分析，匯出了多Scheduler一部分動機。

Batch Job： 量大，但是時間短，佔總體資源相對少。如果不是非常高質量的快速排程，問題不大。

Service Job：相對量少，但是持續時間長，佔總體成本較多。因此在排程時花相對長的時間找到一個高質量的方案是值得的。

然後對幾種常見的scheduling架構進行了對比分析。其中引用了我們上文討論過得幾個方案：

Monolithic

，歷史上Borg就是這種結構。透過一個scheduler（可能包含多執行緒，sharding， 多路徑等最佳化）完成全域性排程任務。值得一提的是YARN，雖然拆開了RM和AM，看似屬於two-level架構。然而由於AM只負責任務生命週期管理，所有排程請求都提交給RM，所以其實是Monolithic的。Monolithic架構隨著規模和策略的增加，scalability和software complexity都會有很大挑戰。

Statically partitioned，靜態的將叢集資源分配給不同（e。g。 Hadoop）的任務很顯然，會導致嚴重的資源利用率和碎片問題。

Two-level，透過一個centralized coordinator將可用資源供各個上層framework選取（二次排程），比如Mesos。由於offer選擇問題，通常coordinator無法併發的分配資源，所以是pessimistic的。另外一個問題是framework只能拿到available offer，因此無法看到全域性資源，因而難以實現諸如搶佔等策略。為了實現gang-scheduling，Mesos會囤積資源導致資源利用率問題，而其他framework無法將短期任務在被囤積的資源上面執行。

Share-state。如Omega，叢集同時存在多個Scheduler在併發的進行排程，每個Scheduler可能是同構或者異構的，它們都能看到全域性的資源，透過opptimistic concurrency control進行衝突處理。透過這種方式，上面提到的諸如無法併發，複雜度，無法跨Framework搶佔，無法利用gang-scheduling的短期閒置資源問題，都能得到一定程度解決。當然，這個方案有潛在發生排程衝突的可能性。後面實驗分析真實場景問題不大。

”About 20% of jobs in Google are MapReduce ones， and many of them are run repeatedly， so historical data is available to build models。“ ——2013

Omega的不同Scheduler可以是異構的。為此Omega專門定製了一個MapReduce Scheduler和其他Scheduler並行執行，實現了基於全域性資源的MapReduce自動配置。

K8S

Omega的一些思想影響了後續Borg的演進，以及K8S的部分設計。K8S繼承了Borg和Omega的一些特性，但是又與Borg， Omega等系統不同，舉幾個例子。

K8S的設計是面向開源的，因此有更嚴格的API設計，統一的API服務隔離內外，一致的API資源抽象。

IP Per Pod。網路身份和應用身份得到了一對一的對應。

基於Label的Pod標記，而不僅僅是簡單地ID序列。

這有一段非常耐人尋味的話，歸根結底叢集管理系統是帶有領域知識的分散式系統，還是離不開分散式系統那些分分合合的問題。而分散式系統終究是軟體，還是離不開復雜度的問題。：

“The design of Kubernetes as a combination of microservices and small control loops is an example of control through

choreography

—achieving a desired emergent behavior by combining the effects of separate， autonomous entities that collaborate。 This is a conscious design choice in contrast to a centralized

orchestration

system

， which may be easier to construct at first but tends to become brittle and rigid over time， especially in the presence of unanticipated errors or state changes。”

這讓人想到了交響樂隊，想到蟻群，想到公司組織架構。。。

總結

叢集管理系統就像是公司業務的作業系統，業務是上層應用，而業務邏輯的運轉深深的依賴叢集管理系統的高效執行。叢集管理系統在滿足QoS的基礎上，充分利用底層龐大的物理資源。

從早期的物理機部署、靜態隔離，到Monolithic、Two-level、Share-state，排程架構過去20年有多輪升級迭代。從物理硬體，系統核心，節點agent和全域性排程多個層面，叢集管理系統能越來越好的將異構任務在共享資源上混合部署，利用潮汐、錯峰，超配，頭部效應等規律挖掘叢集的資源利用率，降本提效。

隨著技術逐漸走向成熟，更多科技公司有了勇氣將叢集管理系統進行整合統一。在更大的資源池和調度搜索空間下，取得了更高的資源利用率，更大的彈性空間。然而，現實情況下混合雲依然不可避免的會長期存在。Kubernetes的開源進一步推進了技術被更快速，更廣泛的使用。