Google sorteert 1TB ruwe data in 68 seconden met eigen technologie

Google heeft een nieuw record neergezet in het sorteren van gegevens: de Mapreduce-software van de zoekgigant slaagde erin 1TB aan gegevens, verdeeld over tien miljoen bestanden, binnen 68 seconden te sorteren.

De Mapreduce-software van Google wordt onder meer door het bedrijf gebruikt om datasets te ordenen en zo gegevens van gespiderde webpagina's en zoekopdrachten in kaart te brengen. Aangezien de zoekrobots van Google enorme hoeveelheden data aandragen, is het efficiënt verwerken hiervan noodzakelijk: dagelijks ordent de Mapreduce-software 20 petabyte aan gegevens. Het record dat Google neerzette, verbeterde de vorige toptijd van 209 seconden die de 910 computers van Yahoo nodig hadden om de gegevens met Hadoop te sorteren. Google benutte de rekencapaciteit van duizend computers om zijn resultaten neer te zetten.

Welke pc-configuraties Google gebruikte, maakte het bedrijf nog niet bekend, maar de Mapreduce-software en het bestandssysteem Google File System draaien normaliter op huis-tuin-en-keuken-pc's. Op de officiële Sort Benchmark-site zijn de resultaten van Google echter nog niet terug te vinden, waardoor de specificaties van de pc's nog niet bekend zijn. Wel is bekend dat Mapreduce in 2004 op clusters bestaande uit pc's met twee 2GHz-Xeons met 4GB geheugen en gigabit-ethernetverbindingen draaide, maar in hoeverre die configuratie veranderd is, is onbekend.

Om het sorteeralgoritme van Mapreduce wat meer werk te verschaffen, zetten de softwareontwikkelaars van Google vierduizend computers aan het werk, ditmaal met duizend maal zoveel data: 1PB moest in zo weinig mogelijk tijd geordend worden. De vierduizend pc's schreven hun data in drievoud weg naar 48.000 harde schijven. De gegevens in de 10 biljoen ongecomprimeerde tekstbestanden van 100 bytes werden door het cluster in zes uur en twee minuten gesorteerd. Een van de factoren die aan de rappe verwerking van de gegevens bijdroeg, was de manier waarop werd omgegaan met achterblijvende processen: deze zogenaamde 'stragglers' vertragen het sorteerproces.

Reacties (54)

De schaalbaarheid is wel enorm.

1TB in 68 seconden met 1000 computers.
1PB in 6 uur en 2 minuten met 4000 computers

Aangezien de TB/PB termen gebruikt worden inplaats van TiB/PiB, ga ik in mijn berekeningen uit van factor 1000.

1000 * 68 sec = 68000 sec = 18 uur, 53 minuten en 20 seconden om 1PB met 1000 computers te doen.

Het was echter met 4000 computers gedaan, wat met ideale schaling op 4 uur, 43 minuten en 20 seconden uitkomt. Er is dus maar een vertraging van 28% bij het opschalen, dat is een stuk beter dan bijvoorbeeld met SLi wordt behaald, en in dit geval is de verbinding tussen alle computers waarschijnlijk nog steeds 1GbE, waardoor het helemaal imposant is.

Tevens sorteerd Google dus 20PB aan data elke dag.

20x 6h2m = 5 dagen en 40 minuten.

Dus als ze dat elke dag willen doen en laten we er van uitgaan dat ze dat in de volle 24 uur willen doen, dan kom je uit op:

5 dagen en 40 minuten = 7240 minuten = 120,67 uur = 5,028x aantal computers nodig

Er is echter 28% schaalverlies, dus 5,028 * 1,28 = 6,436 aantal computers nodig.

4000 computers gebruikt voor 1PB * 6,436 = 25.743 computers nodig om de 20PB per dag te sorteren.

Het schaalverlies zal echter meer zijn, omdat het nerwerkverkeer wat nodig is, een nog grotere druk zet op de resultaten. Dus er zijn dan grofweg 30.000 computers nodig om de 20PB in 24 uur te sorteren.

Mooie score . Misschien zou zo iets ook niet verkeerd zijn (in natuurlijk een aangepaste vorm) om hardeschijven te defragmenteren. Want dat is ook het 'ordenen van losse bestanden'. Nu doet een pc er best lang over om pc's de defragmenteren.

