An elegant new algorithm developed by Danish researchers can significantly reduce the resource consumption of the world's computer servers. Computer servers are as taxing on the climate as global air traffic combined, thereby making the green transition in IT an urgent matter. The researchers, from the University of Copenhagen, expect major IT companies to deploy the algorithm immediately.
One of the flipsides of our runaway internet usage is its impact on climate due to the massive amount of electricity consumed by computer servers. Current CO2 emissions from data centers are as high as from global air traffic combined—with emissions expected to double within just a few years.
Only a handful of years have passed since Professor Mikkel Thorup was among a group of researchers behind an algorithm that addressed part of this problem by producing a groundbreaking recipe to streamline computer server workflows. Their work saved energy and resources. Tech giants including Vimeo and Google enthusiastically implemented the algorithm in their systems, with online video platform Vimeo reporting that the algorithm had reduced their bandwidth usage by a factor of eight.
Now, Thorup and two fellow UCPH researchers have perfected the already clever algorithm, making it possible to address a fundamental problem in computer systems—the fact that some servers become overloaded while other servers have capacity left—many times faster than today.
"We have found an algorithm that removes one of the major causes of overloaded servers once and for all. Our initial algorithm was a huge improvement over the way industry had been doing things, but this version is many times better and reduces resource usage to the greatest extent possible. Furthermore, it is free to use for all," says Professor Thorup of the University of Copenhagen's Department of Computer Science, who developed the algorithm alongside department colleagues Anders Aamand and Jakob Bæk Tejs Knudsen.
Soaring internet traffic
The algorithm addresses the problem of servers becoming overloaded as they receive more requests from clients than they have the capacity to handle. This happens as users pile in to watch a certain Vimeo video or Netflix film. As a result, systems often need to shift clients around many times to achieve a balanced distribution among servers.
The mathematical calculation required to achieve this balancing act is extraordinarily difficult as up to a billion servers can be involved in the system. And, it is ever-volatile as new clients and servers join and leave. This leads to congestion and server breakdowns, as well as resource consumption that influences the overall climate impact.
"As internet traffic soars explosively, the problem will continue to grow. Therefore, we need a scalable solution that doesn't depend on the number of servers involved. Our algorithm provides exactly such a solution," explains Thorup.
According to the American IT firm Cisco, internet traffic is projected to triple between 2017 and 2022. Next year, online videos will make up 82 percent of all internet traffic.
From 100 steps to 10
The new algorithm ensures that clients are distributed as evenly as possible among servers, by moving them around as little as possible, and by retrieving content as locally as possible.
For example, to ensure that client distribution among servers balances so that no server is more than 10% more burdened than others, the old algorithm might deal with an update by moving a client one hundred times. The new algorithm reduces this to 10 moves, even when there are billions of clients and servers in the system. Mathematically stated: If the balance is to be kept within a factor of 1+1/X, the improvement in the number of moves from X2 to X is generally impossible to improve upon.
As many large IT firms have already implemented Professor Thorup's original algorithm, he believes that industry will adopt the new one immediately—and that it may already be in use.
Studies have demonstrated that global data centers consume more than 400 terawatt-hours of electricity annually. This accounts for approximately two percent of the world's total greenhouse gas emissions and currently equals all emissions from global air traffic. Data center electricity consumption is expected to double by 2025.
According to the Danish Council on Climate Change, a single large data center consumes the equivalent of four percent of Denmark's total electricity consumption.
Mikkel Thorup is head of the BARC research center (Basic Algorithms Research Copenhagen) at the University of Copenhagen's Department of Computer Science. BARC has positioned Copenhagen as the world's fourth best place in basic research in the design and analysis of algorithms. BARC is funded by the VIILUM FOUNDATION.
Read Vimeo Engineering Blog about the implentation of Mikkel Thorup's algorithm: https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed
More information: Anders Aamand et al, Load balancing with dynamic set of balls and bins, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021). DOI: 10.1145/3406325.3451107
Provided by University of Copenhagen