（计算机应用技术专业论文）分布式数据流自适应查询处理技术研究.pdf

五邑大学硕士学位论文 捅斐 随着网络技术的发展，越来越多的数据正以数据流的形式存在于各种各样的网 络系统中。数据流的特点是数据不是永久储存在传统数据库中的静态数据，而是瞬 时处理的源源不断的连续数据流。因此，作为这种新型数据模型的处理应用也逐渐 引起了相关领域研究人员的广泛关注。 在大量的数据流应用系统中，数据流是来自分布于地理上不同位置的数据源， 非常适合分布式查询处理。分布式处理是数据流管理系统发展的必然趋势。而查询 处理技术是数据流处理中的关键技术之一。在数据流应用系统中，系统的运行环境 和数据流本身的一些特征不断地发生变化，因此，对分布式数据流自适应查询处理 技术的研究成为了数据流查询处理技术研究的热门领域之一。 首先，对分布式数据流查询处理模型和现有的分布式数据流查询操作放置技术 进行了详细的介绍。在深入研究和分析分布式数据流查询处理结构的基础上，提出 了分布式数据流查询操作贪心放置算法，并通过实验验证了该算法的执行性能。 其次，对数据流中适应性查询处理技术进行了深入研究。针对查询中不同类型 的查询操作符，根据动态查询选择率，给出不同的白适应查询优化机制，有效地减少 了查询“阻塞 的现象，提高了查询性能，更好地满足了查询需求，并通过实验验 证了相关算法的性能。 最后，针对如何管理好大量并行执行的连续查询、提高查询系统的执行性能以 及节省系统资源这个分布式数据流查询的核心问题，给出了分布式数据流查询处理 过程模型，并研究了多连续查询中的查询操作重叠的问题。在深入分析了现有的查 询重用算法存在的不足后，提出了一个基于查询操作表的分布式数据流查询重用算 法，并通过实验验证算法性能。 关键词：分布式数据流；查询操作；查询放置；自适应查询；查询重用 五邑大学硕士学位论文 a bs t r a c t r e c e n t l y , a st h er a p i de v o l u t i o no ft h en e t w o r kt e c h n o l o g y , an e wc l a s so fd a t a i n t e n s i v e a p p l i c a t i o n sh a sb e e nw 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 o d e l e db e s tn o ta sp e r s i s t r e l a t i o nb u tr a t h e ra st r a n s i e n td a t as t r e a m s t h ec h a r a c t e ro ft h ed a t as t r e a mi st r a n s i e n t l y , m u l t i p l e ， u n b o u n d e da n dc o n t i n u o u s l y t h ed a t as t r e a mp r o c e s s i n gt e c h n o l o g yb e c o m e san e wa n dp o p u l a r t o p i ci nd a t a b a s er e s e a r c ha r e a i nl a r g en u m b e r so fd a t as t r e a ma p p l i c a t i o ns y s t e m s ，t h ed a t as t r e a m sa r ed i s t r i b u t e di n g e o g r a p h i c a h y ，s od a t as t r e a ms y s t e m sa r ev e r ys u i t a b l ef o rd i s t r i b u t e dp r o c e s s i n g d i s t r i b u t e d p r o c e s s i n gi sn e c e s s a r i l ya n dt h eq u e r yp r o c e s s i n gt e c h n o l o g yi so n eo fp i v o t a lt e c h n o l o g i e s b e c a u s e o ft h ed a t as t r e a ms y s t e m sp a r a m e t e r sc h a n g e dc o n s t a n t l y , t h et e c h n o l o g yo fd i s t r i b u t e dd a t as t r e a m s e l f - a d a p t i n gq u e r yp r o c e s s i n gb e c o m e so n eo fp o p u l a ra r e ai nd a t as t r e a mr e s e a r c ha r e a f i r s t l y , t h ed i s t r i b u t e dd a t as t r e a mq u e r yp r o c e s s i n gm o d e lc o n c e p ta n dt h ee x i s t i n gq u e r y o p e r a t o rp l a c e m e n to fd i s t r i b u t e dd a t at e c h n o l o g ya r ei n t r o d u c e di nd e t a i l o nt h ef o u n d a t i o no f a n a l y z i n gt h es t r u c t u r eo fd i s t r i b u t e dd a t as t r e a mq u e r yp r o c e s s i n g ，w ep r o p o s ead i s t r i b u t e dd a t a s t r e a m q u e r yo p e r a t o r sp l a c i n gg r e e d ya l g o r i t h m a n de x p e r i m e n t a l r e s u l t ss h o wt h a tt h e p e r f o r m a n c eo ft h i sa l g o r i t h mi se f f e c t i v e l y s e c o n d l y , i n v e s t i g a t ed e e p l yi nd a t as t r e a ms e l f - a d a p t i n gq u e r yp r o c e s s i n gt e c h n o l o g y w eo f f e r d i f f e r e n to p t i m i z e dm e t h o d so fs e l f - a d a p t i n gq u e r yp r o c e s s i n gf o rd i f f e r e n tk i n d so fq u e r yo p e r a t o r s ， a n dt h e s em e t h o d sa r eb a s e do nd y n a m i cq u e r ys e l e c t i v i t y t h eo p t i m i z e dm e t h o d sr e d u c i n gt h ec a s e o fb l o c k i n ge f f e c t i v e l y , i n c r e a s i n gq u e r yp r o c e s s i n g sp e r f o r m a n c ea n ds a t i s f y i n gt h ea p p l i c a t i o n r e q u i r e m e n tb e t t e r v e r i f yt h ep e r f o r m a n c eo fa l g o r i t h m sb yd o i n ge x p e r i m e n t s f i n a l l y , t h ep a p e rg i v et h em o d e lo fd i s t r i b u t e dd a t as t r e a mq u e r yp r o c e s s i n g h o wt om a n a g ea l a r g en u m b e r so fp a r a l l e lc o n t i n u o u sq u e r i e s ，i n c r e a s et h ep e r f o r m a n c eo fq u e r ys y s t e ma n ds a v e s y s t e mr e s o u r c eb e c o m e so n eo ft h ek e yp r o b l e m si nd i s t r i b u t e dd a t as t r e a mq u e r yt e c h n o l o g ya r e a a f t e rs t u d i e dt h eq u e r yo p e r a t e so v e r l a p p i n gp r o b l e mi nm u l t i - c o n t i n u o u sq u e r i e s ，t h ep a p e ro f f e ra d i s t r i b u t e dd a t as t r e a mq u e r yr e u s ea l g o r i t h mw h i c hi sb a s e do naq u e r yo p e r a t et a b l e t e e a l g o r i t h m sp e r f o r m a n c ei sb e t t e rt h a nt h ee x i s t i n ga l g o r i t h m s k e yw o r d s ：d i s t r i b u t e dd a t as t r e a m ；q u e r yo p e r a t e ；q u e r yp l a c i n g ；s e l f - a d a p t i n gq u e r y ；q u e r yr e u s e 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成，完成论文所用的 一切资料均已在参考文献中列出。 作者：潘谷 签字荔冬 2 0 0 8 年4 月1 5 日 五邑大学硕士学位论文 1 1 课题研究背景 第一章绪论弟一早珀下匕 近年来，一种新型的数据模型的处理应用逐渐引起了相关领域研究人员的广泛 关注。这种数据应用的特点是数据不是永久储存在传统数据库中的静态数据，而是 瞬时处理的源源不断的连续数据流。这样的数据流应用领域范围相当广泛，例如， 大型仓储式超市商品交易即时分析、网络监测、电信数据处理、安全监控系统、金 融证券信息即时分析处理、传感器网络和w e b 日志分析等。 数据流是实时的、连续的、有序的项的序列，且数据流是由到达时间隐含表示 或者由时间戳显式指定，并按照数据项到达的顺序加以控制。数据流到达的频率不 能被处理系统所控制，它们是不可预测和随时间变化的。由于数据流源源不断的到 达的这种无界性特点，完整地将数据流实时存储到传统的数据库管理系统中，并在 其中进行操作是不可行的。 数据流上的查询是长期的连续查询( c o n t i n u o u sq u e r y ) ，即在规定的时间内连 续运行，不断给用户返回所需的查询结果。传统的数据库管理系统中的查询是一次 查询( o n e t i m eq u e r y ) 。显然，把持续到达的数据流简单地放到传统d b 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 ) 的研究开 发工作应运而生，以便克服传统数据库管理系统的不足，满足对上述数据流数据处 理的需要。 1 1 1 数据流管理系统查询应用举例 例1 ：电信行业通话记录信息数据管理 移动公司每时每刻都会采集用户的通话记录，这些通话记录信息数据包含若干 属性，如主叫号码，被叫号码，通话时间，收费金额等属性。大量的通话记录以时 间顺序排序，汇集到移动公司的数据中心，可抽象看成是通话记录信息“流。若移 动公司想查询目前系统中通话时间超过5 分钟且收费金额超过2 元的通话记录数据 信息，则这个查询可以由以下查询语句表示： 五邑大学硕士学位论文 s e l e c i 謇 f r o m 通话记录 w h e r e 通话记录的通话时间 5 分钟a n d 通话记录的收费金额 2 元； 显然，这个查询包含了通话记录数据流的两个选择操作。 例2 ：传感器网络数据管理 传感器网络能够协同地实时监测、感知和采集网络分布区域内各种环境或监测 对象的信息，并对这些信息进行处理，获得详尽而准确的信息，传送到需要这些信 息的用户。传感器网络可以被广泛用于环境监测、交通管理和制造业等领域。假设 在一个仓库内通过多个传感器监控实时的温度情况，当平均温度超出一定的范围则 采取一系列措施，显然监控的温度数据每时每刻都有，并源源不断地“流 入系统 中处理，系统必须一直不间断的查询仓库内的平均温度。 例3 ：股票行情分析 股票交易所的股票信息也是数据流数据应用的一种。例如，股票成交量在线分 析和股票价格在线分析等都涉及到数据流数据。这些股票在线分析系统可以用来识 别趋势，套汇时机和未来价格预测等。典型的股票查询如查询最近成交量震荡的最 高变更率；查找所有价格在2 0 元一1 0 0 元的股票；哪些股票在最近的1 小时内在最 高标记和最低标记之间并大于最后价格的2 ；哪些股票最近5 分钟内平均成交量以 3 0 0 的幅度震荡。 1 i 2d b m s 与d s m s 的区别 d b m s 处理的数据模型与d s m s 处理的数据流数据模型有很大的区别，因此d b m s 和d s m s 两个系统也有很大区别，其主要区别如表1 - 1 所示。 虽然数据流管理系统与数据库管理系统有着很大的不同，但d s m s 也沿用了很多 传统数据库、数据仓库和数据挖掘的概念和原理。例如，d b m s 中的触发器、物化视 图等概念，主存数据库，分布式数据库，实时数据库，适应的、在线和部分结果等 处理方式。 i i 3 面临的挑战 数据流管理系统是新兴的研究领域，很多技术、机制和原理尚处于研究发展阶 段，因此在很多方面都会面临一些挑战性的问题。这里仅说明几个主要的问题。 2 五邑大学硕士学位论文 表卜1d b m s 与d s m s 比较 ( 1 ) 数据流模型的研究 建立数据模型是数据管理和分析的基础，数据流是由有序的元组或者对象组成 的序列，数据流不同于传统的关系模型，其主要特点有如下几个方面： 数据流中的元素在线式到达； 频繁的变化和快速的响应； 系统无法控制将要处理的新到达的数据元素的顺序，无论这些数据元素是在 一个数据流中还是跨多个数据流； 数据流的潜在大小也许是无穷无尽的，而瞬时存储空间是有限的； 一旦数据流中的某个元素经过处理，要么被丢弃，要么被归档存储。因此， 除非该数据被直接存储在内存中，否则不容易被检索。 根据以上特点，数据流模型应该能够解决下面两个问题：1 用有限来表示无限。 同时处理大量数据是不可能的，处理无限的数据更是不可能，所以应该采取一种把 无限数据集映射到有限数据集的方式进行处理。2 能够增量式的维护。在有限的主 存中维持一定数量的数据单元，根据一定的更新机制，进行实时的更新和维护。 3 五邑大学硕士学位论文 ( 2 ) 存储空间的影响和近似性处理 由于数据流潜在的无界性，数据存储的问题就成为了数据流管理中的一个重要 问题。在数据流上计算精确的结果所需要的空间可能是无限增长的，因此，现存的 一些算法是不适合数据流应用的。在数据流应用中，实时性也是非常重要的一个方 面，在先前到达的数据被处理的时候，新的数据还会随时到达一这就要求数据流中 的每个元素的处理时间是很短的，如果处理算法不能跟上数据流的更新速度，则数 据处理的延迟就会很大。因此利用外部存储的解决方法是不适合的。通常的做法是 把数据保存在有限的主存空间中。 与此同时，需要考虑的另外一个问题就是数据处理的精确性问题。对于部分查 询来说，在有限的存储空间中是能够得到准确结果的。但是对于一些查询，如果事 先不知道输入数据流的大小，在一定的存储空间中得到精确的结果是不可能的。所 幸的是，对于大多数的数据流应用，高质量的近似结果是可以接受的。因此，数据 流处理的近似方法成为了研究的重点，同时也是众多研究者所关注的热点问题，提 出了很多有效的解决方法，其中涉及到的技术有很多，特别是可以生成摘要数据结 构的摘要技术，而摘要数据结构的特点则是以小数据集来很好地表示大数据集的轮 廓。例如，草图( s k e t c h e s ) 技术、随机采样( r a n d o ms a m p l i n g ) 技术、直方图 ( h i s t o g r a m s ) 技术和小波( w a v e l e t s ) 技术等等。基于这些摘要技术，我们可以 处理相应的数据流的近似查询问题。 ( 3 ) 数据流的波动性和适应性调节 数据流到达的不可控制性决定了数据流的不稳定性，使得数据处理变得复杂化， 因此在数据流处理过程中需要重点考虑数据的波动性的影响。波动性主要体现在两 个方面，一是数据量的波动性，由于数据流中元素的到达是不可预测的，未来到达 的数据量也是无法预知的，数据量的波动是实际应用中经常遇到的情况；另一个是 更新速率的波动性，数据更新的速率也是不可控的。因此，如何适应不同速率的数 据流也是数据流管理的重点问题之一。 数据流的波动性对数据流管理的影响是很明显的，为了消除这些影响需要采取 一些处理机制。从上面的介绍可以看出，数据流查询处理是带有一定近似性的，因 此，适应性调节应该与近似性结合起来，当检测到流入数据的波动性超过一定程度， 则应该对近似摘要数据结构进行相应的调节，保证处理的正常进行。其中涉及两个 方面的难点，即波动性的检测方法和适应性的调节方法。 4 五邑大学硕士学位论文 ( 4 ) 块查询操作在数据流上的实现 块查询操作( b l o c k i n gq u e r yo p e r a t o r ) 是指那些只有得到所有输入后才能得 出查询结果的查询。排序就是典型的块操作，此外，还有一些集合性操作，例如s u m 、 c o u n t 、m i n 、m a x 、a v g 等等，这些操作都不适合数据流模型，因为数据流是无限的。 如果用传统的查询操作树来表示数据流的连续查询，则块操作是不能插入到树 结构中的。块操作把一个数据流作为输入，是无法得到整个输入集合的，也就无法 产生最终的结果。但是，排序和集合性查询在实际应用中是常见的。如何有效解决 这个问题是数据流计算中一个重要的挑战性问题。 ( 5 ) 查询语言 查询语言的实际作用就是能够描述用户的查询需求，并能够转换为系统所能实 现的形式。典型的查询语言就是传统的关系数据库中的标准语言s q l 。在数据流环 境中，数据集不再以固定的关系元组的形式存在，而是一种无限的数据流形式，因 此，如何有效表达用户的需求就成了一个重点研究问题。其中的关键问题是对数据 流处理模型的支持和对操作算子的描述。 事实上，流查询语言的表示可以有多种方式，大体可分为三类，一是基于关系 的查询语言，它类似于s q l 的结构，例如，斯坦福大学的研究中定义了c q l 作为连 续查询语言；二是基于对象的查询语言；三是基于过程的查询语言，通过符号化定 义表示相关的操作和过程。目前各研究机构都分别提出了各种不同的查询语言，如 何能真正适应用户的查询需求是重点研究的问题。 ( 6 ) 查询处理机制及查询优化 在数据流管理中存在大量的连续查询，而且是长期运行的。在运行期间，数据 流的数据特征、数据到达速率和查询的数量都是相当可观的。因此，在处理过程中 需要采取一定的处理机制进行协调和管理。为了处理波动性，查询操作必须是适应 性的，即针对波动，调整查询操作处理策略。 带来的问题主要有两个方面： 资源管理需要处理多重查询、操作和摘要数据结构之间的动态资源分配。摘 要数据结构存储管理方法是在给定大小的存储空间内，优化摘要数据结构获得更高 的准确性。一个重要问题是如何在多重查询操作和查询之间共享摘要数据结构存储。 此外，还包括系统资源的合理分配及其对查询效率和准确性的影响。系统状态变化 时，需要系统具有适应性再分配资源的能力。因此，资源管理优化问题的实质是查 5 五邑大学硕士学位论文 询结果准确性和资源分配的折中。其中准确性为查询操作资源分配的函数，资源分 配中包括存储空间分配，还有计算和i o 的资源分配等。整体的优化问题是对于给 定一系列的查询，如何达到最优的资源分配和最高的准确性。 动态调度系统需要处理多重查询计划调度的问题，调度需要解决操作内部和 操作之间的速率同步问题。到达速率和输出的时变性给该问题处理带来一定的复杂 性。调度的目标是使得响应时间和q o s ( o u a n l i t yo fs e r v i c e ，服务质量) 达到最 优化，调度还需要考虑查询操作间的内存分配，包括到达流的缓冲区管理，磁盘上 摘要数据结构的容量和个别查询的性能要求等等。 ( 7 ) 分布式结构的影响 在很多应用中，例如，传感器网络和w e b 应用等，数据源可能是分布在远端的 结点，因此产生的数据流是分布的，这就决定了查询也可能是分布的，可能会涉及 到不同结点的数据。因此，解决分布式的查询就成为数据流处理中一个重点问题。 通用的分布式策略目标是减少通信消耗，把计算推向结点，而传感器网络独有 的特点决定了分布式策略的特殊性，具有通信能力有限、电源能量有限、计算能力 有限和网络动态性强等特点。因此，解决这种复杂环境下特定路由的查询分发和结 果收集是研究的关键问题。 上述七点挑战中的最后两条为本文研究的重点。 1 2国内外的研究现状 数据流管理系统作为一个新兴的研究领域引起国内外专家和学者的关注，很多 大学和研究机构在流式数据库方面进行了大量的研究工作。 1 2 1 国外研究状况 ( 1 ) 斯坦福大学开发的s t r e a m ( s t a n f o r ds t r e md a t am a n a g e r ) 系统n 一一3 是一 种通用的基于关系的数据流管理系统，同时支持连续数据流上和传统的静态存储数 据集上的连续查询。s t r e a m 原型系统的目标是在数据流到达速度迅速、查询负载随 时间的变化无法预测以及系统资源有限的环境下运行良好。该系统中提出连续查询 语言c o l ( c o n t i n u o u sq u e r yl a n g u a g e ) h 5 1 ，该语言是基于s o l 基础上的关系查询 语言，并定义了数据流查询中的查询执行计划、操作符、内操作队列和摘要等概念。 6 五邑大学硕士学位论文 当以c q l 注册查询后，系统就为它编译查询计划。每个查询建立一个相应的查询计 划，并在系统中保持运行状态直到查询失效。s t r e a m 系统的重点在于内存管理呻，7 阳 和近似查询四1 训，其查询性能非常好。s t r e a m 中还提出了链式( c h a i n ) 1 1 m 副调度 算法，算法目的在于对运行状态进行自我控制和再优化，以期可以最大限度的减少 内存的占用。 ( 2 ) 布朗大学和麻省理工大学联合开发的大型数据流监控系统a u r o r a n 2 一引， 它支持大数量的触发器，因此，又被称为触发器网络。系统的最基本结构是b o x 和 a r r o w ，每个b o x 是一个处理单元，a r r o w 反映了数据的流动方向和处理单元处理数 据的先后次序。查询是通过图形化的用户界面，以b o x 和a r r o w 形式实现的。用户 也可以用扩展的s q l 语句实现查询，但是，扩展的s q l 将被系统编译成b o x 和a r r o w 形式，这是a u r o r a 与其它数据流管理系统的显著不同。a u r o r a 简单独特的框架结 构可以处理三种不同的应用：实时监控应用、处理以时间序列存储的大量历史数据 的档案管理型应用以及包含对历史及当前数据进行处理的跨度应用。a u r o r a 系统的 核心是一个巨大的触发器网络。每个触发器是一个数据流向图，图中的每一个结点 则是七种b u i l t - i n 操作中的一个。对每一个使用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 的研究n 们。b o r e a l i s 的主要目标在于使系统对分布式数 据流处理的应用达到一种比较高的可测量性和实用性。 ( 3 ) 美国加州大学伯克利分校的研究项目t e l e g r a p h 是一个自适应的数据流连 续查询处理系统n5 1 6 1 。主要是基于主动查询处理引擎来处理查询，其元组路由和分 组过滤技术可以实现多查询操作算子的共享，有效地降低了查询处理的内存开销。 在t e l e g r a p h 系统中，查询首先要被注册，注册后，返回给用户一个句柄，接下来， 不停地执行查询请求。t e l e g r a p h c q 的核心是e d d y n ，e d d y 是一个元组路由选择器， 当元组进入e d d y 后，e d d y 将引导元组经过它需要经过的操作符，当元组经过了所 有它应该经过的操作符之后，e d d y 将把最后得到的结果元组输出。e d d y 的特点在于 它能够对操作符进行排序，即可以动态地调整每个元组所经过的路由，也就是说， e d d y 对查询计划的调整精确到了元组的粒度，两个元组虽然需要进行同样的处理， 但是，它们所经过的操作符次序却有可能不一样。e d d y 根据它的调度策略排列操作 符顺序，不同的调度策略下元组所经操作符的顺序不尽相同，而且会有不同的优化 7 五邑大学硕士学位论文 效果。在e d d y 的调度策略中，需要考虑到操作符的处理能力、处理速度和选择率等 等。 ( 4 ) 麻省理工学院的h a r ib a l a k r i s h n a n 等人开发的m e d u s a 是一个分布式数 据流管理系统n 引。m e d u s a 提供了一个通用的分布式基础架构，这个架构提供了很多 功能。比如，它支持一个分布式的命名机制，这样就可以把某一个站点产生的已命 名的a u r o r a 输出工作流和另一个站点产生的已命名的a u r o r a 输入工作流相连，因 此，可以把本地a u r o r a 工作流汇集为一个更大的分布式工作流。另外，在网络层， 来自不同数据流的消息重发机制使得t c p i p 连接数大大减少。 ( 5 ) o r e g o n 研究生院和威斯康新大学共同参与开发了n i a g a r a 项目。该项目 对数据流的查询进行了深入研究，提出了标点模式( p u n c t u a t i o ns c h e m e s ) n 们在查 询中的应用。n i a g a r a c q 乜町系统支持连续查询，能支持监视整个广域网络上持久稳定 的数据集。例如，整个i n t e r n e t 上的w e b 站点。n i a g a r a c q 提出分组连续查询技术 以达到高效计算( e f f i c i e n te v a l u a t i o n ) 的目的，在此基础上还引出了查询总数 的可测量性问题。在n i a g a r a c q 项目中，s h a n m u g a s u n d a r a m 等人心订讨论了数据流查 询计划中的支持块操作符的问题，v i g l a s 和n a u g h t o n 口2 1 针对数据流查询提出了基于 速率的优化( r a t e d - b a s e do p t i m i z a t i o n ) 方法。 其他的研究成果如加利福尼亚大学的d s t o t tp a r k e r 等人在t a n g r a m 建模环境 的开发中提出了对仿真数据的分析方法心羽，使用流处理技术和复杂数值计算来分析 大量已存储的数据。还有b e l l 实验室的m a r ks u l l i v a n 研发的t r i b e c a 流数据管理 系统乜钔，主要应用在网络传输层的数据流分析，包括协议分析、适应性测试、差错 监控和异常检测。该系统还提供了面向数据流应用的查询语言，提供有限能力的查 询操作。 1 2 2 国内研究状况 与国际上数据流领域极其活跃的研究态势相比，国内数据流技术的研究基本处 于跟踪学习阶段。复旦大学、北京大学、哈尔滨工业大学、东北大学、东南大学等 一些研究机构已经针对数据流的各种相关问题展开研究，发表了一些有关数据流技 术的论文。但国内目前还没有一个原型系统，具有国际影响的技术成果很少，有待 进一步提高。 8 五邑大学硕士学位论文 1 3 本文的主要工作 本文主要围绕分布式数据流自适应查询处理的相关技术进行研究，在吸收前人 大量研究成果的基础上，主要完成以下三个方面的研究工作： ( 1 ) 对分布式数据流查询处理模型和现有的分布式数据流查询操作放置技术进 行了详细的介绍。我们所采用的分布式数据流查询处理的模型为将任一查询计划中 的查询操作分布式放置。本文提出了分布式数据流查询操作贪心放置算法，并通过 仿真实验验证了在分布式网络环境中，分布式数据流查询操作贪心放置算法的执行 性能。 ( 2 ) 对分布式数据流查询处理的自适应性进行了深入研究。具体研究了对于不 同类型操作符构成的查询，提出了根据动态查询选择率进行适应性优化的思想和方 法，并给出了相应的实验结果。 ( 3 ) 对分布式数据流管理系统中的多连续查询进行了深入研究。阐述了分布式 数据流多连续查询中的问题，提出了基于查询操作表的查询重用算法。 1 4 论文结构和内容 本文共分5 章，内容包括： 第一章首先阐明了课题的背景和意义，研究中面临的挑战和问题、国内外研究 现状、本文的主要工作和论文组织结构。 第二章首先介绍了数据流管理系统结构，并讨论了数据流管理系统和传统的数 据库管理系统在处理和设计上的区别。之后介绍了数据流系统查询处理机制，并给 出了查询处理结构图，最后讨论了数据流系统查询处理相关技术。 第三章对分布式数据流查询处理模型和现有的分布式数据流查询操作放置技术 进行了详细介绍。首先阐述了分布式数据流查询处理结构，然后介绍了现有的数据 流查询操作放置技术，最后提出了分布式数据流查询操作贪心放置算法，并通过仿 真实验验证了在分布式网络环境中，分布式数据流查询操作贪心放置算法的执行性 能。 第四章对分布式数据流查询处理的自适应性进行了深入研究。基于动态选择率 来进行自适应优化查询计划。文中按照多选择、多流水线、多连接查询操作符及混 合查询操作符的顺序，一一研究其自适应查询优化算法和策略，并分别通过模拟实 验对算法进行了验证。 9 五邑大学硕士学位论文 第五章对分布式数据流管理系统中的多连续查询进行了深入研究。多连续查询 是分布式数据流管理系统中查询处理的重要特性。提出了基于查询操作表的查询重 用算法。查询重用算法的核心问题是多连续查询中查询操作的重叠问题，针对现有 查询重用算法存在的问题，提出了基于查询操作表的查询重用算法，并通过模拟实 验对提出的算法思想进行了验证。 最后，在结论中对本文的工作进行总结，并对进一步的研究进行分析和展望。 1 0 五邑大学硕士学位论文 第二章数据流系统查询处理 2 1 数据流管理系统 图2 - 1 h 所示的是一个典型的数据流管理系统的结构：共包含五个部分，输入 流监控部分主要负责监测到达数据流的输入速率，当数据流过载时，将采取一定的 措施保持系统的稳定性。例如，丢弃一些输入数据。工作存储区主要保存最近的一 些数据，直到处理完毕。摘要存储区用于保存数据流摘要信息。静态存储区主要包 含有元信息，例如每个数据源的物理位置等等。长期运行的连续查询是由用户定义 并注册到查询库中的。查询处理器根据用户提供的查询信息处理相关的数据并返回 结果，同时与数据流监控部分通信以优化查询计划或者改变数据流输入速率，提高 系统的稳定性。查询结果通常以流的形式返回给用户，根据运行情况在缓存进行缓 冲。 广扒 l _ 1 卜、 = - - v ，八 i 一j p - 输入数据流 更新静态数据用户查询 图2 1 数据流管理系统结构 2 1 1d s m s 与d b m s 在处理上的区别 由于数据流的特点，传统的d b m s 不适合于对数据流的处理。 1 d b m s 并不是为处理大量的连续的数据流而设计，因此很难将大量的数据流存 储到d b m s 中。 2 d b m s 所提供的操作符难以处理对无界的数据流的查询。例如，连接操作和 害日 五邑大学硕士学位论文 聚集操作都需要得到所有的数据才能进行查询处理，而在数据流中，由于数据会持 续地到达，这些操作会因为等待数据结束而被永远地阻塞起来。显然这些操作需要 进行改进才能适应数据流环境中的计算。 3 d b m s 不支持实时的元组处理方式。它们难以应用在需要对数据进行实时分析 的应用中，如网络监控等。 4 d b m s 通常需要产生的是精确的答案，且没有实时性的限制，而数据流应用通 常产生的是近似解，且对数据的处理速度具有一定的要求。 5 对流式数据的处理通常是基于连续查询模型的，而d b m s 所能处理的是一次查 询，虽然触发器( t r i g g e r ) “3 1 能够解决一定的连续查询问题，但是它缺乏通用性， 并且传统数据库系统难以处理大量的触发器。 在数据流管理系统中，不仅数据可以以多种形式存在，对数据流的查询也可能 具有不同的形式。对传统数据库的查询多为一次性查询，返回数据集中的当前状态。 而在数据流系统中，查询可以是一次性的，也可以是连续的，并且当前的应用大多 要求连续的查询，系统可以持续长时间的对数据流进行查询操作，并持续地向用户 返回操作结果。 2 1 2d s m s 与d b m s 在设计上的区别 由于对流式数据所需的不同处理，d s m s 与d b m s 在设计上也有很多区别。 1 模型上的区别。在d b m s 中仅存在持久关系( p e r s i s t e n tr e l a t i o n s ) ，除非 刻意修改，该关系不会改变；在d s m s 中，仅仅存在瞬间关系( t r a n s i e n tr e l a t i o n s ) ， 它随着数据流上元组的到达而不断变化。 2 关系上的区别。d b m s 中一个关系表现为元组的集合( s e t ) ，可以随机访问； 而在d s m s 中，一个关系实质上是一个元组序列，只能够顺序访问。 3 数据更新上的区别。d b m s 和d s m s 均可以对关系进行操作。不同的是，前者 可以有插入( i n s e r t ) 、删除( d e l e t e ) 、更新( u p d a t e ) 等多种方式，而后者却仅 有添加( a p p e n d ) 一种方式。 4 查询上的区别。在d b m s 中，查询是瞬时的，执行完毕之后就不再有效；在 d s m s 中，查询是永久的，除非被强制取消，否则该查询会一直存在以处理新到达的 元组。 5 查询结果上的区别。d b m s 产生的是确切的查询结果；d s m s 产生的查询结果往 1 2 五邑大学硕士学位论文 往是近似的。 6 查询执行上的区别。在d b m s 中，可以任意多次访问关系中的元组；但是在 d s m s 中，却只能够一次遍历访问关系中的元组。 7 查询计划上的区别。在d b m s 中，查询计划一旦生成就不能更改；但是在d s m s 中，查询计划往往需要随着外部环境的变化而更改。 2 2 数据流管理系统的查询处理机制 通过上一节对d b m s 和d s m s 的比较可知，数据流管理系统是以查询为中心的。 而数据流中的查询多为连续查询，即用户只需发送一次查询请求，查询就一直不断 运行，它是对数据流的连续处理计算。在数据流管理系统中，查询模块是查询的执 行部分，它的主要功能是接受注册的查询、执行查询以及返回查询结果。 图2 - 2 所示的是数据流管理系统的查询处理结构。查询处理器作为查询处理的 核心部分，输入的数据流由系统接受后进行预处理，然后输入到查询处理器中；查 询的注册可由用户提交查询语句，经语法分析后得到查询计划，也可由有经验的用 户自行设计查询计划；查询处理器根据注册的查询对流进行操作，将得到的结果返 回，处理过后的流交给系统，系统根据需要进行必要保存和丢弃。 图2 2 数据沉查询处理结构 大多数系统在查询处理过程中采用的是元组到达后直接进入查询处理系统的方 式，系统使用查询计划中的操作符序列处理元组。某些系统在查询处理的过程中还 可以兼顾关系和流，在系统中定义了流与关系的相互转化的操作，在查询处理及结 果输出的过程中也进行必要的流与关系之间的相互转换，使查询处理过程中流和关 系可以统一起来。 1 3 五邑大学硕士学位论文 2 2 1 数据流系统查询处理特点 与传统数据库查询处理比较，数据流查询处理主要有以下三个特点： 1 基于内存的查询处理要求。与传统关系数据库不同，数据流查询处理主要以 内存为基础完成，这主要是因为大多数数据流应用要求较高的实时响应，对外部存 储器的读取会大大地影响处理速度，但从另一方面来讲，内存容量相对于外存储器 偏小，也对查询处理的结果造成较大的影响。 2 实时性要求。数据流查询处理的另一个特点就是关注于数据的时间性，实时 且连续地输出结果是数据流算法最基本的要求。对于数据流到达的任一元组，要求 数据流算法能很快处理完成，否则，数据不断到达，延时不断积累，最终导致q o s 显著减低。另外在大多数应用中，数据流速率会随着外部环境变化而改变。因此， 实时输出查询结果是一个重要的研究课题。 3 适应性要求。在很多应用中，数据流的变化很大。这个变化不仅可以是流速 变化，还可以是数据分布的变化。例如在传感器网络中，各个传感器结点都采集数 据，发送到中心主机进行数据流处理，传感器结点发送数据的速率和外部条件紧密 相关，即在某一时间，有些结点会发送更多的数据。对于数据流算法而言，当外部 条件变化时，能够根据数据流的变化及时调整参数，进而提高性能就非常重要。因 此，适应性就是指系统能随着数据特性和系统属性的变化动态的调整查询执行的行 为。 2 2 2 数据流系统查询方式分类 按照对数据流查询方式的不同，可以将查询分为两种： 1 一次( o n e - t i m e ) 查询：根据某个时间点数据集的状态计算查询结果，再把 结果返回给用户。 2 连续( c o n t i n u o u s ) 查询：指用户只需发送一次查询请求，就一直不断运行 的查询，它是对数据流的持续计算。连续查询的查询结果是基于时间的，它反映了 到目前为止已到达的数据流的情况，查询结果本身以数据流的形式输出。 按照注册查询的形式不同，又可将查询分为两种。 1 预定义( p r e d e f i n e d ) 查询：任何相关数据到达前就已经提交给数据流管理 系统的一种查询。虽然一次性查询也可以被预先定义，但实际应用中预定义查询通 常是连续查询。 1 4 五邑大学硕士学位论文 2 即时( a d h o c ) 查询：指在数据流已经到达后的在线查询。由于两个原因， 使得在数据流上计算即时查询变得很复杂。一是由于即时查询不能提前预知，因此 无法找出不同查询间的公共子表达式，从而对查询进行优化；二是即时查询有时需 要引用数据流中的历史数据，而已到达数据很可能已经被丢弃了。 针对数据流的特点，如何研制一个有效的数据流管理系统( d s m s ) 用以管理流 式数据便成了一个需要解决的问题。数据流管理系统跟传统的数据库管理系统在功 能上是相似的，不同的是前者允许数据以连续的数据流形式出现。如果把数据集看 作是一种特殊的数据流，则可以把数据流管理系统理解为传统数据库系统的扩展。 2 2 3 数据流系统的连续查询 由于数据流系统中的查询多为连续查询，因此，连续查询成为数据流系统查询 处理研究中的一个重要问题。 连续查询是对数据流的连续计算，连续查询一旦建立，将随着新的数据的到达 不断地产生新的查询结果。连续查询的查询结果是基于时间的，它反映了到目前为 止已到达的数据流的情况。下面，我们来讨论连续查询的具体含义。 对于连续查询，每当数据流中有一个新的数据元素到达时，如果只需要利用这 个新的数据元素便可计算出一个新的输出，我们称这种连续查询为单调的 ( m o n o t o n i c ) 。为了方便表达，我们用整数t 表示数据元素到达的序号，( 也可以是 数据元素到达的时间) ，用a ( q ，t ) 表示连续查询q 在序号为t 的元素到达时的查询 结果集合，用f 表示当前到达的元素的序号，0 是第一个到达的元素的序号，那么单 调的连续查询的语义可形式化定义如公式2 - 1 h 卯所示。 f 么( q ，f ) = u ( a ( q ，f ) 一a ( o , t 一1 ) ) u a ( q ，o ) ( 2 1 ) t = l 另外一些连续查询，在一个新的数据元素到达时，必须引用输入流或者输出流