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

Reacties

« 1 2 »

Door dutchcow, zondag 23 november 2008 11:45

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.

Door AdnanKananda, zondag 23 november 2008 11:48

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

Door riezebosch, maandag 24 november 2008 09:34

3 keer zo snel.

Door Joey_k, zondag 23 november 2008 11:49

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....

Door SH4D3H, zondag 23 november 2008 11:49

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.

Door martijnve, zondag 23 november 2008 11:50

"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)?

Door FuZi0n, zondag 23 november 2008 11:50

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.

Door Hensz, zondag 23 november 2008 18:22

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.

Door ETA, zondag 23 november 2008 19:07

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.

Door RemcoDelft, maandag 24 november 2008 10:47

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.

Door HoeZoWie, maandag 24 november 2008 10:23

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....

Door worldcitizen, zondag 23 november 2008 11:46

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.

Door GravGunner, zondag 23 november 2008 17:03

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

Door SiegeSapper, maandag 24 november 2008 13:27

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.

Door Grrmbl, zondag 23 november 2008 11:50

Door Blisterin_Bull, zondag 23 november 2008 11:53

Door Bazilfunk, zondag 23 november 2008 12:12

2 reacties volledig verborgen op huidige niveau

Door dasiro, zondag 23 november 2008 15:25

het concept blijft wel hetzelfde: je hebt hier geen blades of supercomputers, maar relatief simpele configuraties die heel snel te vervangen zijn in een volledig geautomatiseerd proces

Door humbug, zondag 23 november 2008 16:18

Ik zie eigenlijk geen reden om geen blades te pakken. Efficienter qua ruimte en makkelijker qua beheer en niet of nauwelijks duurder dan standaard 1U spul

Door Jareth, zondag 23 november 2008 11:53

1 reactie volledig verborgen op huidige niveau

Door Ad-, zondag 23 november 2008 12:02

Door Rauzi, zondag 23 november 2008 14:12

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.

Door A Lurker, zondag 23 november 2008 14:40

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 zondag 23 november 2008 20:07]

Door Ch3cker, zondag 23 november 2008 16:45

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.

Door Adion, zondag 23 november 2008 17:53

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.

Door DrClaw, zondag 23 november 2008 19: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!

Door Grrmbl, zondag 23 november 2008 15:01

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 zondag 23 november 2008 15:04]

Door PrisonerOfPain, zondag 23 november 2008 22:05

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 zondag 23 november 2008 22:06]

Door OMX2000, maandag 24 november 2008 00:24

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

Door Munters, maandag 24 november 2008 11:51

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

Door daboemann, zondag 23 november 2008 12:14

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!

Door Ortep, zondag 23 november 2008 12:19

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

Door Dykam, zondag 23 november 2008 14:14

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.

Door Dizzy Grizzly, zondag 23 november 2008 12:27

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 zondag 23 november 2008 13:00]

Door flubug, zondag 23 november 2008 12:34

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.

Door Dizzy Grizzly, zondag 23 november 2008 12:59

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 zondag 23 november 2008 13:02]

Door FreshMaker, zondag 23 november 2008 12:39

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

Door BeF-Bacchus, zondag 23 november 2008 13:19

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.

Door beschuit, zondag 23 november 2008 12:39

Door Fiander, zondag 23 november 2008 12:44

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 zondag 23 november 2008 12:49]

Door BTU_Natas, zondag 23 november 2008 13:37

« 1 2 »

Op dit item kan niet meer gereageerd worden.

12:17	Lerares met pornopopups tijdens les ontsnapt aan flinke celstraf
16:02	Google overweegt Chrome-browser op nieuwe pc's te installeren

Nieuws I/O

Shortcuts

Categorieën

Lees meer over

Gerelateerde content

Reacties

17:46 Nieuws

15:30 Productreviews

17:57 Vraag & Aanbod

23-05 Jobs

17:57 Etc.

17:59 Reacties

17:59 Forum

14:31 Gesponsorde acties

16:05 Tweakblogs

17:40 Computable headlines

13:29 CRN headlines