Research And Implementation Of Complex Events Based Abnormality Recognition And Early-Warning Technologies In Distributed Computing Systems

With the continuous development of information technology, distributed computing systems become increasingly sophisticated. A variety of abnormalities in distributed systems, such as virus attacks in network, vehicle blockings in traffic monitoring systems, malicious money launderings hidden in financial algorithm trading, are bound to reflect a series of abnormal changes of information states. The states changes that systems concerned are events. That is to say, system abnormalities are related to a set of events in essential. On the other hand, events among this set are related to each other by temporal and logical correlations. Events with such temporal and logical correlation relationship involved in an abnormality together give rise to the concept of complex events. How to timely find and locate the speficied system abnormalities throuth recognition of complex events, is becoming one of important and hot research topics in distributed computing community. Based on the analysis of the latest achievements in this community, we conduct in-depth studies on expressive language of complex events, recognition algorithm, instance screening policy, and proactive early-warning technologies of abnormalities, the main contributions include:First, based on event algebra we design a formal expressive language of complex events called CREWLan. CREWLan defines event structure, including temporal and logical operators, as well as recursive generation rule of complex events connected by operators. Event structures define event type, occurrence time, and other event properties for an event, and define occurrence time of an event as interval time stamp. Based on event structure and time model, event operators define the temporal and logic relationship among events which recursively constitute complex events. CREWLan clearly expresses the sturctures and complicated relationships of a set of events invovled in an abnormality, thus it is expressive. We present the BNF of CREWLan, then use meta-language tool ANTLR to get the compiled syntax parser. For each expression of complex event, the parser can automatically generate a corresponding recognition tree, which represents the specified system abnormality. The leaf nodes of recognition trees are primitive events come from external environments. Multiple recognition trees might constitute a forest, which represent multiple system abnormalities.Secondly, we propose deadline matching policy based recognition methods, and design a corresponding recognition engine. Under network environments, events occurred early can arrive in recognition engine later, this is called the out-of-order arrival problem. Deadline matching policy allows the early arrived events matching with the delayed events during a specified time span. Thus, deadline matching policy can solve the out-of-order arrival problem in some degree. Further, there are shared nodes, especially nodes in equivalent semantic but different syntax, in a recognition forest composed by a number of recognition trees. These shared nodes can share the same matching process. Based on algebraic semantic ecuivalence of nodes, we design a shared nodes searching algorithm to effectively reducing matcing time in recognition forest. Experimental results show that in scenarios of multiple recognition trees, our recognition engine can achieve 25% lower matching time and 40% higher throughput than other similar systems.Thirdly, we designed retaining-latest principle based event intances screening strategy and its implementation algorithm, which effectively prevent the combinatorial explosion of event instances during recognition process. If there are multiple matching instances during recognition process, based on latest principle, the strategy only retain instances with latest start time and same end time as intermediate outputs to the next matching step. Algebraic reasoning shows that the strategy is of good algebraic properties that it can be recursively applied to the child complex events, and its spatial and temporal complexity of recognition is only proportional to the depth D of recognition tree, i.e. O(D2). The experimental results verify the effectiveness of the screening strategy.Fourthly, for weak complex events which ignore temporal relationships, we designed top-k based proactive early-warning technology of system abnormalities. For early-warning of system abnormalities, we treat complex events or abnormalities as sets of events occure during a time span. This method stores importance and probability of complex events in database and build indices for them, and based on top-k., computes continuously the overall scores of importance and occurrence probability upon events in sliding window, to decide which k complex events with highest overall scores are most likely to be imminent, without waiting until the total corresponding component events arrive. As optimization, we make preprocess through sorted access phase, to reduce the main computing overhead caused by random accesses. Expriment results show that the method can achieve rapid top-k continuous computing, and the sliding window size and other factors have no obvious effects on the computing performance.Finally, based on the above works, we design and implement a complex event based abnormality recognition and early-warning system called CREW. We discuss its applications too.