InWissenswertes

Architektur von Google

Den Aufbau von Google zu analysieren gestaltet sich schwierig, da keine Veröffentlichung über Architektur und Struktur der derzeitigen Arbeitsweise von Google einzusehen ist.

Die Wirtschaftswoche schreibt bspw. über das Unternehmen: “kaum ein anderes börsennotiertes Unternehmen geizt so mit Informationen über sich selbst.” Doch es gibt Informationen über die Anfänge von Google und daraus kann das Grundprinzip der bestehenden Algorithmen abgeleitet werden.

Google besitzt eines der weltweit größten verteilten Suchmaschinenarchitekturen. Sie besteht aus über 15.000 Rechnern  die durch ein highspeed Intranet verbunden sind und bildet somit eines der weltweit größten Linux Cluster. Dieses Cluster ermöglicht eine hochgradig parallele Verarbeitung auf verschiedenen Einzelrechnern bzw. Prozessoren und somit einer der Gründe für die schnellen Antwortzeiten bei der Suche mit Hilfe von Google.

In unten stehendem Bild werden die Funktionsweise und der Aufbau der derzeit weltweit größten Suchmaschine dargestellt. Die Objekte in Form einer Tonne stellen die Datenstrukturen dar und die Objekte in Ellipsenform Applikationen. Die aufgezeigte Architektur lässt sich in drei Hauptbestandteile gliedern. Bei denen Bereichen handelt es sich um Crawling, Indexing und Searching.  Folgendes Schaubild soll dazu dienen, einen Überblick darüber zu erhalten, wie die Architektur von Google gestaltet ist.

 

Googles Crawler werden von einem URL Server mit zu besuchenden Internetadressen versorgt. Die besuchten Seiten werden durch den Store Server komprimiert und in der Repository abgelegt. Zeitgleich zu diesem Arbeitsschritt erhält jedes noch nicht betrachtete Dokument eine eindeutige Nummer, welche als docID bezeichnet wird und aus der übergebenden URL ermittelt wird. Dieses Vorgehen unterscheidet sich nur unwesentlich von dem beschriebenen Verfahren der allgemeinen Architektur.

In einem nächsten Schritt werden die Dokumente vom Indexer aus der Repository ausgelesen, dekomprimiert und analysiert. Die betrachteten Webseiten werden in eine Liste umgewandelt, welche die Häufigkeit des Auftretens der einzelnen Wörter innerhalb der Seite erfasst und als Hits bezeichnet. Die so erzeugten Hits enthalten neben dem Wort selbst weitere Meta-Informationen, wie z. B. die Position innerhalb des Dokumentes oder die relative Schriftgröße. Die Hits werden nun mittels des Indexers auf eine Reihe von Barrels aufgeteilt, wodurch ein teilweise sortierter Forward Index entsteht. Diese Aufteilung auf viele, relativ kleine Barrels geschieht, damit ein hoher Grad an Parallelität innerhalb der Verarbeitung ermöglicht wird. Der Indexer erfüllt noch eine weitere wichtige Aufgabe. Durch ihn werden alle Links einer Seite analysiert und mit zusätzlichen Informationen innerhalb der Anchors-Datei gespeichert. Die gespeicherten Informationen beinhalten zum einen, wohin ein Link verweist und auf welcher Seite er sich befindet, zum anderen den Text den der Link enthält, den so genannten Anchortext.

Mittels des URL Resolvers werden nun aus den relativen Links innerhalb der Anchors-Datei die entsprechenden absoluten URLs errechnet, die im weiteren Verlauf in docIDs konvertiert werden. Der Anchortext wird den Informationen der so ermittelten docIDs innerhalb des Forwarded Indexes hinzugefügt. Durch die mittels des URL Resolvers gewonnenen Informationen wird der Link-Graph konstruiert, mit dessen Hilfe der PageRank, dass von Google verwendete Wichtigkeitsmaß, berechnet werden kann. Der PageRank stellt Googles zentralen Unterscheid gegenüber der allgemeinen Suchmaschinenarchitektur dar.

Ein weiteres Element der Architektur von Google ist der Sorter. Seine Aufgabe ist es, den nach docID sortierten Forwarded Index in einen nach wordID sortierten Inverted Index zu transferieren. In vielen anderen Suchmaschinenarchitekturen ist der Sorter im Indexer enthalten. Ein weiteres Programm namens DumpLexicon erstellt mittels des Inverted Indexes und des Lexicons ein neues aktuelleres Lexicon. Das Lexicon ist eine Datenstruktur, die für jede gültige wordID einen Zeiger auf das jeweilige Barrel beinhaltet, in dem sich die wordID befindet. Dieses Lexicon wird vom Searcher
zusammen mit dem Inverted Index und dem PageRank benutzt, um die Anfragen der Benutzer zu beantworten.  Die nachstehende Tabelle veranschaulicht einen Invertierten Index.

WordID   DocID (Zeiger)
004532    000034, 001243, 000872, 007360
002176    000237, 371613, 002371, 927872
093278    000281, 287301, 984590, 298732

Das grobe Vorgehen von Google unterscheidet sich hauptsächlich durch die
Verwendung des PageRanks von anderen Suchmaschinen. Der PageRank selber wird unter dem Punkt Bewertungsverfahren erklärt.

Mehr Informationen zur Arbeitsweise der Internet-Crawler gibts über “Weiter”.


Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *