MapReduce

MapReduce je programovací model zavedený společností Google Inc. pro souběžné výpočty nad (několik petabajtů ) velkého množství dat v počítačových klastrech . MapReduce je také název implementace programovacího modelu ve formě softwarové knihovny.

U metody MapReduce jsou data zpracovávána ve třech fázích (Map, Shuffle, Reduce), z nichž dvě jsou specifikovány uživatelem (Map and Reduce). To umožňuje paralelizovat výpočty a distribuovat je do několika počítačů. V případě velmi velkého množství dat může být nutná paralelizace, protože množství dat je pro jeden proces (a provádějící počítačový systém) příliš velké.

Programovací model byl inspirován mapou a funkcemi redukce , které se často používají ve funkčním programování , i když se od nich liší způsob práce knihovny. V roce 2010 byl pro MapReduce udělen americký patent. Hlavním příspěvkem MapReduce je však základní systém, který silně paralelizuje výpočty, optimalizuje reorganizaci dat v kroku náhodného míchání a může automaticky reagovat na chyby v klastru, jako je selhání celých uzlů.

Způsob práce

Ilustrace toku dat

Obrázek výše ilustruje tok dat ve výpočtu MapReduce.

• Fáze mapy:
  • Vstupní data (D, A, T, A) jsou distribuována do několika mapových procesů (ilustrovaných barevnými obdélníky), z nichž každý vypočítává mapovou funkci poskytovanou uživatelem.
  • Mapové procesy se v ideálním případě provádějí paralelně.
  • Každá z těchto instancí mapy ukládá průběžné výsledky (ilustrované růžovými hvězdami).
  • Z každé instance mapy proudí data do případně různých mezilehlých pamětí výsledků.
• Náhodná fáze:
  • Mezivýsledky jsou redistribuovány podle výstupních klíčů vytvořených funkcí mapy, takže všechny mezivýsledky se stejným klíčem jsou zpracovány v dalším kroku ve stejném počítačovém systému.
• Snižte fázi:
  • Pro každou sadu průběžných výsledků přesně jeden redukční proces (ilustrovaný fialovými obdélníky) vypočítá redukční funkci poskytnutou uživatelem a tedy výstupní data (ilustrovaná fialovými kruhy X, Y a Z ).
  • V ideálním případě se redukční procesy provádějí také paralelně.

Definice funkce MapReduce

Tyto MapReduce knihovna implementuje funkce , která vypočítá nový seznam dvojic klíč-hodnota (seznam výstup) z v seznamu všech dvojic klíč-hodnota (seznam vstupu):

${\ displaystyle {\ begin {aligned} \ mathrm {MapReduce}: (K \ times V) ^ {*} & \ to (L \ times W) ^ {*} \\ {\ lbrack (k_ {1}, v_ {1}), \ ldots, (k_ {n}, v_ {n}) \ rbrack} & \ mapsto \ lbrack (l_ {1}, w_ {1}), \ ldots, (l_ {m}, w_ { m}) \ rbrack \ end {zarovnáno}}}$

Vysvětlení:

• Množství a obsahují klíče , množství a obsahují hodnoty .${\ displaystyle K}$${\ displaystyle L}$${\ displaystyle V}$${\ displaystyle W}$
• Všechny klíče jsou stejného typu , např. B. Struny.${\ displaystyle k \ v K}$
• Všechny klíče jsou stejného typu, např. B. celá čísla.${\ displaystyle l \ v L}$
• Všechny hodnoty jsou stejného typu, např. Atomy.${\ displaystyle v \ ve V}$
• Všechny hodnoty jsou stejného typu, např. B. Čísla s plovoucí desetinnou čárkou.${\ displaystyle w \ in W}$
• Pokud a jsou množiny, pak se míní množina všech párů , kde a ( kartézský součin ).${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A \ krát B}$${\ displaystyle (a, b)}$${\ displaystyle a \ v A}$${\ displaystyle b \ v B}$
• Pokud existuje množina, pak je míněna množina všech konečných seznamů s prvky (na základě hvězdy Kleene ) - seznam může být také prázdný.${\ displaystyle M}$${\ displaystyle M ^ {*}}$${\ displaystyle M}$

