…und das Leben nach SQL geht weiter … jetzt wird reduziert!

von Wolfgang Gassler am 22. Oktober 2009

Lesetipps

MapReduce – erfunden von Google, Nachfolger von SQL und neuer leuchtender Stern am Buzzword-Himmel (oder sollte ich besser Cloud sagen). Es handelt sich hierbei um eines der Hauptkonzepte von Key-Value Datenbanken, das es erlaubt, flexible Abfragen auf die gespeicherten Daten abzusetzen und mit ihnen zu arbeiten.
Oft wird MapReduce als SQL der Key-Value Datenbanken (Einführung siehe Gibt es ein Leben nach SQL?) bezeichnet. Es handelt sich hierbei aber nicht um eine Sprache, sondern um ein allgemeines Konzept, das festlegt, wie auf sehr große Datenmengen zugegriffen wird, wie Abfragen abgearbeitet werden und wie diese skalierbar und verteilbar gehalten werden.

Objekte in Key-Value Datenbanken können nur über einen eindeutigen Key angesprochen werden. Ein Zugriff erfolgt daher immer direkt und betrifft nur einen Datensatz. Suche, Joins, Aggregationen oder ähnliche Konstrukte, die bei relationalen Datenbanken über SQL realisiert werden, und mehrere Daten betreffen, sind daher grundsätzlich nicht möglich. Um trotzdem komplexe Berechnungen oder Manipulationen, wie zum Beispiel im Data Mining Bereich, durchführen zu können, wird bei den meisten Key-Value Datenbanken das MapReduce Konzept eingesetzt. Das Konzept wurde zum ersten Mal 2004 von Google unter dem Namen MapReduce veröffentlicht [1] und zielt auf einen hohen Grad an Verteilung und Skalierbarkeit ab. Zahlreiche Prozesse bei Google, wie z.B. Aufbau des Suchindex, werden mit Hilfe von MapReduce realisiert und bewältigen mehrere Terabyte an Daten.
Grundsätzlich besteht ein MapReduce-Prozess aus zwei Funktionen, der Map- und der Reduce-Funktion. Die Map Funktion wird auf alle gespeicherten Daten angewandt. Die Ergebnisse aller ausgeführten Map-Funktionen werden dann über die Reduce-Funktion eingesammelt und zusammengefasst.

Der folgende Pseudo Code zeigt ein Beispiel zur Berechnung der Anzahl aller Artikel, die das Wort ‘phphatesme’ beinhalten. Das Beispiel ist mit der SQL Query SELECT count(*) FROM articles WHERE content LIKE ‘%phphatesme%’ zu vergleichen.

function mapSearch ($article) {

 //search for string 'phphatesme' and exclude self-praise
 if (strstr($article->content, 'phphatesme')
    && $article->author != 'Nils') {
  return 1;
 } else {
  return 0;
 }
}

function reduceSearch($resultArray) {

 //sum up all occurrences of 'phphatesme'
 $count = 0;
 foreach ($resultArray as $value) {
  $count = $count + value;
 }
 return $count;
}

Die Funktion mapSearch, die mit Hilfe von strstr nach dem String ‘phphatesme’ sucht, wird hierbei für jedes gespeicherte Objekt (im relationalen Modell eine Zeile) aufgerufen. Die return-Werte werden dann vom MapReduce Framework gesammelt und der Funktion reduceSearch als Array übergeben. Diese muss nur mehr die 1-Werte aufsummieren und kann das Gesamtergebnis zurückliefern.

Um eine hohe Nebenläufigkeit (Parallelität) bzw. Skalierbarkeit zu ermöglichen, übernimmt MapReduce ein Konzept aus der Funktionalen Programmierung. Die Map- und Reduce-Funktionen dürfen dabei keine Seiteneffekte aufweisen. Den Funktionen ist es daher nicht erlaubt, auf Objekte außerhalb ihres eigenen Scopes (z.B. globale Variablen) zuzugreifen bzw. diese zu verändern. Die einzige Kommunikation mit der “Außenwelt” erfolgt über die übergebenen Parameter (keine Referenzen, nur Call by value) und dem return-Wert. Durch die so gewährleistete Unabhängigkeit jeder Funktion können die Funktionen parallel, auf verschiedenen CPUs, auf verschiedenen Rechnern oder in beliebiger Reihenfolge aufgerufen werden.

Im ersten Moment erscheint die MapReduce-Variante der “count” Abfrage eventuell komplexer und umständlicher, als eine klassische SQL-Query. Der Vorteil liegt jedoch in der Verwendung einer vollwertigen Programmiersprache, mit der im Gegensatz zu SQL wesentlich komplexere Prozesse modelliert werden können. Zusätzlich erhält man durch das funktionale Konzept eine ideale Grundlage zur Parallelisierung. Zum Beispiel verteilt Google mit dem eigenen MapReduce Framework Prozesse auf tausende Rechner und setzte damit 2008 den Rekord mit dem TeraSort Benchmark (1 Milliarde Datensätze mit 1 Terabyte sortieren) mit 1000 Rechnern auf 68 Sekunden.

