Tag Archive for: Map Reduce

Big Data mit Hadoop und Map Reduce!

Foto von delfi de la Rua auf Unsplash.

Hadoop ist ein Softwareframework, mit dem sich große Datenmengen auf verteilten Systemen schnell verarbeiten lassen. Es verfügt über Mechanismen, welche eine stabile und fehlertolerante Funktionalität sicherstellen, sodass das Tool für die Datenverarbeitung im Big Data Umfeld bestens geeignet ist. In diesen Fällen ist eine normale relationale Datenbank oft nicht ausreichend, um die unstrukturierten Datenmengen kostengünstig und effizient abzuspeichern.

Unterschiede zwischen Hadoop und einer relationalen Datenbank

Hadoop unterscheidet sich in einigen grundlegenden Eigenschaften von einer vergleichbaren relationalen Datenbank.

Eigenschaft Relationale Datenbank Hadoop
Datentypen ausschließlich strukturierte Daten alle Datentypen (strukturiert, semi-strukturiert und unstrukturiert)
Datenmenge wenig bis mittel (im Bereich von einigen GB) große Datenmengen (im Bereich von Terrabyte oder Petabyte)
Abfragesprache SQL HQL (Hive Query Language)
Schema Statisches Schema (Schema on Write) Dynamisches Schema (Schema on Read)
Kosten Lizenzkosten je nach Datenbank Kostenlos
Datenobjekte Relationale Tabellen Key-Value Pair
Skalierungstyp Vertikale Skalierung (Computer muss hardwaretechnisch besser werden) Horizontale Skalierung (mehr Computer können dazugeschaltet werden, um Last abzufangen)

Vergleich Hadoop und Relationale Datenbank

Bestandteile von Hadoop

Das Softwareframework selbst ist eine Zusammenstellung aus insgesamt vier Komponenten.

Hadoop Common ist eine Sammlung aus verschiedenen Modulen und Bibliotheken, welche die anderen Bestandteile unterstützt und deren Zusammenarbeit ermöglicht. Unter anderem sind hier die Java Archive Dateien (JAR Files) abgelegt, die zum Starten von Hadoop benötigt werden. Darüber hinaus ermöglicht die Sammlung die Bereitstellung von grundlegenden Services, wie beispielsweise das File System.

Der Map-Reduce Algorithmus geht in seinen Ursprüngen auf Google zurück und hilft komplexe Rechenaufgaben in überschaubarere Teilprozesse aufzuteilen und diese dann über mehrere Systeme zu verteilen, also horizontal zu skalieren. Dadurch verringert sich die Rechenzeit deutlich. Am Ende müssen die Ergebnisse der Teilaufgaben wieder zu seinem Gesamtresultat zusammengefügt werden.

Der Yet Another Resource Negotiator (YARN) unterstützt den Map-Reduce Algorithmus, indem er die Ressourcen innerhalb eines Computer Clusters im Auge behält und die Teilaufgaben auf die einzelnen Rechner verteilt. Darüber hinaus ordnet er den einzelnen Prozessen die Kapazitäten dafür zu.

Das Hadoop Distributed File System (HDFS) ist ein skalierbares Dateisystem zur Speicherung von Zwischen- oder Endergebnissen. Innerhalb des Clusters ist es über mehrere Rechner verteilt, um große Datenmengen schnell und effizient verarbeiten zu können. Die Idee dahinter war, dass Big Data Projekte und Datenanalysen auf großen Datenmengen beruhen. Somit sollte es ein System geben, welches die Daten auch stapelweise speichert und dadurch schnell verarbeitet. Das HDFS sorgt auch dafür, dass Duplikate von Datensätzen abgelegt werden, um den Ausfall eines Rechners verkraften zu können.

Map Reduce am Beispiel

Angenommen wir haben alle Teile der Harry Potter Romane in Hadoop PDF abgelegt und möchten nun die einzelnen Wörter zählen, die in den Büchern vorkommen. Dies ist eine klassische Aufgabe bei der uns die Aufteilung in eine Map-Funktion und eine Reduce Funktion helfen kann.

Bevor es die Möglichkeit gab, solche aufwendigen Abfragen auf ein ganzes Computer-Cluster aufzuteilen und parallel berechnen zu können, war man gezwungen, den kompletten Datensatz nacheinander zu durchlaufen. Dadurch wurde die Abfragezeit auch umso länger, umso größer der Datensatz wurde. Der einzige Weg, um die Ausführung der Funktion zu beschleunigen ist es, einen Computer mit einem leistungsfähigeren Prozessor (CPU) auszustatten, also dessen Hardware zu verbessern. Wenn man versucht, die Ausführung eines Algorithmus zu beschleunigen, indem man die Hardware des Gerätes verbessert, nennt man das vertikale Skalieren.

Mithilfe von MapReduce ist es möglich eine solche Abfrage deutlich zu beschleunigen, indem man die Aufgabe in kleinere Teilaufgaben aufsplittet. Das hat dann wiederum den Vorteil, dass die Teilaufgaben auf viele verschiedene Computer aufgeteilt und von ihnen ausgeführt werden kann. Dadurch müssen wir nicht die Hardware eines einzigen Gerätes verbessern, sondern können viele, vergleichsweise leistungsschwächere, Computer nutzen und trotzdem die Abfragezeit verringern. Ein solches Vorgehen nennt man horizontales Skalieren.

Kommen wir zurück zu unserem Beispiel: Bisher waren wir bildlich so vorgegangen, dass wir alle Harry Potter Teile gelesen haben und nach jedem gelesenen Wort die Strichliste mit den einzelnen Wörtern einfach um einen Strich erweitert haben. Das Problem daran ist, dass wir diese Vorgehensweise nicht parallelisieren können. Angenommen eine zweite Person will uns unterstützen, dann kann sie das nicht tun, weil sie die Strichliste, mit der wir gerade arbeiten, benötigt, um weiterzumachen. Solange sie diese nicht hat, kann sie nicht unterstützen.

Sie kann uns aber unterstützen, indem sie bereits mit dem zweiten Teil der Harry Potter Reihe beginnt und eine eigene Strichliste nur für das zweite Buch erstellt. Zum Schluss können wir dann alle einzelnen Strichlisten zusammenführen und beispielsweise die Häufigkeit des Wortes “Harry” auf allen Strichlisten zusammenaddieren.

MapReduce am Beispiel von Wortzählungen in Harry Potter Büchern

MapReduce am Beispiel von Wortzählungen in Harry Potter Büchern | Source: Data Basecamp

Dadurch lässt sich die Aufgabe auch relativ einfach horizontal skalieren, indem jeweils eine Person pro Harry Potter Buch arbeitet. Wenn wir noch schneller arbeiten wollen, können wir auch mehrere Personen mit einbeziehen und jede Person ein einziges Kapitel bearbeiten lassen. Am Schluss müssen wir dann nur alle Ergebnisse der einzelnen Personen zusammennehmen, um so zu einem Gesamtergebnis zu gelangen.

Das ausführliche Beispiel und die Umsetzung in Python findest Du hier.

Aufbau eines Hadoop Distributed File Systems

Der Kern des Hadoop Distributed File Systems besteht darin die Daten auf verschiedene Dateien und Computer zu verteilen, sodass Abfragen schnell bearbeitet werden können und der Nutzer keine langen Wartezeiten hat. Damit der Ausfall einer einzelnen Maschine im Cluster nicht zum Verlust der Daten führt, gibt es gezielte Replikationen auf verschiedenen Computern, um eine Ausfallsicherheit zu gewährleisten.

Hadoop arbeitet im Allgemeinen nach dem sogenannten Master-Slave-Prinzip. Innerhalb des Computerclusters haben wir einen Knoten, der die Rolle des sogenannten Masters übernimmt. Dieser führt in unserem Beispiel keine direkte Berechnung durch, sondern verteilt lediglich die Aufgaben auf die sogenannten Slave Knoten und koordiniert den ganzen Prozess. Die Slave Knoten wiederum lesen die Bücher aus und speichern die Worthäufigkeit und die Wortverteilung.

Dieses Prinzip wird auch bei der Datenspeicherung genutzt. Der Master verteilt Informationen aus dem Datensatz auf verschiedenen Slave Nodes und merkt sich, auf welchen Computern er welche Partitionen abgespeichert hat. Dabei legt er die Daten auch redundant ab, um Ausfälle kompensieren zu können. Bei einer Abfrage der Daten durch den Nutzer entscheidet der Masterknoten dann, welche Slaveknoten er anfragen muss, um die gewünschten Informationen zu erhalten.

