KortReducer

M ap R educe er født ud fra de principper, der er kendt siden firserne for distribueret databehandling .

M ap R educe er en programmeringsmodel til at understøtte parallel computing på store samlinger af data i grupper af computere og commodity computing . Navnet på rammeværket er inspireret af navnene på to vigtige metoder , makroer eller funktioner i funktionel programmering: Kort og Reducer . Map Reduce er blevet vedtaget over hele verden, da der er en OpenSource implementering kaldet Hadoop. Dets udvikling blev oprindeligt ledet af Yahoo og udføres i øjeblikket af Apache-projektet . Siden 2010'erne har der været flere initiativer, der ligner Hadoop, i både industrien og den akademiske verden. Implementeringer af Map Reduce - biblioteker er blevet skrevet i forskellige programmeringssprog såsom C ++ , Java og Python .

M ap R educe bruges i den praktiske opløsning af nogle algoritmer, der kan paralleliseres. Men Map Reduce er ikke løsningen på ethvert problem, på samme måde som ethvert problem ikke kan løses effektivt af Map Reduce . Problemer med store datasæt, der når petabytes i størrelse, behandles generelt. Det er af denne grund, at denne ramme normalt kører på et distribueret filsystem (HDFS).

Historie

Tidlige Google-implementeringer var nødvendige for at udføre store matrixmultiplikationsoperationer for at beregne PageRank , det vil sige rangeringen af ​​sider i en søgning. På denne måde blev Map Reduce populær som en beregningsmetode til lineær algebra . Bekymringen for at håndtere store samlinger af data førte til skabelsen af ​​algoritmer og rammer, der er i stand til at behandle terabyte af information. En af de første applikationer, der var i stand til at programmere Map Reduce , blev oprindeligt implementeret i Hadoop , oprindeligt designet af Doug Cutting , som opkaldte den efter sin søns legetøjselefant. Det blev oprindeligt udviklet til at støtte distributionen af ​​Nutch -søgemaskineprojektet . ]

Oversigt

M ap R educe er en ramme til at behandle problemer parallelt på tværs af store datasæt ved hjælp af et stort antal computere (knudepunkter), samlet omtalt som en klynge (hvis alle noder er på det samme lokale netværk og bruger lignende hardware) eller et netværk (hvis noder deles på tværs af geografisk og administrativt distribuerede systemer og bruger mere heterogen hardware). Behandling kan ske på data gemt i et filsystem (ustruktureret) eller i en database (struktureret). M ap R educe kan drage fordel af lokaliteten af ​​dataene og behandle dem tæt på, hvor de er gemt for at minimere kommunikationsomkostninger.

En Map Reduce - ramme (eller et system) er typisk sammensat af tre operationer (eller trin):

1. Kort: Hver slavenode (arbejder) anvender funktionen maptil lokale data og skriver outputtet til midlertidigt lager. En masterknude sikrer, at kun én kopi af de redundante inputdata behandles.
2. Bland: Arbejdere omdistribuerer data baseret på outputnøgler (produceret af funktionen map), så alle data, der hører til en nøgle, er i den samme arbejderknude.
3. Reducer: Arbejdernoderne behandler nu hver gruppe af outputdata, efter nøgle, parallelt.

M ap R educe muliggør distribueret behandling af kort og reducerer operationer. Kort kan udføres parallelt, så længe hver kortlægningsoperation er uafhængig af de andre; i praksis er dette begrænset af antallet af uafhængige datakilder og/eller antallet af CPU'er tæt på hver kilde. På samme måde kan et sæt "reducere" udføre reduktionsfasen, så længe alle udgange fra kortoperationen, der deler den samme nøgle, præsenteres for den samme reducer på samme tid, eller reduktionsfunktionen er associativ . Selvom denne proces ofte virker ineffektiv sammenlignet med algoritmer, der er mere sekventielle (fordi flere forekomster af reduktionsprocessen skal udføres), kan Map Reduce anvendes på væsentligt større datasæt, end en enkelt "grundlæggende" server kan håndtere. ". En stor serverfarm kan bruge Map Reduce til at sortere en petabyte af data på blot et par timer. Parallelisme giver også mulighed for at genoprette efter en delvis fejl på servere eller lager under drift: Hvis en mapper eller reducer fejler, kan jobbet omlægges, forudsat at inputdata stadig er tilgængelige.

Logisk visning

Ikke alle processer kan behandles fra M ap R educe- rammen . Specifikt er det kun dem, der kan opdeles i map()- og reduce()- operationerne, der kan adresseres, og det er vigtigt, når man vælger denne ramme for at løse et problem. Kort- og Reducer-funktionerne er begge defineret med hensyn til data struktureret i tuples af typen (nøgle, værdi).

Map() funktion

Map tager et af disse datapar med en type i ét datadomæne og returnerer en liste over par i et andet domæne:

Kort(k 1 ,v 1 ) -> liste(k 2 ,v 2 )

• Map() - funktionen : håndterer tilknytningen og anvendes parallelt for hvert element i datainputtet . Dette giver en liste over (k2,v2) par for hvert opkald. Derefter samler Map Reduce-rammen alle parrene med den samme nøgle fra alle listerne og grupperer dem, og opretter en gruppe for hver af de forskellige genererede nøgler. Fra et arkitektonisk synspunkt tager masternoden inputtet, deler det op i små stykker eller problemer med mindre identitet og distribuerer dem til de såkaldte worker noder . En arbejderknude kan underopdeles igen, hvilket giver anledning til en træstruktur . Arbejdernoden behandler problemet og sender svaret til masterknuden .

Reduce() funktion

Reduceringsfunktionen anvendes parallelt for hver gruppe og producerer en samling værdier for hvert domæne:

Reducer(k 2 , list (v 2 )) -> list(v 3 )

• Funktionen reduce() : Hvert kald til Reducer producerer typisk en v3-værdi eller et tomt kald, selvom et kald kan returnere mere end én værdi. Returneringen af ​​alle disse opkald indsamles som den ønskede resultatliste.

Derfor transformerer MapReduce-rammen en liste af (nøgle, værdi) par til en liste med værdier. Denne adfærd er forskellig fra funktionel programmerings "map and reduce" join , som accepterer en vilkårlig liste over værdier og returnerer en enkelt værdi, der kombinerer alle værdier returneret af kortet.

KortReducer arkitektur

Map()- funktionen udføres på en distribueret måde på tværs af flere maskiner. Inputdataene, som normalt kommer fra en stor fil (fil), er opdelt i et sæt af M inputpartitioner på generelt 16 til 64 megabyte. Disse partitioner kan behandles på forskellige maskiner. Adskillige handlinger forekommer normalt i en MapReduce- påkaldelse :

• Indtastningerne er derefter opdelt i M partitioner med en omtrentlig størrelse fra 16 til 64 megabyte . MapReduce-programmet begynder at instansiere sig selv på de forskellige maskiner i klyngen. Som regel er antallet af forekomster konfigureret i applikationerne.

• En af kopierne af programmet er speciel og tager rollen som "mester". Resten af ​​kopierne kaldes "arbejdere" og modtager tildelingen af ​​deres opgaver fra mesteren. Det vurderes, at der er et antal M map() opgaver og R reduce(). "Mesteren" er ansvarlig for at samle "arbejdere" i hvile (dvs. uden nogen tildelt opgave) og vil tildele en specifik map() eller reduce() opgave til den. En arbejder kan kun have tre tilstande: inaktiv, arbejder, komplet.

• En arbejder, der er tildelt en specifik map()- opgave , vil tage den tilsvarende partition som input. Den vil parse parrene (nøgle, værdi) for at skabe et nyt outputpar, som specificeret i dets programmering. Nøgle-værdi-parrene produceret af map()-funktionen er bufret i hukommelsen.

• Periodisk bliver buffernøgle -værdi-par skrevet til den lokale disk, spredt over R-områder. Regionerne i disse nøgleværdi-par videregives til master, som er ansvarlig for at omdirigere arbejdere, der har reduce()-opgaver.

• Når en arbejder af typen reducere får besked af "masteren" med placeringen af ​​en partition, bruger den fjernopkald til at læse informationen, der er gemt på harddiskene hos de forskellige arbejdere af typen map(). Når en arbejder af typen reduce() læser alle de mellemliggende data, bestiller den nøglerne på en sådan måde, at de fundne data med den samme nøgle er grupperet sammen. Rækkefølgen er nødvendig, fordi mange forskellige map() funktionstaster som hovedregel kan gå ind i den samme reduce() funktion . I tilfælde, hvor mængden af ​​mellemdata er meget stor, anvendes ofte en ekstern sortering.

• Arbejderen af ​​typen reduce() itererer over sættet af mellemsorterede værdier, og det gør det for hver unik nøgle fundet. Den tager nøglen og det værdisæt, der er knyttet til det, og sender dem til reduce()-funktionen. Outputtet af reduce() føjes til MapReduce-outputfilen.

• Når alle map() og reduce() opgaver er udført, bringer "masteren" brugerprogrammet frem. På dette tidspunkt returnerer MapReduce-opkaldet kontrol til en brugers kode.

Opgaver anses for afsluttet, når denne kontrol er returneret til brugeren. Outputtene distribueres i en komplet fil, eller hvis de ikke er distribueret i R-filer. Disse R-filer kan være input fra en anden MapReduce eller kan behandles af ethvert andet program, der har brug for disse data.

Combiner (Local Aggregators)

I et klyngemiljø findes en af ​​begrænsningerne i transporten af ​​store filer mellem computere på grund af deres begrænsede båndbredde . I MapReduce-rammeværket skriver map()-funktionen til en lokal tegnbuffer, såsom en harddisk . De oplysninger, der er skrevet lokalt, samles og bestilles af en aggregatorfunktion, der er ansvarlig for at udføre denne operation. De ordnede værdier er af formen [k, [v ₁ , v ₂ , v ₃ , ..., v _n ]]. På denne måde modtager reduce()-funktionen en liste over værdier forbundet med en enkelt nøgle fra kombinatoren. Da latensen af ​​netværket af computere og deres diske normalt er større end nogen anden operation, vil enhver reduktion i mængden af ​​mellemliggende data øge effektiviteten af ​​algoritmerne. I MapReduce forårsager enhver lokal aggregering af de mellemliggende resultater en reel forbedring af den globale effektivitet.

Det er af denne grund, at mange officielle MapReduce-distributioner ofte inkluderer lokale aggregeringsoperationer ved at bruge funktioner, der er i stand til at aggregere data lokalt. Undgå eller reducere så vidt muligt bevægelsen af ​​store filer. Enten tilføjet til map()-funktioner eller til lokale aggregatorer.

Fejltolerance

MapReduce-mekanismen er fejltolerant , når en af ​​arbejderne udsættes for en fejl. Ligesom MapReduce er den designet til processer, der involverer store datastørrelser ved hjælp af hundredvis eller tusindvis af computere. Selvom sandsynligheden for fejl er lav, er det meget muligt, at en (eller flere) af arbejderne bliver deaktiveret netop på grund af fejlen på den maskine, der understøttede den. "Masteren" pinger periodisk hver arbejder for at kontrollere dens status.

Hvis der ikke er svar efter en vis ventetid, tolker skibsføreren, at arbejderen er deaktiveret. Enhver map()-opgave, der er blevet fuldført af arbejderen, vender straks tilbage til sin ventetilstand og kan derfor være kvalificeret til tildeling til andre arbejdere. På samme måde nulstilles enhver map() (eller reducer) funktion, der er i gang under fejlen, til inaktiv og kan vælges til genallokering.

Fuldførte map()-opgaver udføres igen ved fejl, delvis fordi deres output er gemt på de lokale diske på den maskine, der fejlede, og derfor anses for utilgængelige. Hele reduce()-opgaver behøver ikke at blive genudført, da deres output er blevet gemt i systemet globalt. Når map()-opgaven udføres af arbejder A og derefter af arbejder B (hovedsageligt på grund af et nedbrud), får alle reduce()-opgaver i dette tilfælde besked om at fjerne data fra arbejder A og acceptere data fra arbejder A. arbejder B. På denne måde er MapReduce-udførelsen modstandsdygtig .

