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