Zum Inhalt springen

Einführung in Apache MapReduce

  • Daten

MapReduce ist ein Algorithmus, der es ermöglicht große Datensätze parallel, also auf mehreren Computern gleichzeitig, verarbeiten zu können. Dadurch werden Abfragen für große Datenmengen stark beschleunigt.

Wofür nutzen wir MapReduce?

MapReduce wurde ursprünglich von Google eingesetzt, um die große Menge an Suchergebnissen effizient durchsuchen zu können. Richtig berühmt wurde der Algorithmus jedoch erst durch die Nutzung innerhalb des Hadoop Frameworks. Dieses Tool speichert große Datenmengen in dem Hadoop Distributed File System (kurz: HDFS) und nutzt MapReduce für Abfragen oder Aggregationen von Informationen im Bereich von Terra- oder Petabytes.

Angenommen wir haben alle Teile der Harry Potter Romane in Hadoop als PDF abgelegt und möchten nun die einzelnen Wörter zählen, die in den Büchern vorkommen. Dies ist eine klassische Aufgabe bei der uns die Aufteilung in eine Map-Funktion und eine Reduce Funktion helfen kann.

Wie wurde es früher gemacht?

Bevor es die Möglichkeit gab, solche aufwendigen Abfragen auf ein ganzes Computer-Cluster aufzuteilen und parallel berechnen zu können, war man gezwungen, den kompletten Datensatz nacheinander zu durchlaufen. Dadurch wurde die Abfragezeit natürlich auch umso länger, umso größer der Datensatz wurde.

Angenommen wir haben die Harry Potter Texte bereits Wort für Wort in einer Python Liste vorliegen:

harry_potter_words = ['Once', 'upon', 'a', 'time', 'Harry', 'Potter', 'met',         
                      'Ron', 'Weasley', 'and', 'Hermine', 'Granger', 'and', 
                      'they', 'became', 'Harry', 'Potters', 'best', 'friends', 
                      '.']

Wir können die vorkommenden Wörter zählen, indem wir diese Liste mit einer For-Schleife durchlaufen und jedes Wort in den „Counter“ aus dem Python Modul „Collections“ laden. Diese Funktion übernimmt dann für uns das Zählen der Wörter und gibt die zehn häufigsten Wörter aus. Mithilfe des Python Moduls „Time“ können wir uns anzeigen lassen, wie lange unser Computer benötigt hat, um diese Funktion auszuführen.

import collections

def find_top_words(list_of_words):
    cnt = collections.Counter()
    for word in list_of_words:
        cnt.update([word])
    return cnt.most_common(10)

Laut der Website wordcounter.io hat der erste Harry Potter Teil insgesamt 76.944 Wörter. Da unser Beispielsatz nur 20 Wörter (inklusive Punkt) hat, bedeutet das, dass wir etwa 3.850 Mal (76.944 / 20 ~ 3.847) diesen Beispielsatz wiederholen müssen, um eine Liste mit genauso vielen Wörtern zu bekommen, wie Harry Potter’s Stein der Weisen:

# Part 1 = 76,944 words ~ 3,850 example sentences of length 20
harry_potter_part_1 = harry_potter_words * 3850

%time find_top_words(harry_potter_part_1)

Out: 
Wall time: 312 ms
[('Harry', 7700),
 ('and', 7700),
 ('Once', 3850),
 ('upon', 3850),
 ('a', 3850),
 ('time', 3850),
 ('Potter', 3850),
 ('met', 3850),
 ('Ron', 3850),
 ('Weasley', 3850)]

Unsere Funktionen benötigt 312 Millisekunden, um alle Wörter des ersten Teils zu durchlaufen und zu zählen, wie oft sie vorkommen. Wenn wir die gleiche Abfrage für alle Harry Potter Teile mit insgesamt 3.397.170 Wörtern (Quelle: wordcounter.io) durchführen, dauert es insgesamt 3,7 Sekunden.

# All Parts = 3,397,170 words ~ 170,000 example sentences of length 20
harry_potter_all_parts = harry_potter_words * 170000

%time find_top_words(harry_potter_all_parts)

