MapReduce

**MapReduce** programazio-eredu bat da, eta hari lotutako inplementazioa, datu kopuru handiekin lan egin ahal izateko.

Erabiltzailearekiko gardena den, paralelizazio automatikoa erabiltzen du. Gainera, lanaren banaketa dinamikoa egiten du, makinen hutsegiteei aurre egiten die eta makina arteko komunikazioa jorratzen ditu, besteak beste. Google-ren MapReduce inplementazioa cluster handiekin eta datu kopuru handiekin lan egiteko pentsatuta dago.

## Sarrera 
Programazio-eredu honen helburua abstrakzio maila handiago batekin lan egitea da, Google-n
egunerokotasunean aurkitzen dituzten arazoei erarik eraginkorrenean aurre egin ahal izateko.
Eredu hau, datu kopuru handien tratamenduan oinarrituta dago eta hauek makina handietan
exekutatuko dira. Abstrakzio maila handiago bat diseinatu dute, non paralelizazioko mami
nahasgarriak ezkutatzen diren. Eredu hau Lisp-eko map eta reduce funtzioetan oinarrituta
dago.

Lan honen ekarpenik handiena interfaze sinple eta boteretsu bat eskaintzea da, eta honen
bitartez paralelizazio zein datu kopurua oso handien banaketa automatikoa. Modu honetan,
errendimendu oso handia lortzen dute makina arruntez osatutako clusterretan.

## Programazio-eredua 
Ereduaren konputazioak sarrerarako gako/balio pareen bilduma bat hartzen du, eta irteera
bezala beste gako/balio pare bilduma bat ematen du. MapReduce liburutegiaren erabiltzaileak
bi funtzio idatzi behar ditu: Map eta Reduce.
Map eta Reduce funtzioak, Lisp-en (LISt Processing) oinarrituta egonda , zerrendekin lan egiten
dute. Map funtzioak eragiketa bat aplikatzen die zerrendako elementu bakoitzari. Adibidez, +1
izan daiteke eragiketa eta (0, 3, 4, 89, 6, 11) hasierako zerrenda. Map funtzioa aplikatu eta gero
(1, 4, 90, 7, 12) zerrenda izango dugu. Adibide honetan bezala, eragiketa trukakorra baldin bada
elementu guztien artean, paralelizazio inplizitu bat dago eta eragiketaren aplikazio ordenak ez
du garrantzirik. Hots erraz inplementatu daiteke.

### Adibideak 
Adibide gisa, izan bedi datu kopuru handi batean hitz bakoitzaren maiztasuna kontatu nahi
dugula. Erabiltzaileak ondorengo pseudokodea idatzi dezake:

  virtual void Map(String gakoa, String balioa) {
  // gakoa: dokumentuaren izena
  // balioa: dokumentuaren edukia
  for each word in balioa
    EmitIntermediate(w,"1");
  }

  virtual void Reduce(String gakoa, Iteratzailea balioak) {
  // gakoa: hitz bat
  // balioa: kontatutakoen zerrenda
  int emaitza = 0;
  for each v in balioak
    Emit(AsString(emaitza));
  }

Map funtzioak hitz bakoitzerako, hitza bera gehi eragiketa bat bidaltzen du (kasu sinple
honetan ‘1’ zenbakia soilik), Emit gisa. Reduce funtzioak hitz bakoitzarentzako bidalitako Emit
guztiak baino ez ditu biltzen eta emaitza bezala itzultzen.

## Inplementazioa 
Teknika honen inplementazioak erabiliko den ingurunearen eragin handia dauka. Hau da,
inplementazioa erabat aldatuko da erabiliko den makina bat memoria konpartitukoa bada edo
NUMA (memoria fisikoki banatua eta logikoki konpartitua) edo cluster handi bat bada.
Artikuluan, azken mota honetako makina bat erabiltzen dute eta probak egiteko erabili duten
cluster bateko ezaugarrien adibide bat dago segidan:
* x86 arkitekturako bi nukleotako prozesagailuak.
* Linux sistema eragilea.
* 2-4 GB RAM memoria.
* Sare hardware arrunta: normalean 100 Mbps edo 1 Gbps Ethernet sareak.
* Ehunaka milaka nodo cluster bakarrean, ondorioz nodoen akatsak ohikoak dira.
* Disko gogorrak IDE interfaze arruntaz konektatuta daude nodo bakoitzera. GFS(Google File System): fitxategi sistema banatua. Eskuragarritasuna eta fidagarritasuna eskaintzen du hardware ez-fidagarriaren gainean. Gainera bloke tamaina oso handiak dituzte, datu trukaketa azkarragoa izan dadin.
* Lanak exekutatzeko ilara bat erabiltzen da. Erabiltzaileak lana ilarara sartzen du eta antolatzaile batek lanak era egokian banatzen ditu, nahiko baliabide libre daudenean.

