Nach dem schmerzhaften zweiten Teil, der Installation, haben wir jetzt ein Hadoop-System zum Spielen. Es läuft lokal, reagiert aber wie ein echter Cluster (außer natürlich dass es nicht schneller sondern langsamer läuft, weil es nur pseudoverteilt ist). Und nach dem Spielzeug-Beispiel Wörter zählen können wir auch endlich einen Algorithmus implementieren, bei dem es einfach einleuchtet warum die Grenzen eines einzelnen Rechners schnell erschöpft sind. PageRank ist der Algorithmus, auf dem das Google-Imperium aufgebaut ist, benannt nach Gründer Larry Page, und nicht etwas nach den web pages die er bewertet (fragt sich nur, nach wem Facebooks Edgerank benannt ist). (Natürlich sehen wir hier nur die ganz einfache, ursprüngliche Variante.)
Die Aufgabe von PageRank ist es, die Wichtigkeit einer Webseite zu bewerten, die sich daran misste wie wahrscheinlich es ist dass man auf sie stößt, wenn man im Internet unterwegs ist. Das hängt davon ab, wieviele Links auf eine Seite verweisen, und wieviele Wege darüber auf die Seite führen. Bildlich – und glücklicherweise auch theoretisch – kann man das ganze als Graph darstellen:
Unser Mikro-Internet hier hat nur sechs Seiten und sieben Verlinkungen. Ein schneller Blick, wo die Links hinführen, zeigt schon dass B eine beliebtere Seite ist als E – drei einkommende Links für B, nur ausgehende für E.
PageRank
PageRank ist ein iterativer Prozess, wiederholt also mehrfach die gleichen Schritte bis ein Gleichgewicht erreicht ist. Der Algorithmus weist jedem Knoten (=Webseite) ein Gewicht zu, das zu Beginn gleich für alle Knoten ist, und am Ende so umverteilt wurde, dass die wichtigen Knoten (das wären dann die, die zuerst in der Google-Suche auftauchen) ein hohes Gewicht haben, so wie hier:
Wenn der Algorithmus richtig läuft, sollte sich die Verteilung der Gewichte nach einigen Iterationen nicht mehr groß verändern und der Prozess ist konvergiert.
In jedem Iterationsschritt verteilt jeder Knoten sein gesamtes Gewicht an alle Seiten, auf die er liegt. Im ersten Schritt würde also z.B. Knoten A je die Hälfte seines Gewichtes an Knoten B und D weitergeben. Da B von drei anderen Knoten Gewicht erhält, wird er am Ende der schwerste Knoten sein. A aber hat nur ausgehende Links, würde also mit Gewicht Null enden.
PageRank hat aber zwei Methoden, Knoten Gewicht zu geben, die Bewegungsmuster von Internetusern abbilden sollen. Mit hoher Wahrscheinlichkeit (z.B. 85 %) folgt ein Benutzer einem Link auf der Seite, die er gerade besucht. In den anderen Fällen bewegt er sich zu einer zufälligen Seite im Netz weiter, das ist also die Chance für A, doch noch ein paar Besucher abzubekommen.
Ein weiteres Problem stellt Knoten D dar, der zwar einkommende, aber keine ausgehenden Links hat – ein hängender Knoten. Würden wir den Algorithmus nicht daran anpassen, würde alles Gewicht (außer dem zufällig verteilten) zu D hinfließen. Die Lösung ist, in jedem Schritt das gesamte Gewicht von D gleichmäßig an alle Knoten zu verteilen )eigentlich an alle anderen, aber da Netzwerke meistens so gewaltig groß sind, kann man das vernachlässigen).
Das war auch schon das Prinzip. Es ist leicht, sich vorzustellen, dass auch nur Ausschnitte aus dem Internet so gewaltig viele Seiten und Links haben, dass kein einzelner Rechner das bewältigen kann. Glücklicherweise, wenn wir Mapper und Reducer richtig wählen, brauchen wir uns nicht darum sorgen, denn wir können die Aufgaben verteilen. Wie wir sehen werden, erfordern die hängenden Knoten allerdings, je Iteration zwei MapReduce Schritte zu verknüpfen. Wieder einmal – dies ist eine Lösung die funktioniert. Wie effektiv sie ist, da habe ich mir (noch) keine eingehenden Gedanken drüber gemacht.
MapReduce 1
Ich habe Skripte für die Mapper und Reducer und ein Shell-Skript für die Iterationen vorbereitet, außerdem eine etwas größere Beispieldatei als die oben im Bild. Peinlicherweise hab ich nur noch meine verarbeitete Datei gefunden, die ich mal aus einem (frei verfügbaren) Datensatz mit einem kleinen Netzwerk (~280000 Knoten) erstellt habe.
Wenn ihr die Skripte nicht aus dem Artikel kopieren möchtet, und die Beispieldatei haben wollt, klont euch einfach mein Git dazu:
Kommentare (1)