（计算机软件与理论专业论文）实时数据流系统中调度算法的研究与实现.pdf

东北大学硕士学位论文 摘要 实时数据流系统中调度算法的研究与实现 摘要 随着信息处理在通信、工业生产、商务处理等领域的广泛应用，数据已不仅仅拘泥 于文件、数据库等传统的静态形式，一种连续、无界、不定速度的数据流已经出现在越 来越多的应用领域，如：网络监控，传感器的数据处理，生产线管理，股市信息分析等。 特别是在数字化、智能化的嵌入式系统中，需要对实时数据进行复杂、高效的分析和处 理。对流式数据的管理是这些应用领域的核心问题，由此兴起的支持高性能实时计算的 流式数据管理技术正在成为数据库领域新的研究课题。 在一些关键应用中，要求实时处理大量、连续到达、快速甚至爆发的数据流，在截 止期内给出实时查询结果。由于系统资源( 如c p u 速度、内存容量等1 限制，特别是在流 爆发时，不可能实时处理完数据流上的所有数据，而是尽力处理尽可能多的流数据，以 获得高质量的近似查询结果。 提供数据流管理功能的系统称为数据流管理系统( 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 ) ，而调度策略是影响系统的整体性能最为关键的因素之一。在动态爆发的数 据流环境中，如何设计实时调度策略，保证应用的实时需求，并获取高质量的近似查询 结果，成为目前学术界和产业界关注的热点问题。 本文讨论了当有截止期实时约束以及存在有流爆发的数据流环境中，如何设计高效 的固实时任务调度策略，以最小化截止期错失率( s d m r ) 的问题。首先给出了固实时 模型定义，并提出批划分单位，作为准确划分批任务的依据。给出了一种基于t j c k 的 基本批任务调度方法，称为b a s i c t i c ks c h e d u l i n g ( b t s ) 方法，有效降低了系统开销。 但b t s 方法以统计计算( 如服务开销、操作符选择度估计等) 作为任务执行依据，可 能导致无效的执行，并且不能适应于流速时变的流爆发特性。通过克服统计计算的不足 并动态控制t i c k 批大小、消除流速时变性造成的忙等待，进而提出了一种白适应的精确 批处理策略，称为a d a p t i v et i e ks c h e d u l i n g ( a t s ) 方法，实现了最小化s d m r 。理论 分析和实验表明，在目前所有的批处理调度策略中，a t s 方法是最有效的。 关键词：数据流；实时调度；截止期；t i c k 东北夫学硕士学位论丈 r e s e a r c ha n di m p l e m e n t a t i o no fs c h e d u l i n g s t r a t e g i e si nr e a l - t i m ed a t as t r e a m s a b s t r a c t w i t he x p l o s i v ea p p l i c a t i o n so fi n f o r m a t i o np r o c e s s i n gi n c o m m u n i c a t i o n ，i n d u s t r y m a n u f a c t u r i n g ，b u s i n e s sp r o c e s s i n ga n dm a n yo t h e ra r e a s ，m o r ea n dm o l ed a t at a k et h ef o r m o fc o n t i n u o u sd a t as t r e a m sr a t h e rt h a nf i n i t es t o m _ 虹d a t as e t e s p e c i a l l yi ni n t e l l i g e n td i g i t a l e m b e d d e ds y s t e m s ，d a t an e e dt ob ee f f i c i e n t l yp r o c e s s e di nr e a lt i m e ，i n d e e ds t r e a md a t a m a n a g e m e n ti st h ek e yo ft h e s ea p p l i c a t i o n s ，s ot h ed a t as t r e a mm a n a g e m e n tt e c h n o l o g yf o r h i 曲一p e r f o r m a n c er e a l t i m ec o m p u t a t i o ni sb e c o m i n gan e wa n dp o p u l a rt o p i ci nd a t a b a s e r e s e a r c ha r e a m a n ys t r e a m b a s e da p p l i c a t i o n sa r ed e a d l i n e s e n s i t i v ea p p l i c a t i o n s ，i nw h i c he a c hq u e r y h a sa s p e c i f i c r e a l t i m e p e r f o r m a n c ee x p e c t a t i o n h o w e v e l d u et ot h er e s o u r c e l i m i t a t i o n ( s u c ha sc p u ，m a i nm e m o r ya n ds oo m ，e s p e c i a l l yo v e rb u r s t i n gd a t as t r e a m c i r c u m s t a n c e ，i ti si m p o s s i b l ef o rt h es y s t e mt op r o c e s sa l lt h ei n c o m i n gd a t a u s u a l l y , t h e s y s t e mw i l lt r yt op r o c e s sa sm a n yd a t aa sp o s s i b l et oa c q u i r eh i g hq u a l 磅q u e r ya n s w e r s d a t as t r e a mm a n a g e m e n ts y s t e m s ( d s m s ) a r ed e v e l o p e dt oa d d r e s st h e s ea p p l i c a t i o n s a n dt h es c h e d u l e ri so n eo ft h ek e y c o m p o n e n t si nad s m s h o w t od e v e l o pa ne f f i c i e n ta n d e f f e c t i v es c h e d u l i n gs t r a t e g yt om e e tt h ea p p l i c a t i o n s r e a l - t i m er e q u i r e m e n t sa n da c q u i r eh i 曲 q u a l i t yq u e r ya n s w e ro v e rt i m ev a r y i n g ，b u r s t i n gd a t as t r e a m sh a sb e e nr e c e i v e dg r e a t a t t e n t i 0 1 1 i nm a n ys t r e a m b a s e da p p l i c a t i o n sd e m a n d i n gd e a d l i n e w i t ht h ec h a r a c t e r i s t i c so f b u r s t y a r r i v a lr a t e sa n dr e a l t i m ep e r f o r m a n c er e q u i r e m e n t s ，h o wt o d e s i g nah i g hp e r f o r m a n c e f i x e d t i m et a s ks c h e d u l i n gs t r a t e g yt om i n i m i z et h es t r e a m i n gd e a d l i n e m i s s e dr a t i o ( s d m r ) i sd i s c u s s e di nt h i sp a p e r t oa d d r e s st h ec h a l l e n g e s ，w ef n - s tp r e s e n t0 1 1 1 f i x e d t i m ep r o c e s s i n g m o d e la n dg i v et h ed e f i n i t i o no fs c h e d u l i n gg r a n u l a r i t y ( t i c p ab a t c hs c h e d u l i n ga p p r o a c h ， n a m e l yt h eb a s i ct i c ks c h e d u l i n g ( b t s ) ，i st h e nd e v e l o p e d ，w h i c hc a ne f f e c t i v e l yr e d u c et h e s y s t e mo v e r h e a d h o w e v e r , b t ss t r a t e g ys h o w sw e a ka d a p t i v i t ya n dc a l l ts a t i s f yd e a d l i n e r e q u i r e m e n t sa c c u r a t e l y w et h u sd e v e l o pan o v e lp r e c i s eb a t c h i n g t e r m e da sa d a p t i v e 乃办 s c h e d u l i n gat s 3 ，w h i c he f f i c i e n t l yo v e r c o m e st h ed e f i c i e n c y i n d u c e d b y s t a t i s t i c a l c o m p u t i n g ，d y n a m i c a l l yc o n t r o lt h et i c ks i z ea n d a l s oi nt h ee x t r e m ea d a p tt ot h et i m e v a r y i n g d a t aa r r i v a l r a t e t h ea n a l y t i c a ta n de x p e r i m e n t a lr e s u l t ss h o w st h a tt h ea t ss t r a t e g yi st h e m o s te f f i c i e n ta n de f f e c t i v ei na l lb a t c h i n gs t r a t e g i e s k e yw o r d s ：d a t as t r e a m s ；r e a l t i m es c h e d u l i n g ；d e a d l i n e ；t i c k i l 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：政；彦坪 日 期：“辫，闫留 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字期： 东北大学硕士学位论文 第二章相关工作 第一章引言 本章首先给出当前数据流研究的概述，然后详细给出当前的研究现状，介绍了数据 流研究中的一些典型问题，之后给出本文研究的课题背景，最后给出本文结构 1 1 数据流研究的概述 随着信息处理在通信、工业生产、经济信息处理等领域的广泛应用，数据已不仅仅 拘泥于文件、数据库等传统的静态形式，而是以一种流的形式存在，本文称之为数据流 【b s 0 2 。 在数据流这种应用模型中，单一的数据元素是元组，其形式类似于关系数据库中数 据表里的行，但它们都是以单独的形式存在于流当中，例如通话记录、网页访问、传感 器探测值等等。在这些实际应用中，几乎所有的数据都不是按照传统数据库的方式统一 存储为持久稳定的关系提供给用户使用的，而是以一种连续、无界、不定速度的流的形 式在线到达的( 交通管理 h m 0 4 、传感器网络i s 0 2 等等) 。不仅仅原始数据是以这种流 的形式到达，而且在对这样的数据流进行各种处理( 主要是查询操作) 之后所得到的结 果也同样可能是流的形式，通过各种方式传递给查询者( 用户或计算机) 或继续传递给 下一个应用来使用。另外以在线的方式对流进行挖掘分析处理也是一个重要的研究与应 用的方i 句 y g 0 4 1 。 在实际生活中，数据流应用非常广泛，例如： 网络监控和交通工程； 电信通信记录； 网络安全： 金融应用； 传感器网络； 制造工艺过程： 网络日志和网页点击流。 在数据流模型中，部分或全郡数据都是以一种连续的流的形式在线到达的r j 传统 的关系模型相比，具有以下个之处： 流的数据圯索存线到哒： 系统无法摔制数据几素刊达川页i j ： 数据流司能是屯界的 东北大学硕士学位论文 第二章相关工作 数据元素一经流过就不复存在，除非进行特别的处理( 如将数据元素存储在内 存当中) ，否则无法轻易重新使用这些数据元素。 在上面提到的所有的应用中，简单的把到达的数据载入传统的数据管理系统d b m s 以进行处理是不可行的。传统的d b m s 不是为快速连续的数据载入而设计的，它主要 适应商业数据处理的需求而产生豹，因而，它也有很多局限性。 表1 1d b m s 和d s m s 的对比 t a b l e1 1c o m p a r i s o nb e t w e e nd b m sa n dd s m s d b m sd s m s 操作对象持久稳定的关系瞬间数据流 查询性质一次性查询连续查询 存储方式随机存储顺序存储 存储空间极大的磁盘存储有限的主存 时间粒度仅关注当前状态重点在历史和到达时间 存储特性被动存储主动存储 数据速率 相对较低的修改速度可能是多g b 字节的高速 实时性非实时服务实时服务 精确性数据集上的精确查询历史查询，近似查询 存储计划存储计划由查询处理器和数据到达速率及其属性不 物理数据库实现产生可预计并可变 针对普遍存在的流式应用，本文引入了数据流管理系统( d s m s - - d a t as t r e a m m a n a g e m e n ts y s t e m ) 专门处理数据流这种新的数据形式。本文把传统的数据库管理系 统与数据流管理系统相比较，如下表1 1 所示。 冷回 图1 1 关系数据库管理系统模型 f i g 1 1m o d e lo fr e l a t i o n a ld b m s 在传统的关系数据库应用中，数据是持久稳固的。全部的数据都保存在外存，当需 东北大学硕士学位论文第二章相关_ t - 作 要进行查询处理的时候可以得到全部需要的数据，即使内存不能全部装载所需的数据， 仍然可以分批的将这些数据调入到内存中进行查询处理。并且通常情况下，数据库中包 含的是无序的静态数据集，这些数据的插入与删除操作相对于查询的插入与删除是很少 的，即查询的更新频率要远远大于数据的更新频率。用户可以随时注册一个查询来获得 自己关心的结果。传统数据库的查询处理模型如图1 1 所示。 e = 匕= 匕 亡 = 输入数据 眄闶 注册查询 o暮 返阐结果 令匕今 亭 亭 过期数据 圈1 2 数据流处理模型 f i g u r e l 2p r o c e s s i n gm o d e lo f d a t as t r e a m 数据流管理系统d s m s 如图1 2 所示。数据在线到达之后，并不是存储到磁盘上， 而是直接进入到流查询处理器当中，流查询处理器即时地对流数据进行处理。当用户或 应用注册一个查询之后，流查询处理器将保持这个查询直至其失效为止( 查询到达结束 时间或用户显式注销) ，也就是说用户注册的查询始终保持有效状态，这也就是连续查 询的形式。数据流入流查询处理器之后，流查询处理器直接根据当前注册的查询对数据 进行操作，所产生的结果同样以流的形式返回给用户或应用( 当然也可以将结果保存成 为关系形式，不过这并不是数据流管理系统的主要工作) 。当系统资源不足时，则流查 询处理起根据需要考虑返回近似结果，主要方法是返回部分结果i v j 0 2 或对需要处理的 数据作l o a ds h e d d i n g n u 0 3 1 。 在数据流上注册的查询可以有多种形式： 预定义查询：在所需查询的数据尚未到来之前即注册的查询； a dh o e ( 即席) 查询：查询范围比较自由的一种查询，它可能对某些已经成为 历史数据的流数据进行查询； 激活式查询：也是预定义的查询，但只有在被系统或用户调用时才开始的查询。 查询返回的结果也有多种形式： 一次性：将查询得到的结果一次性返回给用户或应用： 蚤 东北大学硕士学位论文 第二章相关工作 基于时间事件：在特定时间或特定事件发生时向用户或应用返回结果； 周期性：将查询得到的结果周期性返回给用户或应用： 连续性：每当得到结果便立刻返回给用户或应用，即在查询有效期问连续地将 结果以流的形式返回或保存为关系数据。 1 2 研究现状 目前，数据流的研究已经得到了越来越多的关注，并出现了一些初具规模的研究原 型系统：b r a n d e i s ，m i t 和b r o w n 几所大学联合设计的a u r o r a d d 0 3 ，s t a n d f o r d 大学的 s t r e a m r j 0 3 ，n i a g a r a c q m o o ，u cb e r k e l e y 的t e l e g r a p h s 0 3 ，t r i b e c a m a 9 8 等， 它们都对流式应用中的一些问题进行了或正在进行探讨。作为一个新兴的研究课题，数 据流研究中仍有许多开放的问题需要进一步的探讨和解决，归纳为如下几点： 数据流模型； 数据流查询语言； 数据流上的适应性查询处理； 数据流处理中的调度策略； 数据流系统中的负载调整： 数据流查询中的近似计算： 分布式数据流处理。 另外，数据流挖掘也是一个相关的课题。随着流式应用的发展和广泛应用，将会有 更多更具挑战性的问题不断出现。下面就其中的几个主要问题进行进一步阐述。 1 2 1 数据流上的适应性查询处理 q u e r y ：| | i | 户弋 刘导 q u e r ye x e c u t o r 图1 3 数据流查询处理结构 f i g 1 3s t r u c t u r eo f q u e r yp r o c e s s i n g o v e rd a ms t r e a m 数据流系统的查询处理机制如图1 3 所示，查询处理器作为查询处理系统的核心部 4 昌弓 东北大学硕士学位论文第二章相关工作 分，输入的数据流由系统接收后进行预处理，然后输入查询处理器；查询的注册可由用 户提交查询语句，经语法分析后得到查询计划，也可由有经验的用户自行设计查询计划； 查询处理器根据注册的查询对流进行操作，将得出的结果返回，处理过后的流交给系统， 系统根据需要进行必要的保存或直接丢弃。 大多数系统在查询处理过程中采用的方式是元组到达后直接进入查询处理系统，系 统使用查询计划中的操作符处理元组。如t e l e g r a p h c q 系统和a u r o r a 系统等。 某些系统在查询处理的过程中还可以兼顾关系和流，在系统中定义了流与关系相互 转换的操作，在查询处理及结果输出的过程中也进行必要的流与关系之间的相互转换， 使查询处理过程中流和关系可以统一起来。如斯坦福大学的s t r e a m 系统。 流式数据的查询处理有两个特性：实时性和适应性。简单的说，实时性是指系统需 在规定的时间内对查询处理任务有所响应；适应性是指系统能随着数据特性和系统属性 的交化动态的调整查询执行的行为，以在满足实时性要求的前提下完成查询任务。适应 性查询一直是传统数据管理中的一个热点和难点，随着数据库系统的演变和发展以及查 询需求的不断提高，适应性查询的内涵也不断丰富，特别是在流式数据这一新型的数据 形式下，适应性查询就有了更重要的涵义和作用。 【h f o o 一文中指出，具有如下属性的系统可以称作为适应性查询处理系统：( 1 ) 系统 从周围环境中获得信息，( 2 ) 系统根据获得的信息确定自身的行为，( 3 ) 这个处理过程是 周而复始的进行的，构成了一个环境和系统行为之间的反馈环。其中第三点是适应性系 统区别于一般做静态优化的系统的不同之处。由此可以看出适应性系统的三个特殊的属 性：( 1 ) 适应性的频度，即系统获取信息和更新行为的频获取信息和更新行为的频度( 2 ) 适应性的影响，即为提高适应性系统行为有哪些变化( 3 ) 适应性的程度，即反馈环持续 的时间。 在对数据流这一不确定性强、实时处理要求高的新型数据形式处理中，适应性查询 就更显得尤为重要。系统只有周而复始地、迅速地从流数据以及系统中获得查询性能相 关的信息，并以此指导自身的后继行为，才能完成对流式数据的连续查询要求。可以看 出，数据流上的连续查询完全符合了前面提到的适应性查询的性质。 比较典型的流处理系统中的适应性查询实例是u cb e r k e l e y 大学开发的 t e l e g r a p h c q 系统中的适应性查询模块e d d y a h 0 0 。e d d y 的特点在于它能够对每个元 组动态的选择路由，使得查询适应性的粒度达到了元组的粒度。e d d y 的适应性技术主 要体现在它对元组的路由是随着系统性能、查询特性等情况的动态变化而变化的。其它 数据流处理系统中也都从不同的角度出发来实现适应性查询的目标。 实际上，下面将要介绍的调度策略，负载调整以及近似计算都是数据流上适应性查 询机制的具体体现。 东北大学硕士学位论文第= 章柱关_ 二作 1 2 2 数据流处理中的调度策略 调度优化是一种积极的优化策略，是影响系统的整体性能最关键的冈素之。理想 的调度策略应当能够保证：( 1 ) 在资源一定的情况下获得最优的性能；( 2 ) 及时发现系 统过载，井触发相应解决机制( 如突发流量处理) ；( 3 ) 保证特定查询的q o s 需求；( 4 ) 部署简单，操作方便 j c 0 4 】。在部署调度策略时，主要性能指标包括：对元组的响应时 问，内存需要量，吞吐毒，精确度等。在实施过程中，系统为达到各种性能指标的要求 会发生冲突( 例如较小的相应时间必然要求较大的内存) ，所以对实际系统而言，寻找 各种指标的平衡至关重要。具体的d s m s 会根据数据流的特点和要达到的目的，以部分 牺牲其他性能为代价，选取其中的一个或一部分性能作为主要衡量指标。 s t r e a m 系统的中央调度器采用了种链式调度策略 b b 0 3 1 ，最终使得系统运行 利最大内存使用量虽小化。从本质上来说，链式调度是从把操作符处理代价和操作符的 选择度结合起来考虑的一种调度策略，使得操作符的输入队列使用的内存尽量的少。 a u r o r a 系统的采用一种基于q o s 的调度策略 c c u 0 3 ，调度器在系统运行过程中不断应 用动态的两层调度策略：一是确定选择哪个查询进行调度，即操作符序列的选择；二是 确定每个查询如何执行，即操作符序列的顺序确定。文献 j c 0 4 提出了一种基于算子路 径的调度策略p c s ( p a dc a p a c i t ys c h e d u l i n g ) ，通过为具有最大能力处理的路径安排进 度的方式来达到是小化响应时间的目的，并在其基础上，综台c h a i n 策略的优点，提出 了s e g m e n ts c h e d u l i n g 策略，通过将算子路径分解为若干片断，在处理占用空间控制方 面取得了较好的效果。 c h m n 策略虽然通过对算子运算次序的调整，有效的解决了内存占用问题，但这是 建立在系统有足够物理资源的假设基础上，并且只处理单条输入数据流的查询，当突发 流量维持较长时间时，系统的响应时间会延长并有可能产生饥饿的现象 8 8 0 3 。虽然 p c s 在运行过程中采用了基于输入流大小致的假设的内存优化方法，但是仍然在内存 占用方面的性能要比c h a i n 策略差。s e g m e n ts c h e d u l i n g 策略虽然在一定周期可以比 c h a i n 策略释放更多的资源并有较好的响应时问，但在具体运行时所占用的空间要大于 c h a i n 策略。 从 j c 0 4 i 给出的试验结果看，在响应时间和占用内存方面，三种调度算法各有所长， 但总体而言，c h m n 策略的吞吐量要略低于其他两种算法。 1 2 3 数据流系统中的负载调整 当突发流量超过系统的处理能力，如果不采取相应的措施进行负载调整，会导致整 个系统的吞吐量和响应时问都恶化，系统应能够通过调整查询处理策略，适应性地满足 它的实时处理要求。负载调整以多维q o s 函数为前提，主要采崩两种方法对系统的负载 它的实时处理要求。负载调整以多维o o s 函数为前提，主要采用两种方法对系统的负载 东北大学硕士学位论文 第二章相关工作 1 2 2 数据流处理中的调度策略 调度优化是一种积极的优化策略，是影响系统的整体性能最关键的因素之一。理想 的调度策略应当能够保证：( 1 ) 在资源一定的情况下获得最优的性能；( 2 ) 及时发现系 统过载，并触发相应解决机制( 如突发流量处理) ；( 3 ) 保证特定查询的q o s 需求；( 4 ) 部署简单，操作方便 j c 0 4 1 。在部署调度策略时，主要性能指标包括：对元组的响应时 间，内存需要量，吞吐量，精确度等。在实旄过程中，系统为达到各种性能指标的要求 会发生冲突( 例如较小的相应时间必然要求较大的内存) ，所以对实际系统而言，寻找 各种指标的平衡至关重要。具体的d s m s 会根据数据流的特点和要达到的目的，以部分 牺牲其他性能为代价，选取其中的一个或一部分性能作为主要衡量指标。 s t r e a m 系统的中央调度器采用了一种链式调度策略 b b 0 3 ，最终使得系统运行 时最大内存使用量最小化。从本质上来说，链式调度是从把操作符处理代价和操作符的 选择度结合起来考虑的一种调度策略，使得操作符的输入队列使用的内存尽量的少。 a u r o r a 系统的采用一种基于q o s 的调度策略 c c u 0 3 ，调度器在系统运行过程中不断应 用动态的两层调度策略：一是确定选择哪个查询进行调度，即操作符序列的选择；二是 确定每个查询如何执行，即操作符序列的顺序确定。文献 j c 0 4 提出了一种基于算子路 径的调度策略p c s ( p a t hc a p a c i t ys c h e d u l i n g ) ，通过为具有最大能力处理的路径安排进 度的方式来达到最小化响应时间的目的，并在其基础上，综合c h a i n 策略的优点，提出 了s e g m e n ts c h e d u l i n g 策略，通过将算子路径分解为若干片断，在处理占用空间控制方 面取得了较好的效果。 c h a i n 策略虽然通过对算子运算次序的调整，有效的解决了内存占用问题，但这是 建立在系统有足够物理资源的假设基础上，并且只处理单条输入数据流的查询，当突发 流量维持较长时间时，系统的响应时间会延长并有可能产生饥饿的现象 b b 0 3 1 。虽然 p c s 在运行过程中采用了基于输入流大小一致的假设的内存优化方法，但是仍然在内存 占用方面的性能要比c h a i n 策略差。s e g m e n ts c h e d u l i n g 策略虽然在一定周期可以比 c h a i n 策略释放更多的资源并有较好的响应时间，但在具体运行时所占用的空问要大于 c h a i n 策略。 从 j c 0 4 给出的试验结果看，在响应时间和占用内存方面，三种调度算法各有所长， 但总体而言，c h a i n 策略的吞吐量要略低于其他两种算法。 1 2 3 数据流系统中的负载调整 当突发流量超过系统的处理能力，如果不采取相应的措施进行负载调整，会导致整 个系统的吞吐量和响应时间都恶化，系统应能够通过调整查询处理策略，适应性地满足 它的实时处理要求。负载调整以多维q o s 函数为前提，主要采用两种方法对系统的负载 6 东北大学硕士学位论文第二章相关工作 进行调整：是l o a ds h e d d i n g t c 0 3 技术。即在保证满足查询要求的q o s 前提下，对 数据进行随机的丢弃；二是采用无损的或有损的数据压缩技术，通过减少数据容量，达 到减轻负载的目标。 l o a ds h e d d i n g 通过丢弃一定数量的数据，在部分牺牲准确性和完整性的条件下，保 证系统的性能。l o a ds h e d d i n g 处理方式分为以下两种：随机的l o a ds h e d d i n g 算法和基 于语义的l o a ds h e d d i n g 算法。随机l o a ds h e d d i n g 是指在发现数据输入超出系统处理能 力时，通过按一定的比重随机丢弃部分元组保证系统的正常运行。基于语义的l o a d s h e d d i n g ，通过用户对流处理语义的理解，有选择地丢弃一部分元组，使元组损失对系 统性能和输出结果的影响最小化。 随机l o a ds h e d d i n g 的算法比较简单，所需占用的内存和计算量都比较小，但是由 于没有考虑选择丢弃元组对总体性能和输出的影响，在某些情况下可能导致系统性能的 恶化和输出结果的精确性，所以目前普遍采用的负载调整算法一般是基于语义的 【t c 0 3 b d 0 3 c c c 0 2 。 基于语义的负载调整算法与系统的上下文有关，主要考虑的问题是：何时，何处以 及如何进行s h e d d i n g 。 c c c 0 2 1 提出了通过丢弃元组实现的随机负载调整和通过过滤 元组实现的语义负载调整，过滤指有控制地丢弃一些不重要的元组来保证系统的q o s 。 【b b 0 2 中指出了应该基于语义的负载调整并不能有效地保证查询的精确性，从而提出改 善精确性的方法，并通过配置随机抽样算子来具体实现基于语义的负载调整。 1 2 4 数据流查询中的近似计算 为了获得数据流上的连续查询的精确结果，查询处理所需要的内存会随着数据量的 不断增加而变得无界。而对于数据流的处理来说，外存的算法是难以满足实时性要求的 v 9 9 。文献 a b 0 4 对数据流上操作的内存需求进行了分析和演算，把数据流上的查询 按照内存的需求分为可在有限内存中获得精确结果的查询和在有限内存中只能获得近 似结果的查询两大类。他们的结论表明在未知输入数据流大小的情况下，对于数据流上 的某些操作是难以获得精确的查询结果的。例如数据流上的连接，当前数据可能要与未 来的数据进行连接。 此外，系统负载超出系统的处理能力时，如突发流量，数据延迟等，可能导致系统 总体性能下降甚至出现错误。 因此，在数据流管理系统中广泛的使用了近似计算的方法，在部分牺牲精确性的条 件下获得处理时间的减少和存储空间上的节省。而且在大多数实际应用领域中，高质量 的近似结果( a p p r o x i m a t er e s u l t s ) b b 0 2 是完全可以满足应用需求的。近似查询 ( a p p r o x i m a t eq u e r y ) 是d s m s 中重要的数据处理方式，己逐渐成为数据流研究领域的 东北大学硕士学位论文第二章相关工作 一个热门话题，同时也出现了不少实现近似查询的技术，归结起来主要有两方面： 滑动窗口技术( s l i d i n gw i n d o w ) ：不在所有的数据上进行查询，而把滑动窗口作用 在数据流上，仅对窗口中可视的数据进行查询。滑动窗口技术的虽然应用降低了查询的 准确性，但从某种意义上来说，它强调了“最近的”数据； 数据缩减( d a t ar e d u c i n g ) ：以准确性为代价，对数据进行缩减或压缩。数据缩减的 方法很多，如：采样( s a m p l i n g ) ，直方图( h i s t o g r a m ) ，概要( s k e t c h e s ) ，小波压缩( w a v e l e t ) 等。 b b 0 2 中提出了应用于数据流摘录的三种直方图模型：v - o p t i m a lh i s t o g r a m ， e q u i w i d t hh i s t o g r a m s ，e n d - b i a s e dh i s t o g r a m s 。小波变换算法是利用小部分系数的集合 替代潜在的信息，近期在数据流近似值计算中利用比较广泛。目前计算近似值的方法有 多项算法相结合，取长补短的趋势。 其中，实时调度策略是影响系统的整体性能最关键的因素之一。实时数据流处理技 术发展迅速，在工业控制、军事指挥、网络监控、证券交易、传感器网络等重要领域中 广泛应用。在一些关键应用中，要求实时调度大量、连续到达、快速甚至爆发的数据流， 在截止期内给出实时查询结果。由于系统资源( 如c p u 速度、内存容量等) 限制，特 别是在流爆发时，不可能实时处理完数据流上的所有数据，而是尽力处理尽可能多的流 数据，以获得高质量的近似查询结果。因此，数据流上的查询处理具有近似性，实时需 求一般分为软实时( s o f tr e a lt i m e ) 或固实时( f i x e dr e a lt i m e ) 。在动态爆发的数据流环 境中，如何设计实时调度策略，保证应用的固实时需求，并获取高质量的近似查询结果， 成为目前学术界和产业界关注的热点问题。 1 3 课题来源 数据流管理系统r t s t r e a m 实现对实时的流式数据进行查询管理的一系列任务。该 项目得到国家8 6 3 高技术计划“面向大型机电设备状态监测与故障诊断的智能仪器嵌入 式软件开发平台”( 编号：2 0 0 2 a a l z 2 3 0 8 ) 、“手持智能化大型旋转类设备故障监测与诊 断设备”( 编号：2 0 0 2 a a l l 8 0 3 0 ) 项目基金的资助和国家自然科学基金( 编号：6 0 4 7 3 0 7 3 ) 的资助。本文的主要工作是对实时数据流模型查询处理技术的研究。 1 4 本文组织结构 全文一共分为七章。 第一章是前言，主要介绍了数据流和数据流系统的相关概念及特点；然后介绍了当 8 东北大学硕士学位论文 第二章相关工作 前数据流研究领域中几个典型的数据流管理系统，以及相关的实时调度策略。 第二章给出实时调度领域内的相关工作，介绍了一些典型数据流管理系统及相关实 时调度策略。 第三章给出了数据流上基于截止期的实时调度策略的问题描述，并给出相关定义分 析。 第四章提出了本文的核心调度策略一适应性t i c k 调度策略，给出了详细的设计、实 现及相关定理分析。 第五章给出r e a l s t r e a m 系统中调度子系统的详细设计。 第六章对本文提出的调度算法与相关算法进行实验与评价。 第七章总结全文并给出未来展望。 9 东北大学硕士学位论文第二章相关工作 第二章相关工作 本章将介绍当前比较流行的数据流管理系统，以及相关的数据流上实时调度策略。 此外，还引入传统实时数据库中的一些典型的实时调度方法，并分析了它们的执行性能 与适用性。 2 1s t r e a m 与链式调度 斯坦福大学的s t r e a m ( s t a n f o r ds t r e md a t a m a n a g e r ) 系统 r 0 0 3 ，b s 0 2 是一个 通用的数据流管理系统，系统通过自行设计的查询语言c q l ( c o n t i n u o u sq u e r y l a n g u a g e ) a 0 3 ，a s 0 3 注册查询，也可以直接输入查询计划，并将相应的查询编译成 为查询计划，对连续、无界、随时间变化的数据流进行实时的查询处理，为各种形式的 连续查询提供连续、实时的结果。 目前，s t r e a m 系统可以直接以h t t p 方式提供w e b 接口。系统提供一个基于w e b 的图形用户接口，通过该接口远程应用程序可以不受开发平台和编程语言的限制，直接 注册查询并以h t t p 流的形式获得x m l 格式的查询结果。此外，该接口还向用户提供 了一个交互式监控系统运行的途径。 图2 1s t r e a m 体系结构 f i g 2 1s y s t e ms t r u c t u r eo fs t r e a m 图2 1 给出了s t r e a m 系统的系统结构。用户或应用向系统注册查询，注册进系 统的查询将一直被保留到查询被显式的注销为止。左侧的数据流不断向系统输入源数据 并驱动查询执行。虽然系统主要处理在线的连续查询，但是在许多应用中可能需要保存 东北大学硕士学位论文 第二章相关工作 历史数据或进行离线分析，挖掘处理等，所以数据也可能复制到a r c h i v e 结构中。此外， 在连续查询的过程中很可能有一些中间状态，系统把它们保存在s c r a t c h 结构中， s t r e a m 系统中的s c r a t c h 结构目前只驻留在内存。连续查询的结果通常以流化形式 ( s t r e a m e dr e s u l t ) 返回给用户或应用程序，也可能是类似于物化视图的内容随时间变 化的关系形式( s t o r e d r e s u l t ) 。流化的结果和关系形式的结构合在一起构成了连续查询 的最终查询结果。此外，s t r e a m 系统支持数据流和二维表的兼容查询。 t u p l es 图2 2 链式调度 f i g 2 2c h a i ns c h e d u l i n g 在s t r e a m 系统中，中央调度器采用了一种链式调度策略，使系统运行时最大内 存使用量最小化。如图2 1 2 所示，横轴表示时间，纵轴表示元组的大小，图中的点( 廿， s i ) 表示第i 个操作符( o ) 。第i 个操作符用t i - t i 1 单位时间处理大小为s i l 的一个元 组，并产生大小为s i 的一个元组。改操作符的选择度为s i s i 一1 。操作符间连线的倾斜程 度表明单位时间内调度个元组后内存的变化程度，简单的说，也可以看作操作符释放 内存的能力。所毗，链式调度每次调度最倾斜的低包络线对应的操作符的输入元组。 从本质上来说，链式调度是从把操作符处理代价和操作符的选择度结合起来考虑的 一种调度策略，使得操作符的输入队列使用的内存尽量的少。在处理不可预测、爆发的 数据流时，s t r e a m 系统通过折衷查询优化、资源分配以及复杂的调度以获取高质量 的近似结果，保证了一定的实时性。 东北大学硕士学位论文第二章相关工作 2 2t e l e g r a p h c q 与e d d y t e l e g r a p h c q 是u cb e r k e l e y 在开放的关系数据库管理系统p o s t g r e s q l 基础上开发 的一个数据流管理系统。它继承了一些u cb e r k e l e y 以前的数据流开发成果，如适应性 查询实体e d d y ，p s o u p 等模块。如图2 5 所示。 t e l e g r a p h c q 的大致执行过程是：首先监听器从客户端得到指令后选择在哪晕执行， 如果是基于表的查询则在前端就可以执行完毕，而对流进行操作的连续查询则在预处理 之后通过查询计划队列( q u e r yp l a nq u e u e ) 送到后端进行处理；后端不断得到新的查 询并把它们动态转换成为运行状态，查询得到的结果则被送至各个客户端的查询结果队 列( q u e r y r e s e t q u e u e ) 当中；前端把连续查询传送给后端之后，则在微型执行器中产 生一个局部最小化查询计划，并不断从查询结果队列当中得到结果再返回给客户端。包 装清理器( w r a p p e rc l e a r i n g h o u s e ) 得到元组后进行处理使之便于后端进行查询，如果 必要的话还可以对它进行压缩，再把它们经由内存缓冲池转交给后端处理。 图2 3t e l e g a p h