Boffins say they've improved on algorithm for dynamic load balancing of server workloads
- Reference: 1625667304
- News link: https://www.theregister.co.uk/2021/07/07/dynamic_load_balancing_algorithm/
- Source link:
The algorithm ensures that incoming requests from clients, like those connecting to streaming video services, don't all pile on to one server, overloading it while leaving other servers idle.
Thorup originally [1]co-published an algorithm in 2016 to address this issue. At the time, Vimeo reported it had [2]dramatically reduced its outgoing bandwidth during peak hours .
[3]
He said the new algorithm, developed with Anders Aamand and Jakob Bæk Tejs Knudsen, improves on its predecessor by making sure no server is more than 10 per cent more burdened than others in 10 jumps instead of 100, essentially by limiting a user's movement once placed on the system and retrieving content locally.
[4]GitHub Copilot auto-coder snags emerge, from seemingly spilled secrets to bad code, but some love it
[5]BBC makes switch to AWS, serverless for new website architecture, observers grumble about the HTML
[6]Ex Netflix IT ops boss pocketed $500k+ in bribes before awarding millions in tech contracts
[7]Apple stung for $308m in battle over patent used in FairPlay DRM software
While balancing the load across servers might not seem like such a huge task, it can be quite iterative given that a system can contain up to a billion servers. It is further complicated by the constant joining and leaving of users on the servers.
"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," said Thorup in a [8]canned statement .
[9]
The algorithm will grow in relevance as internet traffic is predicted to triple between 2017 and 2022 with 82 per cent of traffic expected to be made up of online videos next year.
As more of our lives goes online, computer servers increase not only in wear and tear, but also in their energy usage and climate impact. Thorup predicted this problem would grow, but said he believes improved efficiency in data centres will help mitigate the increased usage.
[10]
Thorup and team said they expect major IT companies will deploy the algorithm immediately. They presented their [11]paper [PDF] at The 53rd ACM Symposium on Theory of Computing ( [12]STOC 2021 ) online, which took place 21-25 June. ®
Get our [13]Tech Resources
[1] https://arxiv.org/abs/1608.01350
[2] https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed
[3] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/servers&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=2&c=2YOXPn-rmrhSxafmXzoG9UQAAAIw&t=ct%3Dns%26unitnum%3D2%26raptor%3Dcondor%26pos%3Dtop%26test%3D0
[4] https://www.theregister.com/2021/07/06/github_copilot_autocoder_caught_spilling/
[5] https://www.theregister.com/2020/11/04/bbc_embraces_aws_serverless/
[6] https://www.theregister.com/2021/05/03/netflix_bribery_conviction/
[7] https://www.theregister.com/2021/03/22/apple_loses_308m_patent_case/
[8] https://www.eurekalert.org/pub_releases/2021-07/uoc--dit070621.php
[9] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/servers&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44YOXPn-rmrhSxafmXzoG9UQAAAIw&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[10] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/servers&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44YOXPn-rmrhSxafmXzoG9UQAAAIw&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[11] https://arxiv.org/pdf/2104.05093.pdf
[12] http://acm-stoc.org/stoc2021/
[13] https://whitepapers.theregister.com/
Playing with their balls, in bins
Abstract
In dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any bin but we also want to minimize the number of balls and bins that are affected when adding or removing a ball or a bin. We want a hashing-style solution where we given the ID of a ball can find its bin efficiently.
So server A is less than 10% more burdened than server B. If B has 50, A has 50-55.
Re: Playing with their balls, in bins
It's the "in 10 jumps rathe than 100" part that I don't get.
Whats old is new again
I'm reading a marketing press release.
What they are describing is a bit like the old probes that pulled server metrics such as CPU and RAM when doing weighted load balancing, exactly like we used to do about 20 years ago, yes it levels out load changes from sessions stopping and new ones being added, so nothing new there at all. Same thing with their description of sticky sessions, which seems a bit odd given the move to stateless techniques where possible.
It suggests that people will start using it immediately - well, its decades old so I'd guess some are already
I'm also struggling with the idea of a billion servers for one platform, that seems rather a lot for a world population of 7.9 billion.
But as they say 76.345% of all statistics are made up on the spot.
From my perspective, nothing new here, just a regurgitation of already known problems and already engineered solutions.
> no server is more than 10 per cent more burdened than others in 10 jumps instead of 100,
I've read that about ten times. What?