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