Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

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.

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

Door Willem de Moor

Redacteur componenten

23-11-2008 • 11:40

54 Linkedin Google+

Reacties (54)

Wijzig sortering
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 :o. 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.
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 :9~ ?

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

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

Op dit item kan niet meer gereageerd worden.


Apple iPhone XS Red Dead Redemption 2 LG W7 Google Pixel 3 XL OnePlus 6T FIFA 19 Samsung Galaxy S10 Google Pixel 3

Tweakers vormt samen met Tweakers Elect, Hardware.Info, Autotrack, Nationale Vacaturebank en Intermediair de Persgroep Online Services B.V.
Alle rechten voorbehouden © 1998 - 2018 Hosting door True