Dokument: Schnelle parallele Fehlererholung in verteilten In-Memory Key-Value Systemen

Titel:	Schnelle parallele Fehlererholung in verteilten In-Memory Key-Value Systemen
Weiterer Titel:	Fast Parallel Crash Recovery in Distributed In-Memory Key-Value Stores
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=48474
URN (NBN):	urn:nbn:de:hbz:061-20190415-091904-4
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Beineke, Kevin [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 18,03 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 03.02.2019 / geändert 03.02.2019
Beitragende:	Prof. Dr. Schöttner, Michael [Gutachter] Prof. Dr. Mauve, Martin [Gutachter]
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Big-Data-Analysen und große interaktive Graphanwendungen erfordern Datenzugriffe mit niedriger Latenz und hohem Durchsatz für Milliarden bis Billionen von zumeist kleinen Datenobjekten. Verteilte In-Memory-Systeme bewältigen diese Herausforderung, indem sie alle Datenobjekte im Arbeitsspeicher halten und Hunderte bis Tausende von handelsüblichen Servern, mit jeweils 128 GB bis 1024 GB Arbeitsspeicher, in Clustern oder in der Cloud aggregieren. Diese Arbeit befasst sich mit zwei grundsätzliche Forschungsherausforderungen von großen verteilten In-Memory-Systemen: (1) schnelle Wiederherstellung ausgefallener Server und (2) nebenläufiges Senden/Empfangen von Netzwerknachrichten (kleine und große Nachrichten) mit hohem Durchsatz und geringer Latenz. Das Maskieren von Serverausfällen erfordert Datenreplikation. In dem vorgeschlagenen Konzept werden Daten auf entfernten Festplatten bzw. SSDs und nicht im entfernten Speicher repliziert, da Arbeitsspeicher zu teuer und flüchtig ist, was zu Datenverlusten im Falle eines Stromausfalls im Rechenzentrum führt. Für interaktive Anwendungen ist es wichtig, dass die Serverwiederherstellung sehr schnell erfolgt, d. h. die Verfügbarkeit der Objekte innerhalb von ein bis zwei Sekunden wiederhergestellt wird. Dies ist eine Herausforderung für Server, die Hunderte von Millionen oder sogar Milliarden von kleinen Datenobjekten speichern. Zusätzlich hängt die Wiederherstellungsgeschwindigkeit von vielen Hardware-Faktoren wie Festplatten-, Speicher- und Netzwerkbandbreite sowie der Rechenleistung, welche für das Laden der Objekte in den Arbeitsspeicher benötigt wird, ab. Diese Arbeit schlägt ein neuartiges Backup- und Wiederherstellungskonzept vor, das darauf basiert die Daten von einem Server auf viele Backup-Server zu replizieren, welche die Replikate in Logs auf ihren lokalen Festplatten speichern. Dies ermöglicht eine schnelle, parallele Wiederherstellung eines abgestürzten Servers durch Aggregation der Ressourcen von Backup-Servern, die jeweils einen Teil der Objekte des ausgefallenen Servers wiederherstellen. Die globale Backupverteilung ist optimiert, eine schnelle, parallele Wiederherstellung eines abgestürzten Servers zu ermöglichen und zusätzlich die Wahrscheinlichkeit eines Datenverlustes im Falle mehrerer gleichzeitiger Serverausfälle steuern zu können. Diese Arbeit schlägt außerdem einen neuen zweistufigen Logging-Ansatz und ein effizientes Epochen-basiertes Versionsmanagement vor, die beide für die Speicherung von Replikaten vieler kleiner Datenobjekte mit geringem Speicherbedarf entwickelt wurden. Die Erkennung von Serverausfällen sowie die Koordination der Wiederherstellung basiert auf einem Superpeer-Overlay-Netz. Das Konzept wird ergänzt durch eine schnelle, parallele lokale Wiederherstellung, welche für Mehrkern-Prozessoren optimiert ist und durch die parallele Ausführung die Lesezeiten von Festplatte weitestgehend verdeckt. Alle vorgeschlagenen Konzepte wurden implementiert und in das Java-basierte In-Memory-System DXRAM integriert. Die Auswertungen zeigen, dass die vorgeschlagenen Konzepte deren von modernen verteilten In-Memory Key-Value-Speichern überlegen ist. Große Experimente in der Microsoft Azure Cloud zeigen zudem, dass Server, die Hunderte von Millionen kleiner Objekte speichern, auch unter hoher Last in weniger als 2 Sekunden wiederhergestellt werden können. Die vorgeschlagene Crash-Recovery-Architektur und der Key-Value-Speicher selbst erfordern ein schnelles und hoch-paralleles Netzwerk-Subsystem, mit dem viele Threads pro Server synchron und asynchron kleine Datenobjekte gleichzeitig senden/empfangen können. Zusätzlich müssen die Datenobjekte parallel in Nachrichten serialisiert und transparent zu großen Netzwerk-Paketen aggregiert werden können, um hohe Durchsätze mit kleinen Objekten zu erzielen. Nach bestem Wissen bietet keines der für Java verfügbaren Netzwerksysteme alle diese Funktionen. Diese Arbeit schlägt ein Netzwerk-Subsystem vor, das die parallele Serialisierung von Objekten, synchrones und asynchrones Nachrichtenversenden und automatisches Verbindungsmanagement bietet. Der modulare Aufbau unterstützt verschiedene Transport-Implementierungen, die derzeit für Ethernet und InfiniBand implementiert sind. Es werden verschiedene bekannte und neuartige Techniken, wie nicht-blockierende Synchronisierung, Senden/Empfangen ohne das Kopieren von Daten, parallele De-/Serialisierung und implizites Thread-Scheduling kombiniert, um das Senden/Empfangen von Nachrichten mit niedriger Latenz bei gleichzeitig hohem Durchsatz zu ermöglichen. Die Auswertung des entwickelten Netzwerk-Subsystems zeigt eine gute Skalierbarkeit mit konstanten Latenzen und voller Sättigung des zugrundeliegenden Netzwerkes, selbst im schlimmsten Fall mit einem jeder-zu-jedem-Kommunikationsmuster, getestet mit bis zu 64 Servern in der Cloud. Das Netzwerk-Subsystem erreicht Latenzen von unter 10 µs (Umlaufzeit) inklusive Objekt-De-/Serialisierung und Duplex-Durchsatz von mehr als 10 GB/s mit FDR InfiniBand und gute Performance mit bis zu hunderten von Threads, die parallel senden und empfangen, auch bei kleinen Nachrichtengrößen (< 100 Bytes). Big data analytics and large-scale interactive graph applications require low-latency data access and high throughput for billions to trillions of mostly small data objects. Distributed in-memory systems address these challenges by storing all data objects in RAM and aggregating hundreds to thousands of servers, each providing 128 GB to 1024 GB RAM, in commodity clusters or in the cloud. This thesis addresses two main research challenges of large-scale distributed in-memory systems: (1) fast recovery of failed servers and (2) highly concurrent sending/receiving of network messages (small and large messages) with high throughput and low latency. Masking server failures requires data replication. We decided to replicate data on remote disks and not in remote memory because RAM is too expensive and volatile, resulting in data losses in case of a data center power outage. For interactive applications, it is essential that server recovery is very fast, i.e., the objects’ availability is restored within one or two seconds. This is challenging for servers storing hundreds of millions or even billions of small data objects. Additionally, the recovery performance depends on many factors like disk, memory and network bandwidth as well as processing power for reloading the storage. This thesis proposes a novel backup and recovery concept based on replicating the data of one server to many backup servers which store replicas in logs on their local disks. This allows a fast-parallel recovery of a crashed server by aggregating resources of backup servers, each recovering a fraction of the failed server’s objects. The global replica distribution is optimized to enable a fast-parallel recovery of a crashed server as well as providing additional options for tuning data loss probability in case of multiple simultaneous server failures. We also propose a new two-level logging approach and efficient epoch-based version management both designed for storing replicas of large amounts of small data objects with a low memory footprint. Server failure detection, as well as recovery coordination, is based on a superpeer overlay network complemented by a fast, parallel local recovery utilizing multiple cores and mitigating I/O limitations. All proposed concepts have been implemented and integrated into the Java-based in-memory system DXRAM. The evaluation shows that the proposed concept outperforms state-of-the-art distributed in-memory key-value stores. Large-scale experiments in the Microsoft Azure cloud show that servers storing hundreds of millions of small objects can be recovered in less than 2 seconds, even under heavy load. The proposed crash-recovery architecture and the key-value store itself require a fast and highly concurrent network subsystem enabling many threads per server to synchronously and asynchronously send/receive small data objects, concurrently serialized into messages and aggregated transparently into large network packets. To the best of our knowledge, none of the available network systems in the Java world provide all these features. This thesis proposes a network subsystem providing concurrent object serialization, synchronous and asynchronous messaging and automatic connection management. The modular design is able to support different transport implementations, currently implemented for Ethernet and InfiniBand. We combine several well-known and novel techniques, like lock-free programming, zero-copy sending/receiving, parallel de-/serialization and implicit thread scheduling, to allowlow-latency message passing while also providing high throughput. The evaluation of the developed network subsystem shows good scalability with constant latencies and full saturation of the underlying interconnect, even in a worst-case scenario with an all-to-all communication pattern, tested with up to 64 servers in the cloud. The network subsystem achieves latencies of sub 10 µs (round-trip) including object de-/serialization and duplex throughputs of more than 10 GB/s with FDR InfiniBand and good performance with up to hundreds of threads sending/receiving in parallel, even with small messages (< 100 bytes).
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Betriebssysteme
Dokument erstellt am:	15.04.2019
Dateien geändert am:	15.04.2019
Promotionsantrag am:	26.07.2018
Datum der Promotion:	17.12.2018