Combining expressiveness and efficiency in a complex event processing middleware

Several complex systems operate by observing a set of primitive events that happen in the external environments, interpreting and combining them to identify higher level composite events, and finally sending the notifications about these events to the components in charge of reacting to them, thus determining the overall system’s behavior. Examples of systems that operate this way are sensor networks for environmental monitoring, financial applications, fraud detection tools, and RFID-based inventory management. More in general, the information system of every complex company can and should be organized around an event-based core that realizes a sort of nervous system to guide and control the operation of the other sub-systems. The task of identifying composite events from primitive ones is performed by the Complex Event Processing (CEP) Engine. It operates by interpreting a set of event definition rules that describe how composite events are defined from primitive ones. The CEP engine is usually part of a CEP system or middleware which also handles the communication with local and remote clients. To capture all the requirements of the aforementioned applications, a CEP engine has to face several challenges. First, it has to provide a suitable language for rule specification, explicitly tailored to model complex temporal relationships that join together primitive events in composite ones. Second, it has to implement efficient processing algorithms, to detect composite events and deliver notifications to interested parties with the lowest possible delay. Finally, it has to support distributed scenarios, in which the communication parties may be deployed over a wide geographical area. This thesis first proposes a modelling framework to compare and analyze not only existing CEP systems, but all the systems developed with the aim of processing continuous flows of information according to pre-deployed processing rules. This allows us to identify the main advantages and limitations of existing approaches, by looking at a wide range of proposals. Moreover, our modelling framework draws a common ground for comparing efforts coming from different research communities, with different background, expertise, and vocabulary. We believe that our work can bridge the gap between different worlds, promoting the communication and reducing the effort required to compare and merge the results produced so far. Moving from the issues identified while analyzing existing works, we introduce T-Rex, a new CEP system explicitly designed to combine expressiveness and efficiency. In particular, we first present TESLA, the new event definition language used by T-Rex. TESLA is explicitly designed to model in an easy and natural way the complex relationships that join primitive events and the actions required to aggregate them to obtain composite events. Then we discuss in details the implementation of T-Rex, studied to efficiently process TESLA rules. First of all we focus on the problem of matching, i.e., selecting relevant (primitive) events based on their content, which is one of the fundamental actions present in every event-based system. We propose a novel matching algorithm explicitly designed to take advantage of parallel hardware, including modern Graphical Processing Units (GPUs). This is the first solution that analyzed the adoption of parallel hardware to speed up matching and our evaluation shows impressive results with respect to existing sequential solutions. Afterward, we focus on complete TESLA rules, and we discuss and compare two different processing algorithms that take two opposite approaches to process incoming events. A comparison with existing products shows the effectiveness of both our proposals and the differences among them. Independently from the adopted algorithm, T-Rex leverages the presence of multiple processing cores to efficiently evaluate different rules in parallel. To further reduce the time required to handle the most complex rules, i.e., those involving a large number of primitive events, we present and evaluate a third algorithm to process TESLA rules on GPUs. Our contribution goes beyond the implementation of T-Rex, indeed this is the first work that describes in details how CEP can leverage off-the-shelf parallel hardware: multi-core CPUs and GPUs. Since our analysis is organized around the basic language constructs provided by TESLA, but also present in most of existing CEP languages, our work represents an important contribution to determine how CEP can take advantage of currently available parallel hardware architectures and which processing algorithms are best suited to exploit their processing power. The last aspect examined by this thesis is how to take advantage of the availability of multiple processing nodes, distributing the processing load over different machines, to better support large-scale distributed scenarios, reducing the delay required to receive results, or the occupation of network resources. To this extent, we present and compare different solutions for a distributed T-Rex, extracting the advantages and limitations of each of them. They include the protocols to organize available nodes into an overlay network, to partition and distribute event definition rules, and to cooperatively handle event processing and delivery.

