Inhaltsverzeichnis

  INHALTSVERZEICHNIS  II

1.  EINLEITUNG  1

2.  GOOGLE  2

2.1  DIE GOOGLE-GESCHICHTE  2

2.2  GOOGLE APPLIKATION  2

2.3  SYSTEM HARDWARE  4

3.  GOOGLE FILE SYSTEM  5

3.1  DESIGN ÜBERBLICK  5

3.1.2  Master Metadaten  6

3.2.  SYSTEMINTERAKTIONEN  9

3.2.1  Mutationsreihenfolgen  9

3.3  MASTEROPERATIONEN  13

3.4  FEHLERTOLERANZ ZUVERLÄSSIGKEIT UND VERFÜGBARKEIT  16

3.5  DATENFLUT UND WORKLOAD  17

3.5.3  Master und Chunkserverworkload  18

4.  ZUSAMMENFASSUNG  20

  LITERATURVERZEICHNIS  21

1. Einleitung

Die Bedeutung der Suchmaschine Google hat in den letzten Jahren sehr stark zugenommen. Durch die immer komplexer werdenden Googleapplikationen sowie die immer stärkere Nutzung der Suchmaschine ist die zu verwaltende Datenmenge in den letzten Jahren stark angewachsen. Dies war die Ursache für die Entwicklung neuer Konzepte, um eine konsistente Datenhaltung und -verwaltung sowie eine schnelle Datenrettung zu ermöglichen. Im Mittelpunkt dieser Entwicklung steht die Sicherung der Performance des Systems, das Milliarden von Dokumenten verwaltet und mehrere Tausende Treffer pro Suchanfrage nach Relevanz ordnet. Der Umfang und die Komplexität des Systems stellen dabei sowohl besondere Herausforderungen an die einzusetzende Hardware, als auch an die Konzepte der Datenverteilung und -sicherung. Eine neue Entwicklung ist dabei der Verzicht auf teure Spezialhardware. Alle Anwendungen laufen auf gewöhnlicher PC-Hardware und sind somit sehr wirtschaftlich im Vergleich zu teurerer Spezialhardware. Durch den Einsatz gewöhnlicher PC-Hardware sind Ausfälle von Festplatten oder ganzer Server wesentlich wahrscheinlicher, es wird sogar mit dem Ausfall von Systemen gerechnet. Dass Anwendungen dennoch so zuverlässig und schnell funktionieren, liegt an der Struktur des von Google entwickelten Dateisystems. Das Google File Systems (kurz GFS) bietet eine hohe Fehlertoleranz, Fehler werden automatisch entdeckt und Wiederherstellungen automatisiert ausgeführt, so dass die Nachteile der Hardwarekonfiguration abgefangen werden können. Dieser Fehlertoleranz kommt bei multiplen Clustern mit Größen von bis zu 300 TB sowie mehreren hunderten Clientzugriffen sehr große Bedeutung zu.

Eine weitere strukturelle Besonderheit des Google File Systems stellt die Verwaltung von Schreibzugriffen dar. Bestehende Dateien werden nicht durch schwer zu kontrollierende Schreiboperationen, sondern vielmehr durch leichter zu verwaltende „Append“ Operationen erweitert. Es ist somit möglich, dass viele Nutzer gleichzeitig auf größere Dateien schreibend zugreifen, ohne dass eine ständige Synchronisation zwischen diesen Nutzern stattfinden muss.

Die dadurch realisierten Vorteile bezüglich Performance, Verlässlichkeit und Verfügbarkeit sowie die daraus resultierenden Anforderungen an das System sollen im Mittelpunkt dieser Arbeit stehen. Es soll ein Einblick in die Funktionsweisen und Komplexitäten des Google File Systems gegeben und weiterhin die strukturelle Umsetzung der Anforderungen aufgezeigt werden.

1

2. Google

2.1 Die Google-Geschichte

Die Geschichte von Google ist eine überaus erfolgreiche. Google wurde von Larry Page und Sergey Brin [BP, S.18], zwei Stanford-Studenten, entwickelt. 1998 startete Google als Beta-Version, ein Jahr später wurde die Suchmaschine kommerziell und verzeichnet seitdem eine stetig steigende Benutzerzahl. Aufgrund des verwendeten Index, der über 8 Milliarden Websites [Gi] umfasst, ist Google in der Lage, den Nutzern überall auf der Welt gute Ergebnisse zu liefern, und das normalerweise in weniger als einer halben Sekunde.

Die einfach zu bedienende Benutzeroberfläche sowie die fortschrittliche Suchtechnologie von Google und die damit verbundene Qualität der Suchergebnisse machte Google innerhalb kurzer Zeit zu einer der beliebtesten Suchmaschine im Internet. Google ant-wortet auf mehr als 200 Millionen Suchvorgänge pro Tag. Die Applikationen und die Systemarchitektur, welche für die Bereitstellung der Suchergebnisse entwickelt wurden, sollen im nächsten Kapitel kurz vorgestellt werden, wobei jedoch auf die detaillierte Vorgehensweise bei der Bearbeitung einer Suchanfrage verzichtet werden soll.

