【經(jīng)典論文】Google Borg大規(guī)模集群管理(三、四章)
3. Borg架構(gòu)
一個Borg的Cell包括一堆機器，一個邏輯的中心控制服務(wù)叫做Borgmaster，和在每臺機器上跑的Borglet的agent進程(見圖1)。所有Borg的組件都是用C++寫的。
3.1 Borgmaster
Cell的Borgmaster由2個進程組成，主的Borgmaster進程和一個單獨的 scheduler($3.2)。主的Borgmaster處理所有客戶端的RPC請求，例如修改狀態(tài)(創(chuàng)建job)，提供數(shù)據(jù)讀取服務(wù)(查找job)。它同時管理系統(tǒng)中所有組件(機器、task、allocs等等)的狀態(tài)機，和Borglet通信，并且提供一個Sigma的備份Web UI。
Borgmaster在邏輯上是一個單進程，但實際上開了5個副本。每個副本維護了一個內(nèi)存級別的cell狀態(tài)拷貝，這些狀態(tài)同時被記錄在一個高可用、分布式、Paxos-based存儲[55]放在這些副本的本地硬盤上。在一個cell里面，一個單獨的被選舉出來的master同時用于 Paxos leader和狀態(tài)修改器，用來處理所有改變cell狀態(tài)的請求，例如提交一個job或者在一個機器上終止一個task。當(dāng)cell啟動或前一個 master掛了時，Paxos算法會選舉出一個master;這需要一個Chubby鎖然后其他系統(tǒng)可以找到master。選舉一個master或者換一個新的需要的典型事件是10s，但需要大概1分鐘才能讓一個大的cell內(nèi)生效，因為一些內(nèi)存狀態(tài)要重構(gòu)。當(dāng)一個副本從網(wǎng)絡(luò)隔離中恢復(fù)時，需要動態(tài)的從其他Paxos副本中重新同步自己的狀態(tài)。
某個時刻的Borgmaster的狀態(tài)被稱為checkpoint，會被以快照形式+change log形式保存在Paxos存儲里面。checkpoints有很多用途，包括把Borgmaster的狀態(tài)恢復(fù)到以前的任意時刻(例如在處理一個請求之前，用來解決軟件缺陷);極端情況下手動修改checkpoints，形成一個持續(xù)的事件日志供今后用;或用于線下的在線仿真。
一個高仿真的Borgmaster叫Fauxmaster，可以用來讀取checkpoint文件，包括一份完整的Borgmaster的代碼，和Borglet的存根接口。它接受RPC來改變狀態(tài)機和執(zhí)行操作，例如調(diào)度所有阻塞的tasks，我們用它來debug錯誤，和它交互就和 Borgmaster交互是一樣的，同樣我們也有一個仿真的Borglet可以用checkpoint重放真實的交互。用戶可以單步調(diào)試看到系統(tǒng)中的所有過去的改變。Fauxmaster在這種情況下也很有用：多個這個類型的job比較合適?以及在改變cell配置前做一個安全檢查(這個操作會把任何關(guān)鍵 jobs給踢掉嗎?)
3.2 調(diào)度 schedule
當(dāng)一個job被提交的時候，Borgmaster會把它持久化的存儲在Paxos存儲上，然后把這個 job的task放到等待(pending)的隊列里面去。這個隊列會被scheduler異步的掃描，然后分發(fā)task到有充足資源的機器上。 scheduler主要是處理task的，不是job。掃描從高優(yōu)先級到低優(yōu)先級，在同個優(yōu)先級上用round-robin的方式處理，以保證用戶之間的公平性和避免頭上的大job阻塞住。調(diào)度算法有2個部分：可行性檢查(feasibility checking)，找到一臺能跑task的機器，和打分(scoring)，找個一個最合適的機器。
在可行性檢查這個階段，scheduler會找到一組機器，都滿足task的約束而且有足夠可用的資源 —— 包括了一些已經(jīng)分配給低優(yōu)先級任務(wù)的可以被騰出來的資源。在打分階段，scheduler會找到其中“***”的機器。這個分?jǐn)?shù)包括了用戶的偏好，但主要是被內(nèi)置的標(biāo)準(zhǔn)：例如最小化的倒騰其他task，找到已經(jīng)有這個task安裝包的，在電力和出錯的可用域之間盡可能分散的，在單臺機器上混合高低優(yōu)先級的 task以保證高峰期擴容的。
Borg原來用E-PVM[4]的變種算法來打分，在異構(gòu)的資源上生成一個單一的分?jǐn)?shù)，在調(diào)度一個task時最小化系統(tǒng)的改變。但在實踐中，E- PVM***把負(fù)載平均分配到所有機器，把擴展空間留給高峰期 —— 但這么做的代價是增加了碎片，尤其是對于大的task需要大部分機器的時候;我們有時候給這種分配取綽號叫“最差匹配”。
分配策略光譜的另一端是“***匹配”，把機器塞任務(wù)塞的越緊越好。這樣就能留下一些空的機器給用戶jobs(他們也跑存儲服務(wù))，所以處理大 task就比較直接了，不過，緊分配會懲罰那些對自己所需資源預(yù)估不足的用戶。這種策略會傷害爆發(fā)負(fù)載的應(yīng)用，而且對需要低CPU的批處理任務(wù)特別不友好，這些任務(wù)可以被輕易調(diào)度到不用的資源上：20%的non-prod task需要小于0.1核的CPU。
我們目前的打分模型是一個混合的，試圖減少擱淺的資源 —— 一些因為這臺機器上資源沒被全部用掉而剩下的。比起“***匹配”，這個模型提供了3%-5%的打包效率提升(在[78]里面定義的)。
如果一臺機器在打分后沒有足夠的資源運行新的task，Borg會驅(qū)逐(preempts)低優(yōu)先級的任務(wù)，從***優(yōu)先級往上踢，直到資源夠用。我們把被踢掉的task放到scheduler的等待(pending)隊列里面去，而不是遷移或冬眠這些task。
task啟動延遲(從job提交到task運行之間的時間段)是被我們持續(xù)關(guān)注的。這個時間差別很大，一般來說是25s。包安裝耗費了這里面 80%的時間：一個已知的瓶頸就是對本地硬盤的爭搶。為了減少task啟動時間，scheduler希望機器上已經(jīng)有足夠的包(程序和數(shù)據(jù))：大部分包是只讀的所以可以被分享和緩存。這是唯一一種Borg scheduler支持的數(shù)據(jù)本地化方式。順便說一下，Borg分發(fā)包到機器的辦法是樹形的和BT類型的協(xié)議。
另外，scheduler用了某些技術(shù)來擴散到幾萬臺機器的cell里面。($3.4)
3.3 Borglet
Borglet是部署在cell的每臺機器上的本地Borg代理程序。它啟動停止task;如果task失敗就重啟;通過修改OS內(nèi)核設(shè)置來管理本地資源;滾動debug日志;把本機的狀態(tài)上報給Borgmaster和其他監(jiān)控系統(tǒng)。
Borgmaster每過幾秒就會輪詢所有的Borglet來獲取機器當(dāng)前的狀態(tài)還有發(fā)送任何請求。這讓Borgmaster能控制交流頻率，避免一個顯式的流控機制，而且防止了恢復(fù)風(fēng)暴[9].
選舉出來的master負(fù)責(zé)發(fā)送消息給Borglet并且根據(jù)響應(yīng)更新cell的狀態(tài)。為了性能可擴展，每個Borgmaster副本會運行一個無狀態(tài)的連接分配(link shard)來處理和特定幾個Borglet的交流;這個分配會在Borgmaster選舉的時候重新計算。為了保證彈性，Borglet把所有狀態(tài)都報上來，但是link shard會聚合和壓縮這些信息到狀態(tài)機，來減少選舉出來的master的負(fù)載。
如果Borglet幾次沒有響應(yīng)輪詢請求，將會被標(biāo)記為掛了(down)，然后上面跑的task會被重新分配到其他機器。如果通訊恢復(fù)，Borgmaster會讓這個Borglet殺掉已經(jīng)被分配出去的task，來避免重復(fù)。Borglet會繼續(xù)常規(guī)的操作即使和Borgmaster 恢復(fù)聯(lián)系，所以目前跑的task和service保持運行以防所有的Borgmaster掛了。
3.4 可擴展性
我們還不知道Borg的可擴展性極限在哪里，每次我們碰到一個極限，我們就越過去。一個單獨的Borgmaster可以管理一個cell里面幾千臺機器，若干個cell可以處理10000個任務(wù)每分鐘。一個繁忙的Borgmaster使用10-14個CPU核以及 50GB內(nèi)存。我們用了幾項技術(shù)來獲得這種擴展性。
早期的Borgmaster有一個簡單的，同步的循環(huán)來處理請求、調(diào)度tasks，和Borglet通信。為了處理大的cell，我們把 scheduler分出來作為一個單獨的進程，然后就可以和別的Borgmaster功能并行的跑，別的Borgmaster可以開副本來容錯。一個 scheduler副本操作一份cell的狀態(tài)拷貝。它重復(fù)地：從選舉出來的master獲取狀態(tài)改變(包括所有的分配的和pending的工作);更新自己的本地拷貝，做調(diào)度工作來分配task;告訴選舉出來的master這些分配。master會接受這些信息然后應(yīng)用之，除非這些信息不適合(例如，過時了)，這些會在scheduler的下一個循環(huán)里面處理。這一切都符合Omega[69]的樂觀并行策略精神，而且我們最近真的給Borg添加這種功能，對不同的工作負(fù)載用不同的scheduler來調(diào)度。
為了改進響應(yīng)時間，我們增加了一些獨立線程和Borglet通信、響應(yīng)只讀RPC。為了更高的性能，我們分享(分區(qū))這些請求給5個Borgmaster副本$3.3。***，這讓99%的UI響應(yīng)在1s以內(nèi)，而95%的Borglet輪詢在10s以內(nèi)。
一些讓Borg scheduler更加可擴展的東西：
分?jǐn)?shù)緩存：評估一臺機器的可用性和分?jǐn)?shù)是比較昂貴的，所以Borg會一直緩存分?jǐn)?shù)直到這個機器或者task變化了——例如，這臺機器上的task結(jié)束了，一些屬性修改了，或者task的需求改變了。忽略小的資源變化讓緩存保質(zhì)期變長。
同級別均化處理：同一個Borg job的task一般來說有相同的需求和資源，所以不用一個個等待的task每次都去找可用機器，這會把所有可用的機器打n次分。Borg會對相同級別的task找一遍可用機器打一次分。
適度隨機：把一個大的Cell里面的所有機器都去衡量一遍可用性和打分是比較浪費的。所以scheduler會隨機的檢查機器，找到足夠多的可用機器去打分，然后挑出***的一個。這會減少task進入和離開系統(tǒng)時的打分次數(shù)和緩存失效。適度隨機有點像Sparrow [65]的批處理采樣技術(shù)，同樣要面對優(yōu)先級、驅(qū)逐、非同構(gòu)系統(tǒng)和包安裝的耗費。
在我們的實驗中($5)，調(diào)度整個cell的工作負(fù)載要花幾百秒，但不用上面幾項技術(shù)的話會花3天以上的時間。一般來說，一個在線的調(diào)度從等待隊列里面花半秒就能搞定。
#p#
4. 可用性
在大型分布式系統(tǒng)里面故障是很常見的[10,11,12]。圖3展示了在15個cell里面task驅(qū)逐的原因。在Borg上跑的應(yīng)用需要能處理這種事件，應(yīng)用要支持開副本、存儲數(shù)據(jù)到分布式存儲這些技術(shù)，并能定期的做快照。即使這樣，我們也盡可能的緩和這些事件造成的影響。例如，Borg：
- 自動的重新調(diào)度被驅(qū)逐的task，如果需要放到新機器上運行
- 通過把一個job分散到不同的可用域里面去，例如機器、機架、供電域
- 在機器、OS升級這些維護性工作時，降低在同一時刻的一個job中的task的關(guān)閉率
- 使用聲明式的目標(biāo)狀態(tài)表示和冪等的狀態(tài)改變做操作，這樣故障的客戶端可以無損的重新啟動或安全的遺忘請求
- 對于失聯(lián)的機器上的task，限制一定的比率去重新調(diào)度，因為很難去區(qū)分大規(guī)模的機器故障和網(wǎng)絡(luò)分區(qū)
- 避免特定的會造成崩潰的task:機器的匹配
critical級別的中間數(shù)據(jù)寫到本地硬盤的日志保存task很重要，就算這個task所屬的alloc被終止或調(diào)度到其他機器上，也要恢復(fù)出來做。用戶可以設(shè)置系統(tǒng)保持重復(fù)嘗試多久：若干天是比較合理的做法。
一個關(guān)鍵的Borg設(shè)計特性是：就算Borgmaster或者Borglet掛了，task也會繼續(xù)運行下去。不過，保持master運行也很重要，因為在它掛的時候新的jobs不能提交，或者結(jié)束的無法更新狀態(tài)，故障的機器上的task也不能重新調(diào)度。
Borgmaster使用組合的技術(shù)在實踐中保證99.99%的可用性：副本技術(shù)應(yīng)對機器故障;管理控制應(yīng)對超載;部署實例時用簡單、底層的工具去減少外部依賴(譯者：我猜測是rsync或者scp這種工具)。每個cell和其他cell都是獨立的，這樣減少了誤操作關(guān)聯(lián)和故障傳染。為了達(dá)到這個目的，所以我們不搞大cell。
