MapReduce

M ap R educe är född från de principer som är kända sedan åttiotalet för distribuerad datoranvändning .

M ap R educe är en programmeringsmodell för att stödja parallell beräkning av stora samlingar av data i grupper av datorer och commodity computing . Namnet på ramverket är inspirerat av namnen på två viktiga metoder , makron eller funktioner i funktionell programmering: Map och Reduce . Map Reduce har antagits över hela världen, eftersom det finns en OpenSource- implementation som heter Hadoop. Dess utveckling leddes ursprungligen av Yahoo och utförs för närvarande av Apache-projektet . Sedan 2010-talet har det funnits flera initiativ liknande Hadoop inom både industri och akademi. Implementeringar av Map Reduce -bibliotek har skrivits i olika programmeringsspråk som C ++ , Java och Python .

M ap R educe används i den praktiska upplösningen av vissa algoritmer som kan parallelliseras. Men Map Reduce är inte lösningen på alla problem, på samma sätt som alla problem inte kan lösas effektivt med Map Reduce . Problem med stora datamängder, som når petabyte i storlek, tas i allmänhet upp. Det är av denna anledning som detta ramverk vanligtvis körs på ett distribuerat filsystem (HDFS).

Historik

Tidiga Google-implementeringar behövde utföra stora matrismultiplikationsoperationer för att beräkna PageRank , det vill säga rankningen av sidor i en sökning. På detta sätt blev Map Reduce populär som en beräkningsmetod för linjär algebra . Oron för att hantera stora samlingar av data ledde till skapandet av algoritmer och ramverk som kan bearbeta terabyte med information. En av de första applikationerna som kan programmera Map Reduce implementerades initialt i Hadoop , ursprungligen designad av Doug Cutting , som döpte den efter sin sons leksakselefant. Det utvecklades ursprungligen för att stödja distributionen av Nutch -sökmotorprojektet . ]

Översikt

M ap R educe är ett ramverk för att bearbeta problem parallellt över stora datamängder med ett stort antal datorer (noder), gemensamt kallade ett kluster (om alla noder finns i samma lokala nätverk och använder liknande hårdvara) eller ett nätverk (om noder delas över geografiskt och administrativt distribuerade system och använder mer heterogen hårdvara). Bearbetning kan göras på data som lagras i ett filsystem (ostrukturerat) eller i en databas (strukturerat). M ap R educe kan dra fördel av lokaliseringen av data, bearbeta den nära där den lagras för att minimera kommunikationskostnader.

Ett Map Reduce- ramverk (eller system) består vanligtvis av tre operationer (eller steg):

1. Karta: Varje slavnod (arbetare) tillämpar funktionen mappå lokal data och skriver utdata till temporär lagring. En masternod säkerställer att endast en kopia av den redundanta indata bearbetas.
2. Blanda: Arbetare omfördelar data baserat på utdatanycklar (producerade av funktionen map), så att all data som hör till en nyckel finns i samma arbetarnod.
3. Minska: Arbetarnoderna behandlar nu varje grupp av utdata, med nyckel, parallellt.

M ap R educe tillåter distribuerad bearbetning av kartan och reducerar operationer. Kartor kan göras parallellt, så länge varje kartläggning är oberoende av de andra; i praktiken begränsas detta av antalet oberoende datakällor och/eller antalet CPU:er nära varje källa. På liknande sätt kan en uppsättning "reducerare" utföra reduceringsfasen, så länge som alla utgångar från kartoperationen som delar samma nyckel presenteras för samma reducerare samtidigt, eller så är reduceringsfunktionen associativ . Även om denna process ofta verkar ineffektiv jämfört med algoritmer som är mer sekventiella (eftersom flera instanser av reduceringsprocessen måste utföras), kan Map Reduce tillämpas på betydligt större datamängder än vad en enda "grundläggande" server kan hantera. ". En stor serverfarm kan använda Map Reduce för att sortera en petabyte data på bara några timmar. Parallellism erbjuder också möjligheten att återhämta sig från ett partiellt fel på servrar eller lagring under drift: om en mappare eller reducerare misslyckas kan jobbet schemaläggas om, förutsatt att indata fortfarande är tillgängliga.

