Window drop load shedding in complex event processing

Abstract

In Complex Event Processing (CEP) huge input event streams are processed to interpret specific situations in real time. In the field of parallel CEP the event stream is split into different windows which can be processed in parallel by several operator instances. This paradigm reduces the load imposed on a single operator instance and allows for horizontal scalability. However, in case of high load, the operator instances may not be able to process the incoming events in time; the unprocessed events are queued up resulting in a higher processing latency. In such situations it can be desirable to impose a latency bound on the system. One way to satisfy the given latency bound, is to do load shedding by dropping incoming windows. This problem is not trivial, as it is unclear when, which and how many windows need to be dropped. To answer these questions we try to find out the most promising windows, e.g. windows which may yield a high amount of complex events, yet impose a low impact on processing time. However, this adds additional challenges, as the processing latency of a window depends on many unknown variables, such as the size of the window, the types of incoming events, the position of these events relative to each other and even on the processing latency of other overlapping windows. Furthermore, even if the quality and processing latency of a window is determined, there are several open questions regarding the timing and frequency of load shedding in order to not violate the latency bound, but still keep enough windows active. In the scope of this thesis, we introduce a latency and quality model to estimate the processing latency a window induces. Based on this model, we propose an algorithm which decides the windows to drop in case of high system load to satisfy a given latency bound while minimizing the loss of quality.

Beim Complex Event Processing werden große Datenströme verarbeitet, um daraus bestimmte Situationen in Echtzeit herzuleiten - sogenannte komplexe Ereignisse. Beim Distributed Complex Event Processing wird der Datenstrom in separate Fenster unterteilt, die dann parallel von verschiedenen Operatoren verarbeitet werden. Dieses Paradigma dient dazu, die Last auf einem einzelnen Operator zu reduzieren und ermöglicht dadurch horizontale Skalierbarkeit. Im Falle von hoher Last in kurzer Zeit, kann es jedoch dazu kommen, dass die Operatoren die Ereignisströme nicht in hinnehmbarer Zeit abarbeiten können. In solchen Situationen kann es sinnvoll sein, eine Latenz-Obergrenze zu definieren, die das System erfüllen muss. Eine Möglichkeit diese Latenz-Obergrenze zu gewährleisten ist mit Lastabwurf - das abwerfen von ganzen Fenstern. Dieses Problem ist nicht trivial, da es nicht klar ist, welche und wie viele Fenster abgeworfen werden müssen. Um diese Frage zu beantworten, versuchen wir die aussichtsreichsten Fenster zu finden, also die Fenster welche am ehesten komplexe Ereignisse detektieren und welche am wenigsten Last erzeugen. Dies erzeugt jedoch weitere Herausforderungen, da die Last und Qualität eines Fensters von vielen unterschiedlichen Faktoren abhängt, die teils unbekannt sind. Beispielsweise die Größe eines Fensters, die Typen der einkommenden Ereignisse, die Positionen der Ereignisse relativ zueinander und die Last eines Fensters. Selbst wenn diese Faktoren klar wären, stünde noch die Frage, welche und wie oft Fenster abgeworfen werden müssen, um die Latenz-Obergrenze zu erfüllen. Im Umfang dieser Arbeit stellen wir eine Methode zur Bewertung von Fenster vor. Mithilfe dieser Methode zeigen wir einen Algorithmus, welcher entscheidet, welche Fenster im Falle von hoher Last abgeworfen werden sollen, um einen möglichst geringen Verlust von komplexen Ereignissen in Kauf zu nehmen.