Hintergrund

Odysseus ist ein an der Universität Oldenburg entwickeltes Datenstrommanagementsystem, das die kontinuierliche Verarbeitung potenziell unendlicher Datenströme ermöglicht. Weitere Informationen zum System sind unter https://odysseus.uni-oldenburg.de verfügbar.

Eine kontinuierliche Anfrage in Odysseus besteht aus miteinander verbundenen Operatoren. Einige dieser Operatoren besitzen einen internen Zustand. Ein Aggregationsoperator muss beispielsweise bisher empfangene Werte verwalten, während ein Join-Operator Daten aus mehreren Eingabeströmen zwischenspeichert. In vorangegangenen Arbeiten wurden bereits Verfahren entwickelt, um die Zustände ausgewählter Operatoren persistent zu speichern und nach einem Systemausfall wiederherzustellen.

Die Wiederherstellung der Operatorzustände allein reicht für ein korrektes Recovery jedoch nicht aus. Ereignisse können zum Zeitpunkt eines Fehlers bereits vom System empfangen worden sein, ohne vollständig verarbeitet oder Bestandteil eines gespeicherten Operatorzustands zu sein. Dies betrifft insbesondere:

• Ereignisse, die von einem Zugriffsoperator empfangen, aber noch nicht an nachfolgende Operatoren weitergegeben wurden,

• Ereignisse in den Warteschlangen zwischen zwei Operatoren,

• Ereignisse, deren Verarbeitung begonnen hat, aber noch nicht durch einen konsistenten Checkpoint abgesichert wurde.

Diese Ereignisse werden bisher typischerweise in hauptspeicherbasierten Queues verwaltet und gehen bei einem Absturz verloren.

Ziel der Arbeit

Ziel der Bachelorarbeit ist die Konzeption, prototypische Implementierung und Evaluation eines persistenten Queue- beziehungsweise Replay-Mechanismus für Odysseus.

Der Mechanismus soll empfangene, aber noch nicht dauerhaft verarbeitete Ereignisse so verwalten, dass sie nach einem Systemausfall erneut bereitgestellt werden können. Gleichzeitig soll untersucht werden, zu welchem Zeitpunkt ein Ereignis als erfolgreich verarbeitet gelten und aus dem persistenten Puffer entfernt beziehungsweise als bestätigt markiert werden darf.

Die zentrale Forschungsfrage lautet:

Wie kann ein Datenstromverarbeitungssystem nach einem Fehler genau diejenigen Ereignisse erneut verarbeiten, die bereits empfangen, aber noch nicht erfolgreich und dauerhaft verarbeitet wurden?

Dabei sollen insbesondere die Auswirkungen unterschiedlicher Persistenzstrategien auf Verarbeitungslatenz, Durchsatz, Speicherbedarf und Wiederherstellungszeit untersucht werden.

Grundidee

Anstelle einer rein hauptspeicherbasierten Queue kann ein persistentes, fortlaufendes Eingabeprotokoll verwendet werden. Ein möglicher Ablauf ist:

1. Ein Ereignis wird von Odysseus empfangen.

2. Das Ereignis wird persistent in einem Eingabeprotokoll gespeichert.

3. Anschließend wird es durch den Operatorgraphen verarbeitet.

4. Der erfolgreiche Verarbeitungsstand wird durch einen persistenten Commit-Offset oder einen vergleichbaren Bestätigungsmechanismus festgehalten.

5. Nach einem Fehler wird ab der letzten bestätigten Position weitergelesen.

6. Nicht mehr benötigte Einträge können später entfernt oder überschrieben werden.

Als konzeptionelle Vorbilder können unter anderem Kafka sowie aus Datenbanksystemen bekannte Write-Ahead-Logging-Verfahren betrachtet werden. Ziel ist jedoch nicht zwingend die Integration eines externen Brokers. Untersucht werden sollen insbesondere leichtgewichtige, eingebettete Lösungen, die direkt innerhalb von Odysseus eingesetzt werden können.

Aufgabenstellung

Im Rahmen der Arbeit sollen insbesondere die folgenden Aufgaben bearbeitet werden:

• Analyse der bestehenden Verarbeitung und des bisherigen State-Managements in Odysseus

• Untersuchung der derzeit verwendeten Queues an Zugriffsoperatoren und zwischen Operatoren

• Definition eines geeigneten Fehler- und Recoverymodells

• Präzisierung der Begriffe „empfangen“, „verarbeitet“ und „dauerhaft bestätigt“

• Analyse bestehender Ansätze für persistente Queues, Logs und eingebettete Speichersysteme

• Konzeption einer einheitlichen Schnittstelle für persistente Replay-Puffer

• Entwicklung eines Verfahrens zur Verwaltung persistenter Schreib- und Commit-Positionen

• prototypische Implementierung ausgewählter Persistenzstrategien

• Integration mindestens einer Implementierung in einen ausgewählten Verarbeitungspfad von Odysseus

• Abstimmung des Queue-Recoverys mit dem bestehenden Operator-State-Management

• Entwicklung reproduzierbarer Fehler- und Recoverytests

• experimentelle Evaluation der implementierten Ansätze

Als mögliche technische Grundlagen können beispielsweise Chronicle Queue, RocksDB, MapDB oder H2 MVStore untersucht werden. Zusätzlich kann eine eigene einfache dateibasierte Write-Ahead-Log-Implementierung als Vergleich dienen. Die Auswahl und Begründung der untersuchten Ansätze ist Bestandteil der Arbeit.

