MapReduce

M ap R educe syntyy hajautetun laskennan 80 - luvulta lähtien tunnetuista periaatteista .

M ap R educe on ohjelmointimalli , joka tukee rinnakkaislaskentaa suurissa tietokokoelmissa tietokoneryhmissä ja hyödykelaskentaa . _ Viitekehyksen nimi on saanut inspiraationsa kahden tärkeän menetelmän , makron tai funktion funktionaalisessa ohjelmoinnin nimistä: Map ja Reduce . Map Reduce on otettu käyttöön maailmanlaajuisesti, koska siellä on avoimen lähdekoodin toteutus nimeltä Hadoop. Sen kehitystä johti alun perin Yahoo , ja tällä hetkellä sitä toteuttaa Apache-projekti . 2010-luvulta lähtien on ollut useita Hadoopin kaltaisia ​​aloitteita sekä teollisuudessa että korkeakouluissa. Map Reduce -kirjastojen toteutukset on kirjoitettu useilla ohjelmointikielillä , kuten C ++ , Java ja Python .

M ap R educea käytetään joidenkin algoritmien käytännön ratkaisussa, jotka voidaan rinnastaa. Map Reduce ei kuitenkaan ole ratkaisu kaikkiin ongelmiin, samoin kuin kaikkia ongelmia ei voida ratkaista tehokkaasti Map Reducen avulla . Ongelmiin, jotka liittyvät suuriin tietojoukkoihin, joiden koko on petabyyttiä , käsitellään yleensä. Tästä syystä tämä kehys toimii yleensä hajautetussa tiedostojärjestelmässä (HDFS).

Historia

Varhaiset Google-toteutukset tarvitsivat suurten matriisikertotoimintojen suorittamista PageRank : n eli sivujen sijoituksen laskemiseksi haussa . Tällä tavalla Map Reduce tuli suosituksi lineaarialgebran laskentamenetelmänä . Huoli suurten tietokokoelmien käsittelystä johti algoritmien ja kehysten luomiseen, jotka pystyvät käsittelemään teratavuja tietoa. Yksi ensimmäisistä sovelluksista, jotka pystyivät ohjelmoimaan Map Reducen , otettiin alun perin käyttöön Hadoopissa , jonka alun perin suunnitteli Doug Cutting , joka nimesi sen poikansa lelunorsun mukaan. Se kehitettiin alun perin tukemaan Nutch - hakukoneprojektin jakelua . ]

Yleiskatsaus

Map R educe on kehys ongelmien käsittelyyn rinnakkain suurten tietojoukkojen välillä käyttämällä suurta määrää tietokoneita (solmuja), joita kutsutaan yhteisesti klusteriksi (jos kaikki solmut ovat samassa paikallisverkossa ja käyttävät samanlaista laitteistoa) tai verkkoa. (jos solmut jaetaan maantieteellisesti ja hallinnollisesti hajautettujen järjestelmien kesken ja ne käyttävät heterogeenisempaa laitteistoa). Käsittely voidaan tehdä tiedostojärjestelmään (strukturoimaton) tai tietokantaan (strukturoitu) tallennetuille tiedoille. M ap R educe voi hyödyntää tietojen sijaintia ja käsitellä niitä lähellä tallennuspaikkaa minimoidakseen tiedonsiirron.

Map Reduce -kehys ( tai järjestelmä) koostuu tyypillisesti kolmesta operaatiosta (tai vaiheesta):

1. Kartta: Jokainen orjasolmu (työntekijä) käyttää toimintoa mappaikallisiin tietoihin ja kirjoittaa lähdön väliaikaiseen tallennustilaan. Pääsolmu varmistaa, että vain yksi kopio redundantista syöttötiedosta käsitellään.
2. Sekoitus: Työntekijät jakavat tiedot uudelleen tulosavainten perusteella (funktion tuottamat map), niin että kaikki avaimeen kuuluvat tiedot ovat samassa työntekijäsolmussa.
3. Vähennä: Työntekijäsolmut käsittelevät nyt jokaista lähtötietoryhmää avaimella rinnakkain.

M ap R educe mahdollistaa karttojen hajautetun käsittelyn ja toimintojen vähentämisen. Kartat voidaan tehdä rinnakkain, kunhan jokainen kartoitustoiminto on riippumaton muista; Käytännössä tätä rajoittaa riippumattomien tietolähteiden määrä ja/tai kunkin lähteen lähellä olevien prosessorien määrä. Samoin joukko "vähentäjiä" voi suorittaa pienennysvaiheen, kunhan kaikki karttatoiminnon lähdöt, jotka jakavat saman avaimen, esitetään samalle supistimelle samanaikaisesti tai vähennystoiminto on assosiatiivinen . Vaikka tämä prosessi näyttää usein tehottomalta verrattuna algoritmeihin, jotka ovat peräkkäisempiä (koska vähennysprosessia on suoritettava useita esiintymiä), Map Reduce -toimintoa voidaan soveltaa huomattavasti suurempiin tietokokonaisuuksiin kuin yksi "perus"palvelin pystyy käsittelemään. Suuri palvelinfarmi voi Map Reducen avulla lajitella petatavun dataa vain muutamassa tunnissa. Rinnakkaisuus tarjoaa myös mahdollisuuden toipua palvelimen tai tallennustilan osittaisesta toimintahäiriöstä käytön aikana: jos kartoitus tai supistin epäonnistuu, työ voidaan ajoittaa uudelleen olettaen, että syöttötietoja on edelleen saatavilla.

Looginen näkymä

Kaikkia prosesseja ei voida käsitellä M ap R educe - viitekehyksestä . Tarkemmin sanottuna vain ne, jotka voidaan jakaa map() - ja vähentää() -operaatioihin, ovat osoitettavissa, ja tämä on tärkeää valittaessa tämä kehys ongelman ratkaisemiseksi. Map- ja Reduce-funktiot on molemmat määritelty suhteessa tietoihin, jotka on strukturoitu tyyppisiksi monikoiksi (avain, arvo) .

Map()-funktio

Map ottaa yhden näistä tietopareista tyypin kanssa yhdessä tietoverkkotunnuksessa ja palauttaa luettelon eri verkkotunnuksen pareista:

Kartta(k 1 ,v 1 ) -> lista(k 2 ,v 2 )

• Map() - funktio : käsittelee kartoituksen ja sitä käytetään rinnakkain jokaiselle tietosyötteen kohteelle . Tämä tuottaa luettelon (k2,v2) pareista jokaiselle puhelulle. Tämän jälkeen Map Reduce -kehys kokoaa kaikki samalla avaimella olevat parit kaikista luetteloista ja ryhmittelee ne luoden ryhmän kullekin eri luodulle avaimelle. Arkkitehtonisesta näkökulmasta pääsolmu ottaa syötteen, jakaa sen pieniksi paloiksi tai vähemmän identiteettisiksi ongelmiksi ja jakaa ne ns. työntekijäsolmuille . Työntekijäsolmu voi jakaa uudelleen, jolloin syntyy puurakenne . Työntekijäsolmu käsittelee ongelman ja välittää vastauksen pääsolmulle .

Reduce()-funktio

Vähennystoimintoa käytetään rinnakkain jokaisessa ryhmässä, jolloin saadaan kokoelma arvoja kullekin toimialueelle:

Pienennä(k 2 , lista (v 2 )) -> lista(v 3 )

• Reduce () - funktio : Jokainen Reduce-kutsu tuottaa tyypillisesti v3-arvon tai tyhjän kutsun, vaikka kutsu voi palauttaa useamman kuin yhden arvon. Kaikkien näiden puheluiden palautukset kerätään haluttuun tulosluetteloon.

Siksi MapReduce-kehys muuttaa luettelon (avain, arvo) pareista arvojen luetteloksi. Tämä käyttäytyminen eroaa toiminnallisen ohjelmoinnin "kartta ja vähennä" -liitos , joka hyväksyy mielivaltaisen arvoluettelon ja palauttaa yhden arvon, joka yhdistää kaikki kartan palauttamat arvot.

MapReduce-arkkitehtuuri

Map() - funktio suoritetaan hajautetusti useille koneille. Syöttötiedot, jotka tulevat yleensä suuresta tiedostosta (tiedostosta), jaetaan M syöttöosioiden joukkoon, jotka ovat yleensä 16-64 megatavua. Näitä osioita voidaan käsitellä erilaisilla koneilla. MapReduce - kutsussa tapahtuu yleensä useita toimintoja :

• Merkinnät jaetaan sitten M osioon, joiden koko on noin 16-64 megatavua . MapReduce-ohjelma alkaa ilmentyä klusterin eri koneilla. Pääsääntöisesti esiintymien lukumäärä määritetään sovelluksissa.

• Yksi ohjelman kopioista on erityinen ja ottaa "mestarin" roolin. Loput kopiot kutsutaan "työntekijöiksi" ja saavat tehtävänsä isännältä. Oletetaan, että on olemassa useita M map() - tehtäviä ja R Reduction(). "Mestari" on vastuussa "työntekijöiden" keräämisestä levossa (eli ilman määrättyä tehtävää) ja määrittää sille tietyn map()- tai redusointitehtävän. Työntekijällä voi olla vain kolme tilaa: tyhjäkäynti, toimiva, valmis.

• Työntekijä, jolle on määritetty tietty map() - tehtävä , ottaa syötteenä vastaavan osion. Se jäsentää parit (avain, arvo) luodakseen uuden lähtöparin ohjelmoinnin mukaisesti. Map()-funktion tuottamat avainarvo-parit puskuroidaan muistiin.

• Ajoittain puskuroidut avain-arvo-parit kirjoitetaan paikalliselle levylle hajautettuna R-alueelle. Näiden avainarvoparien alueet välitetään masterille, joka on vastuussa työntekijöiden uudelleenohjaamisesta, joilla on vähennystehtäviä.

• Kun "isäntä" ilmoittaa osion sijainnin tyyppiselle työntekijälle, se lukee etäkutsujen avulla eri map(-tyypin) työntekijöiden kiintolevyille tallennetut tiedot. Kun reduction()-tyypin työntekijä lukee kaikki välitiedot, se järjestää avaimet siten, että samalla avaimella löydetyt tiedot ryhmitellään yhteen. Järjestys on välttämätön , koska yleensä useat erilaiset map()-funktionäppäimet voivat mennä samaan vähennysfunktioon. Tapauksissa, joissa välitiedon määrä on erittäin suuri, käytetään usein ulkoista lajittelua.

• Reduction()-tyypin työntekijä iteroi välilajiteltujen arvojen joukon yli, ja se tekee niin jokaisen löydetyn yksilöllisen avaimen kohdalla. Se ottaa avaimen ja siihen liittyvän arvojoukon ja välittää ne vähennysfunktiolle (). Reduce():n tulos lisätään MapReduce-tulostetiedostoon.

• Kun kaikki map()- ja vähentää()-tehtävät on suoritettu, "master" tuo käyttäjäohjelman esiin. Tässä vaiheessa MapReduce-kutsu palauttaa ohjauksen käyttäjän koodiin.

Tehtävät katsotaan päättyneiksi, kun tämä ohjaus on palautettu käyttäjälle. Tulosteet jaetaan täydellisenä tiedostona, tai jos se ei ole mahdollista, ne jaetaan R-tiedostoina. Nämä R-tiedostot voivat olla toisen MapReducen syöte tai ne voidaan käsitellä millä tahansa muulla ohjelmalla, joka tarvitsee näitä tietoja.

Combiner (paikalliset kokoajat)

