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
kj/mapreduce.txt · Poslední úprava: 18.09.2017 15:50 autor: kj

Nástroje pro stránku