Distributed computing on event-sourced graphs

Abstract

Modern applications with increasingly connected domain topologies require processing and programming abstractions that reflect the network structure inherent to these applications. At the same time, data-intensive applications necessitate more and more online processing capabilities when consuming incoming streams of events to execute continuous computations and provide fast results. Only very few systems have taken into account the combined challenge of executing graph processing on a dynamically evolving graph. However, this is a critical capability as timely computations enable reactive application behaviors upon graph changes. In addition, no existing system supports processing on a live graph and on past version of that evolving graph at the same time.

The distinct characteristics of event processing and graph computing, as well as batch processing and live processing yield specific requirements for any computing platform that unifies these approaches. Solutions require (i) data management strategies to keep track of the continuous graph evolution, (ii) appropriate graph processing models that can simultaneously handle computations and graph updates, and (iii) an efficient platform implementation that provides the necessary performance at runtime.

To this end, this thesis suggests a combination of an adapted actor model, an event-sourced persistence layer, and a vertex-based, asynchronous live programming model. The event-sourced actor model enables highly concurrent computations in which the full application history is implicitly persisted. This model is then refined into a live graph processing model with a particular focus on asynchronicity, liveness, and parallel execution support. At the same time, the use of event sourcing enables the model to reconstruct global and consistent graph representations from arbitrary points of the timeline. These graph representations form the basis for decoupled, non-live graph processing models.

The Chronograph platform represents an implementation of the event-sourced graph model. The platform ingests external update streams and maintains a live graph representation as part of a user-specified graph application. It thus enables live and offline computations on event-driven, history-aware graphs and supports different processing models on the evolving graph.

This thesis provides the following contributions: (i) a distributed computing approach with history support based on the actor model and event sourcing, as wall as corresponding and supplementary concepts, (ii) a data management approach for evolving graphs that builds on the event-sourced actor model, (iii) a set of novel and adapted programming and processing models that integrate well with event-sourced graphs, (iv) a distributed platform architecture that implements the event-sourced graph model; and (v) an evaluation framework for such live graph processing systems.

Moderne Software-Systeme bilden immer komplexere Szenarien mit zunehmend vernetzteren Anwendungsdaten ab. Dies erfordert neue Verabreitungsmodelle, welche die Vernetzung der Daten miteinbezieht. Gleichzeitig erfordern datenintensive Anwendungen vermehrt eine echtzeitnahe Verarbeitung, um auf eingehenden Datenströmen kontinuierliche Berechnungen mit zeitnahen Berechnungen durchzuführen. Kaum ein System erlaubt bisher die Kombination beider Ansätze – kontinuierliche Berechnungen auf Graphen, die sich zugleich auf Basis von externen Ereignisströmen verändern. Dies ist jedoch eine wichtige Fähigkeit, wenn Anwendungen kontinuierlich auf dynamischen Graphen operieren und auf Veränderungen reagieren müssen. Zudem unterstützt keines der existierenden Systeme sowohl Berechnungen auf dem Live-Graph als auch auf älteren Versionen des Graphs.

Ein solches System muss einerseits die Anforderungen von Event Processing und Graph Processing gegeneinander abwägen, als auch die Konzepte echtzeitnaher und stapelbasierter Berechnungen zusammenführen. Dies erfordert (i) Datenverwaltungsstrategien zur Verfolgung des sich entwickelnden Graphs, (ii) angemessene Ausführungsmodelle, die gleichzeitig Berechnungen und Graph-Änderungen verarbeiten können sowie (iii) eine Implementierung der Plattform, die zur Laufzeit die erforderliche Leistung bereitstellt.

In dieser Arbeit wird die Kombination des Aktor-Modells, Event Sourcing, sowie einem vertex-basierten, asynchronen Programmiermodell vorgeschlagen. Das resultierende Modell ermöglicht ermöglicht hochgradig parallele Berechnungen bei gleichzeitiger Persisitierung der vollständingen Zustandshistorie de Aktoren. Dieses Modell dient als Grundlage für ein darauf aufbauendes Verarbeitungsmodell für Graphen mit besonderem Schwerpunkt auf Asynchronität, Reaktionsvermögen und Unterstützung der parallelen Ausführung. Gleichzeitig ermöglicht der Einsatz von Event Sourcing die konsistente und globale Rekonstruktion beliebiger Graph-Zustände aus der Zeitleiste, welche als Grundlage für weitere, entkoppelte Berechnungen.

Chronograph implementiert als Plattform das konzeptuelle Modell und führt benutzerdefinierte Graph-Anwendungen auf sich ändernden Graphen aus. Externe Datenströme dienen dabei als Quelle für Änderungen, welche vom System direkt eingepflegt werden. Chronograph unterstützt gleichzeitig verschiedene Berechnungsmodelle, sowohl auf dem Live-Graphen, als auch auf älteren Graph-Versionen.

Diese Arbeit bietet die folgenden Beiträge: (i) ein Konzept für verteilte, persistierte Berechnungen auf Basis des Aktor-Modells und Event Sourcing, (ii) ein darauf aufbauender Data-Management-Ansatz für sich ändernde Graphen, (iii) eine Reihe von neuartigen und darauf angepassten Programmier- und Verarbeitungsmodellen für Graphen, (iv) eine verteilte Plattformarchitektur, die das konzeptuelle Modell implementiert und (v) ein Framework zur Evaluation solcher Systeme.