● 摘要
随着大数据时代的来临，应用消费的数据越来越呈现出超大规模、连续到达且没有边界、时效性以及网络分布等特点。传统的数据库管理和数据仓库技术，甚至以Hadoop为代表的批处理技术都不足以适应这种数据处理的需求。近年来出现的分布式流处理技术，为解决这类问题提供了一个很好的途径。分布式流处理技术是在早期数据流管理技术的基础上进一步发展而来，它将对数据流的处理分布到网络环境中进行，利用分散的资源来提升数据处理的性能和可靠性。由于分布式流处理在改善性能瓶颈和可靠性方面的优势，使得它非常适用于互联网、金融、军事等领域的众多应用。这方面的研究正受到研究工作者的密切关注。应用的服务质量保障是分布式流处理技术研究一个基本的关键问题。然而在分布式环境下，资源的动态变化对这一问题的解决提出了挑战。数据流处理的特点使得应用的服务质量水平需要与所获得的资源能力相匹配。当应用运行过程中所获得的资源不能够满足处理负载的需求时，数据流处理的能力会下降，从而影响应用最终的服务质量。更甚的是，应用依赖的资源节点发生故障将导致整个应用无法正常运行。由于资源的动态变化往往具有随机性，使得在动态资源环境下保证应用的服务质量成为分布式流处理技术研究的一个难点，在实际应用中也具有非常重要的意义。本文针对动态资源环境给服务质量保障带来的挑战，以满足应用的端到端延迟和吞吐量约束，最大化应用的可用性，以及最小化应用的数据传输丢失率为目标展开深入的研究，取得的主要研究成果及创新如下：1. 针对在算子布局过程中需要考虑满足服务质量约束、负载均衡以及解决多个应用间服务质量冲突的需求，提出了服务质量感知的算子布局方法。首先设计了一种基于节点优化潜力的算子布局算法，以启发式的策略解决单个应用的算子布局问题。提出了节点优化潜力的概念，用以描述算子所在的资源节点对于最终满足服务质量约束以及对减小网络使用负载的潜在贡献能力。通过为算子选择具有高优化潜力的节点，能够提高单个应用算子布局的成功率以及减小网络使用负载。然后，以单个应用的算子布局算法为基础，设计了基于博弈的并发算子布局算法。通过将应用间的资源竞争看成是市场竞争中的博弈过程，并对应用的布局策略组合进行调整以达到纳什均衡，实现应用间服务质量冲突的最小化。实验结果和分析表明，相较已有的算子布局算法，本文提出的算法在减小网络使用负载、增加布局成功率以及减小算子迁移次数上都具有一定的优势。2. 针对在动态资源环境中，由于节点故障或者组件异常易导致应用不可用的问题，提出了以最大化应用的可用性为目标的副本布局与异常预测方法。在副本布局方法的研究中，通过分析，确定最大化应用可用性的副本布局原则：尽量将属于同一个算子的副本分布到不同的宿主节点上，而将属于不同算子的副本分布到相同的宿主节点之上。并基于此原则设计了分布式的副本布局算法：首先为算子的每个副本计算最大宿主集合，使得集合中的节点所能够容纳的不同算子的副本个数之和最多，然后通过迭代的方式，依次为每一个算子副本从对应的宿主节点集合中按照之前确立的副本布局原则选取最终的节点，从而最大化应用的可用性。在异常预测方法的研究中，通过分析异常发生之前对组件特征指标取值的影响，提出了在线的组件异常预测技术。预测过程中利用隐马尔可夫模型来捕捉特征值的变化规律，然后利用混合专家模型调整最终预测值的大小，以最小化预测误差；在获得预测值的基础上，采用支持向量机对特征值在未来时间内的变化进行分类和识别。通过异常的预测，能够在故障发生之前就及早地采取补救措施，从而最大程度地提高应用可用性。理论分析和实验结果表明，与同类型的副本布局算法相比，基于副本最大宿主集合的副本布局算法能够提高应用可用性和资源利用率；所提出的异常预测技术对于常见的异常具有高预测精度和低时间开销。3. 针对算子间的数据流传输缺乏足够的灵活性和可靠性的问题，提出了支持点到点通信的覆盖网络技术。首先，设计了一个基于点对点的成员管理机制，系统中的每个节点成员可以独立与随机的部分节点(随机局部视图)交换信息，从而使得每个节点都能够及时地发现系统中资源的动态变化情况，包括节点加入/退出、节点间网络状态波动以及节点的可用资源量改变。然后，设计了面向发布订阅通信模式的覆盖网络：通过所提出的成员管理机制，有效地维护代理节点之间网络拓扑结构，使其接近K正则随机图，从而获得在消息通信方面良好的容错性；通过采用哈希和布鲁姆过滤器对事件和订阅条件进行索引，加速事件匹配；采用基于会合点的事件路由避免广播带来的带宽消耗过大的问题，同时具有比广播更高的传输可靠性。理论分析和实验结果表明，基于点对点的成员管理具有很高的成员发现效率和可伸缩性；而面向发布订阅的覆盖网络能够维持稳定的网络拓扑结构，发布订阅匹配具有很小的误报率，基于会合点的路由相对于广播方式来说，具有更小的带宽消耗以及更低的数据传输丢失率。