Definice mapy a redukčních funkcí

Uživatel konfiguruje knihovnu poskytnutím dvou funkcí Map a Reduce, které jsou definovány následovně:

${\ displaystyle {\ begin {aligned} \ mathrm {Map}: K \ times V & \ to (L \ times W) ^ {*} \\ (k, v) & \ mapsto \ lbrack (l_ {1}, x_ {1}), \ ldots, (l_ {r_ {k}}, x_ {r_ {k}}) \ rbrack \ end {zarovnáno}}}$

nebo.

${\ displaystyle {\ begin {aligned} \ mathrm {Reduce}: L \ times W ^ {*} & \ to X ^ {*} \\\ left (l, {\ lbrack y_ {1}, \ ldots, y_ {s_ {l}} \ rbrack} \ right) & \ mapsto \ lbrack w_ {1}, \ ldots, w_ {m_ {l}} \ rbrack \ end {aligned}}}$

Fáze mapy

• Mapa mapuje dvojici skládající se z klíče a hodnoty na seznam nových párů, které hrají roli mezivýsledků . Hodnoty jsou stejného typu jako konečné výsledky .${\ displaystyle k}$${\ displaystyle v}$${\ displaystyle (l_ {r}, x_ {r})}$${\ displaystyle x_ {r}}$${\ displaystyle w_ {i}}$
• V případě nového páru klíč přiřazený mapou odkazuje na seznam průběžných výsledků, ve kterých se shromažďuje hodnota vypočítaná mapou .${\ displaystyle (l, x)}$${\ displaystyle l}$${\ displaystyle T_ {l}}$${\ displaystyle x}$
• Knihovna volá funkci Map pro každý pár ve vstupním seznamu.
• Všechny tyto výpočty map jsou na sobě nezávislé, takže je lze provádět souběžně a distribuovat v počítačovém klastru.

Náhodná fáze

• Než může začít fáze Reduce, musí být výsledky fáze Map seskupeny do seznamů podle jejich nového klíče .${\ displaystyle l}$${\ displaystyle T_ {l}}$
• Pokud jsou funkce map a redukce prováděny souběžně a distribuovány, je k tomu nutná koordinovaná výměna dat.
• Výkon systému s redukcí mapy závisí do značné míry na tom, jak efektivně je implementována fáze náhodné reprodukce.
• Uživatel bude zpravidla ovlivňovat pouze fázi náhodné reprodukce prostřednictvím návrhu kláves . Stačí tedy ji jednou dobře optimalizovat a může z toho těžit řada aplikací.${\ displaystyle l}$

Snižte fázi

• Pokud již byla provedena všechna mapová volání nebo jsou k dispozici všechny mezivýsledky , knihovna zavolá funkci Zmenšit pro každý seznam mezilehlých hodnot , která to použije k výpočtu seznamu hodnot výsledků, které knihovna shromáždí jako páry ve výstupním seznamu .${\ displaystyle T_ {l}}$${\ displaystyle w_ {j}}$${\ displaystyle (l, w_ {j})}$
• Hovory ke snížení lze také distribuovat nezávisle na různé procesy v počítačovém clusteru.

Poznámka: Tato reprezentace byla poněkud zjednodušená, protože řízení postupu MapReduce bude obvykle zaměřeno na řadu redukčních procesů, takže pokud existují mezivýsledky pro více než různé klíče , mezilehlé výsledky s různými klíči jsou uloženy ve společném seznamu. Odpovídající páry jsou tříděny podle klíče před výpočtem Zmenšit. ${\ displaystyle R}$${\ displaystyle R}$${\ displaystyle l}$${\ displaystyle (l, x)}$${\ displaystyle (l, x)}$${\ displaystyle l}$

Zkombinujte fázi

