MapReduce
MapReduce (někdy též Map/Reduce nebo MapRed) je programovací model pro zpracování a generování velkých množin dat, vyvinutý společností Google pro návrhy paralelně zpracovávaných úloh, a současně knihovna v jazyce C++, která jej implementuje.
Princip
- Máme 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á noda z clusteru) přijme Map/Reduce požadavek od klienta
- Master noda rozešle funkci Map (nebo více zřetězených funkcí) všem ostatním nodá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 nod - 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 nod (a sám od sebe), nebo vyprší časový limit pro odpověď od těchto nod, 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 nod.
- 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ávací engine má cluster s redundantně replikovanou databází textových dokumentů - např replikace.: AB, BC, CA
- jedna z nod (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 nody 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é nodami, čí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).