发布订阅系统中基于属性流行度的事件匹配方法

摘要

本发明公开了一种发布订阅系统中基于属性流行度的事件匹配方法，目的是解决基于结构化对等网络的发布订阅系统的事件匹配问题。技术方案是先根据应用的历史数据获得发布订阅系统中各个属性的流行度，并把流行度超过k的属性赋给属性集合MPAS；接着根据MPAS确定订阅存储所需要的汇聚节点，进行订阅注册，最后根据MPAS确定事件发布所需要的汇聚节点，进行事件发布。本发明从事件和订阅两个角度考虑匹配问题，充分利用系统中属性流行度的信息，是一种通用性强，带宽开销小、负载均衡的事件匹配方法。

说明书

 

技术领域

本发明涉及结构化对等网络中基于内容发布订阅系统的事件匹配方法。

 

背景技术

发布订阅系统用于分布式系统中高效按需查找资源。 一个典型的发布订阅系统可以描述为：订阅者（信息消费者）以订阅的形式表达自己对特定内容（对象、资源等）的兴趣，并把订阅注册到事件系统中；发布者（信息产生者）把信息以事件的形式发布到系统；发布订阅系统负责把事件发送到所有对该事件感兴趣的订阅者。订阅者和发布者彼此不相知。事实上，发布者和订阅者有三个方面的解耦：（1）时间解耦，即发布者和订阅者交互不需要同时在线；（2）空间解耦，即发布者和订阅者不需要知道对方的地址，比如IP地址等；（3）同步解耦，即发布者和订阅者的交互不需要打断各自的进程。发布订阅系统的这些特性非常适合因特网规模的应用。

发布订阅系统可以分为两类：基于主题的和基于内容的。其中基于主题的通过一个主题词把交互者归为一个个小组，它实现简单，但是表达能力较弱。而基于内容的则可以在订阅中对多个属性施加约束来表达复杂的兴趣，因而表达能力更强。 

基于内容的发布订阅系统的事件模型包括一系列的属性。典型的事件模型可以描述为S＝{A₁, A₂, A₃, … A_N}，其中A_i为属性。订阅包含模型中的某些属性和对这些属性的取值约束；而事件则包含模型中的某些属性和这些属性的取值。各个属性有不同的流行度:某些属性被所有或者大部分用户关心，叫做流行属性；而另一些属性则只被少部分用户关心，叫做不流行属性。大部分订阅和事件都包含流行度高的属性，而只有少部分的订阅和事件包含流行度低的属性。一个事件匹配某个订阅的含义是：对该订阅的所有属性，事件在该属性上的取值满足订阅对该属性的约束。

通过分布式哈希表建立的结构化对等网络DHTs（Distributed Hash Tables）具有可扩展性好、容错和自组织等特性，非常适合在其上构建发布订阅系统。基于DHTs的发布订阅系统中，发布者和订阅者都是网络中的节点，而网络中的任何节点都可以是发布者或者订阅者。在DHTs中，每个节点都有一个逻辑名字，所有节点的名字都属于同一个名字空间。每一个数据对象都哈希到该名字空间而得到一个名字。每个节点同时负责该名字空间的一小段, 即名字处于该段空间中的数据对象将路由到该节点。基于DHTs的发布订阅系统中，订阅和事件都需要路由到系统中的某些节点，这些节点叫做汇聚节点。因此，对于订阅和事件，需要通过哈希它们的某些元素而路由到负责这些哈希值的汇聚节点。

汇聚节点有两种负载：（1）订阅存储负载表示汇聚节点存储的订阅个数；(2) 事件处理负载表示汇聚节点处理的事件个数。系统带宽开销跟所有汇聚节点的负载息息相关。设计高效的发布订阅系统需要综合考虑这两种负载。

发布订阅系统的正确性要求设计合理的事件匹配方法使得所有匹配的事件和订阅在系统中相遇，即：如果事件e匹配订阅s，e和s必须路由到同一个汇聚节点。为了达到这个要求，需要选择适当的哈希元素来哈希订阅和事件。现有的一种事件匹配方法基于订阅允许的内容来选择哈希元素，它们把订阅的约束视为一个数值范围约束，这类事件匹配方法通用性不强。另一种事件匹配方法基于属性名来选择哈希元素，因而可以处理结构类型复杂的订阅，比如发布订阅系统Ferry。 Ferry的缺点是汇聚节点数目少，导致一些汇聚节点过载。为了克服Ferry汇聚节点少的弱点，研究者提出了Eferry，通过引进更多的汇聚节点来改进Ferry的性能。然而，Eferry仅仅降低了汇聚节点的订阅存储负载，并没有降低汇聚节点的事件处理负载；另外，它大大增加了事件发布所需的带宽开销。

