Load shedding in complex event processing with probabilistic features

Abstract

Complex Event Processing (CEP) is a stream processing paradigm primarily searching for event type patterns in continuous event streams. Furthermore, load shedding is a common practice in CEP applications when resources are limited and under heavy load. Operators, which become a bottleneck due to bursts in event streams and therefore message queuing, drop event messages with a low matching probability to comply with their latency bound. Existing CEP load shedding mechanisms show a need for improvement if application queries consider an arithmetic relation between event attribute values, which are then called dependent attributes. In this case, incoming events of the same type must be differentiable in their individual matching probability, which bases on their dependent attribute values. This work introduces the Probabilistic Feature Shedding (PFS) approach, which leverages probability distributions of the dependent attribute values to derive thresholds as shed margins for incoming events. These thresholds categorize incoming events into probable and improbable events to fulfill the arithmetic relation. Improbable events are dispensable for their lower matching probability. The intention behind the PFS mechanism is, that existing shedding mechanisms are complemented with its functionality. In the course of this work, a random shedding mechanism and a distributed shedding approach with linear program solver are each extended with an implementation of the introduced PFS paradigm. Hence, extensive experiments on synthetic datasets as well as a real world dataset are executed with the different shedding paradigms and extensions. The results of all experiments confirm the expectation of a significant improvement in output quality, measured in the number of complex events. Furthermore, simulations show a linear dependency between probabilistic feature evaluation and processing time.

Complex Event Processing (CEP) ist ein Paradigma zur Bearbeitung von Datenströmen, welches kontinuierliche Eventströme auf Muster von Event Typen untersucht. Desweiteren ist Load Shedding eine übliche Praxis bei CEP Anwendungen, wenn Operatoren eine hohe Belastung aufweisen, aber in ihrer Rechenleistung limitiert sind. Operatoren, welche aufgrund von Belastungsspitzen in Eventströmen starten, Nachrichten einzureihen und darum zu einem Flaschenhals der Anwendung werden, lehnen die Bearbeitung von Eventnachrichten mit niedriger Wahrscheinlichkeit für eine Übereinstimmung mit dem gesuchten Muster von vonherein ab, um ihre Grenze der Latenzzeit einhalten zu können. Existente CEP Load Shedding Mechanismen sind verbesserungsfähig sobald Anwendungen in ihren Suchanfragen nach arithmetischen Beziehungen zwischen den Werten von Eventattributen, welche aus diesem Grund auch abhängige Attribute genannt werden, suchen. In diesem Falle müssen eingehende Events desselben Typs differenzierbar in ihrer Wahscheinlichkeit der Übereinstummung mit dem Suchmuster sein, welche auf den Werten ihrer abhängigen Attribute basiert. Diese Arbeit stellt einen Probabilistic Feature Shedding (PFS) Ansatz vor, welcher die Wahrscheinlichkeitsverteilungen von abhängigen Attributen verwendet, um Schwellenwerte zur Ablehnung von eingehenden Eventnachrichten zu bestimmen. Diese Schwellenwerte erlauben eine Kategorisierung von eingehenden Events in wahrscheinlich und unwahrscheinlich, dass sie die arithmetische Beziehung erfüllen. Events, welche als unwahrscheinlich eingestuft wurden, sind aufgrund ihrer niedrigen Wahrscheinlichkeit für eine Übereinstimmung schlussendlich entbehrlich. Die Intention hinter diesem PFS Mechanismus ist eine Erweiterung mit dessen Funktionalität, und dadurch eine Verbesserung von existenten Load Shedding Mechanismen. Im Verlauf dieser Arbeit wurde ein zufälliger Load Shedding Mechanismus sowie ein verteilter Ansatz, welcher auf einem Gleichungslöser für Lineare Programme basiert, um eine Implementierung des vorgestellten PFS Paradigmas erweitert. Daraufhin wurden umfangreiche Experimente mit synthetischen sowie echten Daten für verschiedene Load Shedding Paradigmen und deren Erweiterungen durchgeführt. Die Ergebnisse dieser Experimente bestätigen die Erwartung einer signifikanten Verbesserung der Qualität, welche an der Anzahl der erzeugten Komplexen Events gemessen wird, am Ausgang der Anwendung. Desweiteren zeigen Simulationen eine lineare Abhängigkeit zwischen der Auswertung von Wahrscheinlichkeiten der Attributwerten zu der benötigten Zeit um diese zu berechnen.