云平台发布用户系统事件匹配流行启发式分析

Subasish Mohapatra¹， Bhagyashree Mohanta²， Subhadarshini Mohanty^3.

印度布巴内斯瓦尔，CET, CSA系讲师
印度布巴内斯瓦尔国际热核聚变实验中心CSE系研究学者2
印度布巴内斯瓦尔CET CSE系讲师3

摘要

发布者/订阅者系统因提供定制化的信息传递而受到越来越多的关注。在大规模事件匹配发布/订阅系统中，基于上下文的事件匹配是一个令人烦恼的问题。分布式环境中的主要约束条件，如位置、行为，激励为可扩展通信系统设计有效的算法。对其困难的分析和对其解决办法的评估仍然是一个问题。本文对现有的发布者/订阅者系统事件匹配算法进行了综述。

关键字

事件匹配，发布者/订阅者系统，云计算，基于内容的模型，快速匹配算法。

介绍

发布/订阅系统通常由一个覆盖的代理网络组成。事件来自发布者，由代理传递给感兴趣的订阅者。传统的发布/订阅是基于主题的，订阅者订阅一组重新定义的主题，如“苹果新闻”或“美国偶像”[1]。另一方面，基于内容的发布/订阅允许订阅者将兴趣表示为针对事件[2][3]中的属性值的布尔谓词。例如，一个订阅者可以订阅eBay古董拍卖，卖家评分高于90%，起价在100美元到200美元之间。只有匹配谓词的事件才会被传递给订阅者[4]。数据库和网络社区都对基于内容的发布/订阅感兴趣，因为它必须解决事件空间中的订阅匹配和网络空间中的事件传播的双重挑战。每个订阅者都需要分配一个代理，该代理负责将匹配事件转发给该订阅者。直观地说，我们希望将具有相似兴趣的订阅者分配给相同的代理，以便交付给代理的事件可以为许多订阅者服务。如果分配给代理的所有订阅者都有类似的兴趣，那么所有可能事件中只有一个子集需要通过代理。 At the same time we may not want to assign a subscriber to a broker located far away in the network because by doing so increases delivery latency and communication cost. Finally, we should not assign too many subscribers to one broker, which creates a performance bottleneck and delays event delivery. Balancing these considerations—similarity of interests in the event space, proximity of locations in the network space, and balance of load across brokers—is a difficult optimization problem [4].In the matching problem, we are given an events schema and a finite set of subscriptions (sub). Subsequently, we are given an event (e), and the goal is to determine all those subscriptions in sub that match e. We allow pre-processing of the set Sub before we are given e. A solution to the matching problem has two phases: pre processes and match pre processed data with the event. Initially in the pre-processing phase, the algorithm pre-processes the set of subscriptions into a data structure that allows fast matching [5]. Pre-processing makes sense in most pub/sub environments, where subscriptions tend to change infrequently enough that they can be considered approximately static, but where events are published at a fast rate. The first phase takes the set of subscriptions and outputs an internal representation of the subscriptions. The second phase match takes this internal representation an event and outputs of those subscriptions that match the event.

启发式的描述

对于发布/订阅系统，下面的小节描述了一些事件匹配算法的分析。

A.朴素算法

这是一个解决匹配问题的简单算法，包括针对每个传入事件[25]逐一测试所有订阅。通常，匹配算法可用于具有大量订阅(数十万甚至更多)的环境中。在这样的环境中，如果处理事件的响应时间是一个重要因素，或者处理事件的速率很高，那么朴素算法就不是一个令人满意的解决方案。该算法的主要问题是在谓词的计算中存在高度冗余。事实上，同一个谓词可以被求值的次数与它在订阅集中出现的次数相同。它逐个计算订阅，并对每个订阅计算其谓词，直到其中一个为假或全部求值为止。

上述算法的局限性在于匹配过程的评估时间太长，需要逐个评估所有订阅。因此，为了减少匹配时间，我们使用树匹配算法，它比Naive算法计算量更少。这个朴素算法与订阅数[5][26]线性运行。在实践中，pub/sub系统可以部署在具有数万个发布者/订阅者的环境中，并且一般来说，pub/sub系统的目标是为大规模、广泛分布的应用程序提供支持。因此，匹配问题的线性时间解是不够的。

