Dnes: 28. dubna 2017    | Registrace | Hledáme | Redakce | Info | Testy | Školení | Ocenění | Nápověda | Čtenář: nepřihlášen

Rychlé odkazy
  • Hlavní stránka
  • Seznam rubrik
  • Ankety
  • Editoriály
  • TOP 15
  • KONFERENCE 2008
  • KONFERENCE 2007
  • KONFERENCE 2006
  • KONFERENCE 2005
  • KONFERENCE 2004
  • Sborník
  • Testy
  • Virtuální školení
  • Personalizace


  • Hledáte práci?
    Hledáme redaktora - pojďte s námi tvořit Databázový svět!

    Vyhledávání

    Hledej
    na Databázovém světě!



    Rozšířené vyhledávání

    Rubriky
    Aktuality
    Bezpečnost
    Business
    Česká scéna
    Datové sklady
    Dokumentace
    Dotazovací jazyky
    Hardware
    Historie
    Komentáře
    Literatura
    Metodologie
    Nondb
    Open Source
    Poradna
    Produkty
    Případové studie
    Redakce
    Rozhovory
    Standardy
    Technologie
    Tipy - triky
    Tiskové zprávy
    Vývoj
    Vývojové nástroje
    Zajímavosti

    Co je to?
    Replikace
    Replikace slouží pro zajištění konzistentnosti dvou a více databází, nejčastěji pak o stejné struktuře v rámci distribuovaného zpracování. Vyspělé SŘBD replikace podporují, případně lze použít řešení třetích stran či replikační logiku zajistit vlastními postupy.

    Akce
    Dynamická Datová Centra
    - na semináři se seznámíte s komplexním řešením a koncepcí Dynamických Datových Center od Fujitsu Siemens Computers se speciálním důrazem na řešení FlexFrame.

    Textová inzerce
    IBPhoenix - Vše o InterBase a Firebirdu.

    Smějete se rádi? - Pak je pro vás Vtipník to pravé!

    Prodejce reklamy - Hledáme schopného prodejce reklamního prostoru, možnost i externí spolupráce.

    Přihlášený čtenář
    Nepřihlášený čtenář

    O portálu
    Databázový svět
    ISSN: 1213-5933

    Web je optimalizován pro rozlišení 1024x768, nicméně kromě větších rozlišení podporujeme i 800x600. Podrobnosti najdete zde.

    Chcete-li mít kdykoliv možnost zkontrolovat obsah našeho portálu, můžete využít podporu rss. Podrobnosti najdete zde.
    Map&Reduce – jak to dělá Google?


    [Zajímavosti] - S rozšiřujícím se rozmachem počítačů přibývá také dat, která je třeba zpracovávat. Avšak ne vždy můžeme lehce zvyšovat výkon, například proto, že produkce našich dat, respektive úkolů nad nimi by vyžadovala velký skokový růst výkonu, kterého těžko dosáhneme.



    Na druhou stranu se ukazuje, že pro jisté třídy úloh je možné se dostat na lepší výsledky než obecně a přitom tato omezení nemusí být pro nás problémem. Jako příklad můžeme použít řazení posloupnosti. Je dobře známo, že pro obecnou posloupnost je dolní odhad času n*log n. Ale i přesto můžeme dosáhnout zlepšení v podobě například O(n). Příkladem je algoritmus Count Sort (konkrétně O(n+k), kde n je délka vstupního pole a k délka "count" pole), patřící mezi lineární řadící algoritmy. Ten je vhodný, pokud vstupní množina bude obsahovat relativně málo různých prvků (avšak v mnoha opakováních). Jinou možností je masivní paralelizace – rozdělení úkolu na mnoho strojů, které vyřeší malý kousek úlohy. Zde je možné se dostat s rychlostí i do sublineárního času.

    Právě paralelizace je velmi zajímá možnost, neboť vlastní stoje jsou dnes velmi levné (v porovnání se speciálními clustery). Na druhou stranu je velmi obtížné psát (a ladit) programy, které poběží v distribuovaném prostředí. Je třeba též řešit rozdělení zátěže, odolnost proti výpadkům, prostorovou lokalitu dat (je-li to významné) či "jen" schopnost algoritmu dobře škálovat po přidání dalších strojů.

    Jedním ze zajímavých modelů je tzv. MapReduce model či chcete-li přístup. Jedná se o omezený programovací model, na druhou stranu však přináší mnohé výhody – de facto všechny nevýhody popsané výše jsou tímto modelem vyřešeny. Primitiva map a reduce jsou známa především z funkcionálních programovacích jazyků – např. Lisp, Haskell apod.

    Infrastruktura MapReduce je rozdělena na dva základní elementy:

    • Map – funkce beroucí jako vstup dvojici {klíč, hodnota} a na výstup dává jinou dvojici {klíč, hodnota}
    • Reduce – tato funkce dostává jako vstup výstup předchozí funkce a jako výstup již poskytuje výsledek nebo množinu výsledků (mohou být dále zpracovávány).

    Mezi tyto funkce bývá většinou vřazena jedna nebo více pomocných funkcí, například pro šetření datového toku mezi stroji apod., stejně tak výsledek může být ještě finálně transformován.

    Pro pochopení uveďme dva jednoduché příklady – počítání slov v textu a tvorba invertovaného indexu:

    • Funkce map pro každé slovo vrátí {<slovo>, 1} a reduce provede sumaci těchto dvojic. Výsledkem je počet slov pro každé slovo v textu.
    • Funkce map pro každá slovo vrátí {<slovo>, <identifikace dokumentu>} a reduce pro každé slovo seřadí identifikace dokumentů a vrátí {<slovo>, list(<identifikace dokumentu>, …)}. Tento "seznam" je jednoduchý invertovaný index.

    Možná se nyní pozastavujete nad tím, kde je vidět zmiňovaná paralelizace? Jak jsme již uvedli výše, výhodou tohoto modelu je skrytí vlastní paralelizace před programátorem – je proto možné uvažovat v rámci běžného sekvenčního neparalelního programování. Avšak pokud – pro náš příklad – vstupní text bude rozdělen na M dílů, může být těchto M dílů předáno jednotlivým map funkcím, které běží na mnoha strojích. Výsledek, samozřejmě po stejně distribuované aplikaci funkce reduce, může být spočítán mnohem (řádově) rychleji.

    A jak to vše souvisí s Googlem? Právě Google se začátkem roku 2003 začal o možnosti využití MapReduce zajímat. A velmi se jim možnosti, které tento model nabízí, zalíbily. Během roku a půl bylo napsáno téměř 900 aplikací využívajících vlastní googlovskou implementaci v C++. Mimo jiné na tomto systémů běží i indexovací systém, který je využíván pro hledání na webu. Tento systém zpracovává desítky terabajtů dat (kolem roku 2004 přibližně 20 TB) a došlo i ke zjednodušení vlastního kódu z přibližně 3800 řádek C++ kódu na 700 (a samozřejmě díky zaměření se pouze na vlastní tvorbu indexu je kód lépe udržovatelný).

    Google využívá pro tyto distribuované výpočty levné stroje s jednotkami GB RAM a levnými IDE disky. Tyto stroje konstantně "umírají" – proto je třeba jednotlivé přidělené díly k výpočtu v případě potřeby zpracovat znova. Toto hlídání zajišťuje plánovací systém s master procesem. Tento master proces řídí také rozdělování úloh – především tak, aby jednotlivé procesy byly na strojích, které daná data obsahují (čí jsou na strojích, například na stejném přepínači) a také tak, aby všechny procesy byly "blízko" u sebe (pro optimalizaci toku dat na síti). Protože vlastní distribuovaný systém souborů Googlu – GFS využívá relativně velké bloky dat (v řádech desítek megabajtů) jsou data pro jednotlivé map procesy vybírána podobných velikostí jako bloky na disku – mezi 16 MB až 128 MB.


    Fungování MapReduce [Zdroj: Google Labs]

    Jak jsme uvedli na začátku, k výpadkům strojů dochází často a je třeba proces běžící na tomto stroji spustit znovu. Překvapivě to není jediný problém – v Googlu zjistili, že někdy stroj nevypadne kompletně, ale rapidně se sníží jeho výkon, například. kvůli chybujícímu disku, odcházející síťové kartě apod. a dokončení úkolu, který je stroji přidělen pak trvá extrémně dlouho a brzdí výpočet jako celek.

    Proto při finální fázi master proces úkoly, které stále nejsou dokončeny, předá zároveň na jiný stroj, který již svůj díl dokončil. Výsledek, který dostane první, použije. Bez použití tohoto principu dochází k prodloužení doby dokončení o několik (desítek) procent – například při řazení přibližně jednoho terabajtu dat na ~1800 strojích došlo k nárůstu času o 44 %. Zajímavé také je, že při simulaci výpadku 200 strojů došlo pouze k 5% nárůstu času získání výsledku. Abychom si udělali představu, jak v obrovském balíku strojů, které jsou pro spuštění MapReduce procesů používány, dochází k výpadkům strojů (a tedy že se jedná o opravdu běžná PC), uveďme, že při průměrném času 634 sekund na dokončení úlohy (srpen 2004) dojde v průměru k výpadku 1,2 stroje.

    Není překvapením, že rozdělením úkolu na části a necháním jej spočítat na mnoha strojích přináší své výsledky. Vždyť většina dnešních počítačů na trhu obsahuje minimálně dvě jádra a každým rokem obsahují nové procesory jader více. Programování pro stroj s dvěma, čtyřmi, možná osmi procesory, tak aby byly tyto jednotky dobře zatíženy, je ještě úkol, který zvládne většina programátorů v libovolném jazyce. Ale programování pro tisíce procesorů, které ani nejsou v jednom počítači (tedy nemají například společnou blízkou paměť) není úplně triviální (obecně paralelizace algoritmu není triviální). S použitím MapReduce přístupu, se problém citelně zjednodušil a není problém takto výpočet téměř bez práce paralelizovat na tisíce strojů – leč vaše úloha musí být vyjádřitelná pomocí těchto dvou funkcí, což nemusí být vždy jednoduché nebo dokonce možné.

    ( Celý článek! | Autor: Jiří Činčura | Počet komentářů: 1 | Přidat komentář | Informační e-mailVytisknout článek )

    Vyhledávání
     

    Anketa
    Kolik ročně utratíte za dovolené?

    Nic 
     (1121 hl.)
    Do 1 000,- Kč 
     (816 hl.)
    Do 10 000,- Kč 
     (785 hl.)
    Do 25 000,- Kč 
     (1045 hl.)
    Do 50 000,- Kč 
     (807 hl.)
    Do 75 000,- Kč 
     (942 hl.)
    Více než 75 000,- Kč 
     (787 hl.)

    Celkem hlasovalo: 6303


    Poslední komentáře
    frontierd@126.com
    frontierd@126.com
    frontierd@126.com
    c
    http://www.coachoutl

    Newsletter
    Přihlaste si nezávazně - i bez registrace - odběr informačního newsletteru. Podrobné informace najdete zde.

    Emailová adresa:


    Kalendář
    <<  Duben  >>
    PoÚtStČtSoNe
         12
    3456789
    10111213141516
    17181920212223
    24252627282930

    Redakci připojuje


    Nejčtenější

    Databáze je prázdná!


    Nejvíce komentářů

    Databáze je prázdná!


    Reklama






    Nenechte si ujít články na dalších webech




    Na této stránce použité názvy programových produktů, firem apod. mohou být ochrannými známkami
    nebo registrovanými ochrannými známkami příslušných vlastníků.

    Databázový svět | dfKlub - digitální fotografie | Vtipník - vtipy přímo k Vám | Reminder - přestaňte zapomínat | Databázový svět

    Copyright (c) 2004 AVRE Publishing, spol. s r.o. Všechna práva vyhrazena