（计算机系统结构专业论文）数据流qos自适应框架聚集查询卸载策略的研究.pdf

at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e ra r c h i t e c t u r e ， r e s e a r c ho nl o a ds h e d d i n gf o ra g g r e g a t i o nq u e r i e so v e r 量d a t a s t r e a m si nt h eq 。sa d a p t a t i o nf r a m e w 。r k a j b yd uy u s u p e r v i s o r ：p r o f w a n gg u o r e n n o r t h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 一 l ， t 本人声明所呈交的学位 。研究成果除加以标注和致谓 k 研究成果，也不包括本人为 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：齐土锄 签字日期：，i 弓p 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：奢上名知导师签名 ：习司了 签字日期：了口。7 i _ q签- 7 日期：矽t i 岁。 ， ， 一 东北大学硕士学位论文 数据流q o s 自适应框架聚集查询卸载策略的研究 摘要 数据流自然地出现于很多监控应用中，如网络和金融服务，而这些数据流应用限制 了标准关系数据库技术的适用性。许多数据流源在量上是倾向于爆发性的，而c p u 处 理能力不足和内存有限等瓶颈，一个过载的系统将不能处理它所有的输入数据，而且不 能跟上数据的到达速率，从而使服务质量( q o s ) 降低。因此，使系统能自动地适应于 超过系统能力的输入数据速率高峰，使之能连续地提供当前查询的响应，卸载技术显得 尤为重要。 数据流管理系统中的查询处理需要满足各种服务质量要求，其中延迟是用户非常关 注的q o s 参数。本文研究的基础数据流管理的服务质量自适应框架，它综合考虑了c p u 和内存的限制，保证c p u 负载的平稳和c p u 处理能力被充分利用。 本文研究了在数据流q o s 自适应框架中，数据流聚集查询的卸载算法问题。在c p u 处理能力不足内存超载情况下，在聚集查询操作中对负载进行卸载，并能满足一定的服 务质量。对于一个或多个聚集查询存在的情况下，将原有的框架从得到近似结果进一步 拓展为可以得到精确结果子集的系统框架。在保留原有清洗器，调度器以及卸载器功能 的前提下，进一步改善卸载器的功能，并加入新的如窗口分配器、聚集操作器两个新的 功能模块，以确保满足结果是正确结果的子集。本文使用新的卸载算法与原框架相结合， 保证系统在执行聚集查询操作时能在动态环境中具有良好的自适应性。实验结果表明， 该方法在c p u 利用率及结果错失率性能方面优于其它方法。 关键词：数据流管理系统聚集卸载服务质量自适应 一 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho nl o a ds h e d d i n gf o ra g g r e g a t i o nq u e r i e so v e rd a t a s t r e a m si nt h eq o sa d a p t a t i o nf r a m e w o r k a b s t r a c t d a t as t r e a m sa r i s en a t u r a l l yi nan u m b e ro fm o n i t o r i n ga p p l i c a t i o n si nd o m a i n ss u c ha s n e t w o r k i n ga n df i n a n c i a ls e r v i c e s ，b u tt h e s ea p p l i c a t i o n sl i m i tt h ea p p l i c a b i l i t yo f t h es t a n d a r d r e l a t i o n a ld a t a b a s et e c h n o l o g y m a n yd a t as t r e a ms o u r c e sa r ep r o n et od r a m a t i ca n db u r s t y , a n dc p u c a p a b i l i t ya n dm e m o r y i sl i m i t e d ，s ot h a t0 1 1o v e r l o a d e ds y s t e mc a n n o tp r o c e s sa l lo f t h ei n p u td a t aa n dk e e pu pw i t ht h er a t eo fd a t aa r r i v a l ；a sar e s u l t ，i tc a n n o ta s u r et h eq u a l i t y o fs e r v i c e i nt h i sc a s e ，l o a ds h e d d i n gb e c o m en e c e s s a r yt ol e tt h es y s t e mp r o v i d et h e u p - t o d a t eq u e r yr e s p o n s e sc o n t i n u o u s l y q u e r yr e s u l t si nd a t as t r e a mm a n a g e m e n ts y s t e ms h o u l dm e e tt h er e q u i r e m e n t so fa l l k i n d so fq o s s ，o fw h i c hd e l a yi sa ni m p o r t a n to n et h a tm o s tu s e r sc a r ea b o u t t h ed s m s f r a m e w o r kw h i c ht h i st h e s i sb a s e do nt a k e sb o t hc p ua n dm e m o r yi n t oa c c o u n t o n es i d ei t c a na s s u r et h a tt h el o a di sb a l a n c e da n dt h ec p u c a p a b i l i t yi se f f e c t i v e t h i st h e s i ss t u d i e st h el o a ds h e d d i n gf o ra g g r e g a t i o nq u e r i e so v e rt h ed a t as t r e a m s ， w h i c hi sb a s e do nt h ec o n t r o l - b a s e dq o sa d a p t a t i o nf r a m e w o r k i nt h ec a s eo ft h a tt h ec p u c a p a c i t yi sl i m i t e da n dt h em e m o r yi so v e rl o a d e d ，t h i st e c h n i q u es h e d sl o a df r o mm e m o r y i n a g g r e g a t i o no p e r a t i o n ，m e a n w h i l e ，p r o m i s i n gap r o p e rq o s a st h e r ei sas i n g l ea g g r e g a t i o n o rs e v e r a la g g r e g a t i o no p e r a t i o n s ，t h i st e c h n i q u ee x t e n d st h ee x i s t e df r a m e w o r kt oa n a d v a n c e do n ew h i c hc a ng e tt h es u b s e to ft h ea c c u r a t er e s u l ti n s t e a do fg e t t i n gt h e a p p r o x i m a t eo n e s i tk e e p st h eo r i g i n a lc o m p o n e n t ss u c ha st h ec l e a n e r , s c h e d u l e ra n dt h e l o a ds h e d d e r , - b u ta l s oe x t e n d st h e1 0 a ds h e d d e rp a r t f u r t h e r , a d d i n gn e wc o m p o n e n t sc a l l e d w i n d o w d i s t r i b u t o ra n da g g r e g a t e - o p e r a t o rt ot h ef r a m e ，t op r o m i s et h ea c c u r a t e n e s so ft h e r e s u l t i tc o m b i n e st h en e ws t r a t e g yt ot h ee x i s t e df r a m et om a k es u r et h a tt h es y s t e mc a nb e a d a p t i v ei nd y n a m i ce n v i r o n m e n t sw h e np r o c e s s i n gt h ea g g r e g a t i o nq u e r i e s t h ee x p e r i m e n t s s h o wt h a tt h es y s t e mi so u t p e r f o r m so t h e re x i s t i n gw a y so nr e s o u r c eu t i l i z a t i o na n dd e a d l i n e m i s sr l t i o k e y w o r d s ：d a t as t r e a mm a n a g e m e n t ；a g g r e g a t e ；l o a ds h e d d i n g ；q u a l i t yo fs e r v i c e ；a d a p t i v e ； - - i i i - - ， 东北大学硕士学位论文 目 独创性声明 摘要 a b s t r a c t 。： 第一章引言 1 1 数据流简介 1 2 数据流查询相关技术 1 2 1 滑动窗口3 1 2 2 数据流卸载4 1 2 3 近似查询结果4 1 3 数据流阻塞操作：5 1 4 数据流的应用方向6 1 5 本文组织。8 第二章相关工作9 2 1 数据流原型系统概况9 2 1 1 原型系统简介9 2 2 聚集查询卸载技术的研究1 2 2 2 1 插入卸载操作符的卸载技术1 2 2 2 2w i n d o w - a w a r e 卸载技术1 5 2 3 本章小结j l7 第三章聚集查询卸载框架- 1 9 3 1 总体框架结构及各个组件功能1 9 3 1 1 窗口分配器2 0 3 1 2 卸载器2 1 3 1 3 聚集查询操作器2 l 3 1 4 清洗器2 1 3 1 5 调度器2 4 3 1 6 控制器。2 5 3 2 相关定义及q o s 指标选择2 9 3 3 本章小结3 0 第四章卸载控制的设计31 4 1 窗口分配器31 一i v 东北大学硕士学位论文目录 4 2 卸载器3 2 4 2 1 三种卸载策略的分析3 2 4 2 2 卸载规则3 5 4 2 3 算法3 8 4 3 聚集查询操作器3 9 4 3 1 聚集操作规则3 9 4 3 2 算法3 9 4 4 本章小结3 9 第五章实验测试与分析4 1 ， 5 1 测试平台及测试集4 l 5 1 1 测试平台4 1 5 1 2 测试数据集4 1 5 2 部分模块功能与实现4 5 5 3 实验结果与分析。4 6 5 3 1 数据处理时间估计误差的影响4 6 5 3 2 合成数据集上的比较4 7 5 3 3 真实数据集上的比较4 9 5 4 本章小结5 0 第六章结束语51 i 参考文献5 2 ；g !谢5 7 攻读硕士期间发表的论文矗：5 9 一v 一 东北大学硕士学位论文 第一章引言 第一章引言 随着计算机的普及、新技术的开发和应用领域的扩展，数据库技术发展迅速 并得到了广泛的应用并不断面临着新的挑战。数据的产生形式和管理对传统的数 据库提出了新的功能要求，而数据流技术是应此需求而产生的新的数据库技术。 近几年来，数据流已经成为数据库领域研究的主流方向和热点之一【lj 。它拥有广 。阔的应用前景，w e b 网络，传感器等产生和处理的都是不断变化的流数据，例如： 在传感器网络中，传感器不断产生监控信息( 如：外界环境信息) ，可能需要对数 据做聚集( a g g r e g a t e ) 或连接( j o i n ) 等操作，获得运行状态，做出决策分析。另外 在网络安全方面，需要对数据包流、用户的会话等信息进行监控、过滤，异常监 测、抵御网络攻击和屏蔽病毒来源等操作。在金融领域，需要操作交易数据流， 股票行情数据流，预测行情走势，分析套汇可能性，挖掘数据之间的相关性等等。 数据流技术应用的需求刺激了近几年数据流管理系统( d s m s d a t as t r e a m m a n a g e m e n ts y s t e m ) 的构建，以及相关算法和查询处理技术的研究。许多数据流 源( 例如，网站访问模式，金融市场中的交易，以及网络流量的通讯) 在量上是 倾向于显著尖峰的或是爆发性的，而此时，该过载的数据流管理系统无法对所有 的流式数据进行处理，并且不能跟上数据到达速率。因此，如何根据查询的q o s ， 合理地并且自适应地调整系统处理的数据流负载( 也称卸载l o a ds h e d d i n g ) ，从 而在维持系统的稳定的同时，尽可能地充分利用c p u 资源，使系统能连续地提供 当前的查询响应，提供用户可接受的查询结果，便是亟待解决的问题之一。 1 1 数据流简介 传统的数据库存储的是静态的关系型数据记录的集合，它们具有限定的大小、 可控制的操作、详细定义的结构，同时这些数据具有持久性。传统数据库中的计 算具有时间复杂度和空间复杂度，其查询处理为单次查询，查询计划为静态的， 且最终生成确定的查询结果。另外，传统数据库中的数据除非明确地加入了时间 戳的属性，否则没有时间的概念。虽然这种模型也能充分地满足某些商业或个人 的信息存储的要求，但许多当前的以及今后的应用要求它可以对不断快速变化的 数据流提供在线分析支持。 数据流是连续的，无限的，快速的，随时间变化的数据元素的流。与传统的 东北大学硕士学位论文第一章引言 数据相比，流式数据具有许多特点：它是大量的，连续的，无限的数据；变化很 快，并且要求快速的响应；数据流能很好地满足我们当今数据处理的需要；数据 流管理中随机存取采用的是一种代价昂贵的单一线性的扫描算法；仅仅存储到目 前为止的现有的数据或只存储近期的一部分数据。 针对数据流的这些特点，如何研制一个良好的数据流管理系统( d s m s ) 用 于管理流式数据便成了一个需要解决的问题。就功能和性能而言，一个数据流管 理系统与传统的数据库管理系统( d b m s ) 相似，不同的是，前者允许一些或者 所有数据都以连续的数据流的形式出现。如果将数据集看作是一个特殊的数据流， 那么数据流管理系统可以定义为传统数据库管理系统的扩充。数据流管理系统既 可以管理常规存储的数据关系，又可以处理多维的、连续的、无限制的、快速的 和随时间变化的数据流，它支持长时间连续的查询，并且产生连续带有时序特征 的结果。下面对传统数据库管理系统和新兴的数据流管理系统作简单的比较，以 便了解不同数据形式的处理机制。 d s m s 与d b m s 有许多不同之处： ( 1 ) 关于数据源的前提假设方面。传统的数据库是限定的、静态的数据集合， 它们具有限定的大小，可控制的操作，是持久的、结构详细定义的记录( 关系) 。 数据流则是无限的、在线的数据序列，它们的大小是不确定的，具有不可预知的 动作，是非持久的、无结构或半结构化的数据项。 ( 2 ) 在计算方面。传统的数据库对数据集合进行计算，这种计算是多次的或 无限次的，具有时间复杂度和空间复杂度，可看作事务处理。而数据流管理系统 则是对数据流进行计算，这种计算是一次性的，要求即时响应，其控制或查询大 多为只读式查询。 ( 3 ) 查询处理方面。传统数据库查询处理为单次查询，其查询计划为静态的， 在执行之前进行优化，且只运行一次，最终生成确定的查询结果，系统模型是“数 据被动，查询主动 的，用于处理永久的数据和进行瞬时的查询。对流式数据的 查询处理则是连续的，它们的查询计划是动态的，需要长期的不断地运行，随时 间的变化不断进行优化，其结果是无限的数据流和近似的结果。数据流管理系统 是一种“数据主动，查询被动的模型。 表1 1 总结了数据流管理和数据库管理的不同点。 一2 一 东北大学硕士学位论文 第一章引言 表1 1 数据库和数据流的比较 t a b l e1 1c o m p a r i s o n sb e t w e e nd a t a b a s ea n dd a t as t r e a m s 数据流数据库 数据源元组序列元组集合 数据持续时间瞬时性持久性 查询性质 实时性，连续查询离线性，一次性查询 查询处理一遍扫描 任意多次 查询结果近似结果精确结果 查询计划适应性的固定的 数据量无限的有限的 数据流管理系统设计中的一个重要问题是如何有效地处理连续查询( 流式查 询) 。所谓连续查询，是指一旦一个查询确立之后它将长时间连续执行。对数据流 进行的查询为连续查询，它在一段时间内连续执行，随着新的数据的到达将不断 地产生新的查询结果。例如，在网络通信量管理中，连续查询用于在线监控网络 行为，以便及时发现异常( 如连接异常) 和产生异常的原因( 如硬件失败、服务 器受到攻击等) 。连续查询还用于支持负载平衡或其他网络性能调整。在许多金融 管理系统中，连续查询常用于监控趋势变化。 1 2 数据流查询相关技术 流式数据本身的独特性给数据流计算模型中的查询处理带来了许多新的挑 战。传统的数据库管理系统中的触发器、物化视图等概念为流式系统的研究提供 了许多借鉴之处。 1 2 1 滑动窗口 一种用于对数据流查询产生近似结果的方法是：不是对数据流的所有的历史 数据进行求值，而是仅仅对数据流的最近的滑动窗口中的数据进行求值。例如， 仅仅考虑最近一周中的数据，而其他一周之前的数据都不作考虑。 在数据流中引入滑动窗口来产生近似的查询结果，这种方法有其自身的道理。 首先，滑动窗口是被详细定义过的，而且很易理解：近似语义是很清楚的，因此 系统的用户可以确信他们能够理解在产生近似结果时丢弃掉的那部分数据。其次， 一3 一 东北大学硕士学位论文第一章引言 由于滑动窗口具有确定性，所以不必担心不适宜的任意地选取将产生非近似的计 算结果。最重要的一点是，滑动窗口强调的是最近的数据，在现实世界的大多数 应用中，最近的数据要比旧的数据重要得多。而且人们关心的往往是最新的数据， 这在流式应用中格外明显。 从另外一个角度理解，滑动窗口的目的就是阻止陈旧的数据影响系统的分析 和统计，并且它是利用有限的内存空间的一种近似工具。d a t a r 等人1 2 j 研究了如何 对滑动窗口进行简单的统计，包括概要的提取技术。b a b o c k 等人【3 】将取样技术用 于滑动窗口模型。目前在将概要技术用于滑动窗口方面的工作还很少，此方面的 研究时机已经成熟。 1 2 2 数据流卸载 当突发流量超过系统的处理能力，如果不采取相应的措施，会导致整个系统 的吞吐量和响应时间都恶化。卸载通过丢弃一定数量的数据，在部分牺牲准确性 和完整性的条件下，保证系统的性能。卸载算法可以根据采用的处理方式分为以 下两种：随机的卸载算法和基于语义的卸载算法。 随机卸载是指在发现数据输入超出系统处理能力时，通过按一定的比重随机 丢弃部分元组保证系统的正常运行。基于语义的卸载，通过用户对流处理语义的 理解，有选择地丢弃一部分元组，使元组损失对系统性能和输出结果的影响最小 化。目前普遍采用的卸载算法般是基于语义的【4 ，5 】。基于语义的卸载算法与系 统的上下文有关，主要考虑的问题是：何时，何地以及如何进行。它包含更多的 语义判断条件。 d c a r n e y 4 j 提出了通过丢弃元组实现的随机卸载和通过过滤元组实现的语义 卸载，过滤指有控制地丢弃一些不重要的元组来保证系统的q o s 。b b a b c o c k ， m d a t a r 5 】指出了d c a r n e y 的不足一一该基于语义的卸载并不能有效地保证查询 的精确性，从而提出改善精确性的方法，并通过配置随机抽样算子来具体实现基 于语义的卸载。随着数据流上查询代价的增加，研究者已经广泛地意识到了卸载 研究的意义和重要性。 1 2 3 近似查询结果 当系统性能满足数据流处理的要求时，处理结果可以正常输出。但当处理要 求超出系统的处理能力时，如突然爆发流量、处理数据流所需内存超出物理内存、 c p u 处理能力不够时，可能导致系统总体性能降低。这时对数据流的查询不可能 一4 一 东北大学硕士学位论文第一章引言 产生精确的结果。然而，高质量的近似结果在许多情况下也可以被接受。d s m s 采 用计算近似值的方法，通过发现处理数据流的相似性，将其进行归类处理，对每 一个数据项的处理时间要尽量减少，在准确性与存储数据流摘要的存储空间之间 折中平衡。近似值计算是d s m s 中重要的数据处理方式，所采用的算法根据具体 方法的不同分为计数( c o u n t i n g ) 、哈希【6 ，7 1 ( h a s h i n g ) 、抽样( s a m p l i n g ) 8 , 9 1 、概 要( s k e t c h e s ) 、直方图( h i s t o g r a m s ) 1 0 , 1 1 1 和小波【1 2 】( w a v e l e t s ) 等。 g a r o f a l a k i s ，g i b b o n s l l 3 1 提出了一种任意纲要的思想，该方法已经被广泛采用。 小波分析图通常作为一种数据的摘要表示法，它的系数是已给信号( 数据值集) 在一 个基向量的正交集上的投影。基向量的选择决定了小波分析的类型。小波分析变 换将潜在的信号化简为一小部分系数，这些系数用于对无限的数据流进行近似合 计。另外，直方图也是一种常用的概要结构表示方法，用于简洁地表达一个数据集 合的数据值分布情况( 如一个库表中的一列) 。直方图可用于多重目的，如查询大 小估计、近似查询结果以及数据挖掘等。可以通过直方图来研究数据流的概要【1 4 】。 1 3 数据流阻塞操作 所谓阻塞操作，是指只有当获得所有的输入数据之后，输出结果的第一个元 组才有可能产生的查询操作。排序就是一个阻塞操作的典型例子。另外s u m ， c o u n t ，mi n ，m a x 以及a v g 等聚集操作都属于阻塞操作。利用传统的查询 操作树来对流式查询进行求值，假设数据流从叶节点输入，从根节点输出最终查 询结果，则查询树中阻塞操作的合作执行构成了问题的关键。由于连续的数据流 是无限的，一个阻塞操作将数据流作为它的输入将不可能获得一个完整的输入， 因此它也不可能产生任何输出结果。显然，阻塞操作不适合数据流模型的计算， 然而聚集查询又是非常普通的操作，并且分类过的数据比未分类过的数据更容易 处理，同时会大大提高处理的效率。由此去除所有的阻塞操作是不切实际的，如 何有效地处理它们就变成了数据流计算的一个重要的问题。 针对阻塞操作的局限性，目前提出了两种解决该问题的方法，以更好的计算 数据流上的阻塞操作符： ( 1 ) 用功能类似的非阻塞操作代替查询树中的内部阻塞操作。该方法的一个 典型例子是j u g g l e 操作【l5 1 ，它是一个用于排序的非阻塞操作。其目的是在新的数 据到来之前先对已到达的数据进行局部性排序，在数据输入的过程中不断地重新 排序。该方法存在的问题是如何将这种方法应用到其他类型的阻塞操作中，以及 如何有效地评价用非阻塞操作代替阻塞操作过程中产生的近似误差。 ” 一5 一 东北大学硕士学位论文。第一章引言 ( 2 ) t u c k e r 等人提出了另外一种处理阻塞操作的方法。他们建议在数据中 增加断言，用于声明在后继的数据流中什么是可以出现的，什么是不可以出现的。 这些断言叫作p u n c t u a t i o n s ，它们在数据流中与数据项进行交叉存储。例如，在一 个具有属性“a g e 的数据流中，一个该类型的断言为“f o ra l lf u t u r et u p l e s ，a g e 2 0 。在该断言的基础上，通过a g e 进行分组的聚集操作将流出a g e 2 0 的结果。 1 4 数据流的应用方向 数据流应用具有广泛的需求和应用前景。下面以几个发展方向为例，进行简 ， 要的介绍。 传感器网络传感器网络可用于地理位置监控，公路拥塞监控，动物追踪，生 命信号的医疗监控和制造过程的超级监控。这些应用都涉及复杂的过滤和发现数 据中异常模式的被激活的报警设置。分析从多个数据源到达的大量流式数据的聚 合和连接。当某些传感器失败时，流数据的聚合需要补偿。传感器的数据挖掘可 能需要访问一些历史数据，代表性的查询操作有：激活触发器。当同一地域的几 个传感器报告测量值超过给定闽值；在气象图上绘制温度控制线，执行由气象监 控站产生的温度流的连接，连接结果形成带有每个站的经度和纬度的静态表，将 报告同一温度的点连成线；数据流当前能量使用统计分析，必要时调整能量产生 率。 网络流量分析实时分析i n t e r n e t 流量的特殊网络( a dh o cn e t w o r k ) 已经被使 用。与传感器网络功能相同的是：多个数据源到达的数据连接、包监控、包过滤、 检测异常情况和支持历史查询。此外，它的功能还包括监控对热点u r l 的需求或 发现用户消耗的最大带宽。在网络流量分析中典型的查询是：流量许可。决定源 一目的节点对以及不同i p 地址组、子网掩码和协议类型站点的总带宽，i p 流量 是多元统计的，因此，流量数据流必须能逻辑分解以便能重构基本的t c p i p 会 话。而且，分解进入会话的数据流涉及临时语义问题。比较不同的源一目的站点 对的数量：比较在t c p 三次握手中分别包含第二第三步的逻辑流中不同的源一目 的站点对的数量。若计数值超过一个大的极限，那么一个拒绝服务事件会产生， 连接许可不被欺骗的用户承认。 金融分析在线股票价格分析涉及发现关联、鉴别趋势、仲裁机会和预测未来 值。典型的基于w e b 金融分析器允许用户作如下查询：h i g hv o l a t i l i t yw i t hr e c e n t v o l u m es u r g e ，即查询所有股票价格在2 0 美元到2 0 0 美元，其最高价和最低价之 间在过去3 0 m i n 高过三个百分点的股票分布图，以及最后5 m i n 其震荡平均量超 一6 一 东北大学硕士学位论文第一章引言 过3 0 0 的股票；n a s d a ql a r g ec a pg r a i n e r ，即查询n a s d a q 指数高于2 0 0 天 的平均变动，以及当天开盘起价格盈利在2 l0 个百分点，买卖量超过5 0 亿的股 票：t r a d i n gn e a r5 2 2w e e kh i g ho nh i g h e r v o l u m e ，即查询所有价格在5 2 周高度 的两个百分点，每天成交量至少一百万的股票。 事务日志分析在线挖掘w e b 使用日志、电话记录和自动银行取款交易也符 合数据流的模型。其目标在于发现有趣的客户行为模式，鉴别可疑的开销行为以 便防止欺诈和预测未来数据。与其他数据流应用一样，它需要多个数据流的连接、 复杂的过滤和统计分析。常见的查询有：查询某一服务器的最近l5 m i n 被访问的、 其速率至少高于日平均速率4 0 的所有w e b 页；如果主服务器过载，实时检测 w e b 服务器日志和重新路由的用户；漫游直径，挖掘无线电话和每个客户，决定 每个电话使用的不同基站的最大数量。 需求分析下面列举的是流式数据连续查询基本操作项集和在未来的新应用 中可能增加的需求：s e l e c t i o n 一一所有流数据的应用都需要支持复杂的过滤； n e s t e da g g r e g a t i o n 一一复杂的聚合，包括嵌套聚合，用于计算数据的趋势； m u l t i p l e x i n ga n dd e m u l t i p l e x i n g 一一物理流需要被分解为一系列逻辑流，相反， 逻辑流需要合成物理流( 类似于g r o u p b yu n i o n ) ；f r e q u e n ti t e mq u e r i e s 一一已知 的有t o p k 项或阈值查询，依赖于分离点的条件；s t r e a mm i n i n g 一一模式匹配、 相似性查询和预测都需要在线的流数据挖掘。目前已有的流挖掘算法有计算流信 号和代表性趋势、决策树、预测、k m e d i a n 聚类、最近相邻查询和回归分析；j o i n 一一支持多个数据流连接和带静态元数据的流数据的连接；w i n d o w e dq u e r i e s 一 一上述所有查询类型的返回结果都可能被限制在一个窗口内。 数据流挖掘自2 0 世纪9 0 年代中后期数据挖掘( d a t am i n i n g ) 技术引起研 究者的重视以来，这个研究方向发展非常迅速。经过近十年的发展，关联规则、 聚类、分类等的基本挖掘算法已经比较成熟。目前，挖掘技术的研究重点逐渐转 移到新应用领域上，即演变为数据流上的知识发现。在分析和挖掘数据流时，由 于数据流迅速、大量、连续地到达，算法只能对数据流进行单遍扫描，仅临时在 内存中存储少量数据，因此原来许多较为成熟的静态数据挖掘技术变得不再适用 了，需要提出新的内存驻留相关的算法。这是数据流连续挖掘问题出现的技术背 景和要求。 由于数据流具有独特的性质，对其进行连续挖掘是一个挑战性的问题。当前 的有关算法的研究有很多是在传统的增量式挖掘技术基础之上发展而来的，探索 数据流连续挖掘技术与传统的静态数据挖掘技术之间的本质区别，提出更有效、 一7 一 i 东北大学硕士学位论文第一章引言 新颖的基于内存的数据流连续、快速挖掘算法是当前研究面临的重要问题。 1 5 本文组织 本文选取数据流研究领域中的一个具体问题一一聚集查询的负载控制，进行 了详细的分析和讨论，提出了一个基于q o s 自适应的聚集查询框架，实现并研究 了在此框架下采用不同策略构建系统的性能。 第一章介绍了数据流的涵义，数据流研究领域所要研究的问题，未来研究的 方向，数据流的具体应用实例等。第二章总结了数据流管理系统的研究现状和关 于数据流卸载问题主要是聚集查询技术的相关工作。第三章提出基于q o s 自适应 的聚集查询框架及卸载的理念，目的是尽可能地充分利用c p u 资源，提高流处理 的效率和准确性。第四章具体设计了该框架中的重要组成部分，讨论了卸载策略。 第五章则是在数据集上测试了该框架的性能。最后在第六章对进行了全文进行了 总结，并介绍了未来的需要继续深入的研究工作。 一8 一 东北大学硕士学位论文第二章相关 第二章相关工作 针对目前出现的这种对流式数据进行管理的应用需求，国外的许多大学 构已在这方面开展了大量的研究工作。下面介绍一些国外研制的与数据流管 关的原型系统，数据流上的查询处理研究以及聚集查询卸载的相关工作。 2 1 数据流原型系统概况 当网络控制器、电信数据管理、网络个性化、生产、传感器网络等应用出现 之后，数据大都是连续的数据流，而不是有限存储的数据集合，并且与过去的那 种单次查询相反，在此用户需要长期的、连续的查询，这就对数据库系统以及数 据的处理算法等提出了新的挑战。目前很多大学和机构正在致力于开发一种面向 新的应用的数据流管理系统，比较成型的数据流管理系统原型有斯坦福大学的 s t r e a m 系统【l6 1 ，布朗大学、布兰德斯大学和麻省理工大学联合开发的a u r o r a 1 7 】， 美国加州大学伯克利分校的t e l e g r a p h c q i s 】等。 2 1 1 原型系统简介 s t r e a m 斯坦福大学已经开始了一种全面d s m s 的设计和原型实现，该系统为 s t r e a m ( s t a n f o r ds t r e a md a t am a n a g e r ) 。它是一个通用的数据流管理系统。 该系统支持一种描述性查询语言c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) ，用户可以采 用c q l 注册数据流查询，也可以直接输入查询计划。s t r e a m 可按照用户的查 询需求针对数据流进行实时的连续查询。用户或应用程序向系统注册查询，被注 册的查询将一直保留到查询被显式地注销为止。在s t r e a m 系统中，用户采用 。 c q l 注册的查询经过查询编译器生成查询计划，系统为每个查询产生一个独立的 查询计划。在用户直接输入查询计划的情况下，调度策略在有流速突发的情况下 可能导致很高的输出延迟，对其改进( c h a i n f l u s h ) 后可以把输出延迟限定在某 个预定义的范围内。它可以用于处理快速的、易变的、大量涌入的数据流信息， 其连续查询能力非常好。 s t r e a m 是一个以关系为基础的数据流管理系统，它重点在于内存管理和近 似查询。s t r e a m 的主要处理技术包括：连续的自我监控和再优化；适应于不同 一9 一 东北大学硕士学位论文 第二章相关工作 需要的良好近似；合理的资源分配和使用。如今，s t r e a m 项目已经结题，它可 以支持多种查询语言。s t r e a m 工作组正准备在w e b 上开放一个服务，以供感 兴趣的人可以通过w e b 对s t r e a m 原型系统进行试验和研究，另外他们还计划 提供下载。 a u r o r a 布朗大学、布兰代斯大学和麻省理工大学联合开发的a u r o r a b o r e a l i s 系统是 新型的数据处理系统，被设计用来处理大数量的数据流。用户在一组操作符( 也叫 b o x e s ) 之外建立查询。当前的执行提供一个用户接1 3 用来录入预先存在的输入及 网络流，并将b o x 绑在一起来产生输出结果。 i 一个简单的流是元组的无限序列，有着同样的流i d 。一个弧( a r c ) 携带多 个简单流。简单流可以从系统中被添加和删除，不需要修改该系统的基本网络结 构。一个查询，是一个子网，以一个单独的输出结束，并包含任意数量的输入。 b o x e s 可以连接到多个下游的b o x e s 。所有这样的分裂路径携带同样的元组。多重 流可以被合并，因为一些b o x e s 接受多于一个的输入( 例如，j o i n ，u n i o n ) 。 a u r o r a 运行引擎，通过一个大型的工作流图表处理流。从数据源来的输入和 从b o x 所产生的输出被送给路由器，路由器将其传给外部的应用，或传给存储管 理器而后放入适当的队列中。存储管理器用来维护b o x 的队列并管理着缓存。调 度器挑选一个用来执行的b o x ，确定需要什么处理，并给该b o x 的描述以一个指 针( 以及给该b o x 的状态一个指针) 指向多线程b o x 处理器。该b o x 处理器执行 适当的操作，然后将输出元组传寄给路由器。之后，调度器会确定下一个处理步 骤，周而复始。对q o s 进行求值的程序则一直监测系统的性能，当它监测到卸载 情况的发生以及系统性能变坏时，采用l o a d s h e d d i n g 技术，即激活卸载器进行卸 载，直到系统的性能达到可接受的水平。 a u r o r a 系统采用了批处理技术来降低调度代价和操作符执行代价【l 。系统 支持两种方式的批处理：对操作符调度的批处理和对元组的批处理。a u r o r a 系统 对于大量的实时数据，根据定义的服务质量( q o s ) 模型，必要时，修改查询计划， 卸掉一定的过量负载，以保证系统的响应速度。a u r o r a 简单独特的框架结构可以 处理三种不同的应用：实时监控应用，处理以时间序列存储的大量历史数据的档 案管理型应用和包含对历史以及当前数据进行处理的跨度应用。 a u r o r a 系统的核心是一个巨大的触发器网络。每个触发器是一个数据流向图， 图中的每一个节点则是七种b u i l t i n 操作( 或b o x e s 一一a u r o r a 系统的术语) 中的一 一1 0 一 东北大学硕士学位论文第二章相关工作 个。对每一个使用a u r o r a 系统的流监控应用，应用管理器创建一个或多个触发器 加入到a u r o r a 的触发器网络中。a u r o r a 系统实现了触发器网络的编译时优化和运 行时优化。在进行运行时优化时，a u r o r a 可以检测到资源超载并根据实际应用情 况进行负荷减压。另外，他们还正在设计一种可升级的分布式a u r o r a ，叫作 b o r e a l i s 1 9 】。b o r e a l i s 的主要目标在于使系统对分布式数据流处理应用达到一种比 较高的可量测性和实用性。 t e l e g r a p h c q 加州大学伯克利分校研制的t e l e g r a p h c q 系