Pagerank berechnen

Eines von vielen Kriterien ist dabei die Anzahl anderer Seiten, die auf eine Seite im Netz verlinken. Vereinfacht dargestellt bildet diese Annahme auch die Grundidee hinter dem Pagerank-Algorithmus, mit dessen Hilfe Google die Relevanz einer Seite im Netz einschätzt. Dazu durchsucht Google fortlaufend das Web nach neuen Informationen und speichert dabei unter anderem die Verlinkungen zwischen den Seiten. Wer sich die Anzahl der Seiten und Links im Netz vorstellt, versteht sofort, wieso die parallelisierte Berechnung des Pagerank-Algorithmus eine der ersten Anwendungen von Map-Reduce bei Google war.

In Abbildung 2 ist die Berechnung der Anzahl eingehender Links für eine Seite mit Hilfe von Map-Reduce schematisch dargestellt. Die Eingabe besteht hier aus einer Menge von »(A,B)« -Paaren, die jeweils einem Link von Seite A nach Seite B entsprechen. Sie ist in zwei Blöcke mit jeweils sechs Einträgen unterteilt – in der Praxis umfasst die Eingabe natürlich sehr viel mehr Blöcke.

Abbildung 2: Schematischer Ablauf einer Map-Reduce-Berechnung. Der Mapper (links) wendet eine Funktion auf alle Schlüssel-Wert-Paare an, Shuffle sortiert sie nach dem Schlüssel und der Reducer (rechts) errechnet zu jedem der Schlüssel ein Ergebnis.

Jeden Block der Eingabe weist das Framework einem Mapper zu, der die Map-Funktion auf jeden Eintrag aus dem Block anwendet. Um die Anzahl der Seiten zu zählen, die auf eine bestimmte Seite verlinken, bietet es sich an, das Ziel des Links (zweiter Wert im Eingabe-Paar) als Schlüssel für die Ausgabe der Map-Funktion zu verwenden, da im weiteren Verlauf alle Paare mit dem gleichen Schlüssel zusammengefasst werden. Als Wert für die Ausgabe der Map-Funktion dient die Zahl 1, die signalisiert, dass es einen Link auf die entsprechende Seite gibt (Listing 1).

01 method Map(source,target)
02   emit(target,1)
03 end

Sortieren und aggregieren

Die Shuffle-Phase fasst alle Ausgaben der Map-Phase mit identischem Schlüssel zusammen, sortiert und verteilt sie auf die Reducer. Folglich gibt es für jede verlinkte Seite genau ein Paar mit der entsprechenden Seite als Schlüssel und einer Liste von Einsen als Wert. Der Reducer wendet dann die Reduce-Funktion auf jedes dieser Paare an. In diesem Fall muss sie einfach die Einsen in der Liste summieren (Listing 2).

01 method Reduce(target,counts[c1,c2,...])
02   sum <- 0
03   for all c in counts[c1,c2,...] do
04     sum <- sum + c
05   end
06   emit(target,sum)
07 end

Beim Betrachten des schematischen Ablaufs fällt schnell auf, dass ein Mapper durchaus mehrere Schlüssel-Wert-Paare für eine Seite erzeugen kann. In der Ausgabe des Mappers für Block 1 kommt beispielsweise gleich zweimal das Paar »(B,1)« vor, denn in Block 1 gibt es zwei Links auf Seite B.

Auffällig ist zudem, dass erst der Reducer die Werte aggregiert. Abhilfe schaffen im Hadoop-Framework so genannte Combiner, die die Ausgaben eines Mappers aufbereiten, bevor sie über das Netzwerk zum Reducer geschickt werden, um so die Menge der übertragenen Daten zu reduzieren.

In diesem Beispiel kann der Combiner einfach alle Ausgaben eines Mappers bezüglich einer Seite zusammenfassen und summieren (siehe Abbildung 3). Combiner lassen sich aber nicht immer sinnvoll in den Ablauf integrieren und sind daher optional. Der Benutzer muss jeweils für seinen konkreten Anwendungsfall entscheiden, ob ein Combiner eine Verbesserung bringt oder nicht.

Abbildung 3: Der Einsatz so genannter Combiner ist optional. Vor allem bei arithmetischen Operationen kann er jedoch die Auslastung des Netzwerks verringern, indem er die große Anzahl von Zwischenergebnissen auf wenige Elemente reduziert.