Big Data: MapReduce

3.1 Historik om uppkomsten av termen BigData

Termen Big Data dök upp relativt nyligen. Google Trender visar början på en aktiv tillväxt i användningen av frasen sedan 2011:

Samtidigt är det bara den lata som inte använder begreppet nu. Särskilt ofta används termen olämpligt av marknadsförare. Så vad är Big Data egentligen? Eftersom jag bestämde mig för att systematiskt ange och lyfta fram frågan är det nödvändigt att definiera begreppet.

I min praktik mötte jag olika definitioner:

• Big Data är när det finns mer än 100 GB data (500 GB, 1 TB, vad du än vill).
• Big Data är data som inte kan behandlas i Excel.
• Big Data är data som inte kan behandlas på en enda dator.

Och även dessa:

• Big Data är i allmänhet vilken data som helst.
• Big Data finns inte, den uppfanns av marknadsförare.

Jag kommer att hålla mig till definitionen från wikipedia:

Big data är en serie tillvägagångssätt, verktyg och metoder för att bearbeta strukturerad och ostrukturerad data av enorma volymer och betydande mångfald för att erhålla mänskliga märkbara resultat som är effektiva under förhållanden av kontinuerlig tillväxt, distribution över flera noder i ett datornätverk, bildat i slutet av 2000-talet, alternativ till traditionella databashanteringssystem och business intelligence-klasslösningar.

Med Big Data förstår jag alltså inte någon specifik mängd data och inte ens själva datan, utan metoder för att bearbeta dem, som tillåter distribuerad behandling av information. Dessa metoder kan tillämpas på stora datamängder (som innehållet på alla sidor på Internet) såväl som små dataset (som innehållet i denna föreläsning).

Här är några exempel på vad som kan vara en datakälla som kräver big data-tekniker:

• Loggar över användarbeteende på Internet
• GPS-signaler från bilar för ett transportföretag
• Data hämtade från sensorer i Large Hadron Collider
• Digitaliserade böcker i det ryska statsbiblioteket
• Information om transaktioner för alla bankkunder
• Information om alla köp i en stor detaljhandelskedja m.m.

Antalet datakällor växer snabbt, vilket gör att databehandlingstekniker blir mer och mer efterfrågade.

3.2 Big data-principer

Baserat på definitionen av Big Data kan vi formulera de grundläggande principerna för att arbeta med sådan data:

1. Horisontell skalbarhet. Eftersom det kan finnas en godtyckligt stor mängd data måste alla system som involverar bearbetning av stora data vara utbyggbara. Datavolymen ökade med 2 gånger - mängden järn i klustret ökades med 2 gånger och allt fortsatte att fungera.

2. Feltolerans. Principen om horisontell skalbarhet innebär att det kan finnas många maskiner i ett kluster. Till exempel har Yahoos Hadoop-kluster över 42 000 maskiner (du kan se klusterstorlekar över organisationer på den här länken). Det betyder att några av dessa maskiner garanterat kommer att misslyckas. Big data-praxis måste vara medveten om dessa störningar och överleva dem utan några betydande konsekvenser.

3. Datalokalitet. I stora distribuerade system distribueras data över ett stort antal maskiner. Om uppgifterna fysiskt finns på en server och behandlas på en annan kan kostnaderna för dataöverföring överstiga kostnaderna för själva behandlingen. Därför är en av de viktigaste principerna för att designa BigData-lösningar principen om datalokalitet – om möjligt behandlar vi data på samma maskin som vi lagrar dem på.

Alla moderna big data-verktyg följer dessa tre principer på ett eller annat sätt. För att följa dem är det nödvändigt att komma med några metoder, metoder och paradigm för att utveckla verktyg för datautveckling. En av de mest klassiska metoderna kommer jag att analysera i dagens föreläsning.

3.3 MapReduce

MapReduce är en distribuerad databearbetningsmodell som föreslagits av Google för att bearbeta stora mängder data på datorkluster. MapReduce illustreras väl av följande bild:

MapReduce antar att data är organiserade i vissa poster. Databehandling sker i tre steg:

