流式計(jì)算系統(tǒng)-Borealis
Borealis是Brandeis University、Brown University和MIT合作開發(fā)的一個(gè)分布式流式系統(tǒng)，由之前的流式系統(tǒng)Aurora、Medusa演化而來(lái)。目前Borealis系統(tǒng)已經(jīng)停止維護(hù)，***的Release版本停止在2008年。
Borealis具有豐富的論文、完整的用戶/開發(fā)者文檔，系統(tǒng)是C++實(shí)現(xiàn)的，運(yùn)行于x86-based Linux平臺(tái)。系統(tǒng)是開源的，同時(shí)使用了較多的第三方開源組件，包括用于查詢語(yǔ)言翻譯的ANTLR、C++的網(wǎng)絡(luò)編程框架庫(kù)NMSTL等。
Borealis系統(tǒng)的流式模型和其他流式系統(tǒng)基本一致：接受多元的數(shù)據(jù)流和輸出，為了容錯(cuò)，采用確定性計(jì)算，對(duì)于容錯(cuò)性要求高的系統(tǒng)，會(huì)對(duì)輸入流使用算子進(jìn)行定序。
Borealis的系統(tǒng)架構(gòu)如圖4所示。
- Query Processor(QP)是計(jì)算執(zhí)行的地方，是系統(tǒng)的核心部件，其大部分功能繼承自Aurora。
- I/O Queues將數(shù)據(jù)流導(dǎo)入QP，路由Tuples到其他節(jié)點(diǎn)或客戶端程序。
- Admin模塊用來(lái)控制本地的QP，例如建立查詢、遷移數(shù)據(jù)流圖片段，該模塊也會(huì)同Local Optimizer協(xié)作優(yōu)化現(xiàn)有數(shù)據(jù)流圖。
- Local Optimizer職責(zé)包括本地調(diào)度策略、調(diào)整Operator行為、超載后丟棄低價(jià)值元組等。
- Storage Manager模塊用于存儲(chǔ)本地計(jì)算的狀態(tài)數(shù)據(jù)。
- Local Catalog存儲(chǔ)本地?cái)?shù)據(jù)流圖和元數(shù)據(jù)，可以被本地所有組件訪問(wèn)。
- Borealis Node還有彼此通信的模塊用于執(zhí)行協(xié)作任務(wù)。
- Neighborhood Optimizer使用本地和鄰居節(jié)點(diǎn)來(lái)優(yōu)化節(jié)點(diǎn)間的負(fù)載均衡或shed load。
- High Availability (HA)模塊相互監(jiān)測(cè)，發(fā)現(xiàn)對(duì)方故障時(shí)及時(shí)代替對(duì)方。
- Local Monitor收集本地性能相關(guān)統(tǒng)計(jì)數(shù)字報(bào)告給本地和Neighborhood Optimizer。
- Global Catalog為整個(gè)數(shù)據(jù)流計(jì)算提供了一個(gè)邏輯上的完整視圖。
除作為基本功能節(jié)點(diǎn)外，Borealis Server也可以被設(shè)計(jì)成一個(gè)協(xié)作節(jié)點(diǎn)來(lái)執(zhí)行全局的系統(tǒng)監(jiān)控和其他優(yōu)化任務(wù)，比如全局的負(fù)載分布和Global Load Shedding，因此Borealis實(shí)際上提供了完整的3級(jí)監(jiān)控和優(yōu)化（Local、Neighborhood、Global）。
負(fù)載均衡方面，Borealis提供了動(dòng)態(tài)和靜態(tài)兩種部署機(jī)制。
- Correlation-based Operator Distribution
通過(guò)分析不同Operators和Nodes間的負(fù)載變化的關(guān)系，決定和動(dòng)態(tài)調(diào)整Operatpr的部署，使之達(dá)到負(fù)載均衡。
- Resilient Operator Distribution Algorithm
該算法的目標(biāo)是提供一種靜態(tài)的Operator部署方案，該方案能夠在不需要重新調(diào)整的情況下處理***可能的輸入速度變化范圍。
由于動(dòng)態(tài)調(diào)整需要時(shí)間和消耗，前者適用于負(fù)載變化持續(xù)時(shí)間較長(zhǎng)的系統(tǒng);而后者則能處理較快較短的負(fù)載峰值。在實(shí)現(xiàn)上前者使用相關(guān)系數(shù)作為節(jié)點(diǎn)關(guān)聯(lián)度指標(biāo)，并通過(guò)貪婪算法將NP問(wèn)題轉(zhuǎn)化為多項(xiàng)式求解;而后者在部署前計(jì)算完畢，保證系統(tǒng)能夠容忍負(fù)載峰值。該算法在線性代數(shù)上建模，包括Operator Ordering、Operator Assignment兩個(gè)階段。
Borealis通過(guò)四種容錯(cuò)機(jī)制來(lái)滿足用戶需求。
- Amnesia Backup
備機(jī)發(fā)現(xiàn)主機(jī)故障，立即從一個(gè)空的狀態(tài)開始重做。
- Passive Standby
主機(jī)處理，備機(jī)待命，主機(jī)按周期做Checkpoint，主機(jī)故障后切換到備機(jī)，重放Checkpoint和數(shù)據(jù)流，對(duì)于不確定性計(jì)算可以很好地支持，缺點(diǎn)是恢復(fù)時(shí)間較長(zhǎng)。
- Active Standby
主備機(jī)同時(shí)計(jì)算，主機(jī)故障時(shí)直接切換到備機(jī)，不支持不確定性計(jì)算，浪費(fèi)計(jì)算資源，不過(guò)恢復(fù)時(shí)間幾乎沒(méi)有。
- Upstream Backup
通過(guò)上游備份來(lái)容錯(cuò)，故障時(shí)從上游重放數(shù)據(jù)即可，恢復(fù)時(shí)間最長(zhǎng)，不過(guò)最節(jié)省資源。
除此之外，Borealis還提供了更高級(jí)的容錯(cuò)機(jī)制Rollback Recovery，它是一種基于副本在節(jié)點(diǎn)失效、網(wǎng)絡(luò)失效或網(wǎng)絡(luò)分區(qū)時(shí)的故障恢復(fù)機(jī)制，在盡量減少系統(tǒng)不一致的情況下，盡可能地保證系統(tǒng)的可用性。該機(jī)制允許用戶定義一個(gè)閾值來(lái)在一致性和可用性之間做一個(gè)平衡。當(dāng)系統(tǒng)數(shù)據(jù)恢復(fù)后，系統(tǒng)支持重新計(jì)算輸出正確的結(jié)果，保證最終一致性。該機(jī)制使用了Data- serializing Operator(SUnion)來(lái)確保所有的副本處理同樣順序的數(shù)據(jù)。當(dāng)失效恢復(fù)后，通過(guò)Checkpoint/Redo、Undo/Redo來(lái)實(shí)現(xiàn)恢復(fù)重放。
【編輯推薦】
