Googles Big Data-udviklingsafdeling kan ikke prale med at være indehavere af en officiel rekord i sortering af store datasæt, for resultaterne er ikke officielle. Men formentligt sidder Google på den uofficielle rekord i sortering af data i petabyte-klassen.
Det skriver Google-udvikler Marian Dvorsky i et blogindlæg om, hvordan Google eksperimenterede med værktøjet MapReduce til sortering.
Big Data-holdet, som havde udviklet Googles MapReduce-værktøj, havde adgang til at prøvekøre nye klynger i Googles datacentre, inden de blev sat i drift, og en måde at teste systemerne på var sortering.
Da Googles implementering af reduce-metoden i MapReduce sorterer data leksikografisk, kunne MapReduce bruges til sortering af meget store datasæt. I den størrelsesorden, Google opererede i, var benchmarken GraySort, som kræver en sortering af mindst 100 terabyte data, hvor hver post er 100 byte.
Google sorterede i de første forsøg ti gange så meget, altså én petabyte. I 2007 kunne en Google-klynge sortere én petabyte på 12 timer. I 2011 tog det blot en halv time.
En del af forbedringerne kom fra erfaringer med at optimere delprocesserne, og i 2012 kørte Google den hidtil største sorteringstest med 50 petabyte, der blev sorteret på 23 timer.
De store sorteringstests var imidlertid ikke bare en måde at teste datacenterklyngerne på. De gav også Google erfaringer med MapReduce, som var medvirkende til, at Googles Big Data-folk gik væk fra det første værktøj og i stedet udviklede nye værktøjer.
Et af problemerne ved MapReduce var, at der skulle bruges rigtig mange kræfter på finjustering af systemerne. Den proces var manuel med MapReduce, og derfor byggede Google-udviklerne mere automatisk optimering ind i efterfølgeren Dataflow.
Nå ja, og så fandt Google også ud af, at der simpelthen ikke eksisterer nogen realistiske scenarier, hvor der er brug for at kunne sortere 50 petabyte.
Bare rolig, Søren Pind har en plan...
Der blev sagt realistisk. Ikke at det er urealistisk, at Pind får sin vilje, men det er urealistisk, at det indsamlede data faktisk bliver brugt til noget.
Uden basal baggrundsviden er denne nyhed svær at forstå.
Hvis man ikke ved hvordan sorteringsalgoritmer skalere, ligner dette en nyhed om at man fra 2011 til 2012 optimerede en sortering med 8%, hvor der i samme periode kom ca. 66% mere regnekraft til, ifølge Moors lov.
Det havde været pænt at nævne at søgning skalere med n^2 og ikke linært i artiklen. (eller gjorde, i 90'erne da jeg lærte om quick- og bubble-sort algoritmer)
Man må næsten antage at de bruger en variation af merge sort, som skalerer i O(n lg n) da denne variant både er "stable" og passer ganske godt i MapReduce-frameworket.
Hvordan du får en forbedring fra 720 minutter til 30 minutter til kun at være en forbedring på 8% må jeg være dig svar skyldig :-)
Forbedringen på 8% er jo ikke fra 2007 til 2011, men fra 2011 til 2012...
Men det giver vel bare et hint om, at tidsforbruget ikke skalerer lineært med datamængden. Når der er tale om så store datamængder, så er der andre ting end antallet af transistorer, som eks. infrastrukturen der kan have en begrænsende effekt.
Husk at nærlæse detaljerne, i stedet for forhastede konklusioner.
Testen i 2011 var efter omhyggelig tuning af setup, hvor 2012 blot var at gentage den på ny cluster, med 5 x data. Hvis de igen havde prøvet at presse citronen, må det antages at forskellen havde været betydeligt større.
Hvad tal angår, var forskellen fra 2011 ("sølle" 1 PB og 10 PB) til 2012 (50 PB) snarere over 39% end blot de 19% som overskrifts-tallene kunne udlægges som. "Over" fordi det jo er naturligt at større datamængder giver lavere rate.
Hvordan regnede du forresten det ned til 8% ?
Jeg kommenterede udelukkende de informationer der var tilgængelige i artiklen her på V2, hvilket nok var en fejl :-) Og de 8% fremkommer ved at se på tidsforbruget pr. PB.
2011: 1PB pr. 30 min
2012 50PB pr. 23 t (= 1380 min) -> 1PB pr. 1380/50 = 27,6 min.
Forbedring i tid: 30 min - 27,6 min = 2,4 min
I procent: 2,4 min / 30 min. * 100 = 8 %.
Men den oprindelige artikel viser så at den halve time, var 0,55 time. Og at de 23 timer var 23 t og 5 min. Og så er de 8% helt i hegnet...
Jamen, den udregning er ganske irrelevant når det ikke samme størrelsesorden data. Der er vel ikke nogen med IT viden som er i tvivl om at det ikke er lineært.
Det kunne selvfølgelig have haft en vis underholdningsværdi om Google havde brugt kræfter på at deltage i sortbenchmark.org (GraySort), i stedet for at putte med tallene om at de i 2012 havde interne tal langt bedre end 2015-føreren her - "langt bedre" ikke blot halv tid, men på grund af 500x større dataset.
Det er så her jeg tænker et lille startup med at købe raspberry pis ind. Smide en Tor proxy på og et WiFi netkort så alt routes igennem Tor. Eller via en af de gratis vpn løsninger der er.
Store muligheder anes i horisonten, men teksten lidt for teknisk for en nOOb. Forklar, forklar...
På det ikke-tekniske plan, handler det om at Google morer sig med at teste nye datacentre ved gøre ting som at sortere meget store datamængder. De 50 petabyte svarer cirka til hvad der kan være på 11 millioner DVD skiver, med en spilletid på ca. 2500 år (døgnet rundt). Eller 100.000 almindelige harddisk på 500 GB. Det klarede de tilbage i 2012 på 23 timer (det er meget hurtigt), hvorefter de gik i gang med at lave en bedre måde at styre sådanne voldsomt store processer.
De markerer jo så også at der næppe er realistiske scenarier med nytteværdi af en så stor sortering. Men de skal jo have noget til at sikre sig at udstyret fungerer, og styringen er god.
Sådan et cluster (med nogle tusinde computere), der kan klare den opgave, har de mange af pr. datacenter, som de igen har mange af. Lidt inddirekte blærer de sig med hvor stor kapacitet de har på deres maskiner, som i dagligdagen bruger kræfterne på Google søgemaskinen, YouTube, Gmail, Android og mange andre ting som Google har på programmet.