The Influence of Load Shedding on the Stream Quality in CEP Applications

Abstract

Both the Digitalisation and Industry 4.0 result in continuous data streams in all areas of life. To get high-level information out of these streams in real-time, we can use Complex Event Processing (CEP) and Stream Processing (SP). This is often done on several operator nodes on different sites. Each of these operators works on a fraction of the whole information gathering process. There are different types of operators for different tasks. The most important for this work are the propositional logic operator, the pattern-finding operator, and the average-building operator. The operators are organized in a directed acyclic graph, called the operator graph. Often the operator graph has to deal with great amounts of continuously incoming data. The data is bundled in discrete events. We can use load shedding to reduce the workload and to ensure that the operators process incoming data quickly. Load shedding removes some of the events from the waiting queue at an operator. As such it leads to lower latency and workload. But it can also lower the accuracy of the found information. Most publications on load shedding in CEP or stream processing examine, how to make good load shedders. But in this work, we examine how inaccuracies caused by load shedding propagate through the operator graph. This means how load shedding at a preceding operator can influence the current operator. We examine which operator types can potentially repair the inaccuracies in the data stream caused by prior load shedding. That means that the data stream is more accurate after the operator than it was before. As a baseline for comparison, we take a run of the same scenario without load shedding. To do this, we created a Java program that can simulate CEP and stream processing for different scenarios, using different operator types. For the experiment, we apply load shedding to the operators in the operator graphs of the different scenarios. In the evaluation, we explain how and why load shedding affects the different operator types in the way it does. We give guidelines on how to optimally shed load for each operator type. If the propositional logic operator has an input event type that is the limiting factor it reacts well to load shedding of the non-limiting factor. If the limiting factor is greatly outnumbered, this operator type can even repair the accuracy of the data stream. The accuracy of the pattern-finding operator is very negatively affected by load shedding, if we shed whole input events. If at some point in the operator graph we can shed load in such a way that only the attributes of the input events of the pattern-finding operator are altered, the resulting accuracy is much better. This could happen if we e.g. aggregate events prior to the pattern-finding operator. There is no potential here to improve the accuracy of the data stream. The average-building operator has very high accuracy when we use load shedding. We need to do the load shedding in a way that we shed all input data for the average-building operator proportionally. If that is the case the accuracy remains on average at 100%. There is only a small variance for higher load shedding drop rates. This operator type can, therefore, repair a prior loss of accuracy of the data stream almost entirely.

Die Digitalisierung und Industrie 4.0 sorgen für kontinuierliche Datenströme in allen Lebensbereichen. Um Informationen aus diesen Streams in Echtzeit zu erhalten, können wir Complex Event Processing (CEP) und Stream Processing verwenden. Dies geschieht häufig an mehreren Operator-Knoten an verschiedenen Standorten. Jeder dieser Operatoren bearbeitet einen Bruchteil des gesamten Informationserfassungsprozesses. Es gibt unterschiedliche Typen von Operatoren für verschiedene Aufgaben. Die wichtigsten Typen für diese Arbeit sind der Aussagenlogik-Operator, der Musterfindungsoperator und der Durchschnittsbildungsoperator. Die Operatoren sind in einem gerichteten azyklischen Graphen organisiert, der als Operatorgraph bezeichnet wird. Oft muss der Operatorgraph mit großen Mengen kontinuierlich eingehender Daten umgehen. Die Daten werden oft in diskreten Events gebündelt. Mit Load-Shedding können wir den Arbeitsaufwand reduzieren und sicherstellen, dass die Operatoren eingehende Daten schnell verarbeiten. Durch das Load-Shedding werden einige Events aus der Warteschlange eines Operators entfernt. Dies führt zu einer geringeren Latenz und Arbeitsbelastung. Es kann aber auch die Genauigkeit der gefundenen Informationen verringern. In den meisten Veröffentlichungen zum Load-Shedding in CEP oder Stream Processing wird untersucht, wie man gute Load-Shedder herstellt. In dieser Arbeit untersuchen wir jedoch, wie sich durch Lastabwurf verursachte Ungenauigkeiten im Operatorgraphen ausbreiten. Das bedeutet, wie ein Load-Shedding bei einem vorhergehenden Operator den aktuellen Operator beeinflussen kann. Wir untersuchen, welche Operatortypen möglicherweise die Ungenauigkeiten im Datenstrom beheben können, die durch vorheriges Load-Shedding verursacht wurden. Das heißt, dass der Datenstrom nach dem Operator genauer ist als zuvor. Als Vergleichsbasis nehmen wir genau das gleiche Szenario ohne Load-Shedding. Zu diesem Zweck haben wir ein Java-Programm erstellt, das CEP und Stream Processing für verschiedene Szenarien unter Verwendung verschiedener Operatortypen simulieren kann. Für das Experiment wenden wir Load-Shedding auf die Operatoren in den Operatorgraphen der verschiedenen Szenarien an. In der Auswertung erklären wir, wie und warum sich das Load-Shedding auf die verschiedenen Operatortypen auswirkt. Wir geben Richtlinien an, wie die Load-Shedding für jeden Operatortyp optimal betrieben werden kann. Hat ein Aussagenlogik-Operator einen Event-Typ, der der begrenzende Faktor ist, reagiert er gut auf das Abwerfen des nicht begrenzenden Faktors. Wenn der begrenzende Faktor stark in der Unterzahl ist, kann dieser Operatortyp sogar die Genauigkeit des Datenstroms reparieren. Die Genauigkeit des Musterfindungsoperators wird durch den Load-Shedding sehr negativ beeinflusst, wenn ganze Input-Events abgeworfen werden. Wenn wir an einer Stelle im Operatorgraphen die Last so reduzieren können, dass nur die Attribute der Input-Events des Mustersuchoperators geändert werden, ist die resultierende Genauigkeit viel besser. Das kann z.B. geschehen, wenn wir vor dem Musterfindungsoperators Events aggregieren. Hier gibt es kein Potenzial, die Genauigkeit des Datenstroms zu verbessern. Der Durchschnittsbildungsoperator hat eine sehr hohe Genauigkeit, wenn wir den Load-Shedding verwenden. Wir müssen das Load-Shedding so durchführen, dass wir alle Input-Events für den Durchschnittsbildungsoperator proportional abwerfen. In diesem Fall bleibt die Genauigkeit im Durchschnitt bei 100%. Es gibt nur eine geringe Varianz für höhere Load-Shedding-Raten. Dieser Operatortyp kann daher einen vorherigen Genauigkeitsverlust des Datenstroms nahezu vollständig beheben.