Volitelně může před kombinací proběhnout fáze kombinování. To obvykle má stejnou funkčnost jako funkce redukce, ale je prováděno na stejném uzlu jako fáze mapy. Cílem je snížit množství dat, která musí být zpracována ve fázi náhodného přehrávání, a tím snížit zatížení sítě. Smysl fáze kombinování se projeví okamžitě při pohledu na příklad Wordcountu : Kvůli rozdílné četnosti slov v přirozeném jazyce by například německý text velmi často vytvořil výstup formuláře ("a", 1) (totéž platí pro články a pomocná slovesa). Fáze kombinování nyní změní 100 zpráv formuláře ("a", 1) na jednu zprávu formuláře ("a", 100). To může výrazně snížit zatížení sítě, ale není to možné ve všech případech použití.

Příklad: Analýza distribuované frekvence s MapReduce

problém

U rozsáhlých textů chcete zjistit, jak často se která slova objevují.

Specifikace funkcí mapy a zmenšení

 map(String name, String document):
  // name: document name ("key")
  // document: document contents ("value")
  for each word w in document:
    EmitIntermediate(w, 1);

 reduce(String word, Iterator partialCounts):
  // word: a word ("key")
  // partialCounts: a list of aggregated partial counts ("values")
  //     for 'word'
  int result = 0;
  for each v in partialCounts:
    result += v;
  Emit(word, result);

Fáze mapy

• Na mapě je uveden název dokumentu a dokumentový dokument jako řetězec znaků.
• Mapa prochází dokument od slova do slova.
• Pokaždé, když narazí na slovo w , přesune se 1 na w -časový seznam výsledků (pokud ještě neexistuje, je vytvořen).
• Pokud jste prošli všemi slovy a text obsahuje celkem n různých slov, fáze mapování končí n seznamy mezilehlých výsledků, z nichž každý shromažďuje jiné slovo, které obsahuje tolik 1 položek, kolik bylo odpovídající slovo nalezeno v dokument.
• Je možné, že mnoho instancí mapy běželo současně, pokud bylo knihovně předáno několik slov a dokumentů.

Náhodná fáze

• Seznamy mezilehlých výsledků několika procesů / systémů pro stejné slovo w jsou kombinovány a distribuovány do systémů pro reduktory.

Snižte fázi

• Reduce se volá pro slovo slovo a částečný počet seznamů průběžných výsledků .
• Funkce Reduce prochází seznamem průběžných výsledků a sečte všechna nalezená čísla.
• Celkový výsledek je vrácen do knihovny, obsahuje počet nalezených slov ve všech dokumentech.
• Průběžné výsledky lze vypočítat paralelně pomocí simultánních hovorů Omezit.

Celkem

• Seznam slov a četnosti slov je generován ze seznamu názvů dokumentů a dokumentů.

Příkladný výpočet

Například pro klasický text je myslitelný následující výpočet :

 Text = "Fest gemauert in der Erden
         Steht die Form, aus Lehm gebrannt.
         Heute muß die Glocke werden,
         Frisch, Gesellen! seid zur Hand.
         Von der Stirne heiß
         Rinnen muß der Schweiß,
         Soll das Werk den Meister loben,
         Doch der Segen kommt von oben."

Text je rozdělen do vět; normalizaci lze provést tak, že vše napíšete malými písmeny a odstraníte interpunkční znaménka:

 Eingabeliste = [ (satz_1, "fest gemauert in der erden steht die form aus lehm gebrannt"),
                  (satz_2, "heute muß die glocke werden frisch gesellen seid zur hand"),
                  (satz_3, "von der stirne heiß rinnen muß der schweiß soll das werk den meister loben doch der segen kommt von oben") ]

Vstupní seznam má tři páry jako prvky, takže můžeme spustit tři mapové procesy:

 P1 = Map(satz_1, "fest gemauert in der erden steht die form aus lehm gebrannt")
 P2 = Map(satz_2, "heute muß die glocke werden frisch gesellen seid zur hand")
 P3 = Map(satz_3, "von der stirne heiß rinnen muß der schweiß soll das werk den meister loben doch der segen kommt von oben")

