Archive by Author

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Optimieren einer MapReduce Jobkette oder Datenstrukturen, Datenstrukturen, Datenstrukturen und an die Algorithmen denken!

29 Jul

Ich habe in letzter Zeit einen Algorithmus zur near copy detection (NCD) in MapReduce für Apache Hadoop implementiert und dabei erst richtig gelernt, was es eigentlich heißt, mit Big Data umzugehen. Ich habe den Algorithmus mittlerweile das dritte mal implementiert und unzählige (> 100) Versionen, in denen immer wieder Optimierungen eingeflossen sind, erstellt. Hier ein kleine Geschichte von Datenstrukturen und Algorithmen und vielen vielen Daten.

Ich teste meinen Algorithmus mit einem Satz von Testdaten, der 230.000 verschiedene Sätze und 124.000 verschiedene Worte umfasst. Der Algorithmus ist eine Implementierung von Fuzzysets, die die Ähnlichkeit zwischen Sätzen berechnen. Der erste Schritt ist für jeden Satz der gegen den Hintergrundkorpus geprüft werden soll einen Liste an Zielsätze zu finden, die eine gewisse Ähnlichkeit zum Quellsatz haben, um nicht den Quellsatz gegen alle Sätze des Korpus prüfen zu müssen. Hierfür baue ich eine Lookuptabelle auf, in der alle Worte auf die Sätze abgebildet sind die sie enthalten, also ein inverser Index. Hiermit können alle Sätze ermittelt werden, die z.B. zumindest ein Wort mit dem Quellsatz gemein haben. Der nächste Schritt umfasst das Holen der Zielsätze und die Berechnung der Ähnlichkeiten zum Quellsatz. Hierfür habe ich eine Tabelle die die Termfrequenzen für alle Sätze enthält. Die Sätze haben als ID einen MD5Hash über die alphabetisch geordnete Menge der Worte des Satzes („Das ist ein Haus und ein Auto“ = MD5Hash (autodaseineinhausistund)). Dies garantiert eindeutige Hashes, da die Anordnung der Worte für Fuzzyset unwichtig ist. Als letzter Schritt sollen die Ergebnisse weggeschrieben werden. Die drei Version des Algroithmuses unterscheiden sich hauptsächlich in der Anzahl und der Funktion der MapReduce Jobs. Waren es in der erst noch drei Jobs, so waren es in der zweiten 9 und in der dritten vier. Die Ausführungszeiten und die Größe der Zwischenergebnisse unterscheiden sich in den drei Versionen drastisch, so variierte die Ausführungszeit auf meinem Testsatz zwischen 2 Stunden in der dritten Version und >16Stunden in der zweiten. Auch die Größe der Zwischenergebnisse variierte drastisch. In der zweiten Version ca. 6Tb und in der dritten <3Gb.

Ein paar Kleinigkeiten die ich schmerzlich gelernt habe stehen unter den Motto „Datenstrukturen, Datenstrukturen, Datenstrukturen und an die Algorithmen denken!“. Einige Beispiele werden im Folgenden näher erläutert:

Datenstrukturen 1
Was der Begriff BigData bedeutet, habe ich festgestellt als ich darüber nachdachte, ob ich ein Integer sparen sollte oder ob ich mir den Luxus gönne. :-) (Ich fühlte mich in die Zeit versetzt als man beim 386er jedes Byte im untern Speicherbereich gespart hat um ein bestimmtes Spiel zu starten können). Hierbei ging es um die Frage, wie ich die md5 Hashes meiner Satzids speichern sollte. Hadoop stellt ein Objekt zur Speicherung von dynamisch langen Bytearrays zur Verfügung (BytesWritable). Nach meiner ersten Implementierung der Kandidatenauswahl hatte ich 3Mrd Vergleiche von Satzpaaren, was sich in 6Mrd. Ids niederschlägt. Das ByteWirtable speichert einen Integerwert für die Länge des Bytearray und das Array an sich. Da die Länge bei md5 aber fix mit 16Byte ist, sind die 4Byte für das Längenint überflüssig. Ein anderes Objekt von Hadoop, MD5HashWritable, speichert nur ein Bytearray, mit der fixen Größe von 16Byte. Das macht 25% Overhead (24Gb) bei 96GB für die ids. Es lohnt sich über die Datenstrukturen nachzudenken, denn ein gespartes Int kann mal schnell drei DVDs ausmachen.

