Transcript
¨ Uberblick
MapReduce: Einfu¨hrung MapReduce: Programmiermodell zur Strukturierung von Programmen f¨ ur parallele, verteilte Ausf¨ uhrung
MapReduce Framework MapReduce
Map und Reduce urspr¨ unglich Bausteine aus funktionalen Programmiersprachen (z. B. LISP)
Einf¨ uhrung und Grundlagen Ablauf eines MapReduce-Jobs Aufgaben des Frameworks
Map: Abbildung eines Eingabeelements auf ein Ausgabeelement Reduce: Zusammenfassung mehrerer gleichartiger Eingaben zu einer einzelnen Ausgabe
Aufgabe 4 Abstract Factory Entwurfsmuster Vergleichen und Sortieren mit Java Zusammenf¨ uhrung vorsortierter Listen Futures Daten finden und extrahieren
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
Formulierung zu l¨ osender Aufgabe in MapReduce Aufteilen in (potentiell mehrere) Map- und Reduce-Schritte Implementierung der Map- und Reduce-Methoden (Entwickler) Parallelisierung und Verteilung (MapReduce-Framework)
6–1
MapReduce: Einfu¨hrung
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6–2
Hadoop-Framework (Komponenten)
,,MapReduce: Simplified data processing on large clusters” (OSDI’04) Implementierung von Google nicht o¨ffentlich Zahlreiche Open-Source-Implementierungen (z. B. Disco, Apache Hadoop, Phoenix) → Erm¨ oglicht Verarbeitung riesiger Datenmengen → Vereinfachung der Anwendungsentwicklung
Literatur Jeffrey Dean and Sanjay Ghemawat MapReduce: Simplified data processing on large clusters Proceedings of the 6th Conference on Operating Systems Design and Implementation (OSDI ’04), pages 137–150, 2004.
Quelle der Illustration: https://blog.codecentric.de/2013/08/einfuhrung-in-hadoop-die-wichtigsten-komponenten-von-hadoop-teil-3-von-5/
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6–3
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6–4
Ablauf von MapReduce
Map-Phase
¨ Ubersicht: Ablauf eines MapReduce-Durchlaufs.
Abbildung in der Map-Phase Parallele Verarbeitung verschiedener Teilbereiche der Eingabedaten Eingabedaten in Form von Schl¨ ussel-Wert-Paaren Abbildung auf variable Anzahl von neuen Schl¨ ussel-Wert-Paaren
Partitionierung
Merge
o
Key Value Eingabe
Ausgabe
Key Value Map
Sortierung & Gruppierung
Key Value
Reduce
Key Value Key Value
Key Value
Key Value ...
Darstellung der Daten in Form von Schl¨ ussel-Wert-Paaren
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6–5
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
Mapper-Schnittstelle
Mapper-Beispiel
Schnittstelle Mapper in Apache Hadoop
Beispiel: Z¨ahlen von W¨ ortern Mapper-Eingabe Schl¨ ussel: Zeilennummer Wert: Textzeile Mapper-Ausgabe Schl¨ ussel: Wort Wert: Anzahl (hier: 1 f¨ ur jedes Wort)
public class Mapper { void map(KEYIN key, VALUEIN value, Context context) { context.write((KEYOUT) key, (VALUEOUT) value); } }
Festlegen von Datentypen mittels Generics“ ” key: Schl¨ ussel, z. B. Zeilennummer
Key 1
value: Wert, z. B. Inhalt der Zeile
Value We saw lions and tigers. The lions and we 1
Eingaben
context: Ausf¨ uhrungskontext, enth¨alt write()-Methode zur Ausgabe von Schl¨ ussel-Wert-Paaren
2
lions 1
saw 1
fantastic 1 were 1
MapReduce Framework – MapReduce
6–7
tigers 1
}
lions 1
the 1
and 1
and 1
Ausgabe
tigers were fantastic. The lions had babies. tigers 1
¨ MW-Ubung (WS14/15)
6–6
¨ MW-Ubung (WS14/15)
lions 1
the 1
babies had 1
MapReduce Framework – MapReduce
1
}
Ausgabe
6–8
Sortierung und Gruppierung
Partitionierer Zuordnung zu sp¨aterem Reducer bei Mapper-Ausgabe
Sortierung und Gruppierung nach Schl¨ ussel
Reducer-Eingaben unabh¨angig → parallelisierbar Gleiche Schl¨ ussel m¨ ussen zu gleichem Reducer
Lokale Vorsortierung nach Verarbeitung der Daten durch Mapper Zusammenfassen aller Werte unter identischem Schl¨ ussel Statt Schl¨ ussel-Wert-Paar nun Schl¨ ussel und Liste von Werten
Schnittstelle in Apache Hadoop public class Partitioner { int getPartition(KEY key, VALUE value, int numPartitions) { return Math.abs(key.hashCode()) % numPartitions; } } Key
Value
red 1 bike 1
Partition 1
red 1 red 1
low 1
rocks 1 Partition 2
rocks 1
shed 1
rocks 1
amiable 1 red 1 rocks 1 low 1
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6–9
¨ MW-Ubung (WS14/15)
bike 1 amiable 1
MapReduce Framework – MapReduce
Partition 3 shed 1
6 – 10
Ablauf von MapReduce
Merge
¨ Ubersicht: Ablauf eines MapReduce-Durchlaufs.
Eingaben f¨ ur Reducer befinden sich in (mehreren) Mapper-Ausgaben Zusammenfassung der vorsortierten Partitionen zu einer vollst¨andig sortierten und gruppierten Gesamtliste (Merge)
Partitionierung
Merge
Eingabe
Ausgabe
Map
¨ MW-Ubung (WS14/15)
Sortierung & Gruppierung
MapReduce Framework – MapReduce
Reduce
6 – 11
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6 – 12
Reduce-Phase
Reducer-Schnittstelle
Zusammenf¨ uhren von Daten in der Reduce-Phase
Schnittstelle Reducer in Apache Hadoop:
Eingabe in Form von Schl¨ ussel und alle zugeh¨origen Werte aus Mapper Parallele Verarbeitung verschiedener Teilbereiche von Schl¨ usseln Abbildung auf variable Anzahl von neuen Schl¨ ussel-Wert-Paaren Key Values
lions 1 1 1 1
Key Value
lions 4
public class Reducer { void reduce(KEYIN key, Iterable values, Context context) { for(VALUEIN value : values) { context.write((KEYOUT) key, (VALUEOUT) value); } } }
key: Schl¨ ussel aus Sortierungsphase values: Liste von Werten, welche zu dem Schl¨ ussel gruppiert wurden
tigers 1 1
tigers 2
were 1 1
context: Ausf¨ uhrungskontext, enth¨alt write()-Methode zur Ausgabe von Schl¨ ussel-Wert-Paaren
were 2
Reduce ¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6 – 13
Aufgaben des Frameworks
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
6 – 14
Framework-Entwicklung
Generelle Steuerung der MapReduce-Abl¨aufe Framework stellt Rahmen f¨ ur Anwendungen auf
Scheduling einzelner (Teil-)Aufgaben Einhaltung der Reihenfolge bei Abh¨angigkeiten Zwischenspeicherung der Daten
Lediglich grunds¨ atzlicher Ablauf vorgegeben Details der Anwendung nicht vorab bekannt → Hohe Flexibilit¨at und Konfigurierbarkeit notwendig
Implementiert grunds¨atzliche Algorithmen (z. B. Sortierung)
Im Fall des MapReduce-Frameworks aus Aufgabe 4: Mapper Reducer Sortierung
Bereitstellen von Schnittstellen zur Anpassung von Partitionierung Dateneingabe (Deserialisierung) Mapper Sortierung/Gruppierung Reducer Datenausgabe (Serialisierung)
¨ MW-Ubung (WS14/15)
MapReduce Framework – MapReduce
Ausw¨ahlbare Implementierung f¨ ur einzelne Schritte Framework muss notwendige Objekte selbst instanziieren L¨osung mittels Factory Pattern“ ”
6 – 15
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 16
Factory Pattern
Abstract Factory Pattern
Problemstellung: Es sollen Objekte instanziiert werden, welche eine bestimmte Schnittstelle zur Verf¨ ugung stellen, ohne dass der genaue Typ vorab bekannt ist.
L¨osung durch weitere Abstraktionsschicht: Schnittstelle zur Instanziierung
→ Kapselung der Instanziierung in eigener Klasse
public class WordCountMapper implements Mapper { ... } public interface MapperFactory { public Mapper createMapper(); }
Beispiel: public class WordCountMapper implements Mapper { ... }
public class WordCountFactory implements MapperFactory { public Mapper createMapper() { return new WordCountMapper(); } }
public class WordCountFactory { public Mapper createMapper() { return new WordCountMapper(); } }
Verwendung:
Allerdings: Klasse WordCountFactory muss Framework bekannt sein
void myMethod(MapperFactory mfact) { Mapper m = mfact.createMapper(); ... }
¨ MW-Ubung (WS14/15)
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 17
MapReduce Framework – Aufgabe 4
Sortieren mittels Comparator-Objekten
Sortieren mittels Comparator-Objekten
Standardisierte Schnittstellen zum Vergleich von Objekten: Comparable
Verwendung: int x = links.compareTo(rechts); int y = comparator.compare(links, rechts);
Vergleicht Objekt mit anderem gegebenen Objekt
Methoden compareTo() und compare() liefern Integer zur¨ uck
public interface Comparable { public int compareTo(T o); }
negativ: Linker Wert kleiner als rechter Wert (kommt vor...) 0: Beide Werte sind gleich (¨ aquivalent) positiv: Linker Wert gr¨ oßer als rechter Wert (kommt nach...)
Comparator Vergleicht zwei gegebene Objekte miteinander ¨ equals() vergleicht Aquivalenz verschiedener Comparator-Typen
Beispiel: Strings r¨ uckw¨arts sortieren
public abstract class Comparator { public int compare(T o1, T o2); public boolean equals(Object obj); }
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 18
class RevStringComparator implements Comparator { public int compare(String o1, String o2) { return -o1.compareTo(o2); } }
6 – 19
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 20
Sortieren mittels Comparator-Objekten
Zusammenfu¨hrung mittels Priority-Queues
¨ Comparator erm¨oglicht Anderung der Sortierreihenfolge ohne Ableiten der zu sortierenden Objekte
Aufgabe: Zusammenf¨ uhren bereits vorsortierter Listen
Einstellung bei sortierenden Standard-Containern in Java
Datenstruktur Priority-Queue
Vergleich des obersten Elements u ¨ber alle Listen Kleinstes Element bestimmt n¨achstes Ausgabeelement
Einf¨ ugen von Elementen mit zugeordneter Priorit¨at Entfernen entnimmt immer Element mit h¨ ochster Priorit¨at ¨ Ublicherweise als Heap-Datenstruktur implementiert
Beispiel: TreeMap (implementiert SortedMap) RevStringComparator revcmp = new RevStringComparator(); TreeMap treemap = new TreeMap(revcmp);
→ Iterieren u ussel in umgekehrter Reihenfolge ¨ber Map liefert Schl¨
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 21
Nutzung als Merge-Algorithmus: Priorit¨at entspricht Wertigkeit des obersten Elements jeder Liste Entnahme aus Priority-Queue liefert Liste mit n¨achstem Element
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
Zusammenfu¨hrung mittels Priority-Queues
Zusammenfu¨hrung mittels Priority-Queues
Algorithmus:
Priority-Queues in Java: java.util.PriorityQueue
6 – 22
H¨ ochste Priorit¨ at entspricht erster Stelle nach Sortierung Festlegen der Sortierung mittels Comparator:
1. Priority-Queue mit vorsortierten Listen bef¨ ullen 2. Entnahme des Elements h¨ochster Priorit¨at liefert Liste, welche das n¨achste auszugebende Listenelement an erster Stelle enth¨alt
public PriorityQueue(int capacity, Comparator c);
3. Ausgeben und Entfernen des obersten Listenelements aus der entnommenen Liste
Einf¨ ugen eines Elements vom Typ E: public boolean add(E item);
4. Liste wieder in Priority-Queue einf¨ ugen 5. Wiederholen ab (2), bis alle Listen leer sind
Abfrage des obersten Elements: public E peek();
Entnahme des obersten Elements: public E poll();
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 23
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 24
Futures
Futures in Java
Oftmals synonym verwendet: Promise
Schnittstelle Future Umfang
Schnittstelle
Methoden der allgemeinen Future-Schnittstelle Zus¨atzliche Methoden zum Abbrechen von Tasks
boolean poll(); get();
Schnittstelle
Funktionsweise 1. Beim asynchronen Aufruf wird (statt dem eigentlichen Ergebnis) sofort ein Future-Objekt zur¨ uckgegeben 2. Das Future-Objekt l¨asst sich befragen, ob der tats¨achliche R¨ uckgabewert der Operation bereits vorliegt bzw. ob die Operation beendet ist → poll() 3. Ein Aufruf von get() liefert das Ergebnis der Operation sofort zur¨ uck, sofern es zu diesem Zeitpunkt bereits vorliegt oder blockiert solange, bis das Ergebnis eingetroffen ist
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
Futures in Java
public interface Future { public V get(); public V get(long timeout, TimeUnit unit); public boolean isDone();
// --> poll()
public boolean cancel(boolean mayInterruptIfRunning); public boolean isCancelled(); }
6 – 25
java.util.concurrent.ExecutorService
Anwendungsbeispiel Executor-Service Interface ExecutorService
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
Futures in Java – Anwendungsbeispiel
6 – 26
ExecutorService
Klasse java.util.concurrent.Executors ¨ Uberblick
Erlaubt asynchrone Ausf¨ uhrung von Tasks Task bei Executor-Service abgeben“, Ergebnis per Future ” Zentrale Methode
Hilfsmethoden zur Erzeugung von Callable-Objekten Bereitstellung von ExecutorService-Implementierungen
Wichtige Factory-Methoden f¨ ur ExecutorServices
Future submit(Callable task)
Ausf¨ uhrung in einem einzigen Thread public static ExecutorService newSingleThreadExecutor();
Interface Callable Schnittstelle
Konstante Thread-Anzahl
public interface Callable { V call() throws Exception; }
public static ExecutorService newFixedThreadPool(int nThreads);
...
Unterschiede zu Runnable
ExecutorService
R¨ uckgabewert Exception
¨ MW-Ubung (WS14/15)
java.util.concurrent.Future
nach Verwendung wieder beenden:
public void shutdown();
MapReduce Framework – Aufgabe 4
6 – 27
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 28
Futures in Java – Anwendungsbeispiel
Extrahieren von Daten
ExecutorService
Beispielklasse
Extrahieren von Daten typische MapReduce-Anwendung
public class FutureExample implements Callable { private int a, b;
Statistiken, Data Mining Mustererkennung, Machine Learning Graph-Algorithmen
public FutureExample(int a, int b) { this.a = a; this.b = b; }
Eingabedaten h¨aufig in Form von Textzeilen
public Integer call() throws Exception { return a * b; }
Partitionierung von Eingabedaten problematisch: Zusammengeh¨ orige Daten k¨ onnen in unterschiedlichen Worker-Threads verarbeitet werden
}
Aufruf L¨osungsm¨ oglichkeiten:
ExecutorService es = Executors.newSingleThreadExecutor(); FutureExample task = new FutureExample(4, 7); Future f = es.submit(task); [...] System.out.println("result: " + f.get()); ¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
Beeinflussung der Partitionierung durch Eingabedaten Verwerfen unvollst¨andiger Datens¨atze, z. B. bei statistischen Auswertungen großer Datenmengen 6 – 29
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
Auffinden von Zeichenketten
Regul¨are Ausdru¨cke in Java
Einfache Methoden in Java.lang.String Finden konstanter Zeichenketten
Regul¨are Ausdr¨ ucke mit java.util.regex.Pattern N¨ utzliche Teilausdr¨ ucke
Vorw¨arts suchen ab bestimmter Position:
6 – 30
Beliebiges Zeichen: . Anfang des Strings: ^ String-Ende: $ Wiederholung: * → beliebig oft, + → mindestens einmal Zeichenauswahl: [abc] → a, b oder c Zeichenklassen: \s Leerzeichen, \d Ziffern
public int indexOf(String str, int start);
R¨ uckw¨arts suchen ab bestimmter Position: public int lastIndexOf(String str, int start);
Operationen mit regul¨aren Ausdr¨ ucken: Beispiele:
Test, ob regul¨arer Ausdruck anwendbar:
^Hallo // Hallo am Anfang des Strings welt.$ // welt gefolgt von beliebigem Zeichen am Stringende te[sx]+t // te, mindestens einmal s oder x, t
public boolean matches(String regex);
Aufteilen in Array anhand von regul¨arem Ausdruck: public String[] split(String regex, int limit); ¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 31
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 32
Regul¨are Ausdru¨cke in Java
Teilstrings extrahieren
Vorkompilieren h¨aufig ben¨otigter Ausdr¨ ucke:
Bei bekanntem Start- und End-Index:
Pattern p = Pattern.compile(regex); Matcher m = p.matcher(str);
public String substring(int start, int end);
Ausgabe des Strings ab start bis end, ohne end selbst.
Test, ob Ausdruck passt:
Tipp: Zum Test ein Zeichen vor und nach dem gesuchten Teilbereich ausgeben lassen
public boolean matches();
Position abfragen, wo ein Treffer gefunden wurde:
Aufteilen nach regul¨arem Ausdruck:
public int start(); String[] parts = input.split(regex, 2);
Beispiel:
if (parts.length() < 2) System.err.println("Not found");
if (m.matches()) { int pos = m.start(); ... } ¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
String left = parts[0], right = parts[1];
6 – 33
Weitere Informationen J. Dean, S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI 2004 Proceedings, S. 137-150, http://www.usenix.org/events/osdi04/tech/dean.html
Apache Hadoop http://hadoop.apache.org/
Hadoop SVN repository http://svn.apache.org/viewvc/hadoop/common/
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 35
¨ MW-Ubung (WS14/15)
MapReduce Framework – Aufgabe 4
6 – 34
