（计算机软件与理论专业论文）流式数据库系统的研究与设计.pdf

南京航空航天大学硕士学位论文 摘要 在当今的网络监控、电信数据管理、传感器数据监控等应用中，数据采取 的是多维的、连续的、快速的、随时间变化的流式数据的形式，对数据的访问 也是多次和连续的，并要求即时的响应。研究表明传统的关系数据库系统难于 适应这种流式应用的数据管理需求，因此如何有效地开发一种新型的数据库系 统来满足这种新的数据处理要求已成为目前研究的一个热点课题。本文研究的 目的就是设计一个通用的流式数据库管理系统，该系统不仅支持对固定存储的 关系数据的管理，而且支持对流式应用中快速变化的、连续的流式数据的管理。 目前国内在此方面的矾究还比较少，本文以国外几个典型的数据流管理系统为 参考，集成它们各自的特点设计了一个新型的数据流管理系统p h o s p h o r 。 p h o s p h o r 区别于其他d s m s 的显著特点主要包括：既支持对传统的关系数据的 操作，又支持对连续的流式数据的操作：具有丰富查询窗口类型的流式查询语 言；独特的内存中组织流式数据的方法：基于内存资源的负载平衡控制策略。 关键词：数据流，连续查询，数据流管理系统，流式数据库系统，流式查询语 言，滑动窗口，负载平衡 流式数据库系统的研究与设计 a bs t r ac t r e c e n t l y an e wc l a s so fd a t as t r e a m s a p p l i c a t i o n s h a sb e c o m e w i d e l y r 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 h t 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 d w i t ht i m e t h ea c c e s st 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 d r 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 fs 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 c m 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 d o t h e r s t h e e x p e d e n c e s 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 t s a t i s f y t h ed a t as t r e a m s y s t e m sr e q u i r e m e n t s s oh o w t od e s i g na l le f f e c t i v en e wd a t a b a s es y s t e mi no r d e r t o p r o c e s sd a t as t r e a m s - b e c o m e sa no p e nr e s e a r c hp r o b l e m t h ep u r p o s eo ft h i s d i s s e r t a t i o ni st od e s i g nau 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 mn 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 r c o u n t r y ，w ed e s i g n e dad 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 h o s p h o r ，i tr e f e r s t 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 t h ei m p o r t a n td i f f e r e n c eb e t w e e n p h o s p h o ra n do t h e rd s m s si n c l u d e ：b o 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 t et h e m a n a g e m e n to b j e c t so fp h o s p h or 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 e w i n d o wt y p e s ，t h en o v e lt e c h n i q u ef o r o r g a n i z i n g d a t as t r e a m si n m e m o r y , t h e s t r a t e g yo f l o a ds h e d d i n gb a s e do n m e m o r y r e s o u r c e k e y w 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 a s t r e a m m a n a g e m e n ts y s t e m ( d s m s ) ，d a t a s t e a m s y s t e m ，s t r e a m i n gq u e r yl a n g u a g e ，s l i d ew i n d o w s ，l o a d s h e d d i n g 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的 研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被 查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名 日期 鲨迨基 d b m s d s m s s t r e a m d s s d s d b a c i d c q l s q c i s t r e a m d s ；t r e a m r s t r e a m m m d b d b c m d b a i d b w r a p i q o s l s r m c s c d i p p d c 注释表 d a t a b a s em a n a g e m e n ts y s t e m d a t as t r e a mm a n a g e m e n ts y s t e m s t a n f o r ds t r e a md a t as y s t e m d a t as t r e a ms y s t e m d a t as t r e a md a t a b a s e a t o m i c i t yc o n s i s t e n c yi s o l a t i o n d u r a b i l i t y c o n t i n u o u sq u e r yl a n g u a g e s t a n d i n gq u e r yl a n g u a g e i n s e r ts t r e a m d e l e t es t r e a m r e l a t i o ns t r e a m m e m o r ym a n a g e m e n td a t a b a s e d a t a b a s ec o n t r o lm a n a g e r d a t a b a s ea c c e s si n t e r f a c e d a t a b a s ew r i t e a p p l i c a t i o np r o g r a m m i n g i n t e r f a c e q u a l i t yo fs e r v i c e l o a ds h e d d in gr o a dm a p c y c l es a v i n g sc o e f f i c i e n t s d r o pi n s e r t i o np l a n p e r c e n tg e li v e r yc u r s o r s v 南京航空航天大学硕士学位论文 第一章绪论 三十年来，数据库理论与技术的发展极其迅速，其研究取得了丰硕成果， 其应用日益广泛，时至今日，它几乎无所不在。以三大经典( 层次、网状、关 系) 系统为代表的传统数据库技术对于管理结构简单、操作简单、完全格式和 结构化且较稳定的数据已经证明是很成功的，因而在一类重要但有限的传统商 务和管理的事务性应用领域中获得了普遍而有效的应用。然而，近年来随着信 息技术的高速发展，电信数据管理、传感器应用、网络监控等流式应用大量涌 现，而且今后还将继续大量涌现，有发展成为数据库应用主流的可能，它们已 经并将继续对数据库技术提出新的要求与挑战，从而促使了现代流式数据库技 术的研究与发展。本文将围绕现代流式数据库这个主题进行相关的研究和探讨。 本章主要讨论流式数据库的研究背景、国内外的研究现状、本文所要研究的内 容以及组织。 1 1 流式数据库研究 在现实世界的许多应用中，数据大都是连续的数据流，而不是有限存储的 数据集合，并且与过去的那种单次查询相反，在此用户需要长期连续的查询， 例如，网络控制器、电信数据管理、网络个性化、生产、传感器网络等等。这 些应用一方面需要维护大量共享数据和控制信息；另一方面其应用活动有很强 的时间性，要求连续不断地自外部环境采集数据，并根据要求进行相应的处理 及存储，再在规定的时间内做出及时响应。同时，它们所处理的数据往往是“短 暂”的，即只在一定的时间范围内有效，过时则无意义( 对当前的决策或推导) 。 所以这种应用同时需要数据库技术和流式数据处理技术两者。但传统的关系数 据库存储的是静态的关系型数据记录的集合，它们具有限定的大小、可控制的 操作、详细定义的结构，同时这些数据具有持久性。传统数据库中的计算具有 时间复杂度和空间复杂度，其查询处理为单次查询，查询计划为静态的，且晟 终生成确定的奁询结果。另外，传统数据库中的数据除非明确地加入了时制戳 的属性，否则没有时间的概念。因而传统的商务型和管理事务型d b m s 不能满足 这种流式应用的需求。只有将数据库与流式系统两者的概念、技术、方法与机 制“完善”地集成在一起的流式数据库系统才能充分满足这种流式应用的需求。 流式数据库系统就是其数据可以是连续的无界的加入时间概念的数据流， 流式数据库系统的研究与设计 对数据的处理具有时间限制的数据库系统。系统的正确性不仅依赖于逻辑结果， 还依赖于逻辑结果产生的时间。近年来。随着流式应用的大量涌现，流式数据 库系统的研究已经引起了越来越多的数据库工作者的关注。然而，流式数据库 系统并非是数据库与流式系统两者的概念、机构、工具等的简单集成，需要对 一系列问题进行研究与决策：数据和数据库的结构与组织；查询语言；事务的 优先级分配、调度和并发控制的协议与算法；内存的分配 查询处理算法；数 据以及事务特性的语义以及这种语义与一致性、正确性的关系等等。这些问题 互相关联且与应用的性质紧密相连。 1 2 国内外研究现状 目前国内对流式数据库系统的研究还比较少，且处于初期阶段。哈尔滨工 业大学、复旦大学、北京大学走在了前列。文献 1 讨论了数据流环境中异常模 式的提取和趋势监测，提出了进行异常模式提取的度量框架和相应算法，然后提 出了对于每个异常模式在时问轴上的变化趋势的监测算法。文献 2 、3 、4 讨论 了各种情况下对数据流的处理连续查询处理。文献 5 讨论了多数据流上共 享窗口连接查询的降载策略，结合共享滑动窗口查询操作的调度优化方法和降 低负载方法，提出了两种在b u r s t 环境下提高查询吞吐率的策略：均匀降载策 略、小窗口准确降载策略。 针对目前出现的这种对流式数据进行管理的应用需求，国外的许多大学和 机构已在这方面开展了大量的研究工作，下面介绍国外研制的与数据流管理相 关的原型系统及相关的工作。 斯坦福大学已经开始了一种全面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 ) 圈。s t r e a m 是一个以关系为基础的数 据流管理系统，它重点在于内存管理和近似查询。它可以用于处理快速的、易 变的、大量涌入的数据流信息，其连续查询能力非常好。s t r e a m 的主要处理技 术包括：连续的自我监控和再优化：适应于不同需要的良好近似；合理的资源 分配和使用。如今s t r e a m1 0 版本已经设计完成并正在运行期间，它可以支 持多种查询语言。 布朗大学、布兰代斯大学和麻省理工大学联合开发的a u r o r a 【7 j 系统正在 构建一个新型的数据处理系统，它的目标是专门处理流式监控。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 【s j 系统，该系统用于 连续的数据流的处理。t e l e g r a p h c q 的目的在于处理对大量高速变化的数据流 而进行的大量连续查询流。在该项目的早期工作中 9 , 1 0 , 1 i j 已经建立了一个j a v a 版本的适应性数据流处理系统。如今他们决定利用p o s t g r e s q l 坦j ( 一个源码公 开的r d b m s ) 作为进一步研究的起点。o p e n c q l l 3 系统与n i a g a r a c q 1 4 1 系统都支 持对分布于网络上的持久性数据进行连续的查询监控，如：i n t e r n 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 系统 1 5 】，该系统对只增型电子邮件信 息和电子公告信息数据库进行以内容为基础的过滤。s q l 的一个有限的子集作 为该系统的查询语言，以确保查询求值的有效执行以及生成只增型查询结果。 a l e r t 系统 1 6 1 通过使用定义在特殊的只增型的活跃库表上的连续查询，提供一 种传统s q l 数据库中的事件一条件一动作触发器机制。基于内容的x f i l t e r 过 滤系统以用户的角度利用x p a t h 语言进行连续查询，从而实现了对x m l 文档的 有效过滤。c o u g a r ”j 是一个传感器数据库，它将传感器建模为a d t s ，同时它 的输入为一个时间序列。g i g a s c o p e 懵】是一个分布式网络监控结构，它提议将 一些查询操作加到数据源中( 如：路由) 。s t a t s t r e a m 1 9 是一个流监控系统，它 用于同时在线统计几个数据流。 1 3 本文组织 本文首先从基本概念出发，然后逐层深入地论述流式数据系统中的诸多问 题及相关的技术，全文由七章组成。第一章介绍流式数据库系统的研究背景及 国内外研究情况。第二章介绍了流式数据库系统中的基本概念与基础知识，给 出了流式数据库系统与传统数据库系统之间的区别和联系。第三章讨论了 p h o s p h o r 系统的体系结构设计及各功能模块的描述，重点给出了p h o s p h o r 系 统中的两种查询处理流程。第四章对目前存在的流式查询语言进行了分类总结， 流式数据库系统的研究与设计 并对p h o s p h o r 系统中的流式查询语言p h o s p h o r c q 进行了详细说明。第五章讨 论流式数据的组织，给出了内存中组织流式数据的思想及方法。第六章讨论了 构建一个d s m s 的关键问题一一负载平衡控制问题，提出了一种新的“懒”方式 内存负载平衡控制策略。第七章对全文进行了总结，并提出了进一步研究的方 向及工作。 南京航空航天大学硕士学位论文 2 1 数据流 第二章流式数据库系统概述 因特网、w e b 以及传感器网络等已经促使应用将数据看作一种连续的数据 流，而不是固定的数据集合。电话记录，股票报价以及从传感器那里得出的数 据都属于流式数据。由此可见，数据流是连续的、无限的、快速的、随时间变 化的数据元素的流。 与传统的数据相比，流式数据具有许多自己的特点：它是大量的连续的无 限的数据；流式数据变化很快，并且要求快速的即时的响应；数据流能很好的 满足我们今日数据处理的需要；数据流管理中的箍机存取采用的是一种代价昂 贵的单一线性的扫描算法：仅仅存储到目前为止现有的数据：大多数流式数据 初始时处于相当低层次或者多维状态，需要多层次化和多维化处理。 2 2 流式应用要求 正如2 1 节中所列，数据库应用正在从传统领域迅速不断地向新的流式应 用领域扩展。这些应用有着与传统应用不同的行为特性和数据特性。 2 2 1 流式应用的行为特性 不同行业的流式应用可能有各自的不同特征、限制与要求，但与传统应用 比较而言，流式应用有下列一般性动态特征： 1 复杂性 其行为方面的复杂性主要表现在：操作复杂，不仅包括传统的插入、删除、 修改操作，还有关于时间的操作以及用户自定义的操作；执行处理复杂，其执 行处理不仅要考虑其逻辑结构本身的正确性，还要考虑逻辑结果产生的时间的 正确性。 2 。合作与协同性 各个应用任务的执行不是独立的，它们在语义结构、数据、操作、时间等 方面有相互依赖性，因而有事务级的各种通信与同步问题需要解决。 3 时间性 流式应用的i ：l , l - r e t 性表现在两个方面：一是它们所使用的数据随时间而变化， 流式数据库系统的研究与设计 即不但要处理对象的“当前”值，还要处理其变化的历史；二是应用处理的定 时性，即查询和事务有定时限值，如截止时间等。 4 主动性 许多应用能自动监控特定的情形( 条件) ，一旦该情形发生( 条件成立) ，能 自动反应而执行预先指定的活动，无须人工干预。 5 过程不可逆性 在许多时间关键型、实时过程型和工程型应用领域中，其应用工程是不可 还原和重现的，或者由于工程是连续和“长寿”的，还原和重现也是毫无实际 意义的。 2 2 2 流式应用的数据特性 流式应用中的数据较之传统应用的数据表现出的不同特点，主要表现在以 下几个方面： 在数据结构表示方面，流式应用要求更高。不但要求传统的基本数据类型， 如整型、实型、字符串等，还要求复杂的或构造的数据类型，如集合、时间序 列、递归结构及抽象数据类型等。对象之间存在着复杂的联系，如n 一元联系、 关于时间等的多种类型多种语义的联系等。对象的表示，除了表示一般的结构 化、格式化的数据，还要表示非结构、半结构化的数据。 在流式应用中的数据，本身表现出了与一般传统应用数据的不同特性，主 要有：多维性，每一数据对象不再唯一由其值来表示，每个值还有一个与之相 联的时间，即数据是二维的( 值、时间) ，更进一步，值本身也可能是多维的， 即数据对象不只是代表线上的点，还可能是平面、空间等的点、线、面、体； 易变性，数据对象频繁地动态变化，其变化不仅表现在数据的值上，而且也表 现在它的定义上，即数据的定义( 如：类型、联系、构造等) 也动态改变：多态 性，数据对象不仅是传统意义下的“值”，还可能是过程、规则、方法、模型等， 也可能是声音、影像或图像等。 流式应用对数据的使用也表现出了许多不同特性，主要有：数据操作，不 仅要进行通常的插入、删除、修改、查询，还要进行各种其他类型的操作、特 殊操作，如执行( 过程) 、时态查询等等，还要能即席构造操作和用户自定义操 作等；使用方式，传统的数据使用都是被动的、单向的，即只能经应用( 联机用 户请求或应用程序) 中的操作而被动地存取，其作用方向也只是应用作用于数 据，而流式应用要求数据使用的主动性和双向作用，即数据的状态或状态变迁 可主动地驱动操作，除了应用作用于数据外，数据也可作用于应用；变化历史， 许多现代应用要求数据的状态( 值) 和模式( 定义) 的变化记录，即要求数据的多 南京航空航天大学硕士学位论文 版本：数据正确性，在流式应用中，数据的正确性不仅表现在数据值上，而且 表现在其值产生的时间上，即数据有值和时间二维正确性。 2 2 3 流式应用对数据库的要求 由上两节所述流式应用的行为和数据特征，可以得出流式应用要求数据库 除了具备传统数据库的特点外，还应具备以下特点： ( 1 ) 强有力的数据建模能力：数据模型就是帮助人们研究设计和表示应用的 静态与动态特性及完整性约束的概念集合。这是任何数据库系统的基础。而流式 应用要求更强的建模能力，要求数据库系统提供丰富的基础数据类型一一除整 型、实型、字符串及布尔等原子型外，还有记录、表、集合等基本构造型和抽象 数据型。提供多种数据抽象技术，如聚集、概括、取样和大纲等，有建模复杂对 象的能力。 ( 2 ) 新的查询设施：流式应用中的查询不仅包括建立在固定集合上的、可进 行多次的、可得出固定准确结果的单次查询，还包括建立在连续的无限的数据流 上的无限的、持久的连续查询。这就要求一方面丰富查询语言以支持基于序列和 时间的查询语言能力，另一方面提供新的查询优化策略，如根据实际环境状况动 态优化查询计划的策略等。 ( 3 ) “识时”的系统处理：如上面两节中所述，流式应用的数据与任务( 事 务) 往往都有与之相联的时间，因此系统必须“识时”地进行数据存取与事务处 理。 ( 4 ) 触发器或主动能力：流式应用常常要求表示和监控数据与活动的静态特 性( 静态约束) 和动态变化( 动态约束) ，即要求触发器或主动机制。这种机制不仅 用于数据库系统本身( 如实现完整性检验、一致性和安全性控制等) ，还直接支持 应用语义的需要。 2 3 数据库、流式系统和流式数据库 这里主要分析传统数据库、流式系统( d s s ) 和流式数据库( d s d b ) 彼此间的联 系与差别以说明什么是d s d b 、为什么要研究d s d b 。 2 3 1 数据库与流式系统 数据库系统组合了多种功能： ( 1 ) 数据描述( 模型、模式) ； ( 2 ) 数据j 下确性维护( 完整性、一致性检验) 流式数据库系统的研究与设计 ( 3 ) 有效的数据库存取( 数据库组织、操作与存取方法) ； ( 4 ) 查询与事务的正确执行( 事务管理、调度与并发控制) ； ( 5 ) 数据的安全与可靠性保护( 安全性检验、恢复) 。 随着当今流式系统处理的信息量越来越大，对这些功能的要求也越来越迫 切。但在传统的数据库系统中。其设计与开发主要强调维护数据的正确性、保 持系统代价低、提供友好用户接口。这种数据库系统对传统的商务型和事务型 应用是有效的、成功的，但它不适合流式应用，关键在于它不考虑与数据及其 处理相联系的流式特性( c o n t ir l u o u s l ys t r e a m i n g ) 。系统的性能目标是吞吐量 和平均响应时间，而不是数据和各个事务的定时限制，故系统做调度决策时根 本不管各种流式特性。 相反，流式系统所支持的应用其数据是连续的、快速的、随时间变化的数 据流，对数据的处理也是连续的、快速的并且要求及时的响应。因而流式系统 强调的是流的特性，系统目标是满足各种流式处理的要求。 数据库与流式系统的结合导致了流式数据库系统的产生，它集成两者的概 念与要求以同时处理流的特性与一致性，这使得存储、调度等问题要复杂和困 难得多。 2 3 ，2 传统数据库与流式数据库 对于传统数据库，其事务具有a c i d ( a t o m i c i t y ，c o n s i s t e n c y ，i s o l a t i o n d u r a b i l i t y ) 特征，即： ( 1 ) 强调一致性、可恢复性和永久性； ( 2 ) 事务无内部构造，彼此之间无合作( 交互作用、通信) ； ( 3 ) 进行不可预报的数据存取，故其执行时间不可预测： ( 4 ) 无“时间维”，更不显式地考虑时间。 所以，事务的原子性和可串行化是普遍接受的正确性、一致性标准。 对于流式数据库系统，则有根本性的不同。其事务由下列特性组成： ( 1 ) 可见性事务执行时可查看另一执行事务的操作结果的能力； ( 2 ) 正确性事物本身的正确性及提交事务所产生的数据库状态的一致性 ( 3 ) 可恢复性发生故障时使数据库成为某种被认为是正确状态的能力： ( 4 ) 永久性事务记录其结果到数据库及识别其中数据的有效期的能力； ( 5 ) 可预报性事先预测一个事物是否会满足其时限的能力。 由此在流式应用环境下数据库的处理必须支持： ( 1 ) 传统的平坦原子事务模型已不适用，要求复杂事务； ( 2 ) 事务的合作、协调且并发地执行，即要求事务削的直接交互作用和通信 南京航空航天大学硕士学位论文 ( 3 ) 及时性比正确性更重要的性能标准，有时宁愿要求及时而部分正确的信 息，而不愿得到完全正确但是过时( 无效) 的信息： ( 4 ) 数据的时间相关性，即数据存储、组织与存取都是“识时”的，并非所 有数据都是永久的，许多是短暂的，甚至不一定要求所有结果都记录到永久数据 库中； ( 5 ) 恢复不一定就是数据库状态的完全复原，要求特殊的提交与恢复机制。 所以，流式数据库系统与传统数据库在概念、原理、结构、算法等方面都 存在着很大差别，最根本的区别在于数据与事务的流式特性，同时还具有时间 的特性。 2 4 数据流管理系统 针对数据流的诸多特点，如何研制一个有效的数据流管理系统( d s m s ) 用 以管理流式数据便成了一个需要解决的问题。就功能和性能而言，一个数据流 管理系统与传统的数据库管理系统( d b m s ) 相似，不同的是前者允许一些或者 所有数据都以连续的数据流的形式出现。如果将数据集看作是一个特殊的数据 流，那么数据流管理系统可以定义为传统数据库管理系统的扩充。数据流管理 系统既可以管理常规存储的数据( 关系) ，又可以处理多维的、连续的、无限制 的、快速的和随时间变化的数据流，它支持长时间连续的查询，并且产生连续 的时序的结果。 d s m s 与d b m s 有许多不同之处： 关于数据源的前提假设方面：传统的数据库是限定的静态的数据集合，它 们具有限定的大小、可控制的操作，是持久的、结构详细定义的记录( 关系) 。 数据流则是无限的在线的数据序列，它们的大小是不确定的，具有不可预知的 动作，是非持久的，无结构或半结构化的数据项。 在计算方面：传统的数据库对数据集合进行计算，这种计算是多次的或无 限次的，具有时间复杂度和空间复杂度，可看作事务处理。而数据流管理系统 则是对数据流进行计算，这种计算是一次性的，要求即时响应，其控制或查询 大多为只读式查询。 查询处理方面：传统数据库查询处理为单次查询，其查询计划为静态的， 在执行之前进行优化，且只运行一次，最终生成确定的查询结果以对流式数据 的查询处理则是连续的，它们的查询计划是动态的，需要长期得不断地运行， 随时间的变化不断进行优化，其结果也是近似的无限的数据流。 漉式数据库系统的研究与设计 一种典型的数据流管理系统的结构如图2 1 【2 0 j 所示。输入监控器可用于控 制输入速率。数据被分为三部分分别存储：l 临时工作存储( 例：用于窗口查询) 、 数据流的概要存储及中间数据的静态存储( 例：每个数据源的物理地址) 。虽然 可能对数据流现有状态只进行一次查询，长时间连续查询也要注册到查询库并 插入到队列中等待共享处理。查询优化器与输入监控器进行交互，在改变输入 速率的同时对查询计划进行重新优化。最后生成的结果也以数据流的形式显示 给用户或者进入临时缓存。 山 】工作存储 输查 输 入 i 概要存储l 询 出 监处 缓 控理 器器 存 数据流入 静态存储查询库 个个 2 5 小结 更新静态数据用户查询 图2 1 数据流管理系统的结构图 本章介绍了流式数据库系统中的基本概念与基础知识。首先介绍了流式应 用中的数据是连续的、无限的、快速的随时间变化的数据元素的流；然后分析 了流式应用的特点，包括：流式应用的行为特性、数据特性以及流式应用对数 据库的要求；根据流式应用区别于传统应用的特性进一步分析了传统数据库、 流式系统( d s s ) 和流式数据库( d s d b ) 彼此间的联系与差别，进而说明了什么是 d s d b 、为什么要研究d s d b ；最后比较了传统的数据库管理系统( d b m s ) 与数据流 管理系统( d s m s ) 之间的区别，同时给出了一个典型的d s m s 的结构。 南京航空航天大学硕士学位论文 第三章p h o s p h o r 的系统结构设计 为了实现前面所述流式应用的要求，我们正在构建一个通用的流式数据库 管理系统，取名叫p h o s p h o r ( 启明星) 。该系统特别针对目前大量涌现的流式 应用的特点进行设计，用于管理大量的连续变化的数据流以及固定存储的关系。 本章讨论p h o s p h o r 作为一个数据流管理系统，为了实现前面所述目标：保证数 据的一致性( 尤其是时间一致性) 和事务的流式特性，它所必须具备的功能与特 性，它的主要组成部件及其结构模型。 3 1 p h o s p h o r 的体系结构设计 从系统的组成结构来看，一个流式数据库管理系统与传统的数据库系统没 有什么区别，图3 1 给出了它的功能分解。其主要部件有： 流式应用：流式任务的产生源，提供同用户应用的接口。包括两部分： 数据输入接口负责数据的收集，包括流和关系；查询接口用于管理建立在数据 流以及固定存储的关系上的任务，流式系统中的主要任务就是查询，所有的查 询均注册到查询库进行统一管理。 数据监控；对输入流进行监控，监控每个输入流的流量，数据流流量参 与计算当前系统的负载容量，进行负载平衡控制。另外，数据监控跟查询处理 器进行交互，指导查询优化。 查询处理器：接收查询库中的查询任务，对其进行分析处理生成查询计 划，读取数据流入，进行查询处理，最终生成结果输出到输出缓冲区。 输出缓冲：缓存查询处理输出的结果，按照要求流出结果流到用户。 工作区：查询处理过程中，系统需要为当前查询分配f 临时工作区，用于 缓存流入的数据，相当于窗口查询。 概要存储：用于保存数据流的概要信息。 元数据存储：存储系统的元数据，相当于数据字典功能。 数据流存档：虽然我们主要是对连续查询进行在线处理，然而在许多流 式应用中还是需要对数据流进行存档，以便长期保存并进行事后的代价分析及 挖掘查询。 关系存储：系统中数据源不仅仅是连续的数掘流，还包括一些固定存储 的关系，其次有些查询的结果也是关系，保存在磁盘上。 流式数据库系统的研究与设计 卜 控制信息 二= 二= 二= = 数据信息 图3 1p h o s p h o r 的体系结构图 从系统的特性和能力来看，d s m s 与传统的数据库有着一些根本性的不同， 数据流以及连续查询的特性决定了一个数据流管理系统具有以下特点： 数据模型和查询语义必须支持基于时间的和基于序列的操作。 由于不可能将一个数据流完整的保存下来( 数据流可能是无界的) ，因此 引入了近似概要结构的应用，这样一来建立在概要上面的查询就不可能产生精 确的结果。 流式查询计划不可能使用块操作，所谓块操作是指只有当拥有了所有的 输入数据之后才能产生结果的操作，如求和、求最大值、求最小值等。 根据执行、存储约束，对一个数据流查询其历史数据是不可行的，因为 在线流式算法只对数据流进行单次处理。 对数据流进行监控的应用要求系统对非正常信息能够做出快速反应。 长时间连续查询在整个生命周期中，可能要经历系统环境参数的变化， 如数据流量的变化等。 为了保证平衡，需要多个连续查询共享执行。 南京航空航天大学硕士学位论文 3 2 流式模型 流式数据库系统是支持流式模型的数据库系统。流式数据库系统借鉴了关 系型数据库的数据建模方式，以关系模型为基础进行了丰富，加入了时间的概 念。 流式数据库系统包含两种基本的数据结构类型：流和关系。它们都是用一 个离散的有序的时间域r 来定义： 流s 是一个无界的 的数据包( 多重集) ，其中s 是元组，t r 是 时间戳，它表明流s 中元组s 到达的逻辑时间。 关系r 是一个随时间变化的元组的多重集。在t 1 1 时的元组多重集记为 r ( t ) ，读为瞬时关系。这里值得注意的是，我们在此定义的关系与传统的关系 不同，传统的关系没有加入时间的概念。 建立在流和关系上的抽象语义包含如下三类算子： 关系到关系算子：以一个或多个关系作为输入，并以一个关系作为输出。 流到关系算予：以个流作为输入，并以一个关系作为输出。 关系到流算子：以一个关系作为输入，并以一个流作为输出。 这里省略了流到流的算子，因为它可以由前三种算子组合而成。在我们的 抽象语义中，这三种类型的算子构成了我们的抽象语义：语义与这三种类型中 的具体算子无关，只同每类算子的共同特性有关。图3 2 归纳了数据类型和算子 类别的关系。 流到关系算子 关系到流算子 图3 2 数据类型与算子类别 关 系 到 关 系 一个连续查询q 是由上述三种类型的算子组成的一棵算子树。q 的输入是树 中叶节点算子的输入关系和流。而q 的输出是树的根节点算子的输出。该输出可 能是流也可能是关系，这取决于根节点算子的类型。在- 时刻，q 中的一个算子 逻辑上依赖于到t 时刻的它的输入：对于每个s 的时间戳小于t 的元组和每个 r 的瞬时关系r ( - ) ( - 7 t ) 。而算子对应于时刻t 的输出为：流s 的具有 时i 剐戳z 的元组或瞬时关系r ( t ) 。q 的行为来自它的算子。 流式数据库系统的研究与设计 3 3p h o s p h o r 系统中的查询处理流程 p h o s p h o r 系统作为一个通用的流式数据库管理系统，不仅能够处理传统的 建立在固定存储的关系上的查询，而且能够处理建立在不断变化的流动的数据 流上的查询，可以说，流式数据库系统是传统的关系型数据库的扩充。为了充 分说明流式查询的处理过程，首先说g l j p h o s p h o r 系统对传统的建立在固定关系 上的查询的处理过程，与此对应，接着介绍建立在数据流上的连续查询的处理 过程。 3 3 1 建立在固定关系上的查询处理过程 传统的查询处理的基本流程可以用图3 3 来表示： 图3 3 查询处理流程 上图给出了查询处理的一个基本流程，用户将一个用d m l 语句表示的查询 语句输入到查询处理模块，语法分析器分析查询语句，并生成相应的内部表示 ( 查询树) ，查询优化器根据数据字典中保存的信息，对查询树做语义检查， 并将查询树转成逻辑操作符树，再根据逻辑操作符与物理操作符的对应关系， 生成若干个物理操作符树，优化器根据数据字典信息，计算并找出最低执行代 价的物理树，交给查询执行器处理。查询执行器接收一个物理操作符树，执行 并输出处理结果。对用户来说，查询处理的具体过程被查询处理模块屏蔽了， 用户只需输入一个描述性的s q l 语句说明他所要查找的数据，然后查询处理模 块会准确，快速地输出所需结果，在这个过程中，用户不用知道数据放在什么 地方，必须做什么样的操作才能取到数掘，查询处理模块会自动完成这些工作。 南京航空航天大学硕士学位论文 3 3 2p h o s p h o r 中的连续查询处理方法 我们知道传统的查询访问的是固定存储的关系，然而连续查询是对不断变 化的数据流进行的查询，而且连续查询要求不断地返回连续的查询结果，即查 询结果可能也是不断变化的数据流。我们不可能将所有的数据流完整的保存到 磁盘上，同时系统应用要求即时的响应，因此我们必须在内存中完成对大多数 流式数据的存储以及处理。p h o s p h o r 系统中的连续查询的处理流程如图3 4 所 示： 圈3 4 迁续凳询处理流程 如上图所示，客户通过向系统注册一个连续查询说明开始。查询说明的格 式如下： s e l e c ts e l e c t - 1i s t f r o ms b e g i n ，e n d w h e r ec o n j o i n e d b o o l e a n f a c t o r s 语法分析器首先对其进行检查查询字符串的语法。如果语法正确，则创建 个分析树并对其进行语义检查，如果语义检查成功则系统为其分配一个唯一 的查询i d ( q u e r y d ) ，用来给用户提供将来调用的旬柄，否则返回错误。客户 流式数据库系统的研究与设计 端可以断开，并间歇性的调用查询来检索当前的结果。这一阶段的实现一般都 是用y a c c 和l e x 自动生成的。当查询分解器接收到一个查询说明 ( s p e c i f i c a t i o n ) ，就把它分割成两部分。第一部分包含去掉查询窗口描述剩 余的s e l e c t - f r o m - w h e r e 予句的说明，用s t a n d i n gq u e r yc l a u s e ( s q c ) 表示。 第二部分是数据流的窗口描述，存储在一个叫做单独的窗口结构中，用来提供 未来查询调用的参考。s q c 被插入到共享内存中的查询队列中等待执行器的共享 执行。 连续查询离不开对数据流的考虑，系统通过专门的外部应用接口程序接收 数据流，并进行相应的流量控制等。当一个新元组进入系统后，则给它分配一 个全局的唯一t u p l e i d 和一个与系统时间相对应的物理时间戳( 叫做 p h y s i c a l i d ) 。数据流元素被送往缓冲池等待处理或者直接送至查询执行器进 行处理，同时根据需要数据流可以被存储到磁盘数据库中进行存档。 针对流式数据库区别于传统关系数据库的特点，p h o s p h o r 系统中增加三种 结构：针对系统中的所有连续查询，建立一个连续查询存储结构( q u e r ys t e m ) ； 为系统中注册的每一个数据流，建立一个存储结构( d a t as t e m ) ：结果结构 ( r e s u l t a n ts t e m ) ，连续查询与数据元组的二维表，如果某个数据元组符合某 个连续查询的查询条件，则进行记录。 图3 5 查询数据连接 在内部，p h o s p h o r 把查询流的执行和数据流数据看作两个数据流的连接。 如图3 5 所示。我们把这个处理方式叫做查询一数据连接。 当客户端第次注册一个查询的时候，查询被插入到q u e r ys t e m 中，然后 用它来搜索d a t as t e m 。这种“新”查询对“旧”数据的方法就是p h o s p h o r 执 行参考历史数据的查询方式。同样的，当一个新数据元素到达的时候，被插入 南京航空航天大学硕士学位论文 到d a t as t e m 中，用它来搜索q u e r ys t e m 。这种“新”数据对“旧”查询的应 用就是p h o s p h o r 支持连续查询的方法。两种情况下，搜索的结果物化在一个结 果结构( r e s u l t a n ts t e m ) 中。当调用一个查询的时候，根据输入的窗口，对 查询结果进行物化生成结果输出。 3 4 实现一个d s m s 的几个关键问题 建立一个d s m s 除了前面提到的一般性问题外，还需要解决以下关键技术问 题，传统的数据库管理系统中的触发器、物化视图等概念为流式系统的研究提 供了许多借鉴之处。本节探讨了目前数据流管理系统中存在的一些主要技术问 题以及相关的解决方法。 3 4 ，1 块操作 所谓块操作是指只有当获得所有的输入数据之后，输出结果的第一个元组 才有可能产生的查询操作。排序就是一个块操作的典型例子，另外s u m 、c o u n t 、 m i n 、m a x 以及a v g 等聚集操作都属于块操作。利用传统的查询操作树来对流式 查询进行求值，假设数据流从叶节点输入，从根节点输出最终查询结果，则查 询树中块操作的合作执行构成了问题的关键。由于连续的数据