基于云计算思想和HXFA机的主动Web服务研究

1、云计算专栏基于云计算思想和机的主动服务研究木王桐。赵春晖。陆军（哈尔滨工程大学信息与通信工程学院哈尔滨；黑龙江大学计算机学院哈尔滨）圜云计算是一个更先进的计算概念，是网格计算和分布式计算的延伸。基于的主动服务具联网海量的异构半，结构化数据，过滤引擎执行效率通常是该系统的瓶颈所在。鉴于此，利用森林原型系统中，并阐述该系统的组成及其关键技术。有异构性、海量性、按需服务等特点，因此可看作是具有网络计算能力的云计算的应用之一。面对互文法提出机算法以提高执行匹配能力结合云计算思想，将该算法应用于提出的主动服务；关键诩海量数据；生动服务；云计算；模式量性、数据驱动、按需服务等特点。因此可看作是具有网络引言

2、云计算【是分布式处理、并行处理、网格计算、网络存计算能力的云计算的重要应用之一。这类服务通常以、语句作为订阅模型。用自动机对查询进行描述，并将其作为过滤引擎同其他事件代理结点路由而来的发布流进行匹配，返回相关结果。然而，在处理大规模异构数据时，过滤引擎的处理效率将成为系统的瓶颈。很多研究表明闱线性有限自动机处理匹配问题时，需要将路径表达式中的祖先符，、通配符木等不确定因素改写。以增强运行时的效率。而从到的转换过程经常导致搜索空间的组合爆炸。另外，一些研究引入了树自动机来处理树状结构数据。树自动机是传统字符自动机的扩展，在很多领域发挥了巨大优势。然而，现有的树自动机（如二叉树自动机或储等的进一步

3、发展和商业实现。由于数据具有海量性和异构性，如何对这些海量半非结构数据进行分析和自动处理也就成为云计算中亟待解决的重要课题。主动服务是在服务框架模型基础上按需定制的查询模式，在这种模型产生前，人们采用传统搜索引擎（如）进行检索，返回数以万计的文档，仍需在返回结果中人工筛选，导致“数据丰富而信息贫乏（）”的现象。近年来，由于文档自身带有结构和语义信息等优势越来越多的信息通过格式进行交互和发布一互联网出现大量基于的主动服务应用【：发布，订阅系统、实时股票系统、个性化网购系统等。与传统的分布式计算环境相比，主动服务具有异构性、海）存在一些不足，如兄弟结点有序性、无法表述无根结点的森林（）问题。，而森

4、林文法的出现懈决了这些中国博士后科学基金资助项目（），中央高校基本科研业务费专项资金资助项目）根据以上分析，本文采用扩展森林文法来更自然地描述路径表达式，然后通过机进行匹配。在此匿丐云计算专栏基础上进一步将算法用到我们开发的主动服务仿真平台上，获得了良好的效果。机过滤算法机生成过程森林（）概念是由“最早提出的，其原意为一系列树，或称森林。在参考文献】中第一次将概念引用到领域中。本文将扩展森林文法，并通过该森林文法描述及模式。建立森林机并通过模式约束自动机来优化其分析处理能力。定义（非终结符集合上的正则式和正则集）给定非终结符集合则之上的正则式和它所表示的正则集可递归定义如下：（）占是正则式，其

5、表示的正则集是忙；（）任意是正则式，它表示的正则集是；（）如果、是正则式，分别表示的正则集是三似）和（），则、也都是正则式，分别表示的正则集是（），（）（），（）。仅由有限次使用以上条规则所定义的表达式，称为上的正则式且这些正则式表示的字符串集合才是上的正则集。同样地下文使用的状态集合上的正则式可类似定义。定义（正则森林文法）正则森林文法定义为一个五元组（三，），其中：三表示符号的有限集合；表示数据类型的有限集合：表示非终结符的有限集合；由非终结符组成，且；表示产生式的有限集合每条产生式满足以下两种形式之一：（）咄，其中，算；（）口，其中，三，是由非终结符构成的正则式。舟畎肿，可以得到语言（）

6、：，声，。例：给定正则森林文法（，仁，。？）其中给出的正则森林文法与是可以转换的，即通过给定可以构造一个相应的森林文法。定义（扩展正则森林文法）一个扩展正则森林文法定义为一个六元组：（三，研，其中：三表示符号的有限集合；表示数据类型的有限集合；表示树变量的有限集合；表示森林变量的有限集合：由非终结符组成，且；表示产生式的有限集合，每条产生式满足以下几种形式之一。），其中，口。，本规则适用于产生单结点树。，其中，三，巩，本规则适用于给森林加一个结点。口厂切。，其中，），），本规则适用于森林中生成子森林或子树。定义扩展了定义。将树的概念扩展到森林，通过这条产生式规则将二者有机地统一起来。根据正则森

7、林文法本文给出构造森林自动机（。）的过程如下。定义（森林自动机）定义森林自动机为六元组三，仃，其中：三表示符号的有限集合；表示数据类型的有限集合；表示状态集合；表示状态转移函数：，叮，舢，印表示，三上的正则集；丌为从到的映射，仃：；为终止状态集。是上的正则集。定理给定正则森林文法（三，），产生的语言为（），则存在一个接受的语言三（）。证明从略。下文将根据路径表达式来构造，本文称之为（）机。用来对流进行过滤。基于机流过滤算法本节将详细描述如何用机作为过滤器完成流上的路径表达式查询。教授在参考文献【】证明了用传统的转换方法将带有，的查询转化为是一个问题并提出了一个的转换方法即当文档流入时才在内存中