Big Data Essentials – Intro

1. Big Data Definition

Data umfasst Nummern, Text, Bilder, Audio, Video und jede Art von Informationen die in Ihrem Computer gespeichert werden können. Big Data umfasst Datenmengen, die eine oder mehrere der folgenden Eigenschaften aufweisen: Hohes Volumen (High Volume), hohe Vielfalt (High Variety) und / oder eine notwendige hohe Geschwindigkeit (High Velocity) zur Auswertung. Diese drei Eigenschaften werden oft auch als die 3V’s von Big Data bezeichnet.

1.1. Volumen: Menge der erzeugten Daten

Volumen bezieht sich auf die Menge der generierten Daten. Traditionelle Datenanalysemodelle erfordern typischerweise Server mit großen Speicherkapazitäten, bei massiver Rechenleistung sind diese Modelle nicht gut skalierbar. Um die Rechenleistung zu erhöhen, müssen Sie weiter investieren, möglicherweise auch in teurere proprietäre Hardware. Die NASA ist eines von vielen Unternehmen, die enorme Mengen an Daten sammeln. Ende 2014 sammelte die NASA alle paar Sekunden etwa 1,73 GB an Daten. Und auch dieser Betrag der Datenansammlung steigt an, so dass die Datenerfassung entsprechend exponentiell mitwachsen muss. Es resultieren sehr hohe Datenvolumen und es kann schwierig sein, diese zu speichern.

1.2. Vielfalt: Unterschiedliche Arten von Daten

Das  traditionelle  Datenmodell (ERM)  erfordert  die  Entwicklung  eines  Schemas,  das  die  Daten in ein Korsett zwingt. Um das Schema zu erstellen, muss man das Format der Daten kennen, die gesammelt werden. Daten  können  wie  XML-Dateien  strukturiert  sein,  halb  strukturiert  wie  E-Mails oder unstrukturiert wie Videodateien.

Wikipedia – als Beispiel – enthält mehr als nur Textdaten, es enthält Hyperlinks, Bilder, Sound-Dateien und viele andere Datentypen mit mehreren verschiedenen Arten von Daten. Insbesondere unstrukturierte   Daten haben   eine   große   Vielfalt.  Es   kann   sehr   schwierig   sein, diese Vielfalt in einem Datenmodell zu beschreiben.

1.3. Geschwindigkeit: Geschwindigkeit, mit der Daten genutzt werden

Traditionelle Datenanalysemodelle wurden für die Stapelverarbeitung (batch processing) entwickelt. Sie sammeln die gesamte Datenmenge und verarbeiten sie, um sie in die Datenbank zu speichern. Erst mit einer Echtzeitanalyse der Daten kann schnell auf Informationen reagiert werden. Beispielsweise können Netzwerksensoren, die mit dem Internet der Dinge (IoT) verbunden sind, tausende von Datenpunkten pro Sekunde erzeugen. Im Gegensatz zu Wikipedia, deren Daten später verarbeitet werden können, müssen Daten von Smartphones und anderen Netzwerkteilnehmern mit entsprechender Sensorik in  Echtzeit  verarbeitet  werden.

2. Geschichte von Big Data

2.1. Google Solution

  • Google File System speichert die Daten, Bigtable organisiert die Daten und MapReduce verarbeitet es.
  • Diese Komponenten arbeiten zusammen auf einer Sammlung von Computern, die als Cluster bezeichnet werden.
  • Jeder einzelne Computer in einem Cluster wird als Knoten bezeichnet.

2.2 Google File System

Das Google File System (GFS) teilt Daten in Stücke ‚Chunks’ auf. Diese ‚Chunks’ werden verteilt und auf verschiedene Knoten in einem Cluster nachgebildet. Der Vorteil ist nicht nur die mögliche parallele Verarbeitung bei der späteren Analysen, sondern auch die Datensicherheit. Denn die Verteilung und die Nachbildung schützen vor Datenverlust.

2.3. Bigtable