B.树匹配算法

基于树的匹配算法优于基于naive的匹配算法。基于树的算法[27]将订阅组织到根搜索树中。树的第i层的每个节点代表一个属性ipp，并且最多有3个继承者对应于值{0,1，*}ipp。每个树叶子包含所有订阅的列表，这些订阅的谓词值由从根到叶子的路径指定。给定一个事件k e{0,1}，搜索树将从根向下遍历。在每个节点上，都会测试事件属性的值，并遵循满足要求的分支。所有匹配的订阅都在算法命中的树的叶子处获得。

这里，在预处理阶段，我们的算法创建了一棵匹配树[5]。在匹配树中，每个节点都是对某些属性的测试，边是这些测试的结果。树的每个较低级别都是在较高级别执行的测试的细化，在树的叶子部分我们有订阅。有了这样的树，我们可以通过在每个节点上从根开始遍历树来找到与事件匹配的订阅，我们执行节点规定的测试，并跟踪所有与结果一致的边(可能有多条边)。然后重复这些步骤，直到我们得到叶子。最终访问的叶与与事件匹配的订阅相对应。

C.快速匹配算法

快速匹配是基于树的匹配方法。RAPID Match通过根据事件的“相关”属性对应的谓词对订阅进行分区，从而对订阅进行预处理，因此对于给定的事件，它可以快速消除大量不匹配的订阅，并专注于可能匹配的订阅的一小部分。

为了验证模型的有效性，本文以一份在线报纸为例进行了分析。这家报纸定期发表文章，并希望在他们感兴趣的文章发表时通知订户。用户可以根据自己感兴趣的话题来指定自己的喜好，比如时事、体育、艺术等。他们可能会具体说明他们对每个话题是感兴趣、不感兴趣还是中立。例如，指定订阅者对体育感兴趣，对政治不感兴趣，对其他不感兴趣的订阅可能有这样的订阅(sports = *)， (politics = 1)， (arts = 0)和……这里，1表示感兴趣，0表示不感兴趣，*表示“不在乎”。一个事件，比如一篇关于政治和艺术但对任何其他主题都中立的文章，将被指定为(sports = *)， (politics = 1)和(arts = 1)和其他约束。形式上，订阅由k个谓词(1 1 p v)和(1 2 p v)和…(k k p v)，其中j p被称为属性，i v取{0,1，*}中的值。事件以类似的方式表示，只是i v取{0,1}中的值。如果一个事件的属性值满足订阅中的所有谓词，即订阅中的0和1分别与事件中的0和1匹配，并且*也匹配。 For conciseness, the property names are omitted and only the values are specified.

在这个算法中使用的术语是，

e =发布事件。

S=一组订阅。

ipp =事件的属性。

kp =订阅中的谓词。

k = No。的谓词。

j P =No。发布事件的分区。

j T =包含T中有0或*的订阅

t S =包含最多t1的订阅。

S=任何与事件e匹配的订阅都意味着sS

t = No。事件e中的1。

1)订阅分区:在这个过程中首先是k p, p…P 1 2分为t+1个块，每个块有k/ (t+1)个连续属性。设r = k/ (t+1)分区为| rp p。P 1 2 || r r r P P p1 2 2 ..|……| tr tr tr p p p 1 2 (1) ..|。为清晰起见，这些块被表示为t t t t P P 1 2 1， ... .使用这个分区，二级分区在RAPIDMatchSets中定义如下:t S被划分为t+1集t t t t t t 1 2 1， ... .集合tj t包含在tj P中有0或*的订阅。请注意，由于t S包含最多t1的订阅，并且由于有t+1个谓词块，因此至少有一个谓词块必须完全没有1，因此每个订阅可以放置在至少一个t j t中。订阅可能适合(并被放入)更多这样的集合。 The partitions are illustrated in Fig. 7 [27].

2) RAPIDMatch使用的数据结构:基于上述分区，在RAPIDMatch中构建数据结构如下[27]:

RAPIDMatchSets S0, S1，…c S。

对于0≤t≤c，进一步将t S划分为t+1组t T1, t T2，…t t T1。对于每个这样的集合，为集合中的订阅构建一个名为RAPIDMatchTree的搜索树。