Volání mapy generují tyto dvojice mezilehlých výsledků:

 P1 = [ ("fest", 1), ("gemauert", 1), ("in", 1), ("der", 1), ("erden", 1),
        ("steht", 1), ("die", 1), ("form", 1), ("aus", 1), ("lehm, 1),
        ("gebrannt", 1) ]
 P2 = [ ("heute", 1), ("muß", 1), ("die", 1), ("glocke", 1), ("werden", 1),
        ("frisch", 1), ("gesellen", 1), ("seid", 1), ("zur", 1), ("hand", 1) ]
 P3 = [ ("von", 1), ("der", 1), ("stirne", 1), ("heiß", 1), ("rinnen", 1),
        ("muß, 1), ("der", 1), ("schweiß", 1), ("soll", 1), ("das", 1),
        ("werk", 1), ("den", 1), ("meister", 1), ("loben", 1), ("doch", 1),
        ("der", 1), ("segen", 1), ("kommt", 1), ("von", 1), ("oben", 1) ]

Mapové procesy doručují své páry do knihovny MapReduce, která je shromažďuje v seznamech mezilehlých výsledků. Mohlo by se stát paralelně (stejné načasování 3 mapových procesů je nereálné, verze se skutečně překrývají. Seznamy T_word jsou k dispozici místně pro každý mapový proces a nejsou synchronizovány mezi kroky):

 1. Iteration:
    P1:  T_fest     = [ 1 ]     (neu)
    P2:  T_heute    = [ 1 ]     (neu)
    P3:  T_von      = [ 1 ]     (neu)

 2. Iteration:
    P1:  T_gemauert = [ 1 ]     (neu)
    P2:  T_muß      = [ 1 ]     (neu)
    P3:  T_der      = [ 1 ]     (neu)

 3. Iteration:
    P1:  T_in       = [ 1 ]     (neu)
    P2:  T_die      = [ 1 ]     (neu)
    P3:  T_stirne   = [ 1 ]     (neu)

Ve čtvrtém kroku můžete vidět, že průběžné seznamy výsledků existují místně pro každý proces mapy a nelze je globálně znovu použít:

 4. Iteration:
    P1:  T_der      = [ 1 ]     (neu, der 1. Map-Prozess hat noch kein T_der, nur P3)
    P2:  T_glocke   = [ 1 ]     (neu)
    P3:  T_heiss    = [ 1 ]     (neu)

 5. Iteration
    P1:  T_erden    = [ 1 ]     (neu)
    P2:  T_werden   = [ 1 ]     (neu)
    P3:  T_rinnen   = [ 1 ]     (neu)

 6. Iteration
    P1:  T_steht    = [ 1 ]     (neu)
    P2:  T_frisch   = [ 1 ]     (neu)
    P3:  T_muß      = [ 1 ]     (neu, der 3. Map-Prozess hat noch kein T_muß, nur P2)

V sedmém kroku se poprvé stane, že se další výskyt shromáždí v prozatímním seznamu výsledků, který již byl vytvořen:

 7. Schritt
    P1:  T_die      = [ 1 ]     (neu, der 1. Map-Prozess hat noch kein T_die)
    P2:  T_gesellen = [ 1 ]     (neu)
    P3:  T_der      = [ 1, 1 ]  (beim 3. Map-Prozess seit Iteration 2 vorhandene Liste verwenden)

atd.

Po 21 krocích jsou všechny tři procesy mapy dokončeny se svou prací, fáze mapy končí a začíná fáze redukce. Seznamy mezilehlých výsledků, které byly vytvořeny různými mapovými procesy pro stejné slovo, jsou sloučeny. Pro každý z výsledných seznamů průběžných výsledků (zde seřazené)

                     reduce
   T_der      = [ 1 ] ++ [ 1, 1, 1 ] -> [ 4 ]
   T_die      = [ 1 ] ++ [ 1 ]       -> [ 2 ]
   T_fest     = [ 1 ]                -> [ 1 ]
   T_gemauert = [ 1 ]                -> [ 1 ]
   T_glocke   = [ 1 ]                -> [ 1 ]
   T_heiss    = [ 1 ]                -> [ 1 ]
   T_heute    = [ 1 ]                -> [ 1 ]
   T_in       = [ 1 ]                -> [ 1 ]
   T_muß      = [ 1 ] ++ [ 1 ]       -> [ 2 ]
   T_stirne   = [ 1 ]                -> [ 1 ]
   T_von      = [ 1, 1 ]             -> [ 2 ]
   .
   .
   . (für alle verschiedenen T-Listen)

můžeme spustit proces redukce paralelně, který vyjmenuje prvky. Výsledek MapReduce vypadá asi takto:

 Ausgabeliste = [ ("fest", 1), ("heute", 1), ("von", 2), ("gemauert", 1),
                  ("muß", 2), ("der", 4), ("in", 1), ("die", 2), .. ]

Další příklady

zobecnění

Poté, co byl proces v roce 2014 starý deset let, společnost Google nedávno začala nabízet rozšíření Cloud Dataflow , které nabízí větší flexibilitu a má ještě více podpořit cloud computing.

Viz také

• Apache Hadoop - rámec Java založený na algoritmu MapReduce

webové odkazy

Technický článek

• Jeffrey Dean , Sanjay Ghemawat : MapReduce: Simplified Data Processing on Large Clusters , OSDI'04: Sixth Symposium on Operating System Design and Implementation (prosinec 2004), online
• Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, Christos Kozyrakis: Hodnocení zmenšení mapy pro vícejádrové a víceprocesorové systémy . (PDF; 353 kB) Stanfordská univerzita
• Proč MapReduce záleží na datovém skladu SQL . Analýza zavedení MapReduce / SQL společností Aster Data Systems a Greenplum
• Marc de Kruijf, Karthikeyan Sankaralingam: Zmenšení mapy pro architekturu Cell BE . (PDF; 528 kB) University of Wisconsin - Madison
• Hung-Chih Yang, Ali Dasdan, Ruey-Lung Hsiao, D. Stott Parker: Map-Reduce-Merge: Zjednodušené relační zpracování dat na velkých klastrech . In: Proc. of ACM SIGMOD , 2007, pp. 1029-1040 (This paper shows how to extend MapReduce to relational computing)
• Flux: The odolný proti chybám , vyrovnávání zátěže operátora eXchange od UC Berkeley nabízí alternativu k Google MapReduce se selhání , ale dodatečné náklady implementace.

software

• Apache Hadoop MapReduce
• diskotékový open source projekt (Python a Erlang) od Nokia Research Center
• DryadLINQ - MapReduce implementace pomocí Microsoft Research . Na základě PLINQ a Dryad .
• MATLAB MapReduce je implementace MathWorks v Matlabu s podporou Hadoop .
• Plasma MapReduce je open source implementace MapReduce v Ocaml s vlastním distribuovaným souborovým systémem
• QtConcurrent Open Source C ++ MapReduce implementace (nedistribuované) vývojových rámců Qt pro rozvoj společnosti Digia
• Skynet Ruby Map / Zmenšit knihovnu

PlasmaFS. Plasma MapReduce vyvinul Gerd Stolpmann (Darmstadt).

• Nástroj pro správu a analýzu dat Splunk.com pro velká data založený na MapReduce
• Programovací model Stratosphere PACT: Rozšíření a zobecnění programovacího modelu MapReduce

Individuální důkazy

1. ↑ Google reflektory vnitřní fungování datového centra . CNET News, blog o technických novinkách
2. ^ Jeffrey Dean, Sanjay Ghemawat: MapReduce: Zjednodušené zpracování dat na velkých klastrech . Laboratoře Google : „Naše abstrakce je inspirována mapou a omezuje primitiva přítomná v Lispu a mnoha dalších funkčních jazycích.“
3. ^ Ralf Lämmel ( Microsoft ): Programovací model MapReduce společnosti Google - revidováno . (PDF)
4. ↑ USP 7 650 331. Úřad pro patenty a ochranné známky Spojených států
5. ↑ MapReduce Paper