XML, Text, Hadoop, CouchDB und die Google Search Engine

Größere Datenmengen bringen deutlich andere Herausforderungen mit sich. Durch eine Teststellung ergab sich eine Herausforderung, deren Lösung eine kleine Evolution durchgemacht hat. Ziel des Vorhabens ist, jedes Element aus der ersten Menge mit einer unbekannten Anzahl von weiteren Informationen aus der zweiten Menge anzureichern und das Ergebnis zu einer für die Google Search Appliance brauchbaren HTML Seite zu vereinen.

Ausgangssituation

• 18 Gbyte XML Daten in einzelnen Dateien
• ca. 60 Gbyte “Metadaten” in einzelnen Dateien (JPG, HTM, XML) und einer 1:n Zuordnung zu den XML Daten aus dem ersten Punkt

In den XML Daten, nennen wir sie mal “Produkte”, gibt es zu jedem Produkt verschiedene Typen von Metadaten. Dies können Bilder, erweiterte Beschreibungen und sonstige Zusatzinformationen sein. Jedes Produkt hat mindestens eine eindeutige ID aus einem von zwei Nummernkreisen. Diese ID findet sich ebenfalls im Dateinamen der zugehörigen Metadaten wieder. Die Anzahl der Produkte liegt bei ca. 5,7 Mio.

Beispiel: Produkt 4711 -> Produktbilder/Bild_4711_Ansicht1.jpg

Der erste Ansatz ist es, bei einer Iteration durch alle Produkte, jeweils alle Metadaten zu finden. Hier kann ein kleiner Shell Aufruf schon ausreichen:

find . -name "*_4711_*" -type f

Dabei sollte 4711 natürlich durch den aktuellen Wert des Produktes ersetzt werden. Wer nun die Hände über dem Kopf zusammenschlägt und I/O Probleme wittert, dem sei gesagt … yes! Ist verflucht lahm.

Kurz ein paar Variabeln definiert

p = Produkt

C(p) = Count(Produkt) -> ca. 5.700.000

m = eine Metainformation

C(m) = Count(m) Gesamtanzahl der Metadaten -> ca. 25.000.000

k = Konstante für die Kosten des I/O Seek auf der HDD, hier in Sekunden gemessen.

Laufzeiten

Bei einer Laufzeit von O(C(p) * C(m)) ist die Platte (Seek I/O) hier sicherlich noch als Konstante zu sehen, womit sich O(C(p) * C(m) * k) ergibt und nach erster Beobachtung k > 8 ist. Ohne es bewiesen zu haben, liegt die errechnete Laufzeit bei weit mehr als einem Jahr ;).

Die nächste Variante war per find ein Directory Index zu erstellen, also find über alle Verzeichnisse zu schicken und das Ergebnis in Textdateien zu Speichern. Diese Textdateien kann man mit grep durchsuchen. Auch hier entsteht eine Laufzeit von O(C(p) * C(m) * k), wobei sich k = 8 herausstellte. Auch hier liegt die Laufzeit bei ca. einem Jahr.

Die Anzahl der Metadaten pro Produkt spielt keine Rolle, da immer die gesamte Menge an Metadaten durchsucht werden muss.

Das Problem bei beiden Ansätzen besteht deutlich in der Multiplikation der Ergebnismengen. 142.500.000 Operationen sind auch ohne Konstante schon eine viel zu große Menge.

Was kann man also tun, damit man die Multiplikation los wird? Es müsste eine Möglichkeit geschaffen werden, dass der Iterator nur eine “Anfrage” an die Ergbnismenge stellen muss und daraufhin alle Metadaten zurück geliefert werden – alternativ ist die Menge 0 auch eine valide Antwort. Um dies zu erreichen brauchen wir einen Index, der auf Basis eines Schlüssels eine Liste von Werten zurück geben kann. Dieser Index muss einmalig befüllt werden. Die technologische Entscheidung fiel hier auf Hadoop für die Vorbereitung der Daten, ein PHP Script zum Einfügen der Daten in den Index und eine CouchDB als eigentlicher Index. Vorteil bei dieser Konstellation ist, dass CouchDB über HTTP angesprochen werden kann. Es gibt also nur zwei Möglichkeiten für die Antwort auf die Frage nach dem Schlüssel: HTTP 200 OK oder HTTP 404 NOT FOUND. Sicherlich könnte man dies auch über Redis abbilden, jedoch war die Anbindung der CouchDB einfacher und schneller für diesen Anwendungfall.