每个RAPIDMatchTree tj t是一棵受限搜索树，它以循环顺序处理所有属性，从tj P之后的属性，即jr1 P，到kp，然后绕到1p，最后到jr P(1)。这样，就避免了块t j P中的性质。

对于c1 S中的订阅，构建一个标准的(1 p, 2 p，…，k p)限制搜索树，以测试所有的k个属性。

？匹配算法:RAPID Match匹配算法的运行过程如下:[27]:

上述算法的局限性在于，算法只有在t ?K /(t ?1)，但当该条件不满足时，匹配过程的运行时间增加，算法的效率降低。因此，我们对快速匹配算法进行了改进，命名为改进快速匹配算法。

D.提出的改进快速匹配算法在这个算法中使用的术语是，

e =发布事件。

S=一组订阅。

ipp =事件的属性。

kp =订阅中的谓词。

k = No。的谓词。j P =No。发布事件的分区。

j T =包含T中有0或*的订阅

t S =包含最多t1的订阅。

S=任何与事件e匹配的订阅都意味着S ?年代

t = No。在事件e中0或1，以计数少者为准。

修改后的RAPIDMatch算法中使用的订阅分区和数据结构与上述RAPIDMatch算法中使用的数据结构相同。但该算法的修改只是在匹配过程中

St 1点如下所述。

1)匹配算法:改进的RAPID Match匹配算法运行如下:

该算法可以检查在给定事件e中出现次数较少的布尔值，而不是根据其中出现的1的数量来划分订阅。例如，如果事件e给定为{0,1,1,0,1}，并且七个订阅被给定为:

S = {0,0,1,1,1}

S = {0,1,1,0,1}

S = {*， 1,1， *， 1}

S = {0,0,0,0,0}

S = {0,1， *， 0,1}

S = {0,1,0,0,0}

S ={1,0， *， 0,1}给定的事件有两个0和三个1。所以，对0的搜索要比对1的搜索简单。订阅是根据0的数量进行分区的。分组是:

2)考虑位置的搜索。在这里，*被视为0和1，包含*的订阅出现在两列中，首先接受0，然后接受1。该算法不考虑包含全部0或全部1的订阅，因为它们与事件不匹配。然后，算法转到包含两个0的列(因为事件有两个0)。我们知道0在st 1和th 4的位置。现在，它不再线性比较订阅与事件，而是检查订阅中0的位置。它消除了订阅7s，在st 1的位置，有1而不是0。考虑到其他两个订阅，我们发现在所需的两个位置都有0。因此，匹配事件的订阅为2s和7s。

E. SGIM算法

SGIM算法分为两个阶段。在第一阶段，它通过与事件[28][29]的相关属性相对应的谓词对订阅进行分组，从而对订阅进行预处理。利用统计学的基本分组思想来确定的个数。在第二阶段中，匹配的订阅或谓词按顺序派生。存储在系统中的所有谓词都与唯一的ID相关联。类似地，订阅也用订阅id标识。

我们框架中的发布-订阅组件工作流如下:

？用户向各种SaaS应用程序注册他们的信息和订阅，然后这些应用程序将所有这些信息传输到发布/订阅代理注册中心。

？当传感器数据从网关到达系统时，发布/订阅代理中的事件/流监视和处理组件(SMPC)决定是否需要处理它，或者只是存储以定期发送或立即交付。

？如果传感器数据需要定期/紧急交付，分析人员将确定事件属于哪些SaaS应用程序，然后将事件连同应用程序id一起传递给传播者。

？传播程序使用事件匹配算法为每个应用程序找到适当的订阅者，并将事件交付使用。

SGIM算法是一种快速、可扩展的事件匹配算法，称为统计组索引匹配。SGIM算法分为两个阶段。在第一阶段，它通过根据事件的相关属性对应的谓词对订阅进行分组，从而对订阅进行预处理。采用统计学的基本分组思想来确定

组数。在第二阶段中，匹配的订阅或谓词按顺序派生。存储在系统中的所有谓词都与唯一的ID相关联。类似地，订阅也用订阅id标识。

