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

• 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

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

• 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í

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

• Google
• Google File System

Externí odkazy

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

Autoritní data	LCCN: no2013077469 NLI: 987007371891305171 VIAF: 305041139