MapReduce in Googles Go
Googles relativ neue Programmiersprache Go ist ein bunter Mix unterschiedlicher Sprachmittel. Eine ihrer wichtigsten Fähigkeiten ist jedoch die Unterstützung nebenläufig arbeitender Programmlogik.
- Frank Müller
Googles relativ neue Programmiersprache Go ist ein bunter Mix unterschiedlicher Sprachmittel: im Grundgerüst imperativ, mit Anleihen der objektorientierten Programmierung und abgerundet durch Funktionen höherer Ordnung. Eine der wichtigsten Fähigkeiten ist jedoch die Unterstützung nebenläufig arbeitender Programmlogik. In der Regel als Strukturierungsmittel eingesetzt, lässt sich Go auch zur Parallelisierung von Aufgaben einsetzen.
Die aktuelle Welt der Programmiersprachen ist durch eine Vielzahl an Neuerscheinungen oder von wieder auflebendem Interesse an einigen länger existierenden Vertretern der Zunft geprägt. Die Motivation hierfür liegt im Wandel der Rechnerarchitekturen, die inzwischen selbst im mobilen Sektor die parallele Code-Ausführung unterstützen. Und für Server sind Konfigurationen mit 64 Prozessoren mit je vier Kernen und hierin je zwei Threads erhältlich.
Go – das Buch
Der Artikel ist ein für heise Developer aufbereiter Auszug des "Go"-Buchs aus dem dpunkt Verlag, das auf knapp 300 Seiten auf die Grundlagen der Sprache, ihre Konzepte bei Skalierbarkeit, Performanz und Sicherheit sowie auf Bibliotheken und Werkzeuge für einen praktischen Umgang eingeht.
Dadurch lassen sich viele Aufgaben gleichzeitig verarbeiten, vorausgesetzt, die Software ist hierzu in der Lage. Für die parallele Verarbeitung bringen die Sprachen teilweise einfache Hausmittel mit, andere greifen auf externe Bibliotheken zurück. Vielfach sind die Hilfen jedoch unkomfortabel und anfällig für Fehler im Umfeld der Nebenläufigkeit. Hierauf liegt das Augenmerk der aktuellen Bemühungen.
Die im November 2009 von Google vorgestellte Sprache Go sieht auf den ersten Blick unspektakulär aus. Ein typischer Vertreter der C-Sprachenfamilie mit ein paar kosmetischen Änderungen, neuen Datentypen und Schlüsselwörtern. Doch die Entwickler von Go – anfangs Ken Thompson, Rob Pike und Robert Griesemer, ab 2008 durch Ian Lance Taylor und Russ Cox ergänzt – hatten mehr im Sinn. Sie waren bei Google in die Entwicklung großer C++-Systeme involviert. Die hierbei auftretenden langen Übersetzungszeiten waren kontraproduktiv, ebenso weitere Anachronismen in der Syntax. Zu sehr prägte C als Urahn die Sprache.
Daraus wuchs die Idee, eine neue Systemsprache zu entwickeln – schnell in der Übersetzung, trotz statischer Typisierung mit dem Komfort dynamischer Sprachen sowie Konstrukten und einem Unterbau für massiv nebenläufige Anwendungen. Diese basieren auf einer Menge von bis zu mehreren 10.000 Coroutinen, die mit geringem Overhead in einem intelligent gesteuerten Thread Pool ihre Arbeit verrichten. Der gemeinsame Zugriff auf Variablen ist zwar erlaubt, jedoch nicht das Sprachmittel der Wahl. Stattdessen kommen typisierte und je nach Bedarf synchron oder asynchron arbeitende Channels zum Einsatz. Jede Coroutine – in Go als Goroutine bezeichnet – kann dabei aus mehreren Channels lesen und schreiben. Dem regen Datenaustausch steht so nichts entgegen.
Die zu übertragenden Daten sind vielfältig. Der Entwickler kann bei der Deklaration eines Channels aus der ganzen Bandbreite der Go-Typen wählen. Seien es einfache Typen wie boolesche Variablen, Integers, Floats und komplexe Zahlen unterschiedlicher Präzision und Strings oder auch zusammengesetzte Typen wie Strukturen, Maps, Arrays und Slices, einer mit Arrays verwandten Speicherstruktur. Da Funktionen, Schnittstellen und Channels ebenfalls Datentypen sind, steht auch hier dem Austausch über Channels nichts im Wege. Die so versandten Daten werden in der Regel innerhalb einer Goroutine verarbeitet. Hierbei handelt es sich um eine mit dem Schlüsselwort go gestartete Funktion. In der Rolle eines internen Servers enthält sie eine Endlosschleife innerhalb derer sich mit der select-Anweisung aus mehreren Channels lesen lässt. Die dadurch empfangenen Daten lassen sich nun verarbeiten, die Auslieferung der Ergebnisse erfolgt über weitere Channels.
Ist ein Channel für die Verarbeitung hinreichend, lässt sich alternativ auch die for-Schleife zusammen mit der range-Anweisung nutzen. Sie liest aus einem Channel, bis dieser geschlossen wird. Der typische Einsatzfall hierfür ist die nebenläufige Verarbeitung von Massendaten. Während beispielsweise eine Goroutine Daten einliest, bereitet eine weitere sie vor oder grenzt sie ein, die folgende Goroutine kümmert sich um die Hauptverarbeitung und eine weitere um die Nachbereitung. Schließlich kümmert sich eine Goroutine um die Ausgabe. Ist die Beschleunigung in dieser linearen Form noch eingeschränkt, verbessert es sich mit Verzweigungen in parallele Verarbeitungsstränge, die abhängig von den Dateninhalten sind – eine klassische Pipes-and-Filters-Architektur.
Nebeneinander miteinander
Eine weitere Technik zur Verarbeitung von Massendaten kommt ebenfalls aus dem Hause Google. Das wohl bekannteste Beispiel ihres Einsatzes ist die Beschleunigung der Suche von Webseiten durch eine massive Parallelisierung, und zwar über das im Rahmen eigener Forschungsarbeiten entwickelte MapReduce-Verfahren. Es basiert auf der Arbeitsweise der von Lisp bekannten Funktionen map und reduce, auch wenn die gesamte Technik durch die Verteilungsaspekte deutlich komplexer als das hier vorgestellte Beispiel ist.
Im Wesentlichen basiert es auf der nebenläufigen Ausführung der Funktionen in zwei Phasen. Die Eingangsdaten liegen in Form einer Liste von Paaren aus Schlüsseln und Werten vor. Ihre Verarbeitung wird gleichmäßig auf eine Menge parallel arbeitender Map-Prozesse verteilt. Die einzelnen Paare in den Listen verarbeiten nun hierin die Map-Funktionen. Das Ergebnis jedes Aufrufs ist eine Liste neuer Schlüssel-Wert-Paare. Die gewählten Schlüssel sind dabei vom Ziel der gesamten Verarbeitung abhängig. Diese Ergebnislisten sind als Zwischenergebnis der Phase des Reducings zuzuführen. In dieser arbeiten ebenfalls parallele Prozesse. Ihnen werden die Ergebnisse des Mappings auf Basis der Schlüssel zugeführt. Somit werden gleiche Schlüssel immer den gleichen Prozessen zugeordnet, auch wenn diese für mehrere Schlüssel zuständig sein können. Mit dem Ende der Eingangsdaten und nach dem anschließenden Mapping geben die Reduce-Prozesse ihre aggregierten Daten aus.
Das Verfahren soll nun über ein eigenes Package für den Einsatz in eigenen Programmen zur Verfügung gestellt werden. Als ein erstes Anwendungsbeispiel dient eine Liste mit Bestellungen. Jede dieser Bestellungen enthält ihrerseits wieder eine Liste von Positionen mit Angaben des Artikels, der zu liefernden Anzahl, Einzelpreis und Rabatt. Die individuellen Bestellungen werden für den ersten Schritt der Verarbeitung auf die Map-Prozesse verteilt. Die hier genutzte Funktion berechnet für jede Auftragsposition die Gesamtsumme sowie den Gesamtrabatt. Anschließend werden die so berechneten Artikelinformationen auf die Reduce-Prozesse verteilt.
In der nun folgenden zweiten Phase summieren diese Prozesse für ihre auf Basis der Artikelnummern zugeordneten Artikel die Anzahl der Bestellungen, Verkaufsbeträge sowie die Rabatte. Mit der Beendigung der Dateneingänge geben sie die so berechneten Werte aus. Der Nutzer des MapReduce erhält eine Liste der bestellten Artikel inklusive der drei berechneten Werte.
Das hier beschriebene Grundverfahren lässt sich auf eine Vielzahl unterschiedlicher Datenverarbeitungen anwenden. Google setzt es beispielsweise neben der Suche auch bei der URL-Analyse, der Zugriffsanalyse und dem Sortieren ein. Teilweise erfolgt das mit Daten im Petabyte-Bereich sowie mit 200.000 Map- und 5000 Reduce-Prozessen auf etwa 2000 Knoten. Derartige große Zahlen verdeutlichen, dass das MapReduce-Verfahren seine wirkliche Stärke erst in verteilten Umgebungen mit einer großen Anzahl an Prozessoren und einer entsprechenden Verteilung der Daten ausspielt.
Mit zunehmender Anzahl an Rechenkernen pro CPU kann es jedoch schon auf einem einzelnen Rechner interessant werden. Die Implementierung hier soll das verdeutlichen und zeigen, wie leicht sich der Algorithmus mit Go entwickeln lässt. Ziel ist eine Funktion, die einen Eingangsdaten-Channel, die Funktionen für Map und Reduce sowie für beide jeweils die Anzahlen der Goroutinen entgegennimmt. Die Rückgabe ist ein Channel für die Ergebnisse der Verarbeitung.
