MapReduce - Konzept - Abteilung Datenbanken Leipzig

Transcrição

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
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
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
4
MapReduce
MapReduce-Konzept
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
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
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
8
MapReduce - Beispiel
MapReduce-Konzept
9
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
10
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
11
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
12
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
13
5. Reduce:
●
●
Zusammenfassung der Werte (hier: Maximum finden)
Pro Schlüssel nur noch ein Wert
Jahr
Temperatur
1949
111
1950
22
MapReduce-Konzept
14
6. Ausgabe in eine Datei
MapReduce-Konzept
15
Parallele Abarbeitung
Zusammenführung der
parallelen Ergebnisse
(merge)
MapReduce-Konzept
16
Google's Rechenzentren
MapReduce-Konzept
17
●
●
●
●
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
18
●
45 Container, in jedem befinden sich 1.000 Server:
MapReduce-Konzept
19
●
Standorte:
MapReduce-Konzept
20
Vergleich mit Relationalen DBS
MapReduce-Konzept
21
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
22
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
23
Hadoop
MapReduce-Konzept
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
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
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
27
Hadoop – Schritt 1
●
Aufruf von runJob()
●
Erzeugung einer neuen JobClient-Instanz
MapReduce-Konzept
28
●
Aufruf von getNewJobId()
●
Erzeugung einer neuen Job-ID
MapReduce-Konzept
29
●
●
kopieren aller Job-Daten
in das gemeinsame Filesystem (Programm und
Bibliotheken)
Übertragung der Konfigurationsdaten
MapReduce-Konzept
30
●
Aufruf von submitJob()
●
Job wird an den Job Tracker übergeben
●
Überprüfung von Input und Output Spezifikationen
MapReduce-Konzept
31
●
Initialisierung des Jobs
●
Verwaltung der Jobs mit einer Job-Warteschlange
●
Einteilung eines Jobs in mehrere Tasks
MapReduce-Konzept
32
●
●
MapReduce-Konzept
Abholung der Input Splits
Input Splits sind logische
Referenzen auf einen Block
im HDFS
33
●
●
●
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
34
●
Abholung der Daten und Bibliotheken zum aktuellen
Task
●
Tasks bearbeiten nur lokal vorhandene Input Splits
●
jeder Map-Task verarbeitet einen Input Split
MapReduce-Konzept
35
●
●
TaskRunner Instanz startet
neue JVM zur Ausführung
eines Tasks
Für jeden Task wird eine
eigene JVM gestartet
MapReduce-Konzept
36
●
●
●
●
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
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
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
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
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
41
Praxis-Beispiel
MapReduce-Konzept
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
43
Praxis-Beispiel
Durchführung
MapReduce-Konzept
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
Cluster
Kolb-Cluster
45
Zusammenfassung
MapReduce-Konzept
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
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
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
49
Vielen Dank für Ihre
Aufmerksamkeit!
MapReduce-Konzept
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
51

MapReduce - Konzept - Abteilung Datenbanken Leipzig

Transcrição

Documentos relacionados

Die Glaziale Serie

Die Glaziale Serie – Lösungsvorschlag

Seminarthemen - Lehrgebiet Datenbanksysteme für neue

Editorial

mit Gestalten - Felix Gartenbau AG

Analog oder Digital Analog oder Digital

Die neuen LVS im Test Die neuen LVS im Test

LORENZ MESSTECHNIK GmbH

Bedienungsanleitung GPS Tracker TK105

Aufgabe 2

Thema SAP LES

Coaxial/Optical Audio Converter

Vortragsfolien