Moet google wel hun algoritme vrij willen geven of zelf met zo'n programma komen, ik zou het in elk geval niet erg vinden!

Mooie score . Misschien zou zo iets ook niet verkeerd zijn (in natuurlijk een aangepaste vorm) om hardeschijven te defragmenteren. Want dat is ook het 'ordenen van losse bestanden'. Nu doet een pc er best lang over om pc's de defragmenteren.

Dat is niet afhankelijk van sorteren, maar van mechanica. Je kan misschien in 2 seconden uitrekenen waar de files moeten staan. Maar daarmee staan ze er nog niet. Dat zal je moeten doen door de schijf te laten draaien en de koppen te bewegen.

Ik kan ook bedenken dat ik graag in dat Thaise Restaurant in Bangkok wil eten. Dat kan ik in één seconde. Maar er heen gaan duurt al gauw 15 uur

Moet google wel hun algoritme vrij willen geven of zelf met zo'n programma komen, ik zou het in elk geval niet erg vinden!

Dit staat geloof ik gedeeltelijk beschreven in de MapReduce-Papers. Zeer interessant om te lezen.

Hier staan ook nog wat meer gegevens van Benchmarks, laatste slides.

//1Gb/s ethernet komt neer op dik 100MB/s
Dus lukt dit nooit met huis tuin keuken rommel omdat je niet met 1 comp t netwerk benut

Hier een gigabit netwerkje liggen. Via een Switch

PC 1: C2D E4400 op een Gigabyte GA-EP45-DS3R. Voor test gebruikte hdd: WD500AAKS. Windows Vista

PC 2: C2D E2160. GigabyteGA-G33M-S2H. Voor test gebruikte hdd: WD10001FALS. Windows Home Server. In theorie is de 1001FALS mijn snelste HDD

Maximale doorvoersnelheid Gbit Lan: 125MB/s. ik denk dat als je de boel perfect geconfigureerd hebt, een doorvoer van rond de 110~115MB/s uit moet kunnen komen.

Gemiddelde doorvoer snelheid file copy 2GB bestand van PC1 naar PC2 is ~75MB/s

Als ik dan op PC1 een ramdisk maak en diezelfde file vanaf PC2 (de 1001FALS) naar ramdisk copieer, dan zit ie tegen de 85MB/s (sustained) met een (vrij lange) piek van 89MB/s. ik heb met NETIO de theoretische snelheid gemeten, dan zit ik tegen de 95MB/s en dan heb ik de boel nog niet eens zo heel erg geoptimaliseerd.

Laatst tegelijkertijd bestanden van pc1 naar pc2 en weer terug, een maximale doorvoersnelheid van 102MB/s gehaald.

Dir is dus met maar 1 normale HDD. ik denk dat het met SSD's best mogelijk is om boven die 100MB/s te komen zonder gebruik te maken van RAID.

Ik heb één tip voor je: zet al die indexing, restore en andere meuk eens uit op je pc's. Doet wonderen voor je doorvoersnelheden.

[Reactie gewijzigd door Martin-S op 23 november 2008 15:17]

Dit record met Yahoo te vergelijken is net alsof appels met peren te vergelijken. Er zijn geen details waar de snelheid vandaan komt. Er wordt gesuggereerd dat gewone "huis-tuin-en-keuken-pc's" gebruikt zijn maar dan lijkt mij niet mogenlijk als we alleen al naar de lees snelheid kijken. De IO (=Input\Output) van 1 TB en het weer gesorteerd weg schrijven van de gesorteerde data in 68 seconden over bijna duizend PC's is wel erg snel. Dat moet een gemiddelde leessnelheid van rond de 15MB per seconde betekenen per PC. Onbekent is de groote van de output, wellicht is die minder daar met "pointers" en "indexes" en niet alle data zelf wordt weggeschreven. Die schrijf snelheid moet je dus boven die 15MBps leessnelheid optellen. Wie kan mij vertellen welke "gewone huis-tuin-en-keuken-pc's" die IO snelheden hebben? Verder is IO op "gewone huis-tuin-en-keuken-pc's" enorm CPU intensief en zou dus weer de sorteer capaciteit hinderen.

De onvolmaakte konkusie is dat het nog steeds zo kan zijn is dat Yahoo snellere algoritmes heeft maar minder snelle hardware. Verder is dus wel duidelijk dat zo gewoon die PC's dus niet kunnen zijn. En dat er blijkbaar een goede wellicht fysieke scheiding is tussen de IO en de sorteer algoritmes.