Datenstrukturen 2
Ein weiteres Beispiel, warum es sinnvoll ist, eigene spezielle Datenstrukturen zu verwenden, anstatt von generischen, zeigt sich am Objekt MapWritable von Hadoop. Es ist zwar praktisch ein Objekt zu haben in dem die verschiedensten Writables gespeichert werden können, aber im Fall von sehr vielen kleinen Elementen auch Nachteile mit sich bringen kann. Das MapWritable speichert für jedes Key und Value jedes Elements den Datentyp als fully qualified String. Wenn beispielsweise nur IntWritable’s gespeichert werden sollen, ergibt das einen Overhead von 800% („org.apache.hadoop.io.IntWritable“ = min. 32Byte gegen Integer=4byte). Auch dies kann durch eine spezialisierte Datenstruktur vermieden werden und vermindert die Datenmenge extrem.

Datenstruktutren 3
Die Laufzeit des  Sort and Shuffle Prozess, zwischen Map und Reduce, wird maßgeblich durch die Menge der zu sortierenden Daten dominiert. In einer Version habe ich in der Map Phase die Kandidaten zu einem Quellsatz gesucht und dann die ids von Quell und Zielsatz zu einem 32Byte langen Bytearray kombiniert. Dieses Bytearray habe ich dann als Key zusammen mit einem leeren Value an die Reduce Phase gesendet. Das hat den Vorteil, dass eine totale Ordnung entstand. Der Nachteil bestand darin, dass viel Zeit zum Sortieren benötigt wurde.   Des Weiteren wurde die totale Ordnung auch nicht weiter benötigt. Hierbei werden dann 6Mrd. Elemente sortiert und geshuffelt, dann wird 6Mrd. mal die reduce Methode aufgerufen mit leeren iterable Values. Im Vergleich dazu, wenn nur die Quellid als key und die Zielids als Value zur Reduce Phase übertragen wird, fallen nur ca. 200.000 zu sortierende Elemente an und die reduce Methode wird auch nur 200.000 mal aufgerufen mit gefüllten iterable Values. Das brachte eine enorme Zeitersparnis, die mehrere Stunden umfasste.

Algrithmen
Bei meinem Ansatz hat sich herausgestellt, dass der Random Access auf die Lookupdaten in HBase die meiste Zeit beanspruchte. Hier gilt es noch eine bessere Lösung zu finden. Ich denke hier könnte PIG hilfreich sein. Auch zu große Zwischenergebnisse (Mehrere TByte) oder zu viel Sortierarbeit waren ein großes Hindernis. Schlussendlich kann ich sagen, dass ich aus den vielen Wochen der Optimierungsarbeit viel über die Funktionsweise von MapReduce gelernt habe und für den nächsten Algorithmus eine komplett andere Herangehensweise benutzen würde.

PS.: BigData stimmt bei diesem Artikel auch für die Überschrift.:-)

Kurzmitteilung

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Benchmark 2

18 Mrz

Das neue Cluster ist fertig und funktioniert. Wir haben zu unseren bestehenden Cluster von 3XCore2 quad Maschinen und Imhoteps sechs Kernen, um 14 neue Sechskernmaschinen erweitert. Mit den neuen und den alten Maschinen kommen wir also auf 102 Kerne!

Wir haben uns für die neuen Maschinen für AMD FX 6100 Prozessoren entschieden. Dieser taktet seine 6 Kerne mit bis zu 3,3GHz und hat in einer Preis/Leistungsabwägung gut abgeschnitten. Der Prozessor sitzt auf einem Asus M5A88-Mainboard das mit 4X4GB Ram besückt ist.

Damit die Prozessoren auch immer gut mit Daten versorg werden können haben wir uns entschieden jedem Rechner vier Festplatten zu spendieren. Hier haben wir uns für Seagate Barracuda Green 2TB entschieden. Diese sorgen im Clusterverbund für eine gewaltige Bandbreite. So hat sie in einem Schreibtest eine Bandbreite von 830MB/sec (zweifach redundant, also jeder Datenblock wird drei mal geschrieben. Hieraus ergibt sich 2,4GB/sec) ergeben.

Das ganze wurde in T5 Gehäuse von Sharkoon eingebaut. Diese waren recht Preiswert und haben eine gute Kabelführung. Die Stromversorgung übernehmen 400Watt Netzteile von Sharkoon.

Die Rechner des alten Clusters und die neuen Rechner sind mit einen eigenen 1Gbit Switch verbunden.

Insgesamt kommen wir auf :

18 Workernodes
102 Cores (12xCore2 Quad 2,8GHz, 6xIntel Xeon 2,9GHz, 96x AMD FX 6100 3,3GHz)
260GB Ram (3x8GB, 1x12GB, 14x16GB)
115TB HDD (56x2TB, 1x500GB, 9x330GB)