Wir führen neue Variabeln ein

h = Vorbereitungszeit Hadoop Map & Reduce

v = Vorbereitungszeit für den Index

r = Konstante für die Kosten eines HTTP Requests, ebenfalls in Sekunden gemessen.

Wenn wir unsere Rechnung unter den neuen Gesichtspunkten aufsetzen, ergibt sich O(h + v + C(p) * r). Durch die Nutzung der Loopback Device konnten wir r = 0.2 erreichen. Die Konstanten h und v sind im Vergleich zur voherigen Multiplikation nahezu lächerlich klein. h liegt bei 146 Sekunden und v bei ca. 600 Sekunden.

Hadoop als Vorbereiter

Die im find vorbereiteten Daten werden nun zu 60Mbyte Blöcken zusammengefasst. Hierbei hilft uns ein kleines PHP Script. Man kann hier auch die von Hadoop angebotene Klasse CombineFileInputFormat verwenden. Die neu geschaffenen Dateien kommen dann auf das HDFS und sind damit für den Map & Reduce Schritt verfügbar.

Der Map Job ist recht simpel. Das Ergebnis des finds wird zeilenweise an die Map Methode geliefert. Der LongWritable key ist der byte-Offset, der Text value ist die Zeile selbst.

public void map(LongWritable key, Text value, OutputCollector output, Reporter reporter) throws IOException {
        final String line = value.toString();
        final String[] parts = line.split("/");
                
        if (parts.length > 1) {
                final String filename = parts[parts.length-1];
                final String[] fileParts = filename.split("_");
                
                final StringBuilder sb = new StringBuilder();
                sb.append(fileParts[1]);
                sb.append(fileParts[0]);
                
                keyVal.set(sb.toString());
                valVal.set(line);
                
                output.collect(keyVal, valVal);
        }
        else {
                reporter.incrCounter("org.apache.hadoop.mapred.Task$Counter", "MAP_SKIPPED_RECORDS", 1);
        }
}

Wenn der Mapper alle Values, in unserem Fall also die Pfade, zu den Keys, also den IDs, gefunden hat, wird das Ergebnis an den Reducer weitergeleitet. Der Reducer iteriert über alle Values zum Key und erstellt bereit einen String, der später als Liste in JSON weiterverwendet werden kann.

public void reduce(Text key, Iterator values,
                        OutputCollector output, Reporter reporter) throws IOException {
                        
                StringBuilder sb = new StringBuilder();
                sb.append('[');
                while (values.hasNext()) {
                        sb.append('"');
                        sb.append(values.next().toString());
                        sb.append('"');
                        if (values.hasNext())
                                sb.append(',');
                }
                
                sb.append(']');
                outVal.set(sb.toString());
                output.collect(key, outVal);
        }

Die Ausgabedatei, die der Reducer schreibt ist ca. 300 Mbyte groß. Den Abschluss der Vorbereitung ist wieder ein PHP Script, welches pro 10.000 Zeilen der Ausgabedatei einen Batch Request an die CouchDB absetzt. Für die 5.700.000 Zeilen, die die Ausgabedatei beseitzt, sind das ca. 600 Sekunden.

Der abschließende Prozess ist nun die Zusammenführung von Produkten und Metadaten. Hierzu gibt es ein Java Projekt, dessen Sourcen ich hier leider nicht zeigen darf ;). Es entstehen HTML Seiten und Link-übersichtsseiten, welche der GSA zum Crawling vorgesetzt werden.

Dieser Crawling Prozess dauert unter Verwendung von CouchDB nur noch ca. 3 Tage statt mehr als 400 Tage. Ein deutlicher Gewinn ;).

Bei nächster Gelegenheit schreibe ich noch ein FollowUp zusammen, da eine Alternative zu CouchDB auch Redis sein könnte.