数据流 QoS 自适应框架聚集查询卸载策略的研究

第2卷第10期2007年10月735中国科技论文在线SCIENCEPAPERONLINE数据流QoS自适应框架聚集查询卸载策略的研究杜钰，韩东红，王国仁（东北大学信息学院,沈阳110004）摘要：本文研究了在数据流QoS自适应框架中，数据流聚集查询的卸载算法问题。在CPU处理能力不足内存超载情况下，在聚集查询操作中对负载进行卸载，并能满足一定的服务质量。对于一个或多个聚集查询存在的情况下，将原有的框架从得到近似结果进一步拓展为可以得到精确结果子集的系统框架。在保留原有清洗器，调度器以及卸载器功能的前提下，进一步改善卸载器的功能，并加入新的如窗口分配器、聚集操作器两个新的功能模块，以确保满足结果是正确结果的子集。本文使用新的卸载算法与原框架相结合，保证系统在执行聚集查询操作时能在动态环境中具有良好的自适应性。实验结果表明，该方法在CPU利用率和错失率优于其它方法。关键词：计算机系统结构；数据流管理系统；聚集；卸载；服务质量中图分类号：TP311.13文献标识码：A文章编号：1673－7180(2007)10－0735－60引言数据流技术拥有广阔的应用前景，Web网络，传感器等产生和处理的都是不断变化的流数据，例如：在传感器网络中，传感器不断产生监控信息(如：外界环境信息)，可能需要对数据做聚集(Aggregate)或连接(Join)等操作，获得运行状态，做出决策分析。另外在网络安全方面，需要对数据包流、用户的会话等信息进行监控、过滤，异常监测、抵御网络攻击和屏蔽病毒来源等操作。在金融领域，需要操作交易数据流，股票行情数据流，预测行情走势，分析套汇可能性，挖掘数据之间的相关性等等。数据流技术应用的需求刺激了近几年数据流管理系统(DSMS－DataStreamManagementSystem)算法和架构的研究，并出现一些具有不同应用背景的实际系统，如：STREAM[1]，Aurora[2]，Telegraph[3]等。与传统数据不同的是，流数据具有连续产生在线到达、规模宏大且无界、仅在内存停留有限时间，出现爆发流等特点。在流数据的诸多特点环境下，传统的DSMS中的查询处理要面临着资源有限（如CPU处理能力，内存容量，带宽等）和资源分配高度可变的问题，以及在这种动态的环境中如何保证优质QoS服务的问题。文献[4]中提出的数据流QoS自适应框架正是为解决上述挑战而提出的。该框架综合考虑了CPU的处理能力和内存的负载情况，在数据流速和系统处理代价不可预测的环境中，自适应地通过卸载来保证查询的QoS，原则上适用于任何DSMS系统，结构如图1所示。图1基于控制的QoS自适应框架Fig.1Control-basedQoSadaptationframework基金项目：国家自然科学基金(60573089,60273079)作者简介：杜钰(1982－)，女，硕士研究生通讯联系人：王国仁，教授，E-mail：[e-mail]第2卷第10期2007年10月736本文对聚集查询的研究是建立在文献[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]等，监控方法有反馈触发和提前检测等。卸载方法有随机算法[10]、语义卸载[6]两种，前者只是随机丢弃一定比例的数据，后者在卸载时考虑数据的重要性，文献[9]将抽样应用在卸载控制中，能够提供查询结果的统计抽样结果。常用的卸载方法是在DSMS的操作网络中插入卸载操作，在这方面有许多如何优化的方法，有些文章针对某个查询操作研究卸载控制策略，比如针对连接(join)[11],聚集(Aggregate)[12]等。文献[4]将控制理论应用在卸载控制中，它将DSMS看作被控对象，应用PI控制方法，取得了较好的控制效果，而且理论上能应用于任何种类的DSMS。迄今的卸载控制策略大多数将CPU当作主要的限制瓶颈考虑，所作的监控和优化也都围绕CPU进行，一定程度上忽略了内存的作用。有些考虑内存优化的文章有的是优化某个操作的实现策略以在查询过程中占用尽量少的内存[9],或者寻找某些先进调度方法优化DSMS的内存资源占用量（如Chain）,而不是针对内存瓶颈考虑卸载，没有将内存充分考虑在卸载策略内。文献[5]中提出通用数据流QoS自适应框架，综合考虑内存容量和CPU处理能力，既保证了CPU工作在允许负荷下，也充分发挥了内存的作用尽量提高QoS，对突发流环境有很好的效果。但是该框架中QoS的评价标准是数据的截止期，而且没有定义任何特定的实际操作。如果考虑是聚集查询的话，评价的QoS会有所变化。在某个可以容忍的延迟范围中，用户关心的会是结果的准确性，结果数量的多少等其他方面。关于聚集查询的卸载，文献[12]采用的是将卸载操作符插入到查询树中，以统计学的方法，在使输出结果的相对误差最小的情况下进行卸载。文献[13]采用的是对某些个窗口卸载，在保证输出结果是正确结果的子集的情况下进行卸载。2聚集操作的卸载策略2.1相关定义文中用到的QoS参数定义：错失率(deadlinemissRatio)，CPU利用率。文中相关变量假设：t——单个元组；T——t的时间戳；Qi——第i个查询；wTi——时间戳为T的元组t，其对于查询Qi的窗口标志位；dT——时间戳为T的元组t，其卸载标志位。2.2框架各组件功能由于卸载的存在使得用户得到的聚集操作数据存在误差，在某些情况下这是不允许。尤其是在用户要求结果精确的情况下。但是由于CPU的处理能力有限，面对到达的海量数据是不可能做到完全处理的，即使都能处理，产生的数据早已超时，失去了计算的意义。本文提出的算法是专门针对此类问题的。和其它基于滑动窗口卸载的方法不同，本文方法采用的是可变窗口。窗口分配器根据用户提出查询具体问题、具体数据情况确定窗口大小。例如：数据流QoS自适应框架聚集查询卸载策略的研究第2卷第10期2007年10月737中国科技论文在线SCIENCEPAPERONLINE用户需要在过去5s内的数据上做某些聚集操作查询，每4s更新一次，则窗口分配器定义滑动窗口的大小为5s，滑动间隔为4s。与原来的自适应框架相比较，新框架依旧保留了清洗器，调度器的功能，并对卸载器的功能作了相应的调整以适应聚集操作提出的要求。此外，在图1所示的上游部分添加了窗口分配器，在下游部分添加了聚集操作器。2.2.1窗口分配器每当数据到达缓存时，窗口分配器对其进行窗口范围的划分，即划分出以后将进行聚集查询操作的范围，将未来聚合操作窗口开始的第一个元组其标志位置位。我们从最简单的情况举例说明，即当只有一个聚集查询Q1时，如图2所示。数据到达时，每个窗口标志位w初始值都为0。在每个设置标志位周期内，窗口分配器将根据查询Q1的窗口大小将缓存内的数据划分所属的窗口范围，即对于每个未来在同一个窗口内的数据子集中的第一个元组，将其窗口标志位置为“1”，如图2中窗口标志位一行所示。2.2.2卸载器数据到达时，每个元组的卸载标志位d初始值都为0。在每个卸载周期内，卸载器除了要进行正常的卸载操作，同时还要对每个元组的卸载标志位进行置位。如图2所示，阴影部分是经由计算将要丢弃掉的元组，卸载器将它们正常卸载。卸载掉足够的元组之后，对位于最后一个被卸载元组之后的元组，即不再进行卸载的第一个元组，将它的卸载标志位置为“-1”。由此就能表明，在该元组之前曾经进行过卸载，该元组本身以及后面的部分元组如果继续参加某个窗口上的聚集查询，则得到的结果将是不准确的。因此，从该元组开始的某部分元组不应参与计算。在此做卸载标志位的置位即是提醒未来聚集操作器的计算。2.2.3聚集操作器聚集操作器根据每个窗口的起始位开启一个滑动窗口进行计算，即检查元组的窗口标志位。每当遇到标志位为“1”的元组，则表明到了一个窗口开启的起点。在进行该窗口的聚集查询计算时，还要对属于该范围的每个元组的卸载位进行检验。如果遇到该位被置位为“-1”的元组，则终止该窗口的计算。因为这表示，在该元组之前已经丢弃了部分元组，而导致计算结果不精确。图2单个聚合查询卸载情况Fig.2Loadsheddinginsingleaggregationquery上面讨论了最简单的情况，即只有一个查询Q1的情况。而在实际应用中，会有多个用户提交多个查询。因此，每个元组都要有相应的窗口标志位。窗口分配器根据查询的个数，查询窗口的大小，分别给每个元组相应个数的窗口标志位，并进行置位。如图3所示，由Q1和Q2两个查询，窗口大小分别为5s和4s，滑动间隔分别为4s和3s,则每个元组的窗口标志位有两个即w1，w2。卸载器在卸载时，同样将位于被丢弃元组后的那一元组的卸载标志位置“-1”，而且不同于窗口标志位，每个元组只有一0010001000100010000000000000000窗口标志卸载标志0000000-100000000010001000100010窗口标志卸载标志第2卷第10期2007年10月738个卸载标志位。元组进入聚集操作器后，聚集操作器根据各自的窗口标志位开启滑动窗口并分别进行计算。如果遇到卸载标志位为“-1”的元组，则聚集操作器将放弃Q1和Q2在包含该元组的窗口上的计算结果，以达到结果是精确结果的部分子集的目的。图3多个聚合查询卸载情况Fig.3Loadsheddinginmultipleaggregationqueries由上述例子我们可以拓广到i个查询Q1，Q2，…，Qi，每个元组需要有i个窗口标志位——分别对应i个查询，以及一个卸载标志位。2.3算法描述1)接收数据，应用下列算法：(a)将每个新到来的时间戳为T元组t，放入缓存buffer队列中。(b)定义指针p指向buffer的第一个元组。在每个周期内，调用窗口分配器(i)while(!buffer.end())(ii){p-wT1，…，wTi置位0或1;p-dT置位0;p指向下一个元组;}(c)重新设置p指向buffer的第一个元组。2)卸载数据，应用下列算法：(a)计算卸载数量(b)从指针p开始卸载相应数量的元组(c)对位于最后一个被卸载元组之后的元组，置卸载标志位为-1，即p-dT’=-1(d)令指针p指向buffer的第一个元组3)处理数据，应用下列算法：(a)对每个到达cpu的元组t，检查窗口标志位w1，…，wi(b)ifwTj=1{(i)为查询Qj启动滑动窗口，指针q指向t(ii)if(q-dT!=-1)(iii){t参与计算查询Q1，Q2，…，Qi，q指向下一个元组}(iv)el