（计算机科学与技术专业论文）网络安全事件olap分析中流数据方构建技术的研究与实现.pdf

y 1 7 9 5 鲥百4 r e s e a r c ha n di m p l e m e n t a t i o no fs t r e a m c u b ec o n s t r u c t i o nt e c h n i q u e sf o ro l a p a n a l y s i so f n e t w o r k s e c u r i t yi n c i d e n t s c a n d i d a t e ：w a n gy i b i n g a d v i s o r ：p r o f y a n gs h u q i a n g ad i s s e r t a t i o n s u b m i t t e di np a r t i a lf u l f i l l m e n to f t h er e q u i r e m e n t s f o rt h ed e g r e eo fm a s t e ro fe n g i n e e r i n g i nc o m p u t e rs c i e n c ea n dt e c h n o l o g y g r a d u a t es c h o o lo fn a t i o n a lu n i v e r s i t yo fd e f e n s et e c h n o l o g y c h a n g s h a ，h u n a n ，p r c h i n a a p r i l ，2 0 1 0 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：圃终塞全壹鲑q 垒垒里金堑生速数握虚堑建撞苤塑壁窒皇塞堑 学位论文作者签名： 五1 2 ) ：廛、 日期：加c 口年月2 ，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 交档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：因缝鏖垒圭! 圭! 圭垒丝塑圭逸丝丝垒显逵逝研亥了绞视 学位论文作者签名：圣互生丝、 日期：如c 口年y 月日 作者指导教师签名：幺丕五盛隆日期：如i 口年q - 月乙f 日 国防科学技术大学研究生院硕十学位论文 目录 摘要i a b s t r a c t i i 第一章绪论一1 1 1 课题研究背景及意义1 1 2 研究现状2 1 2 1 数据流技术的研究现状2 1 2 2 联机分析处理技术的研究现状6 1 2 3 数据流立方体构建的研究现状9 1 3 研究内容10 1 4 论文结构。1 0 第二章相关技术研究11 2 1数据流相关技术1 1 2 1 1 数据流管理系统的基本特征1 l 2 1 2 查询模型。1 1 2 1 3 数据流处理模型1 3 2 1 4 阻塞操作的非阻塞化。1 4 2 2 数据立方体技术1 4 2 2 1 数据立方体的概念。1 4 2 2 2 数据立方体的计算1 6 2 3 数据流立方体技术。19 2 3 1 倾斜时间窗口模型。1 9 2 3 2 基于固定时间窗口的数据流立方体。2 0 2 4 本章小结2 l 第三章时间分割数据流立方体2 2 3 1时间分割数据流立方体的定义2 2 3 2 表连接优化2 4 3 2 1 表连接的方法2 4 3 2 2 优化连接器所做的优化2 5 3 2 3 表连接预处理2 6 3 2 4 实验内容。2 7 3 3 模型优化2 8 第1 页 国防科学技术大学研究生院硕士学位论文 3 3 数据流立方体的增量维护3 3 3 3 1 增量维护的设计方案3 3 3 3 2 加载任务的容错机制。3 4 3 4d s m s 和d b m s 的混合存储3 4 3 4 1 混合存储结构3 4 3 4 2t s s c u b e 的查询3 5 3 4 3 实验内容3 5 3 4 本章小结3 6 第四章网络安全态势分析系统实现3 8 3 8 构3 8 ：；9 4 0 4 0 4 3 4 7 ! ；：； 5 4 5 5 ! ；! ； ! ；6 5 7 5 8 6 2 国防科学技术大学研究生院硕七学位论文 表目录 表2 1b u c 算法的伪代码1 8 表3 1i p 维表的结构2 7 表3 2 表连接优化测试结果2 7 表3 3 数据流快照2 9 表3 4 源地址维表s o u r c et a b l e 。2 9 表3 5 时间维表t i m et a b l e 3 0 表3 6 事件维表e v e n t t y p etable 3 0 表3 8 固定c u b e 查询窗口测试结果3 6 表3 9 固定数据流速度测试结果3 6 表4 1s c h e m a 的x m l 描述。3 9 表4 2 压缩前i p 维表的结构4 1 表4 3 压缩后i p 维表的结构4 2 表4 4 i p 表的结构4 2 表4 5i p 表连接优化算法4 2 表4 6 数据流立方体的增量更新算法4 4 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 数据流管理系统原型图4 图2 1 超市数据立方体1 6 图2 2 数据立方体s a l e s 计算示图。17 图2 2 自然倾斜时间窗口和对数尺度倾斜时间窗口2 0 图2 3 翻转窗口数据流模型2 l 图3 1 时间分割数据流立方体2 4 图3 2 在d s m s 中生成的t s s c u b e 。3 1 图3 3 时间分割数据立方体的3 d 表示3 2 图3 4 数据流立方体的星型模型3 2 图3 5 数据加载的整个过程3 3 图3 6 混合存储体系结构3 5 图4 1 网络安全分析系统结构3 8 图4 2 网络安全监控数据4 0 图4 3 采用表连接优化后的处理结构的变化4 1 图4 4 包装器初始化时序图4 3 图4 5 多个查询的立方体更新的调度流程4 5 图4 6 加载模块类图4 5 图4 7 资源管理器类图4 6 图4 8 任务排队器类图4 6 图4 9 容错控制器类图4 7 图4 1 0y h s t r e a m 的系统结构图4 8 图4 1 1 连接树( r s ) t ，r ( s t ) 与e d d y 的比较5 0 图4 1 2t e l e g r a p h c q 的体系结构5 1 图4 1 3 y h s t r e a m 的概念分层5 2 图4 1 4 历史数据多维分析展示5 3 图4 1 5 实时数据分析与预测展示5 3 第1 v 页 国防科学技术大学研究生院硕士学位论文 摘要 互联网是关键的国家信息基础设施，对互联网网络安全状态的实时监控是确 保互联网有序运行的关键，而对互联网网络安全状态的监测分析是对其进行实时 控制的前提。联机分析处理技术( o l a p ) 是一种重要的数据分析技术，可用于互 联网网络安全状态分析。o l a p 高效数据分析需要数据立方体的支持，网络安全数 据的海量性和持续产生性不适合数据立方体的构建，从而制约了o l a p 在互联网 网络安全状态监测中的应用。 本文提出了一种基于数据流管理系统的数据立方体构建方法，应用数据流管 理系统对互联网网络安全监测数据进行预计算，对数据立方体进行实时增量更新 和维护，本文的主要贡献如下： 1 在对网络安全监测数据的数据流特点以及数据流处理技术、o l a p 技术进 行了深入分析的基础上，提出了根据时间切片的数据流立方体构建方法，并对该 方法的有效性进行了分析。 2 针对构建立方体过程中大型维表连接非常耗时的问题，提出了改进的表连 接技术，并对数据流处理模型进行了优化，通过实验验证了该方法的有效性。 3 提出了使决策人员可以注册大窗口查询的混合数据库模式( 基于d s m s 和 d b m s ) 的概念。根据混合数据库的特点设计了数据流立方体的增量维护算法，并 通过实验验证了算法的有效性。 4 针对网络安全监控的需求，基于上述技术，设计并实现了网络安全分析系 统的数据立方体构建子系统y h s t r e a m 。该子系统支持海量数据流的时间切片 数据流立方体的构建，并提供了基于混合数据库的存储与查询。该子系统已经部 署运行。 主题词：数据流，数据流立方体，o l a p ，网络安全态势感知 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t i n t e m e ti san a t i o n a lk e yi n f o r m a t i o ni n f r a s t r u c t u r e m o n i t o r i n ga n dc o n t r o l l i n gt h e i n t e r n e tn e t w o r ks e c u r i t yi n c i d e n t si nr e a lt i m ei sk e yt oi n s u r ei n t e r n e tr u n n i n g n o r m a l l y m o n i t o r i n ga n da n a l y z i n gt h e s t a t eo fi n t e r n e tn e t w o r ks e c u r i t yi st h e p r e c o n d i t i o no fc o n t r o l l i n gi ti nr e a lt i m e o n - l i n ea n a l y t i c a lp r o c e s s i n g ( o l a p ) i s a n i m p o r t a n tt e c h n i q u eo fd a t aa n a l y z i n g ，w h i c hc o u l db eu s e dt oa n a l y z i n gt h es t a t eo f i n t e r n e tn e t w o r ks e c u r i t y d a t ac u b ei sn e e d e df o re f f i c i e n to l a pd a t aa n a l y z i n g ， h o w e v e r ，t h ec o n s t r u c t i o no fd a t ac u b ei sn o ts u i t a b l ef o rn e t w o r ks e c u r i t yd a t aa si t s c h a r a c t e r i s t i c so fb u r s ta n dm a s s i n e s s ，w h i c hl i m i t st h ea p p l i c a t i o no fm o n i t o r i n gt h e s t a t eo fi n t e r a c tn e t w o r ks e c u r i t y t l l i st h e s i sp r o p o s e sad 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 ) b a s e dm e t h o do f c o n s t r u c t i o no fd a t ac u b e ，w h i c hp r e - c a l c u l a t et h ei n t e m e tn e t w o r ks e c u r i t ym o n i t o r i n g d a t a 、析t hd s m s u p d a t et h ed a t ac u b ei n c r e m e n t a l l ya n dm a i n t a i ni t t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r es u m m a r i z e da sf o l l o w s ： 1 t l l i st h e s i s p r o p o s e s t h ec o n s t r u c t i o nm e t h o do ft i m e s l i c e ds t r e a m c u b e ( t s s c u b e ) o nt h eb a s eo fp r o f o u n ds t u d yo fc h a r a c t e r i s t i c so fn e t w o r ks e c u r i t y m o n i t o r i n gd a t as t r e a m ，t e c h n i q u e so fp r o c e s s i n go fd a t as t r e a ma n do l a pt e c h n i q u e s 2 t h i st h e s i sp r o p o s e si m p r o v e dt a b l ej o i n i n gt e c h n i q u e s b e c a u s ei nt h ep r o c e d u r e o fc o n s t r u c t i n gd a t ac u b e ，b i gd i m e n s i o n a lt a b l ej o i n i n gi sv e r yt i m e - c o n s u m i n g t h i s t h e s i sa l s ot e s t si t sv a l i d i t y 3 t h i st h e s i sp r o p o s e st h ec o n c e p to fh y b r i dd a t a b a s em o d e ( b a s e do nd s m sa n d d b m s ) ，w h i c ho f f e rt h ep o l i c ym a k e r st h ec o n v e n i e n c eo fr e g i s t e r i n gb i g w i n d o w e d q u e r y a c c o r d i n gt ot h ep r a c t i c a lc o n t e x t ，t h i st h e s i sr a i s e st h ed a t ac u b ei n c r e m e n t a l u p d m ea l g o r i t h ma n dt e s t si t sv a l i d i t y 4 s i n c et h en e e do fn e t w o r ks e c u r i t ym o n i t o r i n g ，b a s e do nt h et e c h n i q u e sa b o v e ， t h i st h e s i si m p l e m e n t sy h s t r e a mu s e dt oc o n s t r u c t i n gd a t as t r e a mc u b ew h i c hi st h e s u b s y s t e m o fn e t w o r k s e c u r i t ya n a l y s i ss y s t e m y h s t r e a ms u p p o a s t h e c o n s t r u c t i n go ft s s c u b e a n dh y b r i dd a t a b a s e b a s e ds t o r a g e sa n dq u e r i e s t 1 1 i s s u b - s y s t e mh a sb e e nd e p l o y e da l r e a d y k e yw o r d s ：d a t as t r e a m ，d a t as t r e a mc u b e ，o l a p ，n e t w o r ks e c u r i t y s i t u a t i o na w a r e n e s s 第i i 页 来越广泛，并逐渐成 、恶意代码、僵尸网 络等安全事件层出不穷，突显了现有网络防御能力的严重不足并严重制约着互联 网的应用和发展。对互联网进行实时的监控和分析，具有重要的现实意义。 实时监控和分析互联网的安全状况需要对连续、高速、海量的网络安全数据 进行高效的处理。因此，对网络安全实时监控和分析是一个典型的数据流( d a t a s t r e a m ) 应用场景，而联机分析处理( o l a p ) 技术是实现对大规模网络监控数据 进行综合分析的重要技术之一。本文正是围绕网络安全监控数据流的实时处理这 一热点问题展开研究。结合现有的数据流和o l a p 研究技术，通过有限的存储计 算资源来对无限、快速的数据进行分析和处理。 1 1 课题研究背景及意义 随着互联网的迅速发展，互联网的普及率也越来越高。根据中国互联网络信 息中心( c n n i c ) 的报道，截至2 0 0 7 年1 2 月，中国的网民数就已达2 1 亿人，总 上网人数居世界第二，互联网普及率达到了1 6 。网络新闻、电子邮件、网上购 物、网上银行、网络电话等一系列的互联网信息资源使人们的生活方式发生了前 所未有的变化。在互联网规模的扩大和应用的不断深入的同时，各种威胁网络安 全的事件也层出不穷。蠕虫病毒、网络攻击、恶意代码、僵尸网络等网络安全事 件所造成的危害和损失也越来越严重。例如，著名的红色代码蠕虫病毒所造成的 最终损失高达2 6 亿美元：越来越多的类似“熊猫烧香”的病毒和木马也以追求经 济利益为目的。这些网络安全犯罪活动严重的制约了互联网的发展和社会安全稳 定。因此对大规模网络安全事件进行实时监控和分析便显得越来越迫切。 联机分析处理( o l a p ) 技术是对海量数据进行综合分析的重要手段。o l a p 通过快速、一致、交互的访问各种可能的信息视图，帮助网络安全数据的分析人 员、管理人员、决策人员深入观察数据并掌握其中规律。联机分析处理技术经过 多年的发展，已经出现了许多成熟的技术，如数据立方体的建立、计算以及查询 等。但这些技术大多是基于静态的数据仓库进行的研究。因此针对数据流的海量、 高速、无限等特点，如何利用现有时空资源有效的进行数据流多维分析与处理是 我们要解决的主要问题。 在传统的数据处理模型中，数据必须全部存储到数据库或数据仓库中，通过 用户提交的d m l 语句来获取查询结果。当数据规模很大时，传统技术在计算存储 第1 页 国防科学技术大学研究生院硕十学位论文 开销、连续跟踪结果的实时性等方面难以满足实际要求。 传统的数据库管理系统旨在处理持久、稳定的数据，强调维护数据的完整性、 一致性，其性能目标是以较低的代价获得较高的系统吞吐量，其设计目标是维护 数据的绝对正确性、提供友好的用户接口等。这种数据库管理系统对于传统的事 务型应用是有效的、成功的，然而它不适合处理无限数据的、快速的、实时的应 用，关键在于传统的数据库管理系统通常不考虑与事务相关联的时间和空间限制， 其调度与处理决策不考虑数据的各种时间特性，其系统的设计指标并不强调实时 性和查询服务质量的自适应性，而实时性和自适应性恰恰是数据流应用所必须的。 在传统数据库中，数据被存放在特定介质上( 磁盘、磁带等) ，是一种持久 存储。数据变化相对较慢，在一次查询的处理过程中认为数据集是不变的，因此 可以通过对数据集的多遍扫描得到查询结果。数据流场景下是流动的数据，而且 由于数据规模大、到达速度快，不可能将数据全部保存。因此往往只能进行单遍 扫描处理求得近似结果后，数据就被丢弃。 传统数据库中通过s q l 语言描述一次查询请求，通过对当前数据集进行处理 后返回一个结果集，此次查询就结束了。因此，传统数据库中的查询是一次性查 询( o i i c t i m eq u e r y ) 或称为快照查询。而在数据流场景下的查询为连续查询，即 查询相对稳定并持续一段时间，查询结果随着新数据的到达不断发生变化，需要 持续跟踪这种变化进而达到监控等目的。查询结果本身也是以流的形式输出。 数据立方体的有效计算是支撑o l a p 分析的关键。只有预先计算数据立方体 的全部或部分，才能大幅度降低查询响应时间，提供联机分析处理的性能。然而 这种计算是一种挑战，因为它需要大量的计算时间和存储空间。我们如何提前计 算数据立方体，使得它在查询处理时可方便的使用? 计算完全数据立方体将面临 “维灾祸( c u r s eo fd i m e n s i o n a l i t y ) 问题，而完全不计算数据立方体将导致低下 的查询性能，使用户无法忍受。因此，可行的策略是计算部分数据立方体，在数 据立方体的时空开销和查询响应性能之间进行微妙的折中。如何在存储容量、计 算能力的限制下，寻找到计算部分数据立方体的可伸缩的办法，成为研究者关注 的焦点，也是本文工作的核心问题。 1 2 研究现状 1 2 1 数据流技术的研究现状 数据流是实时、连续、有序的数据项序y d ( j 1 0 j i 序由到达时间隐含地表示或显式 地由时间戳指定) ，数据流的数量在理论上是无限的，无法完整地存储下来。数据 流上的查询能够事先或即席注册于系统，以触发的方式或周期性地方式连续运行， 第2 页 国防科学技术大学研究生院硕士学位论文 源源不断地返回查询结果，就是所谓长时间运行的、连续的、持久稳定的查询 3 9 1 。 数据流处理系统的输入数据并不存在于可随机访问的磁盘或主存中，输入数 据以一种瞬态的、持续的流的形式到达。概括来说，相对于传统数据库模型，数 据流模型主要有如下几个方面的特征： 1 流中的数据元素实时到达： 2 系统无法控制将要处理的新到达的数据元素的顺序； 3 从理论上说，数据流的潜在大小是无界的；系统能存储的数据相对数据流 的大小则是非常有限的； 4 一旦数据流中的某个元素经过处理，要么被丢弃，要么被归档存储。但被 丢弃的数据元素可能需要再次被访问； 5 数据流模型中查询是相对静止不变的，而数据是时刻变化的。 由于数据流海量、无限、持续的特点，因此其应用领域主要有以下两个特点： ( 1 ) 应对数据的爆炸性增长：这个增长源自于多年来互联网技术和各种专用网 络技术的发展，例如：银行、传感器网络等等。各个领域信息技术的发展使得数 据采集能力大大增强。在环境科学中，基于卫星的、高清晰度的地球测量，气象 雷达数据，光学、红外和微波的连续大规模天文测量，大气辐射测量等，产生了 大量的流式数据。在互联网中更是如此，不仅数据源是分布的，而且数据使用者 也是分布在各地的大量用户，伴随而来的则是事务的速率成比例的增加，产生了 多重的数据流，例如：浏览点击，用户查询，口传输日志，e m a i l 数据和传输日 志，网络服务器和端到端的传输等等。在互联网中还可以利用特定目的的连续观 测点进行数据监测。无线网络的发展为数据流问题的研究提供了契机。无线技术 和网络技术相结合的传感器网络更是当前众多研究者所关注的热点问题。上述各 领域产生的数据量和速率是相当可观的。对数据流传输、计算和存储都提出了新 的要求。 ( 2 ) 实时条件下的复杂分析需求：在传统方式下，对原始数据的更改就反映了 更新，实时条件下的查询也只是很简单的查找某个数值，这样的业务就像银行的 信贷事务。更为复杂的分析像趋势分析、预测等等一般是在离线状态下对数据库 或者数据仓库存储数据的分析。然而，在来自监控应用的环境下，却产生了一些 实时性或准实时性的应用需求，例如：大气、天文、网络、金融或者传感器等相 关的数据，需要进行一系列的复杂分析，例如孤立点检测、欺诈行为、异常检测、 聚类分析等等。需要监控复杂的相关性和进行趋势预测，支持探测性分析和执行 复杂的任务等等。 数据流管理系统所处理的数据流是一种实时连续的数据信息序列，而且在实 际处理过程中，这种数据序列具有信息到达顺序不可控、单位时间数据到达量不 第3 页 国防科学技术大学研究生院硕士学位论文 均匀、数据量庞大等特点。 为了支持长期运行，连续的、标准的、持久的查询，d s m s 的一般功能结构 主要由3 部分组成：输入部分，处理部分和输出部分。输入部分主要对输入的数 据流进行初步的过滤，并兼有应付突发流量的基本功能( 譬如在系统没有足够资源 处理突发数据流时进行负载脱落) 。处理部分是整个系统的主干，由3 部分组成： ( 1 ) 暂存子系统，数据分为3 部分暂存：静态暂存部分存储元数据( 例如d s m s 各部分的物理位置等) ，允许用户自定义相关的设置；工作暂存部分存储当前处 理的数据流，如果遇到突发流量而没有足够的物理存储空间，可以对数据进行归 纳，将获得的纲要( s y n p o s e s ) 或摘要存储在纲要暂存中；( 2 ) 查询缓存，主要 存储用户定义的查询条件，一般的d s m s 系统支持用户在线修改查询条件； ( 3 ) 查询处理子系统，主要功能是从查询缓存中提取用户定义的查询，根据优化需求 对其进行分组，并将其作用于从输入部分获得的数据流。查询处理子系统还具有 自适应功能，能根据当前数据流量和查询条件调整系统查询策略。输出部分主要 的功能是保证处理所得的结果( 数据流或和关系型数据项) 能够平稳地输出，一 般都包含临时存储的功能。 一种典型的数据流管理系统的结构如图2 1 所示。输入监控器可用于控制输入 速率。数据被分为三部分分别存储：临时工作存储( 用于窗口查询) 、数据流的 概要存储和中间数据的静态存储( 每个数据源的物理地址) 。虽然可能对数据流 现有状态只进行一次查询，长时间连续查询也要注册到查询库并插入到队列中等 待共享处理。查询优化器与输入监控器进行交互，在改变输入速率的同时对查询 计划进行重新优化，最后生成的结果也以数据流的形式显示给用户或者进入临时 缓存。 更新静态数据 用户查询 图1 1 数据流管理系统原型图 数据流管理系统设计中的一个重要问题是如何有效地处理连续查询( 流式查 第4 页 国防科学技术大学研究生院硕十学位论文 询) 。所谓连续查询，是指一旦一个查询确立之后它将长时l 日j 连续执行。对数据 流进行的查询为连续查询，它在一段时间内连续执行，随着新的数据的到达将不 断地产生新的查询结果。例如在网络通信量管理中，连续查询用于在线监控网络 行为，以便及时发现异常( 如连接异常) 和产生异常的原因( 如硬件失败、服务 器受到攻击等) 。连续查询还用于支持负载平衡或其他网络性能调整。在许多金 融管理系统中，连续查询用于监控趋势变化并且识别一些即逝的机会。 最近几年出现了很多以数据流为信息承载模式的应用系统，这些系统都主要 用于处理具有实时性、连续性、顺序性及海量性等特点的数据流处理。目前较为 著名的项目主要有加州大学伯克利分校的t e l e g r a p h c q 5 7 】、a t & t 实验室的 g i g a s c o p e 8 1 0 】、，布朗大学、布兰蒂斯大学和麻省理工大学的 a u r o r a & b o r e a l i s 11 1 6 、斯坦福大学的s t r e a m 3 ，4 】以及w i s c o n s i n 大学的 n i a g a r a c q 1 7 等。 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 是以关系型数据为基础的数据流管理系统，其设计目标是：在 资源紧张的情况下，以有效方式给出近似查询结果，其重点在于内存管理 和近似查询。它可以用于处理快速的、易变的、大量涌入的数据流信息， 具有非常好的连续查询能力 2 3 】。s t r e a m 系统的特点在于有效的内存 分配和摘要的提取。 a u r o r a 是布朗大学、布兰蒂斯大学和麻省理工大学联合开发的一个专门处 理流式监控数据的新型系统。a u r o r a 简单独特的框架结构可以处理三种 不同的应用：实时监控应用、处理以时间序列存储的大量归档数据型应用 和包含对历史以及当前数据进行处理的跨度应用。m e d u s a 18 是麻省理工 学院推出的分布式数据流系统，以a u r o r a 系统作为单个节点的数据流处 理引擎，以重叠网络为基础，将多个含有a u r o r a 的节点连接起来，形成 分布式数据流处理系统。与集中式数据流系统不同，分布式系统的重点在 于将数据流处理任务分发给参与者，利用价格模型规范参与者的行为，组 织参与者相互合作共同完成数据流处理任务。 b o r e a l i s 系统是布朗大学、布兰蒂斯大学和麻省理工大学联合推出的第二 代数据流系统。该系统继承了a u r o r a 系统的核心数据流处理技术以及 m e d u s a 系统的分布式特性。在b o r e a l i s 系统中，所有注册的连续查询经 过组合优化后，多个查询计划被组合到一起，形成一个巨大的连续查询网 络。整个连续查询网络被分配到多个节点中执行，多个节点相互合作共同 完成处理任务。传感器网络也可以通过代理加入到b o r e a l i s 系统。 第5 页 国防科学技术大学研究生院硕十学位论文 g i g a s c o p e 是a t & t 实验室j f = 发的高性能d s m s ，用于监控网络中的高速 数据流。作为基本数据分析引擎，g i g a s c o p e 可以应用于流量分析、性能 监控和调试、路由配置、网络攻击和入侵检测等很多场景。g i g a s c o p e 采 用两层查询结构，以可控的方式处理高速数据流；能够根据数据流的速度 和处理资源的可用性选择最适合的处理策略。g i g a s c o p e 目前运行在 a t & t 实验室的i p 主干网上，在网络监控数据处理方面取得了较好的效 果。 威斯康星州立大学的n i a g a r a c q 提出两种方法来处理多查询问题，即共享 查询计划和索引查询谓词。在这个共享查询计划中，属于同一组的查询共 享一个计划，产生组中每一查询所需的结果的并集，再运用选择操作来得 到最后的结果。问题还包括当新查询加入系统时如何动态地重组、各种窗 口大小的窗口连接的共享估算和复杂查询的计划共享。在索引方法中，查 询谓词存于一个表中，当新元组到达时，它的属性值被抽取并查看查询表， 看是否满足某个查询。数据和查询通过查询谓词表和数据表的多方式的连 接，一起当作两个约减的查询处理。索引方法当前不适用于窗口聚合等查 询。 加州大学伯克利分校的t e l e g r a p h c q 系统是建立在开源数据库系统 p o s t g r e s q l 之上的数据流处理系统。该系统可以对数据流的历史数据进 行查询并对这类数据进行实时监测、分析，以便在发现异常时能够及时准 确地进行处理为了进一步增加自适应性，e d d i e s 方法取代了维护一个生硬 的树结构的查询计划，而是执行每个元组的调度，并通过补偿查询计划的 操作项来路由。t e l e g r a p h c q 已经在网络流量管理等方面得到了一定的应 用。 1 2 2 联机分析处理技术的研究现状 “数据仓库这个名词，是由“数据库之父 w i l l i a mh i n m o n 手2 0 世纪8 0 年代中期第一次提出的。随着互联网和信息技术的快速发展，各行各业的信息量 大大加强，这种海量信息的潜在价值也正在得到越来越多的关注，数据仓库逐渐 成为i t 领域中最被关注的热点之一。o l a p 技术也在数据仓库技术的基础上而出 现的。o l a p 技术主要是针对特定问题进行联机数据查询与分析。如今，数据仓库 与o l a p 技术已发展成为有机的统一整体。 自从“数据仓库 名词的提出，数据仓库历来没有一个公认的、且被标准化 的定义。w i l l i a mh i n l t l o n 在他的( ( b u i l d i n gt h ed a t aw a r e h o u s e ) ) 中给出了数据仓 库的定义：“数据仓库中的数据是面向主题的、集成的、稳定的并随时间不断变 第6 页 ( 1 ) 数据仓库是面向主题的。 数据仓库中数据以面向主题方式组织的。主题是用户所关心的数据对象，每 个主题对应一个客观分析领域。面向主题的数据组织方式就是在较高层次上对分 析对象的数据作一个完整、一致的描述，能有效地刻画出分析对象所涉及的各项 数据及数据间的联系。这种数据组织方式更能适合于较高层次的数据分析，便于 发现数据中蕴涵的模式和规律。 ( 2 ) 数据仓库中的数据是集成的。 数据仓库的数据是从原有的、分散的数据源数据库中抽取得来。数据在进入 数据仓库之前，必须经过数据加工和集成，这是数据仓库建设的关键步骤。不但 要统一原始数据中的矛盾之处，还要将原始数据结构做一个从面向应用向面向主 题的转变。使用数据清理和数据集成技术，确保命名约定、编码结构、属性度量 等的一致性。 ( 3 ) 数据仓库中的数据是不可更新的。 数据仓库是不同时间的数据集合，数据存储从历史角度提供信息。数据仓库 中存放的是供分析决策用的历史数据，而不是联机处理的当前数据，涉及的数据 操作主要是数据查询，一般不进行数据的增、删、改操作，业务系统中的数据经 集成并进入数据仓库之后极少或根本不再更新。 ( 4 ) 数据仓库中的数据是随时间变化的。 数据仓库的数据不可更新是对数据仓库的应用而言，即数据仓库的用户在进 行分析处理时不进行数据更新操作，但这不是说数据仓库是永远不变的。数据仓 库数据是随时间变化的，数据仓库系统需要不断获取联机事务处理系统不同时刻 点的数据，以表明数据的历史时期，并在时间维度上对数据进行分析。 o l a p 分析是建立在数据仓库上的重要应用。数据仓库和o l a p 技术在数据 分析和决策支持中发挥着重要的作用。o l a p 技术对原始数据进行逻辑建模，使分 析人员能够从多个角度观察信息。o l a p 在内的许多应用驱动了数据仓库技术的出 现和发展；而数据仓库技术也加快了o l a p 技术的发展。 在2 0 世纪6 0 年代末期，e f c o d d 提出关系数据模型以后，促进了关系数据 库与联机事务处理( o n l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) 的发展。随着数据库技 术的完善，各行各业积累了大量的历史数据。面对这些大量复杂的数据，传统系 统的访问性能逐渐下降，而且这些大量的数据并不能得到有效利用，不能提供有 效的行业决策。在1 9 9 3 年，e f c o d d 认为，联机事务处理已不能满足终端用户对 数据库查询分析的需要，也不能满足决策者提出的决策分析需求。用户的决策分 第7 页 国防科学技术大学研究生院硕十学位论文 析需要对关系数据库进行大量计算彳能得到结果，而简单的结果并不能满足决策 者提出的要求。因此他提出了多维数据库和多维分析的概念，即联机分析处理。 多维数据分析的核心是有效的计算多维集合上的聚集，也就是分组( g r o u p b y ) 。 每个分组都可以用一个方体( c u b o i d ) 来表示，其中分组的集合形成立方体的格 ( 数据立方体) 。对于不同的查询，o l a p 可能需要访问不同的方体。因此，提前 计算数据立方体可以带来快速的响应时间。j i mg r a y 等人于1 9 9 6 年提出了多维数 据立方体计算方法m e m a r r a y c u b e 2 1 ，2 2 】，m u t o 等人提出了对a r r a y c u b e 算法的 改进方法。尽管多维数据立方体计算方法采取了多种高效算法来减少数据立方体 计算所需的存储计算资源，但如果时间立方体很稀疏，仍将导致计算效率过低。 i b ma l m a d e n 研究中心和w i s c o n s i n m a d i s o n 大学的研究人员总结了数据立方 体计算的各种可能的优化技术 2 4 2 6 】，提出了p i p e s o r t 算法、p i p e h a s h 算法和 o v e r l a p 算法。其中，p i p e s o r t 算法是第一个使用立方体格图描述数据立方体计算 问题的算法，基于立方体格图描述数据立方体计算的问题被后来的数据立方体计 算算法所广泛接受。p i p e s o r t 算法是基于代价和排序的流水线型算法，它主要结合 了“最小父母 、“缓存结果”和“批处理”三种优化方法。p i p e h a s h 算法基于 代价、散y u ( h a s h ) 和划分的思想计算