对于普通的范围谓词或高度重叠的范围谓词，它可以大大减少快速事件匹配的搜索空间，因为它可以通过检查组的索引直接选择或删除一个或多个订阅组。然后使用顺序搜索，当订阅中的任何谓词被求值为false时，不需要对其余谓词求值。此外，如果该谓词由许多订阅共享，则可以忽略这些订阅中的所有剩余谓词，这可以显著降低计算开销。SGIM的评估成本与订阅数成线性关系。

在系统中插入新订阅的算法与事件匹配算法非常相似。首先，算法找到与订阅匹配的组索引并将其插入到该组中。如果需要，可以为订阅插入更新组索引。插入算法的代价接近事件匹配代价。删除算法非常简单。我们只需要找到要删除的订阅的确切组索引，然后从组中删除它，并在必要时更新组索引。如果整个组需要删除，那么我们可以搜索该组索引并删除它。

实验装置

本实验在Java中实现了四种匹配算法。所有实验都是在Pentium IV处理器上进行的，运行频率为2.0 GHz，内存为512 MB。我们生成250-1000个带有50个属性的谓词的订阅。每个订阅谓词接受值0,1，*。性能结果以秒为单位显示。

仿真结果

在模拟中，我们绘制了运行时与no之间的图。的订阅。本文采用三种匹配算法进行评估。可以观察到，在Naive与RAPIDMatch和Modified RAPIDMatch算法的比较中，Naive算法的性能大大降低。但在RAPIDMatch算法与Modified RAPIDMatch算法的比较中，Modified RAPIDMatch算法的效果更好。在图11的另一个图中，我们比较了所有四种算法，得出结论:当没有。的订阅数较少，则Naive、RAPIDMatch和Modified RAPIDMatch三种匹配算法的性能均优于SGIM算法，但SGIM算法的性能优于其他三种匹配算法，此时订阅数过大。

结论

给出了基于内容的发布者-订阅者系统中三种不同的事件匹配问题，如图10中的Naive算法和Tree - based算法。基于树的算法比其他算法效率更高。从观察中可以得出结论，提出/开发的改进RAPIDMatch算法优于其他算法。我们提出的Modified RAPIDMatch根据订阅的谓词特征离线划分订阅，以便对于给定的事件，我们可以快速识别相关订阅的一小部分并减少其搜索空间。但当不选择时，SGIM算法的性能优于其他三种算法。订阅费太高了。事件匹配算法的效率如图所示。我们未来的工作是利用真实的出版者和订户信息进行更深入的了解和更全面的评估。

表格一览

表1

数字一览


图1	图2	图3	图4	图5

图6	图7	图8	图11	图11 b

参考文献

于A, Agarwal, P. K.， Yang J.，“基于内容的发布/订阅”，IEEE，知识与数据工程学报，第24卷，第1期。2012年10月10日。

张，A.K.Y, Jacobsen, H. A.，“发布/订阅系统的绿色资源分配算法”，分布式计算系统国际会议论文集，DOI:10.1109/ICDCS.2011.82，在:分布式计算系统(ICDCS)， 2011。

Baldoni, R.， Marchetti, C.， Virgillito, A.和Vitenberg, R.，“结构化覆盖网络上基于内容的发布-订阅”，ICDCS ' 05, 2005。

张，A.K.Y, Jacobsen, h.a.，“负载均衡内容发布/订阅系统”，多伦多大学，第28卷，第9期，第4期，2010年。

Aguilera, M.K, Strom, R.E. Stunnan, D.C. AsHey, M, Chandra, t.d.，“基于内容的订阅系统中的匹配事件”，在PODC ' 99亚特兰大GA美国版权ACM I-581 13- 09-6/99 /05, 1999。

Eugster, p.t.， Pascal, A.， Felber, Guerraoui, R.， Kermarrec, a.m.，“出版/订阅的多种面貌”，ACM计算调查，第35卷，No. 32, pp. 114-131, 2003。

Oki, B.， Pfluegel, M.， Siegel, A.， Skeen, D.，“信息总线-广泛分布式系统的架构”，1993年ACM操作系统原理研讨会论文集，1993。

Altherr, M.， Erzberg, M.， Maffeis, S.，“iBus - java平台的软件总线中间件”，载于:可靠中间件系统国际研讨会论文集。Pp、49 - 65,1999