Toch wel interesant, betekent dit dat als alles wat ik op Google zoek binnen 68 seconden gesorteerd en gevonden heb ?

[Reactie gewijzigd door Dizzy Grizzly op 23 november 2008 13:00]

Hoe kom jij aan 15GB? 1 TB = 1000 GB, over 1000 pc's -> 1GB/PC

kpeis da je in je redenering alles op 1 PC wilt doen en dus een factor 1000 teveel hebt.

1TB data / 1000 PC's / 68 seconden = 15MBps.
Oops, rekenfoutje , Dank je voor de korrectie. Heb het al gekorigeert. Nog steeds heel snel hoor.
Ondanks de rekenfout ben ik nog steed van de konklusie dat je dit niet met Yahoo gelijken en dat dit blijkbaar geen gewone ordinaire PC's en configuratie is gebruikt.

[Reactie gewijzigd door Dizzy Grizzly op 23 november 2008 13:02]

Huis tuin en keuken search is wel binnen 60 seconden binnen

zoek maar een op de algemene zaken -
wereldtijden
auto / spec's

maar de meer 'speciale' searches worden redelijk vlot aangeboden, alleen zijn "onze" wensen vaak hoger gegrepen

en ondanks google's algoritmes kan wispelturigheid niet zo goed voorspeld worden

Consumenten PC's zijn rap zat voor deze getallen: HD's doen tegen de 100MB/s (ok, seq.), DC DDR RAM rond de 10GB/s, 1Gb/s ethernet komt neer op dik 100MB/s. Sinds de uitvinding van DMA een jaar of vijftien geleden heb je geen (naja, nauwelijks) processor meer nodig voor de IO-taken.

Dé bottlenecks van dit soort systemen lijken me de taakverdeling over de deelsystemen en de netwerktopologie. M.a.w.: Je wil data niet vaker dan nodig is van systeem laten verhuizen.

910 vs. duizenden, dan doet Yahoo! het ddus relatief sneller omdat ze minder computers gebruikten? Google heeft natuurlijk ook erg veel colo's in datacenters over de wereld. Maar wel weer leuk om te weten dat ze er een dikke minuut per tb over doen. Ben benieuwd waneer het in 10 seconden kan. Zal straks als alles SSD is mogelijk worden.

SSD's gaan voorlopig niet helpen.
Bij de 1 PB-test wordt er per HD 2,8 MB data per seconde weggeschreven. Dit tempo houdt een HD van 10 jaar oud zelfs nog bij. Een moderne HD gaat op z'n sloffen 10 keer zo snel en zal dus geen vertragende factor vormen. Zo'n HD vervangen door iets snellers heeft dan ook geen zin.

Het routeren van 3 x 46 GB/sec lijkt me een lastiger klus.

Je gaat wel een hele hoop winnen op de access times van bijna 0.
bestanden van 100 bytes inlezen is op een disk van 10 jaar oud, niet traag, maar de seektime zal hoger zijn dan de readtime.

Gezien de hierboven genoemde 2.8 MB/s zal de seektime niet zo'n probleem zijn, dat zijn namelijk 28000 files per seconde. Grote kans dat ze netjes op volgorde op de disk staan, of een andere methode gebruiken om niet per file de kop te laten bewegen.

Er staat 'duizend' en niet 'duizenden'. Het verschil is dus slechts 90 computers, terwijl Google het wel 2 keer zo snel doet.

3 keer zo snel.

Lezen:

Het record dat Google neerzette, verbeterde de vorige toptijd van 209 seconden die de 910 computers van Yahoo nodig hadden om de gegevens met Hadoop te sorteren. Google benutte de rekencapaciteit van duizend computers om zijn resultaten neer te zetten.

Dus "slechts" 90 computers meer... Waar jij naar doelt betreft het proces om 1PB te ordenen....

Het record dat Google neerzette, verbeterde de vorige toptijd van 209 seconden die de 910 computers van Yahoo nodig hadden om de gegevens met Hadoop te sorteren. Google benutte de rekencapaciteit van duizend computers om zijn resultaten neer te zetten.

"Google benutte de rekencapaciteit van duizend computers om zijn resultaten neer te zetten."

Dat is dus maar een erg klein verschil.
Verder die ik de significantie van dit bericht niet erg zonder dat er meer details bekend zijn, over wat er gesorteerd is, hoe het gesorteerd is en waarmee (wat voor machines dus)?

