Datenmanagement in Clouds Flashcards
1
Q
Motivation & Beispiele
A
Motivation
- Allgemeiner Trend: Extreme Zunahme der zu verarbeitenden Daten
- Induziert durch Zunahme an computergestützter Datenverarbeitung und exponentieller Zunahme der Kapazität von Speichermedien bei gleichen Kosten
- Problematik: Effiziente und skalierbare Verarbeitung von Daten
- Lösungsansatz: Neue Konzepte bzw. Algorithmen für verteiltes Datenmanagement
Beispiele:
- Programmiermodelle: MapReduce/Hadoop, Dryad, Spark und Tez
- Verteilte, einfache Datenbank-ähnliche Systeme bzw. Key-Value-Stores: Dynamo, BigTable bzw. Spanner, PNUTS usw.
- Verteilte Dateisysteme: GoogleFS, HadoopFS
2
Q
MapReduce
A
Motivation von Google zur Entwicklung von MapReduce:
- Programmierung von datenlastigen Anwendungen in verteilten Systemen ist aufwendig
- Kommunikation und Koordination
- Wiederherstellung nach Ausfall eines Rechners
- Statusdaten zur Systemüberwachung und Fehlersuche
- Optimierung der Anwendung
- Programmierarbeit muss für jede Anwendung wiederholt werden
- Lösungsansatz zur Reduzierung des Programmieraufwands:
- Einfache und strukturierte Programmiermethode unterstützt durch eine Laufzeitumgebung für verteilte Systeme
3
Q
Programmiermodell Map Reduce
A
Benutzerdefinierte Funktionen
- Map-Funktion
- Transformation einer Menge von Datensätzen in eine Zwischendarstellung
- Reduce-Funktion
- Reduktion der Zwischendarstellung auf das Endergebnis
- Parametrisierung
- z. B. Festlegung des Grads der Nebenläufigkeit
- MapReduce-Aufruf
- Bereitstellung des äußeren Programmablaufs – Enthält z. B. Management der Ein- und Ausgaben
Durch das Framework definierte Funktionen
- Parallelisierung
- Fehlerbehandlung
- Aufteilung der Daten
- Lastverteilung
4
Q
Map Reduce Implementierungen
A
Technische Rahmenbedingungen bei Google (Stand: 2008)
- x86 Standardrechner
- Doppelprozessor, 4-8GB Arbeitsspeicher, Gigabit-Anbindung
- Lokale IDE-Platten verwaltet über GoogleFS
- Rechner werden in Clustern verwaltet, siehe [Barroso et al, 2003]
- Implementierung in C++
- Nicht öffentlich verfügbar
- Alternative Implementierung
- Hadoop: Open Source Implementation of MapReduce
- https://hadoop.apache.org
- Grundlage für die Übung
- Hadoop: Open Source Implementation of MapReduce
5
Q
Map Reduce Ablaufmodel
A
- Vorbereitungsphase
- Aufteilung der Eingabedaten
- Erzeugung von Kopien der Anwendung
- – Dedizierte Master-Instanz
- – Abhängige Worker-Instanzen
- Master vergibt Map- bzw. Reduce-Tasks an freie Worker
- Verarbeitung der Eingaben
- Worker liest den Inhalt aus den ihm zugewiesenen Teilbereichen der Eingabedaten
- Worker teilt den Input in die Schlüssel-Wert-Paare auf und gibt diese an die Map-Funktion
- Zwischendarstellung wird erzeugt und im Speicher gepuffert
- Sicherung und Vermittlung der Zwischenergebnisse
- Gepufferte Wertepaare werden periodisch auf die lokale Festplatte geschrieben
- Adressen der Daten werden an den Master übertragen
- Gruppierung der Daten
- Master übermittelt Worker Speicherbereiche
- Worker liest die Zwischenergebnisse aus dem lokalen Speicher und sortiert sie nach dem Schlüssel
- Ermittlung der Endergebnisse
- Worker iteriert über die Zwischenergebnisse und gibt die Schlüssel und deren zugehörige Datenwerte an die Reduce-Funktion weiter
- Reduce-Funktion fügt ihre Ausgabe der Output-Datei hinzu
6
Q
Map Reduce Fehlertoleranz
A
Worker
- Watchdog: Worker wird als ausgefallen betrachtet, falls Antwort auf Ping-Anfrage des Masters ausbleibt
- Behandlung eines vermuteten Ausfalls
- Alle laufenden Tasks des Workers werden zurückgesetzt
- Fertiggestellte Map-Tasks müssen erneut ausgeführt werden, da Zugriff auf lokalen Speicher des Workers nicht mehr möglich ist
- Fertiggestellte Reduce-Tasks müssen nicht erneut ausgeführt werden
Master
- Periodisches Sichern der Datenstrukturen des Masters:
- Zustand der Tasks: idle, in-progress oder completed
- Identität der Worker
- Adresse der Zwischenergebnisse
- Bei Ausfall: Kopie vom Master wird mit zuletzt gesichertem Status erneut gestartet
7
Q
Optimierungen Map Reduce
A
Datenlokalität
- Daten werden durch GoogleFS mehrfach repliziert im Cluster abgelegt
- Master kennt Speicherorte der Eingabedaten (welche in 64 MB-Blöcke aufgeteilt sind) und positioniert Worker auf dem Rechner der entsprechenden Daten verwaltet oder in dessen Nähe
Backup-Tasks
- Langsame Rechner (sog. straggler) können ungewöhnlich lange Zeit benötigen, um einen der letzten Map- oder Reduce-Tasks fertig zu stellen
- Reduktion der Gesamtlaufzeit durch redundante Ausführung der letzten laufenden Tasks
Frühe Zusammenfassung von Teilergebnissen
- Mittels einer sogenannten Combiner-Funktion kann die Ausgabe von Map-Taks bereits vor Einspeisung in die Reduce-Phase reduziert werden
Differenzierende Datenpartitionierung
- Standardaufteilung der Daten für Reduce-Tasks geschieht mittels hash(key) mod R (R entspricht Anzahl der Reduce-Tasks)
- In der Regel führt dies zu ausbalancierten Partitionen, ist aber aus Sicht der Daten nicht immer optimal
- z. B.: URLs einer Domäne sollen in der gleichen Ausgabedatei gespeichert werden
8
Q
Fazit Map Reduce
A
- Programmiermodell einfach zu verwenden, auch für Programmierer ohne Erfahrung mit verteilten Systemen
- Vielzahl an Problemstellungen mit MapReduce lösbar
- Sortieren von Daten
- Google-Projekte (z. B. Indexing-System bei der Web-Suche)
- Implementierung von MapReduce in der Grundform einfach möglich
9
Q
Dynamo Motivation & Eigenschaften
A
Motivation
- Verteilter, skalierbarer Key-Value-Store v. a. für kleine Datensätze (z. B. 1 MB/Key), z. B. Warenkörbe
- Hochverfügbarkeit und geringe durchschnittliche Latenz – wichtig für Kundenzufriedenheit
Eigenschaften
- Eventually consistent
- Schreibzugriffe sollen immer möglich sein
- Reduzierte Konsistenzzusicherungen zugunsten von Verfügbarkeit
- Ausgleich durch Versionierung
- P2P-artige Verteilung
- Keine Master-Knoten bzw. alle Knoten haben die selbe Funktionalität
- Verteilung von Daten durch consistent hashing
10
Q
Dynamo Einbindung in Amazon-Architektur
A
Verarbeitung einer Client-Anfrage
1. Webserver (Page-Rendering-Components) nehmen Anfrage entgegen
2. Webserver stellen selbst Anfragen an die Sammeldienste
(Aggregator- Services)
3. Sammeldienste kombinieren Informationen angeschlossener
Datenbanken
4. Weitergabe der Daten an die Webserver
5. Erstellung der Webseite
6. Auslieferung an den Client
Ablaufumgebung
Damals: Keine Public Cloud, d. h. komplette Infrastruktur
vertrauenswürdig: Keine Mechanismen zur Authentifizierung und
Autorisierung nötig!
11
Q
Dynamo Dienstschnittstelle
A
Schnittstelle:
- Lesen: get(byte[] key)
- Kann mehrere Versionen eines Objekts zurückliefern: – Liste von (object, context)-Paaren
- Schreiben: put(byte[] key, Context c, byte[] object)
- Context enthält unter anderem Versionsnummer des Objekts (aus vorheriger Leseoperation)
- Lokales Schreiben des Objektes, Erhöhen der Versionsnummer
- Asynchrone Aktualisierung der Replikate – Konsistenzprobleme möglich!
Eigenschaften
- Entspricht Primary-Key-Zugriff – es werden keine komplexen Anfragen unterstützt!
- Anfrage kann an beliebigen Dynamo-Knoten gesendet werden
- Weiterleitung der Anfrage an verantwortlichen Knoten
- Anwendungen sehen Versionierung
12
Q
Dynamo Basiskonzept
A
Zuordnung des Schlüsselraums an Knoten (Rechner)
- Schlüsselraums wir als Ring modelliert
- Jeder Knoten erhält mehrere IDs innerhalb des Schlüsselraums
- Ein Knoten ist jeweils verantwortlich für den Abschnitt des Schlüsselraums der zwischen einer seiner IDs und der nächst kleineren vergebenen ID liegt
- Ziel: gleichmäßige Aufteilung (z. B. wichtig bei Beitritt neuer Knoten, Ausfällen und heterogenen Rechnern)
Abbildung der Daten auf die einzelnen Knoten mittels Schlüssel
- Daten werden dem Knoten mit der unmittelbar im Ring folgenden ID übergeben
- Für Fehlertoleranz den unmittelbar folgenden N Knoten aus einer Liste von präferierten nachfolgenden Knoten
Hinweis
- Vergleiche Peer-to-Peer-Algorithmus: Chord
Realisierung mittels einer Vorzugsliste
- Enthält mehr als N (im Beispiel 3) Knoten, damit bei Ausfällen die Daten erhalten bleiben
- Auswahlentscheidung: Die virtuellen Knoten möglichst auf unterschiedliche physikalische Rechner und evtl. unterschiedliche Datenzentren verteilen
Basis zur Vermittlung von Anfragen
- Navigation innerhalb des Rings erfolgt über eine Knotentabelle die alle Kontenadressen und Verantwortlichkeiten enthält
- Informationen über neue Knoten und Ausfälle werden asynchron verteilt
- Jeder Knoten wählt zyklisch und zufällig einen anderen Konten aus um Information auszutauschen
13
Q
Dynamo Neue Knoten und kurzfristige Ausfälle
A
Hinzunahme neuer Knoten
- Über wohlbekannte Konten (seed nodes) wird der Kontakt zum Netzwerk aufgenommen
- Es wird eine Reihe von virtuellen IDs erzeugt und benachbarte Knoten von der Teilnahme benachrichtigt
- Daten entsprechend der Verantwortlichkeit angefordert
Kurzfristige Knotenausfälle (Hinted Handoff)
- Falls ein Knoten der ersten N der Vorzugsliste ausfällt, wird ein Ausweichknoten ausgewählt
- …dieser speichert entsprechende Daten in einer separaten Datenbank mit dem Verweis auf den tatsächlich verantwortlichen Knoten
- Rückgabe der Daten an den zuvor ausgefallenen Knoten, wenn dieser wieder anläuft
14
Q
Dynamo Behandlung von Anfragen
A
Read/Write-Quoren
- Menge von Knoten, die im Kollektiv eine Entscheidung treffen
- Quorum-Tripel: (N, R, W ), W + R >N
- N - Gesamtzahl der Konten
- R/W minimale Anzahl der N Replikat-Knoten, die für erfolgreicheRead/Write-Operation übereinstimmen müssen
- Werte für N, R und W frei konfigurierbar →Stellschraube für Performance, Verfügbarkeit, Dauerhaftigkeit und Konsistenz
- Strenge Konsistenz erfordert R + W >N, W >R/2 ⇒hohe Zugriffszeiten
Verwendung von Read/Write-Quoren bei Dynamo)
- Beispiele:
- (3, 2, 2) üblich für Dynamo
- Anderes Bsp. W = 1: Schreiben möglich, solange mindestens ein Knoten arbeitet
- sloppy quorum: Es werden die ersten N verfügbaren Knoten von der Vorzugsliste genutzt, dies müssen nicht immer die logisch nächsten im Ring sein
- ⇒ Es kann zu Inkonsistenzen kommen
15
Q
Dynamo behandlung von inkonsistenten Zuständen
A
Eventual Consistency und die Folgen
- Bedingt durch die Verwendung von Eventual Consistency können inkonsistente Zustände auftreten
- Auflösung kann beim Schreiben oder beim Lesen erfolgen
- Dynamo ist auf Verfügbarkeit ausgerichtet (always writeable)
- ⇒Behandlung erfolgt beim Lesen
- Erkennung von Inkonsistenzen erfolgt mittels Vektoruhren
- Auflösung entweder automatisch durch das System oder durch spezifische Behandlung auf Anwendungsebene
21
Q
Bigtable/Habse technische Umsetzung
A
Tablets
- Horizontale Partitionierung von Tabellen in Tablets
- Mehrere Tablet-Server zur Aufnahme der Tablets →Lastbalancierung
- Tablet-Split in 2 gleich große Tablets, wenn max. Größe (z. B. 128 MB) erreicht
Verwaltung von Tablets
Architektur
- Bibliothek für Anwendungsseite
- Master-Rechner zuständig für die Verwaltung von sogenannten Tablet-Servern
- Zuweisung von Tablets an Server
- Lastverteilung
- Integration von neuen Tablet-Servern
- Tablet-Server
- Abwicklung von Lese-/Schreiboperationen auf Tablets
- Bei zu großen Tablets erfolgt Aufteilung
- Anwendungen kommunizieren direkt mit Tablet-Servern
- Last für den Master-Rechner wird reduziert
24
Q
Google File System Architektur
A
Master-Server: Verwaltung von Metainformationen
- Verwaltung der Namensinformation
- Zuordnung von Chunks (Dateneinheiten von max. 64 MB) zu Dateien
- Ortsinformation von Chunks
- Für gute Performance: Metadaten werden im Hauptspeicher verwaltet
Verwaltung der Ortsinformationen
- Master macht Informationen nicht persistent, sondern hält sie im Arbeitsspeicher
- Operationen bzgl. Ortsinformationen werden protokolliert
- Ortsinformationen werden vom Master periodisch von den Daten-Servern (Chunk-Servern) abgefragt
- Fazit: Optimiert für kurze Latenzen und geringe Last für den Master
Weitere Funktionen des Master-Servers
- Monitor
- Periodische Überprüfung der Chunk-Server
- Übernahme zentraler Verwaltungsaufgaben
- Kontrolle der Chunk-Replikation
Schnittstelle
- Verzicht auf POSIX-konforme Einbindung
- Unterstützung von Standardoperationen:
- Erzeugen, Löschen, Öffnen, Schließen, Lesen und Schreiben von Dateien
- Zusätzliche Operationen: Anfügen und Sicherungspunkt
- Anfügen ist im Kontext von MapReduce besonders wichtig
Eigenschaften des Master-Ansatzes
- Einfaches Design
- Ermöglicht Platzierung und Verteilung von Daten basierend auf
- globaler Sicht
- Master ein Flaschenhals?! →Mechanismen zur Vermeidung
- Master-Server ist bei Schreib-/Leseoperationen nicht involviert
- Clients speichern Metadaten zwischen – z. B. Ortsinformationen von Daten
- Clients sind so ausgelegt, dass Anfragen an den Master-Server kombiniert werden und der Master mehr Metadaten ausliefern kann – z. B. unmittelbar aufeinander folgende Chunks
Zwischenspeichern von Metadaten
- Angeforderte Metadaten werden beim Client kurzzeitig hinterlegt
Zwischenspeichern von Dateien
- Client lagert keine Dateien zwischen
- Risiko für Inkonsistenzen ist zu hoch!
- Chunk-Server lagern keine Dateien explizit zwischen
- Gründe – Datenbestand ist zu groß – Weniger Koordinierungsaufwand, da Zwischenspeicher nicht beachtet werden muss
- Implizit wird kurzfristige Lagerung schon durch Systempuffer von Linux übernommen
Chunk-Server
- Größe eines Chunks 64 MB übersteigt typische Größe eines Dateisystemblocks!
- Vorteile
- Weniger Netzwerkverkehr, da weniger Client/Server-Interaktion – z. B. durch weniger Signalisierungsdaten
- Weniger zu verwaltende Metadaten beim Master
- Nachteile
- Interne Fragmentierung
- Chunks können sehr populär sein! – Lösungsansätze: Replikation, zeitliche Verteilung von Anfragen und direkte Kommunikation zwischen Clients
25
Q
Google File System Konsistenzmodell
A
Operationen auf Metadaten
- Operationen werden durch den Master atomar ausgeführt
Modifizierende Operationen auf Daten
Entwicklungsmodell für Anwendungen
- Ergänzen von Dateien ist zu favorisieren, da stabiler Sicherungspunkte
- Wenn mehrere Schreiber eine Datei ergänzen, sollten Ids für Einträge sowie Prüfsummen verwendet werden
26
Q
Google File System Datenreplikation
A
- Jeder Chunk wird über mehrere Chunk-Server repliziert
- Primäre Zuständigkeit für Chunks wird über Leases realisiert
- z. B. für Google mindestens 3x
- Replikation von Chunks wird in zwei Kontrollabläufe gegliedert
- Replikation der Nutzdaten
- Replikation der Operationen und Festlegung ihrer Reihenfolge
Ablauf der Nutzdatenreplikation (Schritt 3)
- Daten werden direkt durch alle Replikate geleitet
- Daten werden von einem Replikat ans Nächste vermittelt
- Beispiel: A →primary replica →B
Kontrollfluss (Schritt 4-5)
- Sobald Daten versendet wurden wird die eigentliche Anfrage an das primäre Replikat übermittelt
- Das primäre Replikat vergibt eine Id an die Anfrage
- Anfrage wird mit Id an alle Knoten vermittelt