### Exekuzioaren gainbegiratua 
Jarraian, cluster motako makina baten exekuzioa nondik nora joaten den ikusiko dugu.
Hasteko, Map funtzioak sarrerako datuak M zatitan eginez banatzen ditu makina desberdinen
artean. Reduce funtzioak tarteko datuak R zatitan banatzen ditu, normalean horretarako funtzio
bat erabiliz (adib.: hash(gakoa) mod R).
Hurrengo irudiak erakusten du exekuzioaren egitura logikoa:
thumb|eskuina|600px|MapReduce algoritmoaren exekuzioa
# MapReduce funtzioak sarrerako fitxategiak M zatitan banatzen ditu, orokorrean 16 megabytetatik 64 megabytetarainoko zatitan. Orduan, hainbat exekuzio hasten dira clusterrean zehar banatutako makinetan.
# Kopietako bat berezia da, nagusia. Bestelako guztien nagusiak esleitutako lana exekutatuko dute. M Map ataza eta R Reduce ataza daude.
# Map ataza bat esleituta duen prozesuak datuak irakurtzen ditu sarrerako fitxategitik. Sarrerako gako/balio pareak erabiltzaileak idatzi duen Map funtzioarekin parseatzen ditu. Map funtzioak sortutako tarteko balioak memoriako bufferretan gordetzen dira.
# Aldiro, memoriako pareak disko lokalean gordetzen dira, R zatitan banatuta dagoena. Datu hauen diskoko kokalekua ataza nagusiari pasatzen zaio eta honek, murrizketa (Reduce) funtzioa exekutatu behar dutenei abisatzeaz arduratzen da.
# Murrizketa ataza bati kokapen horietaz abisatzen dioenean nagusiak, urruneko prozedura dei (RPC gisako dei bat) bitartez map ataza exekutatu den disko lokaletik datuak irakurriko ditu. Reduce atazak tarteko datu guztiak dituenean, gakoaren arabera bildu eta ordenatzen ditu. Prozesu hau beharrezkoa da askotan gako desberdinak Reduce ataza berdinera mapatzen direlako.
# Reduce atazak, tarteko ordenatutako datuen artean iteratzen du eta gako bakar bakoitzarentzako irteera datu bat sortzen du. Irteera honetan, gakoa eta dagokion datu bilduma itzultzen dizkio erabiltzailearen Reduce funtzioari. Reduce funtzioaren emaitza irteerako fitxategiari eransten zaio, Reduce zati bakoitzarentzako.
# Map eta Reduce funtzio guztiak amaitu direnean nagusiak erabiltzailearen programa esnatzen du. Puntu honetan, MapReduce deiak kontrola erabiltzailearen kodeari itzultzen dio.

### Datu-egitura nagusiak 
Nodo nagusian hainbat datu-egitura gordetzen dira. Nagusiak, Map eta Reduce ataza
bakoitzeko egoera gordetzen du (egonean, lanean edo bukatuta), eta langile bakoitzaren
identifikatzailea ere (egonean ez dauden atazentzat).