In het bericht staat 'duizend', niet 'duizenden', dus maar 90 meer. Dan valt het reuze mee, of is het zelfs niet zo, dat Yahoo het relatief sneller doet lijkt me.

Lezen wat er staat:

Het record dat Google neerzette

Niet "dat doet Yahoo", maar "dat doet Google", het record is van Google, dus Yahoo is daar nog nooit boven uit gekomen....

Wel is bekend dat Mapreduce in 2004 op clusters bestaande uit pc's met twee 2GHz-Xeons met 4GB geheugen en gigabit-ethernetverbindingen draaide, maar in hoeverre die configuratie veranderd is, is onbekend.

Ik verwacht dat deze flink veranderd is. De Xeons in 2004 waren netburst versies. Ik kan me niet voorstellen dat ze die anno 2008 nog gebruiken.

Een systeem wordt meestal in 3 of 4 jaar afgeschreven.

een desktop computer ja, maar een server gaat soms wel veel langer mee.
Zeker als de bak voldoende is om mee te komen.

En 'ff' een paar duizend servers vervangen omdat ze ietwat oud worden doe je ook niet zomaar, dus grote kans dat er nog bulken met deze machines draaien

Google staat bekend om servers te ontwerpen die goedkoop te maken zijn, en daardoor relatief simpel te vervangen. Dus het logisch dat ze desktop modellen of instap server modellen gebruiken.

Hoe kom jij aan die 15GB ?
1TB data, 1000PC's, is 1GB per pc wat gelezen moet worden,
vervolgens moet van deze GB bepaald worden naar welke node de data moet.
statisties zal 1/1000 op de pc zelf blijven, en zal de pc 999 MB van andere pc's ontvangen om zelf te sorteren.

uiteindelijk zal node 1 de data AAA tm AAB bevatten, node 2 AAC tm AAD enz.
deze data word daarna lokaal nog gesorteerd.

edit : was eigenlijks reactie op Dizzy Grizzly hierboven.

[Reactie gewijzigd door Fiander op 23 november 2008 12:49]

Een van de factoren die aan de rappe verwerking van de gegevens bijdroeg, was de manier waarop werd omgegaan met achterblijvende processen: deze zogenaamde 'stragglers' vertragen het sorteerproces.

en toen? hoe werd er mee omgegaan dan?

wat betekent sorteren?
AUB niet de van dale definitie erbij halen, maar de technische betekenis...

Zou zeggen alfabetisch en gecategoriseerd de bestanden in een index verwerken.
Wat het nut is, je zet het eenmalig met een relatief langdurig proces op een bepaalde volgorde en een bepaalde categorisering, en daarna hoeft het proces om iets te vinden en te benaderen niet zo lang meer te duren als zonder de sortering.

Ik snap het artikel niet zo erg. Hebben ze nou een superieur sorteeralgoritme verzonnen of zitten ze nou gewoon te patsen dat ze zoveel machines hebben die zoveel data kunnen sorteren? Het laatste interesseert niemand volgens mij.

Bij een wereldrecord hardlopen maakt het toch ook niet uit of het door je goeie techniek of door je enorme kracht komt?

Maar goed, is zit weldegelijk een slim(mer) algoritme achter:

Een van de factoren die aan de rappe verwerking van de gegevens bijdroeg, was de manier waarop werd omgegaan met achterblijvende processen: deze zogenaamde 'stragglers' vertragen het sorteerproces.

Alhoewel ik niet helemaal snap hoe uberhaupt die stragglers ontstaan.

Sowieso is het interessant (imo) om verbeteringen te zien op dit soort supercomputing gebieden. Je kunt namelijk niet zomaar alle data over 1000 computers verdelen, sorteren, en bij elkaar stoppen. Dat bij elkaar stoppen is namelijk ook weer een klus op zich en gezien het feit dat ze die 1TB data niet op 1 schijf stoppen lijkt me dat vrij ingewikkeld.

Afgezien van de gedecentraliseerde opslag hebben ze effectief dus gewoon een algoritme gemaakt wat met 1000 (of meer) threads werkt. Dat op zich is niet zo moelijk, om het snel te doen wel.

