Research On Data Model And Event Matching Algorithm Of Stateful Publish/Subscribe System

Network computing such as pervasive computing, mobile computing and so on is a new generation of large-scale distributed computing with the main features of large-scale, decentralized control, dynamic, autonomous and loosely coupled. Since publish/subscribe systems have the advantages of loose coupling, anonymity, many-to-many communication and scalability, they have become important infrastructure middleware platforms support for the new generation of network computing.Stateful publish/subscribe system is based on general publish/subscribe system, and realizes the composite event detection. It not only supports single event subscriptions, but also supports for composite event subscriptions. When the publishers publish a sequence of events which satisfy a certain conditioin, notify the subscribers. So you can efficiently handle complex events, thereby improving system performance. It has important application value and research significance.For the deficiency of data models' expressive ability and insufficient performance of matching algorithm of existing stateful publish/subscribe systems, this thesis makes the research mainly on key technologies including data model and matching algorithm of stateful publish/subscribe systems. The work has been supported by the National High-Tech. R&D Program, China.In the first part of thesis, we discuss the research background and significance of publish/subscribe system. After explaining the conceptual model of publish/subscribe system, we introduce research situation of key technologies including data model, matching algorithm, systems' topology and routing algorithm. Finally, we introduce the concept of stateful publish/subscribe systems and analyze the chanllenges and research focus of stateful publish/subscribe systems.In the second part, we present the data model of composite event. First, we analyze the traditional composite event models, and compare their advantages and disadvantages. Then data model of our stateful publish/subscribe system is introduced from two aspects: composite event model and subscription model. Composite event model includes composite event pattern and time model. Composite event pattern describes the trigger relationships of multiple single events or composite events, and time model describes the time relationship between events. Subscription model is concerned about what subscribers want to get, and it greatly decides the system's expressivness. Subscribe model includes subscription language and observation model. Subscribe language is used by subscribers to subscribe composite events which they are interested in. This paper presents an SQL-like query language, which supports a variety of composite event subscription operations. And we use formal language to clearly describe these subscription operations. Observation model is used to detect the composite events which subscribers are interested in, and we propose the extended non-deterministic finite automata for observation model.In the third part, we propose fast event matching algorithm using of the relationship of predicates. Efficient matching algorithm is the key to reconcile the contradictions between abundant expression and scalability of system. We first introduce the entire matching process, including the features and the difficulties in implementation. Then, we propose a pipelined event processing method, which takes advantage of multi-threaded approach to make the matching process pipelining. This method improves the event matcing efficiency from the macro level. Next, we fully exploit the relationship of predicates from micro level, and propose an algorithm, called relation predicates matching algorithm. This algorithm builds a special data structure, called predicate relation table for indexing the predicates of the subscriptions. As the order of the predicates to be judged also plays an inportant role in the event matching, we exploit the order of the predicates to be judged, and propose the other algorithm, called order predicates matching algorithm. It uses of historical data to predict future data, and organize the predicate relation table in sertain order according to the historical data, to further improve the matching efficiency. Finally, we do experiment for relation predicates matching algorithm and order predicates matching algorithm, with base algorithm for comparison. Results show that order predicate matching algorithm demonstrates a very good event matching efficiency, and a good improvement in system performance. In the forth part, we propose a scalable and configurable stateful publish/ subscribe system architecture. The prototype system mainly includes matching manager, subscription manager, event manager, and notify manager. By each module's expansion strategy, meta-service management and configuration management, we make the system extensible and configurable. Finally, we introduce the stateful publish /subscribe prototype system.