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.:-)

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: