MapReduce
MapReduce 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
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ří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).