Konsistenz und Verarbeitungssemantik

Ein besonderer Schwerpunkt liegt auf der Frage, wann ein Ereignis aus dem persistenten Puffer als verarbeitet markiert werden darf.

Wird ein Ereignis zu früh bestätigt, kann es nach einem Fehler verloren gehen. Wird es zu spät bestätigt, kann es während des Recoverys erneut verarbeitet werden. Die persistente Queue muss daher mit den gespeicherten Operatorzuständen beziehungsweise den Checkpoints von Odysseus abgestimmt werden.

Im Rahmen der Arbeit soll untersucht werden, welche Garantien mit dem entwickelten Ansatz erreicht werden können, beispielsweise:

• At-most-once-Verarbeitung,

• At-least-once-Verarbeitung,

• Vermeidung von Datenverlusten bei möglichen Duplikaten,

• Exactly-once-Verarbeitung unter klar definierten Voraussetzungen.

Eine vollständige End-to-End-Exactly-once-Garantie für beliebige externe Quellen und Senken ist nicht zwingend Bestandteil der Arbeit. Die erreichbaren Garantien und ihre Voraussetzungen sollen jedoch eindeutig beschrieben und experimentell überprüft werden.

Fragestellungen

Die Arbeit soll unter anderem folgende Fragen untersuchen:

• Welche Datenstruktur eignet sich für einen persistenten Eingabe- beziehungsweise Replay-Puffer?

• Sollte ein verarbeitetes Ereignis physisch gelöscht oder lediglich durch einen Commit-Offset bestätigt werden?

• Wie können Queuezustand und Operatorzustand konsistent gemeinsam wiederhergestellt werden?

• Welche Persistenzstrategie bietet einen geeigneten Kompromiss zwischen Sicherheit und Verarbeitungsgeschwindigkeit?

• Welchen Einfluss haben synchrone Schreibzugriffe, Batching und unterschiedliche Flush-Strategien?

• Wie schnell kann der Queuezustand nach einem Systemausfall rekonstruiert werden?

• Unter welchen Bedingungen entstehen Datenverluste oder doppelt verarbeitete Ereignisse?

• Wie lassen sich nicht mehr benötigte Logsegmente effizient bereinigen?

• Inwieweit kann der entwickelte Ansatz für Zugriffsoperatoren und für Verbindungen zwischen Operatoren verwendet werden?

Evaluation

Die entwickelten Ansätze sollen mit einer bestehenden hauptspeicherbasierten Queue als Referenz verglichen werden. Mögliche Bewertungskriterien sind:

• Durchsatz bei unterschiedlichen Ereignisgrößen und Ereignisraten,

• zusätzliche Latenz durch die Persistierung,

• Hauptspeicher- und Massenspeicherbedarf,

• Start- und Wiederherstellungszeit,

• Verhalten bei kontrolliert ausgelösten Systemabbrüchen,

• Anzahl verlorener oder doppelt verarbeiteter Ereignisse,

• Einfluss unterschiedlicher Flush- und Commit-Strategien,

• Verhalten bei längerem Rückstau.

Für die Evaluation sollen reproduzierbare Fehlerszenarien entwickelt werden, bei denen Odysseus zu unterschiedlichen Zeitpunkten während der Verarbeitung beendet und anschließend wiederhergestellt wird.

Abgrenzung

Im Mittelpunkt der Arbeit steht die persistente Verwaltung von Ereignissen, die bereits empfangen, aber noch nicht durch einen konsistent gespeicherten Verarbeitungsstand abgesichert wurden.

Nicht erforderlich sind:

• die Entwicklung eines vollständigen verteilten Log- oder Brokersystems,

• die Nachimplementierung von Kafka,

• die persistente Umsetzung sämtlicher Queuearten innerhalb von Odysseus,

• eine vollständige Exactly-once-Garantie für beliebige externe Systeme,

• die Anpassung sämtlicher existierender Operatoren.

Die Integration kann zunächst exemplarisch für einen ausgewählten Zugriffsoperator oder einen klar abgegrenzten Verarbeitungspfad erfolgen. Die Übertragbarkeit auf weitere Stellen innerhalb von Odysseus soll konzeptionell untersucht werden.

Erwartete Ergebnisse

Am Ende der Arbeit sollen vorliegen:

• eine Analyse bestehender Queue-, Logging- und Replay-Ansätze,

• ein definiertes Fehler-, Persistenz- und Recoverymodell,

• eine einheitliche Abstraktion für persistente Replay-Puffer,

• prototypische Implementierungen ausgewählter Speicherstrategien,

• eine Integration in einen exemplarischen Verarbeitungspfad von Odysseus,

• automatisierte Tests für Fehler- und Recoveryfälle,

• eine experimentelle Evaluation der Ansätze,

• eine Dokumentation der Architektur, Implementierung und erreichbaren Verarbeitungsgarantien.

Voraussetzungen

Hilfreich sind Kenntnisse oder Interesse in folgenden Bereichen:

• Programmierung mit Java,

• Datenstrukturen und nebenläufige Programmierung,

• Grundlagen von Datenbank- und Speichersystemen,

• Dateizugriffe und Persistenzmechanismen,

• Softwaretests und experimentelle Evaluation,

• Interesse an Datenstromverarbeitung und fehlertoleranten Systemen.

Kenntnisse über Odysseus werden nicht vorausgesetzt und können im Rahmen der Arbeit erworben werden.