Klusteriympäristössä yksi rajoituksista löytyy suurten tiedostojen siirtämisestä tietokoneiden välillä niiden rajoitetun kaistanleveyden vuoksi . MapReduce-kehyksessä map()-funktio kirjoittaa paikalliseen merkkipuskuriin, kuten kiintolevylle . Paikallisesti kirjoitetut tiedot kokoaa ja tilaa tämän toiminnon suorittamisesta vastaava aggregaattoritoiminto. Järjestetyt arvot ovat muotoa [k, [v ₁ , v ₂ , v ₃ , ..., v _n ]]. Tällä tavalla vähennysfunktio () vastaanottaa yhdistelmästä luettelon arvoista, jotka liittyvät yhteen avaimeen. Koska tietokoneiden ja niiden levyjen verkon latenssi on yleensä suurempi kuin minkään muun toiminnon, mikä tahansa välitiedon määrän vähentäminen lisää algoritmien tehokkuutta. MapReducessa mikä tahansa välitulosten paikallinen aggregointi parantaa todellista globaalia tehokkuutta.

Tästä syystä monet viralliset MapReduce-jakelut sisältävät usein paikallisia aggregointitoimintoja käyttämällä toimintoja, jotka pystyvät kokoamaan tietoja paikallisesti. Suurien tiedostojen liikkumisen välttäminen tai vähentäminen mahdollisimman pitkälle. Joko lisätty map()-funktioihin tai paikallisiin kokoajiin.

Vikasietokyky

MapReduce-mekanismi on vikasietoinen , kun yksi työntekijöistä joutuu vikaan. Kuten MapReduce, se on suunniteltu suuria tietokokoja sisältäviin prosesseihin, joissa käytetään satoja tai tuhansia tietokoneita. Vaikka epäonnistumisen todennäköisyys on pieni, on hyvin mahdollista, että yksi (tai useampi) työntekijöistä deaktivoituu juuri sitä tukeneen koneen vian vuoksi. "Isäntä" lähettää säännöllisesti ping -kutsuja jokaiselle työntekijälle tarkistaakseen sen tilan.

Jos vastausta ei tule tietyn odotusajan jälkeen, isäntä tulkitsee työntekijän deaktivoituneen. Kaikki työntekijän suorittamat map()-tehtävät palaavat välittömästi odotustilaan, ja ne voivat siten olla kelvollisia osoitettavaksi muille työntekijöille. Samoin mikä tahansa vian aikana käynnissä oleva map()- (tai redusointi) -toiminto palautetaan tyhjäkäynnille ja se voidaan valita uudelleenallokoitavaksi.

Valmiit map()-tehtävät suoritetaan uudelleen epäonnistuessa osittain, koska niiden tulos on tallennettu epäonnistuneen koneen paikallisille levyille ja siksi sitä ei pidetä käytettävissä. Koko vähennys () -tehtäviä ei tarvitse suorittaa uudelleen, koska niiden tulos on tallennettu järjestelmän globaaliin. Kun työntekijä A ja sitten työntekijä B suorittavat map()-tehtävän (lähinnä kaatumisen vuoksi), tässä tapauksessa kaikille redusointitehtäville ilmoitetaan poistamaan tiedot työntekijältä A ja hyväksymään tiedot työntekijältä A. työntekijältä B. Näin MapReducen suoritus on joustavaa .

Esimerkkejä

Map Reducen käyttöesimerkkien kuvauksessa tarvitsee vain kuvata yksityiskohtaisesti, kuinka map() - ja vähennys() -operaatiot kussakin tapauksessa toteutetaan. Kirjallisuudessa esitetään toistuvia esimerkkejä sanamäärästä asiakirjassa, matriisioperaatioista ja relaatiotietokantakyselyoperaatioista.

Sanamäärä

Tämä Map Reduce -esimerkki on prosessi, joka laskee jokaisen sanan esiintymät asiakirjajoukossa :

 kartta ( merkkijonon nimi , merkkijonodokumentti ) : _   
  // avain: asiakirjan nimi 
// arvo: asiakirjan sisältö jokaiselle sanalle w asiakirjassa :  
       
    EmitIntermediate ( w , 1 ); 

Tässä tapauksessa map()-funktio jakaa asiakirjan sanoiksi (eli tokenisoi sen ) käyttämällä yksinkertaista leksikaalista analysaattoria ja tulostaa sarjan muotoisia lukuja ( avain , arvo ), jossa avain on sana ja arvo on "1". Toisin sanoen esimerkiksi asiakirjasta "Pikku talo preerialla" karttatoiminto palauttaisi: ("la", "1"), ("talo", "1"), ("of", "1" ), ("the", "1"), ("niitty", "1").

 
 vähentää ( merkkijono sana , iteraattori partialCounts ) :   
  // sana: sana 
