Big Data: MapReduce

3.1 Entstehungsgeschichte des Begriffs BigData

Der Begriff Big Data taucht erst seit relativ kurzer Zeit auf. Google Trends zeigt den Beginn eines aktiven Wachstums der Verwendung des Ausdrucks seit 2011:

Gleichzeitig verwendet nur der Faule den Begriff jetzt nicht. Besonders häufig wird der Begriff von Vermarktern unangemessen verwendet. Was ist Big Data eigentlich? Da ich mich entschieden habe, das Thema systematisch darzulegen und hervorzuheben, ist es notwendig, das Konzept zu definieren.

In meiner Praxis bin ich auf unterschiedliche Definitionen gestoßen:

• Von Big Data spricht man, wenn mehr als 100 GB Daten vorhanden sind (500 GB, 1 TB, was auch immer Sie möchten).
• Big Data sind Daten, die nicht in Excel verarbeitet werden können.
• Big Data sind Daten, die nicht auf einem einzelnen Computer verarbeitet werden können.

Und sogar diese:

• Unter Big Data versteht man grundsätzlich alle Daten.
• Big Data gibt es nicht, es wurde von Vermarktern erfunden.

Ich bleibe bei der Definition aus Wikipedia:

Big Data ist eine Reihe von Ansätzen, Werkzeugen und Methoden zur Verarbeitung strukturierter und unstrukturierter Daten großer Mengen und erheblicher Vielfalt, um für den Menschen wahrnehmbare Ergebnisse zu erzielen, die unter Bedingungen kontinuierlichen Wachstums und der Verteilung über zahlreiche Knoten eines gebildeten Computernetzwerks wirksam sind in den späten 2000er Jahren eine Alternative zu herkömmlichen Datenbankverwaltungssystemen und Lösungen der Business-Intelligence-Klasse.

Unter Big Data verstehe ich also nicht eine bestimmte Datenmenge und nicht einmal die Daten selbst, sondern Methoden zu deren Verarbeitung, die eine verteilte Verarbeitung von Informationen ermöglichen. Diese Methoden können sowohl auf große Datensätze (wie den Inhalt aller Seiten im Internet) als auch auf kleine Datensätze (wie den Inhalt dieser Vorlesung) angewendet werden.

Hier sind einige Beispiele für eine Datenquelle, die Big-Data-Techniken erfordert:

• Protokolle des Benutzerverhaltens im Internet
• GPS-Signale von Autos für ein Transportunternehmen
• Daten von Sensoren im Large Hadron Collider
• Digitalisierte Bücher in der Russischen Staatsbibliothek
• Informationen zu Transaktionen aller Bankkunden
• Informationen zu allen Einkäufen in einer großen Einzelhandelskette usw.

Die Zahl der Datenquellen wächst rasant, wodurch Datenverarbeitungstechnologien immer gefragter werden.

3.2 Big-Data-Grundsätze

Basierend auf der Definition von Big Data können wir die Grundprinzipien für die Arbeit mit solchen Daten formulieren:

1. Horizontale Skalierbarkeit. Da es beliebig große Datenmengen geben kann, muss jedes System, das große Datenmengen verarbeitet, erweiterbar sein. Das Datenvolumen erhöhte sich um das Zweifache – die Eisenmenge im Cluster wurde um das Zweifache erhöht und alles funktionierte weiterhin.

2. Fehlertoleranz. Das Prinzip der horizontalen Skalierbarkeit impliziert, dass sich in einem Cluster viele Maschinen befinden können. Beispielsweise verfügt der Hadoop-Cluster von Yahoo über 42.000 Maschinen (unter diesem Link können Sie die Clustergrößen aller Organisationen sehen). Das bedeutet, dass einige dieser Maschinen garantiert ausfallen werden. Big-Data-Praktiken müssen sich dieser Störungen bewusst sein und sie ohne nennenswerte Konsequenzen überstehen.

3. Datenlokalität. In großen verteilten Systemen werden Daten auf eine große Anzahl von Maschinen verteilt. Wenn sich die Daten physisch auf einem Server befinden und auf einem anderen verarbeitet werden, können die Kosten der Datenübertragung die Kosten der Verarbeitung selbst übersteigen. Daher ist eines der wichtigsten Prinzipien für die Gestaltung von BigData-Lösungen das Prinzip der Datenlokalität – wenn möglich verarbeiten wir Daten auf derselben Maschine, auf der wir sie speichern.

Alle modernen Big-Data-Tools folgen auf die eine oder andere Weise diesen drei Prinzipien. Um ihnen zu folgen, ist es notwendig, einige Methoden, Methoden und Paradigmen für die Entwicklung von Datenentwicklungstools zu entwickeln. Eine der klassischsten Methoden, die ich in der heutigen Vorlesung analysieren werde.

3.3 MapReduce

MapReduce ist ein von Google vorgeschlagenes verteiltes Datenverarbeitungsmodell zur Verarbeitung großer Datenmengen auf Computerclustern. MapReduce wird durch das folgende Bild gut veranschaulicht:

MapReduce geht davon aus, dass die Daten in einigen Datensätzen organisiert sind. Die Datenverarbeitung erfolgt in 3 Stufen:

