Jesper sandal header

Julemanden har brug for en hardcore database og parallel pakkelevering

Illustration: Jesper Stein Sandal

De fleste kender nok fysikudregningen, som konkluderer, at Julemandens slæde ville brænde op i atmosfæren, hvis Julemanden skulle nå at besøge alle artige børn på Jorden. Men hvad nu hvis Julemanden rykkede biksen til cyberspace?

Lad os antage, at Julemanden blot skal aflevere én pakke til hvert artigt barn. I værste fald - for Julemandens it-budget, ikke for forældrene - er alle Jordens børn artige i år. Men selv hvis de ikke var det, så ville Julemandens liste vise sig at være et problem.

Vi ser her helt bortset fra, hvordan Julemanden finder ud af, om et barn har været artigt. Der er nok af bekymring over overvågning fra Google, Facebook og PET.

Der er ifølge FN cirka 1,9 milliarder børn på Jorden i alderen 0-14 år. Lad os antage, at et barn har mulighed for at opføre sig så artigt helt frem til juleaften, at barnet kan nå at skifte fra 'uartig' til 'artig' på Julemandens liste helt frem til, at Julemanden leverer sine pakker.

Vi kan allerede her se, at Julemandens liste ville gøre det umuligt for ham at nå sin tjans uden hjælp fra computere. Hvis det blot tager ham ét sekund at se på sin liste, om et barn har været artigt eller ej, så vil det tage ham 60 år bare at tjekke sin liste. Og fra julesangen ved vi, at han tjekker den to gange.

Heftig hardware til undsætning!

En computer kan naturligvis gøre det hurtigere. En god database-server kan klare 10.000 transaktioner pr. sekund. Med den hastighed vil det imidlertid stadig tage 2 dage 4 timer 46 minutter og 40 sekunder at tjekke alle børn. Og dobbelt så lang tid, hvis han insisterer på at gøre det to gange.

Men lad os antage, at Julemanden kan optimere sin database, så længe han kun skal slå op, om et barn har været artigt eller ej. Med 100.000 opslag pr. sekund vil det tage 5 timer 16 minutter og 40 sekunder at slå alle børn op (tak til WolframAlpha for at gøre den slags udregninger hurtigere).

Han kan selvfølgelig også bruge større hardware. Jeg spurgte Oracle, som mente, at opgaven kunne løses på lidt over 22 minutter med en stor Oracle Exadata-maskine (hvorvidt Oracle rent faktisk er leverandør til Julemanden, har jeg ikke fået oplyst).

Mindre kunne nok også gøre det, hvis vi antager, at 1,9 milliarder artig-værdier kan ligge i én byte hver og et barn har et nummer, hvor 4 bytes burde være nok (til barnets IPv4-adresse), så burde det kunne ligge i 8,85 gigabyte RAM, hvis Julemanden er med på bølgen og bruger en in-memory-database.

Vi kan nok forvente, at Julemanden vil kunne finde en måde at dele problemet op, så han i stedet for én enkelt liste, deler listen op i bidder, som hans ArtigBase 2.0 kan slå op i parallelt og overkomme det værste tidsforbrug. Det er der sikkert databasearkitekter derude, som gerne vil hjælpe med i bytte for nogle større julegaver.

En pakke til alle børn

Vi antog, at alle børn var artige. Hvor lang tid tager det så en pakke at nå frem i cyberspace? Udregningen ser ikke godt ud for Julemanden. Igen bliver han nødt til at hyre nogle netværkskonsulenter og en datalog til at løse problemet.

I bedste fald tager det to millisekunder for en netværkspakke at nå frem til en modtager. Lad os antage, at alle 1,9 milliarder børn har en smartphone eller pc med internetadgang. Ja, det har de ikke, og alt for mange af dem har langt mere alvorlige bekymringer, end at de ikke kan har adgang til YouTube, men det er ikke Cyberjulemandens udfordring i denne omgang.

Hvis Julemanden kun leverer én pakke af gangen, vil det med to millisekunders leveringstid tage 43 dage 23 timer 33 minutter og 20 sekunder at levere alle pakkerne.

