论文部分内容阅读
随着信息处理技术在通信、金融、工业生产等领域的广泛应用,数据已经不仅仅拘泥于文件、数据表等传统形式。大量连续、变化的流式数据在越来越多的现代应用中出现,例如军事指挥、交通控制、传感器数据处理、网络监控、金融数据分析等。在这些应用中,数据以流的形式不断到达,系统需要对这些数据进行连续、及时的处理。如果处理时间超过了查询截止期要求,查询结果就没有意义,甚至会造成灾难性后果。目前大多数研究集中于连续查询的处理与调度,对于以满足截止期为目标的实时查询处理与调度的研究比较少,因此本文主要讨论数据流管理系统中实时查询处理与调度问题。
本文首先系统地分析了数据流系统的应用需求、特点和研究现状,在此基础上提出了一种由周期性查询、非周期性查询(包括连续性查询和一次性查询)构成的混合实时查询模型,并对三种查询的定义和属性进行了形式化描述。为了方便查询的定义与表示,本文设计了一种类soL的实时连续查询语言RT-coL(Real:Time Continuous Query Language)。与已有查询语言相比,RT-coL增加了对周期、截止期、采样率等实时性和近似性特征的描述。
其次,本文结合实时查询的特点,讨论了选择、投影、聚集、连接等基本操作符的设计与实现。针对多查询共享问题,本文提出了一种带共享段的操作符网络构造算法。该算法可以根据多个查询计划构造包含公共操作符路径段的操作符网络,消除重复的操作符,提高查询处理效率。
接着,本文针对共享滑动窗口连接问题提出一种相对截止期优先连接算法RDF-SJoin(Relative Deadline First Shared window Join)和一种绝对截止期优先连接算法EDF-SJoin(Earliest Deadline First Shared window Join)。RDF-SJoin算法优先进行相对截止期较短的窗口上的连接操作。EDF-SJoin算法按照元组的绝对截止期从早到晚的顺序进行连接操作。仿真测试结果表明,这两种算法都能减少查询的截止期错失率。与RDF-SJoin算法相比,EDF-SJoin算法能更公平的执行共享连接操作,避免查询执行中的“饿死问题”。
再次,本文针对多查询的实时调度问题提出一种以操作符路径为单位的最早截止期优先调度算法OP-EDF(Operator-Path Earliest Deadline First),并从调度能力、响应时间、系统开销等方面对算法性能进行了分析。然后,针对流速爆发情况下OP-EDF算法系统开销较大的问题,提出两种改进的内部调度算法~OP-EDF-Batch和OP-EDF-Gate,实现了高效的元组批处理调度。实验结果表明两种改进的算法可以有效地应用于流速爆发环境中的数据流实时查询处理。
进一步,本文把反馈控制思想应用到混合查询调度中,提出了一种基于反馈控制的混合查询调度算法FC-TBS(Feedback-Control-based Total BandwidthServer)。该算法根据周期性查询和非周期性查询的负载情况和截止期错失率,动态分配处理器时间。试验结果表明,与其它混合调度算法相比,FC-TBS算法在保证周期性查询截止期的情况下能够降低非周期性查询的截止期错失率,并能通过自适应调节CPU利用率参数的方法提高查询处理系统的整体服务质量。
最后,设计开发了一个实时数据流管理原型系统RT-DSMS,用于相关策略与算法的性能评估。这个原型系统提供了良好的可扩展性与可配置性,支持对新增查询调度算法、负载管理策略的测试与分析。
以满足截止期和降低截止期错失率为目标的数据流管理系统研究具有较高的应用价值和良好的应用前景。本文的研究成果为进一步探讨实时查询处理与查询优化,以及混合查询调度提供了良好的基础。