Fast crash recovery strategies for many small data objects in a distributed memory storage Akronym: FastRecovery
Final Report Abstract
Große interaktive Graph-Anwendungen erfordern Datenzugriffe mit niedriger Latenz und hohem Durchsatz für Milliarden bis Billionen von zumeist kleinen Datenobjekten. Verteilte In-Memory-Systeme erfüllen diese Anforderungen, indem sie alle Datenobjekte im Arbeitsspeicher halten und handelsübliche Server in Clustern oder in der Cloud aggregieren. Das Hauptziel dieses Projektes war die Entwicklung von Konzepten, die eine schnelle Wiederherstellung eines ausgefallenen Servers erlauben, basierend auf einem Crash-Recovery-Fehlermodell. Hierzu werden die Daten ausschließlich auf entfernten SSDs repliziert, da eine Replikation im Hauptspeicher zu teuer ist, und zudem bei einem Stromausfall die Daten dennoch verloren wären. Für interaktive Anwendungen ist es wichtig, dass die Serverwiederherstellung sehr schnell erfolgt, d. h. die Verfügbarkeit der Datenobjekte innerhalb von ein bis zwei Sekunden wiederhergestellt wird. Dies ist eine Herausforderung für Server, die Hunderte von Millionen kleine Datenobjekte speichern. Zusätzlich hängt die Wiederherstellungsgeschwindigkeit von der Leistungsfähigkeit der verwendeten Hardware ab. Im Rahmen dieses Projekts wurde ein neuartiges Backup- und Wiederherstellungskonzept entwickelt, welches darauf basiert, die Daten von einem Server auf viele Backup-Server zu replizieren, welche die Replikate in Protokollen (eng. logs) auf ihren lokalen SSDs speichern. Hierbei wurden die speziellen Charakteristika von SSDs berücksichtigt. Dies ermöglicht eine schnelle, parallele Wiederherstellung eines abgestürzten Servers durch Aggregation der Ressourcen von Backup-Servern, die jeweils einen Teil der Datenobjekte des ausgefallenen Servers wiederherstellen. Die globale Backupverteilung ist hinsichtlich einer schnellen parallelen Wiederherstellung optimiert. Das Projekt schlägt einen neuen zweistufigen Logging-Ansatz und ein effizientes Epochen-basiertes Versionsmanagement vor. Beides ist optimiert für die effiziente Speicherung von Replikaten vieler kleiner Datenobjekte. Die Erkennung von Serverausfällen sowie die Koordination der Wiederherstellung basiert auf einem Super-Peer-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 SSDs weitestgehend maskieren kann. Alle vorgeschlagenen Konzepte wurden implementiert und in das Javabasierte In-Memory-System DXRAM (entwickelt an der Universität Düsseldorf) integriert. 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 Java-Datenobjekte parallel in Nachrichten serialisiert und transparent zu großen Netzwerk-Paketen aggregiert werden können, um hohe Durchsätze auch mit kleinen Nachrichten zu erzielen. DXRAM hatte im Bereich der Netzwerkfunktionen noch deutliches Optimierungspotential, welches sich nach den ersten großen Experimenten zeigte. Keine der verfügbaren Java-Netzwerk-Bibliotheken bieten die notwendigen Eigenschaften, weswegen eine eigene Entwicklung, genannt DXNet, notwendig war. Diese größere Abweichung vom Projektplan ermöglichte jedoch am Ende die schnelle Wiederherstellung. Die Auswertung von DXNet zeigt eine gute Skalierbarkeit mit konstanten Latenzen und voller Sättigung der zugrundeliegenden Verbindung, 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 GByte/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). Die entwickelten Logging- und Recovery-Konzepte, aufbauend auf DXNet, sind schneller als die von modernen verteilten In-Memory Key-Value-Speichern. Experimente in der Microsoft Azure Cloud belegen, dass ein Master-Server, welcher 500 Mio. kleine Datenobjekte speichert, auch unter hoher Last in weniger als 2 Sekunden wiederhergestellt werden kann. Die Ergebnisse wurden bei wissenschaftlichen Tagungen publiziert und die Implementierungen als Open-Source bei Github veröffentlicht. DXNet wird als eigenständiges Open-Source Projekt bereitgestellt, da die Netzwerk-Bibliothek unabhängig von DXRAM nützlich ist. Aufgrund der verbesserten Fehlertoleranz und Geschwindigkeit des DXRAM-Systems konnte nun damit begonnen werden, echte Graph-Anwendungen zu unterstützen; derzeit eine aus dem Bereich der Bioinformatik und eine aus den Informationswissenschaften. Wir erhoffen uns durch eine anwendungsgetriebene Weiterentwicklung eine bessere Verwertung der Forschungsergebnisse und gleichzeitig neue wissenschaftliche Fragestellungen auf der Systemseite.
Publications
- „High Throughput Log-based Replication for Many Small In-Memory Objects”, IEEE International Conference on Parallel and Distributed Systems (ICPADS 2016), Wuhan, China, December, 2016
Kevin Beineke, Stefan Nothaas, and Michael Schöttner
(See online at https://doi.org/10.1109/ICPADS.2016.0077) - „Fast Parallel Recovery of Many Small In-memory Objects“, IEEE International Conference on Parallel and Distributed Systems (ICPADS 2017), Shenzhen, China, December, 2017
Kevin Beineke, Stefan Nothaas, and Michael Schöttner
(See online at https://doi.org/10.1109/ICPADS.2017.00042) - „DXRAM’s Fault-Tolerance Mechanisms Meet High Speed I/O Devices”, Technical Report, July, 2018
Kevin Beineke, Stefan Nothaas, and Michael Schöttner
- „Efficient Messaging for Java Applications running in Data Centers“, International Workshop on Advances in High-Performance Algorithms Middleware and Applications (In Proceedings of ACM/IEEE CCGrid18), Washington, USA, May, 2018
Kevin Beineke, Stefan Nothaas, and Michael Schöttner
(See online at https://doi.org/10.1109/CCGRID.2018.00090) - „Scalable Messaging for Java-based Cloud Applications“, 14th International Conference on Networking and Services (ICNS), Nice, France, May, 2018
Kevin Beineke, Stefan Nothaas, and Michael Schöttner
