MapReduce

MapReduce (někdy též Map/Reduce nebo MapRed) je programovací model pro zpracování velkých množin dat pomocí paralelního zpracování, a současně knihovna v jazyce C++, která jej implementuje.

Princip editovat

Mějme cluster databázových nebo jiných serverů
Jeden ze serverů (říkejme mu master, ale v některých modelech to může být libovolný uzel z clusteru) přijme požadavek Map/Reduce od klienta.
Uzel master rozešle funkci Map (nebo více zřetězených funkcí) všem ostatním uzlům clusteru, ty provedou kód této funkce a vrátí masteru výsledky, které mohou být i duplicitní (více stejných výsledků z několika uzlů — to je žádoucí kvůli odolnosti proti výpadkům). Master může také zpracovat funkci Map a také to v některých implementacích dělá.
V okamžiku, kdy má master dostatek výsledků z fáze Map od ostatních uzlů (a sám od sebe), nebo vyprší časový limit pro odpověď od těchto uzlů, provede master nad navrácenou množinou dat funkci Reduce. Fáze Reduce odstraní duplicitní data a provede operace, které je možné provést jen v případě, že máme kompletní množinu výsledků ze všech uzlů.
Na konci fáze Reduce je možné navrátit výsledek klientovi, který si tuto operaci zadal.

Postup editovat

Uživatel definuje funkci map (mapování), která z dvojic (klíč, hodnota) vygeneruje pracovní dvojice (klíč2, hodnota2), a funkci reduce (redukce), která spojí všechny hodnoty v pracovních datech, které mají stejný klíč.

Je přitom podstatné, že všechny mapovací funkce mohou běžet nezávisle a své výsledky mohou přímo postupovat redukčním funkcím odpovědným za daný pracovní klíč. Zpracování takto popsané úlohy je tedy téměř lineárně paralelizovatelné.

Příklad editovat

Vyhledávač má cluster s redundantně replikovanou databází textových dokumentů — např. replikace: AB, BC, CA.
Jeden z uzlů (master) dostane od klienta MR požadavek vrátit jména všech dokumentů obsahujících "ŘETĚZEC", číslo řádky a text celé řádky.
MAP(): všechny uzly projdou všechny řádky ve všech dokumentech a vrátí je masteru v poli, kde index je jméno dokumentu a číslo řádky, daty je potom text této řádky.
REDUCE(): master spojí všechna pole vrácené uzly, čímž odstraní (zredukuje) duplicitní indexy (a tím i duplicitní řádky).
výsledky fáze Reduce je možné vrátit uživateli

Příklady použití editovat

Frekvence přístupů na webové stránky: Mapovací funkce zpracovává log požadavků na stránky, výstupem jsou dvojice (URL, 1). Redukční funkce pro každý klíč sčítá hodnoty, výstupem jsou dvojice (URL, celkový počet).
Graf zpětných odkazů: Mapovací funkce vydá (cíl, zdroj) pro každý odkaz na “cíl”, který nalezne v dokumentu “zdroj”. Redukční funkce hodnoty spojuje, takže výsledkem je množina dvojic (cíl, seznam zdrojů).
Zpětný index: Mapovací funkce zpracuje každý dokument, výstupem je větší počet dvojic (IDslova, IDdokumentu). Redukční funkce seřadí všechny hodnoty pro daný klíč a vygeneruje dvojici (IDslova, seznam IDdokumentu).

Související články editovat

Externí odkazy editovat

Obrázky, zvuky či videa k tématu MapReduce na Wikimedia Commons
MapReduce: Simplified Data Processing on Large Clusters
Jak funguje MapReduce