Molti sistemi complessi si basano sull’osservazione di eventi primitivi provenienti dall’ambiente esterno, interpretandoli e aggregandoli in eventi compositi, che offrono una conoscenza del mondo a un livello di astrazione superiore. Infine, inviano notifiche di tali eventi a tutti i componenti adibiti a prendere decisioni e mettere in atto azioni sulla base di essi, determinando in questo modo il comportamento complessivo del sistema. Esistono svariati sistemi che operano in questo modo: le reti di sensori per il monitoraggio ambientale, le applicazioni finanziarie, i tool per la scoperta di frodi bancarie e i sistemi automatici di gestione dei prodotti basati su tecnologia RFID. Più in generale, il sistema informativo di ogni azienda può e dovrebbe essere organizzato intorno a un centro di gestione degli eventi, che realizzi una sorta di sistema nervoso per guidare e controllare il comportamento di ogni altro sotto-sistema. Il compito di identificare eventi compositi a partire da eventi primitivi è svolto da un motore di Complex Event Processing (CEP). Esso interpreta una serie di regole che descrivono come gli eventi compositi sono definiti a partire dai primitivi. Il motore di CEP è solitamente parte di un sistema o middleware di CEP, il quale si occupa anche di gestire la comunicazione con componenti locali e remoti. Per rispondere a tutte le esigenze delle applicazioni prima descritte, un motore di CEP deve soddisfare alcuni requisiti. In primo luogo, deve fornire un adeguato linguaggio per la definizione delle regole, espressamente studiato per esprimere complesse relazioni temporali. In secondo luogo, deve implementare algoritmi di processing efficienti, per produrre eventi compositi e inviare notifiche ai componenti interessati con una bassa latenza. Infine, deve poter supportare scenari distribuiti, in cui gli attori che prendono parte alla comunicazione potrebbero coprire una vasta area geografica. In questa tesi viene dapprima proposto un framework di modelli che permette di analizzare e confrontare non solo i sistemi CEP esistenti, ma più in generale tutti i sistemi nati per processare flussi continui di informazioni sulla base di un insieme di regole. Questo ci permette di individuare i principali vantaggi e limitazioni degli approcci proposti sinora, guardando ad un ampio insieme di sistemi. Inoltre, il nostro framework definisce un terreno comune per il confronto degli sforzi di ricerca intrapresi da diverse comunità, aventi diverse basi teoriche, conoscenze, e terminologie. Crediamo che questo lavoro possa contribuire a ridurre la distanza fra le diverse aree di ricerca, semplificando la comunicazione e agevolando lo scambio di esperienze, per portare a un’unione dei risultati ottenuti nel recente passato. Partendo dalle problematiche individuate durante l’analisi dei sistemi esistenti, nella tesi viene poi presentato T-Rex un nuovo sistema di CEP, pensato per offrire espressività ed efficienza. In particolare, proponiamo innanzitutto TESLA, il nuovo linguaggio utilizzato da T-Rex per la definizione di eventi. TESLA è espressamente pensato per modellare in modo semplice e naturale le complesse relazioni tra eventi primitivi e le azioni necessarie per aggregarli in eventi compositi. Successivamente viene presentata in dettaglio l’implementazione di T-Rex, studiato per processare in modo efficiente regole TESLA. La tesi si sofferma prima sul problema del matching, ovvero della selezione di eventi (primitivi) sulla base del contenuto degli eventi stessi. Tale problema sta alla base di ogni sistema a eventi. Nella tesi si propone un nuovo algoritmo espressamente progettato per sfruttare hardware parallelo, incluse le moderne schede grafiche (GPU). Questo è il primo lavoro in cui si analizza l’utilizzo di hardware parallelo per velocizzare il processo di matching e la fase di valutazione mostra significativi miglioramenti rispetto agli algoritmi sequenziali presenti in letteratura. La tesi si concentra quindi sulla valutazione completa di regole TESLA, descrivendo e confrontando due algoritmi di processing che seguono due diversi approcci per l’analisi degli eventi in ingresso. Un confronto con i sistemi esistenti mostra i benefici della proposta presentata. Indipendentemente dall’algoritmo adottato, T-Rex è in grado di sfruttare la presenza di più core per valutare in maniera efficiente diverse regole in parallelo. Un ulteriore contributo della tesi deriva dalla definizione di un algoritmo di processing espressamente pensato per girare sulle moderne schede grafiche, il quale permette di ridurre significativamente il tempo necessario per gestire singole regole complesse, che richiedono l’analisi di un ingenete numero di eventi. È nostra convinzione che il contributo di questa tesi vada oltre la semplice progettazione e implementazione di T-Rex. Infatti essa è il primo lavoro ad analizzare in dettaglio come CEP possa trarre vantaggio dalla presenza di hardware parallelo: multi-core CPU e GPU. Sebbene la nostra analisi si concentri sugli operatori offerti da TESLA, questi costituiscono la base di molti linguaggi per la definizione di eventi presenti in letteratura. Per tale ragione il nostro lavoro costituisce un importante contributo per determinare come CEP possa trarre vantaggio dalle architetture di hardware parallelo oggi disponibili e quali algoritmi di processing siano più adatti per sfruttarne al meglio le caratteristiche. L’ultimo aspetto esaminato in questa tesi riguarda la possibilità di sfruttare la presenza di diversi nodi, distribuendo il carico di processing tra essi, al fine di offrire un miglior supporto a scenari distribuiti, riducendo la latenza necessaria per la ricezione di risultati e l’occupazione di risorse di rete. In tale ambito presentiamo e confrontiamo diverse soluzioni per un sistema T-Rex distribuito, evidenziando i vantaggi e le limitazioni di ognuna di esse. Tali soluzioni includono i protocolli per organizzare i nodi disponibili in una overlay network, per scomporre e distribuire le regole di definizione degli eventi e per gestire in modo cooperativo l’elaborazione e l’invio di eventi.