MapReduce
Kiejtés
- IPA: [ ˈmɒprɛdut͡sɛ]
Főnév
MapReduce
- (matematika, algoritmusok) A MapReduce egy programozási modell és keretrendszer, amelyet nagy méretű adathalmazok párhuzamos feldolgozására terveztek elosztott környezetben. A koncepciót a Google fejlesztette ki, és széles körben alkalmazzák big data feldolgozásra.
Alapötlet
A MapReduce két fő fázisra bontja az adatfeldolgozást:
- Map (leképezés):
- Az adatok párhuzamos feldolgozása kisebb részekre bontva.
- A bemeneti adatokat kulcs-érték párokra bontja, majd transzformációt alkalmaz.
- Reduce (összegzés):
- A kulcs-érték párok csoportosítása kulcs szerint, majd az adatok összesítése vagy aggregálása.
Ezeket a fázisokat egy shuffle and sort lépés köti össze, amely az adatok újracsoportosításáért felel.
Működés lépései
1. Map fázis
- A bemeneti adatokat feldolgozza, és kulcs-érték párokat generál.
- Példa: Egy szöveges fájl szavainak számlálása esetén minden szó egy kulcs, az érték pedig az előfordulások száma (kezdetben mindig 1).
2. Shuffle and Sort
- Az adatok kulcsok szerint csoportosítva kerülnek tovább a Reduce fázisba.
- Példa: Az azonos kulcsokhoz tartozó értékeket összecsoportosítja.
3. Reduce fázis
- Az azonos kulcsokhoz tartozó értékeket feldolgozza, például összeadja, átlagolja vagy más aggregációt végez.
- Példa: Egy adott szó előfordulási számának összegzése.
Pszeudokód
Szavak számlálása (Word Count)
Bemenet: Egy szöveges fájl. Kimenet: Az összes szó és az előfordulási száma.
// Map fázis
function map(String input):
for each word in input:
emit(word, 1)
// Reduce fázis
function reduce(String key, List values):
sum = 0
for value in values:
sum += value
emit(key, sum)
Python implementáció
A MapReduce folyamat egyszerű példája: szavak számlálása egy szöveges fájlban.
from collections import defaultdict
# Map fázis
def map_function(text):
results = []
for word in text.split():
results.append((word, 1))
return results
# Reduce fázis
def reduce_function(mapped_data):
reduced = defaultdict(int)
for key, value in mapped_data:
reduced[key] += value
return reduced
# Példa
text = "hello world hello mapreduce world mapreduce mapreduce"
mapped = map_function(text)
reduced = reduce_function(mapped)
print("Szavak előfordulása:", dict(reduced))
Kimenet:
Szavak előfordulása: {'hello': 2, 'world': 2, 'mapreduce': 3}
C++ implementáció
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
using namespace std;
// Map fázis
vector<pair<string, int>> map_function(const string& text) {
vector<pair<string, int>> results;
stringstream ss(text);
string word;
while (ss >> word) {
results.emplace_back(word, 1);
}
return results;
}
// Reduce fázis
unordered_map<string, int> reduce_function(const vector<pair<string, int>>& mapped_data) {
unordered_map<string, int> reduced;
for (const auto& pair : mapped_data) {
reduced[pair.first] += pair.second;
}
return reduced;
}
int main() {
string text = "hello world hello mapreduce world mapreduce mapreduce";
vector<pair<string, int>> mapped = map_function(text);
unordered_map<string, int> reduced = reduce_function(mapped);
cout << "Szavak előfordulása:" << endl;
for (const auto& [word, count] : reduced) {
cout << word << ": " << count << endl;
}
return 0;
}
Kimenet:
Szavak előfordulása: hello: 2 world: 2 mapreduce: 3
Alkalmazások
- Nagy adathalmazok feldolgozása:
- Log fájlok elemzése.
- Keresési indexek építése.
- Adatbányászat:
- Mintaillesztés nagy adathalmazokban.
- Asszociációs szabályok feltárása.
- Pénzügyi elemzés:
- Ügyféladatok szegmentálása és aggregálása.
- Tudományos számítások:
- Nagy adatállományok szimulációja (pl. genomika, asztrofizika).
Előnyök
- Egyszerű programozási modell:
- A programozóknak csak a Map és Reduce funkciókat kell megírniuk.
- Skálázhatóság:
- Elosztott rendszerekben egyszerűen skálázható több gépre.
- Hibatűrés:
- Az adatok redundánsan tárolódnak, és a hibás feladatok újraindíthatók.
Hátrányok
- Nem alkalmas minden problémára:
- Iteratív vagy függő számítások nem hatékonyak.
- I/O-költségek:
- A shuffle and sort lépés nagy mennyiségű adatot mozgat, ami lassítja a folyamatot.
- Fejlett optimalizáció hiánya:
- A MapReduce egyszerűsége miatt kevésbé optimalizált, mint más adatfeldolgozási keretrendszerek.
Modern implementációk
- Hadoop: A MapReduce legnépszerűbb nyílt forráskódú implementációja.
- Spark: Fejlettebb adatfeldolgozási keretrendszer, amely gyorsabb alternatívája a MapReduce-nak.
- Google Cloud Dataflow: Felhőalapú MapReduce-feldolgozás.
A MapReduce az elosztott adatfeldolgozás egyik alapvető modellje, amely egyszerűsége és hatékonysága miatt továbbra is széles körben alkalmazott a big data világában.