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