Out: 
Wall time: 3.79 s
[('Harry', 340000),
 ('and', 340000),
 ('Once', 170000),
 ('upon', 170000),
 ('a', 170000),
 ('time', 170000),
 ('Potter', 170000),
 ('met', 170000),
 ('Ron', 170000),
 ('Weasley', 170000)]

Diese Abfrage dauert vergleichsweise lange und wird für größere Datensätze natürlich immer länger. Der einzige Weg um die Ausführung der Funktion zu beschleunigen ist es, einen Computer mit einem leistungsfähigeren Prozessor (CPU) auszustatten, also dessen Hardware zu verbessern. Wenn man versucht, die Ausführung eines Algorithmus zu beschleunigen, indem man die Hardware des Gerätes verbessert, nennt man das vertikales Skalieren.

Wie funktioniert der MapReduce Algorithmus?

Mithilfe von MapReduce ist es möglich eine solche Abfrage deutlich zu beschleunigen, indem man die Aufgabe in kleinere Teilaufgaben aufsplittet. Das hat dann wiederum den Vorteil, dass die Teilaufgaben auf viele verschiedene Computer aufgeteilt und von ihnen ausgeführt werden kann. Dadurch müssen wir nicht die Hardware eines einzigen Gerätes verbessern, sondern können viele, vergleichsweise leistungsschwächere, Computer nutzen und trotzdem die Abfragezeit verringern. Ein solches Vorgehen nennt man horizontales Skalieren.

Kommen wir zurück zu unserem Beispiel: Bisher waren wir bildlich so vorgegangen, dass wir alle Harry Potter Teile gelesen haben und nach jedem gelesenen Wort die Strichliste mit den einzelnen Wörtern einfach um einen Strich erweitert haben. Das Problem daran ist, dass wir diese Vorgehensweise nicht parallelisieren können. Angenommen eine zweite Person will uns unterstützen, dann kann sie das nicht tun, weil sie die Strichliste, mit der wir gerade arbeiten, benötigt, um weiterzumachen. Solange sie diese nicht hat, kann sie nicht unterstützen.

Sie kann uns aber unterstützen, indem sie bereits mit dem zweiten Teil der Harry Potter Reihe beginnt und eine eigene Strichliste nur für das zweite Buch erstellt. Zum Schluss können wir dann alle einzelnen Strichlisten zusammenführen und beispielsweise die Häufigkeit des Wortes „Harry“ auf allen Strichlisten zusammenaddieren.

Das Bild zeigt den MapReduce Algorithmus am Beispiel von Harry Potter Büchern.
MapReduce am Beispiel von Wortzählungen in Harry Potter Büchern

Dadurch lässt sich die Aufgabe auch relativ einfach horizontal skalieren, indem jeweils eine Person pro Harry Potter Buch arbeitet. Wenn wir noch schneller arbeiten wollen, können wir auch mehrere Personen mit einbeziehen und jede Person ein einziges Kapitel bearbeiten lassen. Am Schluss müssen wir dann nur alle Ergebnisse der einzelnen Personen zusammennehmen, um so zu einem Gesamtergebnis zu gelangen.

MapReduce Beispiel in Python

Insgesamt brauchen wir also zwei Funktionen einen Mapper und einen Reducer. Den Mapper definieren wir so, dass er für jedes Wort, das er bekommt, ein Dictionary zurückgibt mit dem Wort als Schlüssel und dem Wert 1:

def mapper(word):
    return {word: 1}

Analog zu unserem Beispiel gibt der Mapper also eine „Strichliste“ zurück, die aussagt: „Das Wort, das mir übergeben wurde, kommt genau einmal vor“. Der Reducer übernimmt dann im zweiten Schritt alle einzelnen „Strichlisten“ und fügt diese zu einer großen gesamten „Strichliste“ zusammen. Er unterscheidet dabei zwei Fälle: Wenn das Wort, das ihm übergeben wird, bereits in seiner großen „Strichliste“ vorkommt, dann fügt er in der entsprechenden Zeile einfach ein Strich hinzu. Wenn das neue Wort noch nicht in seiner Liste auftaucht, fügt der Reducer einfach eine neue Zeile mit dem Wort in die große „Strichliste“ hinzu.

