MapReduce - Konzept - Abteilung Datenbanken Leipzig
Transcrição
MapReduce - Konzept - Abteilung Datenbanken Leipzig
MapReduce - Konzept MapReduce-Konzept Thomas Findling, Thomas König 1 Inhalt 1. Motivation 2. Einführung ● ● ● MapReduce Google Rechenzentren Vergleich MapReduce und Relationale DBS 3. Hadoop ● ● ● Funktionsweise Input / Output Fehlerbehandlung 4. Praxis-Beispiel 5. Zusammenfassung MapReduce-Konzept Thomas Findling, Thomas König 2 Motivation ● ● ● ● Das automatische Erfassen von Daten (Log-Dateien, Aktienkurse, Social Networks, ...) erzeugt riesige Datenmengen Speicherkapazitäten von Festplatten sind in den letzten Jahrzehnten stark angestiegen Mittlere Zugriffszeiten und Transferraten haben sich vergleichsweise wenig verbessert Die Zeit zum Auslesen einer kompletten Festplatte wird immer größer ● 2000: 40 GB, 32 MB/s, 9,5 ms → 21 Minuten ● 2009: 1000 GB, 125 MB/s, 8,5 ms → 136 Minuten MapReduce-Konzept Thomas Findling, Thomas König 3 Motivation ● Mehrere Recheneinheiten mit eigenen Plattenspeichern werden zu Clustern verbunden ● Verteilte Speicherung der Daten ● Deutliche Zeitreduzierung bei Zugriffsoperationen ● Parallele Verarbeitung von großen Datenmengen möglich, z.B. 100te TB bis PB MapReduce-Konzept Thomas Findling, Thomas König 4 MapReduce MapReduce-Konzept Thomas Findling, Thomas König 5 MapReduce ● ● ● ● ● Programmiermodell zur Verarbeitung von großen unstrukturierten oder semi-strukturierten Datensätzen MapReduce nutzt verteilte Speicherung der Daten in Blöcken (sorgt für Datenqualität bei fehlerhaften Schreiboder Lesevorgängen) MapReduce-Framework sorgt für die Aufteilung der Berechnungen auf mehrere Recheneinheiten Dadurch parallele Ausführung auf mehreren Rechnern Nach Beendigung der Berechnungen aggregiert das Framework die Ergebnisse MapReduce-Konzept Thomas Findling, Thomas König 6 MapReduce ● Entwickler von verteilten Anwendungen müssen nur das Framework benutzen, keine Codeänderungen bei der Änderung der Client-Anzahl nötig ● Verwendung von handelsüblichen Computern möglich ● Keine Notwendigkeit für spezielle High-End Server MapReduce-Konzept Thomas Findling, Thomas König 7 MapReduce Konzept: ● 2 separate Abläufe: ● ● ● ● ● Map Reduce Daten-Input: eine ganze Menge unstrukturierte Daten Basis von Map und Reduce-Tasks: Schlüssel-/WertePaare Formel: ● (k , v ) → (k2, v2) 1 1 ● [k , list(v )] → (k , v ) 2 2 2 3 MapReduce-Konzept Thomas Findling, Thomas König 8 MapReduce - Beispiel MapReduce-Konzept Thomas Findling, Thomas König 9 MapReduce - Beispiel 1. unstrukturierte Wetterdaten einlesen ● ● 0029029070999991901010106004+64333+023450FM-12+00059 1901-01-01 9999V0202701N015919999999N0000001N9-00781+9999910200 13:00 1ADDGF108991999999999999999999 -7,2°C 0029029070999991901010113004+64333+023450FM-12+00059 9999V0202901N008219999999N0000001N9-00721+9999910200 1ADDGF104991999999999999999999 MapReduce-Konzept Thomas Findling, Thomas König 10 MapReduce - Beispiel 2. Zuordnung von Datei-Inhalt zu Positionen ● ● ● Jede Zeile wird anhand des Byte-Offsets identifiziert Byte-Offset verweist jeweils auf den Beginn der Zeile (k1, v1) = (long, String) MapReduce-Konzept Thomas Findling, Thomas König 11 MapReduce - Beispiel 3. Map: Transformieren dieser Schlüssel-/Werte-Paare in intermediate Schlüssel-/Werte-Paare ● ● Benötigte Daten werden aus den Zeilen extrahiert Es entstehen viele Key/Value-Paare Jahr Temperatur 1950 0 1950 22 1949 111 1949 78 MapReduce-Konzept Thomas Findling, Thomas König 12 MapReduce - Beispiel 4. Map: Erzeugen von gruppierten Schlüssel-/Werte-Paaren ● ● ● ● Sortieren der Schlüssel Zuordnen von Werten zu einem Schlüssel Jeder Mapper schreibt den sortierten Output ins Filesystem Pro Jahr wird ein eigener Reducer auf einem Rechner im Cluster ausgeführt Jahr Temperatur 1949 111 78 1950 0 22 MapReduce-Konzept Thomas Findling, Thomas König 13 MapReduce - Beispiel 5. Reduce: ● ● Zusammenfassung der Werte (hier: Maximum finden) Pro Schlüssel nur noch ein Wert Jahr Temperatur 1949 111 1950 22 MapReduce-Konzept Thomas Findling, Thomas König 14 MapReduce - Beispiel 6. Ausgabe in eine Datei MapReduce-Konzept Thomas Findling, Thomas König 15 MapReduce - Beispiel Parallele Abarbeitung Zusammenführung der parallelen Ergebnisse (merge) MapReduce-Konzept Thomas Findling, Thomas König 16 Google's Rechenzentren MapReduce-Konzept Thomas Findling, Thomas König 17 Google's Rechenzentren ● ● ● ● Welche Hardwarebasis steckt hinter der Such-Engine von Google? Erstellen der Suchindexe und Page-Rank-Tabellen erzeugt riesige Datenmengen Notwendigkeit für Rechenzentren Ein Rechenzentrum besteht aus 45 Containern mit insgesamt 45.000 Servern ● Einsatz von vielen und großen Rechenzentren seit 2005 ● Energieverbrauch beläuft sich auf 10 Megawatt ● Einsatz von wasserbetriebenen Kühltürmen ● Eigenes Kraftwerk MapReduce-Konzept Thomas Findling, Thomas König 18 Google's Rechenzentren ● 45 Container, in jedem befinden sich 1.000 Server: MapReduce-Konzept Thomas Findling, Thomas König 19 Google's Rechenzentren ● Standorte: MapReduce-Konzept Thomas Findling, Thomas König 20 Vergleich mit Relationalen DBS MapReduce-Konzept Thomas Findling, Thomas König 21 Vergleich mit Relationalen DBS MapReduce ● Datenverarbeitung als Streams, lineare Skalierung ● geeignet für: ● ● ● Batch-Verarbeitung von Daten unstrukturierte / semi-strukturierte Daten nicht-normalisierte Daten Relationale DBS ● Suchanfragen (langsamer), nicht-lineare Skalierung ● geeignet für: ● ● ● gezielte Abfragen und Updates strukturierte Daten normalisierte Daten MapReduce-Konzept Thomas Findling, Thomas König 22 Vergleich mit Relationalen DBS Traditional RDBMS MapReduce Data Size Gigabytes Petabytes Access Interactive and Batch Batch Updates Structure Read and write many times Static schema Write once read many times Dynamic schema Integrity High Low Scaling Nonlinear Linear MapReduce-Konzept Thomas Findling, Thomas König 23 Hadoop MapReduce-Konzept Thomas Findling, Thomas König 24 Hadoop ● Hadoop ist eine Implementierung des MapReduceKonzepts ● Open Source Projekt der Apache Software Foundation ● offen für freiwillige Teilnehmer ● zur Verarbeitung großer Datenmengen ● Zusammenschluss von Recheneinheiten zu Clustern ● ● parallele Abarbeitung auf den Recheneinheiten des Clusters hohe Fehlertoleranz, durchschnittlich passieren 1,2 Hardware-Fehler pro Job MapReduce-Konzept Thomas Findling, Thomas König 25 Hadoop ● Download für Unix/Linux verfügbar ● unter Windows nur mit Cygwin ● Programmierung mit Java, Python, C++, etc. möglich ● Hadoop selbst benötigt Java 1.6 ● ● ● Hadoop Distributed File System (HDFS) dient als gemeinsames Dateisystem für das Cluster Eingabe-Dateien müssen erst in das HDFS kopiert werden, bevor sie verwendet werden können es werden auch andere Dateisysteme unterstützt (z.B. CloudStore/Kosmos, S3) MapReduce-Konzept Thomas Findling, Thomas König 26 Hadoop - Funktionsweise Job Tracker ● ● koordiniert Jobs splittet Job in Tasks Task Tracker ● ● führt die Map und Reduce-Tasks aus Ein Task je Prozessor-Kern Dateisystem ● ● ● stellt die Job-Ressourcen bereit Daten werden in Blöcke gesplittet Daten werden redundant gespeichert MapReduce-Konzept Thomas Findling, Thomas König 27 Hadoop – Schritt 1 ● Aufruf von runJob() ● Erzeugung einer neuen JobClient-Instanz MapReduce-Konzept Thomas Findling, Thomas König 28 Hadoop – Schritt 2 ● Aufruf von getNewJobId() ● Erzeugung einer neuen Job-ID MapReduce-Konzept Thomas Findling, Thomas König 29 Hadoop – Schritt 3 ● ● kopieren aller Job-Daten in das gemeinsame Filesystem (Programm und Bibliotheken) Übertragung der Konfigurationsdaten MapReduce-Konzept Thomas Findling, Thomas König 30 Hadoop – Schritt 4 ● Aufruf von submitJob() ● Job wird an den Job Tracker übergeben ● Überprüfung von Input und Output Spezifikationen MapReduce-Konzept Thomas Findling, Thomas König 31 Hadoop – Schritt 5 ● Initialisierung des Jobs ● Verwaltung der Jobs mit einer Job-Warteschlange ● Einteilung eines Jobs in mehrere Tasks MapReduce-Konzept Thomas Findling, Thomas König 32 Hadoop – Schritt 6 ● ● MapReduce-Konzept Abholung der Input Splits Input Splits sind logische Referenzen auf einen Block im HDFS Thomas Findling, Thomas König 33 Hadoop – Schritt 7 ● ● ● einzelne Tasks werden den Task Trackern gemäß dem Job Scheduling zugeteilt „heartbeat“ meldet dem Job Tracker Statusmeldungen, z.B. dass der Task Tracker zur Verfügung steht Task Tracker können nur begrenzte Anzahl an Tasks gleichzeitig bearbeiten MapReduce-Konzept Thomas Findling, Thomas König 34 Hadoop – Schritt 8 ● Abholung der Daten und Bibliotheken zum aktuellen Task ● Tasks bearbeiten nur lokal vorhandene Input Splits ● jeder Map-Task verarbeitet einen Input Split MapReduce-Konzept Thomas Findling, Thomas König 35 Hadoop – Schritt 9 ● ● TaskRunner Instanz startet neue JVM zur Ausführung eines Tasks Für jeden Task wird eine eigene JVM gestartet MapReduce-Konzept Thomas Findling, Thomas König 36 Hadoop – Schritt 10 ● ● ● ● Ausführung des Tasks Child-Prozess kommuniziert mit dem Parent-Task Tracker melde „finished“ oder „failed“ an Task Tracker wenn alle Tasks fertig, melde Job als „completed“ MapReduce-Konzept Thomas Findling, Thomas König 37 Nodes Job Tracker Node ● ● nur einmal vorhanden verwaltet Jobs Task Tracker Node ● ● beliebig viele möglich führt Tasks aus Name Node ● ● nur einmal vorhanden verwaltet Dateisystem/Zugriffe Data Node ● ● ● MapReduce-Konzept beliebig viele möglich enthält Datenblöcke direkter Zugriff auf Ressourcen Thomas Findling, Thomas König 38 Fehlerbehandlung Task-Fehler ● ● ● Abbruch/Timeout: Task Tracker meldet "failed" (Timeout: 10min) andere Task Tracker starten Task neu (max. 4 Versuche) wenn Limit erreicht, wird Job als "failed" markiert (konfigurierbar) Task Tracker-Fehler ● ● ● ● Abbruch/Timeout: Entfernung aus dem Task Tracker Pool Blacklisting: Task Tracker mit zu vielen Task-Fehlern Slowdown: Task Tracker ist zu langsam Tasks von unvollständigen Jobs werden auf Task Tracker verteilt Job Tracker-Fehler ● schwerwiegender Fehler, noch keine Lösungsmöglichkeit MapReduce-Konzept Thomas Findling, Thomas König 39 Input / Output Formate Allgemein ● ● ● ● ● Input Splits sind logische Referenzen auf einen Teil der Daten Input Splits repäsentieren einen Block im HDFS RecordReader erzeugt daraus Records (Key/Value-Paare) Records werden an den Mapper übergeben der Map-Output muss das Format des Reduce-Inputs haben Text Input / Output ● ● Record besteht aus Byteoffset / Nummer und Inhalt einer Zeile bei XML werden Records an start- und end-Tags angepasst Binary Input / Output ● ● besteht aus Sequenzen von binären Key/Value-Paaren Kompression möglich MapReduce-Konzept Thomas Findling, Thomas König 40 Input / Output Formate Database Input / Output ● ● Nutzung relationaler Datenbanken möglich Zugriff via JDBC Multiple Input / Output ● ● ● für Input-Formate können mehrere Mapper definiert werden Map-Output muss aber immer gleich sein es können mehrere Output-Files oder -Formate genutzt werden Lazy Output ● ● OutputWrapper, für jedes Output-Format geeignet auch ohne Output wird immer eine Output-Datei erzeugt MapReduce-Konzept Thomas Findling, Thomas König 41 Praxis-Beispiel MapReduce-Konzept Thomas Findling, Thomas König 42 Praxis-Beispiel Aufgabe ● Berechnung des günstigsten Preises Daten ● ● ● ca. 3,5 Mio Datensätze von preisvergleich.de 3,8 GB semi-strukturierte Daten in 44 Dateien beinhaltet Produktname, Preis, Händler, Zustand, usw. Map-Phase ● Key/Value-Zuordnung: Produktname → Preis Reduce-Phase ● ● finde für jeden Key (Produktname) kleinste Value (Preis) ca. 2,5 Mio verbleibende Datensätze (= ca. 1 Mio Preisvergleiche) MapReduce-Konzept Thomas Findling, Thomas König 43 Praxis-Beispiel Durchführung MapReduce-Konzept Thomas Findling, Thomas König 44 Praxis-Beispiel ● Vergleich Single Core, Dual Core und Cluster ● ● ● ● Pentium M, 1 * 2,0 GHz → 464 s = 7:42 min Core Duo, 2 * 2,0 GHz → 364 s = 6:04 min Cluster, 3 * 2,0 GHz → 227 s = 3:47 min Kolb-Cluster, 10 * 2,66 GHz ● 2 * 2,66 GHz ● 8 * 2,66 Ghz → 94 s = 1:34 min MapReduce-Konzept 500 Zeitdauer (s) 450 400 350 300 250 200 150 100 50 0 Single Core Dual Core Thomas Findling, Thomas König Cluster Kolb-Cluster 45 Zusammenfassung MapReduce-Konzept Thomas Findling, Thomas König 46 Zusammenfassung MapReduce ● Parallele Verarbeitung von großen Datenmengen führt zu einer deutlichen Zeitreduzierung bei Zugriffsoperationen ● ● ● MapReduce-Framework koordiniert automatisch die Ausführung von Tasks auf mehreren Rechnern (Dateioperationen, Berechnungen, Fehlertoleranz, …) Handelsübliche Computer einsetzbar Bei großen Datenmengen ist die Stream-Verarbeitung von MapReduce schneller als Suchanfragen auf relationale DBS MapReduce-Konzept Thomas Findling, Thomas König 47 Zusammenfassung Hadoop ● Hadoop ist eine Implementierung des MapReduceKonzepts ● ● ● ● Für Unix/Linux frei verfügbar Task Tracker und Job Tracker koordinieren die Ausführung der Tasks Bei fehlerhaften Daten oder bei zu langen Antwortzeiten wird ein Task Tracker automatisch blockiert Er wird aus der Task Tracker-Liste entfernt und die Tasks werden automatisch auf die restlichen Task Tracker aufgeteilt MapReduce-Konzept Thomas Findling, Thomas König 48 Zusammenfassung Hadoop ● Daten sind als Blöcke im HDFS gespeichert ● ● Daten werden immer als Key-/Value-Paare verarbeitet (Records) Es gibt Text-, Binary- und Database-Input / Output MapReduce-Konzept Thomas Findling, Thomas König 49 Vielen Dank für Ihre Aufmerksamkeit! MapReduce-Konzept Thomas Findling, Thomas König 50 Quellen ● ● ● ● ● ● ● ● ● Tom White (2009): “Hadoop – The Definite Guide”, O'Reilly Media, Inc. MapReduce: Simplified data processing on large clusters http://labs.google.com/papers/mapreduce-osdi04.pdf An Introduction to MapReduce http://www.slideshare.net/Wombert/an-introduction-to-mapreduce Google Data Center Video http://blogoscoped.com/archive/2009-04-08-n39.html Map of all Google data center locations http://royal.pingdom.com/2008/04/11/map-of-all-google-data-center-locations/ Apache Hadoop http://hadoop.apache.org/ Running Hadoop On Ubuntu Linux (Single-Node Cluster) http://www.michael-noll.com/wiki/Running_Hadoop_On_Ubuntu_Linux_(Single-Node_Cluster) Running Hadoop On Ubuntu Linux (Multi-Node Cluster) http://www.michael-noll.com/wiki/Running_Hadoop_On_Ubuntu_Linux_(Multi-Node_Cluster) Preisinformationen vom Preisvergleich.de-FTP-Server ftp.preisvergleich.de MapReduce-Konzept Thomas Findling, Thomas König 51