Det bliver ikke bedre, hvis vi ser på en mere realistisk svartid for Julemanden, hvis han sidder på én computer ét sted i verden. Med en svartid på 200 millisekunder i gennemsnit vil det tage Julemanden 12 år at sende alle pakker.

Send pakkerne i blinde

Her har vi forudsat, at Julemanden venter på, at pakken er leveret, før han sender den næste af sted. Sådan behøver han ikke gøre i praksis.

Julemanden har god brug for at se på sine algoritmer. Vi kan se, at det ikke nytter noget, hvis hans software ser nogenlunde sådan her ud i pseudokode (bær over med min håbløse spaghetti-notation):

  • 10: GET NAUGHTY_LIST
  • 20: kid = NAUGHTY_LIST.nextKid
  • 30: IF NAUGHY_LIST.check.once(kid) == "nice" AND NAUGHY_LIST.check.twice(kid) == "nice" GOTO 40 ELSE GOTO 20
  • 40: SEND PACKAGE(kid)
  • 50: IF PACKAGE.received GOTO 20

De to bedste løsninger er, at Julemanden enten blot sender pakkerne af sted så hurtigt som muligt, eller han deler afsendelsen ud på flere servere. Hvis han vælger den sidste løsning, så vil det nok være en god idé at alliere sig med en cloud-udbyder, så han ikke skal have et halvt hundrede eller flere servere stående, som ikke laver noget 364 dage om året.

I stedet for at vente på, at pakkerne modtages, kan han selvfølgelig blot sende pakkerne af sted og i første omgang ignorere, om de når frem eller ej og altså ikke behøve få svar tilbage.

Hvis vi antager, at han bruger en enkelt maskine med en 10 gigabit/s forbindelse og ser bort fra overhead, men til gengæld går ud fra, at alle børn vil have så stor en pakke som muligt, altså 65.535 bytes over IPv4, så vil den i bedste fald kunne sende 19.074 pakker af sted pr. sekund.

Det vil så i alt tage ham 1 dag 3 timer 40 minutter og 12 sekunder at sende alle pakker af sted.

Hvis Julemanden vælger den mere praktiske løsning og hyrer en cloud-udbyder med 100.000 servere til rådighed, så ville de med hver 10 gigabit/s teoretisk kunne klare opgaven på 0,99 sekunder, men det ville nok lægge en router eller 100 ned - eller mere sandsynligt betyde, at en stor del af pakkerne aldrig ville nå frem.

Et kompromis kunne derfor være at dele listen op i 100.000 bidder og lade hver af serverne sende én pakke af gangen og sikre sig, at alle pakkerne når frem. I stedet for 12 år fra det værste tilfælde oven for, vil opgaven kunne løses på bare 1 time 3 minutter og 20 sekunder.

Cookie-oversvømmelse

Skulle Julemanden flyve rundt, kravle gennem skorstene og spise småkager, så ville han nok tage en del på i løbet af sådan en juleaften, selvom det slet ikke ville modsvare den energi, han skulle bruge på fysisk pakkedistribution i nær-relativistisk hastighed.

I cyberspace kan Julemanden selvfølgelig også få småkager eller 'cookies', og her får Julemanden også brug for de digitale bukser med elastik.

En cookie må maksimalt fylde 4 kilobytes. Hvis alle børn giver Julemanden en stor cookie, vil han modtage 7,1 terabytes (jeg bruger rigtige terabytes, ikke marketing-terabytes, men jeg nægter at kalde dem for 'tebibytes').

Julemanden skal altså mindst bruge to store harddiske bare til at opbevare dette års cookies. Om han så spiser dem ved at slette dem, eller om de ender som foder for hans båndrobot, kan vi kun gisne om.

Cyberjulemanden kan altså godt nå sin gaveuddeling via internettet. I praksis skal han dog enten fordele uddelingen på flere servere, eller også skal han sprøjte pakkerne af sted så hurtigt som muligt og så krydse fingre for, at alle pakkerne når frem.

