MapReduce er en distribueret computermodel introduceret af Google , brugt til parallel beregning på meget store, op til flere petabyte [1] , datasæt i computerklynger .
MapReduce er en ramme til beregning af et sæt distribuerede opgaver ved hjælp af et stort antal computere (kaldet "knuder"), der danner en klynge .
Arbejdet med MapReduce består af to trin: Map og Reduce, opkaldt efter funktionerne af højere orden af samme navn , map og reduce .
Korttrinnet forbehandler inputdataene. For at gøre dette modtager en af computerne (kaldet hovedknudepunktet - masterknudepunktet) opgavens inputdata, deler det op i dele og sender det til andre computere (arbejdsknudepunkter - arbejdsknudepunkt) til forbehandling.
Ved reduktionstrinnet reduceres de forbehandlede data. Hovedknudepunktet modtager svar fra arbejderknudepunkterne og genererer på deres grundlag et resultat - en løsning på det problem, der oprindeligt blev formuleret.
Fordelen ved MapReduce er, at det giver dig mulighed for at udføre forbehandlings- og reduktionsoperationer på en distribueret måde. Forbehandlingsoperationerne fungerer uafhængigt af hinanden og kan udføres parallelt (selvom dette i praksis er begrænset af inputkilden og/eller antallet af anvendte processorer). På samme måde kan flere arbejderknudepunkter udføre oprulning - dette kræver kun, at alle forbehandlingsresultater med én specifik nøgleværdi behandles af én arbejderknude ad gangen. Selvom denne proces kan være mindre effektiv end mere sekventielle algoritmer, kan MapReduce anvendes på store mængder data, der kan behandles af et stort antal servere. For eksempel kan MapReduce bruges til at sortere en petabyte af data på blot et par timer. Parallelisme giver også en vis genopretning fra delvise serverfejl: hvis en arbejderknude, der udfører en forbehandlings- eller reduktionsoperation, mislykkes, kan dens arbejde overføres til en anden arbejderknude (forudsat at inputdataene for den operation, der udføres), er tilgængelige).
Frameworket er stærkt baseret på kortet og reducerer funktioner, der er meget udbredt i funktionel programmering [2] , selvom den faktiske semantik af frameworket er forskellig fra prototypen [3] .
Det kanoniske eksempel på en applikation skrevet med MapReduce er processen med at tælle antallet af gange, forskellige ord forekommer i et sæt dokumenter:
// Funktion brugt af arbejderknudepunkter i korttrinnet // til at behandle nøgleværdipar fra inputstrømmens tomhedskort ( String name , String document ) : // Inputdata: // navn - dokumentnavn // dokument - dokumentindhold for hvert ord i dokumentet : EmitIntermediate ( ord , "1" ); // Funktion brugt af arbejderknuderne i Reducer-trinnet // til at behandle nøgleværdi-parrene opnået i Map step void reduce ( Iterator partialCounts ) : // Input data: // partialCounts - liste over grupperede mellemresultater. Antallet af indtastninger i partialCounts er // den påkrævede værdi int result = 0 ; for hver v i partialCounts : resultat += parseInt ( v ); Emit ( AsString ( resultat ));I denne kode, ved Kort-trinnet, er hvert dokument opdelt i ord, og par returneres, hvor nøglen er selve ordet, og værdien er "1". Hvis det samme ord forekommer flere gange i et dokument, vil der som følge af den foreløbige behandling af dette dokument være lige så mange af disse par som det antal gange, dette ord forekommer. De genererede par sendes til yderligere behandling, systemet grupperer dem efter nøgle (i dette tilfælde er nøglen selve ordet) og fordeler dem mellem flere processorer. Sæt af objekter med den samme nøgle i gruppen kommer til input af reduceringsfunktionen, som behandler datastrømmen og reducerer dens volumen. I dette eksempel lægger reduktionsfunktionen simpelthen forekomsterne af et givet ord sammen over hele strømmen, og resultatet - kun én sum - sendes videre som output.