Bigtable ist ein Datenbanksystem, das GFS zum Speichern und Abrufen von Daten verwendet. Trotz seines Namens ist Bigtable nicht nur eine sehr große Tabelle. Bigtable ordnet die Datenspeicher mit einem Zeilenschlüssel, einem Spaltenschlüssel und einem Zeitstempel zu. Auf diese Weise können dieselben Informationen über einen längeren Zeitraum hinweg erfasst werden, ohne dass bereits vorhandene Einträge überschrieben werden. Die Zeilen sind dann in den Untertabellen partitioniert, die über einem Cluster verteilt sind. Bigtable wurde entwickelt, um riesige Datenmengen zu bewältigen, mit der Möglichkeit, neue Einträge zum Cluster hinzuzufügen, ohne dass eine der vorhandenen Dateien neu konfiguriert werden muss.

2.4. MapReduce

Als dritter Teil des Puzzles wurde ein Parallelverarbeitungsparadigma namens MapReduce genutzt, um die bei GFS gespeicherten Daten zu verarbeiten. Der Name MapReduce wird aus den Namen von zwei Schritten im Prozess übernommen. Obwohl der Mapreduce-Prozess durch Apache Hadoop berühmt geworden ist, ist das kaum eine neue Idee. In der Tat können viele gängige Aufgaben wie Sortieren und Falten von Wäsche als Beispiele für den MapReduce- Prozess betrachtet werden.

Quadratische Funktion:

  • wendet die gleiche Logik auf jeden Wert an, jeweils einen Wert
  • gibt das Ergebnis für jeden Wert aus
    (map square'(1 2 3 4)) = (1 4 9 16)

Additionsfunktion

  • wendet die gleiche Logik auf alle Werte an, die zusammen genommen werden.
    (reduce + ‘(1 4 9 16)) = 30

Die Namen Map und Reduce können bei der Programmierung mindestens bis in die 70er-Jahre zurückverfolgt werden. In diesem Beispiel sieht man, wie die Liste das MapReduce-Modell verwendet. Zuerst benutzt man Map der Quadratfunktion auf einer Eingangsliste für die Quadratfunktion, da sie abgebildet ist, alle angelegten Eingaben und erzeugt eine einzige Ausgabe pro Eingabe, in diesem Fall (1, 4, 9 und 16). Additionsfunktion reduziert die Liste und erzeugt eine einzelne Ausgabe von 30, der die Summe aller Eingänge ist.

Google nutzte die Leistung von MapReduce, um einen Suchmaschinen-Markt zu dominieren. Das Paradigma kam in der 19. Websearch-Engine zum Einsatz und etablierte sich innerhalb weniger Jahre und ist bis heute noch relevant. Google verwendete MapReduce auf verschiedene Weise, um die Websuche zu verbessern. Es wurde verwendet, um den Seiteninhalt zu indexieren und ein Ranking über die Relevant einer Webseite zu berechnen.

map(String key, String value): 
    //key: document name 
    //value: document contents 
    for each word w in value: 
        EmitIntermediate(w,"1"); 
     
reduce(String key, Iterator values): 
    //key: a word 
    //values: a list of counts 
    int result = 0; 
    for each v in values: 
        result += ParseInt(v); 
        Emit(AsString(result)); 

Dieses  Beispiel  zeigt  uns  den MapReduce-Algorithmus, mit dem Google Wordcount auf Webseiten ausführte. Die Map-Methode verwendet als Eingabe einen Schlüssel (key) und einen Wert, wobei der Schlüssel den Namen des Dokuments darstellt  und  der  Wert  der  Kontext  dieses Dokuments ist. Die Map-Methode durchläuft jedes Wort im Dokument und gibt es als Tuple zurück, die aus dem Wort und dem Zähler 1 besteht.

Die   Reduce-Methode   nimmt   als   Eingabe auch  einen  Schlüssel  und  eine  Liste  von  Werten an, in der der Schlüssel ein Wort darstellt. Die  Liste  von  Werten  ist  die  Liste  von  Zählungen dieses Worts. In diesem Beispiel ist der Wert 1. Die Methode “Reduce” durchläuft alle Zählungen. Wenn die Schleife beendet ist, um die Methode zu reduzieren, wird sie als Tuple zurückgegeben, die aus dem Wort und seiner Gesamtanzahl besteht.