（计算机应用技术专业论文）数据流管理系统及其相关算法的研究与实现.pdf

大连理工大学硕士学位论文 摘要 传统的数据库管理系统用于处理永久的数据和进行瞬时的查询。然而，随着网络、 电信和传感器技术的发展，出现了一种新的数据处理模型。在这种模型中，出现了一种 瞬时流数据上的连续长时间的查询。传统数据库存储的是相对静态的记录集，不是为快 速和连续输入的单个数据项设计的，而且它不能直接支持连续查询。传统数据库管理系 统在数据流应用方面的限制，引起了国内外很多学者和研究机构的注意。 在当今的网络监控、电信数据管理、传感器数据监控等应用中，数据采取的是多维 的、连续的、快速的、随时间变化的数据流的形式，对数据的访问也是多次和连续的， 并要求即时的响应。研究表明传统的关系数据库系统难于适应这种流式应用的数据管理 需求，因此如何有效地开发一种新型的数据库系统来满足这种新的数据处理要求己成为 目前研究的一个热点课题。 本文的工作就是按照研究课题的要求，针对现实网络速率不稳定这一问题，对数据 流管理系统中输入监控、概要构建和负载平衡控制等三个功能模块的算法进行了改善， 分别对各自现有的常用算法进行了一些改进，设计了可以根据网速进行自适应变化的直 方图算法、分层更新的近似树和基于内存的负载平衡控制方法，使得各功能模块对实际 网络可以有一定的适应能力，特别是在网速突然增大的情况下，可以有一个快速、及时 的处理反应。最后，再将这些改进应用到一个通用的数据流管理系统p o w e r s t r e a m 中， 使得其对于现实环境中，网速不稳定情况下的数据流有了更好地管理支持。该系统是参 考了国外几个典型的数据流管理系统，按照实际课题的要求进行设计的。经过改进的 p o w e r s t r e a m 区别于其他d s m s 的特点主要包括：对现实中网速不稳定的问题有着较好 的自适应能力；支持对网速突变的数据流的操作；具有简便的基于内存资源的负载平衡 控制策略。 关键词：数据流；连续查询；数据流管理；功能模块；直方图 大连理工大学硕士学位论文 r e s e a r c ha n dr e al iz a tio no fd a t as t r e a mm a n a g e m e n ts y s t e ma n d i t sc o r r e i a t e da l g o ri t h m s a b s t r a c t t r a d i t i o n a ld a t a b a s em a n a g e m e ms y s t e m sa r ed e s i g n e dt oh a n d l ep e r s i s t e n td a t aa n d a n s w e rt r a n s i e n tq u e r i e s h o w e v e rd u et ot h ee v o l u t i o no fn e t w o r k , t e l e c o m m u n i c a t i o na n d s e n s o rt e c h n o l o g i e s ，an e wd a t ap r o c e s s i n gm o d e lh a sr e c e n t l ya r i s e n i nt h i ss c e n a r i o ， c o n t i n u o u sa n dl o n g - r u n n i n gq u e r i e sa r ep o s e do v e rt r a n s i e n ts t r e a m i n gd a t a t r a d i t i o n a l d b m sa r en o td e s i g n e df o rr a p i da n dc o n t i n u o u s l yl o a d i n go fi n d i v i d u a ld a t ai t e m s ，a n dt h e y d on o td i r e c t l ys u p p o r tt h ec o n t i n u o u sq u e r i e s l i m i t a t i o n so f t r a d i t i o n a ld b m si ns u p p o r t i n g s t r e a m i n ga p p l i c a t i o n sh a v e b e e nr e c o g n i z e d ，p r o m p t i n gr e s e a r c h t o a u g m e n te x i s t i n g t e c h n o l o g i e sa n db u i l dn e ws y s t e m st om a n a g es t r e a m i n gd a t a r e c e n t l yan e wc l a s so fd a t as t r e a m sa p p l i c a t i o n sh a sb e c o m ew i d e l yr e c o g n i z e d ： a p p l i c a t i o n si nw h i c ht h ed a t ai sm u l t i p l e ，c o n t i n u o u s ，q u i c k l yc h a n g e dw i t ht i m e 啦a c c e s s t od a t as t r e a mi sa l s oc o n t i n u o u sa n dm a n y t i m e s ，a n dr e q u i r e so n - t i m er e s p o n s e e x a m p l e so f s u c ha p p l i c a t i o n si n c l u d en e t w o r kt r a f f i cm o n i t o r i n g ，t e l e c o m m u n i c a t i o n sd a t am a n a g e m e n t ， s e n s o rn e t w o r k s a n do t h e r s ，n l ee x p e r i e n c es h o w st h a tt h et r a d i t i o n a lr d b m sc a n n o ts a t i s f y t h ed a t as t r e a ms y s t e m sr e q u i r e m e n t s s oh o wt od e s i g na ne f f e c t i v en e wd a t i v es y s t e mi n o r d e rt op r o c e s sd a t as t r e a m sb e c o m e s 趾o p e nr e s e a r c hp r o b l e m t h e r ea r es o m ei m p r o v e m e n t si ni 忸c o r r e l a t e da l g o r i t h m so ft i l ed a t as t r e a m m a n a g e m e n ts y s t e ma i m e da tt h eu n s t a b l en e t w o r kr a t ei nt h i sp a p e ri no r d e rt oh a v ear a p i d a n dt i m e l yr e s p o n s et ot h et r e a t m e n ta ss p e e dn l a k e sas u d d e ni n c r e a s e t h i sd i s s e r t a t i o na l s o s c h e m eo u tau n i v e r s a ld a t as t r e a mm a n a g e m e n ts y s t e m ，n a m e dp o w e r s t r e a m ，n o to n l yf o r d a t as t r e a m sb u ta l s of o rs t a t i cr e l a t i o n s t o d a yt h e r ei sal i t t l ew o r ka b o u tt h i si no u rc o u n t r y ， a n di tr e f e r st oaf e wc l a s s i cd a t as t r e a mm a n a g e m e n ts y s t e m s 1 1 地i m p o r t a n td i f f e r e n c e b e t w e e np o w e r s t r e a ma n do t h e rd s m s si n c l u d e ：ab e t t e ra d a p t i v ec a p a c i t yt ot m s t e a d i n e s so f t h er e a ls p e e do ft h en e t w o r k ，b e t hd a t as t r e a m sa n ds t a t i cr e l a t i o n sa r et h em a n a g e m e n t o b j e c t so f p h o s p h o r , c o n t i n u o u sq u e r yl a n g u a g ew i t hc o m p r e h e n s i v ew i n d o wt y p e s ，t h en o v e l t e c h n i q u ef o ro r g a n i z i n gd a t as t r e a m si nm e m o r y , t h es t r a t e g yo fl o a ds h e d d i n gb a s e do n m e m o r yr e s o u r c e k e yw o r d s ：d a t as t r e a m ；c o n t i n u o u sq u e r y ；d a t as t r e a mm a n a g e m e n t ；f u n c t i o n a l m o d u l e ；h i s t o g r a m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 降舡蘼 孟 军 力刃年，2 月丛日 大连理工大学硕士学位论文 1 绪论 近三十年来，数据库理论与技术的发展极其迅速，其研究取得了丰硕成果，其应用 日益广泛，时至今日，它几乎无所不在。以三大经典( 层次、网状、关系) 系统为代表的 传统数据库技术对于管理结构简单、操作简单、完全格式和结构化比较稳定的数据己经 证明是很成功的，因而在一些重要但有限的传统商务和管理的事务性应用领域中获得了 普遍而有效的应用。然而，近年来随着信息技术的高速发展，电信数据管理、传感器应 用、网络监控等流式应用陆续出现，而且今后还将继续大量涌现，有发展成为数据库应 用主流的可能，它们已经并将继续对数据库技术提出新的要求与挑战，从而促使了现代 数据流技术的研究与发展。本文将围绕现代数据流管理系统这个主题进行相关的研究和 探讨。本章主要讨论数据流管理系统的研究背景、国内外的研究现状、本文所要研究的 内容以及组织。 1 1 课题研究背景 传统的数据库管理系统用于处理永久的数据和进行瞬时的查询。然而，随着网络、 电信和传感器技术的发展，出现了一种新的数据处理模型。在这种环境中，出现了一种 瞬时流数据上的连续长时间的查询。这样的应用包括：金融报价、网络监控、安全、电 信数据管理、w c b 和交易日志分析、制造业和传感器等。这些应用中，数据以多个高速 数据流的形式到达，并且要求联机的处理以及提供近似实时的查询。 数据流是连续的、随时间变化的、无界的数据项的序列。在数据流模型中，单个的 数据项通常采用关系元组的形式，经过处理后就会被销毁，这就意味着联机流算法是建 立在一次查询的基础上。数据流到达的速率是不被处理系统所控制的，它们是不可预测 和随时间变化的。由于数据流无界性的特点，所以不可能存储整个数据流。 在典型数据流上进行的最重要的一类查询就是连续查询( c o n t i n u o u sq u e r y ) 。这种查 询通常需要持续很长一段时间，随着新数据的到来连续地进行评估，随时间的变化不断 地产生结果。基本的连续查询操作包括选择、投影、t o p k 检测、聚集、多个数据流的 连接等等。 数据流上的另一种重要的查询就是在已经处理的数据和可能销毁的数据上进行即 时( a d h o c ) 查询。 在上面所提到的应用中，简单的把到达的数据放到传统的数据库管理系统( d b m s ) 中进行处理是不可行的。传统的数据库管理系统不适合快速连续的地存储单个数据项， 而且它不直接支持典型数据流应用的连续查询。传统的d b m s 主要是利用固定的查询 数据流管理系统及其相关算法的研究与实现 计划产生精确的结果。另外，数据流上查询计划执行的近似和自适应的特点，以及在快 速数据流上实施的其它处理( 例如，数据分析和挖掘) ，都是传统数据库管理系统不能处 理的。传统的d b m s 在处理数据流应用方面的限制使得人们开始研究如何利用现有的 技术来建造一个新的系统来管理数据流。 1 2 数据流管理系统研究 数据流管理系统的主要研究内容包括：数据流管理系统的体系结构、数据模型、数 据流处理的相关算法、连续查询处理、连续查询语言、数据流挖掘技术、查询优化等。 数据流应用的特征是：数据不宜用持久稳定关系建模，而适宜用瞬态数据流( d a t as t r e a m s ) 建模【1 】。这些应用的实例包括金融服务，网络监控，安全，电信数据管理，w e b 应用， 生产制造，传感检测等等。在这种数据流模型中，单独的数据单元可能是相关的元组 ( t u p l e s ) ，例如网络测量，呼叫记录，网页访问，传感读数等产生的数据。但是，由于这 些数据以大量、快速、时变( 还可能是不可预知的、极大的) 的数据流形式持续到达，由 此产生了一些基础性的新的研究问题。 在现实世界的许多应用中，数据大都是连续的数据流，而不是有限存储的数据集合， 并且与过去的那种单次查询相反，在此用户需要长期连续的查询，例如，网络控制器、 电信数据管理、网络个性化、传感器网络等等。这些应用一方面需要维护大量共享数据 和控制信息；另一方面其应用活动有很强的时间性，要求连续不断地自外部环境采集数 据，并根据要求进行相应的处理及存储，再在规定的时间内做出及时响应。同时，它们 所处理的数据往往是“短暂”的，即只在一定的时间范围内有效，过时则无意义( 对当 前的决策或推导) 。所以这种应用同时需要数据库技术和数据流处理技术两者。但传统 的关系型数据库存储的是静态的关系型数据记录的集合，它们具有限定的大小、可控制 的操作、详细定义的结构，同时这些数据具有持久性。传统数据库中的计算机具有时间 复杂度和空间复杂度，其查询处理为单次查询，查询计划为静态的，且最终生成确定的、 准确的查询结果。另外，传统数据库中的数据除非明确地加入了时间戳的属性，否则没 有时间的概念。因而，传统的商务型和管理事务型数据库管理系统( d b m s ) 不能满足这 种数据库应用的需求。只有将数据库与数据流两者的概念、技术、方法与机制“完善” 地集成在一起的数据流管理系统才能充分满足这中应用的需求。 数据流管理系统就是其数据可以是连续的无界的加入时间概念的数据流，对数据的 处理具有时间限制的数据库系统。系统的正确性不仅依赖于逻辑结果，还依赖于逻辑结 果产生的时间。近年来，随着数据流应用的大量涌现，数据流管理系统的研究已经引起 了越来越多的数据库工作者的关注。然而，数据流管理系统并非是数据库与数据流两者 一2 一 大连理工大学硕士学位论文 的概念、结构、工具等的简单集成，需要对一系列问题进行研究与决策：数据和数据库 的结构与组织；查询语言；事务的优先级分配、调度和并发控制的协议与算法；内存的 分配；查询处理算法；数据以及事务特性的语义以及这种语义与一致性、正确性的关系 等等。这些问题互相关联且与应用的性质紧密相连。 1 3 国内外研究现状 目前国内对数据流管理系统的研究还比较少，且处于初期阶段。文献【2 】讨论了数据 流环境中异常模式的提取和趋势监测，提出了进行异常模式提取的度量框架和相应算 法，然后提出了对于每个异常模式在时间轴上的变化趋势的监测算法。文献【3 5 】各种情 况下对数据流的处理连续查询处理。文献 6 】讨论了多数据流上共享窗口连接查询的 降载策略，结合共享滑动窗口查询操作的调度优化方法和降低负载方法，提出了两种在 b u r s t 环境下提高查询吞吐率的策略：均匀降载策略、小窗口准确降载策略。 对于数据流的研究，北京大学、复旦大学和哈尔滨工业大学已经走在了前列。其中， 北京大学计算机系数据库实验室数据流组研究和开发了一个通用的数据流系统原型阿 耳戈斯( a r g u s ) 。阿耳戈斯既可以作为通用的数据流系统存在，也可以以库的形式提供给 其它系统，方便的嵌入到其它系统中。同时，他们在数据流系统阿耳戈斯上开发了一套 类似于结构化查询语言的流查询语言，通过这套查询语言，可以非常方便的表达数据流 上的查询。 针对目前出现的这种对新型数据进行管理的应用需求，国外的许多大学和机构已在 这方面开展了大量的研究工作，下面介绍国外研制的与数据流管理相关的原型系统及相 关的工作。 斯坦福大学已经开始了一种全面d s m s 的设计和原型实现，该系统为 s t r e a m ( s t a n f o r ds l r e a md a t am a n a g e r ) t ”。s t r e a m 是一个以关系为基础的数据流管理 系统，它重点在于内存管理和近似查询。它可以用于处理快速的、易变的、大量涌入的 数据流信息，其连续查询能力非常好。s t r e a m 的主要处理技术包括：连续的自我监 控和再优化；适应于不同需要的良好近似；合理的资源分配和使用。如今s n 也蜥1 0 版本已经设计完成并正在运行期间，它可以支持多种查询语言。 布朗大学、布兰代斯大学和麻省理工大学联合开发的a u r o r a 【8 】系统正在构建一个新 型的数据处理系统，它的目标是专门处理数据流监控。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 系统术语) 中的一个。对每一个使用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 ，叫做a u r o r a * 。a u r o r a * 的主要目标在于使系统对分布式数据流处理应用达到 一种比较高的可量测性和实用性。 美国加州大学伯克利分校正在构建一个t e l e g r a p h c q 唧系统，该系统用于连续的数 据流的处理。t e l e g r a p h c q 的目的在于处理对大量高速变化的数据流而进行的大量连续 查询流。在该项目的早期工作中0 0 q 2 已经建立了一个j a v a 版本的适应性数据流处理系 统。如今他们决定利用p o s t g r e s q l t u l ( 一个源码公开的r d b m s ) 作为进一步的研究的起 点。o p e n c q t l 4 】系统与n i a g a r a c q i ”】系统都支持对分布于网络上的持久性数据进行连续 的查询监控，如i n t e m e t 上的w e b 站点。o p e n c q 采用一种基于增量视图维护的查询处 理方法，而n i a g a r a c q 则在许多查询中使用了分组连续查询技术，该技术的使用提高了 查询求值的效率。 另外，连续查询还被用于t a p e s t r y l l 6 l 系统，该系统对只增型电子邮件信息和电子公 告信息数据库进行以内容为基础的过滤。s q l 的一个有限的子集作为该系统的查询语 言，以确保查询求值的有效执行以及生成只增型查询结果。a l e r t 系统【1 7 通过使用定义 在特殊的只增型的活跃库表上的连续查询，提供一种传统s q l 数据库中的事件一条件 一动作触发器机制。基于内容的x f i l t e r 过滤系统以用户的角度利用x p a t h 语言进行连续 查询，从而实现了对x m l 文档的有效过滤。c o u g a r 1 8 1 是一个传感器数据库，它将传 感器建模为a d t s ，同时它的输入为一个时间序列。g i g a s e o p e t l 9 】是一个分布式网络监控 结构，它提议将一些查询操作加到数据源中( 如：路由) 。s t a t s t r e a m 2 0 】是一个流监控系统， 它在于同时在线统计几个数据流。 - 4 - 大连理工大学硕士学位论文 2 数据流概述 本章介绍了数据流的基本概念，列举了数据流相关的一些应用，在此基础上，重点 讨论了数据流查询的相关问题和处理技术。 2 1 数据流 数据流是一个实时的、连续的、潜在无界的、有序的( 聪含的通过到达时间或者明 确的时间戳) 项的序列。 因特网、w e b 以及传感器网络等已经促使应用将数据看作一种连续的数据流，而不 是固定的数据集合。电话记录，股票报价以及从传感器那里得出的数据都是数据流的例 子。由此可见，数据流是连续的、无限的、快速的、随时闯变化的数据项的序列。 与传统的数据相比，数据流具有许多自己的特点：它是大量的连续的、无限的数据； 数据变化很快，并且要求快速即时的响应；数据流能很好地满足我们现在数据处理的需 要；仅仅存储到目前为止的现有数据；大多数数据流初始时处于相当低层次或者多维状 态，需要多层次化和多维化处理。 2 2 数据流模型 实时的数据流是一个以某种顺序到达的数据项的序列，可能只会被访问一次。既然 数据项可能是高速到达的，那么数据流就可以采用元组链表的模型。单个数据项可能是 一个关系元组，也可能是一个对象实例。在基于关系的模型中，数据项是存储在虚拟关 系中的瞬时元组。在基于对象的模型中，数据源和数据项采用的是与方法相关联的数据 类型的模型。 在数据流模型中，一些或者所有输入数据的操作都是建立在一个或多个连续到达的 数据流的基础上，而不是在硬盘或者内存上。数据流和传统的存储关系有以下的不同： ( 1 ) 数据流中的元素是联机到达的。 ( 2 ) 系统不能控制数据元素到达的顺序。 ( 3 ) 数据流是潜在无限的。 ( 4 ) 一旦数据流的一个元素被处理之后，就会被丢弃或者存档：除非明确地把数据存 储在内存中，否则很难再次被检索，相对于数据流的大小来说，内存是相对较小的。 ( 5 ) 数据流模型上的操作对象也包括存储在关系上的数据。通常，数据流查询是在数 据流和存储的关系数据上进行的。 数据流管理系统及其相关算法的研究与实现 2 3 数据流的应用 下面介绍一些数据流的相关应用，以便于了解数据流管理系统应该支持的查询。 ( 1 ) 传感器网络 传感器网络可以用在拥有复杂过滤和对异常情况进行响应的不同的监测应用中。在 多数据源上分析数据需要在多个流上进行聚集和连接操作。 ( 2 ) 网络流量监控 在计算流量统计和发现紧急状况( 比如，拥塞和拒绝服务) 的应用中已经使用即席系 统来进行近似实时的i n t e r a c t 流量分析。i n t e r n e t 的流量模式被认为遵从幂律分布，也就 是说网络的大部分宽带资源是被一小部分的用户所占用，所以监测流行的资源和终端地 址是特别重要的。 ( 3 ) 金融报价器 联机的分析股票价格包括发现相关信息，确定趋势和套得的机会以及预测未来的走 势。 ( 4 ) 交易日志分析 联机地挖掘w e b 日志、通话记录和自动取款机等都符合数据流的模型。其目的是 发现消费者有趣的行为模式，识别可能具有欺诈和可疑的消费行为并预测未来的数据 值。 2 4 需求分析 前面的例子说明了它们在数据模型和应用上的基本操作( 由于工作量的特点，比如， 在数据流到达的速率或者需要历史数据的数量上还有些不同) 有着很大的相似。下面列 出了数据流上的基本连续查询操作，由于需要的变化，将来还可能会有其它的操作： ( 1 ) 选择：所有的数据流应用都需要支持复杂的过滤功能。 ( 2 ) 嵌套的聚集：复杂的聚集操作，包括需要计算数据趋势的嵌套聚集。 ( 3 ) 多路技术和多路分解；分别跟g r o u p - b y 和u n i o n 类似，用来分解和合并逻辑数据 流。 ( 4 ) 频繁数据查询：就是依赖于定点( c u t o f f ) 状态的t o p - k 或者阈值查询。数据流挖掘： 模式匹配，查找相似，预测等等。 ( 5 ) 连接：包括多数据流的连接和数据流跟静态关系数据的连接。 ( 6 ) 窗口查询( w i n d o w e dq u e r i e s ) ：上面所有的查询类型可能会限制在一个窗口中返 回数据( 例如，最近2 4 小时或最近1 0 0 个包) 。 一6 一 大连理工大学硕士学位论文 2 5 数据流查询 连续数据流上的查询跟传统数据库管理系统中的查询有很多共同点。然而，它们之 间存在两含特有的区别：一个区别是一次查询和连续查询。一次查询( 一类包含传统 d b m s 的查询) 是实施在数据集快照上的查询，结果返回给用户。而连续查询是数据流 连续到达的过程中进行连续求值的。连续查询的结果是随时间产生的，通常反映的是到 目前为止的流数据。连续查询结果可能被存储或随新数据的到达进行更新，或者作为数 据流产生。 第二个区别是预定义查询和即席查询。预定义查询是一类在任何相关数据到来之前 在数据流管理系统已经定义的查询。预定义的查询通常产生连续的查询。即席查询也包 括已经开始的数据流的联机情况。即席查询为一次查询或连续查询。由于即席查询不能 事先知道查询优化的目的以及确定查询间共同子表达式的情况，所以使得数据流管理系 统的设计变得更加复杂。更重要的是，即席套询的准确结果需要参考数据流的历史数据。 数据流模型上的查询处理有它独特的难题。下面，我们讨论这些难题的几个最主要 的方面，并给出解决它们的几个可选方法。 2 5 1 无界的内存需求 既然数据流的大小是潜在无限的，那么计算一个准确的数据流查询的结果所需的内 存数量也是无限增长的。数据集处理的外存算法比内存算法研究的多，因为外存算法不 能有效地支持连续查询，所以它不适于数据流的应用，另外它的实时响应时间通常比较 慢。连续数据流模型适合那些对实时响应要求比较高，并且速率随时间高速变化、数据 量产生比较大的应用。新数据是连续到达的，甚至在旧数据还没有处理完，它就达到了； 每个元素的处理时问要尽可能的短，否则计算的执行霎时间将会很高，这样系统的处理 就不能跟数据流同步。 a r a s u 【2 l j 等在应用有限的内存空间得到准确的结果和利用磁盘访问得到近似结果之 间的区别上做了初步的研究。他们主要考虑那些具有潜在无限的内存需求( 跟输入数据 流的大小是成比例的) 的有限查询。其研究结果表明：在不知道输入数据流大小的情况 下，对于诸如连接的大多数普通查询，除非查询所涉及的属性的域有限，否则是不可能 在内存中分配一个有限空间的。一个基本的直觉知识就是没有域的限制，因为它们有可 能与将来到达的数据进行连接操作，所以必须存储无限数量的属性值。 2 5 2 近似结果 正如前面所说的，当局限于有限的内存时，并不是总能产生准确的查询结果，然而， 取代准确结果的高质量的近似结果也是可以接受的。定义在数据流上的近似算法的难题 数据流管理系统及其相关算法的研究与实现 近年来在算法界的研究已经富有成效，这项工作导致了一些为了数据简化和大纲构造的 一些概括的技术，包括草图( s k e t c h e s 【2 2 0 3 1 ) ，随机抽样( r a n d o ms a m p l i n g t 2 4 , 2 5 1 ) ，直方图 ( h i s t o g r a m s 2 6 a t l ) ，和小波( w a v e l e t s 2 8 , 2 9 1 ) 。根据这些概括技术，我们已经看到在近似查 询结果方面所做的一些工作。例如近来的工作除了基于直方图的技术来进行数据流上相 关关系的聚集查询的近似结果外，g i l b e r t l 3 0 】等还提出了一个在数据流上建立小空间概要 的通用技术，以提供很多类似聚集查询的近似结果。下面的两个小节，将介绍几个近似 的方法，其中有些是数据流计算所特有的。 2 5 3 滑动窗口 一种产生数据流查询的近似结果的技术就是通过滑动窗口在最近数据而不是在整 个历史数据上进行查询评估。例如，仅用最近一个星期的数据来产生查询结果，这个星 期以前的数据将会被丢弃。 在数据流上实施滑动窗口是近似的一个很自然的方法。它是定义良好且容易理解 的，更重要的是，它着重于最近的数据，在大多数现实应用中，相对于历史数据，最近 数据更加重要：如果一个人想实时地搞清楚网络流量模式，或电话记录或交易记录，或 科学传感数据，那么观察最近数据比观察陈旧的历史数据更具有参考价值。事实上，很 多类似的应用中，滑动窗口并不是作为由于计算整个历史数据的不可行性而引入的一种 近似技术，而是用户查询的一种查询语义。 在如何于数据流上应用滑动窗口的问题上还存在很多有待于研究的问题。首先一个 基本的问题就是如何在数据流上定义时间戳以便更容易使用窗口。滑动窗口查询的实现 和它们的优化是一个有待于研究的领域。如果滑动窗口大的足够存储窗口的整个内容， 则将无法在内存中缓冲。还有一个问题就是如何设计一个利用有限的内存得到近似结果 的算法，在文献 3 1 ，3 2 中可以找到一些最近的研究成果。 然而，在传统数据库环境上的序列( s e q u e n c e ) 和时序( t e m p o r a l ) 数据库已经存在很多 时间敏感的查询( 一类含有滑动窗口的查询) ，数据流计算模型的不同特点提出了一些新 的挑战。时序数据库研究的主要是随时地维护整个历史的数据值，而数据流系统主要关 心的是实时地处理新的数据元素。序列数据库试图产生允许流访问的查询计划，这意味 着单次扫描输入数据的评估计划是可行的，而且计划评估所需的内存数量是不变的。这 种模型假设数据库系统能够控制处理元组的顺序，它可以合并多个序列，而在数据流系 统中这是不可能的。 大连理工大学硕士学位论文 2 5 4 批处理、抽样和大纲 另一类产生近似结果的技术用某种抽样和批处理来加速查询执行，而不是随数据的 到达处理每一个数据元素。我们描述这些技术的一个总的框架。假设数据流查询的结果 采用的是一种可以增量维护的数据结构。这种数据结构的最主要的特征就是支持两个操 作，更新和计算结果。更新操作是在每个新元素到达的时候被调用来更新这个数据结构 的，计算结果产生新的查询结果或者更新某查询的结果。处理连续查询的时候，最好的 情况就是相对于数据流数据到达的速率来说，这两个操作都是很快的。这种情况下，不 需要使用与数据流同步和实时的产生结果的特殊技术：当每个新数据到达的时候，更新 数据结构，根据数据结构计算出新的结果，这些都少于数据元素到达的时间。如果数据 结构的一个或两个操作比较慢的话，那么就不可能连续产生目前为止的准确结果。我们 考虑这两个可能的瓶颈和处理它们的方法。 ( 1 ) 批处理 第一种情况是更新操作快，计算结果操作慢。这样，一个自然的解决方法就是对数 据进行批处理。新数据到来的时候，不是立刻更新结果，而是缓存起来，查询的响应是 周期性的。因为查询结果不是及时产生的，所以可以认为是近似的，也就是说它表示的 是最近的那一点的准确结果而不是当前时刻的准确结果。由于没有引起准确结果的不确 定性和降低实时性，批处理是一种很有效的近似方法。当数据流爆发时，它是一个很好 地处理方法。一个算法即使不能与数据流速率的峰值同步，但是可以通过缓存来有效地 处理数据流。 ( 2 ) 抽样 另外一种情况就是，计算结果操作快，更新操作慢( 处理时间超过数据元素平均的 到达时间) 。因为数据到达的速度比系统处理的速度快，所以在计算时获得整个数据是 没有用的。一些元组必须被完全的忽略掉，这种查询的执行是在数据流的样本而不是整 个数据流上。这样我们得到的是近似的结果，但是某些情况，抽样处理可能会带来某种 程度的错误。不幸的是，多数情况下( 包括含有连接的多数查询) ，基于抽样的方法不能 提供可行的近似保证。设计一个被证明与准确结果接近的基于抽样的算法是研究中的一 个活跃的领域。 ( 3 ) 大纲数据结构 很明显，我们期望更新和计算结果都很快的数据结构。对于那些想要的属性上没有 准确数据结构的数据流查询来说，可以设计一个维护小的大纲或者概要的近似的数据结 构来代替准确的表示，这样就可以使每个元素的计算量达到最小。通过大纲数据结构实 施数据约减代替批处理或抽样是一个与数据流模型有关的富有成果的研究领域。 数据流管理系统及其相关算法的研究与实现 2 5 5 块操作 块操作就是那些只有获得整个输入才能产生输出的操作。排序就是块操作的一个例 子，还有一些聚集的操作如s u m 、c o u n t 、m i n 、m a x 和a v g 。如果想用传统的操作树进 行连续查询求值的话，数据流进入叶子节点，最终的查询结果在根节点产生，这样把块 操作合并到查询树就带来一些问题。因为数据流可能是无限的，一个块操作的一个输入 是数据流，它将永远得不到整个输入，这样也永远不能产生任何输出。很明显，块操作 不太适合数据流的计算模型，但是聚集操作是非常普遍的，而且排序的数据比未排序的 数据处理起来更有效率。处理这些块操作是比较困难的，如何有效地处理它们是数据流 计算的一个很有挑战性的方面。 块操作作为查询操作的根节点要比作为内部节点，更容易处理，例如，产生中间结 果输入给其它操作进行进一步处理。当有一个聚集查询在查询树的根部时，如果这个操 作产生一个或少数几个值的话，那么结果的更新能随它们的输入被流出。当结果集很大， 产生的是一个排序了的关系时，由于连续地转发整个结果是很麻烦的，所以维护到现在 为止的结果的数据结构是更有实际意义的。这两个方法都不能使块操作很好地产生中间 结果，然而，主要的问题是块操作产生的结果可能是连续变化的，直到获得所有的数据 为止，所以与这些结构相关的操作不能根据查询执行中间阶段的结果做出可靠的决定。 一个处理查询树中块操作作为内部节点的方法就是用模拟近似的同样任务的非块 操作代替。这个方法的一个例子就是j u g g l e 【3 3 愫作，这是一个排序的非块操作版本。一 个有趣的开放难题就是如何把这项工作扩展到其它类型的块操作上，以及如何量化由非 块操作产生的近似块操作的错误。 t u c k e r 3 4 1 等已经提出了一个处理块操作的不同方法。他们建议在数据流上增加一个 断言，用于判断哪些能和哪些不能出现在数据流的剩余部分。这个断言，叫做 p t m c t u a t i o n s ，被数据流的数据元素交叉存取。 2 5 6 参考历史数据的查询 在数据流计算模型中，一旦数据元素已经流过的话，就不会被再一次访问到。这就 意味着对那些与已经丢弃的数据有关的即席查询来说，要得到一个准确的结果是不可能 的。解决这个问题的一个简单的方法就是规定即席查询只能参考将来的数据：它们是在 查询开始的时候对数据流进行求值的，任何过去的流元素都被忽略( 为了查询的目的) 。 然而这种方法可能不会令人满意，但是可以被很多应用所接受。 一个更好地处理参考历史数据的方法就是维护数据流上的概要，这可以使未来的即 席查询得到近似的结果。采用这个方法需要提前决定用最好的方式来使用内存资源为广 大连理工大学硕士学位论文 阔范围的未来查询提供近似的结果。这个问题与物理数据库设计的一些问题，如索引的 选择和视图的物化有些相似。然而，它们有很大的不同：在传统的数据库系统中，在没 有索引或视图的情况下，有可能去访问底层的关系，这样就增加了代价。在数据流计算 模型中，如果没有近似的概要结构，就没有可用的资源。 即使即席查询声明仅适合将来数据，仍然有很多诸如如何更好地处理数据的课题需 要研究。在数据流应用中，大部分查询是长时间的连续查询，而不是短暂的一次查询， 多查询优化带来的效益要比传统的数据要多。即席查询的出现把为查询找到最好的查询 计划从脱机问题转移成联机问题。即席查询引起了查询计划的自适应性问题。 数据流管理系统及其相关算法的研究与实现 3 数据流管理系统体系结构设计 为了满足数据流研究和应用的需求，在斯坦福大学研究的s t r e a m 的基础上，设 计了一个通用的数据流管理系统p o w e r s t r c a m 。它是根据数据流应用的特点设计的，用 于处理数据流上的连续查询和即席查询。本章讨论了p o w e r s t r e a m 系统的设计，给出了 p o w e r s i r e a m 的体系结构，并且对系统主要模块的功能进行了说明。 3 1d s m s ( d a t as t r e a mm a n a g e m e n ts y s t e m ) 数据流是一个实时的、连续的、潜在无界的、有序的( 隐含的通过到达时间或者明 确的时问戳) 项的序列。数据流的项通常采用关系元组的形式。 数据流管理系统( d s m s ) 跟传统的数据库系统在功能上和性能上是相似的，它允许 一些或者所有的数据以连续的数据流形式到达。如果把数据集看作一个特殊的数据流， 可以把数据流管理系统定义为传统数据库系统的扩展。 d s m s 增加了数据流的两个基本查询：连续查询和即席查询。 3 1 1d s m s 与d b m s 的不同 首先了解一下d s m s 与d b m s 有哪些不同： ( 1 ) 传统的d b m s 采用的是被动模式，大部分的数据处理的要求来自于用户提出的 事务和查询。d s m s 还需要一些主动的方法。例如监测数据的流入并对异常的情况做出 处理。 ( 2 ) 传统的d b m s 普遍地在它的表中管理数据。d s m s 通常需要通过一些有界的窗 口处理有限的数据，两不是在过去无限的范围内处理。 ( 3 ) 传统d b m s 提供的是基于精确查询上的精确结果，而且没有实时的限制。d s m s 通常需要实时的响应( 例如，监测敌人位置的军事应用) ，而且一般要提供合理的近似查 询结果。 ( 4 ) 传统的查询处理器以统一方式( 典型的集中在响应时间) 优化所有的查询。流数据 管理通常要满足特殊应用的优化标准( q o s ) 。 ( 5 ) 传统d b m s 的是基于p u l l 的查询处理标准。基于p u s h 的数据处理是d s m s 的处 理标准。 3 1 2d s m s 的基本需求 数据流独特的特点和连续查询使得d s m s 有以下的需求： 大连理工大学硕士学位论文 ( 1 ) 数据模型和查询语义必须允许基于顺序的和基于时间的操作( 例如，在5 分钟的 滑动窗口上的查询1 。 ( 2 ) d a 于无法存储整个数据流，所以可能要使用近似的摘要结构。这样，在摘要上的 查询可能就返回不了精确的结果。 ( 3 ) 数据流查询计划不能使用块操作，因为这些操作需要在产生结果之前获得所有的 输入。 ( 4 ) 由于性能和存储的限制，无法对数据流进行再次访问。联机的流算法是基于一遍 扫描的。 ( 5 ) 监测流的应用必须对异常的数据做出快速的反应。 ( 6 ) 长期运行的查询在它们执行期可能会遇到系统状态变化的情况( 例如，流速率的 变化1 。 ( 7 ) 许多连续的查询的共享执行必须保证可测量性。 3 1 3d s m s 的参考结构 图3 1 【3 5 1 是数据流管理系统的一个参考的抽象结构。 更新静态 用户查询 数据 图3 1 数据流管理系统参考结构图 f i g 3 1r e f e r e n c es t r u c t t t r ef i g u r eo f d s m s = 冷 数据流出 输入监听器可以通过诸如抽样的方法控制数据输入的流量。数据存储通常分为三个 部分：临时工作区( 用于窗l ：3 查询) ，流大纲的概要存储，元数据的静态存储( 每个数据源 数据流管理系统及其相关算法的研究与实现 的物理位置等信息1 。查询库存储的是系统已经注册的连续查询，这些查询可以用作共 享处理。除了连续查询，当前数据流状态上