Study On Event Matching Of Large-Scale Publish/Subscribe Systems

The rapid development of network technologies has been increasing the scale of distributed systems which impose higher requirements for communication models. As being an event-based flexible communication paradigm, the publish/subscribe system realizes full decoupling of communicating parties in space, time and synchronization,satisfying the communication requirements of large-scale distributed systems. The publish/subscribe system has been successfully applied in many fields, such as content dissemination, information filtering, e-commerce and online games. Among the variants of publish/subscribe systems, the content-based publish/subscribe system is the most expressive one, able to achieve fine-grained filtering of information. However, the cost of event matching in the content-based publish/subscribe system is pretty high. Thus, event matching is one of the research focuses and key technologies of the content-based publish/subscribe system.Large-scale content-based publish/subscribe systems have higher performance requirements for matching algorithms. First, there are great number subscriptions in large-scale publish/subscribe systems and each subscription contains multiple constraints. So, the scale of subscriptions set is very large. Second, due to the great number of subscriptions, the number of matched subscriptions is also large in large-scale publish/subscribe systems. However, the performance of most existing matching algorithms degrades with the increase of the number of matched subscriptions. Third,it is difficult to satisfy the quality of service(Qo S) requirements of all subscribers in a large-scale publish/subscribe system, especially during the peak load periods. Providing Qo S support is an effective way to solve the overload problem by guaranteeing event delivery for subscribers with high Qo S requirements. So far, there is no matching algorithm that takes the priority of subscriptions into account in the course of event matching, without supporting Qo S. Based on existing matching algorithms, this thesis focuses on these three aspects, aiming to improve the matching efficiency in large-scale content-based publish/subscribe systems.This thesis first analyzes the effect of the scale of subscriptions set on matching algorithms in large-scale publish/subscribe systems, pointing out that the performance of matching algorithms that are based on counting algorithm rapidly degrades with the number of subscriptions. For this problem, this thesis designs an efficient index structure H-TREE, which is applicable to event matching in large-scale publish/subscribe systems. The basic idea of H-TREE is to speed up event matching by reducing the scale of subscriptions set. H-TREE is a hash table in nature, composed of a certain number of buckets. When indexing subscriptions, similar ones are stored together in the buckets of H-TREE. When matching events, H-TREE is capable of filtering most unmatched subscriptions, only checking subscriptions that have high matching probability. To evaluate the performance of H-TREE, tests are performed on a DEll Power Edge T710 server with 8 2.4GHZ cores and 32 GB RAM. Experimental results show that the matching speed of H-TREE is faster by three orders of magnitude than its counterparts when the numbers of both subscriptions and their component constraints are huge. The research was publish on IEEE Transactions on Parallel and Distributed Systems.To eliminate the effect of the number of matched subscriptions on the performance of matching algorithms, this thesis proposes a fast event matching algorithm REIN.REIN uses reverse searching policy to improve matching speed by finding and marking unmatched subscriptions, rather than traditional policy that is based on counting algorithm. Compared with existing matching algorithms, REIN has several advantages. First, the performance of REIN improves with the increase of the number of matched subscriptions. Second, REIN is not affected by the distribution of constraint values. Third, REIN is very efficient to deal with subscription update(insert or delete)operations, applicable to some dynamic environments. Experimental results show that,on average, REIN is faster by an order of magnitude than its counterparts when the selectivity of subscriptions is high. The research was published on IEEE INFOCOM2014.To address the overload problem in larger-scale publish/subscribe systems, this thesis proposes the idea of prioritized event matching, aiming to provide Qo S support in event matching. Prioritized event matching guarantees that matched subscriptions with high priority should be determined earlier than the ones with low priority. Combined with Qo S support on routing, prioritized event matching can provide complete Qo S support, breaking through the blind spot of Qo S support in the event delivery path.Based on REIN, this thesis implements a prioritized event matching algorithm, called Pri-REIN. Experimental results show that Pri-REIN is able to provide Qo S support in event matching, achieving the intended design goal. More importantly, the idea of prioritized event matching proposed in this thesis can be widely applied to the matching algorithms that are used in cloud computing or complex event processing systems.Experimental results show that the determining time of matched subscriptions with high priority is smaller by 30% than the one with low priority. The research has been accepted by the ACM DEBS 2015.