Das Google File System

von: Michael Leyh

INHALTSVERZEICHNIS

1. EINLEITUNG 1

2. GOOGLE 2

2.1 DIE GOOGLE-GESCHICHTE 2
2.2 GOOGLE APPLIKATION  2

2.2.1 Google Application Programming Interface 2
2.2.2 Guided Google Architecture 3

2.3 SYSTEM HARDWARE 4

3. GOOGLE FILE SYSTEM 5

3.1 DESIGN ÜBERBLICK 5

3.1.1 Architektur  5
3.1.2 Master Metadaten  6
3.1.3 Konsistenzmodell des GFS 8

3.2. SYSTEMINTERAKTIONEN 9

3.2.1 Mutationsreihenfolgen  9
3.2.2 Der Datenfluss  11
3.2.3 Record Appends und Snapshots  12

3.3 MASTEROPERATIONEN 13

3.3.1 Management des Namensraumes 13
3.3.2 Verteilung, Erstellung und Reproduktion von Kopien  14
3.3.3 Der Garbage Collection Mechanismus  15

3.4 FEHLERTOLERANZ, ZUVERLÄSSIGKEIT UND VERFÜGBARKEIT 16

3.5 DATENFLUT UND WORKLOAD  17

3.5.1 Datenflut in Real World Clustern  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.

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 antwortet 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.

Abbildung 1: Google Web API [DB, S. 3] [Abbildung in der Downloaddatei vorhanden]

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.

Abbildung 2: Guided Google Architektur [DB, S. 4] [Abbildung in der Downloaddatei vorhanden]

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.

2.3 System Hardware

[...]