Eksempler

I beskrivelsen af ​​eksemplerne på brug af Map Reduce er det kun nødvendigt at beskrive detaljeret, hvordan map() og reduce()- operationerne implementeres i hvert enkelt tilfælde. Litteraturen viser gentagne eksempler på ordtal i et dokument, matrixoperationer og relationelle databaseforespørgselsoperationer.

Ordantal

Dette Map Reduce - eksempel er en proces til at tælle forekomsten af ​​hvert ord i et sæt dokumenter :

 kort ( strengnavn , strengdokument ) : _ _   
  // nøgle: dokumentnavn 
// værdi: dokumentindhold for hvert ord w i dokumentet :  
       
    EmitIntermediate ( w , 1 ); 

Map()-funktionen opdeler i dette tilfælde et dokument i ord (det vil sige tokeniserer det ) ved hjælp af en simpel leksikalsk analysator og udsender en række tupler af formen ( nøgle , værdi ), hvor nøglen er ordet, og værdien er "1". Det vil sige, for eksempel fra dokumentet "Lille hus på prærien" vil kortfunktionen returnere: ("la", "1"), ("hus", "1"), ("af", "1" ), ("den", "1"), ("eng", "1").

 
 reducer ( strengord , iterator partialCounts ) : _   
  // ord: et ord 
// partialCounts: en [[Iterator (designmønster)|delvis liste]] for at udføre samlede tællinger int resultat = 0 ;  
     
  for hver v i partialCounts :    
    resultat += ParseInt ( v );  
  Udsende ( resultat );

Her er hvert dokument opdelt i ord , og hvert ord tælles med begyndelsesværdien "1" af kortfunktionen, med ordet som nøgleresultat. Frameworket samler alle par med den samme nøgle og feeds ind i det samme Reduce-kald, så denne funktion behøver blot summen af ​​alle sine inputværdier for at finde den samlede forekomst af det ord. I eksemplet ovenfor ("la", "1") vises to gange, fordi tasten "la" har to forekomster, resten af ​​tasterne vises kun én gang.

Multiplikation af en matrix med en vektor

Lineære algebra - eksempler for matrixoperationer er de mest passende på grund af rammens egnethed i disse tilfælde. Antag, at vi har en kvadratisk matrix M af størrelsen nxn. Vi kalder elementet i række i og kolonne for j m _ij . Antag, at vi har en vektor v , således at vi i position j har elementet v _j . På denne måde vil resultatet af multiplikationen mellem matrixen M og vektoren v være en vektor x med længden n, på en sådan måde, at elementet x _i er sådan, at:

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

Denne operation udføres uden problemer for arrays på flere tusinde elementer, hvilket er dyrt for flere millioner. Problemet med dens beregning kommer, når det er beregnet til at blive udført med hundredvis af milliarder . Det er af denne grund, at det antages i anvendelsen af ​​M til at reducere , at n er af størrelsesordenen 10 ¹² . Map()- funktionen tager i dette tilfælde en række i af matricen og hele vektoren v for at danne par: (i, m _ij v _j ). Det vil sige af formen (1, m ₁₁ v ₁ ), (1, m ₁₂ v ₂ ), (1, m ₁₃ v ₃ ) ... (1, m _1j v _j ).

 kort ( Vector rowMatrix , Vector vector ) :   
  // nøgle: i -> vektorindeks 
// værdi: produkt af m<sub>ij</sub> af v<sub>j</sub>. for hver position i i vektor :  
       
    EmitIntermediate ( i , værdi ); 

Funktionen reduce() skal i dette tilfælde kun samle de par, der har den samme nøgle i, og tilføje dem.

 
 reducer ( strengord , iterator partialCounts ) : _   
  // ord: et ord 