### Hutsegiteekiko tolerantzia 
Sistema honek hutsegiteei aurre egiteko diseinatuta egon behar du, ehunaka nodotan exekutatu
behar delako. Hutsegiteei aurre egiteko erabiltzen duten teknika prozesuak berriro exekutatzea
da. Hau da, prozesu langile batek huts egiten badu, horri zegokion lana beste makina batean
exekutatuko da.
Nagusiak, langile batek huts egin duela konturatzeko, aldiro-aldiro mezu bat bidaltzen dio
langile bakoitzari eta denbora jakin batean erantzunik jasotzen ez badu langilea akasdun bezala
markatzen du. Exekutatzen ari zen lana galdutzat joko da, baina langilea berreskuratzen
denean egonean egoerara itzuliko da eta lan gehiago jaso ahal izango ditu.
Aldiz, nagusia baldin bada huts egiten duena, orduan exekuzioa berriro egin beharko du
erabiltzailearen programak. Baina, hori bai, nodo nagusiak sarri gorde dezake uneko egoerari
dagokion informazioa, kudeatzen dituen datu-egiturak disko gogorrera kopiatuz. Horrela,
hurrengo nagusi berriak azkeneko une egonkorretik abiatuko du bere exekuzioa. Estrategia hau
jarraitzen dute, nagusiaren hutsegiteak urriak izango direla argudiatzen dutelako.
Beste hutsegiteko modu bat, exekuzioa gehiegi luzatzea da, makina batek disko-gogorra erdi
hondatuta daukalako adibidez. Hori gertatuz gero, exekuzio orokorra luzatzen da eta ekiditeko
MapReduce-k exekuzioa bukatzera doanen, hots, prozesu gehienek amaitu dutenean, oraindik
lanean daudenen exekuzioen backup atazak bidaltzen ditu beste makina batzuetara. Ataza hori
bukatutzat emango du, bukatu duena backup-a izan edo exekuzio nagusia izan.
Teknika hauen eraginkortasuna frogatzeko hainbat proba egin dituzte. Proba hauetan gutxi
gora-behera 1 TB ordenatzen dituzte. Goiko grafikoek Map atazak laburtzen dituzte, erdikoek,
Map-etik Reduce-ra pasa beharreko datuak eta behekoek, Reduce funtzioaren irteerako datuak.
Ezkerreko zutabean exekuzio arrunta ikusi daiteke eta 850 segundo inguru behar ditu
bukatzeko. Erdiko zutabean backup inplementazioa desgaitu da eta makina motelen eragina
ikus daiteke. Orotara 1.284 segundo behar ditu, hau da, %44 motelago. Eskuineko zutabean, 200
ataza akatzean dituzte, nodoen hutsegiteak simulatzeko, eta lortzen duten exekuzio denbora
933 segundotakoa da, apenas %5 motelago.

## Bestelako inplementazioak 
Google-ren artikuluan oinarrituta hirugarren enpresek beste hainbat inplementazio egin
dituzte. Horien artean Hadoop inplementazioa.
### Hadoop 
Apacheren Hadoop Javan idatzitako software ingurune bat da, eta aipatu bezala, Google-ren
MapReduce eta GFS-n (Google File System) artikuluetan oinarritutako inplementazio libre bat
da.
Tresna nagusia Hadoop Common da eta fitxategi-sistemarako atzipena ematen du. Onartzen
dituen fitxategi-sistemen artean, besteak beste, talde honek berak garatu duen HDFS (HaDoop
File System) dago.
Fitxategi-sistema honek 64 MB tamainako blokeak erabiltzen ditu eta fidagarritasuna datuak
errepikatuz lortzen du. Eta bide batez, RAID sistemen beharra alboratzen du. Besterik ezean 3
kopia gordetzen ditu, bi nodo berdinean eta 3. bat beste nodo batean.
Fitxategi-sistema honen gainean MapReduce motorra dago eta lanen kudeatzaile batean
oinarritzen da. Kudeatzaile honek exekuzioa atazen kudeatzaileetara bidaltzen du. Banaketa
honetan datuak eta exekuzioak ahalik eta hurbilen esleitzen saiatzen den, errendimendua
handiagoa izan dadin. Ezin badu exekuzioa datuak dauden nodoan egin, armairu berdineko
beste nodo batera esleitzen saiatzen da, sare trafikoa txikitu dadin.
Software honek egin duena, azken finean, Google-k bere artikuluetan idatzitako ideiak
inplementatzea izan da.

## Kritikak 
David DeWitt eta Michael Stonebraker-ek (datu-base eta arkitektura paraleloetan adituak)
paradigma hau aplika daitekeen arazo kopuruari buruz zalantzak adierazten dituzte.
Eskaintzen duen interfazea oso behe mailakoa dela adierazten dute eta zalantzan jartzen dute
benetan adierazten duten berrikuntza eskaintzen dutenik. Aipatzen dute orain dela 20 urtetatik
Teradata bezalako adibidetan antzeko estrategia inplementatu dela. Gainera ez ditu B-zuhaitzak
(B-tree) nahiz hash zatiketen abantailarik aprobetxatzen.

## Kanpo estekak