1. Kartsteg . I detta skede förbearbetas data med funktionen map() som definieras av användaren. Arbetet i detta steg är att förbehandla och filtrera data. Operationen är mycket lik kartoperationen i funktionella programmeringsspråk - en anpassad funktion appliceras på varje indatapost.

Map()-funktionen som tillämpas på en enskild indatapost producerar många nyckel-värdepar. Set - det vill säga, det kan bara returnera en post, det kan inte returnera något, eller det kan returnera flera nyckel-värdepar. Vad som kommer att finnas i nyckeln och i värdet är upp till användaren, men nyckeln är en mycket viktig sak, eftersom data med en nyckel i framtiden kommer att falla in i en instans av reduceringsfunktionen.

2. Stage Shuffle. Det går obemärkt för användaren. I detta steg är kartfunktionens utgång "binned" - varje fack motsvarar en utgångsnyckel för kartsteget. I framtiden kommer dessa korgar att fungera som en ingång för reducering.

3. Reducera steg. Varje "korg" med värden som genereras vid shuffle-steget kommer till ingången för reduce()-funktionen.

Reduceringsfunktionen ges av användaren och beräknar slutresultatet för en enda "korg" . Uppsättningen av alla värden som returneras av reduce()-funktionen är det slutliga resultatet av MapReduce-uppgiften.

Några ytterligare fakta om MapReduce:

1. Alla körningar av kartfunktionen fungerar oberoende och kan köras parallellt, även på olika klustermaskiner.
2. Alla körningar av reduceringsfunktionen fungerar självständigt och kan köras parallellt, inklusive på olika klustermaskiner.
3. Shuffle representerar internt en parallell sortering, så det kan också fungera på olika klustermaskiner. Punkterna 1-3 låter dig implementera principen om horisontell skalbarhet .
4. Kartfunktionen används vanligtvis på samma maskin där data lagras - detta minskar överföringen av data över nätverket (principen om datalokalitet).
5. MapReduce är alltid en fullständig dataskanning, det finns inga index. Detta gör att MapReduce är dåligt applicerbart när ett svar krävs mycket snabbt.

3.4 Exempel på uppgifter som effektivt lösts med MapReduce

Antal ord

Låt oss börja med den klassiska uppgiften - Ordräkning. Uppgiften är formulerad enligt följande: det finns en stor korpus av dokument. Uppgiften är att beräkna det totala antalet gånger som det förekommer i korpusen för varje ord som förekommer minst en gång i korpusen.

Lösning:

Eftersom vi har en stor korpus av dokument, låt ett dokument vara en indatapost för MapRreduce-uppgiften. I MapReduce kan vi bara definiera användardefinierade funktioner, vilket vi kommer att göra (vi kommer att använda python-liknande pseudokod):

def map(doc): 
for word in doc: 
yield word, 1 

def reduce(word, values): 
yield word, sum(values) 

Kartfunktionen förvandlar inmatningsdokumentet till en uppsättning par (ord, 1), blanda transparent för oss omvandlar det till par (ord, [1,1,1,1,1,1]), minska summorna av dessa, returnerar det sista svaret för ordet.

Bearbetning av annonssystemloggar

Det andra exemplet är hämtat från Data-Centric Alliances verkliga praxis.

Uppgift: det finns en csv-logg för annonssystemet i formuläret:

<user_id>,<country>,<city>,<campaign_id>,<creative_id>,<payment></p> 
 
11111,RU,Moscow,2,4,0.3 
22222,RU,Voronezh,2,3,0.2 
13413,UA,Kyiv,4,11,0.7 
… 

Det är nödvändigt att beräkna den genomsnittliga kostnaden för att visa reklam i städerna i Ryssland.

Lösning:

def map(record): 
user_id, country, city, campaign_id, creative_id, payment = record.split(",") 
payment=float(payment) 
if country == "RU": 
yield city, payment 

def reduce(city, payments): 
yield city, sum(payments)/len(payments) 

Kartfunktionen kontrollerar om vi behöver denna post - och om vi gör det lämnar den endast nödvändig information (ort och betalningsbelopp) . Minska funktionen beräknar det slutliga svaret för en stad med en lista över alla betalningar i den staden.