MapReduce

Princip:

• MAP
  • vstupní data ve formátu <KEY1, VALUE1> konvertuje na <KEY2,VALUE2>
  • často nás KEY1 nezajímá - může být offset souboru
• REDUCE
  • vstupní data ve formátu <KEY2, LIST(VALUE2)> konvertuje na <KEY3,VALUE3>

Mapper

• vstupní údaje mapuje na hodnoty typu klíč – hodnota
• vstupem je formálně také klíč – hodnota
• ale často nás klíč vůbec nezajímá! Je to třeba offset souboru
• klíč se může libovolně opakovat, hodnota může být různá
• Typicky probíhá v mnoha paralelních jobech
  • Každý soubor, resp. split je zpracován samostatným mapperem
• Výstup se zapisuje na lokální disk

Shuffle & Sort

• vstupem jsou vygenerované soubory z mapperů
• všechna data se stejným klíčem slije na jeden node
  • tj. musí data načíst z jednotlivých nodů (disková operace)
  • ale čte je jen z lokálních disků, nikoli z HDFS
• setřídí data podle klíče (merge)
• optimalizace – malá data pošle rovnou do reduceru, velká merguje na lokálním disku
• typicky nejnáročnější operace

Reduce

• čte produkovaná data pomocí Shuffle & Sort
• všechny dvojice klíč/hodnota se stejným klíčem jdou do stejného reduceru
• „redukuje“ list hodnot čtených z výstupy Shuffle & Sort
• zpravidla je reducerů (řádově) méně než mapperů
• počet lze definovat, default je 1
• každý reducer generuje 1 soubor do HDFS
• výstup se nijak nesortuje

Combiner

• sníží zátěž Shuffle&Sort části
• volitelná část zpracování mapperu, provádí reduce na straně mapperu
• stejné rozhraní jako Reducer
• používáme, protože Shuffle&Sort je nejnáročnější operace, tohle jí uleví

Partitioner

• Partitioner rozděluje data do několika partitions
  • podle klíče
  • podle hodnoty
• MapReduce zajišťuje, že jedna partition je zpracována jedním reducerem
• vlastní partitioner lze použít např. v případech, kdy
  • chci znát nějaké specifické rozdělení (např. věkové kategorie)
  • mám velmi nevyvážené klíče (jeden klíč se vyskytuje abnormálně často)
• klíče jsou z shuffle&sort poslány do partitioneru, který rozhoduje, do kterého reduceru půjde
• Partitioner je funkce, která hashuje klíč a vezme modulo tohoto hashe a počtu reduceru, aby zjistil, který reducer dostane daný pár klíč-hodnota. jelikož hash jednoho klíče bude pořád stejný, všechny páry klíč-hodnota se stejným klíčem budou poslány do stejného reduceru

Příklady

• vhodné úlohy
  • počet slov v textu, četnost slov, reporting – načítání řady dílčích výsledků (prodeje), podle klienta, produktu nebo lokality, řazení dat (sortování), filtrování dat, validace
  • umožňující paralelizaci, při práci se skutečně velkými daty (PB), při práci s výpočetně náročnými úlohami, kde se spíše data načítají než zapisují, když není čas kritický, stačí dávkové zpracování
• nevhodné úlohy
  • průměr, medián - lze přeformulovat
  • nelze paralelizovat, je-li vyžadována okamžitá reakce, když je úkol „malý“
• musí splňovat 3 podmínky
  • asociativita - neovlivníme pořadí vykonávaných operací
  • komutativita - mapper/shuffle může změnit pořadí dat → lze použít combiner
  • existence nulového prvku - node, který nemá výstup/nezpracovává data, neovlivní výsledek