Skriv ut inlägget
Googles viktiga Map Reduce algoritm, grunden till Googles sökfunktion
February 24th, 2008
En lektion om bl.a. Googles Map Reduce algoritm.
Google har byggt upp ett stort antal datacentra världen över med tiotusentals billiga Linuxdatorer i ett “moln” Google Cloud som erbjuder gratisapplikationer som GMail och Blogger.
Det är för att göra det enkelt att skapa applikationer som accessar alla dessa datorer so man har lagt ett abstraktionslager ovanpå och det är alltså det som är Google File System, ett distribuerat filsystem. Dvs det kan inte bara hantera data på en disk utan på tiotusentals sammankopplade datorer som om de vore en enda gigantisk disk.
För att sedan kunna köra sök på Google File System över så många datorer så måste man använda avancerade distribuerade algoritmer och det är alltså det som Map Reduce handlar om: hur man snabbt och effektivt kan söka efter t.ex. hur många gånger ett visst URL har besökts.
Man måste kunna söka igenom gigantiska datamängder - över 100 terabytes - som är distribuerade på tiotusentals olika datorer och göra det på någon sekund.
Här är en mycket bra presentation från Google: MapReduce:
Simplified Data Processing on Large Clusters
Map Reduce består av två funktioner, Map och Reduce som ursprungligen kommer från funktionella språk som Lisp.
Om vi t.e.x. vill räkna hur många träffar ett visst URL har fått så börjar vi med map-funktionen för att gå igenom gigantiska dataloggar som ligger lagrade på Googles datorer och räknar alla förekomster av det eller de URL vi letar efter. Resultatet blir en lång rad med URL, alltså en vektor i formatet <url ,1 >, <url,1 >, <url ,1>, <url, 1 > osv.
Sedan lämnad man över den här vektorn, som kan bestå av mycket stora datamängder till reduce-funktionen som i sin tur räknar samman alla elementen på listan och spottar ut följande resultat, ett enda s.k. key value pair: <URL, total count :gt;.
Som t.ex. <www.usablogg.org, 72 777 000 000>, vilket skulle betyda att min blogg skulle ha fått en himla massa träffar.
Google Filsystem GFS, dess Map Reduce algoritm och dess stora “datormoln” är inte svÃ¥ra att förstÃ¥ pÃ¥ en hög nivÃ¥ och hjälper oss att fÃ¥ en inblick i hur Google och Internet verkligen fungerar under kylaren s.a.s.
Det finns en Öppen Kodimplementation av Map Reduce i Java Hadoop och den som vill kan ladda ner den och börja leka med den här mycket viktiga algoritmen.
En mycket intressant teknologi som alla som är Intresserade av Webben och IT lätt kan lära sig.
Technorati Tags: Silicon Valley, IT, Datorer, Datavetenskap, Dataföretag, Hårdvara, Mjukvara, Programmering, Web 2.0, Mashups, Media, Facebook, Google
Svenska bloggar om: Silicon Valley, IT, Datorer, Datavetenskap, Dataföretag, Hårdvara, Mjukvara, Programmering, Web 2.0, Mashups, Media, Facebook, Google
Läs fler inlägg om Google
Prisjämförelser 
Prenumerera på bloggen
Lämna gärna en kommentar! Scandinavian-language comments only please!