8、组织查询；还提出了如何在图模式中优化路径查询的方法，利用传统自动机表达不包含“口”的路径查询和图模式，通过路径自动机和图模式自动机的约束减少路径查询中的不确定因素，提高路径查询效率。但是，这种方法的处理能力有限，不支持“口竹，也不支持模式。参考文献用模式对查询语句进行约束但是该法主要应用于中的数据。参考文献】利用）完成了表达式的重写简化转换，该方法基于产生了若干规则利用规则等价重写，并且证明了算法在特定和之上是完备的。参考文献】和【】给出了支持不同特性的在下包含判定的复杂性。利用树自动机来表达和获取并解释树自动机上基本运算的结果。本文主要目的是利用约束重写的，而不是讨论的包含问题本文采用基于森

9、林文法的机来更好地进行描述，给出的算法更具通用性。给定路径表达式形，给出对应的机作为过滤引擎算法。输入：路径表达式形输出：正则森林文法（三，）初始化，忍，船行；非终结符遇到三将产生字母表上的正则式，即三；（非空）如一是叶结点坳（）吩三，在产生式中加入规则：巩；（一），靠硒（订码三，在产生式中加人规则：以血；如一与其父结点用“”连接，在产生式中加入规则：三，；：聊射（如，一）；自下而上分析在中，出一指路径表达式埘中的结点，用。三表示产生式集合，口砚。这样，通过自下而上扫描）【路径表达式，得到相应的正则森林文法。随后，根据上文给出的得到机。限于篇幅，算法可行性及完备性证明请参见参考文献。海量数据发

10、布订阅服务云计算应用实例提出的基于森林机的过滤算法在我们开发的主动处理海量数据的发布订阅系统（）原型系统】中起到关键作用得到良好运行效果。笔者开发的主动服务系统具有云计算应用的重要特征：可扩展性和高可用性。可扩展性是指代理结点能够无缝地扩展到大规模的集群之上。甚至包含数千个结点同时处理。高可用性是指该发布订阅系统能够容忍代理结点的错误，甚至有很大一部分结点发生失效也不会影响程序的正确运行。下面简要描述一下某事件代理结点的体系结电信科学年第期构，以说明该算法是如何在该云计算应用起到关键作用的。我们将互联网中每个主机可看作一个事件代理结点。整个云计算过程在互联网中计算机结点进行。每个事件代理结点都

11、可以与其他结点协作完成订阅、发布及事件转发等功能，即将计算量分布到互联网的结点上。每个事件代理结点主要由三部分构成：语义化异构事件处理模块、匹配引擎以及事件转发模块如图所示。（）匹配引擎匹配引擎是系统在线处理部分，包括事件解析器、订阅器、逻辑优化单元及匹配引擎等。其中，事件解析器采用软件包中的，将发布事件处理为解析事件流；订阅器主要负责本地的用户订阅，在用户列表中记录每位用户的名称、订阅条件、等信息：逻辑优化单元通过订阅模型与模式信息对用户订阅条件进行确定性查询重写。匹配引擎由多个逻辑优化单元组合而成，可支持多用户订阅。系统中采用的匹配引擎就是基于森林模式自动机约束的机及其优化算法。（）异构事

12、件处理模块异构事件处理模块是其他数据驱动系统所不具备的，为模型特色之一，包括数据特征生成器、分类器、数据聚合等主要部分。该模块采用基于和支持度相结合的相似性测度方法，然后在空间对文档进行二阶段聚类分析：在自动形成若干类簇后，提取其模式用于订阅模型的建立、自动维护和匹配引擎的生成。该模块详细描述请参阅参考文献】，此不赘述。（）事件转发事件转发模块包括事件加工和事件转发两部分。前者负责对中间形式的查询结果进行处理；后者是将匹配的事件转发给在该事件代理进行订阅个性化信息的本地用户。设置好敏感信息过滤以后，一经发现，可立即采用报警，或者通过短消息、发送到用户的手机，并做出相关响应；同时。将该发布事件继

13、续路由至下一事件代理，以达到连锁应急的效果。如何使事件沿着一种恰当的路径，低成本、高效率地到达各相关订阅者，这是路由协议所要解决的问题。原型系统中。路由算法采用协议和内容匹配优先相结合的精确路由算法。首先，每个事件代理分配有一个位比特的惟一标识（），并按照协议自组织成一个在上呈环状结构的网络。然后，每个事件代理结点构建和维护一棵以自己为根的事件分发树。当某事件代理收到客户端发布的事件消息时，将沿三圣雾薹云计算专栏异构事件事件代理图体系中的事件代理着分发树的结点从上向下转发事件消息。当某事件代理收到客户端发送的订阅消息时。将沿着分发树的逆向转发订阅消息。其次，对于分发树的每条路径设置一个事件匹配引擎，它由所有从该路径逆向转发来的订阅条件汇聚而成，只有事件内容与匹配引擎条件匹配的事件消息才能到达其后续结点，从而避免不必要的事件转发。图是云计算拓扑的示意图，每个事件代理节点都可以进行发布或订阅操作。结束语本文采用扩展森林文法来更自然地描述路径表达式，然后，通过机进行主动服务匹配，最后，将森林机算法应用于自主研发的云计算系统实例主动服务仿真原型上，以处理互联网上海