2.2 Google Applikation

2.2.1 Google Application Programming Interface

Die Google Software Architektur wurde systematisch für die Abfrage von externen Applikationen erweitert, indem ein Web Service Interface zur Verfügung gestellt wurde. Die Kommunikation dieses Web Interfaces mit den User Applikationen ist in Abbildung 1 beschrieben. Der Google Server ist hierbei nur für die Ausführung der Abfrage der User verantwortlich. Ein Entwickler kann die Programmiersprache (C, Perl, Java, PHP, .NET, etc.) frei wählen und eine Verbindung zu dem remote Google Web API’s Service herstellen. Die Kommunikation findet via SOAP (ein auf XML basierender Mechanismus) statt. Sobald sich die Applikation mit dem Google Server verbunden hat, können Suchabfragen auf mehr als 8 Milliarden Webseiten sowie Zugriff auf den Google Cache ausgeführt werden. Die Google Web APIs unterstützen die auf der Google.com verwendete Suchsyntax.

2

2.2.1 Guided Google Architecture

Die integrierte Architektur von Guided Google [DB] sowie die Interaktion zwischen User und Google Server sind in Abbildung 2 dargestellt. Der User erhält Zugriff via JSP (Java Server Pages) auf einem Tomcat Server. Wie bereits in Abbildung 1 beschrieben, werden Daten via SOAP empfangen und gesendet, wobei dieser Prozess im Hintergrund abläuft, so dass der User nur auf eine Webseite zugreift.

Die Qualität der Suchergebnisse einer Suchmaschine hängt maßgeblich von der Relevanz der gefundenen Seiten und Dokumente sowie der Aktualität dieser Treffer ab. Es soll hier auf eine detaillierte Darstellung, wie Google Suchanfrage bearbeitet, Dokumente und Internetseiten durchsucht, die ermittelten Daten ordnet und indiziert, verzichtet werden. Die ermittelten Daten stellen jedoch die Grundlage für die Entwicklung des in Kapitel 3 beschriebenen Google File Systems dar.

3

2.3 System Hardware

Google hat bei seiner Systeminfrastruktur nicht in high-end Hardware investiert, sondern vielmehr auf Standardhardware gesetzt, die in jedem normalen Desktopsystem zu finden ist. Selbst diese normalen Desktopsysteme enthalten nicht die schnellsten Mikro-prozessoren, sondern sind vielmehr an „Costs per query“ [BDH] orientiert. Die Kosten-vorteile, die durch den Einsatz von sehr wirtschaftlichen, PC-basierten Clustern im Vergleich zu high-end Multiprozessor Servern realisiert werden können, vor allem aufgrund der Parallelität der Google Applikationen, sind substanziell. Ein großer Teil dieser Kostendifferenz ergibt sich aus der größeren Bandbreite und Stabilität der Server gegenüber handelsüblicher PC-Hardware. In einem durchschnittlichen Cluster können bis zu 20.000 Rechner unterschiedlichster Bauart in einem Netzwerk zusammengeschlossen werden. Mehrere Rechner werden dabei in „Racks“ zusammengefasst, wobei ein „Rack“ aus 40 bis 80 Rechner besteht. In den Clustern sind dabei verschiedenste

CPU Generationen im Einsatz, diese reichen von 533 MHZ- Celeron bis hin zu 2 GHZ

Intel Pentium IV Servern, wobei jeder dieser Server mit einer 80 GB IDE Festplatte ausgestattet ist. Die Server innerhalb eines Racks sind durch einen 100-Mbps Ethernet Switch verbunden, welcher ein oder zwei Gigabit uplinks zu einem Gigabit switch besitzt, durch den alle Racks untereinander verbunden sind. Die Google Cluster sind weiterhin in kleinere Cluster unterteilt, die aus ein paar tausend Maschinen bestehen, die geographisch verteilt sind, um das System vor katastrophalen Datenverlusten zu schützen. Jedem dieser kleineren Cluster werden Abfragen zugewiesen, abhängig von der geographischen Nähe. Diese Form der Lastverteilung minimiert die “round-trip time” [DB] einer Abfrage und verkürzt die Antwortzeit drastisch. Die Auswahl der Server ist dabei von den bereits beschriebenen „Costs per query“ abhängig. Ältere Server werden daher etwa alle 2 bis 3 Jahre ersetzt, da ihre Performance nicht mehr wirtschaftlich ist, und eine gleichmäßige Lastverteilung innerhalb des Clusters schwieriger wird. Somit enthalten Cluster immer Server mit dem besten Verhältnis zwischen Performance und Kosten, jedoch nicht unbedingt die leistungsfähigsten Server. Die Ausfallwahrscheinlichkeit von Servern innerhalb eines Clusters ist aufgrund des Alters und der Standardhardware sehr hoch im Vergleich zu leistungsstarken Servern. Die Kosten, die beim Monitoring eines Clusters entstehen, steigen nur unterproportional mit der Größe des Clusters. Weiterhin können durch dieses Monitoring fehleranfällige

4