Auf allen Workernodes läuft Ubuntu Server. Das Hadoop Framework wird mit Konfiguration vom Master kopiert und mit Java 1.6 ausgeführt (Ich habe mich hier für java 1.6 entschieden da sich Java 7 in Bezug auf Stringverarbeitung anders verhält).

Neben der Verwendung als Rechencluster, ist es auch sehr dekorativ und nützlich als Heizung an kalten Tagen. :-)

Hier einige Zeiten aus meiner Masterarbeit die ich mit einem Setup von 90 Kernen gemacht habe. Als Testdokumente habe ich 43.000 Paper aus der Computer Science genommen. Diese Paper haben ein Gesamtgröße von knapp 30GB. Auf diesem Datensatz habe ich fünf meiner MapReduce Job ausgeführt, diese haben die unten beschriebenen Funktionen.

PDFToText+Hyphenationremoval+Footer-Headerremoval: 1,35 Sekunden/Core/Dokument | 0,015 Sekunden/Dokument

Sentence+Tokensplitting+POS: 2,34 Sekunden/Core/Dokument | 0,026 Sekunden/Dokument

Lemmatizer: 23,4Sekunden/Core/Dokument | 0,260 Sekunden/Dokument (Der Lemmatizer ist gerade auf deutschen Texten sehr langsam)

Stemmen+Stopword+Numberremoval+Symbolremoval: 0,171 Sekunden/Core/Dokument | 0,0019 Sekunden/Dokument

Wordnet Synonymfindung: 43,2 Sekunden/Core/Dokument | 0,480 Sekunden/Dokument

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Stemming, Stopword, Numberremoval, Symbolremoval)

2 Mrz

Dies ist der vorerst letzte Artikel zum Thema Textvorverarbeitung. Hier werden kurz die Techniken Stemming, Stopworts, Numberremoval und Symbolremoval, die ebenfalls als API und Hadoop Map-Reduce implementiert sind, beschrieben. Die folgenen Artikel werden sind mehr mit dem Detectieren von kopierten stellen und der Verarbeitung mittels Hadoop  zu tun haben.

Weiterlesen

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Was bisher geschah! (Wordnet;Synonym findung)

27 Feb

In dem nächsten spannenden Teil meiner Blogserie „ODIN! Was bisher geschah!“ widme ich mich dem Desynonymifizieren (entfernen von Synonymen wegen der Aussprache). Oft werden kopierte Textstellen abgewandelt um die Herkunft zu verschleiern. Diese Abwandlungen können sein, dass Umstellen von Sätzen, das Entfernen oder Hinzufügen von Worten, das Ändern von numerischen Werten oder das austauschen von Worten gegen Synonyme. Die letzte Möglichkeit ist Thema diese Blogposts.
Weiterlesen

Kurzmitteilung

Masterarbeit: Near Copy Detection in large text corpora (ODIN): Benchmark

21 Feb

In diesem Blog wollte ich ein paar Zwischenergebnisse des Hadoop Clusters auflisten. Das Cluster besteht momentan aus 4 Workernodes mit insgesamt 18 Cores (4,4,4,6 / Core2 2,8GHz) die alle ungefähr gleich schnell sind. Die Rechner sind mit insgesamt 7 Platten (3,3,3,1) ausgestattet und haben pro Core 2GB Ram. Der Testdatensatz umfasst ca. 43.000 PDFs mit einer gesamt Größe von ca. 27GB. Die aufgelisteten Werte drücken die Bearbeitungszeit eines Dokuments auf einen Core aus, dahinter die Bearbeitungszeit eines Dokuments auf den gesamten Cluster (geteilt durch die Anzahl der Cores).

PDFToText+Hyphenationremoval+Footer-Headerremoval: 0,074 Sekunden/Core/Dokument | 0,00411 Sekunden/Dokument

Sentence+Tokensplitting+POS: 1,828 Sekunden/Core/Dokument | 0,1015 Sekunden/Dokument

Lemmatizer: 11,554 Sekunden/Core/Dokument | 0,64189 Sekunden/Dokument

Stemmen+Stopword+Numberremoval+Symbolremoval: 0,111 Sekunden/Core/Dokument | 0,00617 Sekunden/Dokument

Daraus ergibt sich eine gesamt Zeit von 0,75367 Sekunden pro Dokument. Diese Zeit wird dominiert durch das Lemmatisieren was API-bedingt ist.