// partialCounts: en [[Iterator (designmønster)|delvis liste]] for at udføre samlede tællinger int resultat = 0 ;  
     
  for hver v i partialCounts :    
    resultat += ParseInt ( v );  
  Udsende ( resultat );

Dataflow

MapReduce-rammen er en stor distribueret sorteringsalgoritme. De vigtigste moduler, som applikationen definerer, er:

• en inputlæser
• En kortfunktion
• en partitionsfunktion
• En sammenligningsfunktion
• En Reducer funktion
• En udadvendt forfatter

Indtastningslæser

Inputlæseren opdeler inputtet i passende størrelser "slices" (typisk mellem 64 MB og 128 MB), og rammen tildeler et udsnit til hver kortfunktion . Inputlæseren læser data fra stabilt lager (normalt et distribueret filsystem ) og genererer nøgle/værdi-par.

Et almindeligt eksempel vil læse en mappe fuld af tekstfiler og returnere hver linje som en post.

Kortfunktion

Kortfunktionen tager en række nøgle/værdi-par, behandler dem og genererer nul eller flere output-nøgle/værdi-par. Typerne af input- og outputkort kan være (og er ofte) forskellige fra hinanden.

Hvis applikationen tæller ord, vil kortfunktionen opdele linjerne i ord og generere et outputnøgle/værdipar for hvert ord. Hvert outputpar vil indeholde ordet som nøglen og antallet af forekomster af det på linjen som værdien.

Partitionsfunktion

Hvert output fra kortfunktionen er tildelt en reducering ved hjælp af partitionsfunktionen til at generere chunking. Partitionsfunktionen modtager nøglen og antallet af reduktioner og returnerer indekset for den ønskede reduktion .

Standardadfærden er at hente hash af nøglen og bruge hash modulo antallet af reduktioner . Det er vigtigt at vælge en partitionsfunktion, der genererer en tilnærmelsesvis jævn fordeling af data pr. shard for at opretholde balancen, ellers kan MapReduce-operationen blive langsommere ved at vente på, at langsomme reducerere (reducere tildelt flere data, end der er indeholdt i dens shard) er færdig.

Mellem kortlægnings- og reduktionsstadierne blandes dataene (parallelt sorteret / byttet mellem noder) for at flytte dataene fra det skær, hvor det blev produceret, til det skær, hvor det vil blive reduceret. Blanding kan i nogle tilfælde tage længere tid end behandling afhængigt af båndbredde, CPU-hastigheder, producerede data og tidsforbrug mellem kortlægning og reduktion af behandling.

Sammenligningsfunktion

Inputtet for hver reduktion fås fra den maskine, hvor kortet blev udført og bestilt ved hjælp af sammenligningsfunktionen

Reduktionsfunktion

Frameworket kalder applikationens Shrink -funktion én gang for hver unik nøgle i den sorterede liste. Reduceringen kan iterere gennem de værdier, der er forbundet med den pågældende nøgle og producere nul eller flere output.

I eksemplet med ordtælling tager funktionen Reducer inputværdierne, lægger dem sammen og genererer et enkelt output for ordet og den endelige sum.

Afslut forfatter

Output Writer skriver output fra Shrink - funktionen til lagertabeller, normalt et distribueret filsystem.

Bruger

Som en generel regel bruges Map Reduce i de samtidige computerproblemer, der involverer store datasæt , der skal behandles af et stort antal computere (knudepunkter), som tilsammen omtales som klynger (hvis alle noder er i det samme lokale netværk og ved at bruge den samme hardware), eller til grids (hvis noderne deles på en distribueret måde over store geografiske eller administrative områder, og som generelt har mere heterogen hardware). Parallel behandling kan forekomme ved hjælp af data lagret enten i et filsystem (ustruktureret) eller i en database (struktureret). Det er af denne grund, at det bruges i applikationer, der har data i stor skala, såsom parallelle applikationer, webindeksering, datamining og videnskabelig simulering.

Se også

MapReduce implementeringer

• Apache Hadoop
• CouchBase
• sofadb
• Infinispan
• MongoDB
• Riak