http://www.paper.edu.cn数据流QoS自适应框架聚集查询卸载策略的研究1杜钰，韩东红，王国仁东北大学信息学院,辽宁沈阳(110004)E-mail：wangguoren@ise.neu.edu.cn摘要:本文研究了在数据流QoS自适应框架中，数据流聚集查询的卸载算法问题。在CPU处理能力不足内存超载情况下，在聚集查询操作中对负载进行卸载，并能满足一定的服务质量。对于一个或多个聚集查询存在的情况下，将原有的框架从得到近似结果进一步拓展为可以得到精确结果子集的系统框架。在保留原有清洗器，调度器以及卸载器功能的前提下，进一步改善卸载器的功能，并加入新的如窗口分配器、聚集操作器两个新的功能模块，以确保满足结果是正确结果的子集。本文使用新的卸载算法与原框架相结合，保证系统在执行聚集查询操作时能在动态环境中具有良好的自适应性。实验结果表明，该方法在CPU利用率和错失率优于其它方法。关键词:计算机系统结构；数据流管理系统；聚集；卸载；服务质量；中图分类号:TP311.13文献标识码：A文章编号：1673－7180（2007）10－0.引言数据流技术拥有广阔的应用前景，Web网络，传感器等产生和处理的都是不断变化的流数据，例如：在传感器网络中，传感器不断产生监控信息(如：外界环境信息)，可能需要对数据做聚集(Aggregate)或连接(Join)等操作，获得运行状态，做出决策分析。另外在网络安全方面，需要对数据包流、用户的会话等信息进行监控、过滤，异常监测、抵御网络攻击和屏蔽病毒来源等操作。在金融领域，需要操作交易数据流，股票行情数据流，预测行情走势，分析套汇可能性，挖掘数据之间的相关性等等。数据流技术应用的需求刺激了近几年数据流管理系统(DSMS－DataStreamManagementSystem)算法和架构的研究，并出现一些具有不同应用背景的实际系统，如：STREAM[1]，Aurora[2]，Telegraph[3]等。与传统数据不同的是，流数据具有连续产生在线到达、规模宏大且无界、仅在内存停留有限时间，出现爆发流等特点。在流数据的诸多特点环境下，传统的DSMS中的查询处理要面临着资源有限(如CPU处理能力，内存容量，带宽等)和资源分配高度可变的问题，以及在这种动态的环境中如何保证优质QoS服务的问题。文献[4]中提出的数据流QoS自适应框架正是为解决上述挑战而提出的。该框架综合考虑了CPU的处理能力和内存的负载情况，在数据流速和系统处理代价不可预测的环境中，自适应地通过卸载来保证查询的QoS，原则上适用于任何DSMS系统，结构如图1所示。1本课题得到国家自然科学基金(60573089,60273079)的资助。-1-http://www.paper.edu.cn图1基于控制的QoS自适应框架Fig.1Control-basedQoSadaptationframework本文对聚集查询的研究是建立在文献[4]的自适应框架中。由于流数据的无限特性，因此将查询操作建模为在滑动窗口上的操作。该滑动窗口可以是基于时间的(time-based)也可以是基于数量的(count-based)。在本文中滑动窗口是基于时间的，即滑动窗口是由一定时间范围内的连续元组组成。在队列中，调度器要根据某一属性进行排序(通常是时间)。清洗器则根据估计各个窗口中是否超过了所能容忍的延迟范围来对每个窗口进行清洗。卸载器则根据CPU负载能力并在保证结果正确性的条件下，判断和实行对哪些窗口进行卸载。缓冲的数据存储可以采取多种数据结构，比如队列、哈希表、树等结构，可以根据需要选择。数据进入下游的流速控制采用了文献[5]中的基于经典控制理论的反馈控制方法，产生的控制信号是卸载率。我们的QoS是以结果是正确结果的子集为标准的，这样就不同于文献[4]的只能局限于几种特定的聚集查询，而能容易地支持用户定义的查询函数。文献[4]提出的方法考虑了CPU负载能力，而没有将在一定环境下，内存也会超载的情况考虑进去。我们的研究综合考虑了CPU和内存的负载能力。这样，由于操作为聚集查询操作，与文献[4]的框架不同的是，要相应调整控制调度策略和清洗策略、滑动窗口的功能、工作方式及卸载的重要性。1.相关工作DSMS的系统资源瓶颈主要有CPU[6]，内存[7]，和网络带宽[8]，卸载控制主要考虑的问题有：什么时候做(When)，在什么位置做(Where)，应该卸载多少(Howmuch)，卸载的元组如何选择(Which)和如何衡量卸载质量(Objectives)。当前研究考虑的优化衡量参数有包括查询准确性[9]、QoS[6]等，监控方法有反馈触发和