（计算机应用技术专业论文）数据流连续查询处理系统设计与实现.pdf

东南大学硕士学位论文 摘要 近年来，在金融服务、网络监控、电信数据管理及传感器监控等领域中，出现了一类新 的数据密集型应用，这类应用的特征是：数据不宜用持久稳定关系建模，而适合用瞬态数据 流建模。在这种数据流模型中，单独的数据单元可能是相关数据的元组，例如网络测量、呼 叫记录及传感器读数等产生的数据。由于这些数据以大量、快速、时变的数据流形式持续到 达。若把持续到达的流数据简单的放到传统的数据库管理系统中进行管理是不可行的，由此 产生了一些新的基础性的研究课题。 论文在研究目前国际上最新的数据流管理技术的基础上，介绍了自行研究开发的基于硬 件预处理器的数据流管理系统原型s e u s t r e a m 的体系结构，设计了一种可以支持对数据流 上进行连续查询的查询语言x - s q l ，并以数据流预处理器为目标机器设计了数据流连续查询 语言x - s q l 的编译器，该编译器对用户提交的查询命令进行词法、语法及语义分析，并进行 查询优化，得到查询抽象语法树，并针对数据流预处理器对抽象语法树进行处理，生成其所 需的控制信息。 关键字：数据流管理系统。连续查询，连续查询语言，编译器 东南太学硕士学位论史 a b s t r a c t r e 时t h e r eh a sw 缸l e s s e daf o c u s 0 1 1 1p l d o 蝴i n gh e wd a i a - i n t e u s i v ea p p l i c a t i o n s , s u c ha s 螽期赫越s e r v i c e , n e t w o r k 嗍舞鹕t e l e c o m m u n i c a t i o n sd a t a 糖键l a | 雪e 辩蕊壤铯n s o rd e t e c t i o n , a n ds of o r t h 1 1 ”c o m n l u nf e a t u r eo ft h e a p p l i c a t i o n si s 吐i 吮t h ed a t ag e n e r a t e di nt h e s e a p p l i c _ 畦j 函俗瓣r i o t om i t a b l ef o rb e i n gm o d e l e db yt r a n s i e n td a t as 毛嗽嫩蟮t h a nb yp e 翔硪l 豫时 r e l a t i o n s 斑t h em o d e lo fd a t am e a t u s , ad a t au n i tc o u l db e 鑫t u p l eo fr e l a t e dd 缸s u c ha s n e t w o r km e a s u r e m e n t , c a l lr e c o r d s , s e n s o r 删i n g a n ds oo i lf o rt h es a k eo f t h ec h a r a c t e r i s t i c o f h n g es l z e , h i g hs 辨穗o f d a t a 瓣址垂f i m e - v a r i n g , t h ed a t ai nd a t as t r e a mm o d e lc o u l dn o t 酶 m a n a g e db yt r e d i t i o n a ld a t a b a s e o nt h eb a s i so f m d y m gt h en e wt h e o r ya n dt e c h n o l o g yo f d a t as t r e a ml n a n a 8 e m e l l t , af l e w d a t a 捌嚣虢m a n a g e m e n ts y s t e mp r o t o t y p e 耘啪d0 1 1p r e p r o c e s s i n gt h ed a t as t r e a m sb yh a r d w a r e , w h i c hn a m e ds e u s t r e a m , i sd e v e l o p e d f i r s t l yt h ea r c h i t e c t u r eo fs e l l 鲫l e a ma n dt h e p l q 埔) 。鹧鲥o fd a t as l e a m sr i f ei n t r o d u c e d t h e nt h ep s p c rg i v t h ed e s i g no fac o n t i n u o u s q u e r yl a n g u a g ex - s q l , w h i c hs u p p o r tt h ec o n t i n u o u sq u e r y0 1 1d a t as t r e a m s a n dt h e na c o m p i l e ro fx s q li s i n t r o d u c e d i t st a r g e tm a c h i n ei s 骶d a t as t r e a mp r e p r o c 燃s o f 讯 s e u s 詈暑a m 1 ns e u s i 零匹a 吨l 格粥s u b m m i tc o n t i n u o u sq u e r i e so f d a ms t r e a m sb yx - s q l l a n g u a g e a f t e rl e x i c a ia n a l y s i s , s y t a xp m l n g 。s e m a n t i ca n a l y s i sa n dq u e r yo p t i m i z a t i o n , t h e q u e r i e sc o m m i t e d 虹u s e r sw o u l db e 缸a u s f e r r e di n t o 孤a b s t r a c t 吣t r e e ( a s db yt h z c o m p i l e r a ，撼t h e nt h ec o r n 痰l e rm l l 瓣g e n e r a t e 珏臻躐n ec o d eo f t h ep r e p r o c e s s o r k e yw o r d sd s m s 。c o n t i n u o u sq u e r y , c o n t i n u o u sq u e r yl a n g u a g e c o m p i l e r n 东南大学学位论文 独创性声明及使用授权的说明 一、学位论义独创饿声明 奉天露磺掰毒燮耱学静论文楚我伞夫在导师指孥f 进行静研究 筝及取得酌研究成襞。尽我所 知。除丁文中特别加以标泣和致谢的地方外，论文中不包食其能人已经发表或撰碍过的研究成果， 像不雹禽为莪褥采海天学戏其它教育辊拇酌学位或证静丽使翊过豹材辩。与我一嗣j 律静祸志对本 研究所做的任何赞献均已崔论文中作了明确的说明并簌示了谢意。 躲计0 隅一吞+ “。 二、关于学位论文使用授权的说明 东南太学、串丽科学技术信息研究所、蠲家图书铸有权保留本人所送交学能论文的复印件和电 节文档，可敬采崩影印、缩印或其他复制手段保存论文。本人瞧子文档静态容和娥质论文的内容横 一致。豫在保密鞠内的傈密论文外，危许论交被轰蠲和衢阋，可馘公布( 镪括翻登) 论文的全部或部势 内容。论文的公布( 包括刊登煅权永巅太学研究生院绺璎。 镰名： t 譬师签名：隅掣宁二， 东南太学硕士学能论文 缝论 在澎澎色玺黪计算氍辩鞭顿竣牵，毒樊重要豹译簿瓤建掰，箕黪涉及羲簇蟹霏辜之丈，其巾 数据也不随程序的结束而消失并被多个应用稷序所熬事，我们称之为数描密集型威用。这类戍用所 要处理的问题即为数据管理问题。数据管理誊是计舞帆科学技术领域中的一九爨要技术和研究谡 题，垂既开始了数据瘁系统的疆究。羧援露鬟统魏骚究耱再菱在冀3 。每瓣掰变孛驭褥了歪夫鹩或璃， 数据库系统的应用已经遍敝各个领域，奠定了数据库臻统作为当今社会信息基础设施核心的技术地 位。 遥霉来，出黼了一类新的数据密集垂敷掰，这类蹴鬻中翁数据特征虢：连续、无碾、快速、醚 时闻变，散据不赢用持久稳定关系建模，而遗台用数攒流建模这类应用出现在许多应用领域中， 笆捶垒融凝务；瑙嚣鎏控，安全，奄瞎数据管攫，淹b 瘫曩，生产越造，转黪按溅等等。在这静羲 据流模溅中，单独的数据单元可能悬相关的元组，例如网络测爨，呼叫记录，网硪访问，楱感读数 蹲产生的数据。但是，出予这些数据以大量、快速，隧时闯改燮的数据潦璐式持续剥达，出此产生 了一塑彗璐性蘸耨抟矮究瓣惩。 在数据流出现的应用中，如果把流数据稃艘到传统的数据艨管理系统( d b m s ) 用d b m $ 对数 攥滚进行管理会带来攫多姆送。关键的趣题在于数据藏无酲性豹本质窝赞缝静d b 醚s 存结昝鐾的膏 鞭性靛矛蓐，数据流的持续经、交他性和传统d b m s 的静态性、持久性的矛盾撩续查询( c o n t i n u o u s q u e r i 铭) 煺数据流臌用的典越特征，憾传绩d b m s 并不囊持连续畿询。近似性( a p p r o x i m a t i o n ) 和自适戍 经稿却i l 啊，是慰数摆流避嚣抉速套邂、数据分梗窝数耀采集等掇费鹣关键要素，箍蒋统d b m s 彝主 爨目标魁通过稳寇的查询设计，得到精确的豁案。 对数据漉处避的研究趋逼# 常滔骶嬲领域，嚣前燕辨已经在这方霞群麟了大璧魏研究芏捧，取得 了一定雏戒栗，饕疆开发蹬了一些数据流管理系统纛登。这死每采，著毫静罾舔会议v l d b 禚a c m s i g m o d 等都将数据流作为一个重点问题来讨论，数搬流管理技术正成为国际数榭处理领域的一个 热点阀愈。研究数撂滚管理技术不靛青重要的理论意义，覆基裔藿巨大鲶斑屠蘩最，已经l 起了越 来越多的学者酌蓬视。我们现在j e 在研究基于硬件预处联器的散据流管聪原型系统一一 s e u s t r e a m ，通过基于硬件预处璞器的体系架构，该系统能够处理多条高速数据流上的多用户势 发查诲。 东南大学硕士学位论文 1 1 数据流的出现 第一章数据流管理技术概述 近华来，出现了一类新的数据密集型应用，这类成用中的敬据特征是：大量、连续、滗限、快 速、随时闻改变。这类数攒持续到达，数据达到速度及数据量还有可能是不可预知的，我嚣】把这种 数据称两数据流【l 】 这兴应用出珑在许多成用领域巾，包括传感器网络【1 0 】、交通管理f 3 1 、网络j l 荭控【4 1 、电信数据 蟹理嘲、殴票分辑嘲、生产剿造过程控割等。在这静数摆渡模溅串，单独豹数据警元可能殛摆关豹 元组，例如弼络测量。呼科记录，鸸页访问，传感读数等产生的数据。由于这些数据以大黛、快速、 随时间政变的数据流形式持续到达，以一种流的形式源源不断地进入系统，无法以永久的燕系形式 全部保存下来之菇再行憝纛。困魏，许多已磊豹数据鼯技术难疆应用手数据流，蠹既产生了一些蘩 础性的新的研究问题，有必数据流数据处理技术的研究越来越引起人们的关注。 1 1 1 数据流特链 电话记录。股票报价以及从传黪器读数糕是数据流的铡予。数据流鼹一个实时的、连缝的、潜 在无赛的、有序的( 隐含酶避过到迭时闻或者明确的拜| 闻戳诹的序列。 与传统关系数据库中的数据相比，数据流数据具脊许多自融的特点； 数据实对到运，数据藏速震毒可麓誉霉蘸魏，要求快速郄对豹瞬廑； 系统无法控制数搬元素的瓤达次序； 数据随时闻变化，规模宏大且无界( 即不能预知其最火值) ； 数摇蓥零上采角静是萃速粕摇算法，数据一经楚理缀难再次被敢出； 数据结构化程度较低，需罄多层次化和多维化处理。 1 , 1 。2 数据流模溅 在数摆漉模裂中，数据实对到达，嚣不是缘传统数据库中数据存糖谯可随规谤翘的磁擞或内存 中，它们以一个绒多个“连续数据流”( c o n t i n u o u s d a t a s t e a m s ) 的形式叠达令t 表示任一时间戳， a t 表示谯该时间戳到达的数据，流数据可以寝示成 ， l e - b a b l 。 安瓣数据滚楚按照菜一颓亭静数据颈痔捌，霉能必貔被据捺次。魏乎数据磺霉能葬茨式到达， 数据流可以模拟为元素列袭序列，橼个流项雕以关系冗组或对雾实例的形式存在，( 例如s t r e a m 1 5 1 e d 。项是存储在虚关系中的瞬时元缎，可能横越远程带点并能被水平分割；在基于对象 油i e c b 豁c d ，静横式n i 融f 1 2 1 ) 串数据源j 穰壤磊类型按照分痿籀关的方法模按。 在弗数情况下，流的操作只有在给定的范围内是有意义的。这种窗口模式按照下列三个标准分 类： 1 鞴点移动的方向t 两个固定的端点定义一个同定的窗口；两个滑渤端点( 当新数据项到达时 替换掉恫的数据项) 定义一个滑动窗口；个周定的端点和一个移动端点( 向前或向后) 定义一个 赛标塞秘。 2 物理或是逻辑：按照抵达时间定义物理时间窗。按照元缀的数量定义逻辑( 也称基乎计数的) 窗口。 3 舞新辩闻阏隔：在镣一个薪髭蕴到达辩譬薪评价密口薛黧薪，撬矮理导致了一个虢跃的窗日。 如果更新的时间阀隔大于窗口尺寸，结果是系列非黧叠的滚幼窗口。 2 东南太学硕士学位论文 1 1 。3 数据流查询 数据流上的焱询f l 】与传统数据麾中的查询类型基本上相似，但是有一个主要区别，数据库中的 蠢淘主受是一次豢诲，数据瀛上的粪诲剜更多豹是连续查询。次查询怒撑查诲掇交垂系统摄据 当前的数据集合的快照给出查询的结果。连续查询是指查询随着新数据的到来而不断地返湖查询结 果。与次查询相比，连续查询的特点是长期运行。在数据流管理系统中，连续盘询被注册后，有 嚣释方式终络：一是注餐静奁询串明确匏撂蠡7 查运持续静嚣幸溺，二是耀户弱确恁提窭擞镑该壹诲 的请求，否则随着数据流新的数据元素的到然，该查询将源源不断地返回查询结果。 数攒流上的焱诲可以分为预定义查询和邶摩( a dh o c ) 查询甄种查询形式。鞭定义查询是一类 在任何栩关数据捌来之前程数据流镑理系统穗经定义的查诲。预定义查询通常是连续查诲。预定义 查询注册到系统艏，主要针对数据流后续到来的数据计算查询结果：而即席查询是针对数据流中流 遵熬数攒进行壹弼，帮黯掰史数摄遴露查询。由于系统无法探存数据滚滚逑豹所有数据，蓉统最憝 通过提取和组织流过数据的概要信惠来支持即席查询，因此即席查询一般只能得到近似的套询结果。 1 2 传统髓蹒处理数据流遇到的阔题 簧缓酶数据鼯系统鏊纛处理隶久、稳定豹数据，强镶维护数糖豹完整 生、一致经，其馁能鏊舔楚 高的系统吞吐量和低的代价。其设计目标是维护数据的绝对正确性、保证系统的低代价、提供友好 瓣用户接口。这耪数据库系统对传统的商务耧事务型黩用是有效豹、成功静，然恧它不适会无限、 快速、寅时的数据流应用。 在数据流应用中，如果把连续到达的流数据存储到传统的数据库管璎系统( d b m s ) 中，用d b m s 对话绞数据操撵豹方式对数据漉数撰迸孬攥终是l 霉溺瘫豹。鼹统豹d b m s 劳不楚为抉蘧连续豹存 放单独的数据单元而设计的，而且也并不支持“连续焱询”( c o n t i n u o u sq u e r i e s ) ，而“连续查询” 是数据漉应用的典型特征。另外，“近似性”( a p p r o x i m a t i o n ) 和“自适磁性”( a d a p t i v i t y ) 是对数据 流迸行使速处理的关键要素。 数据流数据的特征要求新的数据处理技术，下面我们开始介绍当前难在研究的一些数据流处理 的技术。 1 。3 数据流管理技术研究现状 目前，国外融经在数据流管理领域开展了大量的研究工作，取得了一定的成果，并且开发出了 一些数撰漉营璎系统蒙跫。爱具典型戆琢麓系统主簧毒s t a n f o r d 大学戆s t a n f o r ds u e a md a t a m a n a g e r ( 简称s t r e a m ) 、b e r k e l e y 大学的t e l e g r a p h 系统和b r a n d e i su n i v e r s i t y 、b r o w nu n i v e r s i t y 与m 工t 联合开发的a u r o r a 系统。其它数据流系统主臻有t a p e s t r y 、t r i b e c a 、n i a g a r a 、c o u g a r ， a t l a s 、f j o r d s 、h a n c o c k 等 6 - 1 铂。 1 3 。1s t r e a m 系统 s t r e a m 系统是由s t a n f o r d 大学开发的一个通用的数据流管理系统 1 5 ，1 6 。它的设计目标是处 理裹速数据漉，支持太量磐发的连续壹诲。在数摄流速和查询受载超出w 获褥赘源戆情况下，系绕 优化内部配置，可以为连续查询提供相对准确的近似缩果。系统内部的多查询优化策略、宥效的资 源分配算法和灵活的调度策略保证了系统的离性能。订限资源和结果近似性的自动平衡是系统最重 要的关键技术。 s t r e a m 系统支持查询语言c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) i s ，用户可以采用c q l 注册数 据流查询，也可以直接输入查询计期。s t r e a m 可按照用户的瘫询需求钟对数据流进行实时的连续 3 东南犬学硕士学位论文 查询；搠户或瘦期程序肉系统注爨蠢询，被注册的套诲将一煮被保留到粪询被显式她注销失止。 s t r e a m 系统中，查询首先被注j 搿。随着新数据的到来。豢询不停璃被执行。c q l 是s t r e a m 系统标准查询语富，它既支持传统的关系操作，又支持流操作。c q l 扩展了s q l 语言，主要表现 在f r o m 子母。f r o m 予句穰含一个霹选戆港磅塞珏秘令取棒子訇。爝韵密日由分割子旬( p a r t i t i o n b y ) ，窗口大小和可选的避虑谓词组成。分割子句把数据分成几组，在窗口内计算每组的德，然后合 并结果，类似标准s q l 中的g r o u pb y 窗口大小由r o w 或r a n g e 确定，如：r a l l g c1 0m i n u t e sp r e c e d i n g 。 取样子舒定义7 鞭样静孬分眈，懿s a m p l e ( 3 ) 。 对乎无限的数据流，s t r e a m 系统通过滑动窗口将其转化为有限的关系元组集合。系统又定义 了一些凝豹运算镣，如i s t r e a m ( 捶入漉) 穰d s t r e a m ( 删除流) ，通过它嚣j 将关系元组转纯为流，为 用户提供连续的畿询结果。 s t r e a m 系统中，每一个查询都有一个独立的查询计划。查询计划由三种不同的结构组成：查 询运舅簿( q u e r yo p e r a t o r s ) 、撵捧簸捌( i n t e r - o p e r a t o rq u e u e s ) 、大缡( s y n o p s e s ) 。一黢来说，敬列 是内存中用来存储数据的块缓冲区。由最大容量限制，因此当数据量超出缓冲隧的最犬容量时， 旧的数据就被丢弃，以便誊纳新数据。队列珂以为多个运算符提供数据源在传统的关系数据库中， 两个关系的连接撵作需要多次的扫播关系表，丽数据流其有瞬辩性，数据不停撼棱更新，为了实现 上述功能，s t r e a m 系统定义了大纲数据结构，用于暂时存储数据。当然，大纲不仅仅用于连接操 作。大缨与敬烈麴重要区剐是：大纲是为菜弹操捧嚣援务弱，雾壁大小瀵裳擐撂操终的霰囊嚣决定。 有效的资源管理是数据流管理系统的荚键技术之一。有限资源和结果近似性的自幼平衡怒 s t r e a m 系统娥重要的美键技术。s t r e a m 系统中，重点关注的是内存的管理。针对内存管理蔓 要采臻? 两种技术：稷撂绕计信蠹释壹诲注耱信惑，瓣太缌透嚣莲壤：采用霞纯稳调囊繁蜷，簿羝 队列所占用的存储空间。在数据流的流速和蠢询负载超出可以获得资源的情况下，可以为连续的赢 询提供横对准确的近似结果。那么如何在有隈的资源f 获得最健的查询结果呢? s t r e a m 系统采用 的主要技术是静淼近骰策略和动态避似策略。其中褶较而言，动态近戳策略是雯有挑战谯的课题， 它比静态近似具有更多的优越性。s t r e a m 系统最盘娶的资源消耗在予大纲和队列。因此主要的动 态近叛方法有：采用拄默撼、参菠拣缩等技术实现犬缨豹压缨；采用动态取群、数摆渡丢羚等技术 减少队列所占用存储空间。 s t r e a m 襞统还有不少不完替的地方。它是一个基于关系模型的集中式数据库，而对于许多数 据流懿凝用，分蠢式整理受为重蘩。因魏s t a n f o r d 丈学正在 噱s t r e a m 系统辩缀秀努摩式系统。 查询计划的形成策略还有待于进一步研究，赞源分配孵法还不能很好的支持近似回答。 1 3 。2a u r o r a 系统 a u r o r a 是由b r a n d e i su n i v e r s i t y 、b r o w nu n i v e r s i t y 帮m l t 联合开发的数据流管理系统，它支 持大萤的触发器，因既又被称为触发器孵络 1 7 a s , 1 9 。 a u r o r a 系统是一个丽向数据流监测应用的数据流管理系统。采用了工作流系统中常用的b o x 珐糍鑫操乎# 麓) a r r o w ( 数据滚彝簿) 模型。用户掇撰壹运嚣疆，将套谗表示必瘗a r r o w 漩淘符连 接起来的若干b o x 操作符组合而成的网络模式，这个模式就是初步查询计訇j 。用户注册一个查询， 就是要嫩成一个捆应的查询计划。豢询计划被简单交换成调度嚣中的不问查询处理队列。调度器的 调度分瓣个屡次： ( 1 ) 确定选择哪个查询进行调度： ( 2 ) 确定每令查询如辩执行，群操作符序列的执移颓序。 a u r o r a 系统采用了批处理技术来降低满度代价和操作符执行代价。系统支持两种方式的批簸 理：对操作符调度的批处理和对元组的批处理。a u r o r a 系统对于大量的实时数描，根据定义的服务 震i ( q o s ) 模型，采搏l o a d s h e d d i n g 技术，必要鞋，掺改壹谗谤翅，翔掉一定静避量受载，班保诞 系统的响应速度。 a u r o r a 系统中最基本的结构是b o x 和8 口q l o w ，每个b o x 是一个处理单元，a n o w 反映了数据的流 4 东南火学硕士学位论文 动方向鞠处理单髭处理数据豹先最次序。查锶是逶过擞形化豹耀户界箍，以b o x 秘a l t o w 形式。这 是a u r o r a 与其它数据流管理系统的显著不同 a u r o r a 系统定义了专用的运算符，以完成各种查询需要，这难要包括f i l t e r 、d r o p ，u n i o n 、w s o r t 、 t u m b l e 、w i n d o w e d 、s l i d e 、l a t c h 、r e s a m p l e 、m 带、o , g j p b y 帮j o i n 等。箕孛，f i l t e r 对辕入藏避 虑；u n i o n 将多个输入流合并为一个输出流 w s o r t 缓冲所有的输入流，并按属性排序输出；c , r o u p a y 按照属性进行分组；j 0 i n 是连接操作；w i n d o w e d 截墩一段数搬流，即圈定时间窗口；s l i d e ，滑动 密墨；r e s a m p l e ，是霉取样；m a p ，浃瓣；t u m b l e 秘l a t c h 运葬符魄较复杂。曩体参抽文献f l s l 。 a u r o r a 系统点持三种谥询模式：连续查询( 实时处理) 、视图和a d 蠢询。第一层结构为连续查 询，该燃的数据被实时处理螽，不缳存。暇务质量规藏( q o ss p e c i f i c a t i o n ) 决定资源摇僻分配绘各 个处理单元。通常，一个粥户查询被分解为辫千个b o x ，b o x 由连接点出增加或删除，连接点可以将 数据暂稃一段时间。第二层结构是视图，是往调度器的控制下物化或者部分物化的视图通过视图 霹鞋鸯嚣俊壹运豹逮发，爨务囊量援藏说明务令视图豹鬟要程瘦。第三层缕摘秀稚查询。a 哇壹谗霹 以在任意时刻附加到连接点，实现对历史数据的查询 归纳起来，a u r o r a 系统具有如下特点：1 ) d a h p 模式( d b m s - a c t i v e ，h u m a n - p a s s i v e ) ：2 ) 适宣签瑷对闻痔捌信怠，镬予获取数据静耨簸和| 蠢德；3 ) 触笈耩居于主簿地位，能够有效搂瑗大蠢 的触发器i4 ) 能够根据负荷和资源的情况，实现精确查询或j 琏似查询；5 ) 具有实时性。可以在线 处理数撼。困她a u r o r a 系统敦主要癔用拜境是：处理豹黠象是数据流；舞要大量的触发嚣；寿较赢 的实时住要求：阻非精确的数据处瓒为主或近似查询为主。 对许多的数据流应用，其本质上是分布式的。因此开发分布式的数据流管理系统是必要的。 a r u o r a * 蓬数a u r o r a 舞基磷豹分毒式数据流镑理系统。罴傣冕文藏【l 鼙。 t e l e g r a p h c q 2 0 , 2 1 是个通用的数据流管理系统，在开放式关系数据库管理系统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 数据流项目野发成果，以p s o u p 系统为查询处理 系统，虢f l u x 系统作为敷载平衡秘容镨处瑗系统。程系统中，注蓊的数据流查询经遂预链理后被 变换成个操作符执行序列，而后交给元组路由选择器e d d y 。 p s o u p 是b e r k e l e y 大学戆t e l e g r a p h 系统的查询处遵器。在p s o u p 中蠢诲首先豢被注瓣，注辑矮 返回用户一个旬柄。接下来不停地执行查询请求。查询语句的一般模式悬：s e l e c ts e l e c t - h s tf r o m 丘o m - l i s tw h e r ec o n j o i n e db o o l e a nf a c t o r sb e g i nb e g i nt i m ee n de n dt i m e 。 鸯诲被努解鸯掰蘸分；s e l e c t - f r o m - w h e r e 子每鞠b e g i n - e n d 子匈。 s e u 把w r o 际w ! r e 子旬为标准查询予句( s q c ) ，存储禚数据结构q u e r ys t e m 中。满足s q c 豹元组记录在r e s u rs t r u c t u r e 中。b e g i n - e n d 子句袋达了一个滑动的窟口，该予句存储在一个独 立的缭鞫w i n d o w s t a b l e 巾。薪的数据流入系统后，被分配一个金局的霓维i d ( 称为m p l e l d ) 和秭 理时间戳( p h y s i c a l l d ) ，然后插入剿数据结构d a t as t r u c t u r e 中，r e s u rs t r u c t m e 中的元组中包含元 鳃豹t a p l e t d 襄p h y s i c a i m 。赣静数搀元缀也霉臻蹬索葵它魏d a t as t e m ，实现连接操箨。注瓣一个 查询后，被分配一个唯一的i d 号( q u e r y l d ) 。标准裔询子旬插入去q u e r ys t e m 中。新查询主动检索 d a t as t e m ，满足蘩件的元组记录到r e s u l ts t r u c t u r e 中。由此可见，p s o a p 将数据和查询都作为流来 箍理。簸终套诲绥莱酶获褥是辗撂b e g i n - e n d 子萄检索r e s u l ts t r u c t u r e ，获彀m p l e l d 瘊，裰攥 t u p l e l d 从d a t as t e m 中得到元组。麓询的执行过程如图l - l 所承 出上述分析可以看出，d a t a s t e m ，q 鼬重y s t e m 霸r e s u l t s t r u c t u r e 是p s o u p 中鹱重要的三神数据 结构。镣个数据流有一个d a ms t e m 数据缩构，用于存储和索g f 数据流，d a t as t e m 采用基于错的索 引结构，每个属性建立一颗树。整个系统有个q u e r ys t e m 结构用于存储和索引查询树结构是 翅来表零壤是s q c 豹元壤，掌翅豹结稳由涎秘：8 二维表结籀，每个f r o m - l i s t 商一个独立二维表 结构，行根据元缀的物理时间戳进行排序，列根据查询i d 来捧序；b 、每个查询带有一个链表，包 含所以满足查询条件的元缀。 5 东南大学硕士学位论文 d a t as t e m q u e r ys t e m l f r m j “ i lp 硼础刈 l 。l 一：l 强1 - 1p s o u p 蠢询鹁执行 瓢p s o u p 的基本实现技术可以者出，p s o u p 将数据和查询郡作为流来处理，因此新数据可班主 动检索融注册的旧查询，新查询也可以查询已经存在的旧数据，而其他数据管理系统要么将数据作 您流，簧么褥蠢璃作为瀛，不能褥= 者嚣嚣孝作为瀛来麓蓬。p s o e p 将套游鞫结果鹣传送努汗楚理。 查询在服务器端不停地被执行，结粜记录在r e s u l ts t r u c t u r e 中，结果记泶在r e s u l ts t r u c t u r e 中，客 户端通过r e s u l ts m m u r e 获锝结果，因此客户端短时阕的离线也不会影蟪查询结果。 爵前p s o u p 傲支持内存操作，它今后静磷究方向麓支持磁盘上靛流存储和研究物佬视黼与淆动 窗口之间的关系。 1 3 4 函内研究情况 量内方匿，遮方瑟静磅究正在起步，文献瓷辩也魄较少，毒些学校秘耩究所燕在对数撰流遂纷 研究。鬟壁大学集中在流数据管理和挖掘的研究，中科院计算帆技术研究所试图掏建一个筒向两络 信息安全的数据流计算模型，重点掰f 究的一艟问题有网络数据沉的获取、网络数据流建模、数据流 套诲模蘩、数据漉计算葬法等，毪钓懿磊标燕在这个模型静基稿上并发您具体的霄显示囊静宏霾羁 络监控应用系统。我们现程正在研究基于硬件预处理器的数据流管理原越系统s e u s t r e a m ，该系 统基于硬件预处理器的体系架构，酝够处理多条高速数据藏上的多用户劳发查询。 1 4 主要研究工作和内容安捧 本文主要围绕数据流管理系统设计和查询处理方赋进行研究，本文的主要研究工作有以下几个 方瑟： 1 设计了连续流查询谱言x - s q l 。由于数据流应用的特殊蒲求以及数据流本身的特点，使得数 据流上的查询与传统关系上的查询镩根大的不同。作为数据流管理系统的一个重隳组成部分，我们 设计了流查询语蠢x - s q l ，逶建类纛鬟s q l 瓣语法鞠游动密西络舍，x s q l 髓支持数据流土的连壤 查询语义。同时，x - s q l 去除了s q l 中的些不需疆的元素，使得语言本身简沽、易写，语义氯 加明确。 2 设计实现了x s q l 的编译嚣，该编译器能够按照用户输入的弗教旋询遴行分析处瑗，并生成 系统前端进行数据流处理所需要的树始化状态参数和指令序列。 全文豹缍织魏下： 第一章介绍了课题的研究背景，以及数据流管理系统研究的主要内禅和国内外的研究现状。第 二章对蒸于硬件颊处理的的数据流镣理系统进行了介绍。第三章介绍了可以支持连续查询语义的流 套诲语蠢x - s q l 。第露章给密了x - s q l 编译器的设计过翟。第五章是对本文的慧绪。 6 东南太学硕士学位论文 第二章基于硬件预处理的数据流管理系统 数据流的流动性和无限性和计算资源的有限性之问的矛盾，使得如何提高数据处理速度成为数 撰漉管璞系统的关键。现簌的大多数据流管理系统都是基于软件实现的，会存在定的处理延迟， 在数据流速达副一定程度的时候，簸理速度就会成为系统性蘸簸颈。为了能够快速及时缝娃理高速 数据流，我们提出了一种新的数据流处理系统体系结构采用硬件预处理的并行数据流管理结构。 本章主蘩奔绍基 ：嫒棼豹数据藏譬壤系统s e u s t r e a m 戆捧系缝梅窝基于f p g a 瓣数据藏壤处理器 的设计。 2 1 数据流管理系统( d s m s ) 2 1 1d s m s 懿基本霈求 数攒流和连续查询的特性要求数据流管理系统必须具鍪下然勘能： 数据模式和查询语义必绥允许基于磁序和萋乎孵间的操作，鲡程5 分钝j f 琶寸大小的移动密 口上的蠢询。 长孵阉遮行魏查谗在执行生奔期孛掰能会遇到系统条绺约变化，铡絮漉速率豹交诧。嚣要设 计具有自适应性的查询计划和调度繁略。为确保可伸缩性，需婺负载均衡。流鹰询计划可 能不会使用必须在结果产嫩之前消耗完全部输入的模块化操作。多个近似连续查询的共享 魏行是躲要翡。 在线流算法是受限的，只能遍扫描数据。不能存储垒部的流暗示着需簧使用近似概要结 构，称为大纲固州学) 摘要( d i g e s t s ) ，作用在概要上的查询可糍会返回不糖确的结果。 箍控实孵数据流的应用必须快速晌臌不弼寻常的数据德。为即时准确地螭应用户蕴询，通 过服务质量保证( q o s ) 的梭测指导系统调度和负载均衡的策略。 2 2s e u s t r e a m 体系结构 为了能够快道及时地处理高速数据流，对数据流采用专门硬件进行预处理是个很好的选择。 基于硬件预处理数据流管理系统s e u s t r e a m 并不仅仅依靠查询优化、系统调用等传统手段来提高 兹疆漉翁建理速菠，磊是考虑一静金掰静体系结鞠来这舞蛋静。蘧2 - 1 怒基予骥 串颈处理数据流譬 理系统的体系结构示意圈f 3 4 】。 基予硬孛 预处理的数据藏管理麓统分为强部份：耱端硬处理器秘盾端数据引擎。兹端鞭处理器 负责对进入系统的数据流进行预处瑗，包括通过系统精端传送米的控制命令进行状态裙鳓饱，对蕺 据流数据进行滤波、数据压缩和数据加标记处理等。前端预处理器采用软硬件协同的方式以提高数 撂整理逮痊。羟避蘸壤处壤之矮熬数攥透过嬲终赞往矮墙，经避数据渡翔分控剩器，在势行调痘嚣 的控制下，根据用户查询请求得出的调度策略动态划分数据流咒组，在并行查询执行器的控制f 由 各自的处理器并行地完成凌询处理。 在系统豹后端数据 l 擎。尾户建交静鸯诵经过套溺语法分轿嚣处理麓保存在注嚣查询缓冲孛， 用户提交的查询经过词法、语法及语义分析，并进行焱询优化，得到查询抽象语法树，并针对数据 流预处瑗器对抽象语法孛譬避章亍处理，生成箕掰霪的控制信息，经过查询输出控制嚣下载到魏端硬件 查询处壤模块。 系缆后端的数据引擎童要负责连续查询的语法分析、并行咨询计划嫩成、将预处理过的元组划 分蘩不颡豹数据缓存，对并存憝理褥到憨套谗结采豹遴行最爱续装势发及受载均据秘骧务簇量监控 7 东南犬学硕士学位论文 等功能。系统兹端的查询预处理器接收后端数据引擎的查询请求，对多路数据流采集器传送来的流 数据进行处理，辩将处理结果送交鬣后端查询号l 擎。 多絷流 多豢澎多禁流 图2 - l 萋于硬件j 甄处理的数据流管理系统体系结构豳 2 3 基于f p g a 的数据流预处理器 2 3 1 硬件预处理器的研究背景 数据淀其毒犬董、获、不可聂麓、无疆豹特征，这决定了对数据溅熬壹谗灵缝是实醇懿或者避 似实时的。而目前大多d s m s 的实域都是熬予软件实现的，软件实现具有灵活稷度高的特点，但悬 处理速度还是有一定限制，当数据流速度在一定范围内的时候照然可以正作的很好，但是当数据流 速达刮一定静程凌班后，楚理速庭辘会成为糕颈。魄较可行酶个解决方法是设计专门的硬箨，耱 数据流处理的一烘操作放刹硬件中去实现。 s e u s t r e a m 由一个舞端数攥弓l 擎窝一嫂藏端数摆渡颈处理器缀成。翦端接牧扶后端擐据注珊 查询生成的控翎信息，然詹报据控制信息对数据流进行处理 2 3 。2 蒸手f p g a 豹数撵滚颈始毽器豹髂系绩橡 数搬流预处理器的作用是对进入系统的数据流进行预处理，主要是通过系统后端传送来的控制 禽令进箨获态裙鲶纯，黟黢撂谩数蕹进孬滤波、数摄艇缩垂l 羲攥糖标 若处理。魏端羲蝰璎嚣采霜软 硬件协同的方式以提高数据处理速度。经过前端处理之后的数据通过网络传往届端。数槲流预处理 器的体系结构见嬲2 - 2 。 网络控翩模块负责数据流预簸瑾嚣与静养的逶讯动能，包括； 从数据流采集器传送过来的多个源数据流 麸系统聪溃籍遴过来豹壹询控暴参令 8 东南火学硕士学位论文 向系统鼷端提交焱询结果流 目前该预处联器已经w 以完成多条数据流查询的连接操作对于投影、选择和聚集等撵作将在 下一步的工作中实现。 窝2 - 2 数据巍预处理嚣盼体系缩鞫 2 3 3 数据流预处理器逐接算法及其实现 茸祷大多数擎者硪究静数据流建接算法鼯是基予软件实现的，直接丽磺俘实瑗会有穰大的困难。 目前数据流预处理器已经w 以实现多数据流、多查询的并发连接处理。其所采用的算法是适合用硬 转实现勰流连接方法m 3 j o i n 瑟l ，3 2 l 。算法玖多线程蒡费巍类 娃鼹鑫器静处理方式绦迁数据麴高速处 理。同时通过先分解连接请求后组合部分连接结果的方法保证逑接的高效率和高共享度。 m 3 j o i n 的基本步骤：( 1 ) 将原始数据流既组( 图2 - 3 ) 插a 到缓冲区( i n s e r t ) ；( 2 ) 该元组依照赂由表 避天连撩区连接( 搿。如) 嵇潮臻各连接区孛进瓣瞻愁缝( i n v a l i d a t e ) 。 图2 - 3 是数据流元组的结构，包括路由标记( r o u t et a g ) 、连接因予标记( j o i nf a c t o r t a g ) 、旧 对闻戮( o i dt i m e s t a m p ) 、叛对闽觳( n e wt t m e s t a m p ) 和数据域( d a t af i e l d s ) 缀成。 e l d s 臻2 3 元缀络撺 算法m 3 j 0 i n 的实现架构r o u j o i n 由四部分组成；输入缓冲n ( i n p u tb u f f e r ) 连接路由表( j o i n r o u t i n gt a b l e ) ：连接区( j o i n a r e a ) ：输出缓冲n ( o u t p u tb u f f e r ) 。 其中，连接送由窗口缓冲区( w i n d o wb u f f e r ) 、连接因子区( j o i nf a c t o r a r e a ) 、因子组食区伊船自吖 c o m b i n a t i o na r e a ) 和探测冗组缓冲睡( p r o b et u p | eb u f f e r ) 组成。该架构是数据驱动的，各区域仅对 搴建鹣数据撬露撵痒，然鬃交绘- f 一区域继续处理。壤入缓狰送将嚣鸯纛始藏元组按颓廖存敷，一 旦处理涟度滞后时可以缓冲。流元组由连接路由表引导至合适的连接区执行连接操作。窗口缓冲醒 存救相陂流时间锚内的原始流元组，这些数据可以按时阐顺序存放或再缓关键字建索引，以提高查 找速瘦。另井为避免更薪释元缒移渤，密西缓；孛区设谶为循环酞弼。热袋深测元缀缓洚区稃在数撂， 则按顺序取出一咒组与窗口缓冲区的元组执行连接因子区所有因子操作，将结果标记在元组的连接 因子标记鲢( j o i nf a 咖t a g ) ，然后壤据元缎连接翦路幽标记( p r e - j o i nr o u t et a g ) 、连接因予标记位和 因子维含区内容设置连接腊元缰的路由标记。输出缓冲区存放连接后的待输出元组，并禳据各连攘 的最大简口确定是否将结果输出。 9 东南火学硕士学位论文 2 3 3 1 槊构r o u j o i n 初始化 翔2 4 实现架掬r o u j o h k p r 。j o 嘶t nc o l b i m t i * 麓：甓 算法2 1r o u j o i n 初始化算法 输入：势笈连接谤求； 输出：r o u j o i m 包括连接路融表、连接因子区、因子组含逸和输出缓冲区中的数据。 ( 1 ) 按先与后或规范连接条件表达式。一般情况下与操作比或操作减少结果元组，通过等价转换将与操 器f 接。 ( 2 熵或操作的连接请求分解为等价的多条请求。 渤对嚣或操作连接因子接参与连接流归缎。 ( b ) 对簿一组重霉一连接请求，系统分弱齄壤新的请求，足在输斑结莱辩将其合势。 ( 3 煨取所有不同连接因予，建立连缀请求表。 4 ) 掇撂连接请求裳设萋连接疑子嚣，壤入相关因子。 ( 5 ) 根据连接因子和连接请求表设置闲子组合区的连接游标记、缝合及述接后路由标记。 ( 6 ) 设置谢e l 缓冲区大小。采用l a r g e 、b r m d o wo n l y ( l w o ) 方法。将缓冲区大小设成中所有因子窗口 静最大壤。 ( 7 ) 根据涟接请求袭构造连接路由表，采用规则； a ) 原始凭组要插入到相应的窗口缓冲区，其它爱0 ； ( b ) 连接瓣元维改燮路由标记，该标记阉对存在于连接黯由表 ( c ) 需要探测的元组设置相应连接区标记，否则置o ： q ) 元组符合莱套谗请求慰设置其编号，秀刘受0