| 题名 | 数据流管理系统中查询处理和实时调度技术研究 |
| 作者 | 李新 |
| 学位类别 | 博士 |
| 答辩日期 | 2008-01-16 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 数据流 连续查询 周期性查询 一次查询 实时查询 滑动窗口 查询处理 查询优化 实时调度 反馈控制 截止期 |
| 其他题名 | Query Processing and Real-time Scheduling In a Data Stream Management System |
| 中文摘要 | 随着信息处理技术在通信、金融、工业生产等领域的广泛应用，数据已不仅仅拘泥于文件、数据表等传统的静态形式。大量连续、变化的流式数据已经在越来越多的现代应用中出现，如：军事指挥、交通控制、传感器数据处理、网络监控、金融数据分析等。在这些应用中，数据以流的形式不断到达，系统需要对这些数据进行及时、连续的处理。如果查询处理时间超过了截止期要求，查询结果就没有意义，甚至会造成灾难性后果。目前大多数研究集中于连续查询的处理与调度，对于以满足截止期为目标的实时查询处理与调度研究比较少，因此本文主要讨论数据流管理系统中实时查询处理问题。 本文首先系统地分析了数据流系统的应用特点、需求和研究现状，在此基础上提出了一种由周期性查询、连续查询和一次查询构成的混合实时查询模型，对各种查询的定义和属性进行了形式化描述。为了方便查询的定义与表示，本文设计了一种类SQL的实时连续查询语言RT-CQL（Real-Time Continuous Query Language）。与CQL语言相比，RT-CQL增加了对周期、截止期、采样率等实时性和近似性特征的描述。 其次，本文结合实时查询的特点，给出了一种实时查询处理框架，讨论了选择、投影、连接等基本操作符的设计与实现。针对多查询共享问题，本文提出了一种带共享段的操作符路径图构造算法。该算法可以根据多个查询计划构造包含公共操作符路径段的操作符路径图，消除其中重复的操作符，提高查询处理效率。 接着，本文针对共享滑动窗口连接问题提出一种相对截止期优先连接算法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 Total Bandwidth Server）算法。该算法根据周期性查询和非周期性查询的负载情况和截止期错失率，动态分配处理器时间。试验结果表明，与其它混合调度算法相比，FC-TBS算法在保证周期性查询截止期的情况下能够降低非周期性查询的截止期错失率，并能通过自适应调节CPU利用率参数的方法提高查询处理系统的整体服务质量。 最后，设计开发了一个实时数据流管理原型系统RT-DSMS，用于相关策略与算法的性能评估。这个原型系统提供了良好的可扩展性与可配置性，支持对新的查询调度算法、负载管理策略的测试与分析。 以满足截止期和降低截止期错失率为目标的数据流管理系统研究具有较高的应用价值和良好的应用前景。本文的研究成果为进一步探讨实时查询处理与混合查询的调度，以及实际应用中的混合查询负载管理提供了良好的基础。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 143 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/5764]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 李新. 数据流管理系统中查询处理和实时调度技术研究[D]. 软件研究所. 中国科学院软件研究所. 2008. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论