1. Kartenphase . In dieser Phase werden die Daten mithilfe der vom Benutzer definierten Funktion „map()“ vorverarbeitet. Die Arbeit dieser Phase besteht darin, die Daten vorzuverarbeiten und zu filtern. Die Operation ist der Kartenoperation in funktionalen Programmiersprachen sehr ähnlich – auf jeden Eingabedatensatz wird eine benutzerdefinierte Funktion angewendet.

Die Anwendung der Funktion „map()“ auf einen einzelnen Eingabedatensatz erzeugt viele Schlüssel-Wert-Paare. Set – das heißt, es kann nur einen Datensatz zurückgeben, möglicherweise nichts oder mehrere Schlüssel-Wert-Paare. Was im Schlüssel und im Wert enthalten sein wird, bleibt dem Benutzer überlassen, aber der Schlüssel ist eine sehr wichtige Sache, da Daten mit einem Schlüssel in Zukunft in eine Instanz der Reduzierungsfunktion fallen.

2. Bühnen-Shuffle. Es bleibt für den Benutzer unbemerkt. In dieser Phase wird die Ausgabe der Kartenfunktion „eingeteilt“ – jede Bin entspricht einem Ausgabeschlüssel der Kartenphase. In Zukunft werden diese Körbe als Input für Reduce dienen.

3. Stufe reduzieren. Jeder „Korb“ mit Werten, die in der Shuffle-Phase generiert wurden, gelangt an den Eingang der Funktion „reduce()“.

Die Reduzierungsfunktion wird vom Benutzer angegeben und berechnet das Endergebnis für einen einzelnen „Korb“ . Die Menge aller von der Funktion Reduce() zurückgegebenen Werte ist das Endergebnis der MapReduce-Aufgabe.

Einige zusätzliche Fakten zu MapReduce:

1. Alle Läufe der Kartenfunktion funktionieren unabhängig voneinander und können parallel ausgeführt werden, auch auf verschiedenen Cluster-Maschinen.
2. Alle Läufe der Reduce- Funktion arbeiten unabhängig voneinander und können parallel ausgeführt werden, auch auf verschiedenen Cluster-Maschinen.
3. Shuffle stellt intern eine parallele Sortierung dar, sodass es auch auf verschiedenen Cluster-Maschinen funktionieren kann. Mit den Punkten 1-3 können Sie das Prinzip der horizontalen Skalierbarkeit umsetzen .
4. Die Kartenfunktion wird normalerweise auf demselben Computer verwendet, auf dem die Daten gespeichert sind. Dies reduziert die Übertragung von Daten über das Netzwerk (Prinzip der Datenlokalität).
5. MapReduce ist immer ein vollständiger Datenscan, es gibt keine Indizes. Dies bedeutet, dass MapReduce schlecht anwendbar ist, wenn eine Antwort sehr schnell erforderlich ist.

3.4 Beispiele für effektiv gelöste Aufgaben mit MapReduce

Wortzahl

Beginnen wir mit der klassischen Aufgabe – dem Wortzählen. Die Aufgabenstellung ist wie folgt formuliert: Es liegt ein großer Dokumentenbestand vor. Die Aufgabe besteht darin, für jedes Wort, das mindestens einmal im Korpus vorkommt, die Gesamtzahl der Vorkommen im Korpus zu berechnen.

Lösung:

Da wir über einen großen Dokumentenkorpus verfügen, sei ein Dokument ein Eingabedatensatz für die MapRreduce-Aufgabe. In MapReduce können wir nur benutzerdefinierte Funktionen definieren, was wir tun werden (wir werden Python-ähnlichen Pseudocode verwenden):

def map(doc): 
for word in doc: 
yield word, 1 

def reduce(word, values): 
yield word, sum(values) 

Die Map- Funktion wandelt das Eingabedokument in einen Satz von Paaren (Wort, 1) um, shuffle wandelt es für uns transparent in Paare um (Wort, [1,1,1,1,1,1]), reduziert die Summen dieser und gibt zurück die endgültige Antwort für das Wort .

Verarbeitung von Werbesystemprotokollen

Das zweite Beispiel stammt aus der realen Praxis der Data-Centric Alliance.

Aufgabe: Es gibt ein CSV-Protokoll des Werbesystems der Form:

<user_id>,<country>,<city>,<campaign_id>,<creative_id>,<payment></p> 
 
11111,RU,Moscow,2,4,0.3 
22222,RU,Voronezh,2,3,0.2 
13413,UA,Kyiv,4,11,0.7 
… 

Es ist notwendig, die durchschnittlichen Kosten für die Anzeige von Werbung in den Städten Russlands zu berechnen.

Lösung:

def map(record): 
user_id, country, city, campaign_id, creative_id, payment = record.split(",") 
payment=float(payment) 
if country == "RU": 
yield city, payment 

def reduce(city, payments): 
yield city, sum(payments)/len(payments) 

Die Kartenfunktion prüft, ob wir diesen Eintrag benötigen – und hinterlässt in diesem Fall nur die notwendigen Informationen (Ort und Zahlungsbetrag) . Die Reduzierungsfunktion berechnet die endgültige Antwort für eine Stadt anhand einer Liste aller Zahlungen in dieser Stadt.