题目：复杂事件处理引擎的可用性保障技术研究

近年来，事件驱动架构被广泛应用于分布式系统构建。随着系统规模不断增大，交互关系日趋复杂，大量持续事件流需要得到有效的处理。复杂事件处理通过分析持续实时事件流，提取符合特定模式的事件序列，能够满足应用在实时性、关联关系分析等方支持效率低下面的要求。但是，现有的引擎仍存在某些不足，如针对于某些语义的支持效率低下、要求事件有序进入引擎等。这些都对复杂事件处理引擎的可用性提出了挑战。本文主要针对于复杂事件处理引擎在事件关联关系支持、高吞吐率环境和乱序场景下的可用性问题进行研究，从这三个方面提出了一套完整的解决方案。 为提供丰富的事件关联关系支持，本文设计了一种基于树的模式匹配方法PMTree（Pattern Matching Tree），能够很好地检测不同类型时序关系，可以很容易地进行语义的扩展。PMTree定义了事件模型及不同时序约束关系下的事件算子，将事件序列映射为树节点，这些树节点最终连接成为一棵PMTree。 针对于高吞吐率环境，本文在PMTree结构上进一步提出了优化策略。首先，给出流处理上的一些通用优化方法，如转发节点的谓词索引结构、模式优化等。其次，综合考虑事件流的不同特征，如不同类型事件比例、谓词约束条件满足概率等，对树节点上的事件处理耗费给出代价模型，并基于此提出最优化构建树的算法，以针对不同特征的事件流选择最高效的PMTree构建方式。 针对乱序问题，本文提出了一种基于插入特殊标记事件的方法，通过由数据源产生辅助的控序事件插入原始事件流，供节点判定缓存中无效的事件实例。基于此标记事件，给出节点上的安全缓存管理机制，防止有效事件实例的过早删除，这样，就可以避免生成错误结果或丢失正确结果。 基于上述解决方案，我们实现了复杂事件处理引擎原型系统Cesar。实验证明，该引擎实时数据处理效率较高，同等条件下，吞吐率为开源的复杂事件处理引擎Esper的3~6倍，并且性能在各类时序约束关系及长度下都表现稳定。在乱序场景下，保证了结果的正确性，同时也具有较低的处理延迟。实验验证了应用本文提出的解决方案的复杂事件处理引擎较高的可用性，能够很好地支持各种事件关联关系，并且具有高的吞吐率，同时针对乱序场景兼顾了结果正确性及低处理时延。