Design and implementation of highly-efficient data structures for parallel complex event processing framework on multicore shared memory architecture

Abstract

Social networks, financial applications, Internet of Things (IoT) technology, etc. are systems that produce a continuous stream of data. Due to the increase in the amount of data generated, there is a need for systems that facilitate the real-time interpretation of the generated data. Complex Event Processing (CEP) is one such system. A Distributed Complex Event Processing (DCEP) system helps to infer complex occurrences from the received sensor readings. In order to increase the throughput of operators, data parallel DCEP systems split incoming event streams into windows with overlapping events that can be processed independent of each other. However, as consumption policies call for consumed events of a window to be excluded from dependent windows, data parallelization between windows could be affected. This problem was solved in the existing work by means of speculation. The SPECTRE system proposes maintaining two different versions of a window for each event that could be consumed – one which assumes that a detected event will be consumed and one which assumes that the event will not be consumed. Several data structures are used to represent the relationship between the window versions and this is information is stored in the shared memory. As all components need to access the shared memory, it could cause a bottleneck on the system performance. Also, once the outcome of an event is known (whether it is consumed or not), the memory allocated for the irrelevant window versions should be reclaimed. This poses a load on the garbage collector. Hence, the goal of this thesis is to design data structures to improve memory allocation and utilization and ease the load on the garbage collector.