Foto: DIKU
Mikkel Thorup, professor ved Basic Algorithms Research Copenhagen (BARC) på Datalogisk Institut ved København Universitet, har sammen sammen med Anders Aamand og Jakob Bæk Tejs Knudsen skabt en ny algoritme, som kan gøre verdens computerservere mere klimavenlige ved at effektivisere deres arbejdsgange.
En af bagsiderne ved vores galopperende internetforbrug er den påvirkning, det har på klimaet i kraft af det massive elforbrug, som computerservere har. Serverne bliver ofte overbelastede, fordi de modtager flere anmodninger fra klienter, end de har kapacitet til. Det kan for eksempel være, når en bruger beder om at se en bestemt video på Vimeo eller film på Netflix. Computersystemerne har derfor brug for at flytte rundt på klienter mange gange for at opnå en balanceret fordeling mellem de forskellige servere.
Allerede for en håndfuld år siden skabte vi en algoritme, som gav en banebrydende opskrift til at effektivisere computerserveres arbejdsgange. Både Vimeo og Google har implementeret den i deres systemer, og ifølge Vimeo reducerede den forbruget af båndbredde med otte gange. Nu har vi lavet den perfekte udgave af den smarte algoritme, som gør den i stand til at løse et grundlæggende problem i computersystemer mange gange hurtigere end i dag – nemlig at nogle servere bliver overbelastede, mens andre har plads til overs.
Det er en skalérbar løsning, som ikke er afhængig af hvor mange servere, der er involveret. Algoritmen fjerner én gang for alle en af de store årsager til overbelastede servere, og den bruger så få ressourcer som overhovedet muligt. Det er et hundesvært matematisk regnestykke, da der kan være en milliard servere involveret i systemet, som ovenikøbet er omskifteligt, fordi nye klienter og servere hele tiden kommer og går. Den nye algoritme sørger for, at klienterne bliver fordelt så ligeligt som muligt mellem serverne ved at flytte rundt på klienter færrest gange muligt og hente indhold så lokalt som muligt.
Hvis man for eksempel gerne vil sikre, at ingen af serverne er over 10 procent mere belastet end andre, kunne den gamle algoritme klare en opdatering ved at flytte en klient 100 gange. Den nye er nede på 10 flytninger, selv hvis der er milliarder af klienter og servere i systemet. Sagt i et mere matematisk sprog: Hvis balancen skal overholdes inden for en faktor 1+1/X, er forbedringen i antal flytninger fra X2 til X, hvilket generelt er umuligt at gøre bedre.