Edit: reactie op Ch3cker hier beneden: waar lees jij dat ik het niet interessant vind? Of reageer je misschien op Rauzi? De toekomst ligt in threaded applicaties, immers moeten quadcores toch ooit eens flink aan het werk gezet kunnen worden.

[Reactie gewijzigd door A Lurker op 23 november 2008 20:07]

naja, ik denk dat het om een soort verdeel- en heers algoritme gaat.

Stel, je wilt een array van lengte X sorteren.. dan kun je dat door 1 computer laten doen, met het snelste algoritme dat je kent.

maar je kunt het array ook in 2en breken, dat door 2 computers laten sorteren (ieder zn eigen stukje), en aan het eind de 2 arrays weer mergen.

Nou kost het sorteren van een array een bepaalde tijd. Ze duiden die tijd aan met Big-O notatie .. bijvoorbeeld O( n log n). Dit betekent niet dat het precies n log n tijd kost, maar wel een lineaire factor daarvan.

Nu zie je het al aankomen; er zijn dan best cast scenario's waarbij een array sorteren heel snel gaat, en scenario's waar een array van dezelfde grootte heel traag gaat.

Die trage sorteerders zijn dan stragglers. En je kunt dat proberen te versnellen, door bijvoorbeeld zijn array nogmaals te delen, en dat dan te sorten en weer te mergen. Dat kost dan weer 2 extra computers om het te berekenen, plus de tijd dat je nodig had om erachter te komen dat er een straggler was.

De lol van zo'n dynamisch systeem is, dat ze ook zonder een homogeen cluster hun berekeningen kunnen doen.. ze kunnen zo trage en snelle computers tegelijkertijd gebruiken. De truuk zit m dan daarin om te bepalen welke computer dan werke hoeveelheid werk doet. En dat voorspellen is zeker geen gemakkelijke klus!

Kan me een zinnetje herrineren uit I robot :

"Ever since the first computers, there have always been ghosts in the machine. Random segments of code that have grouped together to form unexpected protocols."

Uhm, zeg je nou dat het niet interessant is dat er vooruitgang geboekt wordt op dit gebied?
Het is imo van groot belang dat hierop vooruitgang wordt geboekt, voor zeer veel doeleinden. Als er efficiënter gewerkt kan worden heeft dat voordelen voor de snelheid, de kosten van de computers (minder computers nodig), en het milieu.

Alhoewel ik niet helemaal snap hoe uberhaupt die stragglers ontstaan.

Ik vermoed dat niet elk stuk data al even gesorteerd is. Afhankelijk van het gebruikte algoritme zal de snelheid dus afhangen van hoe de data aangeleverd word, en zullen sommige computers dus sneller klaar zijn dan anderen.

Het laatste is vooral specificaties van hoe ze die resultaten hebben kunnen halen.
Je kan die 1TB in 68 seconden met 1 miljoen computers halen, of je kan die 1TB in 68 met 1000 (niet overgeklokte?) thuispc's halen.
Dan is het voor het totaalbeeld wel van belang hoe ze dat record resultaat hebben behaald, zeker als ze een ander record willen verbreken.

Ook apart is dat ook Hadoop wat Yahoo gebruikt, (nu ook?) Mapreduce gebruikt:

Hadoop implements MapReduce, using the Hadoop Distributed File System (HDFS)

Maar wel met hun eigen FS.

[Reactie gewijzigd door Grrmbl op 23 november 2008 15:04]

Er is dan stiekem ook maar weinig speciaals aan MapReduce, het is simpelweg een abstractie van de standaard loop mechanisme. Hadoop gewoon een implementatie van die abstractie in Java.

Kort gezegd doen die loop algoritme niet veel anders als dit in een naive implementatie.

' map
for all e in l
f(e)

' reduce
for all e in l
s += e ' += operator can be overloaded
result in s

De truuk zit er in om een slimme implementatie te maken die de taken beter verdeeld over de beschikbare resources (verschillende CPUs of PCs) en dat is dan ook wat Google gedaan heeft. Ze hebben een betere MapReduce implementatie op de kaart gezet als Yahoo destijds, waarschijnlijk is dat deels aan Google File System toe te schrijven en deels aan de manier waarop het om gaat met de 'stragglers'.

[Reactie gewijzigd door PrisonerOfPain op 23 november 2008 22:06]

Vraag ik me af wat er gebeurd als ze een functionele taal zouden hebben gebruikt.

Dan was de data ook gesorteerd, alleen duurde het dan langer.