Ferry和Eferry都从事件的角度来考虑匹配问题：它们都存储某个订阅到系统中某一个汇聚节点，然后采用一种事件发布方法来使得所有跟该订阅匹配的事件都路由到该汇聚节点。基于这种观察，它们可称为基于事件的方法。理论分析表明，基于事件的方法无法避免一些汇聚节点事件处理过载。

以上分析表明，在发布订阅系统中，由于订阅的复杂性和多样性，基于订阅内容的事件匹配方法通用性不强；而目前基于属性名的事件匹配方法都从事件角度考虑匹配问题，不可避免造成一些汇聚节点过载。

发明内容

本发明要解决的技术问题在于：针对基于结构化对等网络的发布订阅系统的事件匹配问题，从事件和订阅两个角度考虑匹配问题，利用系统中属性流行度的信息，提供一种通用性强，带宽开销小，负载均衡的事件匹配方法。 

针对上述技术问题，本发明的技术方案是：根据应用的历史数据，获得发布订阅系统中各个属性的流行度，并找出流行度高的几个属性赋给属性集合MPAS（Most Popular Attribute Set）；然后根据MPAS确定订阅存储和事件发布所需要的汇聚节点。

该技术方案具体可以描述为：

第一步，根据应用的历史数据，获得发布订阅系统中各个属性的流行度，并把流行度超过k的属性赋给属性集合MPAS。k一般为50％。k值越大，订阅注册的开销就越小，而事件发布的开销就越大。

第二步，订阅者根据MPAS确定订阅存储所需要的汇聚节点，进行订阅注册。给定一个订阅s和订阅的属性集合                                               ，定义订阅的发送集合如下:

 = {T|T & T }}MPAS}

并定义订阅消息sub，它是一个二元组，由订阅s和s的订阅者节点名字sID组成， 表示为(s,sID)。

步骤2.1 订阅注册。如果订阅的发送集合中只有一个元素T，执行步骤2.1.1，如果中元素个数超过一个，执行步骤2.1.2。

步骤2.1.1先定义名字key = Hash(T)，再调用DHTs的查询函数lookup(key)，找到负责key的汇聚节点，然后把订阅消息sub直接发送给负责key的汇聚节点；转步骤2.2。

步骤2.1.2先定义名字集合KeySet，对中的每一个元素T计算哈希值，并把哈希值加入到KeySet中，即KeySet = {Hash(T)|T∈}，然后订阅者采用组播方法将sub发送给负责KeySet中每个名字的汇聚节点。

组播方法运行于组播发起者和组播路径上的每个节点，输入为一个数据内容（在事件服务系统中，数据内容可以是订阅或者事件）和一个名字集合，其步骤是：

步骤2.1.2.1 初始化长度为m+1的名字列表数组mult_vec[ ]，置mult_vec[ ]中每个元素为空列表，m为节点邻居节点表的大小； 

步骤2.1.2.2 从KeySet中取出一个名字key； 

步骤2.1.2.3 如果节点在DHTs上的前缀节点的名字predecessor.ID<key 且 key<=节点的名字NodeID，把key放入mult_vec[0]；

步骤2.1.2.4 如果 NodeID<key 并且key<=节点后继节点的名字successor.ID，把key放入mult_vec[1]；

步骤2.1.2.5 置变量i = 1；

步骤2.1.2.6 如果节点第i个邻居的名字fin_table[i].ID<key 并且 key <= 节点第i+1个邻居的名字fin_table[i+1].ID，把key 放入mult_vec[i]，转步骤2.1.2.9，否则，i加1，转步骤2.1.2.7；

步骤2.1.2.7如果i >= m，转步骤2.1.2.8，否则，转步骤2.1.2.6；

步骤2.1.2.8 如果节点第m个邻居的名字fin_table[m].ID<key，把key放入mult_vec[m]；

步骤2.1.2.9 如果KeySet为空，转步骤2.1.2.10，否则转步骤2.1.2.2；

步骤2.1.2.10 如果mult_vec[0]不为空，把数据内容交给本地处理；

步骤2.1.2.11 置变量 j = 1；

步骤2.1.2.12如果mult_vec[j]不为空，则把数据内容和mult_vec[j]发送给节点第j个邻居fin_table[j]。

步骤2.1.2.13 j加1，如果j>m 则结束，否则转步骤2.1.2.12。

步骤2.2 每一个收到sub的汇聚节点存储sub。

第三步，发布者根据MPAS确定事件发布所需要的汇聚节点，进行事件发布。给定一个事件e和事件的属性集合,定义事件的发送集合:

 = {T|T  & T}}MPAS}

步骤3.1 事件发布。如果事件的发送集合中只含有一个元素T，执行步骤3.1.1，若中元素超过一个，执行3.1.2；