Logisk vy

Alla processer kan inte hanteras från M ap R educe- ramverket . Specifikt är endast de som kan delas upp i map() - och reduce() -operationerna adresserbara, och detta är viktigt när man väljer detta ramverk för att lösa ett problem. Map- och Reducer-funktionerna är båda definierade med avseende på data strukturerad i tuplar av typ (nyckel, värde).

Map() funktion

Map tar ett av dessa datapar med en typ i en datadomän och returnerar en lista med par i en annan domän:

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

• Map () -funktionen : hanterar mappningen och tillämpas parallellt för varje objekt i datainmatningen . Detta ger en lista med (k2,v2) par för varje samtal. Efter det samlar Map Reduce-ramverket alla par med samma nyckel från alla listor och grupperar dem, och skapar en grupp för var och en av de olika genererade nycklarna. Ur en arkitektonisk synvinkel tar masternoden ingången, delar upp den i små bitar eller problem med mindre identitet och distribuerar dem till de så kallade arbetarnoderna . En arbetarnod kan delas upp igen, vilket ger upphov till en trädstruktur . Arbetarnoden bearbetar problemet och skickar svaret till huvudnoden .

Reduce() funktion

Reduceringsfunktionen tillämpas parallellt för varje grupp, och producerar en samling värden för varje domän:

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

• Funktionen reduce() : Varje anrop till Reduce producerar vanligtvis ett v3-värde eller ett tomt anrop, även om ett anrop kan returnera mer än ett värde. Returen av alla dessa samtal samlas in som önskad resultatlista.

Därför omvandlar MapReduce-ramverket en lista med (nyckel, värde) par till en lista med värden. Detta beteende skiljer sig från funktionell programmerings "map and reduce" join , som accepterar en godtycklig lista med värden och returnerar ett enda värde som kombinerar alla värden som returneras av kartan.

MapReduce arkitektur

Map () -funktionen exekveras på ett distribuerat sätt över flera maskiner. Indata, som vanligtvis kommer från en stor fil (fil), är uppdelad i en uppsättning M indatapartitioner på vanligtvis 16 till 64 megabyte. Dessa partitioner kan bearbetas på olika maskiner. Flera operationer förekommer vanligtvis i en MapReduce- anrop :

• Posterna delas sedan in i M partitioner med ungefärlig storlek från 16 till 64 megabyte . MapReduce-programmet börjar instansiera sig själv på de olika maskinerna i klustret. Som regel konfigureras antalet instanser i applikationerna.

• En av kopiorna av programmet är speciell och tar rollen som "mästare". Resten av exemplaren kallas "arbetare" och får tilldelningen av sina uppgifter av befälhavaren. Det anses att det finns ett antal M map() -uppgifter och R reduce(). "Mastaren" är ansvarig för att samla in "arbetare" i vila (dvs. utan någon tilldelad uppgift) och kommer att tilldela en specifik map()- eller reduce()-uppgift till den. En arbetare kan bara ha tre tillstånd: inaktiv, arbetande, komplett.

• En arbetare som tilldelats en specifik map() -uppgift kommer att ta motsvarande partition som indata. Den kommer att analysera paren (nyckel, värde) för att skapa ett nytt utgångspar, som specificerats i dess programmering. Nyckel-värdeparen som produceras av map()-funktionen buffras i minnet.

• Periodiskt skrivs buffrade nyckel-värdepar till den lokala disken, spridda över R-regioner. Regionerna i dessa nyckel-värdepar skickas till master, som ansvarar för att omdirigera arbetare som har reduce()-uppgifter.