def reducer(collection, new_word_dict):
    for word in new_word_dict.keys():
        if word in collection:
            collection[word] = collection[word] + 1
        else:
            collection[word] = 1
    return collection

Wenn wir diese beiden Teilaufgaben zusammenführen, dauert dieselbe Abfrage wie zuvor nur noch 1,5 Sekunden:

from functools import reduce

if __name__ == '__main__':
    harry_potter_words = ['Once', 'upon', 'a', 'time', 'Harry', 'Potter', 'met',          
                          'Ron', 'Weasley', 'and', 'Hermine', 'Granger', 'and',  
                          'they', 'became', 'Harry', 'Potters', 'best', 'friends', 
                          '.']

    harry_potter_all_parts = harry_potter_words*170000
    

    # Save the time now to calculate the overall time later
    start = time.process_time()
    
    # Step 1: Apply mapper
    mapped = map(mapper, harry_potter_all_parts)
   

    # Step 2: Apply reducer
    reduced = reduce(reducer, mapped)

    # Print the dictionary with the word_counts
    print(reduced)
    # Print the difference in time between now and when the system started
    print(time.process_time() - start)

Out:
{'Once': 170000, 'upon': 170000, 'a': 170000, 'time': 170000, 'Harry': 340000,
 'Potter': 170000, 'met': 170000, 'Ron': 170000, 'Weasley': 170000, 'and': 340000, 
 'Hermine': 170000, 'Granger': 170000, 'they': 170000, 'became': 170000, 
 'Potters': 170000, 'best': 170000, 'friends': 170000, '.': 170000}
1.5625

Somit konnten wir durch den MapReduce Algorithmus die Abfragezeit für alle Harry Potter Bücher mehr als halbieren, ohne dass wir horizontale oder vertikale Skalierung vorgenommen haben. Wenn uns jedoch die Abfragezeit von 1,5 Sekunden immer noch zu groß ist, könnten wir die Wortliste auch einfach beliebig aufteilen und den Mapper auf verschiedenen Computern parallel ausführen lassen, um den Prozess weiter zu beschleunigen.

Nachteile von MapReduce

Unser Beispiel hat eindrucksvoll gezeigt, dass wir mithilfe von MapReduce große Datenmengen schneller Abfragen können und den Algorithmus gleichzeitig für eine horizontale Skalierung vorbereiten. Jedoch kann MapReduce nicht immer eingesetzt werden oder bringt je nach Anwendungsfall auch Nachteile mit sich:

  • Manche Abfragen lassen sich nicht in das MapReduce Schema bringen.
  • Die Map Funktionen laufen isoliert voneinander ab. Somit ist es nicht möglich, dass die Prozesse untereinander kommunizieren.
  • Verteilte Systeme sind deutlich schwerer zu beaufsichtigen und kontrollieren als ein einziger Computer. Es sollte also genau abgewogen werden, ob wirklich ein Computing Cluster benötigt wird. Für die Kontrolle eines Computer-Clusters kann das Software-Tool Kubernetes genutzt werden.

Das solltest Du mitnehmen

  • MapReduce ist ein Algorithmus, der es ermöglicht große Datensätze parallel und schnell zu verarbeiten.
  • Der MapReduce Algorithmus splittet eine große Abfrage in mehrere kleine Teilaufgaben auf, die dann auf verschiedene Computer verteilt und bearbeitet werden können.
  • Nicht jede Anwendungen lässt sich in das MapReduce Schema überführen, sodass es manchmal auch gar nicht möglich ist, diesen Algorithmus zu nutzen.

Andere Beiträge zum Thema MapReduce

  • Das Paper von Google, in dem MapReduce zum ersten Mal vorgestellt wurde, findest Du hier.
close
Das Logo zeigt einen weißen Hintergrund den Namen "Data Basecamp" mit blauer Schrift. Im rechten unteren Eck wird eine Bergsilhouette in Blau gezeigt.

Verpass keine neuen Beiträge!

Wir versenden keinen Spam! Lies die Details gerne in unserer Datenschutzrichtlinie nach.

Schlagwörter:
Cookie Consent mit Real Cookie Banner