Das sehr einfache und leichtgewichtige MapReduce Konzept wird mittlerweilen in fast allen Key-Value Datenbanken verwendet. Die auf Skalierbarkeit ausgerichteten Datenbanken können hier von der hohen Parallelisierbarkeit unter Beibehaltung des großes Funktionsumfanges der Map und Reduce Funktionen profitieren.

Ich hoffe ich konnte einen schnellen Blick hinter das Cloud-Buzzword auf das Konzept MapReduce ermöglichen. Wer noch nicht genug von diesem Thema hat, und gern mehr lesen will, z.B. wie diese Techniken in PHP eingesetzt werden können, möge dies doch bitte in den Kommentaren unterbringen. Für alle Interessierten und Datenbank-Nerds, die nicht auf weitere Artikel warten wollen/können, hier noch einige Links zum Thema:

MapReduce Artikel:

Key-Value Datenbanken (kein Anspruch auf Vollständigkeit):

Wolfgang Gassler

Wissenschaftlicher Mitarbeiter in der Forschungsgruppe Datenbanken und Informationssysteme an der Universität Innsbruck. Web-Entwickler seit über 10 Jahren - mit PHP3 groß geworden.

Zum Profil von Wolfgang Gassler

16 Kommentare »

Bastian
am 22. Oktober 2009 um 08:26 Uhr

Sehr gute Erläuterung. Hast du schon mal richtig mit MapReduce gearbeitet oder bisher auch nur davon gehört

Ich kann mir, auch nach deiner Erläuterung, noch nicht so richtig vorstellen wie eine Suche über die DB abläuft. Ich brauche doch irgendwo einen Index in dem steht wenn nach XYZ gesucht wird, liegt bei Objekt mit der ID ABC die Antwort.
Sascha Tietze
am 22. Oktober 2009 um 08:27 Uhr

Interessant, mal weiter verfolgen.

Glückwunsch zum 400.?! War doch so, oder
Dennis Becker
am 22. Oktober 2009 um 09:05 Uhr

Für mich ein sehr spannendes Thema Ich hoffe hier kommen auch bald mal praktische Beispiele in PHP, wie man soetwas verwendet Als “SQL-Nerd” muss man glaube ich vollkommen umdenken, was für mich eigentlich der hauptsächliche Reiz ist: über den Tellerrand schauen
Wolfgang Gassler
am 22. Oktober 2009 um 11:47 Uhr

@Bastian: ja ich habe schon damit gearbeitet, wobei man MapReduce weniger für eine AdHoc Anfrage (Suche) verwendet. Das dauert dann meistens zu lang. MapReduce ist mehr für die Verarbeitung großer Datenmengen (klassisches Bsp. wäre DataMining) wenn die Zeit keine wichtige Rolle spielt. Für eine AdHoc Anfrage auf einen Value benötigt man weiterhin Indexstrukturen oder ähnliche Konstrukte. Manche Datenbanken, wie Tokyo Cabinet, bieten auch hierfür fertige Lösungen an.
Bastian
am 22. Oktober 2009 um 13:57 Uhr

@Wolfgang: Also ist der Vergleich mit SQL den Nils hier macht doch eigentlich verkehrt. Ich kann SQL-Anfragen nicht sinnvoll mit MapReduce abbilden. Oder?
Wolfgang Gassler
am 22. Oktober 2009 um 14:01 Uhr

@Bastian: doch, der vergleich stimmt, da auch ein count(*) im normalfall einen full table scan impliziert und daher alle daten eingelesen werden. auch bei komplexen anfragen im data warehouse (data mining) bereich sind full table scans durch SQL anfragen keine seltenheit. SQL und MapReduce sind definitiv nicht das gleiche aber es gibt viele anfragen, die in beiden modellen realisiert werden können.
Nils Langner
am 22. Oktober 2009 um 15:21 Uhr

@Bastian: Der Artikel ist übrigens nicht von mir, sondern von Wolfgang. Will mich ja nicht mit fremden Federn schmücken.
Bastian
am 22. Oktober 2009 um 16:34 Uhr

@Nils: wo du doch sowieso ein Redesign von phphatesme machen wolltest… mach doch mal Autorenfotos neben den Artikel. Das würde Verwechslungen dieser Art vorbeugen
@Wolfgang: Sorry, dein Vergleich mit SQL Wenn ich nen ordentlichen Index in “SQL” benutze, muss er für ein count(*) doch auch nur den Index zählen oder gibts dann trotzdem nen full table scan?
Nils Langner
am 22. Oktober 2009 um 16:58 Uhr

@Bastian: Ist geplant. Wollte die Co-Autoren eh ein wenig mehr “ehren”.
Wolfgang Gassler
am 22. Oktober 2009 um 17:13 Uhr

