查询处理模型的结构化P2P数据流系统
查询处理模型的结构化P2P数据流系统
摘要：分析了基于结构化覆盖网的分布式查询处理模型，支持大量数据流的分布式存储，连续查询间、查询内的并行处理操作，能够在很大程度上消除资源约束问题（主要是内存），提高了查询性能、服务质量，并且该查询模型具有很好的扩展性。
关键词：分布式数据流管理系统； 结构化覆盖网； 分布式散列表； 滑动窗口
近年来，数据流查询处理是数据库研究领域的一个热点方向。数据流的特征可概括为无限性、瞬时性、流速不定性、语义不定性（数据模式随时可能改变）等。针对数据流的以上特征，不考虑将数据流存储在传统的关系数据库中，数据流上的查询是近似查询、连续查询(continuous query)。 目前，数据流管理系统中所采用的近似查询的方法主要有以下几种：随机抽样(random sampling)、数据写生（sketching）、直方图(histograms)、小波变换(wavelets)、窗口（windows）等。如何保证查询的服务质量成为上述各种近似查询方法必须考虑的问题。数据流上的查询处理给人们提出了一个很大的难题——对处理器、内存等系统资源非常苛刻的需求。到目前已经出现了许多数据流的原型系统：单节点（单CPU）上的数据流管理系统，如Stanford 大学的Stream[1] 系统、布朗大学的Aurora[2,3] 系统等；有分布式数据流处理系统，如MIT的Medusa[4,5] 项目，Brandeis、Brown、MIT 的合作项目Borealis[6,7]等。这些项目在数据流处理的查询语言、近似查询算法、保证服务质量的策略，以及系统的负载均衡等方面做了大量的工作，但同时也揭示出在分布式数据流处理系统中更多值得研究的问题。本文将对基于structured overlay network的分布式数据流系统的近似、自适应查询处理进行研究，给出查询处理模型。
1集中式数据流查询处理及分布式散列表、Chord路由协议的相关说明
1．1数据流查询处理相关的概念定义以及假设说明
集中式数据流查询处理的体系结构由两部分构成，即查询计划生成子系统（FRONT－end）以及查询执行子系统(BACK)。其中两部分与关系数据库系统相比均有较大的区别。查询执行子系统如图1所示。
通过这种散列，将系统当前的所有查询映射到节点空间，然后由该节点上的查询处理器完成到达的查询。
b)查询内并行处理方式。在系统的范围内，由操作符、输入均输出记录队列、维持操作符状态的大纲信息构成网状结构。
c)命名发现机制。参与查询处理的节点有全局惟一命名participant（如IP地址等）。当在一个节点上面定义一个新的流模式、数据流、操作符，这些实体均隶属于其命名空间。该实体可以采用下面的命名方式：（participant，entity－name） 。为了了解系统中数据流模式的定义、系统中的数据流、数据流的到达（存放）位置、系统中哪一部分查询执行，就要考虑在catalog中存放必要的数据。其中catalog信息是通过在DHT下分布式存储的，前面已经分析了catalog信息的存储问题。
系统中对每一个数据流、每一个查询、查询中的算子、算子大纲、节点间输出队列均有惟一的命名。查询处理器位于DHT之上。同查询相关的数据粒度限定为数据流、输入数据源（记录集）、节点间传输数据队列、算子大纲，而不是针对单个记录而言。对于这些粒度的数据可以通过在DHT中通过put（namespace，object）、get（namespace）、multicast（namespace）消息得到。
对于操作符（算子）在节点间迁移的情况，可以提供远程算子定义接口。当节点A上查询执行的下一步join操作要求节点B的查询执行器完成时，节点B接收到远程调用请求，初始化join算子，将节点A上发出调用请求算子的状态信息（大纲，synopsis）作为参数传递给B,然后就可以在节点B上进行join算子运算。查询内并行就是有若干这样的节点间的算子迁移，使一个查询计划得以在多节点的算子之间并行执行。
对于基于滑动窗口的数据流处理的join操作，如果有两个数据流，查询处理基于时间的窗口，进行join操作的两个数据流时间范围较长，那么要求在一个节点上维护操作符的状态信息将会变得非常困难，join算子状态信息存储要求的内存空间可能非常大，则会进行操作符分割操作。在该节点的近邻节点上同时进行join操作，最终将各个节点上的状态信息进行合并操作即可。
算子迁移、算子合并、算子分割等操作在基于DHT的系统上实现具有良好的扩展性。DHT层为数据流处理系统在荷载大的情况下进行负载脱落、查询计划间并行、查询计划内并行提供了可以随意扩展的基础平台。
3结束语
本文给出了基于structured overlay network 的分布式数据流查询处理模型，考虑了对于到达系统的大量数据流的分片存放策略；同时在查询处理中对查询内的并行、查询间的并行、算子在分布式节点的迁移等提供了很好的支持。对系统catalog目录信息的分布式存放维护，从而消除了单节点查询处理引擎在资源（CPU、内存）上的约束。本文没有考虑分布式查询模型在网络带宽资源方面的问题，这将是以后要完善的地方。基于结构化覆盖网的分布式数据流查询模型提高了系统性能、查询服务质量，并且基于Chord实现，具有很好的扩展性。
参考文献：
［1］BRIAN B, SHIVNATH B, JENNIFER W. Models and issues in data stream systems[C]//Proc of the 21st ACM Symposium on Principles of Database Systems,2002.
［2］BALAKRISHNAN H, BALAZINSKA M, CARNEY D, et al. Retrospective on Aurora[J]. VLDB Journal, 2004,13(4):370-383.
［3］ABADI D, CARNEY D, STONEBRAKER M, et al. Aurora: a new model and architecture for data stream management[J]. VLDB Journal,2003,12（2）:120-139.
［4］ZDONIK S, STONEBRAKER M, CHERNIACK M,et al. The Aurora and Medusa Projects[J].IEEE Data Engineering Bulletin, 2003,26(1):3-10.
［5］CHERNIACK M, BALAKRISHNAN H, BALAZINSKA M, et al. Scalable distributed stream processing[C]//Proc of the 1st Biennial Conference on Innovative Data Systems Research. Asilomar, California:[s.n.],2003.
［6］ABADI D J, AHMAD Y, BALAZINSKA M, et al. The design of the Borealis stream processing engine[C]//Proc of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR’05). Asilomar:[s.n.],2005.
［7］TATBUL N, ZDONIK S.Dealing with overload in distributed stream processing systems[C]//Proc of IEEE International Workshop on Networking Meets Databases (NetDB’06). Atlanta:[s.n.],2006.
［8］Distributed hash tables links[EB/OL].
［9］DABEK F, STOICA I, BALAKRISHNAN H, et al. Building peer－to－peer systems with Chord, a distributed lookup service[C]//Proc of the 8th Workshop on Hot Topics in Operating Systems(HotOS－VIII).2001.
［10］STOICAL I, MORRIS R, BALAKRISHNAN H, et al. Chord:a sca－lable peer－to－peer lookup service for internet applications[C]//Proc ofACM SIGCOMM. New York: ACM Press, 2001:149-160. 712