Alle ovenstående udregninger er foretaget med kuglepen på ternet papir, WolframAlpha og Wikipedia uden medregning af netværksoverhead, kollisioner eller andre tekniske småting. Der er tale om juleunderholdning, ikke en afhandling i databaser og netværk. Og ja, jeg læser også med stor fornøjelse de fjollede udregninger på xkcd.com's What-If-blog.

Kommentarer (12)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#3 Jesper Stein Sandal

Jeg tænkte, at det var dét, der havde størst chance for at slippe nogenlunde intakt gennem vores CMS. Indrykning i C++ stil var nok blevet noget rod.

Og den uskønne sammenblanding af forskellige syntakser er en del af det underholdende indslag. :)

  • 2
  • 0
#4 Hans Peter Haastrup-Nielsen

Jeg synes godt du kunne simplificere det lidt.. artig/uartig problemstillingen kan jo fint antages til at være en boolean, som så kun vil fylde 1 bit. Nu kommer det naturligvis an på arkitekturen og en masse vil med det samme sige at det slet ikke er muligt at lagre så lidt - derfor byten. Men alligevel, så kunne man pakke det sammen (igen må det antages at det så ikke tager ekstra tid). Til gengæld bliver størrelsen mindre.. ikke?

  • 0
  • 0
#6 Deleted User

Du regner frem til at det tager 27 timer at sende pakker til alle børn, såfremt du bruger en 10gbit maskine, men i realiteten burde det kun være nødvendigt at nå ned under 24 timer. Børnene skulle jo gerne have pakken mens de sover, og det gør de alligevel ikke samtidigt.

  • 0
  • 0
#8 Michael Rangård

:) det er vel meget heldigt for julemanden at julegaveræset er godt fordelt rundt omkring i verden. Dels så kan han udnytte at f.eks. kl 18.00 er godt fordelt ud over 24 timer, rundt på jorden og dels kan han udnytte at i fransk-sproget områder er det normalt at give julegaver d. 6. december, engelsksproget områder giver først d. 25. december og spansksproget områder ofte må vente helt til d. 6. januar :)

  • 2
  • 0
#11 Jakob Dahl

"Der er ifølge FN cirka 1,9 milliarder børn på Jorden i alderen 0-14 år. Lad os antage, at et barn har mulighed for at opføre sig så artigt helt frem til juleaften, at barnet kan nå at skifte fra 'uartig' til 'artig' på Julemandens liste helt frem til, at Julemanden leverer sine pakker."

Jojo, men chancen for at de gør det er jo bare ikke særlig stor. Med til alle udregninger hører også en samtidighed. Altså, det kan ikke betale sig at lave udregninger der tager udgangspunkt i at der skal afleveres pakker til mere end 19 mio. børn det samme år. /Jakob

  • 0
  • 0
#12 Jesper Stein Sandal

Jojo, men chancen for at de gør det er jo bare ikke særlig stor. Med til alle udregninger hører også en samtidighed. Altså, det kan ikke betale sig at lave udregninger der tager udgangspunkt i at der skal afleveres pakker til mere end 19 mio. børn det samme år.

Nu kender vi jo hverken til udgangspunktet (hvor mange børn er artige i år) eller til Julemandens definition på artighed. Jeg er også uenig i, at det ikke kan betale sig at regne på en worst case, hvor alle børn i løbet af juleaftensdag opfører sig så artigt, at de kommer på artig-listen. Da der netop er fokus på børns artighed op til jul, kan man antage, at flere børn vil opføre sig artigt, jo tættere på jul vi kommer.

Vi arbejder altså med ukendte sandsynligheder, og da der er tale om en udregning af den teoretiske mulighed for, hvorvidt Cyberjulemanden kan nå sin pakkeuddeling, er vi nødt til at regne på en absolut worst case for hans it-setup.

Før han går ud og investerer i sit setup, så skal han selvfølgelig finde frem til det reelle behov. Hvis der er nogen konsulenter, som har ham som kunde, så må I gerne spørge, om han har lyst til at fortælle om det til Version2. ;)

  • 1
  • 0
Log ind eller Opret konto for at kommentere