@Bastian: ein count(*) könnte man über den index noch abbilden, aber wenn man eine where clause mit ‘%phphatesme%’ hat, geht das eigentlich nicht mehr. eventuell über einen fulltext index, aber wenn man nach ‘%php%’ sucht geht auch das nicht mehr. es ist aber allgemein schwer das ganze mit klassischen relationalen dbms zu vergleichen, da es sich hierbei doch um verschiedene welten handelt. der vergleich mit sql war eher dazu gedacht, das code fragment schneller zu verstehen…
Bastian
am 22. Oktober 2009 um 18:15 Uhr

@Wolfgang: genau das mit dem Codefragment hab ich halt nicht so recht verstanden. Mit SQL verbinde ich primär JOINS und komplexe Selektionen mit vielen Bedingungen.

Mit MapReduce verbinde ich (nach deinen Ausführungen und ein klein bisschen Recherche im Netz) primär die sehr schnelle Abfrage von komplexen Daten aufgrund eines Keys.

Vielleicht könntest map/reduce funktionen für einen nicht “count(*)” Anwendungsfall zeigen?

Werden die Ergebnisse des MapReduce-Laufes dann irgendwie gespeichert?

Du siehst, ich finde das Thema sehr interessant
Wolfgang Gassler
am 22. Oktober 2009 um 19:20 Uhr

@Bastian: wie im artikel erwähnt, ist das ganze ja kein fix fertiges produkt, sondern ein konzept, das es in verschiedenen ausführungen gibt. einen schnellen zugriff per key (hash) bieten alle key/value datenbanken an. will man jedoch komplexe aufgaben erledigen, kann man z.b. mapreduce verwenden. wikipedia hat ein ausführlicheres beispiel mit den ganzen zwischenschritten http://de.wikipedia.org/wiki/MapReduce
KingCrunch
am 27. Oktober 2009 um 01:23 Uhr

Ich hab mich mal schlau gemacht. Grundsätzlich ist das Konzept interessant, aber wieso genau sollte man zu einem System wechseln, dass a) weniger mächtig, b) zwischen Faktor 3 bis 5 langsamer, als herkömmliche Methoden (CouchDB), und c) nicht mal ansatzweise irgendwie standardisiert (Schnittstelle) ist?
Andre Moelle
am 27. Oktober 2009 um 08:35 Uhr

Was bringt ein Standard, wenn alle Implementierungen ihre Eigenheiten haben? Bei CouchDB ist CouchDB die Referenzimplementierung.
Außerdem würde ich nicht sagen, dass CouchDB weniger mächtig als SQL ist, sie sind nur für verschiedene Zwecke konzipiert. Davon abgesehen schreibt man die CouchDB-Views in einer turingvollständigen Sprache – wie kann das also weniger mächtig sein als SQL? Zwar ist CouchDB langsamer als ein SQL-Server, aber dafür lässt sich CouchDB besser skalieren.

Ich glaube, dass man erstmal erkunden muss, wofür CouchDB und wofür relationale Datenbanksysteme geeignet sind. Bei den meisten Webapplikationen tippe ich zwar auf CouchDB, aber da relationale Datenbanken in diesem Umfeld de facto Standard sind, hat man für fast jedes Szenario bereits annehmbare Wege gefunden, das relationale Modell zu verwenden. Bei CouchDB fehlen diese Erfahrungen natürlich.
In dem Sinne: Seht ihr einen Nagel, nutzt den Hammer. Seht ihr eine Schraube, nutzt den Schraubenzieher.
Wolfgang Gassler
am 29. Oktober 2009 um 23:11 Uhr

Ich glaube Andre hat das ganz gut getroffen. Ich habe auch gerade zufällig vor zwei Tagen einen Artikel von Michael Stonebraker im ACM Communications gelesen. Er sieht auf lange Sicht auch keine Zukunft für die großen monolitischen DBMS, da sie zwar alles können, jedoch mit auf den Anwendungsfall angepasste DBs nicht mithalten können. Er erklärt, dass es bei den meisten Anwendungsfällen eine 50x schnellere/bessere Lösung gibt. Sei es eine XMl DB, Verteilte DB (mit z.B. MapReduce), Column orientierte DB, Analyse-optimierte DB usw…

Hier der Link (leider kostenpflichtig bzw. über viele Uninetze kostenlos)
http://portal.acm.org/citation.cfm?id=1562164.1562169&coll=portal&dl=ACM&idx=J79&part=magazine&WantType=Magazines&title=Communications%20of%20the%20ACM&CFID=58533910&CFTOKEN=89719981
Wer braucht Variablen? Die funktionale Welt… | PHP hates me - Der PHP Blog
am 10. März 2010 um 07:02 Uhr

[...] …und das Leben nach SQL geht weiter … jetzt wird reduziert! [...]