Adaptability in distributed stream processing : implementation and evaluation using ESC

Abstract

Die Verarbeitung von großen Datenbeständen wird in der Regel mithilfe eines Batch-Verfahrens durchgeführt. Wenn jedoch die Verarbeitung von Datenströmen und Events in Echtzeit erforderlich ist, und das Volumen der ankommenden Daten hohen Fluktuationen unterliegt, können diese Batch-Verfahren nicht mehr angewendet werden.<br />Um diesen Anforderungen zu begegnen, wurden verschiedene Systeme zur Verarbeitung von Datenströmen entwickelt. Eines dieser Systeme ist ESC, ein cloud-basiertes System zur Durchführung von Echtzeit-Berechnungen auf Datenströmen geschrieben in Erlang. Da die zur Berechnung erforderlichen Ressourcen ständigen Veränderungen unterliegen, ist ESC in der Lange, durch automatisches Hinzufügen oder Entfernen von Netzknoten zu skalieren.<br />Die dafür notwendigen Informationen werden den Informationen zur Arbeitslast der zugrunde liegenden Maschinen entnommen.<br />Jedoch ist dieses Vorgehen alleine für die Verhinderung einer Überbelastung eines Netzknotens, aufgrund von stoßweise ankommenden Daten oder aufgrund von intensiven Berechnungen, nicht ausreichend. Eine Adaptionstechnik ist erforderlich, welche, auf der einen Seite, eine nicht ausbalancierte Lastverteilung erkennen kann und in der Lage ist, Gegenmaßnahmen zu treffen.<br />Sowie, auf der anderen Seite, intelligente Strategien zur Platzierung von Operatoren auf Netzknoten nutzt, so dass die Wahrscheinlichkeit einer Überlastung deutlich reduziert wird.<br />Die Platzierung von Operatoren auf Netzknoten lässt sich in zwei separate Problemstellungen aufteilen. Zunächst ist die Frage zu beantworten, auf welchem Netzknoten ein Operator erzeugt werden soll. Diesbezüglich wurden drei unterschiedliche Strategien implementiert und analysiert. Dazu gehören die zufällige Zuordnung von Operatoren auf Netzknoten, die Erstellung von Operatoren auf dem am wenigsten ausgelasteten Netzknoten, sowie die Zuordnung eines Operatoren zu einem Netzknoten auf der Basis des eindeutigen Namens des Operators, als auch unter Einbeziehung des Graphen zum aktuell ausgeführten Szenario.<br />Weiterhin wird eine Strategie benötigt, welche eine Entscheidung trifft, wann und wohin Operatoren zu bewegen sind, um eine balancierte Lastverteilung innerhalb des Netzwerks herzustellen. Daher wurden zwei verschiedene Strategien implementiert und analysiert.<br />Die erste Strategie balanciert die Lastverteilung durch die Verschiebung von zufällig ausgewählten Operatoren von Netzknoten mit hoher Last, zu Netzknoten mit geringer Last.<br />Zusätzlich dazu wurde eine zweite Strategie entwickelt, welche den Hauptfokus dieser Arbeit bildet.<br />Dieser Ansatz wurde abgeleitet von einer bereits existierenden Lösung zu dem Problem der Zuordnung von Aufgaben zu Prozessoren zur Laufzeit, bekannt unter dem Namen Particles Approach.<br />Demzufolge wurde der vorhandene Algorithmus in das Umfeld der Datenstrom-Analyse übertragen und, wenn notwendig, angepasst, sowie dessen Effektivität analysiert.<br />

The processing of large data sets is normally done using batch-oriented approaches. However, when confronted with the processing of live data streams and events, which are usually subject to high fluctuations in terms of data arrival, these batch-oriented approaches are not applicable.<br />For addressing these kinds of processing requirements, various stream processing engines have been developed. One of these engines is ESC, a cloud based stream processing engine designed for computations with real time demands written in Erlang. In order to cope with increasing or decreasing computational needs, ESC is able to automatically scale by attaching or releasing nodes using information about the workload of the underlying machines. But, for preventing an overload of a node due to bursty data arrival or intensive computation, this approach alone is not sufficient. An adaptation technique is needed that, on the one hand, is able to identify unbalanced work distributions and take counteracting measures, and, on the other hand, is utilizing strategies of placing operators intelligently onto nodes, such that the chance of an overload situation becomes less likely.<br />The problem of mapping operators to nodes can be divided into two separate problems.<br />First of all, the question on where to place operators initially is to be answered. Therefore, three different approaches have been implemented and analyzed. These include the random mapping of operators to nodes, the creation of operators on the currently least loaded node, as well as the mapping of an operator to a node, according to its unique name and considering the logic of the currently executed scenario.<br />Secondly, a strategy is needed, which is deciding when and where to move operators between nodes, in order to establish a balanced load distribution. Hence, two different load-balancing approaches have been implemented and analyzed. The first strategy balances the load by moving random workers from nodes with a high load to nodes with a lower load.<br />In addition to that, the second strategy, which constitutes the main focus of this thesis, is derived from an existing solution to a problem of mapping tasks to processor nodes at run-time, which is called Particles Approach. Therefore, a porting of the existing algorithm has been performed into the envi- ronment of distributed stream processing systems, together with an analysis of its effectiveness.<br />In order to compare the developed concepts with each other, a benchmarking application is required. Currently, the only available benchmark for stream processing systems is Linear Road, which simulates vehicles on expressways in a large metropolitan area. The developed methods are therefore checked using the Linear Road benchmark. Observed performance gains with different approaches are compared with each other and with the results of other stream computing engines.<br />