Zum Seminar gibt es jetzt hier einen Moodle-Arbeitsraum.
Für das Blockseminar haben wir uns auf die zwei Tage 4. und 5. Dezember 2017 (Montag und Dienstag) geeinigt.
Tiefgreifende Entwicklungen der Hardwaretechnologie rütteln ganz gewaltig an etablierten Techniken der Datenbankimplementation. Hauptspeicher ist nicht mehr unbedingt eine knappe Ressource, die einzig als Cache für Festplatten verwendet wird – Rechner mit 1 TB und mehr an Hauptspeicher sind verfügbar und erschwinglich. Parallelitätsgrade mit hunderten von Prozessoren sind keine Fiktion mehr. Dazu gesellen sich ganz revolutionäre Technologien wie etwa „non-volatile memories“ – nicht-flüchtiger Speicher mit Zugriffscharakteristika ähnlich denen von DRAM – oder Netzwerke mit Hardwarebeschleunigung und extrem hoher Bandbreite.
Im Seminar wollen wir auf einige der (möglichen) Auswirkungen solcher Technologien auf Datenbankarchitekturen schauen. Ein Schwerpunkt wird dabei die Transaktionsverwaltung sein (die etwa in der Vorlesung „Data Processing on Modern Hardware“ etwas zu kurz kommt).
Die Transaktionsverwaltung in modernen Systemen ist zunächst eine große Herausforderung. Many-Core-Systeme erlauben Parallelitätsgrade und Transaktionslasten, denen klassische Ansätze (z.B. Two-Phase Locking) nicht gewachsen sind. Gleichzeitig bietet die Hardware auch neue Rettungsanker, etwa in Form großer Hauptspeicher, schneller Netzwerke oder eben auch nicht-flüchtigen Speichertechnologien. Im Seminar sollen aktuelle Forschungsarbeiten diskutiert werden, die sich dieser Herausforderungen annehmen bzw. die neuen Technologien als Lösung einzusetzen versuchen.
Grundsätzlich beinhaltet die Transaktionskontrolle zwei Komponenten. Durch Concurrency Control (Nebenläufigkeitskontrolle) wird primär die Isolation-Komponente der ACID-Eigenschaften realisiert; nebenläufige Transaktionen verhalten sich dadurch korrekt. Eine klassische Realisierung stellt zum Beispiel Two-Phase Locking (2PL) dar. In der Praxis geht die Nebenläufigkeitskontrolle oft Hand-in-Hand mit dem Problem des Recovery (Wiederherstellung im Fehlerfall), um insbesondere die Durability-Eigenschaft (aber auch Atomicity) zu garantieren. Notwendig sind dazu Mechanismen wie Redundanz oder verlässliche, nicht-flüchtige Speicher (stable storage). Bekanntester Vertreter zur Realisierung von Recovery ist das ARIES-Protokoll.
Die nachfolgende Themenliste ist noch unvollständig, soll aber einen Eindruck der Seminarinhalte geben:
In diesem Vortrag soll es darum gehen, die grundlegenden, bestehenden Techniken der Nebenläufigkeitskontrolle vorzustellen und zusammenzufassen. Im wesentlichen sind das two-phase locking (2PL) (was allerdings ja bereits in der Vorlesung diskutiert wurde) sowie multi-version concurrency control (MVCC) (der wohl interessantere Ansatz im Kontext dieses Seminars.
Die Arbeit von Wu et al. enthält einen kurzen Überblick über die grundlegenden Techniken. Für den Vortrag wird es sicherlich notwendig sein, auch noch weitere Literatur (evtl. auch Lehrbücher) mit heran zu ziehen.
Optimistische Verfahren zur Nebenläufigkeitskontrolle arbeiten ähnlich wie Systeme zur Source Code-Versionskontrolle (z.B. SVN). Transaktionen arbeiten zunächst auf lokalen Arbeitskopien der Daten; Konflikte können dabei nicht auftreten. Mit dem Commit wird zunächst eine Validierung durchgeführt um aufgetretene Konflikte zu erkennen; gegebenenfalls wird die Transaktion abgebrochen. Zuletzt werden die Ergebnisse von erfolgreichen Transaktionen in einer Schreibphase festgeschrieben.
In experimentellen Arbeiten wurde untersucht, wie sich die bestehenden Ansätze auf moderner und zukünftiger Hardware verhalten (würden).
Deuteronomy ist eine Forschungs-Prototyp, der in der Forschungsabteilung von Microsoft entwickelt wird. Im Projekt wurden zahlreiche Techniken für die Transaktionsverarbeitung entwickelt, um einerseits effizient in modernen Hauptspeichersystemen zu funktionieren; andererseits aber auch so skalieren, dass sie mit hohen Parallelitätsgraden und Verteilung umgehen können.
HyPer, entwickelt an der TU München, ist ein Hauptspeicherdatenbanksystem, das ebenfalls volle Serialisierbarkeit garantiert. Serialisierbarkeit und Effizienz werden erreicht durch eine geschickte Implementierung, die den Eigenschaften moderner Hardware Rechnung trägt.
Silo ist ein Hauptspeicherdatenbanksystem. Zur Nebenläufigkeitskontrolle verwendet es Optimistic Concurrency Control. Zusätzlich wird ein Epoch-Mechanismus eingesetzt, um die Synchronisation zwischen Threads zu minimieren.
Das klassische Zwei-Phasen-Sperrprotokoll garantiert (abgesehen vom Phantom-Problem) Serialiserbarkeit. Multi-Versions-Verfahren, insbesondere Snapshot Isolation sind effizienter, garantieren jedoch keine volle Serialisierbarkeit. Diese Lücke schließt das “Serial Safety Net (SSN)” von Wang et al.SSN überwacht die Ausführung eines Systems das z.B. Snapshot Isolation verwendet. Wird eine mögliche Verletzung der Serialiserbarkeit erkannt, werden Transaktionen abgebrochen und dadurch die Serialisierbarkeit sichergestellt.
Im TheDB-Prototyp stellen Wu et al. eine Technik vor, die auf Optimistic Concurrency Control (OCC) aufbaut. In OCC-Verfahren werden Transaktionen erst zum Ende auf mögliche Konflikte untersucht; falls notwendig, werden Transaktionen dann noch abgebrochen (und üblicherweise neu gestartet). Solche Transaktionsabbrüche können sehr teuer werden. Transaction Healing soll vollständige Abbrüche verhindern und stattdessen Transaktionen „reparieren“, sobald ein Konflikt festgestellt wurde.
Die Markteinführung von neuartigen, nicht-flüchtigen Speichermedien steht unmittelbar bevor. Sie sollen die Vorteile von RAM (schnell und byte-adressierbar) und persistenten Medien (billig und nicht-flüchtig) vereinen. Das wird den Recovery-Aspekt in der Transaktionsverarbeitung nachhaltig verändern.
Ein naheliegender Ansatz ist die Verwendung von Non-Volatile Memories zum Speichern des Write-Ahead Log. Durch die Laufzeit-Charakteristika der neuen Speichertechniken werden allerdings Engpässe in konventionellen Log-basierten Ansätzen schnell deutlich. Huang et al. haben sich dieses Problems angenommen.
Chatzistergiou et al. verwenden Non-Volatile Memory ebenfalls in Form von Write-Ahead Logging. Die Arbeit geht jedoch deutlich stärker auf Implementierungsdetails ein.
Durch ihre Laufzeiteigenschaften werden Non-Volatile Memories in der Systemarchitektur eine DRAM-ähnliche Rolle einnehmen. Neben den vielen positiven Konsequenzen bringt das allerdings auch neue Probleme mit sich, zum Beispiel wenn Memory Leaks plötzlich persistent werden. Die Arbeit von Oukid et al. diskutiert daher mögliche Techniken zur Speicherverwaltung beim Einsatz von Non-Volatile Memories.
Schwalb et al. stellen ebenfalls Techniken zur Speicherverwaltung in Non-Volatile Memories vor.
Mnemosyne kapselt den Umgang mit non-volatile memory in einer Programmierschnittstelle und stellt verschiedene Persistenzgarantien sicher.
In transaktionalen Workloads spielen B-Bäume meist eine zentrale Rolle. Im klassischen Design sind sie aber weder optimiert für die reine Verwendung im Hauptspeicher, noch für hohe Grade an Nebenläufigkeit, noch interagieren sie gut mit den Eigenheiten von tiefen Cache-Hierarchien und/oder Non-Volatile Memory-Technologien. Varianten wie Foster B-Trees oder Bw-Treessollen diese Lücke schließen.
Bw-Trees sind für hohe Nebenläufigkeit und die Verwendung im Hauptspeicher und auf Flash-Medien optimiert. Sie werden z.B. in Microsoft Hekaton eingesetzt.
Durch sehr schnelle Zugriffzeiten sind Non-Volatile Memories sensibel auf eine sorgfältige Implementierung. Hier bietet die persistent multi-word compare-and-swap-Operation eine Hilfestellung, die im Umfeld der Bw-Trees entwickelt wurde.
Reale Systeme werden meist Kombinationen aus non-volatile memory (NVM) und konventionellem DRAM anbieten. Für konventionelles DRAM bieten moderne Prozessoren hardware transactional memory (HTM) an, um Transaktionssemantik mit geringem Aufwand und ohne Sperren zu realisieren. Avni und Brown zeigen, wie man NVM und HTM kombinieren kann.
Mit FOEDUS wurde prototypisch ein System entwickelt, das den Umgang mit mehreren neuen Hardwaretechnologien vereint. Insbesondere ist FOEDUS auf Parallelisierbarkeit (viele Rechenkerne) und den Einsatz von non-volatile memories ausgelegt.
Alternativ zu persistenten Speichermedien (wie HDDs, Flash oder NVM) kann eine Wiederherstellungsmöglichkeit auch sicher gestellt werden, in dem Informationen z.B. über ein Netzwerk auf anderen Maschinen „persistent“ gespeichert werden. Damit das Netzwerk dabei nicht zum Flaschenhals wird, können dabei moderne Hardwaretechnologien – allen voran Netzwerke mit Hardwarebeschleunigung, RDMA – eingesetzt werden. Ein System, das auf dieser Idee aufbaut, ist das RAMCloud-System aus Stanford. RAMCloud bietet allerdings keine Transaktionssemantik im klassischen Datenbank-Verständnis (ACID).
FaRM setzt verteilte Commit-Protokolle in Kombination mit RDMA ein, um volle Serialisierbarkeit zu garantieren.
NAM-DB verfolgt eine ähnliche Idee with FaRM, jedoch bietet NAM-DB „nur“ Snapshot Isolation.
Eine Vorbesprechung zum Seminar wird stattfinden am Dienstag, 17. Oktober 2017, 16:15 Uhr im Raum OH14/304.
Im Rahmen der Vorbesprechung findet auch eine Themenvergabe statt. Bitte schauen Sie sich schon im Vorfeld einige der angegebenen Forschungsarbeiten an, damit Sie entsprechende Präferenzen nennen können.
Das Seminar wird als Blockseminar am 4. und 5. Dezember 2017 stattfinden.