// partialCounts: [[Iteraattori (suunnittelumalli)|osittainen luettelo]] aggregaattilaskennan suorittamiseen int tulos = 0 ;  
     
  jokaiselle v : lle partialCountsissa :    
    tulos += ParseInt ( v );  
  Emit ( tulos );

Tässä jokainen asiakirja on jaettu sanoiksi ja Kartta-toiminto laskee jokaisen sanan alkuarvolla "1" käyttämällä sanaa avaintuloksena. Kehys kokoaa kaikki parit samalla avaimella ja syöttää samaan Reduce-kutsuun, joten tämä toiminto tarvitsee vain kaikkien syötearvojensa summan löytääkseen sanan kokonaisesiintymät. Yllä olevassa esimerkissä ("la", "1") esiintyy kahdesti, koska näppäimellä "la" on kaksi esiintymää, loput näppäimet näkyvät vain kerran.

Matriisin kertominen vektorilla

Lineaarialgebran esimerkit matriisioperaatioille ovat sopivimpia kehyksen soveltuvuuden vuoksi näissä tapauksissa. Oletetaan, että meillä on neliömatriisi M, jonka koko on nxn. Kutsumme rivillä i ja sarakkeella j olevaa elementtiä m _ij . Oletetaan, että meillä on sellainen vektori v , että kohdassa j meillä on elementti v _j . Tällä tavalla matriisin M ja vektorin v välisen kertolaskutuloksena tulee vektori x , jonka pituus on n siten, että elementti x _i on sellainen, että:

$x_{i} = \sum_{j=1}^n m_{ij} v_j$

Tämä operaatio suoritetaan ilman ongelmia useiden tuhansien elementtien ryhmille, mikä maksaa useita miljoonia. Sen laskentaongelma tulee silloin, kun se on tarkoitus tehdä sadoilla miljardeilla . Tästä syystä oletetaan M:n sovelluksessa R educe , että n on suuruusluokkaa 10 ¹² . Tässä tapauksessa map() -funktio ottaa matriisin rivin i ja koko vektorin v muodostaakseen pareja: (i, m _ij v _j ). Eli muotoa (1, m ₁₁ v ₁ ), (1, m ₁₂ v ₂ ), (1, m ₁₃ v ₃ ) ... (1, m _1j v _j ).

 kartta ( Vector rowMatrix , Vector vector ) :   
  // avain: i -> vektoriindeksi 
// arvo: m<sub>ij</sub>:n tulo v<sub>j</sub>:lla. jokaiselle paikalle i vektorissa : _ _  
       
    EmitIntermediate ( i , arvo ); 

Reduktorin()-funktion täytyy tässä tapauksessa vain kerätä parit, joilla on sama avain i, ja lisätä ne.

 
 vähentää ( merkkijono sana , iteraattori partialCounts ) :   
  // sana: sana 
// partialCounts: [[Iteraattori (suunnittelumalli)|osittainen luettelo]] aggregaattilaskennan suorittamiseen int tulos = 0 ;  
     
  jokaiselle v : lle partialCountsissa :    
    tulos += ParseInt ( v );  
  Emit ( tulos );

Tiedonkulku

MapReduce-kehys on suuri hajautettu lajittelualgoritmi. Sovelluksen määrittelemät päämoduulit ovat:

• sisääntulolukija _
• Karttatoiminto _
• osiotoiminto _
• Vertailutoiminto _
• A Pienennä -toiminto
• Lähtevä kirjoittaja

Syöttölukija

Syöttölukija jakaa syötteen sopivan kokoisiksi "osiksi" (tyypillisesti 64 Mt - 128 Mt) ja kehys määrittää kullekin karttatoiminnolle osion . Syöttölukija lukee tiedot vakaasta tallennustilasta (yleensä hajautetusta tiedostojärjestelmästä ) ja luo avain/arvo-pareja.

