流式计算系统-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来实现恢复重放。

【编辑推荐】