Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Hadoop)

1 Feb

Mit der Near copy detection Anwendung sollen großen Mengen an Publikationen untersucht werden können. Um dies zu gewährleisten habe ich mich für Apache Hadoop als Paralellisierungsframework entschieden. Hadoop ist eine Opensource Framework dass das Map Reduce Paradigma von google umsetzt. Hierzu benötigt wird außerdem ein verteiltes Dateisystem das in Form von HDFS ( Hadoop Distributed File System) mitgeliefert wird.

Map-Reduce: Das Map-Reduce Pattern wurde von Google (link) beschrieben, es handelt sich hierbei um eine Methode zur Verarbeitung großer Datenmengen in einem Cluster von Rechnern. Map Reduce verarbeitet die Daten in zwei Hauptschritten (Map und Reduce) die durch einige generische Schritte gekoppelt sind:

  • Map: Die Daten werden von dem Speichermedium eingelesen und in Splits an die Map Prozesse verteilt. Splits sind eine Teilmenge der Daten, zum Beispiel 64MB Blöcke, die an die einzelnen Map Instanzen verteilt werden. Der Map Prozess verarbeit den Split und erzeugt eine Map als Ergebnis. Am Beispiel eines Wordcounts enthält diese Map als Key jedes Wort und als Value das aufkommen des Wortes in diesem Split.
  • Shuffel and Sort: Die ergebniss Mengen werden auf alle Reducer verteilt (Shuffel). Dies kann zum Beispiel mit einer Hashfunktion passieren. Da es wahrscheinlich mehr Mapinstanzen geben wird als Reduceinstanzen bekommt jede Reduceinstance 1 bis #Mapinstanzen viele Ergebnismaps. Diese werden in einen merge Schritt vereinigt und sortiert. Dieser Schritt stell auch sicher das das ein Key nur zu einem bestimmten Reducer kommt,  es ist also ausgeschlossen das zwei Reducer des gleichen Key erhalten.
  • Reduce: Der Reduceschritt bekommt als Eingabe eine Map, also beim Wordcount Beispiel mit den Wörtern als Key und einer Liste über aller Value Ergebnisse der Mapper als Value. Die Reducerinstance kann nun alle values zusammen addieren und erhält die Anzahl eines Wortes der kompletten Eingabedaten.

Durch diese Aufteilung können die behandelten Probleme gut mit der Anzahl der Rechner im Cluster skaliert werden.

HDFS: Das verteile Filesystem von Hadoop ist optimiert auf das ausführen von Map-Reduce-Jobs. Große Files werden in Blocke eingeteilt (Standard 64MB). Dies Blöcke werden über alle Datanodes im System verteilt. Hier durch wird eine hohe Parallelität bei Lesen gewährleistet. Die Datanodes sollten zusammen mit den Rechennodes auf den gleichen Rechnern liegen. Sodass das verarbeiten der Daten möglichst Datenlokal geschieht, also kein Netzwerkverkehr benötigt wird.

Als Testinstance habe ich ein 5 Knoten großes Cluster aufgebaut das in Wolles Büro steht. Dieses Cluster verfügt über einen Masterknoten (Dual Core Pentium 4), vier Rechenknoten (3xquadcore Pentium4 und 6 Cores von Imhotep XEON Pentium4). Die Rechenknoten haben dann insgesamt 18 Cores, 30GB RAM, 2.8TB HDD.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: