Google-Rechenschema für alle

“Jedes Mal, wenn ich eine Suchmaschine nutze, bin ich hingerissen von ihrer Fähigkeit, innerhalb von Millisekunden aus einer riesigen Datenmenge Tausende relevante Treffer zu einem bestimmten Schlüsselwort zu finden”, sagt Prof. Christian Lengauer vom Lehrstuhl für Programmierung an der Universität Passau. Was viele Menschen täglich nutzen, ist laut Lengauer die bisher mächtigste Umsetzung von MapReduce. Die DFG hat der Universität Passau nun ein Forschungsvorhaben bewilligt, das an der Fakultät für Informatik und Mathematik von Prof. Lengauer und Dr. Sven Apel koordiniert wird.

Das Projekt MapReduceFoundation will die Nutzung des Rechenschemas erleichtern. Ein wichtiger Schritt auf diesem Weg ist es, bei der Programmierung mit MapReduce die Typsicherheit zu garantieren. In der Programmierung können sich schnell Fehler in den Datenformaten einschleichen. Typsicherheit bedeutet, dass solche Fehler schon während des Programmierens und nicht erst im Betrieb erkannt werden. So können unerwartete Programmabbrüche vermieden werden.

“Obwohl die derzeitig dominierende Programmiersprache Java als typsicher gilt, kann es bei der Programmierung von MapReduce-Berechnungen in Java zu Formatkonflikten kommen, die unerkannt bleiben. Wir entwickeln unter anderem eine Technik, die es ermöglicht, Formatkonflikte vor dem Betrieb zu erkennen, und zwar, ohne den Programmierer zusätzlich zu belasten”, so Lengauer.

Die Idee bei MapReduce ist im Grunde einfach. Anwendungen, die sich dafür eignen, seien weit älter als das Internet. “Ein Beispiel ist die Konkordanz der Bibel, die angibt, wie oft Worte oder Phrasen in einer bestimmten Übersetzung vorkommen.” Mit dem MapReduce lasse sich dies folgendermaßen formulieren: Zunächst wird jedes Wort im Bibeltext mit einer 1 versehen, die ein einmaliges Vorkommen anzeigt: der Map-Schritt. Danach werden die Vorkommen gleicher Worte aufsummiert: der Reduce-Schritt.

Beide Schritte können jeweils auf Prozessoren oder Rechnern hochparallel durchgeführt werden. Durch diese starke Arbeitsteilung steht das Ergebnis viel früher zur Verfügung. “Die Herausforderung besteht darin, dieses simple Prinzip für riesige Datenmengen und eine Palette von Operationen bereitzustellen, den Prozess auf eine Vielzahl von Prozessoren zu verteilen sowie den nötigen Rechen- und Zeitaufwand zu verringern”, erklärt Lengauer.