• När en arbetare av typen reducera meddelas av "mastern" med platsen för en partition, använder den fjärranrop för att läsa informationen lagrad på hårddiskarna hos de olika arbetarna av typen map(). När en arbetare av typen reduce() läser alla mellanliggande data, ordnar den nycklarna på ett sådant sätt att de hittade data med samma nyckel grupperas tillsammans. Ordningen är nödvändig eftersom, som en allmän regel, många olika map() funktionsnycklar kan gå in i samma reduce() funktion. I de fall där mängden mellanliggande data är mycket stor används ofta en extern sortering.

• Arbetaren av typen reduce() itererar över uppsättningen av mellansorterade värden, och den gör det för varje unik nyckel som hittas. Den tar nyckeln och uppsättningen värden som är associerade med den och skickar dem till reduce()-funktionen. Utdata från reduce() läggs till i MapReduce-utdatafilen.

• När alla map() och reduce() uppgifter har slutförts, tar "mastern" upp användarprogrammet. Vid denna tidpunkt returnerar MapReduce-anropet kontrollen till en användares kod.

Uppgifter anses ha avslutats när denna kontroll har återlämnats till användaren. Utgångarna distribueras i en komplett fil, eller om de inte är distribuerade i R-filer. Dessa R-filer kan vara indata från en annan MapReduce eller kan bearbetas av något annat program som behöver dessa data.

Combiner (Local Aggregators)

I en klustermiljö finns en av begränsningarna i transporten av stora filer mellan datorer på grund av deras begränsade bandbredd . I MapReduce-ramverket skriver map()-funktionen till en lokal teckenbuffert, till exempel en hårddisk . Informationen som skrivs lokalt aggregeras och beställs av en aggregatorfunktion som ansvarar för att utföra denna operation. De ordnade värdena är av formen [k, [v ₁ , v ₂ , v ₃ , ..., v _n ]]. På detta sätt får reduce()-funktionen en lista med värden associerade med en enda nyckel från kombinatorn. Eftersom latensen för nätverket av datorer och deras diskar vanligtvis är större än någon annan operation, kommer varje minskning av mängden mellanliggande data att öka effektiviteten hos algoritmerna. I MapReduce orsakar varje lokal aggregering av mellanresultaten en verklig förbättring av global effektivitet.

Det är av denna anledning som många officiella MapReduce-distributioner ofta inkluderar lokala aggregeringsoperationer, genom att använda funktioner som kan aggregera data lokalt. Undvika eller minska så långt som möjligt rörelsen av stora filer. Antingen lagts till map()-funktioner eller till lokala aggregatorer.

Feltolerans

MapReduce-mekanismen är feltolerant när en av arbetarna utsätts för ett fel. Liksom MapReduce har den designats för processer som involverar stora datastorlekar med hjälp av hundratals eller tusentals datorer. Även om sannolikheten för fel är låg är det mycket möjligt att en (eller flera) av arbetarna kommer att avaktiveras just på grund av felet på maskinen som stödde den. "Mastaren" pingar med jämna mellanrum varje arbetare för att kontrollera dess status.

Om det inte kommer något svar efter en viss väntetid tolkar befälhavaren att arbetaren är avaktiverad. Varje map()-uppgift som har slutförts av arbetaren återgår omedelbart till sitt vänteläge och kan därför vara kvalificerad för tilldelning till andra arbetare. På samma sätt återställs alla map()- (eller reducer)-funktioner som pågår under felet till inaktiv och kan väljas för omallokering.

Slutförda map()-uppgifter körs om vid misslyckande, delvis eftersom deras utdata lagras på de lokala diskarna på maskinen som misslyckades, och anses därför vara otillgängliga. Hela reduce()-uppgifter behöver inte köras om eftersom deras utdata har lagrats i systemets globala. När map()-uppgiften exekveras av arbetare A och sedan av arbetare B (främst på grund av en krasch), i detta fall meddelas alla reduce()-uppgifter att ta bort data från arbetare A och acceptera data från arbetare A. arbetare B. På så sätt är MapReduce-utförandet motståndskraftigt .

Exempel

I beskrivningen av exemplen på användning av Map Reduce är det bara nödvändigt att beskriva i detalj hur map() - och reduce() -operationerna implementeras i varje enskilt fall. Litteraturen visar upprepade exempel på ordantal i ett dokument, matrisoperationer och relationsdatabasfrågeoperationer.

Ordräkning

Det här Map Reduce- exemplet är en process för att räkna förekomsten av varje ord i en uppsättning dokument :

 karta ( strängnamn , strängdokument ) : _ _   
  // nyckel: dokumentnamn 
// värde: dokumentinnehåll för varje ord w i dokument :  
       
    EmitIntermediate ( w , 1 ); 

Map()-funktionen delar i det här fallet upp ett dokument i ord (det vill säga tokeniserar det ) med en enkel lexikalanalysator och matar ut en serie tuplar av formen ( nyckel , värde ) där nyckeln är ordet och värdet är "1". Det är till exempel från dokumentet "Lilla huset på prärien" skulle kartfunktionen returnera: ("la", "1"), ("hus", "1"), ("av", "1" ), ("den", "1"), ("äng", "1").

 
 reducera ( Strängord , Iterator partialCounts ) : _   
  // ord: ett ord 
// partialCounts: en [[Iterator (designmönster)|dellista]] för att utföra aggregerade räkningar int resultat = 0 ;  
     
  för varje v i partialCounts :    
    resultat += ParseInt ( v );  
  Emit ( resultat );

Här är varje dokument indelat i ord och varje ord räknas med startvärdet "1" av kartfunktionen, med ordet som nyckelresultat. Ramverket samlar alla par med samma nyckel och matas in i samma Reduce-anrop, så den här funktionen behöver bara summan av alla dess indatavärden för att hitta den totala förekomsten av det ordet. I exemplet ovan visas ("la", "1") två gånger eftersom tangenten "la" har två förekomster, resten av tangenterna visas bara en gång.

Multiplikation av en matris med en vektor

Linjära algebraexempel för matrisoperationer är de mest lämpliga på grund av ramverkets lämplighet i dessa fall. Antag att vi har en kvadratisk matris M av storleken nxn. Vi kallar elementet i rad i och kolumn j m _ij . Antag att vi har en vektor v sådan att vi i position j har elementet v _j . På detta sätt blir resultatet av multiplikationen mellan matrisen M och vektorn v en vektor x med längden n, på ett sådant sätt att elementet x _i är sådant att:

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

Denna operation utförs utan problem för arrayer med flera tusen element, vilket är kostsamt för flera miljoner. Problemet med dess beräkning kommer när det är tänkt att göras med hundratals miljarder . Det är av denna anledning som det antas i tillämpningen av M för att reducera att n är av storleksordningen 10 ¹² . Map () -funktionen tar i detta fall en rad i av matrisen och hela vektorn v för att bilda par: (i, m _ij v _j ). Det vill säga av formen (1, m ₁₁ v ₁ ), (1, m ₁₂ v ₂ ), (1, m ₁₃ v ₃ ) ... (1, m _1j v _j ).

 karta ( Vector rowMatrix , Vector vector ) :   
  // nyckel: i -> vektorindex 
// värde: produkt av m<sub>ij</sub> av v<sub>j</sub>. för varje position i i vektorn :  
       
    EmitIntermediate ( i , värde ); 

Funktionen reduce() behöver i det här fallet bara samla de par som har samma nyckel i och lägga till dem.

 
 reducera ( Strängord , Iterator partialCounts ) : _   
  // ord: ett ord 
// partialCounts: en [[Iterator (designmönster)|dellista]] för att utföra aggregerade räkningar int resultat = 0 ;  
     
  för varje v i partialCounts :    
    resultat += ParseInt ( v );  
  Emit ( resultat );

Dataflöde

MapReduce-ramverket är en stor distribuerad sorteringsalgoritm. Huvudmodulerna som applikationen definierar är:

• en ingångsläsare
• En kartfunktion
• en partitionsfunktion
• En jämförelsefunktion
• En Minska- funktion
• En utåtriktad författare

Inmatningsläsare

Ingångsläsaren delar in inmatningen i "skivor" av lämplig storlek (vanligtvis mellan 64 MB och 128 MB) och ramverket tilldelar en del till varje kartfunktion . Ingångsläsaren läser data från stabil lagring (vanligtvis ett distribuerat filsystem ) och genererar nyckel/värdepar.

Ett vanligt exempel kommer att läsa en katalog full av textfiler och returnera varje rad som en post.

Kartfunktion

Kartfunktionen tar en serie nyckel/värdepar, bearbetar dem och genererar noll eller fler utdatanyckel/värdepar. Typerna av inmatnings- och utgångskartor kan vara (och är ofta) olika varandra.

Om applikationen räknar ord kommer kartfunktionen att dela upp raderna i ord och generera ett utdatanyckel/värdepar för varje ord. Varje utdatapar kommer att innehålla ordet som nyckel och antalet instanser av det på raden som värde.

Partitionsfunktion

Varje utgång från kartfunktionen tilldelas en reducerare som använder partitionsfunktionen för att generera chunking. Partitionsfunktionen tar emot nyckeln och antalet reducerare och returnerar indexet för den önskade reduceraren .

Standardbeteendet är att hämta hash för nyckeln och använda hash modulo antalet reducerare . Det är viktigt att välja en partitionsfunktion som genererar en ungefär jämn fördelning av data per skärva för att bibehålla balansen, annars kan MapReduce-operationen sakta ner genom att vänta på att långsamma reducerare (reducerare tilldelade mer data än vad som finns i dess skärva) ska avslutas.

Mellan mappnings- och reduktionsstegen blandas data (parallellsorterad / växlad mellan noder) för att flytta data från skärpan där den producerades till skärvan där den kommer att reduceras. Blandning kan i vissa fall ta längre tid än bearbetning beroende på bandbredd, CPU-hastigheter, producerad data och tid som går åt mellan kartläggning och minskning av bearbetningen.

Jämförelsefunktion

Indata för varje minskning erhålls från maskinen där kartan utfördes och beställdes med hjälp av jämförelsefunktionen

Reduktionsfunktion

Ramverket anropar applikationens Shrink -funktion en gång för varje unik nyckel i den sorterade listan. Reducera kan iterera genom värdena som är associerade med den nyckeln och producera noll eller fler utgångar.

I exemplet med ordräkning tar funktionen Reducera ingångsvärdena, adderar dem och genererar en enda utdata för ordet och slutsumman.

Avsluta författare

Output Writer skriver utdata från Shrink- funktionen till lagringstabeller, vanligtvis ett distribuerat filsystem.

Använder

Som en allmän regel används Map Reduce i de samtidiga datorproblem som involverar stora datamängder som måste bearbetas av ett stort antal datorer (noder), som tillsammans kallas kluster (om alla noder är i samma lokala nätverk och med samma hårdvara), eller till nät (om noderna delas på ett distribuerat sätt över stora geografiska eller administrativa områden och som generellt har mer heterogen hårdvara). Parallell bearbetning kan ske med hjälp av data lagrad antingen i ett filsystem (ostrukturerat) eller i en databas (strukturerat). Det är av denna anledning som det används i applikationer som har storskalig data, såsom parallella applikationer, webbindexering, datautvinning och vetenskaplig simulering.

Se även

MapReduce implementeringar

• Apache Hadoop
• CouchBase
• couchdb
• Infinispan
• MongoDB
• Riak