（计算机科学与技术专业论文）网络安全监控中重复数据检测技术的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 随着计算机技术的迅猛发展和网络应用的日益广泛，网络安全监控在维护网 络正常高效运行、保障网络和信息系统安全以及分析网络用户行为等方面，具有 越来越重要的作用。然而，大规模网络安全监控数据的高效处理需求和有限的计 算、存储、网络带宽等资源之间的矛盾日渐突出，如何采用合适的技术，在有限 的计算存储资源情况下，对无限、快速、持续到达的网络安全监控数据进行处理， 成为网络安全监控系统面临的首要闻题。流数据重复检测作为流数据处理中的一 个重要环节，一方面，对检测出的重复数据进行分析，进而为后续的网络安全监 控应用提供支持；另一方面，通过删除检测出的重复数据，可以更好地实现有效 的网络传输和高效的在线分析处理。 本文以网络安全监控为背景，针对网络安全监控数据处理存在的问题，对当 前的数据流管理系统和流数据重复检测技术进行了研究。主要工作有： 1 、系统地研究了部分己公开的数据流管理系统，对各自的应用领域、体系结 构、查询语言、组成和特点等进行了分析，提出了满足网络安全监控要求的数据 流管理系统。并以t e l e g r a p h c q 数据流管理系统为例简要分析了其中实现的重复 检测方法。 2 、通过对现有流数据重复检测技术的研究，针对网络安全监控流数据的特点， 提出了一种流数据重复检测算法。该算法通过增加更新过程来弥补b l o o mf i l t e r 的 不足，应用基于改进的b l o o mf i l t e r 的界标窗口模型，在给定固定小的空间和允许 一定误称率的情况下，获得了较好的准确率和时间效率。 3 、在网络安全监控数据流管理系统中实现了上述流数据重复检测算法，降低 了后期需要处理和分析的数据量，提高效率，并节约存储空间。 综上所述，本文针对网络安全监控这一典型的数据流应用场景，提出并实现 了一种流数据重复检测算法，对流数据处理有一定的实用价值。 关键词：网络安全监控，数据流，检测重复，数据流管理系统，b l o o mf i l t e r 第i 页 国防科学技术大学研究生院学位论文 a bs t r a c t w i t l lt h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n di n c r e a s i n g l ye x t e n s i v e n e t w o r ka p p l i c a t i o n s ，n e t w o r ks e c u r i t ym o n i t o r i n gp l a y sa ni n c r e a s i n g l yi m p o r t a n tr o l e i ns o m ef i e l d s ，s u c ha sn e t w o r km a i n t e n a n c e ，n e t w o r k s e c u r i t ya n dn e t w o r ku s e r b e h a v i o ra n a l y s i s h o w e v e r ，t h er e q u i r e m e n to fe f f i c i e n t l yd e a l i n gw i t hm a s s i v e n e t w o r ks e c u r i t ym o n i t o r i n gd a t ai si nc o n f l i c tw i t hl i m i t e dr e s o u r c e s s u c ha s c o m p u t a t i o n ，s t o r a g ea n dn e t w o r kb a n d w i d t h o n eo ft h em o s ti m p o r t a n tc h a l l e n g e s f a c e di nn e t w o r ks e c u r i t ym o n i t o r i n gs y s t e mi sh o wt op r o c e s st h eu n l i m i t e dr a p i d c o n t i n u o u sn e t w o r ks e c u r i t ym o n i t o r i n gd a t ab y a p p r o p r i a t et e c h n o l o g yu n d e rt h e c i r c u m s t a n c e so fl i m i t e dc o m p u t a t i o na n ds t o r a g er e s o u r c e s d e t e c t i n gd u p l i c a t i o n si n d a t as t r e a mi sa ni m p o r t a n tl i n ki ns t r e a md a t ap r o c e s s i n g o nt l l eo n eh a n d a n a l y z i n g d u p l i c a t i o n sw h i c hh a v ea l r e a d yb e e nd e t e c t e dp r o v i d e ss u p p o r tf o rf o l l o w u pn e t w o r k s e c u r i t ym o n i t o r i n ga p p l i c a t i o n s o nt h eo t h e rh a n d ，e l i m i n a t i n gd u p l i c a t i o n si sh e l p f u l f o re f f e c t i v e l yn e t w o r kt r a n s m i t t i n ga n d e f f i c i e n t l yo n l i n ea n a l y z i n ga n dp r o c e s s i n g b a s e do nt h eb a c k g r o u n do fn e t w o r ks e c u r i t ym o n i t o r i n g ，t h i sp a p e rf o c u s e so nt h e p r o b l e mi np r o c e s s i n gn e t w o r ks e c u r i t ym o n i t o r i n gd a t a ，a n dr e s e a r c h e sd s m sa n d d e t e c t i n gd u p l i c a t i o n st e c h n o l o g i e si nd a t as t r e a m t h em a i nc o n t r i b u t i o ni sc o n c l u d e d a sf o l l o w s f i r s t l y ，w er e s e a r c hal o to fp u b l i cd s m s sa n da n a l y z et h e i ra p p l i c a t i o nf i e l d s ， a r c h i t e c t u r e ，q u e r yl a n g u a g e , c o m p o n e n t sa n dc h a r a c t e r i s t i c s a c c o r d i n gt ot h ed e m a n d o fn e t w o r ks e c u r i t ym o n i t o r i n g ，w ep r o p o s ead s m s t h e nw et a k et h ec a s eo f t e l e g r a p h c qa n db r i e f l ya n a l y z et h em e t h o do fd e t e c t i n gd u p l i c a t i o n si ni t s e c o n d l y , o nt h eb a s i so fe x i s t i n ga p p r o a c h e sw ep r o p o s ean o v e la l g o r i t h mo f d e t e c t i n gd u p l i c a t i o n si nd a t as t r e a mf o rn e t w o r ks e c u r i t ym o n i t o r i n gs t r e a md a t a t h e a l g o r i t h ma d d sau p d a t ep r o c e d u r et oe x t e n da n dg e n e r a l i z et h er e g u l a rb l o o mf i l t e r b a s e do ni m p r o v e db l o o mf i l t e rf o rt h el a n d m a r kw i n d o wm o d e l ，t h ea l g o r i t h mi s s u p e r i o ri nt e r m so fb o t ha c c u r a c ya n dt i m ee f f i c i e n c yw h e naf i x e ds m a l ls p a c ea n da n a c c e p t a b l ef a l s ep o s i t i v er a t ea r eg i v e n ， f i n a l l y ，w ei m p l e m e n tt h ea b o v ea l g o r i t h mi no u rn e t w o r ks e c u r i t ym o n i t o r i n g d s m s o u rm e t h o dr e d u c e st h eq u a n t i t yo ff o l l o w - u pd a t an e e dt ob ep r o c e s s e da n d a n a l y z e d ，i m p r o v e se f f i c i e n c ya n ds a v e ss t o r a g es p a c e i ns u m m a r y ，t h i sp a p e rf o c u s e so nt h es c e n a r i oo fn e t w o r ks e c u r i t ym o n i t o r i n g , p r o p o s e sa n di m p l e m e n t saa l g o r i t h mo fd e t e c t i n gd u p l i c a t i o n si nd a t as t r e a m ，a n dh a s s o m ep r a c t i c a lv a l u ef o rs t r e a md a t ap r o c e s s i n g k e yw o r d s ：n 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 as t r e a m ，d e t e c t i n gd u p l i c a t i o n s ， d s m s 。b l o o mf i l t e r 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 数据流管理系统与数据库管理系统的比较7 表2 2 数据流管理原型系统9 表2 3 三种数据流管理系统的性能比较1 4 表2 4 单份数据情况2 2 表2 5 同一地点同一时间段数据间比较情况2 2 表4 1b l o o mf i l t e r 算法4 0 表4 2 参数表4 l 表5 1b l o o mf i l t e r + 与s t a b l eb l o o mf i l t e r 、b l o o mf i l t e r 的错误率比较4 6 第1 v 页 国防科学技术大学研究生院学位论文 图目录 图2 1 数据流管理系统的基本结构6 图2 2 数据流处理模型8 图2 3s t i 迮a m 数据流管理系统模型1o 图2 4a u r o r a 数据流管理系统体系结构1 l 图2 5t e l e g r a p h c q 数据流管理系统体系结构1 3 图2 6 界标窗口15 图2 7 滑动窗口15 图2 8 跳动窗口1 6 图2 9h o p p i n g t u m b l i n g 窗口16 图3 1 流数据重复检测模型2 6 图3 2b l o o mf i l t e r 的位数组2 7 图3 3b l o o mf i l t e r 算法流数据处理过程3 l 图4 1 网络安全监控数据流管理系统结构3 5 图4 2 调度器处理元组过程3 7 图4 3 流数据重复检测模块与其他模块的关系3 9 图4 4 流数据重复检测模块体系结构3 9 图4 5w 对f pr a t e 的影响一4 2 图4 6f pr a t e 与f nr a t e 之间的关系4 2 图4 7p 对f pr a t e 、f nr a t e 的影响4 3 图4 8k 对f pr a t e 、f nr a t e 的影响4 4 图5 1 单元值为o 的单元数随处理的流元素增加的变化情况4 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与找一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：j 整塞全监撞生重复塾堡捡型楚苤的婴充当塑一一 学位敞作者签名：垦坠呲础年1 2 月1 7 日 学位论文版权使用授权书 本人完全了解国防干丰学 寺术大学有关保留、使用学位论文的规定，本人。桴移国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档允 许论文放查阅和借阅：可以悔学位沦文的全部或部分内容编入有天数据库进行检索， 可以采用影印、缩印或扫描尊复制手段保序汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 圈整塞全鳖控主重复墼堡拴型筮盔鲍盟窒兰宴逊一 学位论文作者签名：一正娇 作者指导教师签名：坠鱼圣 日期：砷召年i z 月f 7 日 日期：2 r 年，2 月f c 日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究背景 随着计算机技术的迅猛发展和网络应用的日益广泛，互联网在人们的生产生 活中扮演着越来越重要的角色，网络已经成为影响各国政治、经济、社会、军事、 文化、生活的一个重要因素。中国互联网络信息中心( c n n i c ) 在2 0 0 8 年7 月发 布的第2 2 次中国互联网络发展状况统计报告显示川，截至2 0 0 8 年6 月底，中 国己达到1 9 1 的互联网普及率，网民数量达到2 5 3 亿人，与去年同期相比，中 国网民人数增加了9 1 0 0 万人，是历年来网民增长最多的一年，同比增长达到 5 6 2 。仅2 0 0 8 年上半年，中国网民数量净增量就达4 3 0 0 万人，首次大幅度超过 美国，跃居世界第一位。中国的i p v 4 地址数量达到1 5 8 亿个，年增长率为3 3 7 ， 拥有量已经超过日本，跃升至世界第二位；域名注册总量为1 4 8 5 万个，同比增长 6 1 8 ；网站数量已有1 9 1 9 万个，年增长率为4 6 3 。这一系列数据足以表明， 互联网已经成为中国影响最广、增长最快和市场潜力最大的产业之一，并且正在 以超乎人们想象的深度和广度快速发展，人类社会对计算机网络的依赖程度也日 益增强。 然而，由于计算机网络具有开放性、互联性、连接方式的多样性以及终端分 布的不均匀性等特点，再加上本身存在的技术弱点和人为的疏忽，致使网络容易 受到计算机病毒、黑客或恶意软件的侵害。计算机网络的脆弱性和社会对它的高 度依赖性使得国家的经济和国防安全也变得十分脆弱。近年来，全球互联网络频 繁遭受攻击，导致网络大面积瘫痪，重要信息系统的安全受到严重威胁。据美国 联邦调查局统计，美国每年因网络安全造成的损失高达7 5 亿美元。据美国金融时 报报道，世界上平均每2 0 分钟就发生一次人侵国际互联网络的计算机安全事件， 1 3 的防火墙被突破。 与此同时，我国的网络信息化水平已经发展到一定阶段，各种网络安全事件 也变得不可避免，日益严重的网络安全事件，如网络经济犯罪、大规模网络攻击、 网络失窃密等已成为制约我国国民经济发展，甚至危及社会稳定和国家安全的关 键因素。在互联网迅速普及并对人们生产生活影响越来越大的背景下，网络安全 问题己成为各国政府有关部门、各大行业和企事业领导人关注的热点问题，对网 络实施有效的监控，成为迫切的现实需求。然而，网络监控数据随着网民数量的 增长和网络规模的扩大，逐渐呈现分布、海量、高速、连续等特点，大规模网络 监控数据的高效处理需求和有限的计算、存储、网络带宽等资源之间的矛盾日渐 突出，如何采用合适的技术，在有限的计算存储资源情况下，对无限、快速、持 第1 页 国防科学技术大学研究生院学位论文 续到达的网络监控数据进行处理，成为网络监控系统面临的首要问题。 网络监控数据中存在着大量的重复数据。一方面，同一安全事件在传输的过 程中，经过不同路由器时可能会被部署在不同位置的检测设备检测到进行重复记 录；另一方面，t c p 协议的超时重传机制也会引入重复数据。由于重复数据的存 在，在其上进行查询产生的查询结果会受到影响，进而若在这些错误结果上进行 风险评估等后续操作，得到的结论很可能变得不可靠。 在众多的流数据处理中，重复数据检测是一个重要的数据预处理环节。一方 面，可以通过对检测出的重复数据进行分析，进而为后续的风险评估、防御控制 等网络监控应用提供支持；另方面，可以通过删除检测出的重复数据，以便实 现有效的网络传输和高效的在线分析处理。 在实际应用中，现有的技术无法很好的满足对流数据进行重复检测的需求。 因此，本文针对网络安全监控这一典型的数据流应用场景，进一步研究流数据的 重复检测技术，使流数据的重复检测更好地作为流数据处理必不可少的一部分。 1 2 国内外研究现状 在传统的查询处理中，重复数据检测是一项重要的工作，已经提出了许多与 之相关的算法1 2 j 。但是这些所提出的算法都具有一个共同的特点，就是基于假设整 个数据集是已存储的，可以在需要时随时对数据进行访问。因此，在传统数据库 情况下，对数据多次遍历是允许的。然而，在数据流应用场景下，由于数据流本 身的特点，只能对数据进行单遍扫描，要精确地检测重复数据几乎不可能，取而 代之地是以一定的错误率来识别重复数据。 与传统重复数据检测相比，数据流所具有的一些新特性使得重复数据检测问 题更富于挑战。首先，数据流应用的及时响应特性需要数据流处理系统能实时做 出快速响应。其次，数据流潜在的无限特性导致不可能在有限的空间存储整个数 据流。基于上述数据流的特性，在数据流应用中精确地检测重复数据显然是不可 行的。另一方面，在效率比准确率更重要的场合，在满足允许错误率的条件下快 速响应的查询结果通常要优于精确但响应迟缓的查询结果，有时甚至根本没有办 法获得精确的查询结果。 在数据流应用场景下进行重复数据检测的其中一个方法是采用b l o o mf i l t e r 。 a h m e dm e t w a l l y 等1 3 】研究了点击流场景下基于b l o o mf i l t e r 的重复数据检测问题。 他们分别考虑了三种不同的窗口模型：界标窗口、滑动窗口和跳动窗口。在界标 窗口模型中，他们采用原始的b l o o mf i l t e r 检测重复数据，没有考虑到b l o o mf i l t e r 会产生失效的情况。在滑动窗口模型中，他们考虑到b l o o mf i l t e r 的失效问题，改 用计数型b l o o mf i l t e r 检测重复数据，允许删除b l o o mf i l t e r 中的旧信息。然而， 第2 页 国防科学技术大学研究生院学位论文 删除操作只能在已知被删除项的情况下进行，这在许多数据流应用场景下是不可 能的。例如，如果需要删除b l o o mf i l t e r 中最旧的一项，就必须知道最旧的一项接 触的是哪个计数器，但是在计数型b l o o mf i l t e r 中并不能找到这个信息，因为存储 这个信息的代价非常大。在跳动窗口模型中，他们将一个大的跳动窗口分割成多 个子窗口，并且用相同大小的计数型b l o o mf i l t e r 来表示跳动窗口和子窗口。这样， 跳动窗口可以通过增加和删除子窗口的b l o o mf i l t e r 来向前跳动。f a nd e n g 和 d a v o o dr a f i e i 4 】将基于s t a b l eb l o o mf i l t e r 的界标窗口模型应用于u r lc r a w l i n g 场 景下的重复数据检测问题，发现当给定固定小的空间和允许一定误称率的情况下， 他们所提出的方法与可选择的方法相比，在准确率和时间效率方面都较好。 在数据流应用场景下进行重复数据检测的另一个方法是b u f f e r i n g 或c a c h i n g 。 这种方法已经在很多领域得到研究，如数据库系统【2 】、计算机体系结构【5 】、操作系 统【6 j 和在w e bc r a w l i n g 中进行u r lc a c h i n g 。 近期又有人提出了一种可伸缩的重复流数据检测方法【8 】，通过建立降序的时序 区间链表结构，在遍历链表并判断重复性的同时，动态扩展节点的时序区间，或 者动态增加、删除与合并链表节点。这种方法具有自适应性、可伸缩性及精确性， 但主要针对的是连续、有序、反映时段内观测情况的流数据序列，用来精确检测 重复流数据或判断流数据缺失。 1 3 本文研究工作 本文的研究目标：一方面通过对检测出的重复数据进行分析，获取具有一定 价值的重复数据，进而为后续的风险评估、防御控制等网络监控应用提供支持； 另一方面通过删除检测出的重复数据，降低后期需要处理和分析的数据量，以提 高效率，并节约存储空间。研究内容是以网络安全监控为背景，针对当前已有的 数据流管理系统和重复数据检测技术处理流数据存在的问题和不足，提出更适应 网络安全监控数据流管理系统中流数据处理的重复数据检测技术。 1 4 论文组织结构 本篇论文共分为六章，组织结构如下： 第一章为绪论，概述网络安全监控应用需求及其数据处理中面临的问题；总 结了数据流应用场景下重复数据检测技术的研究现状；同时介绍了本文的研究内 容和组织结构。 第二章对流数据重复检测相关技术进行了详细的综述，包括数据流管理系统、 窗口模型、概要数据结构以及网络监控独有的特点。 第3 页 国防科学技术大学研究生院学位论文 第三章提出了网络安全监控数据流管理系统，并以t e l e g r a p h c q 数据流管理 系统为例对其中实现的重复检测方法进行了简单分析。对b l o o mf i l t e r 进行了研究 和分析，提出了针对网络安全监控流数据的重复检测算法，并进行了理论验证与 分析。 第四章给出了网络安全监控数据流管理系统的结构和流数据重复检测模块的 结构，并给出了流数据重复检测算法的具体实现方法。 第五章对流数据重复检测算法的性能进行了验证。 第六章是结束语，总结全文，并对下一步工作进行展望。 第4 页 国防科学技术大学研究生院学位论文 第二章流数据重复检测相关技术 随着计算机、通信、网络技术的迅猛发展，许多应用领域都出现了海量、高 速、动态的数据，如互联网流量监控、传感器数据定位、金融证券管理等。在这 些应用中，按照数据值序列的形式产生数据，需要及时地处理大规模的快速的数 据流。流数据重复检测作为数据流应用场景下一种数据预处理的手段，已经逐渐 引起了人们的关注，一些数据流管理系统中也开始设立专门的重复检测模块。网 络监控是一种典型的数据流应用场景，其独有的特点决定了重复检测在其中的必 要性。本章的组织结构如下：2 1 节主要介绍一些开源的数据流管理原型系统；2 2 节介绍用来处理流数据的窗口模型；2 3 节介绍概要数据结构现有的方法；2 4 节 介绍网络监控独有的特点及进行重复检测的必要性。 2 1 数据流管理系统 随着互联网以及数据密集型应用的发展，产生了大量的实时在线应用需求， 例如网络安全监控、网络通信管理、w e b 日志分析、传感网络、金融数据处理、 股票行情分析等。这些应用产生的数据都具有连续性、数据量大、生成速度快和 生成速率随时间变化等特点。而对这些数据的处理又要求能够做到持续的查询， 有时候甚至要求实时的连续查询。在有限的内存和处理器资源的情况下，保证这 些实时数据能够快速、有效的处理变得越来越重要。传统的数据库管理系统在处 理有限的存储数据方面是高效的，但是处理流数据则效率低下，甚至无法处理。 因此数据流管理系统研究成为目前数据库领域的研究热点。 2 1 1 数据流管理系统介绍 一般地，连续的、近似无限的、时变的、有序的且快速流动的数据元素组成 的无限序列称为数据流。按照固定的次序，这些数据元素只能被读取一次。若令t 表示任一时间戳，z 表示在t 时刻到达的数据元素，则数据流可以表示为无限集合： ，薯一l ，+ l ， 9 1 。 数据流的特斛9 】主要包括： ( 1 ) 有序性、连续性、实时( 或随时) 性：数据有序地、连续地到达并实时 地变化； ( 2 ) 无限性：大数据量，甚至是无限的数据量，存储所有数据的代价是极大 的； ( 3 ) 单遍性：由于内存的限制，只能对数据流进行单遍扫描； 第5 页 国防科学技术大学研究生院学位论文 ( 4 ) 概要性：处理流数据时，要求构造概要数据结构，概要数据结构需要连 续地被更新； ( 5 ) 低层次性和多维性：数据流的原始细节数据的概念层次较低且具有多维 ( 或高维) 的特点； ( 6 ) 近似性：数据流查询以及挖掘处理得到的结果是近似的； ( 7 ) 即时性：用户要求得到即时的处理结果。 另外，分布式数据流除了具有以上特点外，还具有分布性、并行性和多重性 的特点。 由于时间、空间的复杂度较高，传统的数据库技术在某种程度上只能满足数 据流处理的部分要求，已经不适用于解决数据流的查询、挖掘等问题。为了更好 地处理这种新型的数据形式，数据流管理系统应运而生。一般地，数据流管理系 统的基本结构【1 0 , 1 1 1 如图2 1 所示，由输入监控器、存储器、查询计划器、查询监控 器、操作调度器和输出缓冲器等组成。 图2 1 数据流管理系统的基本结构 输入监控器接收各种类型的数据流，需要时可以对输入数据流实行w r a p p e r 操作以便实现统一接收； 典型的存储器由三个部分组成：工作存储器临时存储处理窗口查询操作所用 的数据及维持一个概要数据结构以便进行查询操作，概要存储器存储流数据的概 要，静态存储器存储每个流的物理位置等元数据； 长期运行的查询在查询监控器中注册，构成一个共享执行的群体，查询处理 器与输入监控器进行交流，以便响应输入流数据的变化执行查询优化策略，查询 处理的结果返回给用户或暂存起来提供给后续的查询操作使用； 查询计划器对查询操作、查询概要、查询执行及存储队列动态调整执行计划。 动态分配存储空间、计算及v o 等资源，实现资源的自适应再分配，同时考虑存储 第6 页 国防科学技术大学研究生院学位论文 管理对查询输出和查询结果准确性的影响； 操作调度器主要对流速率的改变、查询请求操作的变更、查询响应时间和服 务质量、卸载、队列存储之间相互作用进行协调。操作调度主要考虑准确性与资 源之间的权衡。操作调度器对多个可选择的查询计划进行权衡，选择查询计划， 合理分配资源，最优化查询结果的准确性和及时性。 数据流管理系统位于用户和操作系统之间，功能主要包括数据流定义、数据 流操作、数据流操纵、数据流维护等，其与传统数据库管理系统的比较如表2 1 所 示f 9 】。 表2 1 数据流管理系统与数据库管理系统的比较 数据流管理系统数据库管理系统 时变的、连续的数据 连续查询 顺序存取 有限的内存空间 历史数据和当前数据都是重要的 实时性、随时性 原始数据的概念层次较低且具有多维性 近似的处理结果 相对稳定的数据 一次性查询 随机存取 足够的内存空间和海量的磁盘存储空间 当前数据是重要的 一般无实时性 数据可具有多个概念层次 精确的处理结果 2 1 2 数据流管理系统存在的问题【1 2 1 根据数据流管理系统的目标和规则，一个良好的数据流管理系统在处理各种 实时数据流时应能满足以下的需求： ( 1 ) 系统结构方面。存储器操作会增加大量没有必要的数据延迟，要避免延 迟，信息应该在流动的过程被实时地处理。数据流管理系统要保持数据的流动性， 就需要一个高度优化、极小开销的执行引擎，在没有新增外部存储设备的情况下， 使大量的应用程序得到实时的处理和响应。 ( 2 ) 查询语言方面。对于数据流管理系统的查询，如果用一般的高级语言( 如 c h 或j a v a ) 作为主要的开发和编程工具会导致漫长的开发周期和高昂的维护费 用。相比之下，人们更希望用像s q l ( 结构化查询语言) 之类的高级语言来处理 流动的实时数据。s q l 有组强大的数据处理原语，来处理过滤、合并、关联和 聚合。要支持面向流的、可扩展的高级数据流查询语言，针对一些基于数据流的 数据集特征，要专门为其设计基于数据流的s q l 语句，以此扩充标准s q l 的语义， 满足流数据处理的不同需求。 ( 3 ) 适应性方面。数据流管理系统要对数据流的不完整性提供弹性支持。在 第7 页 国防科学技术大学研究生院学位论文 对数据流这一刁i 确定性强、实时处理要求高的新型数据形式处理中，适应性显得 尤为重要。数据流管理系统只有周而复始、迅速地从数据流以及系统中获得查询 性能的相关信息，并以此指导自身的后续行为，才能高效地完成对流数据的持续 查询要求。在长时间运行的数据流管理系统中，到达的数据流的属性值会随着时 间发生较大的变化，查询负载和系统条件也会发生改变。查询处理如果缺乏弹性 支持，没有一个适应性机制，当环境改变时，系统性能就有可能会大幅度下降。 ( 4 ) 兼容性方面。有些查询是从过去的某一时刻开始的，为了实现这样的任 务，就需要保留历史数据，将它和现行的数据都集成在相同的系统中。另一些查 询要求从过去的某一时间点开始，一直延续到当前时刻，然后再切换到实际的数 据中持续计算。这就要求系统在没有人工干预的情况下自动地进行无缝切换。数 据流管理系统应具有有效的存储、访问和修改状态信息的能力以及在线查询流动 数据的能力。 数据流管理系统通过扩展s q l ，使用特别的原语和机制来表达面向数据流的 处理逻辑，用于处理流数据，其数据流处理模型如图2 2 所示。 图2 2 数据流处理模型 数据流查询处理模型要在效率、准确性和存储需求之间做出权衡。既然数据 流在容量上可能是无限的，为了得到数据流查询的精确结果，所需的存储器容量 也会无限制地增长。由于存储器的容量是有限的，对数据流查询就不可能总是产 生精确的结果，用高质量的近似结果来替代精确结果往往是可以接受的。处理高 速到达的数据流的一个重要策略是卸载，当输入速率持续超过系统的最大处理速 率时，卸载是必需的，否则会出现输入队列的堆积直到内存耗尽。当系统出现过 载时，按一些服务质量标准丢弃一些元组，使系统的负载下降到一个可管理的水 平。即使到达的平均速率在可计算范围内，也可能会有爆发性的高负载导致必须 第8 页 国防科学技术大学研究生院学位论文 使用大量内存来缓冲堆积的未处理元组。为了适应这种爆发性的数据流，可以通 过有效地调度运算符，降低内存需求量的峰值，才能在数据流到达速率回落的时 候清除堆积的未处理元组。通过使用卸载和合适的调度策略，做到尽可能降低系 统存储需求，同时保持较低的输出延迟。 2 1 3 数据流管理原型系统实例 针对目前出现的这种对流数据进行管理的应用需求，国内外许多大学和机构 已在这方面开展了大量的研究工作，部分已公开的数据流管理原型系统如表2 2 所 示【9 1 。其中，s t r e a m 是一个通用的数据流管理原型系统，该系统提供了一种连 续查询语言c q l ，既可以处理流数据又可以处理关系型数据。a u r o r a 是应用于数 据流监控的原型系统，其核心组成是多个触发器组成的网络，该系统可以执行一 些优化处理，如c o m p i l e - t i m e 和r u n - t i m e 优化，以及卸载处理等【9 】。 表2 2 数据流管理原型系统 2 1 3 1s t r e a m i n , 1 3 , 1 4 由斯坦福大学设计和实现的s t r e a m 是一个处理在多重连续数据流和关系型 数据上的连续查询的通用系统，它重点在于内存管理和近似查询。它可以用于处 理快速的、易变的、大量涌入的数据流信息，其连续查询能力非常好。于2 0 0 2 年 第9 页 国防科学技术大学研究生院学位论文 提出，2 0 0 6 年停止研究。s t r e a m 数据流管理系统的模型如图2 3 所示。 图2 3s t r e a m 数据流管理系统模型 s t r e a m 定义了一种公开的描述性连续查询语言c q l ( c o m i n u o u sq u e r y l a n g u a g e ) ，建立了数据流到关系、关系到关系、关系到数据流的映射。c q l 语言 是s q l 语言的一个超集，对s q l 语言的语义进行了扩充，简化了s q l 语言的一 些语法，引入了等价的关系，使c q l 能够处理数据流，且在关系运算上比s q l 效率有所提高。另外，c q l 语言还引入了w i n d o ws p e c l a n g u a g e 来定义数据流 的存取方式。用户可以用c q l 注册查询，也可以直接输入查询计划。系统对数据 流按照用户的查询需求进行实时的连续查询，并为各种形式的连续查询提供连续 的和实时的结果。s t r e a m 系统可以直接以h t t p 方式提供w e b 接口。系统提 供一个基于w e b 的图形用户接口，通过该接口远程应用程序可以不受开发平台和 编程语言的限制，直接注册查询并以h t t p 流的形式获得x m l 格式的查询结果。 此外，该接口还向用户提供了一个交互式监控系统运行的途径。 s t r e a m 系统包括：数据流和己存储的关系；注册连续查询的描述性语言； 灵活的查询计划和执行策略；文本的、图形的和应用接口。具有以下特点：在已 注册的查询间共享状态和计算；合理的资源分配和使用；连续的自我监控和再优 化；适应于不同需要的良好近似。 2 1 3 2a u r o r a b 5 - 1 8 】 a u r o r a 是由m i t 、b r o w n 和b r a n d i e s 共同开发的数据流管理系统，于2 0 0 3 年 3 月完成了其原型实现。a u r o r a 是一个为监控应用设计的原型系统，它适用于监控 来源于物理传感器的数据、网络流量信息、g p s 设备获取的数据等等，其体系结 构如图2 4 所示。 第1 0 页 国防科学技术大学研究生院学位论文 卜 一一 y 卜 r i n p u td a t ao u t p u tt o s t r e a m s a p p l i c a t i o n s 卜 y 卜 、i r、i o p e r a t o 沙rb o x e s c o n t 劬吣出搬 y i s t o r a g ei q u e n 鹤 、- 一， 图2 4a u r o r a 数据流管理系统体系结构 a u r o r a 系统采用了工作流系统中常用的b o x ( 查询操作符) & a r r o w ( 查询操 作符之间的数据流) 模型，由用户直接从多种操作符中进行选择并组合成由操作 符构成的网络模型。输入的数据流经过操作符序列的处理，将结果输出给应用程 序。系统还利用h i s t o r i c a ls t o r a g e 结构保存历史数据以支持a d h o c 查询。a u r o r a 的特殊之处在于，它给每个输出关联一个或多个简单q o s 信息反馈，系统运行时 可以根据这些q o s 信息对动态的资源分配提出一定的指导建议。 a u r o r a 原型由基于j a v a 的图形用户界面、目录管理器、存储管理器、实时调 度器和几个基本的流处理操作符组成。a u r o r a 系统包括：基于j a v a 的图形用户界 面开发环境，用来定义元组结构和a u r o r a 流网络；执行a u r o r a 网络的服务器， a u r o r a 服务器的输入和输出都是t c p i p 接口分发的元组流；基于j a v a 的图形用户 界面性能监控器，显示给定时刻服务器提供的服务质量。 a u r o r a 系统的特点： 面向流的查询操作符。a u r o r a 包含7 个原始的操作符：f i l t e r 、m a p 、u n i o n 、 b s o r t 、a g g r e g a t e 、j o i n 和r e s a m p l e ，用来表示流处理的需求； q o s 规范。不仅作为期望的系统行为规范，而且提供调度和卸载的驱动策略。 q o s 通过三个函数记录：( 1 ) 延迟图( 2 ) 基于值的图( 3 ) 容错图。延迟图显示 当应答延迟时，效用如何下降。基于值的图显示输出空间的哪个值最重要。容错 图简单描述应用与近似回答的不同； 卸载。调度程序使用q o s 规范确定何时怎样删除记录； 实时调度； 存储管理。存储有序的元组队列而不是元组集，将基于p u s h 的队列存储与基 于p u l l 的历史存取结合。a u r o r a 有两种不同的方式支持持久的存储。第一种，当 盒子队列消耗的存储超过可用的r a m 时，系统溢出不太可能马上使用的元组到二 级存储。第二种，特殊查询可以通过连接点定义连接到任何a r c 和断开连接。一个 第1 1 页 国防科学技术大学研究生院学位论文 连接点存储已经流过a l e 。的流历史部分。当查询连接时，任何连接到连接点的特殊 查询可以访问整个存储的历史和过去流过的任何额外数据。 a u r o r a 系统是一个具有完全功能原型的面向监控应用的实验性数据流管理系 统，包括图形化的开发环境和运行系统。a u r o r a 被设计用来处理超大规模的数据 流。特点是利用q o s 概念来实现调度控制机制、内存的动态管理以及负载均衡。 q o s 的参数可以是查询处理的响应时间、丢弃的分组数、处理结果的精度等等。 在系统运行过程中，通过改变q o s 参数的值就可以实现系统处理资源的动态分配。 a u r o r a 的算子采用了s q u a l ( s t r e a mq u e r ya l g e b r a ) 语言。s q u a l 定义了处理数据 流所需要的一些运算规则，例如f i l t e r 、m a p 、u n i o n 、o r d e r 、b s o r t 和a g g r e g a t e 等，这些运算规则不但具有s q l 语言的关系运算能力，而且还具有数据流的运算 能力。 a u r o r a 系统主要针对三个主要的应用类型： 1 、实时监控应用，连续监控世界的现状，并对来自环境最新的数据感兴趣。 ( 监控应用指监控连续的数据流，检测异常行为并向用户报警) ； 2 、处理以时间序列存储的大量历史数据的档案管理型应用，对过去感兴趣。 主要关心处理存储在时间序列仓库的大量有限数据； 3 、包含对历史以及当前数据进行处理的跨度应用，包括世界当前的和过去的 状态，需要对输入的实时数据和储存的历史数据进行合并、比较。 2 1 3 3t e l e g r a p h c q t l 9 。2 1 】 由b e r k e l e y 大学开发研究的t e l e g r a p h c q 系统是