步骤3.1.1调用底层DHTs的函数lookup(Hash(T)),找到负责Hash(T)的汇聚节点，然后把事件e直接发送给负责Hash(T)的汇聚节点，转步骤3.2。

步骤3.1.2 如果中元素超过一个，则定义名字集合KeySet = {Hash(T)|T∈}，然后采用步骤2.1.2中的组播方法将事件e发送给负责KeySet中每个名字的汇聚节点。

步骤3.2 每一个收到事件e的汇聚节点将把e和存储于本地的订阅消息中的订阅进行匹配操作，产生匹配事件e的订阅者列表SubscriberList(对于每一个存储的订阅消息sub = (s，sID),如果s匹配e,则把sID加入到SubscriberList)。

步骤3.3 每一个收到事件e的汇聚节点把事件e转发给订阅者，如果SubscriberList只含有一个元素sID，执行步骤3.3.1，如果SubscriberList含有多个元素，执行步骤3.3.2。

步骤3.3.1调用DHTs的路由方法route(e, sID)，把事件e转发给订阅者sID，结束。

步骤3.3.2采用步骤2.1.2中的组播方法把事件e转发给SubscriberList中的每一个订阅者，结束。

 

采用本发明可以达到以下技术效果：

（1）本发明从订阅和事件两个方面考虑事件匹配问题：即分别给订阅和事件定义集合和集合，根据这两个集合确定订阅注册和事件发布需要的汇聚节点。由此为事件匹配的最优解提供了可能性。

（2）本发明利用了发布订阅系统中属性流行度的信息，从而为事件匹配最优解找到了有效可行的方法。

（3）与传统基于事件的方法相比，本发明以增加少量订阅存储开销为代价，极大降低了汇聚节点的事件处理开销，尤其是对于在基于事件方法中事件处理开销最大的那些汇聚节点。

 

附图说明

图1为本发明总体流程图。

图2为步骤2.1.1示例。

图3为步骤3.1.2示例。

图4为步骤3.3.1示例。

 

具体实施方式

下面结合一个具体的例子和附图详细介绍本发明的过程。

该例子是一个宠物搜索的应用。其中的一个订阅是s = { = “cat”, ≠ ‘Japan’}，表明该用户需要的宠物是一只猫，且不要产于日本；一个事件是e = { = “cat”,=‘black’,  = ‘China’}，表明某用户有一条来自中国的猫出售，毛色是黑色。在这个例子中，事件e匹配订阅s，因而e和s必须路由到系统中同一个汇聚节点。

第一步 根据应用历史数据，获得系统的属性流行度，并把流行度高的属性赋给MPAS。在本例中，为了简单起见，令MPAS = {}。

第二步 订阅注册。节点X有一个订阅s = { = “cat”, ≠ ‘Japan’}要注册到系统， = {, }}，根据MPAS和,确定={{,}}； 获得sub = (s, X)。然后对中的每一个元素计算哈希值，并把sub路由到负责这些哈希值的汇聚节点。在本例中，由于只含有一个元素{,}，所以采用步骤2.1.1。

步骤2.1.1如附图2所示，订阅者X调用DHTs的函数lookup()得到N1 = lookup(Hash({,}))，即N1是负责Hash({,})的节点， X把订阅sub发送给节点N1，

步骤2.2 节点N1存储sub。

第三步 事件发布。节点Y有一事件e = { = “cat”,=‘black’,  = ‘China’}要发布， = {, , }，根据MPAS和确定 ＝ {{},{,},{,},{,,}}。然后对中的每个元素计算哈希值，把事件e发布到负责这些哈希值的汇聚节点。在本例中，由于含有多个元素，所以采用步骤3.1.2。

步骤3.1.2 定义名字集合KeySet = {Hash(T)|T∈}，然后采用组播方法，输入为e和KeySet。在附图3中，节点N1, N2, N3, N4是负责中元素哈希值的节点，发布者Y采用组播方法，将事件e发布到这四个汇聚节点（图3中略去了组播路径上的节点）。

步骤3.2 汇聚节点N1, N2, N3, N4接收到事件e后，将e同存储于本地的订阅消息中的订阅做匹配操作。在本例中，只有节点N1存储了订阅消息sub，sub包含订阅s。节点N1将e与s进行匹配操作，发现事件e匹配于订阅s，所以N1产生匹配事件e的订阅者列表SubscriberList={X}。

步骤3.3汇聚节点N1把事件转发给匹配的订阅者，因为SubscriberList只含有一个元素X，所以采用步骤3.3.1。

步骤3.3.1 汇聚节点N1调用底层DHTs的路由函数route(e,X),把事件e发送给订阅者X，如附图4中虚线箭头所示。