title: Robust Stream Indexing
title: Robust Stream Indexing
titleType: AlternativeTitle
Creators: name: Glombiewski, Nikolaus
Publisher: name: Philipps-Universität Marburg
Year: 2023
Subjects: Data Stream Index
Datenverarbeitung
Datenstrom
Robustheit von Performance
Datenstrom Index
Zeitliches Datenbanksystem
Event Stream Processing
Datenbank Index
Datenbanksystem
Ereignisstromverarbeitung
Datenstrommanagementsystem
Informatik
Data processing Computer science
Database Index
Robustness of Performance

description: Kontinuierliche Datenströme stehen im Zentrum von vielen anspruchsvollen und komplexen Anwendungen.
Neben der Online-Verarbeitung durch ein Datenstromsystem müssen Datenströme auch langfristig in einer Datenbank gespeichert werden. Moderne Hardware kann Datenströme meist mit sehr hohem Durchsatz und geringer Latenz persistieren. Allerdings müssen Teile des Datenstroms auch effizient abgerufen werden können, um Wissen aus den Daten zu extrahieren. Jahrzehntelange Forschung hat zu einer unglaublichen Vielfalt an Indexstrukturen geführt, die für viele spezifische Anwendungen Anfragekosten reduzieren können. 
Obwohl die Effizienz von Datenstrom-Indexstrukturen erheblich verbessert wurde, ist die Steigerung ihrer Robustheit nach wie vor eine große Herausforderung, da das kontinuierliche Eintreffen von Daten eine ständige Wartung von Indexstrukturen zur Folge hat. Diese Wartung verbraucht Ressourcen, was zu einer geringeren oder schwankenden Leistung von regulären Einfüge- und Anfrageoperationen führt. Eine Steigerung der Robustheit kann die Betriebskosten erheblich senken und die Benutzbarkeit verbessern. Das Hauptziel dieser Arbeit ist daher, die Robustheit von Datenstrom-Indexierung zu verbessern.

B-Bäume sind gut erforschte und weit verbreitete Indexstrukturen. Da sie ein zentraler Bestandteil vieler Datenbanksysteme sind, hat die Verbesserung der Robustheit von B-Bäumen eine weitreichende Wirkung. Wenn kontinuierlich neue Daten in B-Bäume eingefügt werden, kommt es zur Aufspaltung von Knoten. Für einen durch Bulk-Loading neu erstellten B-Baum treten diese Aufspaltung in Wellen auf, welche sich auf Einfügeoperation und Anfragen auswirken. In dieser Arbeit wird gezeigt, dass durch Anpassungen an Bulk-Loading-Algorithmen diese Wellen reduziert oder eliminiert werden können.

Auf Datenströme optimierte Indexstrukturen, wie Log-Structured Merge-Trees, vermeiden Wellen von Knotenaufspaltungen, die in B-Bäumen auftreten. Da diese Indexstrukturen jedoch aus mehreren Komponenten bestehen, müssen die Komponenten durch eine Merge-Operation zusammengeführt werden, um Anfragekosten gering zu halten. Dies führt zu periodisch auftretender Reorganisationsaktivität. Als Alternative wird in dieser Arbeit Continuous Merging vorgestellt. Die Hauptidee ist ein kontinuierlicher Mergesort-Algorithmus, der zu einer robusteren Leistung von Datenstrom-Indexierung führt.

Datenstrom-Indexstrukturen sind oft Teil eines komplexeren Datenbanksystems. ChronicleDB ist ein Ereignisdatenbanksystem, welches für das Schreiben von zeitlichen Datenströmen optimiert ist. Die Verbesserungen an B-Bäumen und Continuous Merging werden mit dem Gesamtdesign von ChronicleDB in Verbindung gebracht. Darüber hinaus werden in dieser Arbeit allgemeine Verbesserungen an ChronicleDB vorgenommen, welche die Besonderheiten von zeitlichen Daten ausnutzen. Die Ergebnisse führen zu einem robusteren Ereignisdatenbanksystem.