维普资讯 http://www.cqvip.com 第２４卷第１２期 计算机应用研究 Ｖｏ１．２４ Ｎｏ．１２ ２００７年ｌ２月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｄｅｃ．２００７ 基于结构化Ｐ２Ｐ的分布式数据流 系统的查询处理模型 刘云生，赵海谊 （华中科技大学计算机科学与技术学院，武汉４３００７４） 摘要：分析了基于结构化覆盖网的分布式查询处理模型，支持大量数据流的分布式存储，连续查询间、查询内 的并行处理操作，能够在很大程度上消除资源约束问题（主要是内存），提高了查询性能、服务质量，并且该查询 模型具有很好的扩展性。 关键词：分布式数据流管理系统；结构化覆盖网；分布式散列表；滑动窗１７＂ 中图分类号：ＴＰ３１１．１３ 文献标志码：Ａ 文章编号：１００１—３６９５（２００７）Ｉ２—００７４—０３ Ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａ ｓｔｒｅａｍ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｓｔｒｕｃｔｕｒｅｄ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ ＬＩＵ Ｙｕｎ—ｓｈｅｎｇ，ＺＨＡＯ Ｈａｉ—ｙｉ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇ），Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ．Ｗｕｈａｎ ４３００７４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａ ｓｔｒｅａｍ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ ｍｏｄｅｌ ｓｕｐｐｏｒｔｅｄ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒｉｎｇ ｏｆ ｄａｔａ ｓｔｒｅａｍｓ，ｉｎｔｅｒ—ｏｐｅｒａｔｏｒ ｐａｒａｌｌｅｌｉｓｍ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ，ｉｎｔｒａ—ｏｐｅｒａｔｏｒ ｐａｒａｌｌｅｌｉｓｍ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ，ａｎｄ ｒｉｄｅｄ ｔｈｅ ｃｏｍｐｕｔｉｎｇ ｒｅｓｏｕｒｃｅ ｒｅｓｔｒｉｃｔｉｏｎ，ｅｓｐｅ— ｃｉａｌｌｙ ｔｈｅ ｍｅｍｏｒｙ ｌｉｍｉｔａｔｉｏｎ．Ｓｏ ｉｔ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ，ｑｕａｌｉｔｙ ｏｆ ｓｅｒｖｉｃｅ，ａｎｄ ｏｆ ｇｏｏｄ ｓｃａｌａｂｉｌｉｔｙ ａｓ ｗｅ／１． Ｋｅｙ ｗｏｒｄｓ：ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａ ｓｔｒｅａｍ ｍａｎａｇｅｍｅｎｔ ｓｙｓｔｅｍ；ｓｔｒｕｃｔｕｒｅｄ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ；ｄｉｓｔｒｉｂｕｔｅｄ ｈａｓｈ ｔａｂｌｅ（ＤＨＴ）；ｓｌｉｄｉｎｇ Ｗｉｎｄｏｗ 近年来，数据流查询处理是数据库研究领域的一个热点 方向。数据流的特征可概括为无限性、瞬时性 流速不定性、 １ 集中式数据流查询处理及分布式散列表、Ｃｈｏｒｄ 语义不定性（数据模式随时可能改变）等。针对数据流的以 路由协议的相关说明 上特征，不考虑将数据流存储在传统的关系数据库中，数据 １．１ 数据流查询处理相关的概念定义以及假设说明 流上的查询是近似查询、连续查询（ｃｏｎｔｉｎｕｏｕｓ ｑｕｅｒｙ）。日前， 数据流管理系统中所采用的近似查询的方法主要有以下几 集中式数据流查询处理的体系结构由两部分构成，即查询 种：随机抽样（ｒａｎｄｏｍ ｓａｍｐｌｉｎｇ）、数据写生（ｓｋｅｔｃｈｉｎｇ）、直方 计划生成子系统（ＦＲＯＮＴ ｅｎｄ）以及查询执行子系统（ＢＡＣＫ）。 图（ｈｉｓｔｏｇｒａｍｓ）、小波变换（ｗａｖｅｌｅｔｓ）、窗口（ｗｉｎｄｏｗｓ）等。如 其中两部分与关系数据库系统相比均有较大的区别。查询执 何保证查询的服务质量成为上述各种近似查询方法必须考 行子系统如图１所示。 虑的问题。数据流上的查询处理给人们提出了一个很大的 窗Ｌ１状态ＳＷＳＹＮ Ｉ 难题——对处理器、内存等系统资源非常苛刻的需求。到目 前已经出现了许多数据流的原型系统：单节点（单ＣＰＵ）上的 数据流管理系统，如Ｓｔａｎｆｏｒｄ大学的Ｓｔｒｅａｍ【。系统、布朗大学 ／，—、、／—＇ ｎ 的Ａｕｒｏｒａ 系统等；有分布式数据流处理系统，如ＭＩＴ的 。 Ｍｅｄｕｓａ 项目，Ｂｒａｎｄｅｉｓ、Ｂｒｏｗｎ、ＭＩＴ的合作项目Ｂｏｒｅａｌｉｓ 。 连续查询（含有大量即席查询） 等。这些项目在数据流处理的查询语言、近似查询算法、保 图１ 集中式数据流系统的查询计划执行子系统 证服务质量的策略，以及系统的负载均衡等方面做了大量的 定义１ 数据流Ｓ：｛（ｓ，ｔ）ｉ。其中：ｓ是满足数据流模式 工作，但同时也揭示出在分布式数据流处理系统中更多值得 的记录； 是时间戳｝。数据流是一个无穷有序元组序列。 研究的问题。本文将对基于ｓｔｒｕｃｔｕｒｅｄ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ的分布 说明１ 数据流模式（ｓｔｒｅａｍ ｓｃｈｅｍａ）与关系数据库中的 式数据流系统的近似、自适应查询处理进行研究，给出查询 关系模式意义相同。其中时间戳（时标）不属于数据流模式的 处理模型。 一部分。时间戳是系统定义的逻辑时间，而不是物理时间。数 收稿１３期：２００６．０７．２６；修返日期：２００６．１０．２０ 作者简介：刘云生，男，博导，主要研究方向为操作系统、数据库；赵海谊，男，硕士研究生，主要研究方向为数据库、分布式数据流处理系统 （ｅｈｏｕｈｙ２００３＠ｙａｈｏｏ．ｅＯＩＴＩ．ｃｎ）、 维普资讯 http://www.cqvip.com 第１２期 刘云生，等：基于结构化Ｐ２Ｐ的分布式数据流系统的查询处理模型 ・７５・ 据流查询处理计划主要由三部分构成，即操作符（即算子）、操 作符的状态（如ｊｏｉｎ以及聚集操作符中ＭＡＸ、ＭＩＮ、ＡＶＧ、ＳＵＭ、 种Ｃｈｏｒｄ路由协议。其中使用ｆｉｎｇｅｒ ｔａｂｌｅｓ算法构造路由表。 １）数据流分片存储一假定时问长度为ｒ的数据流元组为 ＣＯＵＮＴ）和队列（在操作符问传递记录的数据结构，即内存中 的物化，流水线方式）。 说明２ 数据流是无穷有序元组序列。从系统视图来看， 数据库系统是用户查询驱动模式（ｐｕｌ１）；而数据流系统是数据 驱动模式（ｐｕｓｈ）。数据流到达后，系统必须进行大量的查询处 理。这些处理是系统预先定义的，也可以是用户的即席查询 分片，系统起始时刻为 ，准备存储ｍ片分片数据流，则 ５［ ， ＋ ］，５［ ＋ ， ＋２ ］，…，５［ ＋打， ＋（ｉ＋１） ］， ５［ ＋（ｍ一１）ｒ， ＋ｍ ｒ］（０≤ｉ＜ｍ，ｉ为整数）为（ ＋ｍｒ）时刻 数据分片。在基于滑动窗口的数据流近似查询中，（ ＋ｍｒ）之 后任何时刻系统中将只有一个数据流分片的记录发生更新，即 最早进入系统的数据流分片（５［ ， ＋ｒ］）被当前进入系统数 （Ａｄ ｈｏｃ ｑｕｅｒｉｅｓ）。窗口是将无穷元组转换为有限元组的多种 据流更改。考虑到服务质量，可以调整ｒ的取值（即数据分片 操作符中的一种。窗口类型有多种（滑动窗口等），根据窗口 内容可以分为基于时间的滑动窗口、基于内容的滑动窗口等。 １．２分布式散列表以及路由协议Ｃｈｏｒｄ的相关介绍 分布式散列表（ＤＨＴ）同ｈａｓｈ ｔａｂｌｅ意义相同，即键一值映 射，只是扩展到了分布式环境下。 ＤＨＴ这种数据结构决定了数据存放不是随意的。每一个 数据对象（数值）的存放位置（节点）是由这个数据的键决定 的，键必须是惟一的。每个ＤＨＴ系统均支持一个简单的接口、 给定键、路由消息给键所在的节点。其中消息包括ｐｕｔ（ｋｅｙ， ｏｂｊｅｃｔ）以及ｇｅｔ（ｋｅｙ）、ｒｅｍｏｖｅ（ｋｅｙ）等。 Ｃｈｏｒｄ算法是由ＭＩＴ提出的一种ＤＨＴ系统中用于资源放 置以及查找的路由协议，将ｋｅｙ映射到一维的结构环上。 Ｈａｓｈ的算法有很多种，如ｃｏｎｓｉｓｔｅｎｔ ｈａｓｈｉｎｇ、ｆｉｎｇｅｒ ｔａｂｌｅｓ等。 其中ｆｉｎｇｅｒ ｔａｂｌｅｓ路由算法更优，每个节点需要Ｏ（１ｇｎ）大小的 存储空间保存拓扑信息。查询时通过递归以类似于二分查找 的速度接近目的节点，最终查找成功，查找节点所需的时问复 杂度为Ｏ（１ｇｎ）。 在基于ｓｔｒｕｃｔｕｒｅｄ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ中，对象定位模型的基本 结构为：对于每个节点和对象均具有全局惟一的ｉｄ；对象ｏｉｄ与 节点ｎｉｄ之间是多对一的；对于每一个对象ｏｉｄ必定映射到惟一 的节点ｎｉｄ。对于每一个对象，在某节点存放该对象时，建立对 象索引，包括对象ｏｉｄ、存储对象的节点位置等信息，并将该对象 索引存放到映射后的惟一节点ｎｉｄ上。当其他节点需要定位该 对象时，通过路由算法到达存放有对象索引的节点ｎｉｄ，然后由 对象索引得到存储对象的节点位置，从而能够访问到对象。 ２ 分布式数据流系统的查询处理模型 图２给出了结构化Ｐ２Ｐ网络中每一个节点上基本的数据 流查询处理体系结构。 图２单节点数据流查询处理的软件体系结构 除了查询处理器（ｑｕｅｒｙ ｐｒｏｃｅｓｓｏｒ）与上述单节点下查询处 理器的操作相同（最终生成物理查询计划，由算子、分布式下 不同节点上操作符问传递元组的队列、保存有状态操作符的大 纲组成一个网状图），每个Ｐ２Ｐ节点数据存储层中的分片数据 流及其维护的目录（ｃａｔａｌｏｇ）信息，对于分布式数据流系统支持 大量的、连续的查询起非常重要的作用。 数据存储层中数据模式为：假定数据流处理系统由Ⅳ个 节点组成结构化Ｐ２Ｐ网络，采用了ＤＨＴ系统多种实现中的一 的大小）。每个数据分片有惟一的名称５（ｉ）。根据Ｃｈｏｒｄ中 的ｈａｓｈ函数可知：ｓｔｒｅａｍＫｅｙ＝ＳＨＡ一１（５（ｉ）），Ｎｏｄｅｉｄ＝ＳＨＡ一１ （ｎｏｄｅ ＩＰ ａｄｄｒｅｓｓ）。然后将ｓｔｒｅａｍＫｅｙ映射到Ｎｏｄｅｉｄ，构造 ｎ— ｇｅｒ ｔａｂｌｅｓ，查询通过ｐｕｔ（ｓｔｒｅａｍＫｅｙ，ｖａｌＵｅ），ｇｅｔ（ｓｔｒｅａｍＫｅｙ）就可 以得到一个指定的分片数据流 （ｉ）的数据。通过这种机制， 在系统中维护一个较长时间的数据流。如果考虑将数据流记 录保存很长的时间，可以采用相同方式，数据流存储在文件系 统，不再是内存缓冲区中。 ２）维护系统ｃａｔａｌｏｇ目录信息的机制 系统ｃａｔａｌｏｇ中存放 当前系统中所有关于数据流模式、数据流、系统中正在运行的 查询处理等信息。但是在分布式流处理环境中，ｃａｔａｌｏｇ信息是 分布式地存放在各个节点上面。每个节点维护部分ｃａｔａｌｏｇ信 息。节点之间路由消息维护ｃａｔａｌｏｇ信息的一致性、完整性。 目录ｃａｔａｌｏｇ分片采用合适的命名规则，每个分片通过ｈａｓｈ函 数生成惟一的ｋｅｙ，映射到Ｎｏｄｅｉｄ，构造ｆｉｎｇｅｒ ｔａｂｌｅｓ，最终实现 ｃａｔａｌｏｇ目录信息的分布式存储。通过ｐｕｔ（ｋｅｙ，ｖａｌｕｅ）、ｇｅｔ （ｋｅｙ）、ｒｅｍｏｖｅ（ｋｅｙ）等路由消息来维护目录信息的一致性、完 整性。 下面通过一组数据流上面的查询实例来说明在结构化 Ｐ２Ｐ中，上述的数据存储层以及可扩展的通信层（ＤＨＴ ｌａｙｅｒ） 是如何支持分布式连续查询的。其中支持两类查询，即查询内 并行（不同节点ｎｏｄｅ上的算子之间可以路由数据、传输保存算 子状态的大纲）和查询问并行（不同的查询并行执行。这是目 前数据流处理系统中普遍采用的查询类型）。 Ｒｅｌａｔｉｏｎ：ＣｕｒＰｒｉｃｅ（ｓｔｏｃｋ，ｐｒｉｃｅ）股票价格 Ｒｅｌａｔｉｏｎ：Ｓｔｏｃｋ（ｓｔｏｃｋ，ｃｏｍｐａｎｙ）一个公司的股票 Ｑｕｅｒｙｌ：Ｓｅｌｅｃｔ ｓｔｏｅｋ．Ａｖｇ（ｐｒｉｃｅ） Ｆｒｏｍ Ｓｔｒｅａｍ（ＣｕｒＰｒｉｃｅ）［Ｒａｎｇｅ １ Ｄａｙ］ Ｇｒｏｕｐ Ｂｙ ｓｔｏｃｋ一天内各种股票的平均价格 Ｑｕｅｒｙ２：Ｓｅｌｅｃｔ Ｍａｘ（ｐｒｉｃｅ），ｃｏｍｐａｎｙ Ｆｒｏｍ Ｓｔｒｅａｍ（ＣｎｒＰｒｉｃｅ）［Ｒａｎｇｅ ２ ｈｏｕｒｓ］，Ｓｔｒｅａｍ（Ｓｔｏｃｋ） Ｗｈｅｒｅ Ｓｔｒｅａｍ（ＣｕｒＰｆｉｃｅ）．ｓｔｏｃｋ＝Ｓｔｒｅａｍ（Ｓｔｏｃｋ）．ｓｔｏｃｋ ａ）查询问并行处理方式如下： ｋｅｙｌ＝ＳＨＡ一１（ｎｏｄｅｌＰ ｑｕｅｒｙ１） ｋｅｙ２＝ＳＨＡ一１（ｎｏｄｅＩＰ ｑｕｅｒｙ２） 构造ｆｉｎｇｅｒ ｔａｂｌｅｓ ｐｕｔ（ｋｅｙ１，查询１的内容一一字符串序列） ｐｕｔ（ｋｅｙ２，查询２的内容一一字符串序列） 通过这种散列，将系统当前的所有查询映射到节点空间， 然后由该节点上的查询处理器完成到达的查询。 ｂ）查询内并行处理方式。在系统的范围内，由操作符、输 入均输出记录队列、维持操作符状态的大纲信息构成网状结 构。 Ｃ）命名发现机制。参与查询处理的节点有全局惟一命名 ｐａｒｔｉｃｉｐａｎｔ（如ＩＰ地址等）。当在一个节点上面定义一个新的 维普资讯 http://www.cqvip.com ・７６・ 计算机应用研究 第２４卷 流模式、数据流、操作符，这些实体均隶属于其命名空间。该实 体可以采用下面的命名方式：（ｐａｒｔｉｃｉｐａｎｔ，ｅｎｔｉｔｙ—ｎａｍｅ）。为了 了解系统中数据流模式的定义、系统中的数据流、数据流的到 达（存放）位置、系统中哪一部分查询执行，就要考虑在ｃａｔａｌｏｇ 中存放必要的数据。其中ｃａｔａｌｏｇ信息是通过在ＤＨＴ下分布式 存储的，前面已经分析了ｃａｔａｌｏｇ信息的存储问题。 子在分布式节点的迁移等提供了很好的支持。对系统ｃａｔａｌｏｇ 目录信息的分布式存放维护，从而消除¨ｒ单节点查询处理引擎 在资源（ＣＰＵ、内存）上的约束。本文没有考虑分布式查询模型 在网络带宽资源方面的问题，这将是以后要完善的地方。基于 结构化覆盖网的分布式数据流查询模型提高了系统性能、查询 服务质量，并且基于Ｃｈｏｒｄ实现，具有很好的扩展性。 参考文献： ｌ １］ＢＲＩＡＮ Ｂ．ＳＨＩＶＮＡＴＨ Ｂ，ＪＥＮＮＩＦＥＲ Ｗ．Ｍｏｄｅｌｓ ａｎｄ ｉｓｓｕｅｓ ｉｎ ｄａｔａ ｓｔｒｅａｍ ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｃ￣：ｏｆ ｔｈｅ ２１ ｓｔ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ，２００２． 系统中对每一个数据流、每一个查询、查询中的算子、算子 大纲、节点问输出队列均有惟一的命名。查询处理器位于 ＤＨＴ之上。同查询相关的数据粒度限定为数据流、输入数据 源（记录集）、节点间传输数据队列、算子大纲，而不是针对单 个记录而言。对于这些粒度的数据可以通过在ＤＨＴ中通过 ｐｕｔ（ｎａｍｅｓｐａｃｅ，ｏｂｊｅｃｔ）、ｇｅｔ（ｎａｍｅｓｐａｃｅ）、ｍｕｈｉｃａｓｔ（ｎａｍｅｓｐａｃｅ） ２］ＢＡＬＡＫＲＩＳＨＮＡＮ Ｈ，ＢＡＬＡＺＩＮＳＫＡ Ｍ，ＣＡＲＮＥＹ Ｄ，ｅｔ ａ１． Ｒｅｔｒｏｓｐｅｃｔｉｖｅ ｏｎ Ａｕｒｏｒａ［Ｊ Ｊ．ＶＬＤＢ Ｊｏｕｒｎａｌ，２００４，１３（４）：３７０ ３８３ 消息得到。 对于操作符（算子）在节点间迁移的情况，可以提供远程 ｌ ３］ＡＢＡＤＩ Ｄ．ＣＡＲＮＥＹ Ｄ，ＳＴＯＮＥＢＲＡＫＥＲ Ｍ，ｅｔ ａ１．Ａｕｒｏｒａ：ａ Ｂｅ 算子定义接口。当节点４上查询执行的下一步ｊｏｉｎ操作要求 节点Ｂ的查询执行器完成时，节点Ｂ接收到远程调用清求，初 ｍｏｄｅｌ ａｌｌｄ ａｒｃｈｉｔｅｃｔｕｒｅ ｔｈｒ ｄａｔａ ｓｔｌＴｅａｍ ｍａｎａｇｅｍｅｎｔ［Ｊ］．ＶＬＤＢ Ｊｏｕｒ－ ｈａｌ，２００３，１２（２）：１２０—１３９． ［４１ ＺＤＯＮＩＫ Ｓ，ＳＴＯＮＥＢＲＡＫＥＲ Ｍ，ＣＩｔＥＲＮＩＡＣＫ Ｍ，ｅｔ ａ１．Ｔｈｅ Ａｕｒｏｒａ ａｎｄ Ｍｅｄｕｓａ Ｐｒｏｊｅｃｔｓ【Ｊ ｊ．ＩＥＥＥ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ Ｂｕｌｌｅｔｉｎ，２００３， ２６（１）：３—１０． 始化ｊｏｉｎ算子，将节点４上发出调用请求算子的状态信息（大 纲，ｓｙｎｏｐｓｉｓ）作为参数传递给Ｂ，然后就町以在节点Ｂ Ｌ进行 ｊｏｉｎ算子运算。查询内并行就是有若于这样的节点问的算子 迁移，使一个查询计划得以在多节点的算子之间并行执行。 对于基于滑动窗口的数据流处理的ｊｏｉｎ操作，如果有两个 数据流，查询处理基于时间的窗口，进行ｊｏｉｎ操作的两个数据 流时间范围较长，那么要求在一个节点上维护操作符的状态信 息将会变得非常困难，ｊｏｉｎ算子状态信息存储要求的内存空间 可能非常大，则会进行操作符分割操作。在该节点的近邻节点 ［５ ｊ ＣＨＥＲＮＩＡＣＫ Ｍ，ＢＡＬＡＫＲＩＳＨＮＡＮ ｔｔ，ＢＡＬＡＺＩＮＳＫＡ Ｍ，ｅｔ ａ１． Ｓｃａｌａｂｌｅ ｄｉｓｔｉｒｂｕｔｅｄ ｓｔｒｅａｍ ｐｒｏｃｅｓｓｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １ ｓｔ Ｂｉｅｎｎｉａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ．Ａｓｉｌｏｍａｒ，Ｃａｌｉｆｏｒ— ｎｉａ：［ｓ．ｆｌ ｆ，２００３． ［６ ＡＢＡＤＩ Ｄ Ｊ，ＡＨＭＡＤ Ｙ，ＢＡＬＡＺＩＮＳＫＡ Ｍ，ｅｔ ａ１．Ｔｈｅ ｄｅｓｉｇｎ ｏｆｔｈｅ Ｂｏｒｅａｌｉｓ ｓｔｒｅａｍ ｐｒｏｃｅｓｓｉｎｇ ｅｎｇｉｎｅ ｆ Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｎｄ Ｂｉｅｎｎｉｌａ Ｃｏｎ— ｆｅｒｅｎｃｅ Ｏｈ Ｉｎｎｏｖａｔｉｖｅ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ（ＣＩＤＲ’０５）．Ａｓｉｌｏｍａｒ： 上同时进行ｊｏｉｎ操作，最终将各个节点上的状态信息进行合并 操作即可。 ［ｓ．ｎ．１，２００５． ［７］ＴＡ ＦＢＵｌ Ｎ，ＺＤＯＮＩＫ Ｓ．Ｄｅａｌｉｎｇ ｗｉｔｈ ｏｖｅｒｌｏａｄ ｉｎ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｒｅａｍ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ［Ｃ ｊ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ Ｍｅｅｔｓ Ｄａｔａｂａｓｅｓ（ＮｅｔＤＢ’０６）．Ａｔｌａｎｔａ：［ｓ．ｎ．］，２００６． 算子迁移、算子合并、算子分割等操作在基于ＤＨＴ的系统 上实现具有良好的扩展性。ＤＨＴ层为数据流处理系统在荷载 大的情况下进行负载脱落、查询计划间并行、查询计划内并行 ｝８］Ｄｉｓｔｉｒｂｕｔｅｄ ｈａｓｈ ｔａｂｌｅｓ ｌｉｎｋｓ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｅｔｓｅ．ｕｒｖ．ｅｓ／一 ｅｐａｉｒｏｔ／ｄｈｌｓ ｈｔｍ１． 提供了可以随意扩展的基础平台。 ［９］ＤＡＢＥＫ Ｆ．ｓＴＯＩＣＡ Ｉ，ＢＡＬＡＫＲＩＳＨＮＡＮ Ｈ，ｅｔ ａ１．Ｂｕｉｌｄｉｎｇ ｐｅｅｒ—ｔｏ— ｐｅｅｒ ｓｙｓｔｅｍｓ ｗｉｔｈ Ｃｈｏｒｄ，ａ ｄｉｓｔｉｒｂｕｔｅｄ ｌｏｏｋｕｐ ｓｅｒｖｉｃｅ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ８ｔｈ Ｗｏｒｋｓｈｏｐ ｏｎ ｔｔｏｔ Ｔｏｐｉｃｓ ｉｎ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ（ＨｏｔＯＳ—ＶＩＩＩ）． ２ｏ¨１． ３结束语 本文给出了基于ｓｔｒｕｃｔｕｒｅｄ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ的分布式数据 ｆ １０ Ｊ ＳＴＯＩＣＡＬ １，ＭＯＲＲＩＳ Ｒ，ＢＡＬＡＫＲＩＳＨＮＡＮ Ｈ，ｅｔ ａ１．Ｃｈｏｒｄ：ａ ｓｃａ－ ｌａｂｌｅ ｐｅｅｒ—ｔｏ ｐｅｅｒ ｌｏｏｋｕｐ ｓｅｒｖｉｃｅ ｆｏｒ ｉｎｔｅｒｎｅｔ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００１：１４９－１６０． 流查询处理模型，考虑了对于到达系统的大量数据流的分片存 放策略；同时在查询处理中对查询内的并行、查询问的并行、算 （上接第７３页） ３０ｔｈ ＶＬＤＢ Ｃｏｎｆｅｒｅｎｃｅ．Ｔｏｒｏｎｔｏ：Ｅｐｒｉｎｔ ａｒＸｉｖ，２００４：２２８ ２３９． ［８］ＣＨＵＮＧ Ｗ．Ａｎ ｅｘｔｅｎｓｉｏｎ ｏｆ ＸＱｕｅｒｙ ｆｏｒ ｍｏｖｉｎｇ ｏｂｊｅｃｔｓ ｏｖｅｒ ＧＭＬ ［Ｃ］／／Ｐｒｏ（：ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｏｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ： Ｃｏｄｉｎｇ ａｎｄ Ｃｏｍｐｕｔｉｎｇ．Ｌ孙Ｖｅｇａｓ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｕｅｉｅｔｙ，２００４： １４２．１４７． ［３］ＦＥＧＡＲＡＳ Ｌ．Ｔｈｅ ｊ。ｙ ｏｆ ＳＡＸ［Ｃ］／／Ｐｒｏ（；ｏｆ ｔｈｅ ｌ ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ ＸＱｕｅｒｙ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，Ｅｘｐｅｒｉｅｎｃｅ，ａｎｄ Ｐｅｒｓｐｅｃｔｉ￣’ｅｓ． Ｐａｒｉｓ：Ｍａｉｓｏｎ ｄｅ ａｌ Ｃｈｉｍｉｅ．２００４：６ｌ一６６． ［９］Ｗｒｉｔｉｎｇ ｅｘｔｅｎｓｉｏｎ ｆｕｎｃｔｉｏｎｓ ｉｎ Ｊａｖａ，Ｓａｘｏｎ ｄｏｃｕｍｅｎｔａｔｉｏｎ［ＥＢ／ＯＬ］． ［２００６］．ｈｔｔｐ：／／ｗｗｗ．ｓａｇｏｎｉｃａ．ｃｏｒｎ／ｄｏｃｕｍｅｎｔａｔｉｏｒｔ／ｅｘｔｅｎｓｉｂｉｌｉｔｙ／ ｆｕｎｏｔｉｏｎｓ．ｈｔｍ１． ［４］ＬＩ Ｘｉａｏ—ｇａｎｇ，ＡＧＲＡＷＡＬ Ｇ．Ｅｆｉｃｉｆｅｎｔ ｅｖａｌｕａｔｉｏｎ ｏｆ ＸＱｕｅｒｙ ｏｖｅｒ ｓｔｒｅａｍｉｎｇ ｄａｔａ［Ｃ］／／Ｐｒｏｅ ｏｆｔｈｅ ３１ ｓｔ ＶＬＤＢ Ｃｏｎｆｅｒｅｎｃｅ．Ｔｒｏｎｄｈｅｉｍ， Ｎｏｒｗａｙ．［ｓ．ｎ．］，２００５：２６５－２７６． ［５ Ｊ ＢＯＳＥ Ｓ，ＦＥＧＡＲＡＳ Ｌ．Ｄａｔａ ｓｔｒｅａｍ ｍａｎａｇｅｍｅｎｔ ｆｏｒ ｈｉｓｔｏｒｉｃａｌ ＸＭＩ ［１０］ＲＵＳＳＥＬＬ Ｇ．ＴｙｐＥｘ：ａ ｔｙｐｅ ｂａｓｅｄ ａｐｐｒｏａｃｈ ｔｏ ＸＭＬ ｓｔｅａｍ ｑｕｅｒｒｙｉｎｇ ［Ｃ］／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ ｔｈｅ Ｗｅｂ ａｎｄ Ｄａｔａｂａｓｅｓ （ＷｅｂＤＢ）．ＵＫ：ＡＣＭ ＳＩＧＭＯＤ，２００３：５５ ６０． ｄａｔａ［Ｃ］／／Ｐｒｏｅ ｏｆ ＳＩＧＭＯＤ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００４：２３９．２５０． ［６］ＧＵＡＮ Ｊｉ—ｈｏｎｇ．ＧＱＬ：ｅｘｔｅｎｄｉｎｇ ＸＱｕｅｒｙ ｔｏ ｑｕｅｒｙ ＧＭＬ ｄｏｃｕｍｅｎｔｓ ［Ｊ］．Ｇｅｏｓｐａｔｉａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，２００６，９（２）：ｌｌ８．１２６． ［１１］於荔，鲍培明，张书亮．ＧＭＬ空间数据的对象化存储研究［Ｊ］．南 京师范大学学报：工程技术版，２００６：６（１）：６７．７１． ［７］杨颖，韩忠明，杨磊．数据流的核心技术与应用发展研究综述 ［Ｊ］．计算机应用研究，２００５，２２（１１）：４－７． ［１２］兰小机，闾国年，刘德儿，等．基于ＸＱｕｅｒｙ的ＧＭＬ查询语言研究 ［Ｊ］．测绘科学，２００５，３０（６）：９９ １０２．
