Map/Reduce

Beschreibung

MapReduce ist ein von Google Inc. 2004 eingeführtes Framework für nebenläufige Berechnungen über enorm große (mehrere Petabyte) Datenmengen auf Computerclustern. Dieses Framework wurde durch die in der funktionalen Programmierung häufig verwendeten Funktionen map und reduce inspiriert, auch wenn die Semantik des Frameworks von diesen etwas abweicht. 2010 wurde für MapReduce ein US-Patent erteilt.

MapReduce-Implementierungen wurden in C++, Erlang, Java, Python und vielen anderen Programmiersprachen realisiert.

Funktionsweise


Quelle: [AbMR]

Map/Reduce stammt aus dem Bereich der funktionalen Programmiersprachen wie LISP (List Processing) und ML (Meta Language), was auf die Vorteile funktionaler Sprachen im Umgang mit der Parallelisierung zurückzuführen ist. Da dort nur auf neu erstellten Kopien der Daten, nicht aber auf den vorhanden Datenstrukturen?, also dem Originaldatensatz, gearbeitet wird, kann es weder zu Verklemmungen (deadlock), noch zu Wettlaufbedingungen? (race conditions) kommen: zwei ernst zu nehmenden Problemen in der nebenläufigen Programmierung.

Ohne Seiteneffekte spielt die Ausführungsreihenfolge keine Rolle und man kann von einer "echten Parallelisierung" sprechen. Grundgedanke ist dabei das aus anderen Sprache bekannte map()-Verfahren, also eine Funktion sukzessiv auf Listen anzuwenden.

Beispiel:

Wenn man die Funktion x² auf eine Liste [ 1, 2, 3, 4, 5 ] anwendet erhällt man eine neue (Ergebnis-)Liste [ 1, 4, 9, 16, 25 ].

Quellen:

Weiterführende Literatur:

  • Frey, M.: „Etablierte Datenmodelle der NoSQL-Familie und ihre spezifischen Eigenschaften im Kontext von Cloud-Datenbanken“, Bachelorarbeit, FH Köln, Institut für Informatik, 08/2010
  • Kossmann, D., Kraska T.: „Data Management in the Cloud: Promises, State- of-the-art and Open Questions“, in „Datenbanken und Cloud-Computing“, Datenbank Spektrum, Band 10 Heft 3, Springer-Verlag, 12.2010, S. 121-129

Weiterführende Links:

Kategorie: Neue DB-Entwicklungen, Grundlagen,NoSQL, M