大规模事件数据处理的覆盖检测优化算法

Optimized Covering Detection Algorithm for Big Event Data Processing

内容发布?订阅系统是一种在时间、空间和控制流上完全解耦的分布式事件系统,能够依赖消息的内容来进行事件匹配和路由,支持大规模事件数据的高效处理和分发.在基于内容的路由中,覆盖优化是一种典型的路由优化算法,它有效地避免网络中冗余的订阅,减少路由表存储、网络通信和事件匹配开销.然而,即使对于中等大小的负载,其中核心的覆盖关系检测算法都可能非常耗时并对优化后系统的效率产生负面影响.针对大数据环境下大规模订阅带来的对检测效率的挑战,提出了一种新的、基于匹配树的高效覆盖关系检测算法.实验显示,提出的方法显著地提高了订阅关系检测和维护的效率.

Content based publish subscribe system is a time,space and control flow decoupled distributed event based system,which enables event matching and routing based on the content of messages,and thus supports efficient processing and dissemination of big event data.Content subscription covering is a popular optimization that has been successfully employed in many distributed content-based publish?subscribe systems.It can avoid redundant subscriptions,decrease routing table sizes,reduce message traffic and event matching cost.However,in even moderately large workloads,the cost of computing the covering relationships can be extremely costly and potentially negate any of the above benefits.To cope with the challenge of huge amount of subscriptions in big data environment to the efficiency of covering relationship detection,a new algorithm is proposed which uses a new matching tree as an index data structure to efficiently detect covering relationships among subscriptions.Evaluation shows that our approach significantly improves the cost of detecting and maintaining covering relationships between subscriptions.