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:

MapReduce algoritmoaren exekuzioa

1. MapReduce funtzioak sarrerako fitxategiak M zatitan banatzen ditu, orokorrean 16 megabytetatik 64 megabytetarainoko zatitan. Orduan, hainbat exekuzio hasten dira clusterrean zehar banatutako makinetan.
2. Kopietako bat berezia da, nagusia. Bestelako guztien nagusiak esleitutako lana exekutatuko dute. M Map ataza eta R Reduce ataza daude.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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

• Datuak: Q567759
• Multimedia: MapReduce / Q567759