TU Darmstadt / ULB / TUprints

Event Correlation with Algebraic Effects - Theory, Design and Implementation

Bračevac, Oliver (2019)
Event Correlation with Algebraic Effects - Theory, Design and Implementation.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text (PDF)
DissertationBracevac05112019.pdf - Published Version
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (4MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Event Correlation with Algebraic Effects - Theory, Design and Implementation
Language: English
Referees: Mezini, Prof. Dr. Mira ; Sam, Dr. Lindley
Date: 5 November 2019
Place of Publication: Darmstadt
Date of oral examination: 13 September 2019
Abstract:

Modern software systems are increasingly becoming distributed, reactive, and data intensive. In this context, events are an essential abstraction for representing and communicating interesting situations, enabling loosely-coupled and scalable systems. An integral part of these systems is event correlation, which is about computing relations between observed event notifications in space and time, e.g., to programmatically reason about the state of the system, for reacting to changes, for synchronization, for coordination or data processing.

The importance of event correlation is witnessed by the considerable attention it has received from different research communities, under different names. This has led to the emergence of different "families" of event correlation approaches with a sheer staggering amount of specialized correlation semantics and software abstractions. We distinguish between four families: complex event processing, stream processing, reactive programming, and concurrent programming.

We face a rather dire state of affairs: Existing event correlation approaches lack clarity, and most of them are not designed to be customizable or composable. Software systems evolve and their requirements change over time. Yet, no single approach is sufficiently adaptable to meet all requirements. We lack appropriate conceptual models and software abstractions that enable modular, extensible and cross-cutting compositions of features among the different event correlation families, fostering customizability and adaptability.

It is time for a new generation of unifying, highly adaptable and customizable reactive software systems, by means of event correlation "à la carte". That is, we need language designs for event correlation that can express features from all families in a uniform, extensible and freely composable manner.

This thesis makes event correlation "à la carte" a reality. We solve this issue by principled application of functional programming, in particular algebraic effects and effect handlers, which are a modern take on integrating side effects into functional languages in a modular and extensible way. The main statement of the thesis is that algebraic effects and effect handlers are a good programming abstraction for obtaining principled, versatile event correlation systems.

To validate the thesis, we develop Cartesius, the first computational model that captures the essence of event correlation. It has an extensible and customiz- able semantics based on algebraic effects and effect handlers. We view instances of event correlation as cartesian products over streams of events, where user-defined effect handlers locally customize the control flow of the computation to obtain semantic variants that behave differently. Handlers compose freely and new kinds of correlation features can be added by introducing new user-defined side effects.

Furthermore, we complement Cartesius with PolyJoin, which is an extensible programming language integration of declarative frontend syntax for event correlation systems. It can be deployed independently of Cartesius to provide a type-safe frontend for other event correlation systems in a programming language and subsumes mainstream language-integrated query techniques.

To evaluate our approach, we conduct a survey, comparing the expressivity of Cartesius against representative systems from the above event correlation families. Our findings demonstrate that Cartesius captures the essence of other system's features and is fully customizable and adaptable, to a degree none of the surveyed event correlation approaches offer. Additionally, we evaluate the performance of our approach in terms of synthetic microbenchmarks on common event correlation variants. The benchmarks demonstrate that despite the modular decomposition into an expensive cartesian product and user-defined extensions, Cartesius' design is practical and achieves characteristic time and space complexity of the considered event correlation variants.

Our "à la carte" approach based on algebraic effects and handlers exhibits a degree of unification, fine-grained customization and hybridization that no previous work on event correlation has attained.

Alternative Abstract:
Alternative AbstractLanguage

Moderne Softwaresysteme werden immer verteilter, reaktiver und datenintensiver. In diesem Zusammenhang sind Ereignisse eine wesentliche Abstraktion für die Repräsentation und Kommunikation von interessanten Situationen, die lose gekoppelte und skalierbare Systeme ermöglichen. Ein integraler Bestandteil dieser Systeme ist die Ereigniskorrelation, d. h., die Berechnung von Beziehungen zwischen Ereignisbenachrichtigungen in Raum und Zeit. Zum Beispiel wird dies zur programmatischen Inferenz des Systemzustands, zur Reaktion auf Änderungen, zur Synchronisation, zur Koordination oder zur Datenverarbeitung genutzt.

Die Bedeutung der Ereigniskorrelation wird durch die beachtliche Aufmerksamkeit belegt, die sie bisher durch unterschiedliche Forschungsgemeinschaften erhielt, teilweise unter anderen Namen geführt. Dies hatte zufolge, dass verschiedene Arten von "Familien" von Ereigniskorrelationsansätzen enstanden sind, jeweils mit einer schier unglaublichen Menge an spezialisierten Korrelationssemantiken und Softwareabstraktionen. Wir unterscheiden zwischen vier Familien: komplexe Ereignisverarbeitung, Datenstrom-Verarbeitung, reaktive Programmierung und nebenläufige Programmierung.

Der Ist-Zustand im Bereich der Ereigniskorrelation ist inakzeptabel: Bestehende Ansätze zur Ereigniskorrelation haben eine unklare Semantik, und die meisten von ihnen sind weder auf Anpassbarkeit noch Komponierbarkeit ausgelegt. Softwaresysteme entwickeln sich ständig weiter und ändern ihre Anforderungen im Laufe der Zeit. Jedoch ist kein einziger Ansatz ausreichend anpassungsfähig, um alle Anforderungen zu erfüllen. Wir haben keine geeigneten mentalen Modelle und Softwareabstraktionen für modulare, erweiterbare und familienübergreifende Kompositionen von Funktionalitäten und Merkmalen aus den bestehenden Familien der Ereigniskorrelation. Dieser Zustand erschwert die Anpassbarkeit und Veränderbarkeit von reaktiven Softwaresystemen.

Es ist Zeit für eine neue Generation vereinheitlichter, hoch anpassungsfähiger und veränderbarer reaktiver Softwaresysteme. Sie muss Ereigniskorrelation "à la carte" beherrschen können. Das heißt, wir brauchen Programmiersprachenkonzepte, die Funktionalität und Merkmale aus allen Familien der Ereigniskorrelation in einer einheitlichen, erweiterbaren und frei komponierbaren Form ausdrücken können.

Mit der vorliegenden Arbeit wird die Ereigniskorrelation "à la carte" zur Realität. Wir lösen dieses Problem mithilfe von Prinzipien der funktionalen Programmierung, insbesondere algebraischer Effekte und Effektbehandler. Diese sind eine moderne Form der Modellierung und Integration von Seiteneffekten in funktionale Programmierprachen und stellen hierfür einen modularen und erweiterbaren Ansatz bereit. Die Hauptthese dieser Arbeit ist, dass algebraische Effekte und Effektbehandler eine gute Programmierabstraktion sind, mit deren Hilfe fundierte und vielseitige Ereigniskorrelationssysteme konzipiert werden können.

Um die These zu validieren, entwickeln wir Cartesius, das erste Berechnungsmodell, das die Essenz der Ereigniskorrelation erfasst. Es verfügt über eine erweiterbare und anpassbare Semantik, die auf algebraischen Effekten und Effektbehandlern basiert. Wir betrachten Ereigniskorrelationen als kartesische Produkte über Datenströme von Ereignissen, bei denen benutzerdefinierte Effektbehandler den Kontrollfluss der Berechnung lokal anpassen, um semantische Varianten zu erhalten, die sich anders verhalten. Effektbehandler sind enschränkungslos komponierbar und neuartige Korrelationsfunktionalität kann durch die Einführung weiterer benutzerdefinierter Seiteneffekte hinzugefügt werden.

Darüber hinaus ergänzen wir Cartesius mit PolyJoin, einer erweiterbaren Programmiersprachenintegration von deklarativer Spezifikationssyntax für Ereigniskorrelationssysteme. PolyJoin kann unabhängig von Cartesius verwendet werden für eine typsichere Programmiersprachenintegration anderer Ereigniskorrelationssysteme. PolyJoin subsumiert vorherrschende Techniken zur Programmiersprachenintegration.

Um unseren Ansatz zu evaluieren, führen wir eine Erhebung durch, in der wir die Ausdrucksstärke von Cartesius durch Vergleichen mit repräsentativen Systemen aus den oben genannten Ereigniskorrelationsfamilien untersuchen. Unsere Ergebnisse zeigen, dass Cartesius die Essenz der Funktionalitäten aller anderen Ereigniskorrelationsansätze adäquat erfasst. Es ist wesentlich veränderbarer und anpassbarer als alle untersuchten Ansätze. Zusätzlich evaluieren wir die Leistungsfähigkeit unseres Ansatzes mithilfe synthetischer Mikrobenchmarks, in denen wir häufig genutzte Ereigniskorrelationsvarianten in Cartesius modellieren und messen. Die Messresultate zeigen, dass der Entwurf von Cartesius praktikabel ist, trotz der modularen Zerlegung in ein rechenintensives kartesisches Produkt und benutzerdefinierte Erweiterungen. Wir erreichen eine charakteristische zeitliche und räumliche Komplexität der betrachteten Ereigniskorrelationsvarianten.

Unser "à la carte" Ansatz, der auf algebraischen Effekten und Effektbehandlern basiert, weist einen hohen Grad an Uniformität, Anpassungsfähigkeit und Hybridisierung auf, die keine vorherige Arbeit zur Ereigniskorrelation in dieser Form erreicht hat.

German
URN: urn:nbn:de:tuda-tuprints-92588
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science > Software Technology
Date Deposited: 21 Nov 2019 12:53
Last Modified: 09 Jul 2020 02:49
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/9258
PPN: 455956790
Export:
Actions (login required)
View Item View Item