（计算机软件与理论专业论文）数据流管理系统中查询优化和负载脱落技术的研究.pdf

摘要 iii_n 摘要 数据流管理系统是实时处理大量、快速、无界的数据流的系统，数据流 本身的特点及面向流的应用需求对数据流管理系统实时、高效、稳定的查询 需求提出了诸多挑战。本文从系统查询的高效性和稳定性两个角度出发，研 究了数据流查询中查询优化和负载脱落两个方面的问题，设计了相应的模型 和算法，并实现了一个数据流查询原型系统。 针对查询优化，本文从查询共享和查询调度两方面开展工作。查询共享 即通过对数据流管理系统中相同或相似的存储结构和处理过程进行共享，达 到减少重复存储和计算、提高系统效率的目的。针对数据流存储共享，本文 设计了数据流查询过程中中间结果的存储结构，并设计了基于索引的共享队 列二级间接存储算法，使得中间结果存储得到一定程度的共享。针对多查询 操作共享，本文设计了相同查询操作提取的算法，通过对查询操作中相同计 算资源的共享，减少了系统的处理开销。 针对查询调度，考虑到操作符在运行时轻重缓急的不同，本文采取为每 个操作符设置优先级并根据优先级调度操作符的策略，设计了p r i o p e r a t o r 模 型，综合考虑了影响操作符优先级的四个因素，并通过为每个因素设定系数 的方式，计算得到操作符的优先级并进行调度。然后，本文引入了基于模拟 退火算法的人工神经网络方法，以影响系统性能的两个因素作为反馈，对影 响操作符优先级的四个因素的待定系数进行学习，并将学习结果运用到操作 符优先级的重新计算中，在节省系统存储空间的同时提高了系统查询的效率。 对于负载脱落问题，本文以存在连接操作符的情况时基于语义的负载脱 落为重点，从负载脱落的时机、数量和位置三个方面展开研究。通过监测系 统的负载状态，并在负载达到一定程度时进行预警，在缩小连接操作符滑动 窗口的基础上，给出了负载脱落解决方法。同时，本文设计了一种语义学习 机制，对相应元组属性进行监测并动态学习元组命中率状况，根据学习的结 果确定语义负载脱落的谓词，使得系统负载脱落时能够尽可能提高系统准确 性。在负载量减少时，算法能自适应性地删除负载脱落操作符，增加系统查 询的准确度。 最后，结合本文研究的内容，设计并实现了一个数据流查询系统，作为 本文相关设计模型及算法的运行平台。 关键词数据流；数据流管理系统；查询共享；查询调度；负载脱落 a b s t r a c t _ m mm ii mm a bs t r a c t d a t as t r e a mm a n a g e m e n ts y s t e mi sak i n do fs y s t e mw h i c hc a np r o c e s sl a r g e a m o u n t , r a p i d ，u n b o u n d e dd a t as t r e a mi nar e a lt i m ew a y t h ec h a r a c t e r i s t i c so f d a t as t r e a ma n da p p l i c a t i o nr e q u i r e m e n t sp o s em o r ec h a l l e n g et ot h ed a t as t r e a m m a n a g e m e n ts y s t e m f r o mt h eh i g he f f i c i e n c ya n ds t a b i l i t y , t h ei s s u e so fd a t a s t r e a mq u e r yo p t i m i z a t i o na n dl o a ds h e d d i n ga r es t u d i e di nt h i sd i s s e r t a t i o n t h e c o r r e s p o n d e n tm o d e l sa n da l g o r i t h m sa r ed e s i g n e d ，a n dad a t as t r e a mm a n a g e m e n t s y s t e mp r o t o t y p ei si m p l e m e n t e d i nq u e r y o p t i m i z a t i o n ，q u e r ys h a r i n ga n do p e r a t o rs c h e d u l i n ga r ec a r r i e do u l q u e r ys h a r i n gi st os h a r et h es a m eo rs i m i l es t o r a g es t u c t l l r e sa n dq u e r yo p e r a t i o n s d u r i n gt h ep r o c e s s i o ns oa st ol e s s e nt h er e p e t i t i v es t o r a g ea n dp r o c e s s i n gr e s o u r c e s t h e r e f o r e ，t h es y s t e me f f i c i e n c yi si m p r o v e d i nq u e r ys t o r a g es h a r i n g ，a m i d d l e r e s u l ts t o r a g es t r u c t u r ei s d e s i g n e d ，a n da ni n d e x b a s e da l g o r i t h mw i t h t w o l e v e li n d i r e c ts t o r a g i n go ft h es h a r i n gq u e u ei sp r e s e n t e dt oe n a b l et h ep r o p e r s h a r i n go fm i d d l es t o r a g er e s u l t s i nm u l t i q u e r i e ss h a r i n g ，a na l g o r i t h mt op i c ku p t h es a m eq u e r yo p e r a t i o n si s p r e s e n t e d ，w h i c hr e d u c e st h es y s t e mp r o c e s s i n g r e s o u r c e sb ys h a r i n gt h es a m ep r o c e s s i n gr e s o u r c e si nq u e r yo p e r a t i o n s i no p e r a t o rs c h e d u l i n g ，t a k i n gt h ed i f f e r e n tp r o c e s s i n gs t a t e so f o p e r a t o r si n t o c o n s i d e r a t i o n , t h em e t h o do fs e t t i n gt h ep r i o r i t i e sf o ro p e r a t o r sa n ds c h e d u l i n gt h e o p e r a t o r si nt e r m so fp r i o r i t i e si sa d o p t e di n t h ed i s s e r t a t i o n t h ep r i o p e r a t o r m o d e li sd e s i g n e dw h i c hc o m p r e h e n s i v e l yc o n s i d e r e dt h ef o u rf a c t o r sa f f e c t i n gt h e o p e r a t o r sp r i o r i t y t h eo p e r a t o rp r i o r i t yi sa c q u i r e df o ro p e r a t o rs c h e d u l i n gb y s e t t i n gd i f f e r e n tc o c 伍c i e n t so fd i f f e r e n tf a c t o r sa n dt h ec a l c u l a t i n gf u n c t i o n n e x t t h ea r t i f i c i a ln e u r a ln e t w o r ki si n t r o d u c e di nt h ed i s s e r t a t i o n , b a s e do ns i m u l a t e d a n n e a l i n ga l g o r i t h m , t oi m p l e m e n tt h ed y n a m i cl e a r n i n ga l g o r i t h mb yt a k i n gt w o s y s t e mp e r f o r m a n c er e l a t e df a c t o r sa sf e e d b a c k , w h i c ht r a i n st h ec o e f f i c i e n t sf o r f o u rf a c t o r sa f f e c t i n gt h eo p e r a t o r sp r i o r i t y t h e nt h el e a m i n ga l g o r i t h mi sa p p l i e d t or e c a l c u l a t et h eo p e r a t o rp r i o r i t y , w h i c hb o o s t st h es y s t e mq u e r ye f f i c i e n c ya s w e l la ss a v et h es y s t e mm e m o r ys p a c e a sf o rt h e1 0 a ds h e d d i n gi s s u e ，t h es e m a n t i c b a s e dl o a ds h e d d i n gi nt h e p r o c e s sw i t hj o i no p e r a t o r si sf o c u s e do ni nt h ed i s s e r t a t i o n t h er e l a t e dr e s e a r c hi s c a r r i e do u ti nt e r m so ft i m e ，a m o u n ta n dl o c a t i o no fl o a ds h e d d i n g b ym o n i t o r i n g t h es y s t e ml o a ds t a t ea n dp r e - w a m i n ga tt h es y s t e ml o a dc r i t i c a ls t a t e ，t h es o l u t i o n o fl o a ds h e d d i n ga f t e rt a k i n gt h em e a s u r e so f m i n i m i z i n gt h ej o i no p e r a t o r s s l i d i n g w i n d o ws i z ei sp r e s e n t e d as e m a n t i c b a s e dl e a m i n gm e c h a n i s mi sa l s od e s i g n e d , w h i c hm o n i t o r st h er e l a t e dt u p l e s a t t r i b u t e sa n d l c a m st h et u p l e s o u t p u th i tr a t i o d y n a m i c a l l y , t h e nd e t e r m i n e st h es e m a n t i cl o a ds h e d d i n gp r e d i c a t e sa c c o r d i n gt o t h er e s u l t , w h i c hc a nb o o s tt h es y s t e mq u e r yc o r r e c t n e s sa sm u c ha si tc a n w h e n m - 北京工业大学工学硕士学位论文 t h el o a di sr e d u c e d ，t h el o a ds h e d d i n go p e r a t o r sc a na l s ob er e m o v e da d a p t i v e l yb y t h e a l g o r i t h m t oi n c r e a s et h e s y s t e mq u e r yc o r r e c t n e s s 1 1 1 ed e s i g no fl o a d s h e d d i n gm o d u l ea n dr e l a t e da l g o r i t h m sm a k e st h es y s t e m ac o m b i n a t i o no f c o r r e c t n e s sa n ds t a b i l i t y 。 f i n a l l y , c o m b i n i n gw i t ht h er e s e a r c ho ft h ed i s s e r t a t i o n ，ad a t as t r e a mq u e r y s y s t e mi sd e s i g n e da n di m p l e m e n t e d ，w h i c hi sa l s or u n n i n ga sap l a t f o r mf o r r e l a t e dd e s i g n e dm o d u l e sa n da l g o r i t h m si nt h ed i s s e r t a t i o n k e y w o r d sd a t as t r e a m ；d a t as t r e a mm a n a g e m e n ts y s t e m ；q u e r ys h a r i n g ；o p e r a t o r s c h e d u l i n g ；l o a ds h e d d i n g i v - 独创性声明 。本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名 导师签名：茸日期：力堕墨2 第1 章绪论 1 1 什么是数据流 第1 章绪论 随着网络和通信技术的发展，网上的应用种类越来越多，目前基于流的 应用引起了人们的广泛关注。在这类应用中，数据是以连续的、可变的、无 界的数据序列的形式出现的，如网络中流动的数据包、电信系统的呼叫记录、 零售连锁中的交易记录、w e b 服务器生成的日志记录、工业领域中的网络检 测设备发出的信息、移动物体的位置变化等。以热门网站为例，每时每刻将 会有大量的访客，从而产生大量的流量日志记录。这些记录中蕴含着大量的 用户访问信息，很有价值。可以通过对这些实时产生的大量连续、可变、无 界的数据进行实时在线监测和查询处理，来检测和过滤异常，分析故障原因， 实现网络性能调整，保证系统高效运行。这些连续到达的数据以流的形式存 在并被处理，因此被称为数据流( d a t as t r e a m ) u 】。 数据流中的数据是一个或多个实时的、连续的、有序元素序列( 由到达时 间隐含表示或显式地由时间戳表示) 。它们可以是关系元组的形式，并具有如 下一些新特性： ( 1 ) 数据量大，是以一个或多个连续数据流的形式在线到达，数据流到达 的速率可能不同。 ( 2 ) 数据的及时更新性。数据流中的时序是非常重要的，最近的数据也是 最重要的，而过时的数据或处理过的数据会被丢掉。 ( 3 ) 需要实时在线处理，并将处理的结果及时返回给用户。 ( 4 ) 实现连续查询( c o n t i n u o u sq u e r y ) 。即一个查询请求发出后，随着数据 流新元组的持续到达而不断产生新的处理结果。 ( 5 ) 系统无法控制将要处理的新到达的数据元素的顺序，无论这些数据元 素是在一个数据流中还是跨多个数据流。 ( 6 ) 一旦数据流中的某个元素经过处理，它将被丢弃或者是被归档存储。 因此，除非该数据被明确地存储在内存中，否则不容易找回。 一般将数据流表达为如下的形式：令t 表示任一时间戳，a t 表示在该时间 戳到达的数据，数据流可以表示成 ，a t q ，a t ，鼬l ，) 【2 】。 1 2 数据流的应用 基于流的应用广泛存在于生活和生产领域中，如传感器网络、网络流量 分析、事物日志分析、金融行业等等。 北京工业大学工学硕士学位论文 ( 1 ) 传感器网络 在工程领域中分散着大量的传感器，这种基于传感器的网络 3 1 可用于地理 监控、高速公路拥塞监控、运动追踪、医学上的对生命体征的监控、生产制 造过程的监督管理等等。通过对这些监测设备收集到的数据流信息的在线分 析，可以实现多种监测功能。随着监测设备价格的不断降低和监测的范围不 断扩大，这类应用需求会越来越多，而且这些应用通常涉及复杂的过滤和对 于数据流中异常模式警报活动的响应。同时，通过多数据流上的聚集和连接 操作，可对多个数据源的数据进行分析，对单个数据流的聚集用来作为单个 传感器错误的补偿。在这类传感器网络中的代表性查询如： 如果相同区域内的几个传感器报告的测量值超过给定的阈值，就激活 一个触发器，并报告该值； 在天气图上绘制温度等高线：执行由天气监测站产生的温度流的连接 ( 基于温度属性) 。用一个包含每一个站点的纬度和经度的静态表连接结果，并 且用线把所有所报告的温度相同的点连起来；这就需要对数据流执行连接操 作。 给发电站报告近期电力使用统计流( 按地点分组，如城市、街区) ，并 据此调整电力产生速率。 ( 2 ) 网络流量分析 网络安全通常要求对网络上的数据包设置复杂的规则，而基于数据流的 查询技术【4 】则可以对网络包流、用户会话信息流进行在线连续查询。目前专门 的i n t e m e t 流量分析系统已经应用在流量统计和关键条件的检测( 例如拥塞和 服务的拒绝) 等方面，它们为实现u r l 过滤、网络入侵检测、防止病毒攻击等 提供了良好的手段。同时，通过对多个网段包的流量和流向分析，可以调整 网络路由，减少网络拥塞，提高网络性能。下面是一些网络流量分析中的典 型查询： 通信量基数：确定每一个“源目的”对所使用的带宽数量的总和， 并且按不同的i p 地址，子网掩码和协议类型进行分组。 在t c p 三次握手协议中，可以对第二次和第三次组成的逻辑流上的不 1 同的“源一目的”对的数量进行比较，如果数量上存在巨大的差异，则说明服务 拒绝攻击可能会发生。 ( 3 ) 金融自动收报 在金融领域中，通过对实时的金融数据流( 如股票、期货) 进行连续查询， 可以及时发现市场交易趋势，为用户提供交易指导，获取利润【5 】。例如股票价 格在线分析系统就会分析相关性，确认趋势和套汇时机，以及对未来价格进 行预测。典型的查询如： 最近成交量震荡的最高幅度。 查找所有价格在2 0 8 0 元的股票。 哪些股票最近5 分钟内平均成交量以3 0 0 的幅度震荡。 第1 苹绪论 “) 事务日志分析 w e b 使用日志的在线挖掘，电话呼叫记录，自动化银行处理事务等也符 合数据流模型特御6 1 。通过对这些数据流的分析，可以为应用程序提供个性化 挖掘服务，并发现异常客户的行为模式，鉴别预示着欺诈行为的可疑消费行 为和预测未来的数据值。和其他流应用相同，这可能会涉及到多个流的连接 和复杂的过滤、统计分析操作。如以下的典型查询： 查找某一个特定服务器上的所有w r e b 页，这些w e b 页在过去的1 5 分 钟内以至少大于日常平均运行4 0 的速率被访问。 实时检查w e b 服务日志，如果主服务器负载过大，则为用户重新路由 至备份服务器。 漫游直径：挖掘便携式电话记录，对每一个用户，确定在一次电话呼 叫过程中使用的最大不同基站数量。 1 3 数据流的查询处理 1 3 1 连续查询 由于数据流这种数据形式固有的动态特征以及面向流的应用领域中的具 体要求，人们在数据流的建模、连续查询、查询优化、分布式处理等方面进 行了大量的研究工作。在数据库管理系统的处理技术基础上，基于数据流本 身的特性，需要研究和使用新的适用于数据流的方法和处理技术。与传统数 据库查询处理技术相比，有如下两个不同点： ( 1 ) 一次查询与连续查询 与传统数据库管理系统中的一次查询不同，对于持续到达的数据流，人 们提出了连续查询( c o n t i n u o u sq u e r y ，c q ) 的概念。一次查询，是对数据集在 某个时间点上的一次计算，再把结果返回给用户。连续查询则是随着数据流 中数据的持续到达连续地进行计算。连续查询的答案是基于时间的，它反映 了到目前为止已看到的数据流的情况。当有新的数据到达时，连续查询的结 果可以被存储或更新，或者也可以以数据流的形式输出。例如，聚集查询可 能涉及频繁改变查询结果，因此需要使用存储方法，将当前查询结果存储起 来，当新数据到达时，更新查询结果；而连接查询往往是单调的且产生大量 的、快速的结果，适合以数据流的形式输出连接结果，不需要存储中间结果。 ( 2 ) 有限内存与无限的数据流 由于数据流潜在的流量很大，因此若要精确地得到对某个数据流的查询 结果，所需的内存量就会无边际地增长。例如连接操作，它需要保存各输入 数据流的连接状态，这需要无界的内存空间，而事实上内存空间是有限的。 为处理容量超过内存大小的数据流，人们研究过扩展内存算法，但是这种算 北京工业大学工学硕士学位论文 法并不适合数据流应用，因为它们不支持连续查询，而且对实时响应而言非 常慢。连续数据流模型则适合于实时查询响应的场合，允许大量数据以高速 率连续地产生，新数据在旧数据正在处理过程中持续到达。要求每个数据元 素的计算时间必须很少，否则将会造成较高的计算延迟，用户无法接受。 1 3 2 近似查询处理技术 当系统性能如内存、c p u 处理能力等能够满足数据流查询处理的要求时， 处理结果可以正常输出。但是由于数据流是以一个或多个连续数据流的形式 到达，数据量大，如果系统的处理能力不能满足要求时，如突发流量、处理 数据流所需内存超出物理内存等，可能导致系统总体性能下降，无法产生正 确的结果。 近似查询技术则是针对数据流的特点及系统资源有限而采取的一种查询 处理方法。它并不处理到达的每个数据元组，而是采用某种技术在保证数据 流语义的基础上，对数据流流量进行缩减，只对缩减后的流元组进行查询， 即在部分牺牲精确性的条件下获得处理时间的减少和存储空间上的节省。因 为很多面向流的应用中对数据流侧重于进行异常分析和趋势分析，如对环境 中的异常变化感兴趣，因此大多数情况下并不需要十分精确的查询结果。所 以，近似查询处理技术是数据流管理系统中重要的数据处理技术。 针对数据流问题定义的近似查询处理技术研究近年来取得了较大的成 果，下面是几种常见的近似查询处理技术。 ( 1 ) 滑动窗i = l ( s l i d i n gw i n d o w s ) 为了在有限的内存中实现对数据流的连续查询，在查询中引入窗口概念。 数据流的连续查询中一般采用滑动窗口的方法对数据流进行分割，每个滑动 窗口中存放最近到达的数据元组。查询处理的范围仅限于滑动窗口之内的数 据。滑动窗口一般可分为基于数据元组个数的滑动窗口和基于时间的滑动窗 口，前者存放最近到达的t 个数据元组，后者则存放在最近t 时间段内到达的数 据元组。查询处理器只对窗口中的数据进行处理，同时随着数据流的到来， 窗口向前移动，用新数据替换旧数据。 滑动窗口技术对数据流的数据量进行了缩减，降低了对内存的需求，提 高了查询的效率，增加响应的及时性。但是，因为窗口中的数据不断发生变 化，要考虑减少窗口的维护代价，提高查询执行效率的问题。根据窗口滑动 方式的不同，滑动窗口分为连续更新滑动窗口和周期更新滑动窗口i 7 1 。w a t e r l o o 大学l u k a s zg o l a b 提出的滑动窗口维护方法，是根据应用需求将滑动窗口分 成几个大小相等的子窗口，将子窗口作为存储结构，当一个子窗口填满数据 时，通过窗口索引指针移动在子窗口之间进行切换。因为只需要对子窗口中 的流元组进行扫描和替换，从而提高了在窗口中的执行速度，减少窗口维护 的代价【8 】o 第1 章绪论 ( 2 ) 批处理( b a t c hp r o c e s s i n g ) 当数据元素到达时，并不立即进行处理，而是把它们缓存起来，定期计算 查询结果。这种方法不会影响到查询结果的精确性。批处理适用于更新操作 快但计算结果比较慢的情况。 ( 3 ) 大纲( s y n o p s e s ) 在系统内存资源有限的情况下，需要对数据流的流量进行控制，但是要具 有合理的精确度。大纲技术可用于为用户查询提供近似答案，并且对近似质 量提供一定的保障。 大纲的主要计算方法如下： 采样技术( s a m p l e s ) 在期望用一个小的样本获取数据集的基本特征的情况下，可以用样本作为 一种概要结构，这种方法是数据流管理系统中简单的概要方法。例如当数据 流输入速度过快，考虑采用采样的方法来缩减数据量，也就是说放弃一些元 组，只是对数据流的某些样本进行查询计算。同时考虑采样频率和批处理的 时间间隔。采样适用于计算速度快，但更新操作慢更新所需时间比数据 元素的平均到达时间间隔要长的情况。但是包含连接操作的查询，基于采样 的方法不能提供可靠的近似保证。 草图技术( s k e t c h i n 9 1 7 草图技术用在不同的聚集查询中，包括从某些已知期望的数据流相关属 性值分布图中选出随机向量，获取兴趣函数( 如项目频度) 的内积，同时使用少 量内存建立数据流的一个概要，使用这种技术可以对数据集上的特定查询计 算答案。 直方图( h i s t o g r a m s ) 直方图方法是根据实际数据的分布将数据划分到一系列的区间( 直方桶) 中，以桶为单位估算各个数据的大小。直方图是被广泛应用于简便地获取一 个数据集中值的分布情况的概要结构。直方图一般有等宽、变宽、偏向两端 等类型。其中变宽直方图又有等深( 或等高) 、v - 最优、压缩、最大差异直方图 等类型。在各种类型的直方图中，等宽直方图算法最简单，但精确度很差； 变宽直方图，尤其是v 最优直方图对数据分布的描述有较高的准确度，但v 最优直方图算法的时间和空间复杂度一般较高，并且需要对数据进行多遍扫 描。 小波变换( w a v e l e t s ) 小波变换通常被用作一种提供数据的概要表示的技术，尤其能够很好地 表征信号的突变瞬间特性。小波系数是给定信号( 数据值集) 在基础向量正交系 上的投影，基础向量的选择决定了小波类型。小波变换技术也可以用于实现 无界流的近似聚合。 北京工业大学工学硕士学位论文 1 4 数据流管理系统 1 4 1 数据流管理系统的功能 数据流在各领域的广泛应用使得数据流的有效处理成为人们日益关注的 问题。基于数据流的特殊性，数据流处理时需要大量的存储空间和快速实时 的处理性能，存储相对静止数据的数据库管理系统已经不能满足这种形式数 据的需要，人们开始了对能够实时、有效处理此类数据的系统数据流管 理系统( d a t as t r e a mm a n a g e m e n ts y s t e m ) 的研究。 数据流管理系统 的核心是建立一种查 询模型，如图1 1 所示 【9 1 。这种查询模型具有 三个连续性特点： ( 1 ) 输入的待处 理数据具有连续性，数 据在时间和次序上具 有敏感性。 ( 2 ) 查询具有连 续性，即数据驱动查 询，数据不断则查询不 结束。 数据流1 数据流2 数据流n _ 卜_ 卜_ 一卜_ - 卜 查询 0出流 图1 1 。d s m s 查询模型 f i g u r e1 - 1d s m sq u e r ym o d e l ( 3 ) 输出的查询结果具有连续性，查询的结果可以是一次查询的结果，也 可以是对连续的数据流的查询结果。 1 4 2d b m s 与d s m s 的比较 传统的数据库系统旨在处理永久、稳定的数据，强调维护数据的完整性、 一致性，其设计目标是维护数据的绝对正确性、保证系统的低代价、提供友 好的用户接口。这种数据库系统对传统的商务和事务型应用是有效的和成功 的，然而它不适合无限、快速、实时的数据流应用。d s m s 不考虑与数据及事 务相联的时间和空间限制，其系统的性能指标是吞吐量和平均响应时间，而 不是自适应性和查询服务质量等，调度与处理决策也不考虑各种时间特性。 与传统d b m s 切为了保证结果的绝对正确性不同，数据流管理系统d s m s 贝, i 更看重自适应性。目前还没有d b m s 提供内建的功能支持近似查询。 d b m s 与d s m s 对数据的处理要求是相同的，都是针对用户提出的查询， 对数据元组集合进行处理，最后返回查询结果。但是它们也存在着数据处理 第1 章绪论 方式和和结果上的很大区别，如表1 1 所示f 1 0 1 。 表1 1 数据流管理系统与数据库管理系统的比较 区别 数据库管理系统( d b m s )，数据流管理系统( d s m s ) 处理对象静态数据集合动态数据流 查询方式一次查询 持续查询 数据访问方式随机访问顺序访问 存储媒介大容量磁盘有限内存空间 实时性要求无有 数据更新率相对较低高更新率 查询结果精确查询近似查询 查询确定性事先确定动态改变 数据流管理系统d s m s 与传统d b m s 相比，特殊性主要表现在以下三个方 面： ( 1 ) 语义( s e m a n t i c s ) ：流按时间顺序输入，查询结果以流形式输出。 ( 2 ) 状态( s t a t e ) ：不能存储无终止的流状态，但是某些操作需要历史记录。 ( 3 ) 性能( p e r f o r m a n c e ) ：自适应性( a d a p t i v i t y ) ，速率可变性( v a r i a b i l i t y ) ， 不精确性( i m p r e c i s i o n ) 。 流数据和连续查询的特殊性要求数据流管理系统必须具备下述功能： ( 1 ) 数据模式和查询语义必须允许基于顺序和基于时间的操作，如要求实 现在5 分钟尺寸大小的滑动窗口上的查询。 ( 2 ) 长时间运行的查询在执行期间可能会遇到系统条件的变化，例如流速 率的变化，需要设计具有自适应性的查询计划和调度策略。为确保可伸缩性， 需要负载均衡。多个近似连续查询的共享执行是必要的。 ( 3 ) 流查询算法是受限的，只能一遍扫描数据，而不可能存储全部的流， 意味着需要使用近似的大纲结构，即作用在大纲上的查询可能会返回不精确 的结果。 ( 4 ) 监控实时数据流的应用必须快速响应异常数据。为了及时准确地响应 用户查询，通过服务质量保j a t ( q o s ) 的检测指导系统调度和负载均衡。 1 4 3 数据流管理系统的一般模型 由于数据流的连续、可变、无界的特性与现有数据库中通常处理的静态 数据不同，因此需要研究并建立新的模型来管理数据流，实现各种数据操作。 文献【1 1 】指出，一个数据流管理系统的重要组件如图1 2 所示，包括：调度器、 近似查询处理器、负载管理器、查询优化器、分布式数据监测器等【1 2 1 1 3 1 。每 个组件的详细说明如下： ( 1 ) 输入监视器：用来对大数据量的数据流进行流量调整，按照一定的约 束条件对数据流中的元组进行过滤，仅将过滤后的数据交给系统进行查询处 理。 北京工业大学工学硕士学位论文 更新 查询 图l - 2 数据流管理系统一股模型 f i g u r e1 - 2c - e n e m ld s m sm o d e l ( 2 ) 临时存储区：最新的数据被保存的临时存储区，直到被处理完毕并丢 弃它们。数据流大纲驻留在概要存储区中。 ( 3 ) 静态存储区包含一些数据流特性的元数据如数据流的位置，全部数据 流系统的拓扑结构等。 ( 4 ) 查询知识库维护用户提交的查询请求并将它们提交给查询处理器。 ( 5 ) 查询处理器基于概要存储区中存储的大纲信息执行用户对数据流的 查询请求，并将处理后的数据交给输出缓冲区进行输出。 1 5 数据流管理系统主要研究内容 目前对数据流管理系统的研究尚属起步阶段。针对数据流的特点，数据 流管理系统需要着重解决以下三方面问题【1 5 】1 1 6 】： ( 1 ) 无界数据流到来带来的处理上的无界内存需求； ( 2 ) 数据流实时快速到达带来的处理上的持续性和实时性； ( 3 ) 数据流到来速率易变性带来的处理上的自适应性。 基于以上面临的问题，现阶段数据流管理系统的研究主要围绕着以下几 方面的内容： ( 1 ) 系统体系结构( a r c h i t e c t u r e ) ：近几年，人们设计了针对各种不同研究 应用的系统，尽管具体实现方式不尽相同，但系统结构方面已经初步形成了 以输入监视、输出缓冲、查询处理器、不同内存管理器等模块共同组成的模 型，如图1 2 所示。 ( 2 ) 数据描述类型( d a t am o d e l i n g ) ：与数据库管理系统处理的数据类型类 似，数据流管理系统处理的数据类型也逐渐分化为基于关系型_ ( r e l a t i o n b a s e d ) 的模型和基于对象型( o b j e c t - b a s e d ) l 拘模型。同时，针对不同类型的系统，基于 数据流的特征设计了不同的数据表示形式、查询元操作和查询语言，例如基 于关系型的c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) 语言。 ( 3 ) 查询处t _ 里( q u e r yp r o c e s s i n g ) ：查询处理指的是系统基本的数据处理操 8 第1 章绪论 作，包括查询处理的方式以及查询过程中内存的管理。由于数据流处理的无 界性，通常数据库系统中的块操作需要转化为非块操作【l 。7 1 p g ，因此各种查询 处理机制也处于广泛的研究中。目前人们先后研究了基于界标模型1 1 8 】和滑动 窗口的处理机制来进行处理。界标模型是针对对于内存的使用，不同的系统 设计了不同的内存管理方法。同时，还有一些研究，需要解决数据流系统的 即席查询问题，即对历史数据的查询。 ( 4 ) 查询优化( q u e r yo p t i m i z a t i o n ) ：面对无限的数据流，数据流管理系统 处理资源有限，因此最大限度地利用系统资源，优化配置可以在一定程度上 提高系统性能，是十分必要的。在查询处理过程中，系统需要实时进行优化， 以保证系统资源处理时的准确性和在各种突发情况时的有效利用、高吞吐率。 查询优化主要包括两部分：查询资源的优化和查询的自适应性【2 0 1 2 1 】四】【2 3 1 。前 者主要通过查询过程中c p u 和内存等资源的共享实现的，而后者主要通过动态 调度元组的执行顺序来完成的。 ( 5 ) 数据量缩减( d a t ar e d u c t i o n ) ：由于数据流到来速率的突变性，因此会 出现到来的数据流超过系统处理能力的情况，这将导致系统处理效率变低， 后来的数据得不到实时的响应。这就需要系统及时对待处理的数据进行缩减， 以使得系统能够进行实时的数据处理。这方面的研究主要包括负载脱落技术 ( l o a ds h e d d i n g ) 2 4 1 。负载脱落技术主要通过处理数据流的抽样方式进行，包括 无抽样目标的随机负载脱落和基于元组属性值的语义( s e m a n t i c ) 负载脱落方 法。 1 6 数据流领域研究现状 面向数据流的研究与应用开发，是目前数据库领域研究的一个热点，很 多科研院所和学术团体都认为它蕴涵着巨大的商业和学术价值，从不同的角 度来进行研究，并在数据流系统的建模、查询语言、近似查询算法、流操作 的调度策略、分布式查询的处理、数据流的挖掘等方面开展了大量的研究工 作。比较著名的数据流项目如下： ( 1 ) s t r e a m 系统 美i 雪s t a n f o r d 大学研究开发的数据流管理系统s t r e a m 【2 5 】是一个通用的 数据流管理系统，它侧重于资源管理和近似查询处理。它的流查询语言 c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) 1 2 6 1 是对标准s q l 语句的改进，使得f r o m 子句 中可以同时处理数据流和关系，并基于滑动窗口的数据流实现查询处理。用 户可以采用c q l 注册查询，也可以直接输入查询计划，被注册的查询将一直 被保留到查询被显式地注销为止。 ( 2 ) t e l e g r a p h c q 系统 t e l e g r a p h c q t 2 7 】是一个通用的数据流管理系统，在开放式关系数据库管理 系统p o s t g r e s q l 基础上开发。它继承了u cb e r k e l e y 的t e l e g r a p h 数据流项目开 北京工业大学工学硕士学位论文 iiii 一一一i i i i i 曼蔓! ! 曼苎皇 发成果，以p s o u p 系统为查询处理系统，以f l u x 系统作为负载平衡和容错处理 系统。 、 t e l e g r a p h c q 使用一个自适应查询引擎( 基于e d d y l 拘概念) 来处理不稳定的 和不可预知的环境( 例如i n t e r n e t 上的自治数据资源，或传感器网络) 下的查询效 率问题。注册的数据流查询计划经过预处理后被变换成一个操作符执行序列， 而后交给元组路由选择器e d d y 。同时，它可以对多个数据流进行共享查询处 理，并根据环境的变化进行查询计划的调整。 ( 3 ) a u r o r a 系统 a u r o r a 系统【2 8 】是一个专门针对数据流监控应用的数据流管理系统。它采 用了工作流系统中常用的b o x ( 功能盒操作符) 和a r r o w ( 数据流向符) 模型。用 户可将查询表示为由a r r o w 流向符连接起来的若干b o x 操作符组合而成的网络 模式，这个模式就是初步查询计划。查询计划被简单变换成调度器中的不同 查询处理队列。调度器的调度分两个层次：确定选择哪个查询操作符进行 调度；确定每个查询如何执行，即操作符序列的执行顺序。a u r o r a 系统采 用了批处理技术来降低调度代价和操作符执行代价。系统支持两种方式的批 处理：对操作符调度的批处理和对元组的批处理。a u r o r a 系统对于大量的实 时数据，根据定义的服务质量( q o s ) 模型，采用l o a ds h e d d i n g 技术卸载数据流 量，以保证系统的响应速度。 ( 4 ) n i a g a r a 系统 w e b 流n i a g a r a 系纠2 9 】是一个动态监测w e b 站点内容的连续查询系统。 n i a g a r a 系统可以对以x m l 格式表示的数据执行查询，并且产生的结果也以 x m l 格式表示。n i a g a r a c q 提出以分组方式执行多个连续查询，每个组中相似 查询共享一个查询计划，以达到高效计算的目的。 1 7 本文主要研究内容和意义 由于数据流已经广泛渗透到各个应用领域，人们迫切需要一个能够快速、 实时、准确处理数据流的高可用数据流管理系统。经过几年的发展，数据流 管理系统的研究已经取得了一定的成果，在系统模型、数据表示、查询语言 和查询处理等方面有了一定的积累，为以后的研究提供了较好的理论依据。 但是，目前人们在系统在动态环境中自适应处理上的研究相对较少，还有待 于进一步深入研究，使系统的自适应性提高，高可用性能得到增强，能够进 一步广泛应用于金融服务、网络监控和安全、电信数据管理等处理大批量数 据的部门。 本文主要研究了数据流管理系统的查询优化和负载脱落两个方面的问 题。其中查询优化主要研究如何在系统运行时，利用有限的系统运算和存储 资源来优化系统查询配置，从而最大限度地对输入的数据流进行查询，实时 第1 苹绪论 输出结果，并保证查询的准确率；负载脱落则考虑当系统输入数据超过系统 处理能力时，如何脱去超出系统实时处理能力的数据，在保证系统能够正常 运行的前提下，提高系统的查询准确率。 在以上研究的基础上，本文设计了一个原型系统，实现了数据流的查询 处理、查询调度和负载脱落的功能，为本文设计的相关模型和算法的测