Castro, M.，Druschel, P.， Kermarrec, A.， Rowston, A.，“Scribe:大规模和分散的应用程序级多播基础设施”，IEEE通讯领域杂志，2002。

庄世强，赵碧云，Joseph, A.D.， Katz, R.， Kubiatowicz, J.，“Bayeux:一种可扩展和容错的广域数据传播架构”，第11期。数字音频和视频的网络和操作系统支持研讨会。2001

对象管理组:CORBA事件服务规范，1.1版。OMG正式文档/2000-03-01,2001。

Baehni, S.，Eugster, p.t.， Guerraoui, R.，“数据感知组播”，载于:2004年可靠系统与网络国际会议论文集，第233-242页，2004年。

Carzaniga, A, Rosenblum, d, Wolf，a .“广域通知服务的设计与评估”，计算机学报，第332 - 383页，2003。

Fabret, F.， Jacobsen, A.， Llirbat, F.， Pereira, J.， Ross, K.， Shasha, D.，“快速发布/订阅的过滤算法和实现”，第20届国际会议论文集。数据管理会议(2001)，第115 - 126页，2001。

康帕米拉，A.，Chaki, S.， Clarke, E.M.， Jha, S.， Veith, H.，“使用二元决策图在发布-订阅系统中的有效过滤，载于:软件工程国际会议论文集，第443 - 452页，2001。

Bittner, S.，Hinze，答:,”关于非规范过滤在发布/订阅系统中的好处”，在分布式基于事件的系统国际研讨会论文集(ICDCS/DEBS ' 05)， 2005。

Muhl, G.，“基于内容的发布/订阅的一般约束”，见:第六届国际合作信息系统会议(CoopIS)， 2001。

鹰头狮网站:http://www.research.ibm.com/gryphon/

锡耶纳网站:http://www.cs.colorado.edu/users/carzanig

Cugola, G.， Nitto, E.D.，Fuggetta, A.，“利用基于事件的基础设施来开发复杂的分布式系统”，在第十届软件工程国际会议论文集(ICSE ' 98)中，1998。

皮特,r。Pereira, J.， Llirbat, F.， Fabret, F.， Oss, K.， Shasha, D.，“在网络上以极快的速度发布/订阅”，《数据管理SIGMOD会议论文集》，开罗，埃及，2000。

Gruber, r.e.， Krishnamurthy, B.， Panagosf, E.，“就绪事件通知服务的体系结构”，《分布式计算系统国际会议论文集》，中间件研讨会，奥斯汀，德克萨斯，1999。

Pietzuch, P.， Bacon, J.， Hermes，“分布式基于事件的中间件架构”，在分布式基于事件的系统国际研讨会论文集(DEBS ' 02)。(2003)

segal, B.， Arnold, D.， Elvin已经离开大楼“一个发布/订阅通知服务的淬火”，1997年澳大利亚UNIX和开放系统用户组会议论文集，1997

霍尔，C. P.，卡扎尼加，A.，罗斯，J.和。Wolf, a.l.，“传感器网络的基于内容的网络协议”，科罗拉多大学计算机科学系，技术报告，2004年。

Fabret F。，Llirbat,F., Pereira,J., Shasha,D., “Efficient Matching for Content-based Publish/Subscribe Systems”, Founded by “Instituto SuperiorT´ecnico”- Technical University of Lisbon and by a JNICT fellowship of Program PRAXIS XXI (Portugal)

甘蓝、S。，Hazan,E., Cao,F., Singh,J.P., “Analysis and Algorithms for Content-based Event Matching”, Supported by Prof. SanjeevArora’sDavid and Lucile Packard Fellowship, NSF grants CCR 0205594 and CCR 0098180.

哈桑，m.m.，宋，B。,哈，E.N。”传感器框架-云集成机遇与挑战”，该研究由韩国知识经济部(MKE)支持，由IITA(信息技术进步研究所)监督的ITRC(信息技术研究中心)支持计划(IITA-2009-(C1090-0801-002))。

Hunkeler U。，Truong, H. L., and Stanford-Clark, A. , “MQTT-S –A Publish/Subscribe Protocol For Wireless Sensor Networks”, In IEEEConference on COMSWARE, 2008.

国际电气、电子和仪器工程高级研究杂志