Princip:

• MAP
  • vstupní data ve formátu <KEY1, VALUE1> konvertuje na <KEY2,VALUE2>
• 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
  • A pak musí data přenést (síť)
• 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
• Proč použít combiner
  • data jsou načtena v paměti, ušetří se IO operace – čtení
  • často je výstup menší než vstup, ušetří se IO operace – zápis (a následné čtení)

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
• nevhodné úlohy
  • průměr, medián - lze přeformulovat

Kdy použít MapReduce › Tam, kde úloha umožňuje paralelizaci – a lze ji převést na úlohu vhodnou pro MapReduce › Při práci se skutečně velkými daty (petabajty) – tak velká data se v paměti nedají uchovávat/zpracovat › 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í › Když není dostatek paměti v clusteru

Kdy není vhodný MapReduce › Tam, kde úlohu nelze paralelizovat a převést na MapReduce kompatibilní  › Je-li vyžadována okamžitá reakce – i pro jednoduché úlohy trvá inicializace velmi dlouho › Když je úkol „malý“