MapReduce zaklínadlo pre big data

MapReduce hlavné zaklídandlo pre big data - ako to funguje

MapReduce je pre big data tým, čím je optický kábel pre dátovú komunikáciu. Je to najuniverzálnejší sposob masívneho paraleného spracovania veľkých objemov dát. Túto metódu vytvoril Google a implementoval ju do vlastnej technológie. Google si však toto know how neponechal pre seba, ale publikoval ho verejne prostredníctvom vedeckého článku. Následne viacero spoločnosti a open sourceových komunít na týchto princípoch vyvinuli vlastné systémy. Najznámejším je  Apache Hadoop. Je tu však aj mnoho iných, ako MongoDEB, Couchdb, Riak a ďalšie.

Prečo je MapReduce taký dôležitý? Pri paralelnom spracovaní veľkých dát musia programátori okrem napísania kódu pre samotný algoritmus riešiť aj rozloženie úloh medzi jednotlivé počítače (uzly), zozbieranie všetkých čiastkových výsledkov a ich následnú agregáciu, presúvanie dát medzi počítačmi a ich vzájomnú komunikáciu.

Počítačový server vydrží bežať bez poruchy niekoľko rokov. Pri veľkom počte uzlov však musíme počítať s oveľa častejšími zlyhaniami. Ak by priemerná dĺžka bezporuchovej prevádzky  servera bola, povedzme, 2 roky, tak v zoskupení (clusteri) 2 000 serverov, čo nie je dnes nič mimoriadne, by v priemere vypadol jeden server každých 9 hodín. Súčasťou  každého výpoču musí byť teda aj kontrola, či všetky uzly svoju časť výpočtu dokončili.

Systémy ako Hadoop sa o všetky tieto “vedľajšie” záležitosti postarajú samé. Programátor potrebuje naprogramovať len dve funkcie (procedúry): map a reduce. (Tieto názvy pochádzajú z funkcionálneho programovania a nevyjadrujú veľmi presne to, ako táto metóda funguje, takže človek pochopí MapReduce ľahšie, ak v týchto slovíčkach nebude hľadať veľký zmysel.)

Najlepšie bude vysvetliť to na príklade.

Predstavme si, že chceme urobiť vyhľadávač web stránok, podobne ako Google ;-). Jeho úlohou bude nájsť v databáze stránok všetky, ktoré obsahujú hľadaný výraz a potom ich zoradiť podľa počtu odkazov z iných stránok na danú ňu.

Vytvorme si teda databázu všetkých web stránok, kde budeme mať adresu stránky, jej obsah (text) a počet stránok, ktoré na ňu odkazujú. Ako pomocou MapReduce urobiť rýchle vyhľadávanie a zoradenie stránok s hľadaným výrazom?

Najprv si urobíme funkciu pre fázu map. Vstupnými parametrami do tejto funkcie budú vyhľadávaný výraz (alebo výrazy), text web stránky, jej adresa a počet linkov na túto stránku. Funkcia prehľadá text web stránky a zistí či sa na v ňom nachádzajú vyhľadávané výrazy (pre jednoduchosť ilustračného príkladu nebudeme uvažovať o indexovaní ale o surovom vyhľadávaní textu na stránkach v databáze). Ak na danej stránke nájde hľadaný výraz (výrazy), výstupom tejto funkcie bude adresa web stránky a počet linkov odkazujúcich na stránku. V opačnom prípade bude výstup prázdny.

Funkcia pre fázu reduce bude mať ako vstup adresu web stránky a počet odkazov na ňu. Jej úlohou bude zoradiť stránky podľa počtu odazov od najvyššiho po najnižší.

Programátorovi stačí napísať tieto dve funkcie a o zbytok, teda rozdelenie prehľadávaných stránok medzi jednotlivé uzly (workers) a zozbieranie všetkých výsledkov týchto uzlov a usporiadanie všetkých výsledkov do jedného celku sa postará systém, presnešie riadiaci počítač (master).

Celý proces výpočtu sa dá rozpísať do piatich, na seba nadväzujúcich, krokov:

Pať fáz MapReduce -s harding, map, shuffle, reduce, aggregate
Pať fáz MapReduce

 

  1. Rozdelenie – riadiaci počítač pripraví rozdelenie vstupov pre funkciu map pre jednotlivé robotnícke počítače podľa daného kľúča (napríklad podľa hlavnej domény adresy dokumentu)
  2. Funkcia map s užívateľským programom sa spustí na jednotlivých robotníckych počítačoch podľa daného kľúča (napr hlavnej domény). Výstupm je pár key/value (value môže byť aj viac hodnôt (list), napríklad key je počet odkazov na stránku a value je adresa stránky). Riadiaci počítač zabezpečí aby sa pre každú hodnotu vstupného kľuča funkcia map spustila práve raz. Ak na nejakom robotníckom počítači nastane porucha, alebo mu spracovanie trvá príliš dlho, systém túto úlohu zruší a pridelí ju inému robotníckemu počítaču.
  3. Shuffle – riadiaci počítač rozdelí výsledky spracovania fázy map na základe kľúča z map funkcie (napr. podľa rozsahu počtu odkazov na jednotlivé stránky) medzi jednotlivé robotínícke počítače pre fázu reduce. Zároveň presunie na príslušné robotnícke počítače všetky vstupné údaje (výstupy z fázy map).
  4. Funkcia reduce s užívateľským programom sa spustí na jednotlivých robotníckych počítačoch. Riadiaci počítač zabezpečí, aby sa spracoval každý výstup z fázy map práve raz.
  5. Agregácia – riadiaci počítač zozbiera všetky výsledky fázy reduce a zoradí ich podľa kľúča (je to rovnaký kľúč ako vstupný kľúč ako pre fázu reduce, teda v našom príklade počet odkazov na danú stránku). Poznámka: ak by sme fázu reduce nastavili tak, aby na každý robotnícky počítač išli stránky s rovnakým počtom odkazov, nemuseli by sme funkciu reduce vôbec programovať, systém by sám roztriedil stránky podľa počtu odkazov.

Pre úplnosť je potrebné dodať, že MapReduce v tejto podobe je už už dnes relatívne zastaralý. Stále je to však z najrozšírenejších algoritmických modelov, ak nie vôbec najrozšírenejší, pre masívne paralelné spracovanie dát.

Superinovátor Google už nahradil svoj pôvodný MapReduce systém novším systémovm Cloud Dataflow. Podobne aj Apache v rámci Hadoop ponúka YARN, ktorý je označovaný ako MapReduce 2.0. Tak ist aj mnohí ďalši. Väčšinou to však nie sú úplne nové koncepty, ale vylepšenia a rozšírenia “príliš jednoduchého” pôvodného MapReduce. MapReduce teda nie je slepou uličkou ale raným vývojovým štádiom v spracovaní big data a pochopenie tohto konceptu je dobrým východiskovým bodom pre zvládnutie najmodernejších technológií v tejto oblasti.

Zdieľať na Sieti:

Názor k “MapReduce hlavné zaklídandlo pre big data - ako to funguje

  1. Spätné upozornenie: Hadoop alebo NoSQL?

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *