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

浙江大学硕士学位论文数据流管理系统自适应盘询处理 摘要y 5 8 1 8 67 随着刚络技术的发展，越来越多数据正以数据流的形式存在于各种各样的 网络系统中，同时以数据流处理为中心的应用也越来越多。因此，针对数据流 的查陶处理技术在近年来得到了学术界的广泛关注。由于数据流的处理与传统 的静态数据的处理有着巨大的差异，传统的数据库管理系统( d b m s ) 已经不 能适应对高速、时变的数据流处理的需求。因此，专门针对数据流处理的数据 流管理系统( d s m s ) 也就应运而生了。 d s m si 面临的重大挑战之一是长时间连续查询和多变的系统环境和数据所 带来的对系统在适应性上的特殊需求。学术界在这方面还主要处在研究探索阶 段。目前对数据流的自适应查询处理最为成熟和最有发展前景的成果是e d d y 系统。本文以d s m s 的适应性为研究重点，在继承e d d y 系统在自适应方面的 优越性的基础上，作出了两方面的新贡献。一是对用于在e d d y 中自适应地处 理多路j o i n 操作的s t e m 机制作出了重大的改进，提出按需探测的中间结果算 法，实现了在保持原有的s t e m 算法的适应性的基础上，对中间结果进行适当 的保留，从而在j o i n 的匹配率较高的情况下，减少了重复计算，提高了系统吞 吐率，同时也对原有的路由策略也进行了针对s t e m 机制的有益的改进。另一 方面，针对原有的e d d y 系统的适应粒度过细的缺陷，本文实现了对e d d y 系 统的适应粒度进行自适应地控制，使得e d d y 系统在数据和环境相对稳定的情 况下，减少了路由决策的开销，提高了系统性能，同时并没有削弱在数据和环 境变化频繁的情况下系统的适应性。本文详细地描述了上述两方面改进的具体 算法和实现机制，对算法的性能进行了分析，给出了有说服力的实验结果，并 指出了未来的研究方向。 关键词： 数据流数据流管理系统自适应查询处理多路连接适应粒度 未经作者、导师同意 剪全文公布 浙江大学硕士学位论文数据流管理系统自适应查嘲处王! i l a b s t r a c t r e c e n t l y ，a s t h e r a p i de v o l u t i o no f t h en e t w o r kt e c h n o l o g y ，an e w c l a s so f d a t a i n t e n s i v ea 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 s i n w 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 e n tr e l a t i o n sb u tr a t h e ra s t r a n s i e n td a t as t r e a m s b e c a u s ed a t as t r e a m sa r ec o n t i n u o u s ，u n b o u n d e d ， r a p i da n dt i m e v a r y i n g ，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 n ts y s t e m s ( d b m s ) i s n o t v e r y s u i t a b l ei n p r o c e s s i n g t h i sk i n do fd a t a s 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 ( d s m s ) i sb e i n gd e v e l o p e dt of o c u so nd a t as t r e a m p r o c e s s i n g o n eo ft h eb i g g e s tc h a l l e n g e si nd s m si st h ee s p e c i a ln e e df o ra d a p t i v i t y d u et ot h el o n gr u n n i n gc o n t i n u o u sq u e r i e sa n dt i m e - v a r y i n gf e a t u r eo ft h e d a t as t r e a ma n dt h en e t w o r ke n v i r o n m e n t t h i si ss t i l lat o p i ct h a th a sn o t b e e nw e l ls t u d i e di ne v e r yd e t a i l a n dt od a t e ，a m o n gt h ed i f f e r e n tp r o t o t y p e s i nd a t as t r e a mq u e r yp r o c e s s i n g ，t h ee d d ys y s t e mi st h em o s tp r o m i s i n g t e c h n o l o g yi na d a p t i v i t y t h er e s e a r c ho ft h i sp a p e ri s b a s e do nt h ee d d y ， f o c u s i n g o nt h ea d a p t i v i t yo fq u e r yp r o c e s s i n gi nd s m s t h e r ea r et w o s i g n i f i c a n ti n n o v a t i o n si n t h i sp a p e rt h a tm a k et h ee d d ym o r ee f f i c i e n ta n d a d a p i t i v et h a nt h eo l do n e f i r s t ，w ei m p r o v e dt h es t e mm e c h a n i s m ，w h i c h w a su s e dt od e a lw i t hm u l t i - j o i n si nt h ee d d y w e p r o p o s e d am e t h o dt h a tc a n k e e pt h e i n t e r m e d i a t er e s u l t so ft h ej o i n o p e r a t o r , w i t h o u tr e d u c i n ga n y a d a p t i v i t yo ft h eo r i g i n a ls t e mm e c h a n i s m a n ds om o r ec o m p u t er e s o u r c e s a r es a v e dt oi m p r o v et h ew h o l et h r o u g h p u to ft h es y s t e m s e c o n d ，a st h e g r a n u n a r i t yi st o of i n ei nt h eo r i g i n a le d d y ，e s p e c i a l l yi nt h ec i r c u m s t a n c e s t h a td a t aa n de n v i r o n m e n t sa r er e l a t i v e l ys t a b l e w ep r o p o s e dam e c h a n i s m t h a tc a n a d a p t i v e l yc h a n g i n g t h e g r a n u n a r i t y o ft h e a d a p t i v i t ya c c o r d i n g t ot h e v a r y i n gr a t eo ft h ed a t aa n dt h ee n v i r o n m e n t s ot h es y s t e mi sm o r ee f f i c i e n t i ns t a b l ec i r c u m s t a n c e s ，w i t h o u tl o s i n ga n yb e n e f i to ft h e o r i g i n a la d a p t i v i t yi n u n s t a b l ec i r c u m s t a n c e s a t h ed e t a i l so ft h et w oc o n t r i b u t i o n sa r ed e s c r i b e d i nt h i sp a p e ra n dp r o m i s i n gr e s u l t sa r eg i v e n w ea l s oi n d i c a t e dt h ef u t u r e w o r ka tt h ee n do ft h i sp a p e r k e yw o r d s ：d a t as t r e a m ，d s m s ，a d a p t i v eq u e r yp r o c e s s i n g ，m u l t i - j o i n a d a p t i v eg r a n u n a r i t y 2 浙江大学硕十学位论文数据流管理系统自适应查询处理 1 1 背景 第1 章绪论 随着信息技术的发展，近年来一种新的数据处理应用受到t t h 关领域研究 人员的广泛关注。这种应用的特点是：数据模型不是存放在传统的数据库中的 静态关系表，而是转瞬即逝的动态数据流。这类应用所涵盖的范围相当广泛， 包括：金融证券信息分析处理、网络监测、安全监控系统、电信数据处理、w e b 应用、w e b 日志分析、个性化信息发布、传感器网络等。 1 1 1 应用举例 例1 ： 在网络监测系统中，常常需要在网络中选取一些监测点，采集并记录报文 ( p a c k e t ) 的来源、去向、业务种类、端口、报文长度等各项信息。对于报文流， 实际上可以看作一张简单的关系表，报文的格式即是表的定义，典型的定义如 下： p a c k e t s ( s r c l pp 源地址， s r c p o r t，源端口号+ ， d e s t l p广目标地址+ ， d e s t p r o l 广目标端口号t ，。 l e nr 包长度+ ， f l a g s，用于t c p 协议的标志t ， i d ，包的i d + ， c o l l d ，这个包的采集器的i d 吖。 t i m e s t a m p 广采集的时间戳 只不过这张表的数据不是存放在静态的数据库表当中，而是动态的、源源 不断的数据流，它的每个t u p l e 都是不断的到来，一段时间后又很快被丢弃。 在这张表上可能做这样的查询：统计5 分钟内，来自各源i p 地址的h t t p 请求 的包个数和包的总长度。对应于以下的查询语句： s e l e c t s r c l p , s u m ( 1 e n ) c o u n t ( + ) 5 浙江大学硕i ：学位论文 数据流管理系统自适埘查询处理 f r o mp a c k e t s 【r a n g e5m i n u t e 】 w h e r ed e s t p o r t = 8 0 g r o u pb ys r c l p 其中的关键字r a n g e 表示时问窗口。 例2 ： 再看看同时查询两个数据流的例子。在个性化信息发布系统中，有这样应 用：用户订阅了关于股票评论的消息，而条件是当某股票的股价达到某个临界 值时，则向他发送与该股票相关的评论文章。这罩包含两个数据流的处理：股 价信息和评论文章。这个查询可由以下查询语句表示： s e l e c t f r o ms t o c k sa s s ，a r t i c l e sa s a w h e r e s p r i c e x a n d s s y m b o l = as y m b o 其中s t o c k s 是股价信息流，a r t i c l e s 是评论文章流。很明显，其中包含两个 数据流的j o i n 操作。 数据流模型与传统数据模型相比有几大特殊之处： 1 大规模数据实时到达： 2 深度的网络特性； 3 系统对数据顺序的不可控和对数据和环境特性不可预测； 4 数据通常只能被处理一次，随即丢失或只有有限的数据存在有限的 内存中。 因此，在这些针对数据流处理的应用系统中，我们不能简单地将数据流存 放到传统的数据库( d b m s ) 中再进行查询。因为传统的数据库并不是为不断 快速到达的连续的数据流设计的，不能直接支持数据流应用中典型的“连续查 询”。而且，在对数据流的查询和其它处理( 例如数据分析和挖掘) 中，近似性 和适应性也是两个重要特点，而传统的数据库管理系统所注重的却是通过静态 的执行计划提供精确的查询结果，与数据流处理的需求背道而驰。 在这种情况下，数据流管理系统( d s m s ) 就应运而生了。它是专门为处 理数据流而设计的。它的处理对象与传统的数据库管理系统( d b m s ) 有很大 6 浙江人学硕士学位论文数据流管理系统自适应食询处理 的区别，主要的区别如表1 所示 数据库管理系统( d b m s )数据流管理系统( d s m s ) 持久化的关系转瞬即逝的数据流 一次性的查询( 输出结果集)连续查询( 输出数据流) 随机访问顺序访问 “无限”的磁盘存储有限的内存空间 只有系统当前状态起作用历史信息和到达顺序至关重要 被动的存储主动的存储 相对较低的更新速度可能上g b 的到达速率 没有实时性的需求 实时处理的需求 精确数据 陈旧数据和非精确数据 查询计划静态生成 不可预料的变化的数据特性 虽然d s m s 与传统的d b m s 有很大区别，但实际上在数据库技术的发展过 程中，已经出现了很多与数据流处理相关的技术，其中有很多可被d s m s 借鉴 的思想，包括： 1 传统d b m s 中的触发器、物化视图； 2 内存数据库技术； 3 分布式数据库技术； 4 活动数据库； 5 顺序，临时，时间序列数据库； 6 实时数据库； 7 自适应、联机部分结果生成技术。 1 1 3 面临的挑战 d s m s 是一种新兴的技术，发展还很不完善，面临着许多挑战，下面分别 介绍其中比较重要的几点。 7 浙江人学硕士学位论文数据流管理系统自适膊查询处理 11 3 1 极大内存需求与近似的查询处理 由于数据流本身的数据量是巨大的，在这之卜的一个查询要想得到一个确 切的答案，其内存的需求也将是巨大的。虽然对大的数据集的外部存储的算法 已经比较成熟，但是它们却不适用于数据流应用，因为它们不能支持连续查询， 而且通常较慢而不能满足实时性的要求。在连续的数据流查询中，往往需要很 高的相应时间要求，以及对大规模数据的高速处理。在处理己经到达的数据的 同时，新的数据还在源源不断地到来，因此要求对每个t u p l e 的处理时问不能 太长，否则计算的延迟将会太高，而系统将跟不上后续数据到达的步伐。因此， 需要算法尽量将自己控制在内存范围内，尽量避免对外存的访问。 这因为如此，在数据流的速度超过系统的处理能力时，我们可以尝试一种 近似的解决方案。在高速数据流的场合下，通常高质量近似解是可以被接受的。 近年来，数据流之上的近似算法取得了很好的进步。但这个领域仍然需要进一 步研究。 1 1 3 2 时间窗口 近似处理技术其中之一就是关于时间窗口不是在对所有的到达的历史 数据进行处理，而是在一定的时间窗口内处理最近的数据。例如，只有在一个 小时内到达的数据才被考虑，一小时前到达的数据则被丢弃。当然时间窗口的 大小要由数据流的速度来决定。数据流的速度快，时间窗口越小。 时间窗口有几大优点。首先它定义明确，容易理解，用户很清楚的知道什 么数据被丢弃。其次，它的近似性是确定的，不会在不同的情况下近似质量有 不同。更重要的是，它关注于最近的数据。这一点上，它甚至不仅仅是一种近 似技术，而是很多数据流应用本身的需求。例如，在网络监测的例子中，用户 本身关注的就是最近的流量统计信息，而不是以往所有的数据。 在时间窗口上，有很多值得研究的地方。如何定义时间戳就是其中之一。 如何扩展s q l 语义，使之支持时间窗e l ，也是一个研究方向。时间窗口内查询 的实现及其优化机制也是一个尚待解决的问题。另外，当时间窗口的大小超出 内存的容量时，如何利用有效的内存计算近似解也是一个难题。 虽然对顺序数据库和临时数据库的研究成果很多都与时间序列相关，但是 8 浙江大学砸l 学位论文数据流霄理糸统目造盥髓坷处埋 这与d s m s 中的时问窗口仍然有着很大的区别。临时数据库的侧重点主要是在 维护整个历史数据，而在d s m s 中我们关心的是如何及时处理新到达的数据。 顺序数据库倾向于产生允许流式访问的查询计划，意思是只需要对数据一次性 扫描就足以执行查询计划，而且所需要的内存也是恒定的，与数据无关的。这 种数据模型假定系统能够控制下一步要处理的数据顺序，但这种假设在d s m s 系统中是不存在的。 1 1 3 3 查询处理共享 当长时闯的大量的连续查询同时进行的时候，需要提供一种新的机制来共 享不同的查询所做的共同的工作。当数据到来的时候，为了避免阻塞，需要所 有的查询在数据流过的时候同时对它进行处理。单独地处理每一个查询会导致 性能太低和资源的浪费，因为这些查询一般都会有很多共性。因此，查询共享 称为系统的一个基本需求。而且，对于这些共享的处理，必须做到能够适应新 的连续查询的增加和原有查询的移除。 1 1 3 4 高度的适应性 最后，还有很多的不确定因素导致传统的静态查询计划不能适用于数据流 处理。首先，数据流赖以生存的网络环境本身是非常多变的。负载的预测、远 程系统的代价估计等都是很难做到准确的。而由于连续查询持续的时间很长， 在这期间，环境和数据的特性很难保证不发生变化，因此，需要一种机制来动 态地适应环境和数据的变化，调整查询计划。 1 2 相关的研究 1 9 9 2 年，d o u g l a st e r r y 等人研究开发了用于电子邮件和公告牌的数据库 t a p e s t r y 4 3 。t a p e s t r y 数据库和传统不周在于它的数据是只增的( a p p e n d o n l y d a t a b a s e ) ，而查询是持续的( c o n t i n u o u sq u e r y ) 。b e l l 实验室的m s u l l i v a n 在1 9 9 6 年研发了用于网络监测的t r i b e c a 数据库系统，在1 9 9 8 年又得到了进 一步的完善【2 3 】，主要解决了经过多路信号复用器( m u i t i p i e x e r ) ，多路信号分解器 9 浙江大学硕士学位论文数据流管理系统臼适应查| 旬处理 f d e m u l t i p l e x e r ) 数据流的查询问题，但数据查询相当受限，甚至没有数据流的 联接功能。类似的实际应用越来越多( 见本文第一节) ，数据量也越来越大，而 且到达速度电变得更快。为了处理大量和高速的数据，d b a r b a r a 等人在 4 4 】 中提出，在该类应用中不需要完全精确的计算，研究重点是如何在满足精度和 时间要求的前提下，精简数据得到近似解，并提出了数据大纲( d a t as y n o p s i s ) 的概念。j o s e p hm h e l l e r s t e i n 等人指出用批处理模式对大量数据进行处理计 算对用户来说不可接受，提出了联机聚集( o n l i n e a g g r e g a t i o n ) 以及相应的j o i n 算法 3 7 】，使用户可以看到处理的中间结果并可以调整处理过程。在此后，他 们注意到数据流不仅高速大量，而且速度多变，研究侧重点转移到数据处理的 自适应性【1 6 】。s b a b u 等人在【4 】中正式提出了数据流管理系统的概念( d s m s ) ， 并在【3 】中详细阐述了设计开发一个通用的数据流系统的各项问题。 比较通用和完善的系统有： n i a g a r a c q 【6 1 ，基于一个x m l 的解析引擎，将信息从w e b 站点中抽取并 保存，它可扩展性好，根据数据流的特点优化查询，并考虑了数据达到速度。 a u r o r a 5 ，设计了一系列操作原语( b o x ) ，操作人员可以利用原语搭建一个数据 流的处理流程图。查询计划( q u er yp i a n ) 可以根据数据流特点动态优化，还设 置了q o s 指标，作为调节负载( l o a ds h e d d i n g ) 的依据。 s t r e a m 4 5 ，由s t a n d f o r d 大学从2 0 0 0 年开始研发，正式提出了通用数 据流管理系统的概念。对数据流特性考虑非常充分，假定数据流无界的前提下， 研究如何分配有限资源( 比如内存) ，得到查询结果的最大精度。s t r e a m 目前 还只是一个原型系统，离实用还有比较大的距离。 t e l e g r a p h c q 1 3 】是目前发展时间最长，最成熟的一个数据流管理系统。该 系统由u cb e r k e l e y 开发，从9 7 年增加联机聚集功能以来，不断发展以适应 数据流系统的需要。利用r i p p l e j o i n 算法【3 7 】使查询能够在中间动态修正，并提 供中间结果；利用e d d i e s 结构【1 】，使查询计划由静态变为动态；继而又提出 s t e m 1 9 进一步提高查询的自适应性；提出c a c q 1 8 使系统能够处理大规模 的并行的连续查询；使用p s o u p 将大规模的连续查询本身与连续到达的数据流 同等对待，提供了查询历史数据的机制：还使用f j u x 【2 2 】完成各个并行式站点 问的负载平衡a t e l e g r a p h c q 目前已被应用于专用传感器网络和p 2 p 系统。 数据流管理系统是随着网络应用和网络自身增长而出现的新的研究领域。 1 0 浙江大学硕士学位论文数据流管理系统自适应查询处理 比较早的系统往往足在某个具体应用时，为解决特定困难而设计丌发的，没有 得到推广，处理的更多是分散的、大量的数据，对高速和时变数据流还不能适 应。近期发展的多是通用系统，在系统设计时就充分考虑了数据流的特性，在 算法、体系结构、以及数据查询计算的近似结果、中间结果等方面都出现了大 量成果。 1 3 本文的工作以及论文的组织 本文主要从d s m s 的适应性方面进行研究，在自适应查询处理框架e d d y 技术基础之上，对数据流查询处理机制的适应性进行进一步的探索。并在两个 方面取得了较为明显的成果： 1 改进了e d d y 系统中j o i n 的处理机制：s t e m 机制，以及与之相关的 路由策略。在保持原有s t e m 机制的适应性的前提下，成功地实现 了对中问结果的保留，从而减少了重复计算，并解决了中间结果带 来的重复结果和结果丢失的问题。同时通过对s t e m 按照不同方向 记录路由价值，使得原先的路由策略变得更加合理。 2 提出了自适应的适应粒度，并给出了一个实用的实现机制。提出了 通过将路由计算提前，并控制路由计算的时间间隔来控制适应粒度。 同时，给出了自适应调节算法，根据路由变化的快慢，自适应地调 节路由计算的时间间隔，从而达到自适应的适应粒度。 本文将在接下来的第2 章介绍自适应查询处理技术的发展，并重点介绍本 文的技术基础：e d d y 机制。第3 章将详细介绍改进的自适应的j o i n 算法，及 其路由策略的改进。第4 章介绍自适应的适应粒度的原理和实现机制。第5 章 给出结论和未来的研究方向。 渐江大学硕士学位论文 数据漉管理系统自适应鲞、词处理 第2 章自适应查询处理技术基础 自适应查询处理是本文研究的重点和主要内容。在这一章中，先介绍自适 应查询处理技术的发展，然后再介绍我们着重研究的e d d y 技术基础。 2 1 自适应查询处理技术的发展 2 1 1 介绍 传统数据库系统的查询优化技术的基础是基于统计的代价估计。但随着计 算技术的发展，有几方面的因素导致查询代价的估计很难做到准确： 1 硬件和系统负载的复杂性 2 数据本身的复杂性( 对象一关系数据的出现、w e b 数据的复杂性、 网络数据流) 3 。用户接口的复杂性( 长时间的连续查询需要联机的聚集操作，或者 需要根据部分结果的输出实时调整查询的属性) 因此需要建立一种自适应系统，使用新的查询引擎，新的查询优化机制， 能自适应地处理针对变化的数据流的所有联机复杂查询。 一个自适应的系统必须具备3 种能力： 1 能够感知环境的信息； 2 能够根据环境信息作出反馈； 3 能够不断地重复前两个步骤。 对适应性的评价也有3 个方面： 1 频率接收信息并改变行为的频率 2 效果能改变什么行为 3 时长能持续多长时间 2 1 2 自适应查询处理技术发展纵览 现在我们简单地回顾一下迄今为止已经出现在数据处理中的自适应技术， 看看自适应技术的发展现状和趋势。我们发现适应性发展的基本趋势是适应的 频率越来越高。 1 2 浙江大学顾士学位论文数据流管理系统自适应查询处理 先看看早期的关系系统。在s y s t e mr 的查询优化器中，和现在的大多数 关系系统一样，是通过周期性地大规模地重新收集系统的统计信息，来影响以 后的查询计划的生成。我们把这称为批量适应。在i n g r e s 系统中，通过“查询 分解”技术，在多表连接时，根据每一轮n e s t e d l o o p sj o i n 的情况，动态地确 定下一个要j o i n 的表或中间结果。这里的适应频率相对较高。达到了查询内部 甚至操作( j o i n ) 内部的适应性。但是它的时长较短，只在一次查询内部有效。 另一种自适应技术是关于后期绑定策略。在s y s t e mr 中以及现有的商用 d b m s 中有一种技术是生成带参数的查询计划，可以被多条相同的查询反复使 用。而在8 0 年代末到9 0 年代初，出现了一系列论文论述了这种策略的弱点： 在接下来的查询中，运行时环境参数可能会存在很多的改变，包括用户输入的 常量变化从而引起选择性的变化，可用内存的变化等。为了解决这个问题， g r a e f e 和c o l e 提出了动态查询计划【3 9 】，对环境可能的变化给出一定的约束， 使优化器丢弃那些在所有情况下均是次优的计划，优化的结果就得到一个执行 计划的集合，等到执行的时候再根据环境参数选择一条最适合的进行执行。这 种策略专注于将部分决策推迟到执行时，但在适应性的频率和时艮上与早期的 关系系统没有区别，仍然属于批量适应。 再来看看“每查询”的适应性。针对s y s t e mr 等系统在适应性方面的弱 点，c h e n 和r o u s s o p o u l o s 提出了“自适应选择性估计”( a s e ) 策略束增强 系统的适应性。当一个查询在被执行的过程中，中间结果的大小会被系统记录 和跟踪，从而可以用来更新系统的统计信息，从而有利于对后续的查询做出更 优的查询计划。这种策略可以逐渐适应系统环境的变化，适应性反馈的频率是 “每查询”，粒度比原先s y s t e mr 系统要小得多了。 迄今为止，最为少见的查询优化器是d e c 的( 后来是o r a c i e 的) r d b 4 0 1 系统。r d b 是第一个引入“竞争”机制的系统。它同时执行多种可选的查询计 划，在短时间内选出最快的，结束其它计划的执行。这一点与后来的数据流处 理中的e d d y 机制有类似之处，但仍然属于“每查询”的适应性。 以上介绍的技术在查询优化的水平上进行适应：访问方法的选择，j o i n 算 法，以及j o i n 的顺序选择。然而适应的水平还可以进一步在单独的操作上进行。 这种操作内部的适应性甚至可以在固定的查询计划下达到。例如，对内存大小 自动适应的排序和h a s h 算法 4 1 4 2 ，能够自动的根据可用内存的大小对算法 1 3 浙江大学硕士学位论文数据流管理系统自适成蛰! 询处理 进行调整。近来，在对于数据流的处理的研究过程中，出现了流水线式的j o i n 操作。包括x j o i n 2 7 和r i p p l ej o i n 3 7 等。将适应的程度大大增加。适应的粒 度达到“每t u p l e ”的水平。 而迄今为止，在自适应方面最具有革命性的突破是由r o na v n u r 和j o s e p h mh e l l e r s t e i n 等人提出的e d d y 系统【1o 它取消了查询优化和查询计划的生成 这环节，从根本上改变了查询处理的模式，本身就是一个自适应的框架，通 过对每个数据流t u p l e 的路由调整，可以实时地改变查询进行的路径，在“每 t u p l e ”的频率和程度上达到了最高的适应性，适应的时长也可以随着数据流无 限地延续下去。e d d y 系统正是我们研究的基础。将在下面作详细介绍。 2 2e d d y 系统介绍 2 2 1 工作原理 图1e d d y 系统工作原理图 e d d y 的系统处理的对象主要是数据流的查询处理。查询的类型支持s p j s e i e c t ，p r o j e c t 和j o i n 。对于聚合、g r o u p 等e d d y 并不直接支持，而需 要在e d d y 层之上实现。e d d y 的基本原理是，将s p j 查询分解为一系列单独 的操作：过滤器和j o i n 操作。过滤器是针对s e l e c t 的w h e r e 条件，每个条件 一个过滤器。而j o i n 是对应查询中的j o i n 操作。e d d y 处理的数据的单位是元 组( t u p l e ) 。e d d y 就像数据流里的一个大漩涡，当数据流到来的时候，t u p l e 一个个地进入漩涡，在漩涡中，经过一个个操作的处理之后，再流出去( 输出 结果) 或者停止( 被过滤掉) 。从而完成查询中的s e l e c t 和j o i n 操作，而查询 中的p r o j e c t 则在数据输出的时候进行。e d d y 的输入和输出都是数据流。e d d v 工作原理如图1 所示。 1 4 浙江大学硕士学位论文数据流管理系统白适麻查询处理 举一个简单的例子。假如有一个数据流s ，包含两个字段a 和b 。现在对s 进行简单的s e l e c t 查询： s e l e c t + f r o msw h e r ea = aa n db = b 对于这样一个查询，e d d y 将其中的两个查询条件分解为两个独立的过滤器 操作。当t u p l e 到来的时候，e d d y 负责将t u p l e 先送到其中一个操作，如果t u p l e 不满足条件，则过滤器将其直接丢弃，如果t u p l e 满足条件，则通过，被送回 到e d d y ，e d d y 再将它送到另外一个过滤器进行处理。如果两个过滤器都通过 了，则t u p l e 最终被输出，否则被丢弃。这样，当所有t u p l e 都经过e d d y 之后， 查询结果也就被全部输出了。事实上，一般情况下，这个过程会一直进行下去， 随着数据流的流入，结果也被源源不断地输出，直到数据流结束。我们可以看 出，对于以上的简单查询，e d d y 并没有一个查询优化的步骤，没有生成任何 的查询计划。但是e d d y 可以根据数据在其中流动的情况，根据两个过滤器对 t u p l e 的处理的表现，动态地决定后续数据在操作之间流动的顺序，从而实现查 询处理的动态调整，适应数据和环境的改变。具体的路出策略将在稍后讨论。 对于存在j o i n 的查询，处理会比较复杂。因为j o i n 操作关系到同时对多个 数据流的处理。首先，j i o n 操作不能对整个“无穷”的数据流处理，因为这样 的处理本身是没有意义的，只能对数据流中最近一段时间的数据进行处理。然 而，即使是最近时间段的数据仍然是断断续续地到来的，我们不能等到所有数 据到达了再进行一次性的处理。因此传统的j o i n 算法不能被用在e d d y 系统当 中。e d d y 系统需要能够处理实时到达的数据的j o i n 算法。这就要求算法具有 一定的流水线特性。早期的e d d y 实现对j o i n 操作的处理是将j o i n 封装成一个 独立的操作，操作使用非阻塞的r i p p l ej o i n 算法f 3 7 】，该算法是专门针对流式 数据的j o i n 而设计的，可以随着数据的到达而实时地进行处理，而不必因为其 中某个数据流的阻塞而等待，因为在该算法中，j o i n 的顺序可以实时地发生改 变( 但该算法中j o i n 的遍历树不能改变) 。该算法本文不作过多的探讨，因为 随着e d d y 的发展，已经产生了更适合于e d d y 的s t e m 机制。对于s t e m 机制 及j o i n 算法的改进将在下一章中详细讨论，本章中就不对j o i n 做更多的讨论 了。 下面我们来看看e d d y 是如何对t u p l e 进行路由，从而达到高度的适应性的。 1 5 浙江大学硕士学位论文数据流管理系统自适应矗询处理 2 2 2 路由策略 在e d d y 系统中，每个操作都有一个缓冲区，用来接收被e d d y 送来的t u p l e 。 t u p l e 源源不断地进入操作的缓冲区，操作则不断地从自己的缓冲区中取出 t u p l e 进行处理。因此，当e d d y 对各操作的平等对待的时候，操作的缓冲区的 充满的程度将由操作本身的快慢决定。操作越快，则缓冲区越空，操作越慢( 操 作代价越高) 则缓冲区越满。因此，通过观察各操作的缓冲区的充满的程度， e d d y 可以做出一个基本的优化：将t u p l e 路由给当前最空闲的操作。因为缓冲 区越满意味着操作的“压力”越大，因此我们把这称为“压力”策略。这样做 的好处就是，让处理速度快的操作先处理t u p t e ，t u p l e 被过滤掉一部分之后， 随后慢的操作处理的t u p l e 数量将减少。由此，整个系统的吞吐率将得到提高。 由于每个操作可用单独的线程实现，因此，在s m p 的处理环境中，这种“压 力”策略将更能充分发挥其优越性。 但是，仅仅靠“压力”策略还不能实现全部的优化。操作的选择性也是查 询优化需要考虑的重要因素。当两个过滤器的处理速度相当时，如果个过滤 器a 的选择性是9 0 ( 9 0 的t u p l e 都能通过) ，而过滤器b 的选择性是1 0 ，那么显然的，过滤器b 应该先做，因为它能使系统中的t u n e 数量迅速减 少，从而减少系统中总的处理次数，使系统的吞吐率大大提高。由于e d d y 系 统对数据的统计信息阻及操作本身的特性都没有任何的预知，因此操作对数据 的选择性只能在查询执行的过程中进行观察判断。“压力”策略是通过对操作的 输入进行观察。而选择性本身是由输入和输出共同决定的。操作吸收的输入 t u p l e 越多，选择性越低，而输出的t u p l e 越多，则选择性越高。所以输入越多， 输出越少的操作应该是要优先执行的。e d d y 系统通过t i c k e t 策略来达到这个 目的。t i c k e t 策略的做法是，对于一个操作，当它吸收一个t u p l e 时，它的t i c k e t 加1 ，当它输出一个t u p l e 时，它的t i c k e t 减1 。这样，选择性高的操作，必定 积累的t i c k e t 数量很少，而选择性低的操作积累的t i c k e t 数量则会比较多。 e d d y 只需要将t u p l e 先路由到获得t i c k e t 较多的操作，就能使系统对不同操作 的选择性迸行适应了。 由此，e d d y 系统的路由策略主要有两条：“压力”策略和t i c k e t 策略。“压 力”策略主要反映不同操作的处理代价，而t i c k e t 策略则反映操作的选择性。 1 6 渐扛大学硕士学位论文 数据流管理系统白适席查询处理 二者互为补充，相得益彰。更熏要的是，这种机制可以自动地适应数据和环境 的变化，当操作的代价和选择性随之发生变化时，e d d y 系统能够自动的适应， 调整路由顺序，而不需要任何预知的信息和外界的二f 预。这是以往的任何系统 难以达到的。 2 2 3e d d y 的发展 随着e d d y 技术研究的深入，前面所述的基本的e d d y 机制已经有了很大的 发展和改进。首先是对大量的并行的连续查询的处理，这在传感器网络的应用 中最为常见，系统存在大量的传感器，每类传感器的数据成为一个数据流，而 在这些数据流之上，又有成千上万条并行的查询需要处理。因此m a d d e n s 和s h a h m ，等人提出了c a c q 的概念【1 8 】，在e d d y 系统的基础之上，将其扩 展为能够对大量并行查询同时进行处理，并使具有共性的查询能够共享处理， t u p l e 只要一次性流过e d d y ，不需要进行任何复制就能被所有的查询所处理。 主要的技术有t u p l el i n e a g e 、操作集技术以及将j o i n 操作分解的s t e m 机制。 之后，c h a n d r a s e k a r a n ，s 和f r a n k l i n ，m 等人又继续对e d d y 进行改进，通过 将查询流和数据流对等看待，使新进入的查询可以立即得到对近期历史数据的 查询结果【7 1 。同时，他们还提出了f l u x 2 2 ，一种自适应的p a r t i t i o n i n g 操作， 使得e d d y 系统可以用于大规模的集群的并行环境中。 而e d d y 目前仍然面临着很多挑战，例如，对j o i n 算法的优化对中问 结果的利用，对适应粒度的调整，以及考虑磁盘交换的情况和大规模并发处理 的许多末解决的问题。本文主要在前两个问题上提出了自己的见解，在接下来 的两个章节中分别予以讨论。 1 7 浙江大学硕j j 学位论义数据流管理系统自适应鸯询处理 第3 章自适应j o i n 算法研究 在前面已经提到，我们采用了e d d y 系统作为基本的自适应查询处理架构。 在e d d y 系统的框架之上可以进行各种查询算法的扩充。e d d y 系统的诞生仅3 年时间，它对于简单的s e l e c t 操作的处理比较成熟，而对于j o i n 的处理则处于 研究探索之中。已有的成果主要也出自b e r k e l e y 的t e l e g r a p h 系统。它使用 s l e m 操作，将j o i n 操作分解成单个的s t e m 操作，使j o i n 操作的内部实现完 全暴露给e d d y ，从而让e d d y 可以控制t u p l e 在j o i n 操作内部的流向，从而可 以动态地调整j o i n 操作的内部顺序和实现机制，达到了j o i n 操作内部的适应 性。但是，出于j o i n 操作的复杂性，在多表连接的情况下，原有的算法没有考 虑中问结果的保留，造成了大量的重复计算，浪费了计算资源。问题的关键在 于，原有的算法中所有的s t e m 都是基于原始数据流的。而我们则使用了保留 中间结果的s t e m ( 称为m i d s t e m ) ，提出了一系列的约束规则和优化策略，在 “无环”的多表j o i n 的情况下保证了实现的正确性，并由于中间结果的保留， 提高了系统的总体性能。另外还对原有e d d y 的路e b 策略进行调整和改进，使 之更适合于s t e m 机制。 下面先分析原有e d d y 系统的s t e m 机制对j o i n 操作的处理，然后详细介 绍改进的s t e m 机制的实现方法，并分析其正确性和性能。为降低讨论的复杂 度，这一章的所有探讨除非特别说明，均是基于单查询的情况。而所探讨的适 用于单查询的机制可以按照【1 8 】中提出的方法很容易地扩展到并行多查询的情 况。 3 1 原有s t e m 机制的介绍 在上章中已经介绍了e d d y 系统的结构和实现机制，以及路由策略，这 里再详细分析原有的j o i n 操作在e d d y 中的实现机制s 【e m 机制的实现及 其优缺点。 3 1 1 为什么引入s t e m q f r 已经知道，s e l e c t 操作在e d d y 系统中的实现非常简洁和直观，只需 要将s e l e c t 的每个选择条件对应于个过滤器操作，只需处理单个数据流。但 1 8 浙大学硕+ 学位论文数据流管理系统自适心查询处理 是j o i n 操作则关联到两个或多个( n 路j o i n ) 数据流，而且每个数据流的数据 都是源源不断地到来，在任何时刻都不能保证数据流a 的t u p l e 已经可以找出 其在数据流b 巾的所有匹配。从而j o i n 的实现要比s e l e c t 复杂得多。 首先，我们引入“时间窗口”的概念，对数据流上的j o i n 操作进行限制： 对于无穷无尽的数据流，我们只能允许数据流之间在“时涮窗口”内的数 据进行j o i n 操作。时间窗口的大小根据应用的实际需要由用户指