一种考虑实时约束的数据流卸载技术

Novel Load Shedding Approach for Real-time Data Stream Processing

在数据流管理系统中,流数据的高到达速率和迸发性等特点会引起系统过载,为此人们提出了各种卸载技术来缓解过载问题.目前几乎所有的卸载技术都使用随机丢弃数据的方法,由于随机丢弃数据策略对数据丢弃过程没有任何控制,这对某些考虑实时约束的数据流管理系统是不适合的.本文认为更为精确的卸载模型,比如文中使用的(m,k)截止期模型,更适合于一类重要的实时数据流事件检测应用.基于(m,k)截止期模型,提出一种新的策略SOSA,该策略一方面提供了可证明的卸载能力,同时也保证了系统的时间约束.为验证SOSA的有效性,设计了一种新的数据流调度算法SOSA-DBP.理论分析与模拟实验证明了SOSA-DBP比现有的算法有更好的性能.

Data stream processing is essential for many real-life stream-based applications. Systems designed to run such applications must be prepared to operate under overloaded conditions. Existing load shedding techniques are not suitable for processing a kind of real-time data stream applications because their tuple dropping policies may violate application deadlines in an uncontrolled way. We＇ d argue that a more precise load shedding model, e.g. , the （m,k） deadline model adopted in this paper, is much appropriate than the commonly used random dropping policy. Based on this novel load shedding model, we propose a Safe load Shedding Approach （ SOSA ） that aims to reduce the workload imposed on the system while at the same time preserving system timing constraints by ex- ploiting data stream semantics. SOSA categorizes stream processing into two different modes and allows one to place provably lighter loads on streams that operate in one particular mode. To demonstrate the usefulness of SOSA, we introduce a concrete （ m, k ） scheduling algorithm called SOSA-DBP by combining SOSA with DBP, a well-known （m,k） scheduling algorithm. Probabilistic analysis and experimental results show that SOSA-DBP has significant performance gain over DBP.