En algoritme beskrevet i en videnskabelig grundforskningsartikel er blevet implementeret i en lang række af verdens store serverparker og har resulteret i en meget stor reduktion af ressourceforbruget. Et godt eksempel på, at når grundforskning møder industrien, kan digitale løsninger bidrage direkte til den grønne omstilling.
Grøn omstilling er formentlig ikke det første, man ville tænke på, hvis man faldt over en videnskabelig artikel med titlen ”Consistent Hashing with Bounded Loads”. Men rent faktisk har den algoritme, som Mikkel Thorup, professor på Datalogisk Institut, Københavns Universitet, sammen med to medforfattere har beskrevet i artiklen, fået en markant effekt på den grønne omstilling inden for it-verdenen. Giganter som Google, videoplatformen Vimeo og talrige andre virksomheder har nemlig valgt at implementere algoritmen og har derved opnået en voldsom reduktion i ressourceforbruget på deres servere.
Retfærdig load balancing
”Rigtig meget af det, vi laver i teoretisk datalogi, er at prøve at få en matematisk forståelse for, hvordan man mest effektivt kan løse kombinatoriske problemstillinger, som er inspirerede af situationer, der ikke blot forekommer ét sted, men rigtig mange steder,” forklarer Mikkel Thorup.
Problemstillingen, som løses af algoritmen, er helt renset for det, Mikkel Thorup kalder ”konkret støj” og kan måske bedst beskrives i billeder.
”Vi har begrænsede ressourcer af en eller anden slags. Det kunne for eksempel være flyttekasser, vi skal have fyldt med alle de ting, der skal flyttes. Her skal vi både sikre, at ingen af kasserne bliver overfyldt, og at vi er i stand til at finde tingene igen, når vi undervejs bliver nødt til at fordele dem i flere forskellige kasser. Implementeret i en serverpark betyder vores algoritme, at en enkelt server højst kan blive belastet med eksempelvis 10 procent mere end de øvrige servere. Dermed sikrer man sig mod, at enkelte servere bliver overloadet og dermed ikke længere kan levere de services, der kører på dem,” forklarer Mikkel Thorup, der tilføjer, at der findes systemer, der kan noget lignende, men at løsningen beskrevet i artiklen var banebrydende ved at introducere begrænsningen i balanceringen af loadet.
”Vi lukker automatisk lågene på flyttekasser, der er ved at blive overfyldte. Dermed har vi introduceret en retfærdig load balancing mellem serverne,” siger han.
Løste Vimeos problem
Ressourceforbruget i denne verdens store serverparker er i sig selv en belastning for miljøet, men samtidig kan digitale løsninger, der bor i disse serverparker, være med til at understøtte en grøn omstilling. Og eksemplet med Mikkel Thorup og co.’s algoritme viser, at det ikke kun er forskningsprojekter specifikt rettet mod løsninger til at understøtte den grønne omstilling, der kan levere varen. Der er også meget at hente i grundforskningen, hvis de rette folk og virksomheder ellers bliver opmærksomme på de muligheder, der ligger der.
Algoritmen kunne have levet et forholdsvis stille liv som et stykke grundforskning, men via et tweet fra Damian Gryski, softwareudvikler hos Fastly i San Francisco, blev Andrew Rodland, Principal Engineer hos Vimeo, opmærksom på, at her lå løsningen på et problem, den store videoplatform havde kæmpet med længe.
Når Vimeo, der har omkring 1,4 mio. abonnenter, streamer videoer til brugerne, bliver de ikke leveret i én stor fil, men i segmenter, der bliver leveret on-the-fly, når en afspiller-applikation sender et request. Et indeks holder styr på, hvor de enkelte segmenter befinder sig, og for at spare HTTP-requests og ikke mindst CPU-tid, cacher man et indeks over segmenterne i arbejdshukommelsen på cloud serveren. Da der løbende bliver fjernet og tilføjet servere i Vimeos serverpark, benytter man sig af såkaldt ”consistent hashing” (se Ordforklaring nedenfor) for at have styr på, hvor et request skal styres hen for at finde indekset til en specifik video. Det viste sig dog, at den consistent hashing, der blev benyttet af Vimeo, i flere tilfælde resulterede i server overloads, så brugerne fik hakkende videoer. Så ønsket, som formuleret af Andrew Rodland i blogindlægget ”Improving load balancing with a new consistent-hashing algorithm” lød ganske enkelt: “Use consistent hashing, but please don’t overload any servers”.
Open source
Da han trykkede på linket til artiklen i Damian Gryskis tweet, stod det klart, at her var løsningen. Algoritmen blev implementeret på Vimeos systemer, og resultatet var en dramatisk stigning i antal requests, der kunne håndteres af cachen frem at blive hentet remote. Og jo mere, der kan hentes i cachen, jo flere ressourcer sparer man, forklarer Mikkel Thorup:
”Det er ligesom forholdet mellem egne grøntsager og grøntsager, der skal importeres fra udlandet. Det er stort set gratis at hente de lokale grøntsager, mens det koster mange ressourcer og dermed energi at hente dem i fjerntliggende egne af verden. ”
Vimeo lagde løsningen ud som open source, og kendskabet til den blev spredt vidt omkring med afsæt i Andrew Rodlands blogindlæg og et blogindlæg på Googles AI-blog.
”Vi er rigtig glade for, at de blogindlæg blev skrevet, og i virkeligheden er situationen helt unik, da jeg meget sjældent får noget at vide om, hvem der anvender mit arbejde i praksis, da det bliver betragtet som forretningshemmeligheder. I dette tilfælde var det jo så rigtig vigtigt, at det var et universitet, der leverede løsningen, da den så ikke kunne patenteres og dermed reelt forhindre andre i at bruge den,” siger Mikkel Thorup.
Vidensoverdragelse
Selvom det i det konkrete tilfælde forekommer ret tilfældigt, at en forskningsartikel kan føre til en konkret implementering i industrien, mener Mikkel Thorup ikke, at det nødvendigvis behøver at være tilfældet, der råder.
”Der er faktisk mange, selvfølgelig primært i de store virksomheder, der interesserer sig for, hvad der sker inden for grundforskningen. De store virksomheder har typisk de største udfordringer, eksempelvis med skalering, og når de får løst deres problemer, vil en del af dem som for eksempel Google lægge det ud på offentligt tilgængelig arkiver, så løsningerne også kan anvendes af mindre virksomheder,” siger han og tilføjer, at han har en del følgere på forskellige platforme, hvilket også er med til at udbrede kendskabet til det arbejde, han er involveret i.
Det personlige netværk er også en vigtig faktor i udbredelsen af resultater fra grundforskningen. Således har Mikkel Thorup for nylig gennem en tidligere kollega hos den amerikanske telegigant AT&T erfaret, at en af hans andre algoritmer vil blive anvendt i network controllere til at optimere hastigheden i 5G-netværk over hele verdenen.
Ifølge Anders Pall Skött, der er chef for Erhverv og Innovation på Datalogisk Institut, Københavns Universitet, kan virksomheder få ny viden gennem konkret samarbejde med universiteterne, men vidensoverdragelsen kan også foregå, ved at virksomhederne sender udvalgte medarbejdere på nogle af de grundkurser, eksempelvis i data science og machine learning, der bliver udbudt af Københavns Universitet og andre uddannelsesinstitutioner.
”Målgruppen for disse kurser vil være avancerede domænespecifikke medarbejdere, eksempelvis en geograf, der arbejder med byplanlægning. Ved at deltage i kurserne opnår de en viden, der potentielt kan bringes i spil i deres egen virksomhed, eventuelt som en del af et samarbejde med studerende eller forskere,” siger han.
ORDFORKLARING
- Hashing: funktion, som konverterer et hvilket som helst input af enhver længde til en streng af fast længde.
- Consistent hashing: metode til at distribuere requests i en serverpark, hvor der løbende bliver fjernet og tilføjet servere.
REFERENCER
- Consistent Hashing with Bounded Loads, artikel af Vahab Mirrokni, Mikkel Thorup og Morteza Zadimoghaddam på arXiv.org.
- Improving load balancing with a new consistent-hashing algorithm, blogindlæg af Andrew Rodland, Principal Engineer hos Vimeo, på Vimeo Engineering Blog.
- Consistent Hashing with Bounded Loads, blogindlæg af Vahab Mirrok og Morteza Zadimoghaddam på Google AI Blog.
- Practical Load Balancing with Consistent Hashing, Google TechTalks' præsentation af Andrew Rodland på YouTube.