Yleinen esimerkki lukee hakemiston, joka on täynnä tekstitiedostoja ja palauttaa jokaisen rivin tietueeksi.

Karttatoiminto

Kartoitustoiminto ottaa joukon avain/arvo-pareja, käsittelee ne ja luo nollan tai useamman tulosavain/arvo-parin . Syöttö- ja tulostuskarttojen tyypit voivat olla (ja usein ovatkin) erilaisia.

Jos sovellus laskee sanoja, Map-toiminto jakaa rivit sanoiksi ja luo jokaiselle sanalle lähtöavain/arvo-parin. Jokainen tulospari sisältää sanan avaimena ja sen esiintymien lukumäärän rivillä arvona.

Osiotoiminto

Jokainen Kartta -toiminnon lähtö on kohdistettu supistimelle , joka käyttää osiointitoimintoa paloittelun luomiseen. Osiofunktio vastaanottaa avaimen ja vähennysyksiköiden lukumäärän ja palauttaa halutun supistimen indeksin.

Oletuskäyttäytyminen on saada avaimen tiiviste ja käyttää hajautusarvoa modulo vähennysten lukumäärä . Tasapainon ylläpitämiseksi on tärkeää valita osiotoiminto, joka tuottaa suunnilleen tasaisen datajakauman sirpaleelta, muuten MapReduce-toiminto voi hidastua odottamalla hitaita supistuksia (vähennykset, jotka on määritetty suuremmalle osalle dataa kuin sirpaleessa on).

Kartoitus- ja vähennysvaiheiden välillä data sekoitetaan (rinnakkaislajiteltu / vaihdetaan solmujen välillä), jotta tiedot siirretään sirpaleesta, jossa se tuotettiin, sirpaleeseen, jossa se pienennetään. Sekoitus voi joissain tapauksissa kestää kauemmin kuin käsittely riippuen kaistanleveydestä, suorittimen nopeuksista, tuotetusta tiedosta ja kartoituksen ja käsittelyn vähentämisen välillä kuluvasta ajasta.

Vertailutoiminto

Kullekin vähennykselle syöte saadaan koneelta, jossa kartta suoritettiin ja tilattiin vertailutoiminnolla

Pienennystoiminto

Kehys kutsuu sovelluksen Shrink -funktiota kerran kullekin lajitellun luettelon yksilölliselle avaimelle. Reduce voi toistaa kyseiseen avaimeen liittyvien arvojen läpi ja tuottaa nollan tai useamman tulosteen .

Sanamäärä-esimerkissä Reduce -funktio ottaa syötearvot, laskee ne yhteen ja luo yhden tulosteen sanalle ja loppusummalle.

Poistu kirjoittajasta

Output Writer kirjoittaa Shrink - funktion lähdön tallennustaulukoihin, yleensä hajautettuun tiedostojärjestelmään.

Käyttää

Yleissääntönä on, että Map Reducea käytetään sellaisissa samanaikaisissa laskenta-ongelmissa , joissa on suuria tietojoukkoja , joita on käsiteltävä suurella määrällä tietokoneita (solmuja), joita kutsutaan yhteisesti klustereiksi (jos kaikki solmut ovat samassa lähiverkossa ja käyttämällä samaa laitteistoa) tai grideihin (jos solmut jaetaan hajautetusti laajoille maantieteellisille tai hallinnollisille alueille ja joissa on yleensä heterogeenisempi laitteisto). Rinnakkaiskäsittely voi tapahtua käyttämällä tietoja, jotka on tallennettu joko tiedostojärjestelmään (strukturoimaton) tai tietokantaan (strukturoitu). Tästä syystä sitä käytetään sovelluksissa, joissa on laajamittaista dataa, kuten rinnakkaisissa sovelluksissa, verkkoindeksoinnissa, tiedon louhinnassa ja tieteellisessä simuloinnissa.

Katso myös

MapReducen toteutukset

• Apache Hadoop
• CouchBase
• sohva
• Infinispan
• MongoDB
• Riak